Here's my more-or-less formal proposal to accelerate find-in-files (edit: if you don't see the attachment, you need to log in)
(Sorry for not copying the text earlier, I was in some kind of hurry)
In memory (and stored also in disk, of course) we would have a global index of tokens and filenames. To search a string we would first search in the in-memory global token list. The only drawback I see would be the memory consumption, but there has to be a sacrifice (the same old compromise: Disk / memory / speed).
Global Token list:
1: abcd
2: test
3: myClass
4: for
5: class
6: public
Global filename list:
1: main.cpp
2: main.h
3: include/mylib.h
4: libs/mylib.cpp
5: gui/qt/main_gui.cpp
6: ...
local subdirectory index, e.g. /home/me/projects/proj1/src/sdk/search.cbcache
1 (this is for token #1): Files with ids 1,3,4,17,25,30,32,33,41,42,43
2: 2,3,5,10,12,...
3: ...
4: ...
...
(we could encode the ids with base64 to minimize disk usage)
To search for a string, we would follow these steps:
1) Tokenize the search string ("needle") so we have more but smaller needles. We would search the needles in our haystack, this is, the in-memory token list, and see which tokens match. This is the part where we can apply searching full-words, beginning of words, etc. By doing so, we transform our needles into numeric ids that will be searched in the directory indexes.
2) Some tokens will match part of our search string, while other tokens will match other parts. We can make a temporary "dictionary" so that when we search later, we will see if a file (or directory) has the required matches for ALL the tokens we're searching for (ollydbg explains it further).
3) We can have a global index of directories to minimize searching time (see below)
4) Each directory will have a local index of tokens, followed by a list of which files match that token in particular. If we need a match for tokens A and B, and a file has only token A or token B, we will dismiss that file.
Explanation of 3): For the global index of directories: It would be like the per-directory index explained above. The tokens of all the files for a directory will appear in the directory's entry. If this entry cannot match our search tokens, it means that none of the files in the directory will match, either. (However, if a file matches token A only, and another file matches token B only, and we need a file to have both A and B, the directory will trigger a false positive. This is normal, we can still search in the directory index for all the file entries and dismiss the false positives.
5) For all the matching files, notice that we only have POTENTIAL matches. We still could have false positives. This is where we search the contents of each file as we normally do. But to reach this final step we will have already dismissed a big deal of non-matching files and directories, saving us the time to parse each one of them. Also, I'm wondering if we should have a search-on-demand on indexed files, where in the results list we could click and search the particular file. Until then, the file would appear on the search results as "?", indicating that it ONLY PROBABLY matches our search criteria.
Notice that to build these indexes, we need to scan the entire project once, and re-scan each file and rewrite the indexes after each save.
--- end of explanation ---
Please share your opinions
