Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

x/tools/gopls: workspace symbol results appear imprecise and unstable #50016

Open
myitcv opened this issue Dec 7, 2021 · 16 comments
Open

x/tools/gopls: workspace symbol results appear imprecise and unstable #50016

myitcv opened this issue Dec 7, 2021 · 16 comments

Comments

@myitcv
Copy link
Member

@myitcv myitcv commented Dec 7, 2021

What version of Go are you using (go version)?

$ go version
go version go1.17.3 linux/arm64
$ go list -m golang.org/x/tools
golang.org/x/tools v0.1.9-0.20211203185511-c882a49eac7c
$ go list -m golang.org/x/tools/gopls
golang.org/x/tools/gopls v0.0.0-20211203185511-c882a49eac7c

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GO111MODULE=""
GOARCH="arm64"
GOBIN="/home/myitcv/dev/cuelang/bin"
GOCACHE="/home/myitcv/.cache/go-build"
GOENV="/home/myitcv/.config/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="arm64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/home/myitcv/gostuff/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/myitcv/gostuff"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/home/myitcv/gos"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/home/myitcv/gos/pkg/tool/linux_arm64"
GOVCS=""
GOVERSION="go1.17.3"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/home/myitcv/dev/cuelang/cue/go.mod"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build251903034=/tmp/go-build -gno-record-gcc-switches"

What did you do?

  • Start with a fresh clone of the https://github.com/cue-lang/cue repository. For reference, I was working against 28b42576ce831209f4dd796d3515f16f784ba570.
  • Initiate a workspace symbol search using the query cue.Value
  • Observe the results

What did you expect to see?

Stable results, with cuelang.org/go/cue.Value as the result with the highest score

What did you see instead?

Variously unstable results (highest score at the bottom, fzf-UX):

...
  cuelang.org/go/internal/core/adt.ValueReference
  cuelang.org/go/internal/core/adt.ValueError
  cuelang.org/go/cue.ValueAttr
  cuelang.org/go/internal/core/subsume.Value
  cuelang.org/go/internal/types.Value
  cuelang.org/go/encoding/openapi.value
  cuelang.org/go/internal/encoding.valueToFile
  cuelang.org/go/cue.valueError
  cuelang.org/go/cue.valueSorter
  cuelang.org/go/pkg/list.valueSorter
  cuelang.org/go/cue.valueScope
  cuelang.org/go/cue.Value
> cuelang.org/go/cue.valueToSel
...
  cuelang.org/go/internal/core/adt.Value
  cuelang.org/go/internal/types.Value
  cuelang.org/go/cue.valueSorter
  cuelang.org/go/internal/core/adt.ValueError
  cuelang.org/go/internal/core/adt.valueError
  cuelang.org/go/cue.valueScope
  cuelang.org/go/cue.Value
  cuelang.org/go/cue.valueError
  cuelang.org/go/encoding/openapi.value
  cuelang.org/go/internal/encoding.valueToFile
  cuelang.org/go/cue.valueToSel
  cuelang.org/go/internal/core/subsume.Value
  cuelang.org/go/cue.ValueAttr
  cuelang.org/go/internal/core/adt.ValueClause
  cuelang.org/go/internal/core/adt.ValueReference
  cuelang.org/go/internal/core/export.Value
  cuelang.org/go/encoding/protobuf/pbinternal.ValueType
> cuelang.org/go/pkg/list.valueSorter

Logfile from a session in which I ran three such queries:

gopls.log


cc @findleyr

FYI @leitzler

@findleyr
Copy link
Contributor

@findleyr findleyr commented Dec 7, 2021

Thanks for the report -- it looks clearly like we're not scoring the final path component well enough.

Do you have any settings altering the default behavior of workspace symbols?

@myitcv
Copy link
Member Author

@myitcv myitcv commented Dec 7, 2021

Do you have any settings altering the default behavior of workspace symbols?

From the log I included, I think these are the relevant ones?

"initializationOptions":{"allowModfileModifications":true,"symbolMatcher":"fuzzy","symbolStyle":"full"}

@findleyr
Copy link
Contributor

@findleyr findleyr commented Dec 7, 2021

Right, I could have looked at the log :)

Yes, those are the settings in question, thanks.

@myitcv
Copy link
Member Author

@myitcv myitcv commented Dec 7, 2021

Right, I could have looked at the log :)

No worries at all. I actually stopped short of trying to detail the settings in the original description because I knew the log would do a better job!

@hyangah hyangah removed this from the Unreleased milestone Dec 13, 2021
@hyangah hyangah added this to the gopls/unplanned milestone Dec 13, 2021
@hyangah hyangah assigned findleyr and unassigned findleyr Dec 13, 2021
@hyangah hyangah removed this from the gopls/unplanned milestone Dec 16, 2021
@hyangah hyangah added this to the gopls/v0.7.5 milestone Dec 16, 2021
@findleyr findleyr self-assigned this Jan 7, 2022
@gopherbot
Copy link

