x/tools/gopls: Symbols: use Levenshtein distance for ranking

[adonovan]

I just sought the symbol testincreemntalnope and got an empty result, even though TestIncrementalNope exists. It's 2025, I shouldn't have to spell correctly. Let's rank candidates by Levenshtein distance from the search term and include the closest n results.

See Starlark's spell.Nearest for an implementation we can use.

[mihir7121]

Hi @adonovan — I’d like to work on this issue and have been exploring integration options for using Levenshtein distance to improve symbol search tolerance in gopls.

There are a couple of viable approaches here, and I wanted to get your input before submitting a CL:

Option A: Enhance Existing SymbolFuzzy
Integrate Levenshtein as a fallback within the existing SymbolFuzzy matcher, used only when:

• the fuzzy matcher returns a low score or no match,
• and the Levenshtein distance is within a tunable threshold (e.g. ≤ 3–4).

Option B: Introduce a New Matcher (e.g., SymbolLevenshtein)
Define a separate SymbolMatcher variant to isolate Levenshtein-based scoring. This would preserve the current SymbolFuzzy semantics and allow opt-in use or experimentation.

[adonovan]

I’d like to work on this issue

Thanks @mihir7121 .

There are a couple of viable approaches here, and I wanted to get your input before submitting a CL:
Option A: Enhance Existing SymbolFuzzy
Integrate Levenshtein as a fallback within the existing SymbolFuzzy matcher, used only when:
the fuzzy matcher returns a low score or no match,
and the Levenshtein distance is within a tunable threshold (e.g. ≤ 3–4).

I think Levenshtein should be incorporated into the existing fuzzy.Matcher.computeScore method, since that's the default and thus what 99% of users use. It's possible that the existing algorithm is already somewhat like Levenshtein and thus it needs some careful reading of the existing code and analysis of the ways it falls short: perhaps the solution is a small tweak to the existing logic rather bolting a completely different algorithm on the side.