Adding Fuzzy-Match to the Structure Viewer

[tajmone]

I find the Structure Viewer of PureBasic IDE an extremely useful tool, but I always though that it would greatly benefit from a fuzzy-match search box (Sublime Text like) allowing to quickly find structures, constants and interfaces with a few keystrokes, especially when one is unsure about the correct identifier name of what he/she's looking up.

Currently, in order to focus the entries list on the item you're looking for, you need to get all its initial letters correctly, in the right sequence, and if you misspell a single letter the search ends in failure. Fuzzy matching would allow reducing the list entries with every stroke, eliminating all candidates that don't possibly match the typed characters, listing only matching results, which are sorted by match scores.

I've created a repository dedicated to fuzzy matching algorithms:

• https://github.com/tajmone/fuzzy-search

Right now, the repository contains a single algorithm, fts_fuzzy_match by Forrest Smith, a simple yet effective algorithm that would work just fine for the goal at hand. In my repository I've collected various ports of the algorithm to other languages, which should simplify porting it to PureBasic.

I had planned to port it to PureBasic myself, but have procrastinated to do so for a couple of reasons:

1. The repository doesn't yet provide sample results from the original algorithm, which would allow to verify that the ported version is behaving as expected by comparing the fuzzy-match results between the two, using the same dataset and query string.
2. The algorithm (especially v2, the improved version) relies heavily on recursive function calls. Since the PureBasic compiler doesn't provide tail call elimination code optimization, the algorithm should be written tail-recursively from the onset, to avoid bloating the stack and eating up memory with excessive stack frames.

References

Fuzzy matching:

• Reverse Engineering Sublime Text’s Fuzzy Match — article by Forrest Smith, 2016, 2017.

Tail recursion:

• Wikipedia » Tail call
• GeeksforGeeks » Tail Recursion — tutorial.
• GeeksforGeeks » Tail Call Elimination — tutorial.
• StackOverflow » What is tail recursion?
• Programming in Lua » §6.3 – Proper Tail Calls