@gopherbot gopherbot commented Jan 7, 2022

Change https://golang.org/cl/376360 mentions this issue: internal/lsp/source: sort workspace symbol results for stability

@gopherbot
Copy link

@gopherbot gopherbot commented Jan 7, 2022

Change https://golang.org/cl/376362 mentions this issue: internal/lsp/source: parse symbol queries when using fastfuzzy

@gopherbot
Copy link

@gopherbot gopherbot commented Jan 7, 2022

Change https://golang.org/cl/376361 mentions this issue: internal/lsp/fuzzy: consider whole word matching in SymbolMatcher

@myitcv
Copy link
Member Author

@myitcv myitcv commented Jan 10, 2022

@findleyr I tried searching for the symbol cue.Value using https://go.googlesource.com/tools refs/changes/61/376361/1 and got the following results (that appear to be stable):

...
  cuelang.org/go/cue.Value
  cuelang.org/go/cue.ValueAttr
  cuelang.org/go/cue.valueError
  cuelang.org/go/cue.valueScope
  cuelang.org/go/cue.valueToSel
  cuelang.org/go/cue.valueSorter
  cuelang.org/go/internal/types.Value
  cuelang.org/go/pkg/list.valueSorter
  cuelang.org/go/encoding/openapi.value
  cuelang.org/go/internal/core/adt.Value
  cuelang.org/go/internal/core/export.Value
  cuelang.org/go/internal/core/subsume.Value
  cuelang.org/go/internal/core/adt.ValueError
  cuelang.org/go/internal/core/adt.valueError
  cuelang.org/go/internal/core/adt.ValueClause
  cuelang.org/go/internal/encoding.valueToFile
  cuelang.org/go/internal/core/adt.ValueReference
> cuelang.org/go/encoding/protobuf/pbinternal.ValueType

(again highest score at the bottom)

So this doesn't appear to be quite right to my mind at least?

@findleyr
Copy link
Contributor

@findleyr findleyr commented Jan 10, 2022

@myitcv could you try with "symbolMatcher": "fastfuzzy"? I am planning to make that the default, so concentrated my efforts on improving it rather than "fuzzy".

@findleyr
Copy link
Contributor

@findleyr findleyr commented Jan 10, 2022

For reference, here's what I get with the fastfuzzy matcher at that CL. I can explain the scoring of these results pretty precisely, so please let me know if you think there's a strong context-free case for better scoring.

> gopls workspace_symbol -matcher=fastfuzzy "cue.Value" 2>/dev/null | head -n 20
/home/rfindley/src/cue/cue/types.go:556:6-11 cue.Value Struct
/home/rfindley/src/cue/cue/builtinutil.go:19:6-17 cue.valueSorter Struct
/home/rfindley/src/cue/cue/path.go:494:6-16 cue.valueToSel Function
/home/rfindley/src/cue/cue/types.go:583:6-16 cue.valueScope Class
/home/rfindley/src/cue/cue/errors.go:40:6-16 cue.valueError Struct
/home/rfindley/src/cue/cue/attribute.go:103:2-11 cue.ValueAttr Constant
/home/rfindley/src/cue/cue/types.go:97:6-23 cue.hiddenStructValue Class
/home/rfindley/src/cue/cue/types_test.go:2265:6-21 cue.TestValueLookup Function
/home/rfindley/src/cue/cue/instance.go:32:6-21 cue.InstanceOrValue Interface
/home/rfindley/src/cue/cue/types.go:676:6-20 cue.makeChildValue Function
/home/rfindley/src/cue/cue/types.go:633:6-19 cue.newChildValue Function
/home/rfindley/src/cue/cue/types_test.go:114:6-19 cue.TestValueType Function
/home/rfindley/src/cue/cue/types.go:624:6-18 cue.newValueRoot Function
/home/rfindley/src/cue/cue/types_test.go:2348:6-18 cue.TestValueDoc Function
/home/rfindley/src/cue/cue/types.go:90:6-17 cue.structValue Struct
/home/rfindley/src/cue/cue/types.go:691:6-17 cue.remakeValue Function
/home/rfindley/src/cue/cue/types.go:602:6-17 cue.newErrValue Function
/home/rfindley/src/cue/cue/types.go:594:6-17 cue.hiddenValue Class
/home/rfindley/src/cue/cue/types.go:666:6-15 cue.makeValue Function
/home/rfindley/src/cue/cue/types_test.go:863:6-13 cue.goValue Function

@findleyr
Copy link
Contributor

@findleyr findleyr commented Jan 10, 2022

I should add: in my case the highest scoring results are at top!

@myitcv
Copy link
Member Author

@myitcv myitcv commented Jan 10, 2022

