Editor "Search Help" fuzzy search results are significantly less helpful

[follower]

---

TL;DR:

Could we please revert/rework #32043 so Editor Search Help results are more helpful? :)

---

Godot version: 3.2.1.stable.official

OS/device including version: N/A (Cross-platform)

Issue description:

I'd been wondering for a while why the editor help search results seemed less...helpful of late.

My initial investigations suggest that the switch to "fuzzy" is_subsequence_of() based search in #32043 has resulted in the decrease of useful results and increase of unhelpful "noise".

Screenshot comparison between Godot 3.1.2 & Godot 3.2.1 searches for terms which I recently searched:

• cache

  • 3.1.2:

  • 3.2.1:

• (Three more examples follow under "details".)

• stor

  • 3.1.2:

  • 3.2.1:

• store

  • 3.1.2:

  • 3.2.1:

• search

  • 3.1.2:

  • 3.2.1:

In particular note:

• The number of results returned (compare relative size of the scrollbar position indicator).

• The "usefulness" of the results returned & initially displayed (compare how the subsequence vs substring search returns many results completely unrelated to the search term--due purely to the frequency of the letter order occurring in other method names etc).

• The abundance of results returned makes it difficult to scan through for the exact substring matches that do exist.

Steps to reproduce:

Use the Editor "Search Help" tool bar button or menu options to search for:

• search

• cache

• stor

• store

Minimal reproduction project: N/A

Observations: Factors affecting suitableness of subsequence-based search

While investigating this issue I observed some factors that seem to influence how effective subsequence-based fuzzy matching is in comparison to strict substring-based matches:

• Searches for known results vs unknown results: I notice the original reason for the addition of is_subsequence_of() functionality was to make it easier to get one specific result: e.g. search for kin2 to get KinematicBody2D, i.e. "search as shortcut" or "fewest characters required to get result".

  In comparison, an "exploration" search where the "correct" result is unknown but perhaps relates to a specific keyword seems less likely to use non-contiguous sequences of characters in the search term.

• Search domain with many long common prefixes vs not: e.g. the characters tic in kinematic don't reduce the number of search results so are redundant in filtering.

  But also, k is also less frequent character so is perhaps not a great test case: e.g. compare ka vs sa or ke vs se.

  (Aside: I just noticed that the result list is longer for ki than for k on its own...)

• UI component/display style: e.g. linear/list display vs tree; multi-panel vs single panel affects effectiveness. This impacts the next factor.

• Filtering vs ranking/scoring/sorting: A linear list can more easily suit a "filter and sort by quality" approach than a tree where the hierarchy makes sorting & changing the order of results more difficult.

Observations: Areas of application

Within Godot "filtering a list or tree of potential results" seems to be used in a number of domains, including:

• Code auto-complete [I feel like there's maybe been a regression here too?]

• Reference documentation

• Node creation filtering

• Settings

Each of these domains are influenced by a different combination of the factors discussed above as to the suitableness of subsequence-search.

(There's also an influence based on the level of experience of a particular individual using Godot which affects the appropriateness.)

There also currently seems to be some level of duplication of code between these domains within Godot which means that improvements that are generally appropriate are only made to one specific feature domain.

Observations: Benefit of before vs after patch screenshots

The contrast in the number/quality of the results returned seem fairly stark in the screenshots I recorded--I wonder if it would be good to more commonly request such before/after screenshots for certain types of patches to more readily identify potential issues such as this.

Related links/issues

• This filter+score ("value substring matches higher than subsequence matches") patch for the "Create Node" dialog seems like it could be more generally applied: "Better pre-selection of search result node in "Create New Node" dialog. #30072"

• The quality/priority of filter/search results seems to be a recurring issue:

  • Source code auto-complete

    • Always display subsequence autocompletion matches #34288

    • Improve code completion search #5196 (Note: Specifically mentions "Sort completion list by similarity.")

    • Fix code completion sorting #5507

    • Improved Code Autocompletion #33650

    • Autocompletion doesn't suggest identifiers that begin differently #33425

    • Autocomplete is inaccurate due to alphabetical sorting of suggestions #21726

    • Added ability to filter code complete options by type (function, class, const, signal, etc) #38449

  • Node creation filtering

    • Search letter-wise instead of word-wise #5109 (Led to original subsequence patch.)

    • In Create New Node, always select and show best (shortest) match #12640

    • Create New Node search inaccurate #26010

  • Editor help / Class Reference

    • Make editor help select shortest (best) instead of first match #13390 (Essentially duplicates fix above from Node creation.) (Includes before & after screenshots! :) )

    • Unified Class and Reference Search 2: Resurrection #23680

    • Unify editor class and reference search #14535 (Where I learned about/was reminded about the list/tree view toggle icon. :) )

  • Project Settings

    • Project Settings search brings weird results #33005 (Partially reverts next one?)

    • Improvements on searching in the settings dialog #30516

    • Improved search in settings dialogs #33047

• is_subsequence_of() related: String.is_subsequence_of is either broken or has a very misleading name #37063

Update: Godot 3.2.2b3

For "completeness" I also just tested with Godot 3.2.2b3 but there doesn't appear to be significant/any difference in results:

• cache:

• stor:

• store:

• search:

[follower]

FWIW I'm still of the opinion that this issue rates being treated as a serious usability regression issue rather than a discussion level issue.

Here's a specific example I just encountered when I wanted to know whether there is a method to return the absolute form of a path (for a non-open file). I knew I had to use the search term abs because the existing methods I knew of use both abs & absolute.

Here's the result in 3.2.1 with the help window stretched vertically as far as it will go (and I'm on a (uncommon but fantastic--highly recommend :) ) 16:10 aspect ratio screen, so it'd be worse on a standard 16:9 aspect ratio screen:

And in 3.1.2 (which I opened in order to actually find out the answer--which is...maybe no?) :

Unless there's very specific sequences of letters that someone with experience might use to find a specific item, returning so many irrelevant results really gets in the way of both new comers & experienced people searching.

If there's substring (rather than subsequence) matches they should take priority. Needing to go back to an older Godot version in order to get useful search results is...not ideal. :)

Reverting #32043 would make the most common scenario usable again and the fuzzy search could be re-worked to take advantage of the sorting/scoring functionality already implemented elsewhere and then reinstated.

[Calinou]

cc @akien-mga

[follower]

It's like a hex has been put on help search:

• v3.1.2:

  

• v3.2.2:

  

On my monitor there's four screens of unhelpful results before the useful results.

[Calinou]

@follower If you want to get the ball rolling, please open a pull request reverting the change.