In command palette, sort matches by quality/exactness

[alederer]

This one sort of speaks for itself if you look at the images. But in brief, this change sorts the command palette results according to closeness to your search term.

After this change

A search for "int" yields "interpolate". Reasonable, that's the only one of the options that actually matches, the others are only fuzzy matches. This is a nice quick way of using the keyboard to get to the interpolate action.

Before this change

A search for "int" doesn't yield any results in the first page that even contain "int"!

Even if you expand the search to "inter", "interpolate" is still toward the bottom. This isn't very helpful.

Details

The specific "cost/score" function has two factors:

• Number of characters interleaved within the search term (i.e. searching for "int", the term "ionot" would have a cost of 2, whereas "innt" would have a cost of 1 and thus win). This is the most important score since it reflects the exactness of the match.
• In the case of a tie in the above score, it uses the number of characters preceding the search term, which helps particularly with short search terms. e.g. "Ease" appears in "increase", but it's probably more relevant to put an action that starts with "Ease" at the top of the search.

Further tie-breaking can be done (I experimented with counting characters after the end of the search term) but doesn't seem relevant (below a certain signal-to-noise-ratio, at a certain point the consistency of the original ordering becomes more valuable than seemingly random tie-breaks).

Caveats

I think this is definitely a good and simple change, but there is a weakness I noted in how I'm calculating the score -- it's using a greedy search, i.e. it considers the needle "found" in the haystack as soon as it encounters its first character, even if the full needle might be found perfectly intact later in the haystack. e.g. searching for "hello" in "hippohello" would be considered to have 5 chars interleaved in the search term ("ippoh"), when it would be more accurate to say it has a perfect match score of 0 because "hello" appears in it directly.

I haven't run into issues with this in practice, but I'd consider it an open area for future improvement.

[alederer]

i've converted to draft because i want to address the following:

• utf8 support, i.e. match by full codepoint rather than by char (previous matching algorithm would give incorrect results here too? investigating)... i guess i need to find some kind of public domain search table to identify "similar letters" across character sets, not looking forward to that
• i found these https://www.unicode.org/Public/security/8.0.0/confusables.txt https://www.unicode.org/Public/security/11.0.0/confusablesSummary.txt
• better matching algorithm (find score of best match rather than score of first match), albeit O(nm)
• visually display matching characters in the palette window (like VSCode and others) (screenshot from VSCode, not implemented yet)
• display keyboard shortcuts

[alederer]

[EDIT: including screenshot of what the command palette looks like with this PR, to avoid confusion]

updated the matching/sorting, added coloring, added shortcut display. i decided the utf8 stuff wasn't worth it, we don't support localized action names anyway, can revisit (i have some initial python code for converting that confusables.txt into a C function).

here's an example of the old greedy matcher vs. the new matcher:

greedy (my initial commit)

where are "move cursor up/down by one" when searching for "one"? their scores are poor because the matcher starts matching at the "o" in "move" and finishes it with the final "e" in "one", so it thinks it has a large distance (along the lines of levenshtein distance but just insertions) from "one".

non-greedy (new)

"move cursor up/down by one" are present near the top because the matcher correctly identifies a "tighter fit" is present than just taking the first fit