internal/lsp: add fuzzy completion matching
Make use of the existing fuzzy matcher to perform server side fuzzy
completion matching. Previously the server did exact prefix matching
for completion candidates and left fancy filtering to the
client. Having the server do fuzzy matching has two main benefits:
- Deep completions now update as you type. The completion candidates
returned to the client are marked "incomplete", causing the client
to refresh the candidates after every keystroke. This lets the
server pick the most relevant set of deep completion candidates.
- All editors get fuzzy matching for free. VSCode has fuzzy matching
out of the box, but some editors either don't provide it, or it can
be difficult to set up.
I modified the fuzzy matcher to allow matches where the input doesn't
match the final segment of the candidate. For example, previously "ab"
would not match "abc.def" because the "b" in "ab" did not match the
final segment "def". I can see how this is useful when the text
matching happens in a vacuum and candidate's final segment is the most
specific part. But, in our case, we have various other methods to
order candidates, so we don't want to exclude them just because the
final segment doesn't match. For example, if we know our candidate
needs to be type "context.Context" and "foo.ctx" is of the right type,
we want to suggest "foo.ctx" as soon as the user starts inputting
"foo", even though "foo" doesn't match "ctx" at all.
Note that fuzzy matching is behind the "useDeepCompletions" config
flag for the time being.
Change-Id: Ic7674f0cf885af770c30daef472f2e3c5ac4db78
Reviewed-on: https://go-review.googlesource.com/c/tools/+/190099
Run-TryBot: Rebecca Stambler <rstambler@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Rebecca Stambler <rstambler@golang.org>
diff --git a/internal/lsp/completion.go b/internal/lsp/completion.go
index 2901ce0..9b8e5da 100644
--- a/internal/lsp/completion.go
+++ b/internal/lsp/completion.go
@@ -8,7 +8,6 @@
"context"
"fmt"
"sort"
- "strings"
"golang.org/x/tools/internal/lsp/protocol"
"golang.org/x/tools/internal/lsp/source"
@@ -40,7 +39,9 @@
log.Print(ctx, "no completions found", tag.Of("At", rng), tag.Of("Failure", err))
}
return &protocol.CompletionList{
- IsIncomplete: false,
+ // When using deep completions/fuzzy matching, report results as incomplete so
+ // client fetches updated completions after every key stroke.
+ IsIncomplete: s.useDeepCompletions,
Items: s.toProtocolCompletionItems(ctx, view, m, candidates, params.Position, surrounding),
}, nil
}
@@ -59,9 +60,7 @@
Start: pos,
End: pos,
}
- var prefix string
if surrounding != nil {
- prefix = strings.ToLower(surrounding.Prefix())
spn, err := surrounding.Range.Span()
if err != nil {
log.Print(ctx, "failed to get span for surrounding position: %s:%v:%v: %v", tag.Of("Position", pos), tag.Of("Failure", err))
@@ -75,14 +74,12 @@
}
}
- var numDeepCompletionsSeen int
+ var (
+ items = make([]protocol.CompletionItem, 0, len(candidates))
+ numDeepCompletionsSeen int
+ )
- items := make([]protocol.CompletionItem, 0, len(candidates))
for i, candidate := range candidates {
- // Match against the label (case-insensitive).
- if !strings.HasPrefix(strings.ToLower(candidate.Label), prefix) {
- continue
- }
// Limit the number of deep completions to not overwhelm the user in cases
// with dozens of deep completion matches.
if candidate.Depth > 0 {
@@ -98,6 +95,7 @@
if s.insertTextFormat == protocol.SnippetTextFormat {
insertText = candidate.Snippet(s.usePlaceholders)
}
+
item := protocol.CompletionItem{
Label: candidate.Label,
Detail: candidate.Detail,
diff --git a/internal/lsp/fuzzy/matcher.go b/internal/lsp/fuzzy/matcher.go
index a38a6b4..0ae2137 100644
--- a/internal/lsp/fuzzy/matcher.go
+++ b/internal/lsp/fuzzy/matcher.go
@@ -203,17 +203,7 @@
// The input passes the simple test against pattern, so it is time to classify its characters.
// Character roles are used below to find the last segment.
m.roles = RuneRoles(candidate, m.input, m.rolesBuf[:])
- if m.input != Text {
- sep := len(candidateLower) - 1
- for sep >= i && m.roles[sep] != RSep {
- sep--
- }
- if sep >= i {
- // We are not in the last segment, check that we have at least one character match in the last
- // segment of the candidate.
- return bytes.IndexByte(candidateLower[sep:], m.patternLower[len(m.pattern)-1]) != -1
- }
- }
+
return true
}
@@ -267,12 +257,6 @@
// By default, we don't have a match. Fill in the skip data.
m.scores[i][j][1] = minScore << 1
- if segmentsLeft > 1 && j == pattLen {
- // The very last pattern character can only be matched in the last segment.
- m.scores[i][j][0] = minScore << 1
- continue
- }
-
// Compute the skip score.
k := 0
if m.scores[i-1][j][0].val() < m.scores[i-1][j][1].val() {
diff --git a/internal/lsp/fuzzy/matcher_test.go b/internal/lsp/fuzzy/matcher_test.go
index 49f1caa..4df65dc 100644
--- a/internal/lsp/fuzzy/matcher_test.go
+++ b/internal/lsp/fuzzy/matcher_test.go
@@ -111,7 +111,7 @@
input: fuzzy.Filename,
tests: []scoreTest{
{"sub/seq", ge, 0},
- {"sub/seq/end", eq, -1},
+ {"sub/seq/end", ge, 0},
{"sub/seq/base", ge, 0},
},
},
@@ -120,7 +120,7 @@
input: fuzzy.Filename,
tests: []scoreTest{
{"//sub/seq", ge, 0},
- {"//sub/seq/end", eq, -1},
+ {"//sub/seq/end", ge, 0},
{"//sub/seq/base", ge, 0},
},
},
@@ -242,10 +242,10 @@
{p: "edt", str: "foo.Textedit", want: "", input: fuzzy.Symbol}, // short middle of the word match
{p: "edit", str: "foo.Textedit", want: "foo.Text[edit]", input: fuzzy.Symbol},
{p: "edin", str: "foo.TexteditNum", want: "foo.Text[edi]t[N]um", input: fuzzy.Symbol},
- {p: "n", str: "node.GoNodeMax", want: "node.Go[N]odeMax", input: fuzzy.Symbol},
- {p: "N", str: "node.GoNodeMax", want: "node.Go[N]odeMax", input: fuzzy.Symbol},
+ {p: "n", str: "node.GoNodeMax", want: "[n]ode.GoNodeMax", input: fuzzy.Symbol},
+ {p: "N", str: "node.GoNodeMax", want: "[n]ode.GoNodeMax", input: fuzzy.Symbol},
{p: "completio", str: "completion", want: "[completio]n", input: fuzzy.Symbol},
- {p: "completio", str: "completion.None", want: "[completi]on.N[o]ne", input: fuzzy.Symbol},
+ {p: "completio", str: "completion.None", want: "[completio]n.None", input: fuzzy.Symbol},
}
func TestFuzzyMatcherRanges(t *testing.T) {
diff --git a/internal/lsp/source/completion.go b/internal/lsp/source/completion.go
index bd74eb2..eb72cec 100644
--- a/internal/lsp/source/completion.go
+++ b/internal/lsp/source/completion.go
@@ -9,6 +9,7 @@
"go/ast"
"go/token"
"go/types"
+ "strings"
"golang.org/x/tools/go/ast/astutil"
"golang.org/x/tools/internal/lsp/fuzzy"
@@ -112,6 +113,25 @@
lowScore float64 = 0.01
)
+// matcher matches a candidate's label against the user input.
+// The returned score reflects the quality of the match. A score
+// less than or equal to zero indicates no match, and a score of
+// one means a perfect match.
+type matcher interface {
+ Score(candidateLabel string) (score float32)
+}
+
+// prefixMatcher implements the original case insensitive prefix matching.
+// This matcher should go away once fuzzy matching is released.
+type prefixMatcher string
+
+func (pm prefixMatcher) Score(candidateLabel string) float32 {
+ if strings.HasPrefix(strings.ToLower(candidateLabel), string(pm)) {
+ return 1
+ }
+ return 0
+}
+
// completer contains the necessary information for a single completion request.
type completer struct {
// Package-specific fields.
@@ -155,8 +175,8 @@
// deepState contains the current state of our deep completion search.
deepState deepCompletionState
- // matcher does fuzzy matching of the candidates for the surrounding prefix.
- matcher *fuzzy.Matcher
+ // matcher matches the candidates against the surrounding prefix.
+ matcher matcher
}
type compLitInfo struct {
@@ -203,8 +223,15 @@
Range: span.NewRange(c.view.Session().Cache().FileSet(), ident.Pos(), ident.End()),
Cursor: c.pos,
}
- if c.surrounding.Prefix() != "" {
- c.matcher = fuzzy.NewMatcher(c.surrounding.Prefix(), fuzzy.Symbol)
+
+ // Fuzzy matching shares the "useDeepCompletions" config flag, so if deep completions
+ // are enabled then also enable fuzzy matching.
+ if c.deepState.enabled {
+ if c.surrounding.Prefix() != "" {
+ c.matcher = fuzzy.NewMatcher(c.surrounding.Prefix(), fuzzy.Symbol)
+ }
+ } else {
+ c.matcher = prefixMatcher(strings.ToLower(c.surrounding.Prefix()))
}
}
@@ -243,13 +270,23 @@
// Favor shallow matches by lowering weight according to depth.
cand.score -= stdScore * float64(len(c.deepState.chain))
+
item, err := c.item(cand)
if err != nil {
return err
}
- c.items = append(c.items, item)
+ if c.matcher == nil {
+ c.items = append(c.items, item)
+ } else {
+ score := c.matcher.Score(item.Label)
+ if score > 0 {
+ item.Score *= float64(score)
+ c.items = append(c.items, item)
+ }
+ }
c.deepSearch(obj)
+
return nil
}
diff --git a/internal/lsp/source/source_test.go b/internal/lsp/source/source_test.go
index 9ca7296..7dab497 100644
--- a/internal/lsp/source/source_test.go
+++ b/internal/lsp/source/source_test.go
@@ -17,6 +17,7 @@
"golang.org/x/tools/go/packages/packagestest"
"golang.org/x/tools/internal/lsp/cache"
"golang.org/x/tools/internal/lsp/diff"
+ "golang.org/x/tools/internal/lsp/fuzzy"
"golang.org/x/tools/internal/lsp/source"
"golang.org/x/tools/internal/lsp/telemetry/log"
"golang.org/x/tools/internal/lsp/tests"
@@ -158,16 +159,23 @@
t.Fatalf("failed to get token for %s: %v", src.URI(), err)
}
pos := tok.Pos(src.Start().Offset())
+ deepComplete := strings.Contains(string(src.URI()), "deepcomplete")
list, surrounding, err := source.Completion(ctx, r.view, f.(source.GoFile), pos, source.CompletionOptions{
- DeepComplete: strings.Contains(string(src.URI()), "deepcomplete"),
+ DeepComplete: deepComplete,
WantDocumentaton: true,
})
if err != nil {
t.Fatalf("failed for %v: %v", src, err)
}
- var prefix string
+ var (
+ prefix string
+ fuzzyMatcher *fuzzy.Matcher
+ )
if surrounding != nil {
prefix = strings.ToLower(surrounding.Prefix())
+ if deepComplete && prefix != "" {
+ fuzzyMatcher = fuzzy.NewMatcher(surrounding.Prefix(), fuzzy.Symbol)
+ }
}
wantBuiltins := strings.Contains(string(src.URI()), "builtins")
var got []source.CompletionItem
@@ -175,10 +183,19 @@
if !wantBuiltins && isBuiltin(item) {
continue
}
- // We let the client do fuzzy matching, so we return all possible candidates.
- // To simplify testing, filter results with prefixes that don't match exactly.
- if !strings.HasPrefix(strings.ToLower(item.Label), prefix) {
- continue
+
+ // If deep completion is enabled, we need to use the fuzzy matcher to match
+ // the code's behvaior.
+ if deepComplete {
+ if fuzzyMatcher != nil && fuzzyMatcher.Score(item.Label) <= 0 {
+ continue
+ }
+ } else {
+ // We let the client do fuzzy matching, so we return all possible candidates.
+ // To simplify testing, filter results with prefixes that don't match exactly.
+ if !strings.HasPrefix(strings.ToLower(item.Label), prefix) {
+ continue
+ }
}
got = append(got, item)
}
diff --git a/internal/lsp/testdata/deepcomplete/deep_complete.go b/internal/lsp/testdata/deepcomplete/deep_complete.go
index 2f31b1f..fe985b9 100644
--- a/internal/lsp/testdata/deepcomplete/deep_complete.go
+++ b/internal/lsp/testdata/deepcomplete/deep_complete.go
@@ -34,12 +34,12 @@
}
func _() {
- type deepCircle struct {
+ type deepCircle struct { //@item(deepCircleStruct, "deepCircle", "struct{...}", "struct")
*deepCircle
}
- var circle deepCircle //@item(deepCircle, "circle", "deepCircle", "var")
- circle.deepCircle //@item(deepCircleField, "circle.deepCircle", "*deepCircle", "field")
- var _ deepCircle = ci //@complete(" //", deepCircle, deepCircleField)
+ var circle deepCircle //@item(deepCircle, "circle", "deepCircle", "var")
+ circle.deepCircle //@item(deepCircleField, "circle.deepCircle", "*deepCircle", "field")
+ var _ deepCircle = circ //@complete(" //", deepCircle, deepCircleStruct, deepCircleField)
}
func _() {
diff --git a/internal/lsp/text_synchronization.go b/internal/lsp/text_synchronization.go
index d90b041..0bcfec4 100644
--- a/internal/lsp/text_synchronization.go
+++ b/internal/lsp/text_synchronization.go
@@ -106,7 +106,7 @@
func (s *Server) applyChanges(ctx context.Context, uri span.URI, changes []protocol.TextDocumentContentChangeEvent) (string, error) {
content, _, err := s.session.GetFile(uri).Read(ctx)
if err != nil {
- return "", jsonrpc2.NewErrorf(jsonrpc2.CodeInternalError, "file not found")
+ return "", jsonrpc2.NewErrorf(jsonrpc2.CodeInternalError, "file not found (%v)", err)
}
fset := s.session.Cache().FileSet()
for _, change := range changes {
