This adds a new fuzzy string matching functionality to blenlib in BLI_string_search.h.
At the core of the fuzzy matching is the damerau levenshtein distance. However, just using that algorithm does not solve the problem. The rest of the implementation is loosely based on other searches I regularly use (e.g. the one in vscode) and what felt right. Finding "good" matches that make sense to users does not seem to be an exact science (at least I haven't found a good resource yet). The current approach works quite well in my tests, but we might have to fine tune how strings are matched in the future.
Besides normal fuzzy search, "prefix based searching" is supported as well (not sure what this is officially called). This allows us to search for "iat" and get "Install Application Template" or to search for "anitr" and get "Animated Transforms to Deltas".
I updated a couple of different places where we do search to use the new system. That includes:
- F3 search
- ID data block search (e.g. in the material selector)
- Enum search operator (also includes searches added via the Python API)
- Node name search (ctrl+f)
One surprisingly important aspect of this is performance. In release builds performance is perfectly fine (~0-2ms), no issue there. However, debug build performance was not great at first (~100ms after every change). I implemented a couple of tricks to skip computations to make it faster, so it is also perfectly usable in debug builds now, but that is something we have to keep an eye on. In the future we could make things faster by doing some preprocessing at the beginning of each search and/or by using multithreading (which should be relatively easy to use).
The algorithm is utf8 aware in the sense that the fuzzy matching works on code points (1-4 bytes each) instead of individual bytes.