#8904 closed patch
Case-insensitivy and directory handling for engines
| Reported by: | peres | Owned by: | fingolfin |
|---|---|---|---|
| Priority: | normal | Component: | --Other-- |
| Version: | Keywords: | ||
| Cc: | Game: |
Description
The patch is described in this post on scummvm-devel:
http://sourceforge.net/mailarchive/forum.php?thread_name=op.ue7mvsftag8a5m%40nostro&forum_name=scummvm-devel
Ticket imported from: #2034983. Ticket imported from: patches/1009.
Attachments (11)
Change History (61)
comment:1 by , 16 years ago
by , 16 years ago
| Attachment: | bs2-archive-pre.patch added |
|---|
Changes needed in BS2 before Archive and SearchSet can be used (this is already contained in bs2-archive.patch).
comment:4 by , 16 years ago
bs2-archive-pre holds the changes needed by BS2 so that application of Archive and SearchSet is clean.
Those are mostly changes in the creation of AudioStreams. I tested with the demo, and it worked flawlessly. I hope somebody can give a try to this patch with the full game, too.
This patch is already included in bs2-archive, so there is no need to apply them in sequence.
comment:5 by , 16 years ago
Regarding FSDirectory::lookupCache: Using a case sensitive hashmap means that you have to do a full linear search of the hash to find the match. Bad. That means you are using the wrong data structures, or the wrong approach. Right now, lookups take you O(n), and you would save time and space by just using a Common::Array instead of a HashMap.
"Correct" would be one of these, in my eyes:
EITHER you want to have a case sensitive cache. In that case, use a binary tree for storage; or equivalently, a sorted array of all the entries on which you perform a binary search. That time, lookups take O(log(n)), even if there are clashes.
OR you use a case insensitive HashMap. That way, lookups take O(1). If you want to detect clashes, detect them while creating the cache: In FSDirectory::cacheDirectoryRecursive, you can simply check if a matchin entry already exists, before inserting a new item. If that is so, record that flag. E.g., instead of using a "string->FSNode" map, use a "String->(FSNode, bool)" map, and record in the bool whether there was a clash or not. Or just print out a warning/error while creating the cache, and do not bother to record which file clashed.
Something completly else: You already include nice documentation comments, with only a few tweaks, those could become Doxygen comments... ;)
Finally, you write in a comment: "NOTE: is it sensible/worthy to make SearchSet a subset of Archive" -> Indeed, I think it would make perfect sense to let SearchSet be a subclass of Archive. I don't see a specific application right now, but this simple fact would make it possible to write functions which take an Archive as param, and which you then could use with both FSDirectories, and SearchSets, or ScummArchives, ArjArchives, ZipArchives or whatever.
Lastly: Somehow I am not yet quite satisfied with the name "Archive". Maybe FileGroup? Hrm... Ah well, this is an absolutely minor point :)
comment:6 by , 16 years ago
Oh, and just to offset my previous comment, which maybe sounded overly negative: I think this patch is heading in the right direction and that we are almost there. I really look forward to getting this into SVN and start converting everything to use it :).
comment:7 by , 16 years ago
I noticed that comment about removal of archives from SearchSet and I think it's really something nice to have. Currently I'm implementing a archive based resource loader in kyra. I would consider switching to this approach, but I would really need to remove some archives now and then, so I would *need* a remove functionallity in SearchSet.
Also Kyra has some file clashes sometimes and needs to overwrite files in archives by files in the game dir for example, so some 'priority' based access would be needed.
Another advantage from using this FSDirectory search is that I could reduce the need for Common::File::exists to zero :-) and thus allow faster startup on NDS and other platforms with slow filesystems.
A thing I wonder about the code itself is: "// empty constructor is needed for returning empty objects". Actually I don't think specifying a empty constructor is really needed for that. :-) Very minor though.
Apart I would agree to make SearchSet inherit from Archive.
Bottom line: I'm all for this. And I would adept it in kyra.
comment:8 by , 16 years ago
I posted a new version that includes most of the features we were talking about. I'm not updated the patch for BS2. Just add a new arbitrary string as the first parameter of the calls for SearchSet::add() :)
Archive: * added a pure virtual matchPattern() method * implemented a getAllNames() method, to return a full list of the content
SearchSet: * added remove() * add() now requires a name for each archive * made it a subclass of Archive * implemented matchPattern()
FSDirectory: * added a stub for matchPattern() and a comment about matching strategies * changed caches to be case-insensitive (clash management is done when building cache) * added an _unbound field to be able to tell between instances that are linked or not to real directories File Added: archives-2.zip
comment:9 by , 16 years ago
> Also Kyra has some file clashes sometimes and needs to overwrite files > in archives by files in the game dir for example, so some 'priority' > based access would be needed.
Couldn't you just look first in the game directory for every file you open?
comment:10 by , 16 years ago
Here are some updates. This things seem to be almost ready.
Changes: * renamed files to archive.h and archive.cpp * added doxygen comments * added a new PrioritySearchSet, basically an ordered SearchSet (with adjustable priorities) * removed the unneeded default FSDirectory constructor (thanks to LordHoto)
Notes: * SearchSet and PrioritySearchSet could be merged in a new class that keeps a both a sorted and unsorted list and searches in both. * the implementation of Archive in SearchSet and PrioritySearchSet has a lot of code duplication.
TODO: * decide how to do matching for FSDirectory. Look in the comment for FSDirectory::matchPattern() for a longer explanation. Once this is sorted out, implementation is not hard. File Added: archives-3.zip
comment:11 by , 16 years ago
| Owner: | set to |
|---|
comment:12 by , 16 years ago
Wow, this looks even better now. Will be great to get this into trunk :). Some remarks:
* We could typedef SharedPtr<SeekableReadStream> FileRef; to shorten some code and for convenience of client code authors. Using "File" in the name is consisten with hasFile/openFile, and FileRef won't clash with the existing "File" (once that is gone, we could even rename FileRef to File).
* Why does SearchSet not guarantee an order? I think it should either use the order in which things were added (first added gets priority; that's how SearchSet::openFile work right now); or alternatively the reverse order (things that were added last have priority). For many applications, that may actually be completely sufficient when it comes to priority handling.
* In particular, it is not completely clear to me whether merging SearchSet and PrioritySearchSet is a good idea. The latter seems more complex and incurs overhead which client code won't need.
* But *if* we merge them (e.g. to reduce code duplication), then code which doesn't need priorities should not have to worry about it. So change void PrioritySearchSet::add(const String& name, int priority, SharedPtr<Archive> archive); to void PrioritySearchSet::add(const String& name, SharedPtr<Archive> archive, int priority = 0); or so.
* For FSDirectory, document how clashes are resolved: First found is used, latter matches are ignored; order hence depends on the FSNode code being used, and hence is not well-defined. That should be expected, but mentioning it explicitly is better than letting users guess :)
* You can reduce some code duplication by adding a new internal method ArchiveList::iterator SearchSet::lookupFile(name); which then could be used by both openFile and hasFile.
* You write: "Sadly, we have no means to detect if a constructed node is valid or not. The _unbound field is used to mark instances not linked to a real directory." -> I don't understand that. The way you initialize _unbound, isn't it equivalent to !node.isDirectory() ? So, can't you just change the constructor to always assign node to _node: FSDirectory::FSDirectory(const FilesystemNode &node, int depth) : _node(node), _cached(false), _depth(depth) { } FSDirectory::FSDirectory(const String &name, int depth) : _node(name), _cached(false), _depth(depth) { } Then modify code which checks for !_unbound to just check for "_node.isDirectory()" or even for "_node.isDirectory() && _node.exists()" ?
* I don't get the idea behind FSDirectory::getName() -- what's it good for? If the purpose is to allow code to see from which dir the FSDir object came, wouldn't then a getFSNode() { return _node; } method be much more useful? *And* avoid the _unbound check, too...
* You can simplify lookupCache and create some less temp objects, as follows:
FilesystemNode FSDirectory::lookupCache(NodeCache &cache, const String &name) { // make caching as lazy as possible if (!name.empty()) { cacheDirectory(); if (cache.contains(name)) return cache[name]; }
return FilesystemNode(); }
* Why do FSDirectory::hasFile and ::openFile check for * and ? in the name? If a code is stupid enough to use a pattern in there, he'll notice that this doesn't work quickly enough, by hasFile not returning a match. OTOH, this check makes it impossible to access files which do contain * and ? (right now a theoretical problem only, but still, it seems like an artificial limitation)
* For matchPattern: To decide how this should work, we should first answer the following questions: For what do we need this? What would typical usage examples be? Then, based on use cases, we can decide what it should do, or if it can be axed.
comment:13 by , 16 years ago
Attached a new revision of your code which implements several of my suggestions (I renamed FileRef to FilePtr to be in line with your existing ArchivePtr type). I noticed that my new SearchSet::lookup() is almost the same as your PrioritySearchSet::find. File Added: archive-3-mod.zip
comment:14 by , 16 years ago
I agree with the changes you made to the code. Some of the points in your last post were about some code I had carelessly left-over from previous revisions.
-------------
I take you want any (Priority)SearchSet to be able to contain archives with and without priority.
My implementation did not put any limit to the fantasy of the user with regards to priority values. I guess we could limit this to positive values and keep zero for unprioritized items (and also make higher numbers mean higher priorities). I updated your code to do so (and uploaded archive-4.zip).
We probably want to discard SearchSet and rename PrioritySearchSet now, no?
-------------
Here are the use cases for matchPattern: * gui is using wildcards to look for zip files (themes). * AGI engine looks for *.wag during detection * most (all?) engines when building their save file list * SDL backend looks for *.bmp files to make valid screenshot filenames * Tanoku's branch needs to look for multiple *.stx files in zips.
comment:17 by , 16 years ago
You should try to remove some older patch versions. After that it should work again.
comment:18 by , 16 years ago
(Trying to attach peres' patch, which he emailed me, after removing some older patch versions).
Some remarks: * Yes, merge SearchSet and PrioritySearchSet * Patterns: Savefiles are not regular files, and will not be handled by this class, so strike that from the list of example usages. The same goes for the BMPs in the SDL backend. For the remaining cases, well, they could still use FSNode's directly, without using an Archive class... But if they want to use Archive, I would imagine that they would want to match *all* *.FOO files in the given SearchSet, regardless of how they are nested in dirs. So I'd just match the pattern against the full "key" string.
comment:19 by , 16 years ago
Weird, it says "File Upload: ArtifactFile: Could not open file for writing"
comment:20 by , 16 years ago
I submitted a SF.net SR for this issue, feel free to comment on that if you can confirm the issue: <http://sourceforge.net/tracker/index.php?func=detail&aid=2070259&group_id=1&atid=200001>
comment:22 by , 16 years ago
New (last?) update:
FSDirectory: - implemented full key/pattern match - keys are now stored in lowercase to make pattern matching easier (using Common::matchString)
SearchSet: - removed SearchSet and renamed PrioritySearchSet to SearchSet File Added: archive.zip
comment:23 by , 16 years ago
Updated the patch for BS2, to reflect the development of Archive. File Added: bs2-archive.patch
comment:24 by , 16 years ago
Here's a patch which adopts the Archive/SearchSet API in Kyra.
Some notes:
* SearchSet::add taking an SharedPtr is quite annoying, with that I can not just add SearchSet from inside a class, without using SharedPtr there too (check Kyra::Resource::_archiveFiles and Kyra::Resource::_protectedFiles). Also with that I'm not able to use the DefaultSearchManager proposed in patch #2093502 "DefaultSearchManager", since I can't get a SharedPtr to that, thus I'm unable to add it to my SearchSet (Kyra::Resource::_files). Max proposed using an "Archive *" and an "bool disposeAfterUse" parameter for that.
* Apart I had to add SearchSet::hasArchive, which I already committed with r34397
* For easy subpath addition I would maybe even propose a SearchSet::getArchive, so I can use it to add say the directory 'MALCOLM' later on. Without it I would need to create an FilesystemNode with ConfMan.get("path") as path, then using getChild and then creating FSDirectory again. (Currently I'm not adding 'MALCOLM' as a search path, since our AdvancedDetector doesn't support any sub paths) File Added: kyra_resource_v1.patch
comment:25 by , 16 years ago
Scrap my last point, I totally forgot we don't support dynamic_cast, thus we can't cast a return value from getArchive safely to FSDirectory.
comment:26 by , 16 years ago
[quote] * SearchSet::add taking an SharedPtr is quite annoying ....... Max proposed using an "Archive *" and an "bool disposeAfterUse" parameter for that. [/quote]
Nothing against this. The rationale was to let the engine forget about the objects, but this is an equivalent solution.
[quote] Also with that I'm not able to use the DefaultSearchManager proposed in patch #2093502 "DefaultSearchManager", since I can't get a SharedPtr to that, thus I'm unable to add it to my SearchSet" [/quote]
Now, I don't know if adding the DefaultSearchManager to the SearchSet of an engine would be good, since that object was meant to be used by the middleware. I know Kyra (and others) needs an additional datafile that may be located in the extrapath(s) right now but, unless there are other things that I am not aware of, I would suggest you to directly use the DefaultSearchManager for that.
comment:27 by , 16 years ago
Hm I would really like not to do separate checks once via DefaultSearchManager and once via my own SearchSet. It just bloats the client code of the whole DefaultSearchManger with additional checks, which could be easily hidden when adding the DefaultSearchManager to my SearchSet.
comment:28 by , 16 years ago
Do you need to look in those extra dirs *only* for kyra.dat, or are there other files that might be in extradir / the OS X bundle etc. ? If it's only for "kyra.dat", I don't really see where the bloat comes from -- naively, it would seem you'd have to add a single extra check in a single spot? I.e. by providing an "openKyraDat()" method in a suitable class, or so.
I do see some merits for *not* letting engines search for their files literally everywhere, as we do right now, to be honest.
On the other hand, one use case I mentioned to peres before is that people might want to use the game's extrapath to share huge data files between multiple game variants. Like, to share audio CD tracks between the five language variants of the CD version of Monkey Island 1. So, considering that case, it would be indeed useful to look for all game data in both the game path (and subdirs), as well as the game's extrapath...
Though that would not necessarily require adding the full DefaultSearchManger to the engine's SearchSet.
comment:29 by , 16 years ago
Well the only real use cases are kyra.dat and the fm-towns font rom. The problem is I can not easily provide some "openKyraDat" function. If I would do that, I would always need to load the whole file in memory, which is a bit waste of memory. Of course kyra.dat is only 236KB, but I'm not sure if that would kill maybe kyra3 for NDS, but I don't have any memory usage data for that.
The real problem with kyra.dat is, it's basically just a 'PAK' archive file and all data (read as in file) loading done from it is done via my Resource class, which opens the file on demand and returns a dumped data/read stream for the specific file. So it relies on my own SearchSet _files for loading the archive file. (Check Resource::getFileStream and PlainArchive::openFile). Thus I would need to add branching in Resource::getFileStream so it checks DefaultSearchManager and my SearchSet _files, which I consider bloat instead of just adding DefaultSearchSet to my _files SearchSet.
Apart people might want to share their audio files between Kyra PC98 and FM-Towns and the two different languages supported there. But I thought the CD manager in sound/ would allow that anyway with DefaultSearchManager? Another use case would be sharing the .VRM (speech data archives) in Kyra1 CD between the three different languages.
comment:30 by , 16 years ago
After some talking with peres I would propose the following 'solution' to the confusion/problem with DefaultSearchManager:
* Introduce a DefaultSearchManager, which includes all paths every code is allowed to search.
* Introduce a MiddlewareSearchManager, which includes only paths allowed to be searched by the middleware
* Maybe introduce a EngineSearchManager, which includes all paths which can be searched by the engine (path, extrapath and the OS X bundle path for our engine data files come to mind).
Of course EngineSearchManager might only supply the same paths as DefaultSearchManager, so we could stay just with DefaultSearchManager and MiddlewareSearchManager. And of course we could include DefaultSearchManager into MiddlewareSearchManager and/or EngineSearchManager, when we allow a SearchSet addition without SharedPtr, depending on how we define paths.
This later on would allow me to use EngineSearchManager to include to my own SearchSet and removes the need to 'bloat' (read as in make it more complicated than it should be) the Kyra code.
comment:31 by , 16 years ago
This thread is deviating from its original meaning, so I am posting a patch to get back on track.
Here, I replace the current (as of r34526) implementation of matchPattern() and getAllNames() in Archive and its subclasses with a new approach based on a discussion that has been going along for a while. A snippet from Max's thought follows: [quote] ... a new class which represents members of an Archive. Like, for FSDirs, we could essentially use FSNodes (which we could then base of a new base class, ArchiveMember). Do the same for e.g. ZIPArchives. Then, ... instead of returning somewhat fragile {String, Archive*} pairs, return ArchiveMember objects. [/quote]
About the removal of the old API, I guess we don't need it if it is broken-ish, no? File Added: archivemember.patch
comment:32 by , 16 years ago
Some quick remarks (sorry, no time for a proper review right now :/):
*FSDirectoryMember::getName has a comment saying "I am returning the full path of the node" yet it does return _node.getName(); and not return _node.getPath(); So either the code or the comment should be changed.
* We do this: typedef List<SharedPtr<ArchiveMember> > ArchiveMemberList; so we allocate the ArchiveMembers always on the heap. Any particular reason not to go with typedef List<ArchiveMember> ArchiveMemberList; instead? At least for now that would seem to be more lightweight.
* How about renaming getAllNames to getAllMembers, and to getAllMembersMatching or getMatchingMembers ?
* Fine by me to remove the old API
comment:33 by , 16 years ago
My guess about your first remark is that prolly we have to use a pointer anyway, to allow subclasses to work. And with a plain pointer we would need to define who is responsible for deleting them. Thus SharedPtr, even though a slight memory waste, eases the situation a lot. As I said just my guess though.
by , 16 years ago
| Attachment: | archivemember.patch added |
|---|
ArchiveMember + new implementation of matchPattern and getAllNames. Fixed patch.
comment:34 by , 16 years ago
I updated FSDirectoryMember::getName() to return a the underlying FSNode's path. This was my bad. I'm attaching a new patch with this slight change.
About wrapping ArchiveMember into SharedPtr, the alternative is to use an ArchiveMember*, but then, as LordHoto pointed out, client code would have to deallocate all the returned items. We can't have a List<ArchiveMember> since ArchiveMember is an abstract class (at least in my implementation).
File Added: archivemember.patch
comment:35 by , 16 years ago
You are both of course right on the List bit :). I just find it ugly to have to carry around a shared ptr to a class (FSNode) which essentially itself is nothing but a wrapper around a SharedPtr... But that's once more a minor bit, let's not get distracted.
Some notes: * I would add an explicit implementation of SearchSet::getAllNames(), it's easy to do and speeds up this case * SearchManager is currently unusable: It implement getAllNames() by invoking matchPattern; but it does not implement matchPattern, so the default impl gets used, which works by calling getAllNames -> infinite recursion ;) * As Johannes suggested earlier, you could just subclass SearchManager from SearchSet to save work * rename getAllNames() to getMembers or listMembers * rename matchPattern to list/getMembersMatching or getMatchingMembers
Otherwise, this seems fine to me. Of course, code which implements Archive needs to be adapted (Kyra, ZipArchive)
comment:37 by , 16 years ago
I uploaded a new patch carrying the changes suggested (archivemember-2.patch).
Besides, I explicitly implemented FSDirectory::listMatchingMembers (the old matchPattern), in order to cut down memory allocations. File Added: archivemember-2.patch
comment:39 by , 16 years ago
common/archive.cpp:210: warning: control reaches end of non-void function make: *** [common/archive.o] Error 1
-> seems FSDirectory::listMatchingMembers doesn't count how many items were added to that list :)
by , 16 years ago
| Attachment: | archivemember-2.patch added |
|---|
by , 16 years ago
| Attachment: | archivemember-3.patch added |
|---|
Patch against r34726 (Updated, ZipArchive + KYRA adopted)
comment:41 by , 16 years ago
Ok I attached a patch which updates ZipArchive and Kyra engine to comply to the new API. Also I updated the patch for latest trunk changes. File Added: archivemember-3.patch
comment:42 by , 16 years ago
Look pretty good to me. Only thing to mention: GenericArchiveMember is a bit unsafe (because it won't work if you delete the "parent" archive). This is not a big deal, but this should be clearly and explicitly documented in its doxygen comment, to alert people about this.
Otherwise, feel free to commit this -- assuming it solves LordHoto's problems :)
comment:43 by , 16 years ago
Ok changed the doxygen comment and committed it now.
I guess it's safe to close this tracker entry now, if not feel free to reopen it again.
comment:44 by , 16 years ago
| Status: | new → closed |
|---|
comment:45 by , 16 years ago
I'm reopening this ticket to propose a slight change in FSDirectory: see the attached patch.
I encountered the need for this modification when updating BRA to use Archive and related classes. The problem is rather simple to understand, but I couldn't come up with a short explanation, so please be patient :P
There are about 2400 files in a full version of the game, but only a smaller subset is needed at any time (ranging from 300 to 600 files), so it seems a good idea to use a SearchSet with a wise choice of FSDirectory's, instead of a single FSDirectory. The directory layout for the full PC version of BRA has the data for the 5 sections in the game mapped onto 5 directories. In this simple case, using a single FSDirectory to access the active section data does the trick. Other versions use slightly different layouts, the worst having one or more directories for storing shared data at the game root level. If I used the current FSDirectory for these shared directories, then I couldn't search them using the same strings (in format "path/file") I use for the other data, because FSDirectory caches filenames with their relative path.
So - hoping that the previous long explanation is clear - the change allows client code to customize the 'prefix' parameter that is passed down to cacheDirectoryRecursive(). This way, a string can be prepended to the keys in cache, making searching easier in my case (and possibly others).
comment:46 by , 16 years ago
| Status: | closed → new |
|---|
comment:47 by , 16 years ago
Well, seems fair enough to me. Some details about the implementation, though:
- setPrefix(String::emptyString) is superfluous in the constructor, please remove it - please add a Doxygen comment for the prefix params. They are far from being self-explanatory, I think. In particular, their format should be documented (and possibly examples given).
- also, instead of doubling the number of constructors, how about using:
FSDirectory(const String &name, int depth = 1, const String &prefix = "");
That simplifies things a bit.
And while I am at it, some more problems with class Archive: - ArchiveMember is not documented at all. Given that it's a somewhat arcane part of the system, we really should fix that. - actually, we do not document anywhere how "depth" works for FSDirs, either. I.e. we nowhere document that you can use "foo/bar.txt" as a param to "FSDir::hasFile", and what that means... - finally: Do we really need "FilePtr" ? It seems that class File now does the same job, but in a more convenient form (IMHO).
comment:48 by , 16 years ago
| Status: | new → closed |
|---|
comment:49 by , 16 years ago
I committed the patch and followed most of your suggestions. I retained the additional constructors, though, since prefix and depth are totally orthogonal and it is not clear which should go first (and I am not fond of optional parameters either).
-------------- Sidenote: the new patch tracker interface doesn't let you do 2 things at the same time: either you type a comment, or you close an item.
comment:50 by , 5 years ago
| Component: | → --Other-- |
|---|
Rewrite of the last patch.
An Archive interface has been introduced.
FSDirectory (subclassing Archive) has been implemented, allowing case-insensitive, recursive searches in a directory from the filesystem.
A set of archives - which can be used to search in disjointed directories - has been renamed SearchSet. File Added: archives.zip