Improve Command Palette search experience for word permutations

[guywaldman]

When searching with the Command Palette, right now you can use fuzzy search which is great.
Searching for "pop stash" or similar will bring up Git: Pop Stash... from the native Git extension.
Searching for "stash pop" however, will not.

I frequently search for "stash pop" instead of "pop stash" and it doesn't match since it expects the word in order. That is just a contrived example, I am sure that there are better ones.

Anyway, not sure whether this is a good idea just in my eyes, but in some cases I think it would be useful if the words could be out of order.
This could be implemented using keywords (for secondary search in case there are no matches) or implementing the out of order functionality. If performance is an issue, you could opt for this search heuristic lazily in cases where there are no results without it.

[bpasero]

Related issues: #27317

[guywaldman]

@bpasero You mind if I try to tackle this in the next few weeks if no one beats me to it?

[bpasero]

Yeah maybe. One fear I always have in this area is that people might have build up muscle memory how command palette works. Now you want to change that filter logic and users that have typed certain commands might now get something totally different selected by default. So I think this can only be a setting for more fuzzy search in commands?

[guywaldman]

Mhm that's an option, an alternative would be maybe to opt-in to keywords only if there would have otherwise not been any search results. This will be "backwards compatible" with the old search.
For example, right now I would search for "stash pop" and no results would appear. In this case where the first search yielded no results, we would use keywords and in the future maybe the two could be consolidated. WDYT?

[guywaldman]

Another option: give the "new" results less weight so they would appear last.

[bpasero]

Yeah that sounds like a good direction. Maybe quickly check what #27317 is talking about already with respect to command palette to gather more ideas:

The filter/sorting logic is here:

vscode/src/vs/platform/quickinput/browser/commandsQuickAccess.ts

Line 63 in b4da98a

// Filter

We typically also want to preserve alphabetical sorting to not confuse muscle memory. That would probably conflict with the idea of putting those results last.

[guywaldman]

I agree 👍

I therefore suggest the following as a one-size-fits-all solution for all the items, would love to hear your thoughts:

Let's denote "old" search results as set A and "new" search results (which would be matched only by the new filtering logic) as set B.
Assume that the new searching logic could overlap with the old one (meaning, will return some of the same results, maybe in a different order) but we will enforce that B will filter out search results that have already appeared (are in A), so A and B would be mutually exclusive. This is so that you will not have duplicates in the search results.

For example, when searching "stash pop", A would contain nothing and B would contain "Git: Pop Stash"

1. Add new filtering logic with a lower weight than A, so that they will appear last in the search
2. From the search items in the previous results, remove what has already appeared in A (this will be our B)
3. Add a new option for the enhanced search experience ("Enhanced Search" or along those lines) that if enabled, will not calculate A and only B will be displayed)
4. Let users try this out and start encouraging migration to the new experience (so that people will build up new muscle memory for their frequent searches)
5. In the future deprecate the old search behavior and enable the enhanced experience by default

Pros:

1. Progressive enhancement - users can have enhanced search experience without their "muscle memory" getting compromised
2. The new experience is opt-in, so this would enable a gradual migration for a new search experience with better fuzzy matching
3. Relatively straight forward to implement

Cons:

1. Degraded search performance. Possible solution if so: if the "Enhanced Search" flag is not enabled, only then would you calculate B only if A contained no results

[bpasero]

Maybe this is too complicated and we should simply allow "foo bar" to match either a command "foo bar" or "bar foo", I wonder how big the change would be in the end. The algorithm would then be:

• separate the query by spaces to get the words of the query
• match each word on the full command name
• require all matches to be present in the command name but not necessarily in the order typed

This is still not fuzzy matching, e.g. typing "gstash" would not match "git stash". I was mainly worried that enabling fuzzy matching would potentially conflict with built muscle memory, but I am less worried about word permutations the more that I think about it?

[bpasero]

Ah ok so we do a bit of fuzzy matching already:

Then maybe the only change and impact is to match in word-independent order.

[guywaldman]

Yep, there is existing fuzzy matching but the requests were for smarter searches e.g. better ranking (#1964, #99685, #14727, #40044), adapative searching (#17697) or customizations (#38841)

[guywaldman]

There is still the problem of users having their "muscle memory" compromised if we implement what you suggested no?

[bpasero]

Yeah you are right, but what if that would only apply if no commands are otherwise found?

[guywaldman]

Yeah that or ranking them lower, after the first ones as I mentioned before, for which no results is a private case. WDYT: only if no results or with less weight?

[bpasero]

The problem with "ranking them lower" is that you suddenly no longer have commands sorted in alphabetic order. We do that on purpose so that commands with the same prefix are close to each other.