rschmitt
commented
9 years ago The only issue with extracting the matcher is the fact that I'm not sure what level of stability I can guarantee. Source compatibility isn't too hard, but there are lots of ways to tweak a fuzzy matcher (Heatseeker's smart case, Selecta's boundary matching): I'd have to do one of the following:
- Create a very general, highly configurable matching engine
- Stop changing Heatseeker's matching
- Regularly change the matching crate's scoring algorithm
- Not actually use the matching crate in Heatseeker, but rather essentially fork my own library
There are also some stability issues with Rust's scoped threads, which were recently removed from the standard library after they were discovered to be unsound. I'm not sure what the story will be in the future for data parallelism, which is why it's not as simple as "take an optional thread pool."
SirVer
focusaurus
Sorry, this is kind of a brain dump. I hope you'll help me turning your tool into the core fuzzy matcher of my editor WIP. Otherwise I need to reinvent the wheel again :)
Background
Fuzzy matching is a common task and useful in many places. My use case is a better Vim like editor (https://github.com/swiboe/swiboe) which I feel driven to write after being fed up with Vim's (and other editors) shortcomings over the last 7 years writing and maintaining one of Vim's most popular plugins.
Suggested design changes
I outlined an implementation for a fuzzy matcher to test the basic design of Swiboe here. The lessons I learned so far are the following:
What you match is not what you want.
What I mean is that a potential match candidate has a text - displayed to the user and used for scoring. But when it is selected, it might return another value to the caller of the matcher - for example I might match for filenames under a certain directory, but want a fully sanitized absolute path back.
Related, a matching candidate should contain additional information - for example for a UI to display. Continuing with the file path example, you might want to attach if the file is new, added or edited inside a git repository - since the gui will draw it differently.
I think the easiest way of achieving this is to introduce a Candidate struct (as I did in my toy implementation), but make it generic over some user data T that can be queried and contain all this additional information.
Multi threaded matching and optimizations
I tested my toy matcher on ~300k of files and realized that in such cases parallel matching on many CPUs is needed. I think the library should take an optional thread pool on construction or query time and use it to match on many cores.
Related: A big optimization that i stole from YCM's matcher and I am not sure if heatseeker implements is to do a cheap filtering on the characters for each match, before doing the full subsequence match. This works like this: we use a bitset with 127 entries (ASCII only, but that does not mean it does not work for utf, it just means that all strings with utf have to be matched all the time) and set each bit for each character in the string. If a candidate has a zero where a query has a one, the candidate does not need to be matched. This comparison is super fast. If you are interested, this optimization is implemented in my toy matchers.