x/tools/gopls: support server-side fuzzy matching

[myitcv]

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

$ go version
go version devel +44c9354c5a Fri Jun 21 05:21:30 2019 +0000 linux/amd64
$ go list -m golang.org/x/tools
golang.org/x/tools v0.0.0-20190620191750-1fa568393b23
$ go list -m golang.org/x/tools/gopls
golang.org/x/tools/gopls v0.0.0-20190620191750-1fa568393b23

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="on"
GOARCH="amd64"
GOBIN="/home/myitcv/gostuff/src/github.com/myitcv/govim/cmd/govim/.bin"
GOCACHE="/home/myitcv/.cache/go-build"
GOENV="/home/myitcv/.config/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
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_amd64"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/home/myitcv/gostuff/src/github.com/myitcv/govim/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 -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build615872690=/tmp/go-build -gno-record-gcc-switches"

What did you do?

Raising this following a conversation with @muirrn and @ianthehat

There are a variety of approaches to deciding what completion candidates to offer:

• fuzzy match
• case insensitive
• something very vogue like an AI or ML based approach
• ...

We ultimately, however, need a way for users to configure which method they want.

Whilst there will likely be necessary discussion on what is the most sensible default, this issue is a request to make the option configurable.

The same option could also define the behaviour of functions like #32749, for example

---

cc @stamblerre @ianthehat

[myitcv]

In our discussion @muirrn suggested that the current default method is such that a lowercase partial pattern implies case insensitive candidate selection. However I don't think I'm seeing this:

package main

type S struct{}

func (s *S) Help() {}

func main() {
	var s *S
	s.h
}

Trying to complete s.h results in no completion candidates. If instead this is changed to s.H and completion attempted, Help is correctly returned as the single candidate.

Which seems to suggest that candidate selection is case sensitive.

[muirdm]

Sorry @myitcv, I was talking specifically about the un-merged fuzzy matching logic. Currently gopls has no matching logic at all, it is always an exact prefix match. Editors however can fetch all the candidates when you type s. and then have smart filtering as you continue to type.

[myitcv]

Sorry @myitcv, I was talking specifically about the un-merged fuzzy matching logic. Currently gopls has no matching logic at all, it is always an exact prefix match

Thanks for clarifying.

Editors however can fetch all the candidates when you type s. and then have smart filtering as you continue to type.

This is exactly why I don't think this logic belongs in editors. Because qualified identifier/selector-based completions are only part of the picture. But also because presumably the editors need to keep asking for completion candidates because they can't know when to stop? At which point, gopls might as well do the fuzzy matching bit?

Would this not also give us consistency across editors?

Apologies if part of the reason we're talking past each other here is a difference between the different editor approaches here. My experience is only Vim.

[muirdm]

qualified identifier/selector-based completions are only part of the picture.

I think VSCode works the same for unqualified completions. If you haven't typed anything yet you can manually trigger a completion, or once you type your first character it will fetch the completions and then filter in the editor as you continue typing. Emacs works similarly by default, but LSP completions in Emacs do not currently support fuzzy matching.

presumably the editors need to keep asking for completion candidates

VSCode does not refetch candidates as long as you are still typing in the same identifier. Emacs works the same way normally, but currently it refetches candidates after every keystroke to work around a previous bug.

But, I think we are in agreement in regards to who should be doing the matching. Server side matching should give a better (faster, more consistent) experience overall. The downside is it pushes the various matching preferences/options from the editor into gopls (i.e. gopls might not support the matching/completion options you are used to in your editor).

If you want to try out server side fuzzy matching (as well as deep completions) you can use this branch https://github.com/muirrn/tools/tree/lsp-fuzzy (just rebased on master). Then if you complete something like "conBack" it will complete to "context.Background()" (assuming "context" is already imported). This also works for "deep" completing into structs, so if you have some struct "foo" and you want to access "foo.bar.baz.qux" you can directly type "qux" and complete and it will expand to "foo.bar.baz.qux".

[myitcv]

But, I think we are in agreement in regards to who should be doing the matching.

Yes, indeed.

The downside is it pushes the various matching preferences/options from the editor into gopls

I think it forces the editor (plugin) to map between the two, yes, and tie the two together from the user's perspective. But I don't see that as a problem: editor (plugins) are already having to do this sort of mapping in any case with LSP concepts.

And it should be relatively easy to add additional strategies to the gopls side, if we find a gap.

If you want to try out server side fuzzy matching.... This also works for "deep" completing into structs

I'm very keen to give this a try and see how my brain maps to it! Will try and find some time to do so. Thanks again for your work experimenting with this.

[stamblerre]

I agree that we definitely need fuzzy matching on the server side in gopls (in progress, I'll be adding a fuzzy matching library soon). My worry with it is the same issue of "mapping" between gopls and the editor, particularly VSCode. If there are differences between the VSCode fuzzy matching and the gopls fuzzy matching, it might make for a confusing experience for VSCode users.

[myitcv]

My worry with it is the same issue of "mapping" between gopls and the editor, particularly VSCode

There are other editors out there 😉

This was exactly my point above. If, for any given editor, we find a gap/difference in the strategy expected, we can fill that with an alternate implementation within gopls, driven by config.

I don't think we can try and cover all bases for all editors with a single default.

[stamblerre]

Sorry, I totally phrased that incorrectly. I said VSCode specifically because it's the only editor I knew about that does the fuzzy matching.

There is also a way to force the client to use gopls fuzzy matching - by setting isIncomplete to true in the completion results. That forces the client to ask gopls for completions on every keystroke rather than a single time as VSCode currently does. That might be a reasonable approach to start with, since it's basically what every non-VSCode editor does.

[gopherbot]

Change https://golang.org/cl/184441 mentions this issue: internal/lsp/fuzzy: add fuzzy matching library

[myitcv]

@muirrn - the work in https://go-review.googlesource.com/c/tools/+/190099 looks great.

Is it worth leaving this issue open pending making the option for fuzzy matching independent of deep completions?

[muirdm]

Oops, forgot to tag this issue.

I think we should keep this open until fuzzy matching is "released" (i.e. enabled by default, perhaps with a config flag to disable).

On that note, I've been assuming that everyone wants fuzzy matching, but that sounds like a silly assumption. We need to gather feedback on use cases to disable fuzzy matching, and also detailed feedback on sub-optimal results from the fuzzy algorithm. Maybe we can gather that feedback on this issue as well?

[gopherbot]

Change https://golang.org/cl/192137 mentions this issue: internal/lsp: enable deep completion and fuzzy matching by default

[muirdm]

@myitcv can you kindly try out fuzzy matching on master and see if you think it satisfies this issue?

[myitcv]

@muirrn - sure will. Currently blocked on #33647 but I'll try and do some manual testing to side step that.

[myitcv]

@muirrn - the options for disabling deep completions and fuzzy matching appear to work, thank you. For now, deep completions and fuzzy matching are enabled by default for govim users (pending govim/govim#321)

I've just raised govim/govim#490 to investigate adding support in govim for the gopls server-side fuzzy matching.

If you are happy that server-side fuzzy matching is working, then please do close this issue :)

Thanks for working on this!

[muirdm]

Thanks for testing it out!

please do close this issue

I think this issue can be closed now, but I don't have the power to do it myself :)