Change Details

This adds a new fuzzy string matching functionality to blenlib in `BLI_string_matching.h`. The new `BLI_string_matching_filter_and_sort` function takes a query string and many possible result strings. It will return an array of indices that match the query. The returned array is sorted by match quality. At the core of the fuzzy matching is the [[ https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance | 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". So far I only implemented this functionality in the F3 search. However, given that this is a library in blenlib, it should be relatively easy to use the same code for other searches as well. 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.

This adds a new fuzzy string matching functionality to blenlib in `BLI_string_matchingsearch.h`. The new `BLI_string_matching_filter_and_sort` function takes a query string and many possible result strings. It will return an array of indices that match the query. The returned array is sorted by match quality. At the core of the fuzzy matching is the [[ https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance | 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". So far I only implemented this functionality inI updated a couple of different places where we do search to use the F3 searchnew system. However,That includes: * F3 search * ID data block search (e.g. givein that this is a library in blenlib, it should be relatively easy to usee material selector) * Enum search operator (also includes searches added via the same code for otherPython API) * Node name searches as well. (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.