Broken fuzzy search algorithm in picker

[fabiospampinato]

The fuzzy search algorithm can be improved to solve all problems listed in #27317, but IMHO it's completely broken and it should be rewritten from scratch. Let me show you some of the errors I've found:

Doesn't work with leading spaces

This is the expected behavior:

This is what happens if the strings have some leading spaces (useful for extensions like Projects+ for showing a tree-like structure):

Not really "fuzzy"

As I understand it, the term "fuzzy" in "fuzzy search" basically means that the characters provided in the search query can have 0 or more other arbitrary characters between them in the matching string. The current algorithm looks like regular search instead:

Overly strict about string position

For some reasons there are strings that match against some queries, but don't mach against less specific versions of those queries. I mean, a more specific query should provide the same or less results, not more, right?

[bpasero]

@fabiospampinato some of this can be explained by the fact that fuzzy search is NOT enabled for the normal picker (see #34088). Currently we have it only enabled for the file search because it still needs to be tweaked. I need to check for the leading whitespace issue but it may be related to the same cause.

[bpasero]

@fabiospampinato trying to reproduce the issue with leading white space but I cannot:

Is there any way I could try it on the code that you used for your animation to reproduce the same?

[fabiospampinato]

@bpasero Try prefixing those strings with exactly 8 spaces. For whatever reason the bug doesn't manifest itself with just 4 spaces in my system.

If it doesn't work, install Projects+, run Projects: Edit Configuration and paste this:

{
  "groups": [
    {
      "name": "open",
      "groups": [
        {
          "name": "vscode",
          "projects": [
            {
              "name": "vscode-projects-plus-todo-plus",
              "path": "/"
            },
            {
              "name": "vscode-todo-plus",
              "path": "/"
            }
          ]
        }
      ]
    }
  ]
}

Then run Project: Open and try it again.

It would be weird if it still doesn't work.

[bpasero]

@fabiospampinato thanks, I can reproduce now.

[fabiospampinato]

@bpasero Here there's another bug, in the following gif I hit down 2 times and then up 2 times and nothing gets selected instead of selecting the last item:

When will this bugs be resolved?

[bpasero]

@fabiospampinato I think that one is fixed already in our latest insider build, can you check

[fabiospampinato]

@bpasero It's fixed. Thank you.

[bpasero]

/duplicate #34088

[vscodebot]

This issue has been closed because it is already tracked by another issue. See also our GitHub issues to search for existing issues and our issue reporting guidelines.

Happy Coding!