Ah thanks! That looks better.

Just to observe however that a search criteria of cue.Val returns longer matches in preference to shorter ones:

...
  cuelang.org/go/cuego.Validate
  cuelang.org/go/cue.Value
  cuelang.org/go/cue.ValueAttr
  cuelang.org/go/cue.valueError
  cuelang.org/go/cue.valueScope
  cuelang.org/go/cue.valueToSel
> cuelang.org/go/cue.valueSorter

(again, best match at bottom)

That doesn't feel quite right to me?

@findleyr
Copy link
Contributor

@findleyr findleyr commented Jan 10, 2022

Just to observe however that a search criteria of cue.Val returns longer matches in preference to shorter ones:

Err, embarrassingly I broke the tie the wrong way: I intended to do the opposite and prefer shorter. Patching, along with a proper test. Nice catch!

@gopherbot
Copy link

@gopherbot gopherbot commented Jan 10, 2022

Change https://golang.org/cl/377434 mentions this issue: internal/lsp/source: use the fastfuzzy matcher in experimental mode

@findleyr
Copy link
Contributor

@findleyr findleyr commented Jan 10, 2022

Ok, the stack to improve this is mailed, although I don't go so far as to enable the fastfuzzy matcher by default. Since this is going to take some days to review and merge, and then some additional time to let the fastfuzzy matcher soak, this probably isn't going to make v0.7.5. Remilestoning for v0.8.0.

As for why I only fixed this in the 'fastfuzzy' matcher: this matcher is knowledgeable about the structure of Go symbols, and so can do things like prefer matches further to the right of the fully qualified symbol string. This ends up being significantly more performant than trying to make a naive fuzzy matcher work for our purposes. The fastfuzzy matcher also just does a naive linear algorithm (not guaranteed to produce the highest score), which is sufficient for symbol matches, and is easier to maintain.

@findleyr findleyr removed this from the gopls/v0.7.5 milestone Jan 10, 2022
@findleyr findleyr added this to the gopls/v0.8.0 milestone Jan 10, 2022
@myitcv
Copy link
Member Author

@myitcv myitcv commented Jan 10, 2022

gopherbot pushed a commit to golang/tools that referenced this issue Jan 11, 2022
Add additional order invariants to workspace symbol results to
differentiate between items of equal score: sort next by symbol length,
and then finally by lexical ordering.

For golang/go#50016

Change-Id: Ic5cda2628f57cecfe972b7585525c49b0f8518bf
Reviewed-on: https://go-review.googlesource.com/c/tools/+/376360
Trust: Robert Findley <rfindley@google.com>
Run-TryBot: Robert Findley <rfindley@google.com>
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Paul Jolly <paul@myitcv.org.uk>
gopherbot pushed a commit to golang/tools that referenced this issue Jan 19, 2022
In the new SymbolMatcher, add an additional scoring feature that
considers whether the matching pattern streak is part of a whole-word
match. This differentiates matches of "foo" against "pkg.foo" and
"pkg.foobar".

For golang/go#50016

Change-Id: Ib84ff13eee0b7ec23143325592cef9a41be07375
Reviewed-on: https://go-review.googlesource.com/c/tools/+/376361
Trust: Robert Findley <rfindley@google.com>
Run-TryBot: Robert Findley <rfindley@google.com>
Reviewed-by: Peter Weinberger <pjw@google.com>
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
gopherbot pushed a commit to golang/tools that referenced this issue Jan 19, 2022
Hook up the fastfuzzy symbol matcher to our fzf-style query parsing, for
consistency with the (slow) fuzzy matcher.

In the past I had wanted to implement this natively inside the
SymbolMatcher, but it is much simpler to keep using combinators. In the
common case we'll just be using fuzzy matching.

For golang/go#50016

Change-Id: I1c62c8c8e9d29da570cb1e4034c2b10782529081
Reviewed-on: https://go-review.googlesource.com/c/tools/+/376362
Trust: Robert Findley <rfindley@google.com>
Run-TryBot: Robert Findley <rfindley@google.com>
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Peter Weinberger <pjw@google.com>
gopherbot pushed a commit to golang/tools that referenced this issue Jan 19, 2022
The fastfuzzy matcher is around 3x faster than the fuzzy matcher for
queries that need to search a large number of symbols, and has improved
scoring due to built-in knowledge about the structure of Go symbols.

Enable it in experimental builds of gopls, with plans to enable it by
default in the next release.

For golang/go#50016

Change-Id: Ie2c333f248bb8397d92f52fbbfdd2bf623372d0a
Reviewed-on: https://go-review.googlesource.com/c/tools/+/377434
Trust: Robert Findley <rfindley@google.com>
Run-TryBot: Robert Findley <rfindley@google.com>
Reviewed-by: Hyang-Ah Hana Kim <hyangah@gmail.com>
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants