1 files changed, 294 insertions, 0 deletions
diff --git a/internal/fuzzy/matcher_test.go b/internal/fuzzy/matcher_test.go
new file mode 100644
index 000000000..528224bd9
--- /dev/null
+++ b/internal/fuzzy/matcher_test.go
@@ -0,0 +1,294 @@
+// Copyright 2019 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Benchmark results:
+//
+// BenchmarkMatcher-12    	 1000000	      1615 ns/op	  30.95 MB/s	       0 B/op	       0 allocs/op
+package fuzzy_test
+
+import (
+	"bytes"
+	"fmt"
+	"math"
+	"testing"
+
+	"golang.org/x/tools/internal/fuzzy"
+)
+
+type comparator struct {
+	f     func(val, ref float32) bool
+	descr string
+}
+
+var (
+	eq = comparator{
+		f: func(val, ref float32) bool {
+			return val == ref
+		},
+		descr: "==",
+	}
+	ge = comparator{
+		f: func(val, ref float32) bool {
+			return val >= ref
+		},
+		descr: ">=",
+	}
+	gt = comparator{
+		f: func(val, ref float32) bool {
+			return val > ref
+		},
+		descr: ">",
+	}
+)
+
+func (c comparator) eval(val, ref float32) bool {
+	return c.f(val, ref)
+}
+
+func (c comparator) String() string {
+	return c.descr
+}
+
+type scoreTest struct {
+	candidate string
+	comparator
+	ref float32
+}
+
+var matcherTests = []struct {
+	pattern string
+	tests   []scoreTest
+}{
+	{
+		pattern: "",
+		tests: []scoreTest{
+			{"def", eq, 1},
+			{"Ab stuff c", eq, 1},
+		},
+	},
+	{
+		pattern: "abc",
+		tests: []scoreTest{
+			{"def", eq, 0},
+			{"abd", eq, 0},
+			{"abc", ge, 0},
+			{"Abc", ge, 0},
+			{"Ab stuff c", ge, 0},
+		},
+	},
+	{
+		pattern: "Abc",
+		tests: []scoreTest{
+			{"def", eq, 0},
+			{"abd", eq, 0},
+			{"abc", ge, 0},
+			{"Abc", ge, 0},
+			{"Ab stuff c", ge, 0},
+		},
+	},
+	{
+		pattern: "U",
+		tests: []scoreTest{
+			{"ErrUnexpectedEOF", gt, 0},
+			{"ErrUnexpectedEOF.Error", eq, 0},
+		},
+	},
+}
+
+func TestScore(t *testing.T) {
+	for _, tc := range matcherTests {
+		m := fuzzy.NewMatcher(tc.pattern)
+		for _, sct := range tc.tests {
+			score := m.Score(sct.candidate)
+			if !sct.comparator.eval(score, sct.ref) {
+				t.Errorf("m.Score(%q) = %.2g, want %s %v", sct.candidate, score, sct.comparator, sct.ref)
+			}
+		}
+	}
+}
+
+var compareCandidatesTestCases = []struct {
+	pattern           string
+	orderedCandidates []string
+}{
+	{
+		pattern: "Foo",
+		orderedCandidates: []string{
+			"Barfoo",
+			"Faoo",
+			"F_o_o",
+			"FaoFooa",
+			"BarFoo",
+			"F__oo",
+			"F_oo",
+			"FooA",
+			"FooBar",
+			"Foo",
+		},
+	},
+	{
+		pattern: "U",
+		orderedCandidates: []string{
+			"ErrUnexpectedEOF.Error",
+			"ErrUnexpectedEOF",
+		},
+	},
+}
+
+func TestCompareCandidateScores(t *testing.T) {
+	for _, tc := range compareCandidatesTestCases {
+		m := fuzzy.NewMatcher(tc.pattern)
+
+		var prevScore float32
+		prevCand := "MIN_SCORE"
+		for _, cand := range tc.orderedCandidates {
+			score := m.Score(cand)
+			if prevScore > score {
+				t.Errorf("%s[=%v] is scored lower than %s[=%v]", cand, score, prevCand, prevScore)
+			}
+			if score < -1 || score > 1 {
+				t.Errorf("%s score is %v; want value between [-1, 1]", cand, score)
+			}
+			prevScore = score
+			prevCand = cand
+		}
+	}
+}
+
+var fuzzyMatcherTestCases = []struct {
+	p    string
+	str  string
+	want string
+}{
+	{p: "foo", str: "abc::foo", want: "abc::[foo]"},
+	{p: "foo", str: "foo.foo", want: "foo.[foo]"},
+	{p: "foo", str: "fo_oo.o_oo", want: "[fo]_oo.[o]_oo"},
+	{p: "foo", str: "fo_oo.fo_oo", want: "fo_oo.[fo]_[o]o"},
+	{p: "fo_o", str: "fo_oo.o_oo", want: "[f]o_oo.[o_o]o"},
+	{p: "fOO", str: "fo_oo.o_oo", want: "[f]o_oo.[o]_[o]o"},
+	{p: "tedit", str: "foo.TextEdit", want: "foo.[T]ext[Edit]"},
+	{p: "TEdit", str: "foo.TextEdit", want: "foo.[T]ext[Edit]"},
+	{p: "Tedit", str: "foo.TextEdit", want: "foo.[T]ext[Edit]"},
+	{p: "Tedit", str: "foo.Textedit", want: "foo.[Te]xte[dit]"},
+	{p: "TEdit", str: "foo.Textedit", want: ""},
+	{p: "te", str: "foo.Textedit", want: "foo.[Te]xtedit"},
+	{p: "ee", str: "foo.Textedit", want: ""}, // short middle of the word match
+	{p: "ex", str: "foo.Textedit", want: "foo.T[ex]tedit"},
+	{p: "exdi", str: "foo.Textedit", want: ""},  // short middle of the word match
+	{p: "exdit", str: "foo.Textedit", want: ""}, // short middle of the word match
+	{p: "extdit", str: "foo.Textedit", want: "foo.T[ext]e[dit]"},
+	{p: "e", str: "foo.Textedit", want: "foo.T[e]xtedit"},
+	{p: "E", str: "foo.Textedit", want: "foo.T[e]xtedit"},
+	{p: "ed", str: "foo.Textedit", want: "foo.Text[ed]it"},
+	{p: "edt", str: "foo.Textedit", want: ""}, // short middle of the word match
+	{p: "edit", str: "foo.Textedit", want: "foo.Text[edit]"},
+	{p: "edin", str: "foo.TexteditNum", want: "foo.Text[edi]t[N]um"},
+	{p: "n", str: "node.GoNodeMax", want: "[n]ode.GoNodeMax"},
+	{p: "N", str: "node.GoNodeMax", want: "[n]ode.GoNodeMax"},
+	{p: "completio", str: "completion", want: "[completio]n"},
+	{p: "completio", str: "completion.None", want: "[completio]n.None"},
+}
+
+func TestFuzzyMatcherRanges(t *testing.T) {
+	for _, tc := range fuzzyMatcherTestCases {
+		matcher := fuzzy.NewMatcher(tc.p)
+		score := matcher.Score(tc.str)
+		if tc.want == "" {
+			if score > 0 {
+				t.Errorf("Score(%s, %s) = %v; want: <= 0", tc.p, tc.str, score)
+			}
+			continue
+		}
+		if score < 0 {
+			t.Errorf("Score(%s, %s) = %v, want: > 0", tc.p, tc.str, score)
+			continue
+		}
+		got := highlightMatches(tc.str, matcher)
+		if tc.want != got {
+			t.Errorf("highlightMatches(%s, %s) = %v, want: %v", tc.p, tc.str, got, tc.want)
+		}
+	}
+}
+
+var scoreTestCases = []struct {
+	p    string
+	str  string
+	want float64
+}{
+	// Score precision up to five digits. Modify if changing the score, but make sure the new values
+	// are reasonable.
+	{p: "abc", str: "abc", want: 1},
+	{p: "abc", str: "Abc", want: 1},
+	{p: "abc", str: "Abcdef", want: 1},
+	{p: "strc", str: "StrCat", want: 1},
+	{p: "abc_def", str: "abc_def_xyz", want: 1},
+	{p: "abcdef", str: "abc_def_xyz", want: 0.91667},
+	{p: "abcxyz", str: "abc_def_xyz", want: 0.91667},
+	{p: "sc", str: "StrCat", want: 0.75},
+	{p: "abc", str: "AbstrBasicCtor", want: 0.83333},
+	{p: "foo", str: "abc::foo", want: 0.91667},
+	{p: "afoo", str: "abc::foo", want: 0.9375},
+	{p: "abr", str: "abc::bar", want: 0.5},
+	{p: "br", str: "abc::bar", want: 0.25},
+	{p: "aar", str: "abc::bar", want: 0.41667},
+	{p: "edin", str: "foo.TexteditNum", want: 0.125},
+	{p: "ediu", str: "foo.TexteditNum", want: 0},
+	// We want the next two items to have roughly similar scores.
+	{p: "up", str: "unique_ptr", want: 0.75},
+	{p: "up", str: "upper_bound", want: 1},
+}
+
+func TestScores(t *testing.T) {
+	for _, tc := range scoreTestCases {
+		matcher := fuzzy.NewMatcher(tc.p)
+		got := math.Round(float64(matcher.Score(tc.str))*1e5) / 1e5
+		if got != tc.want {
+			t.Errorf("Score(%s, %s) = %v, want: %v", tc.p, tc.str, got, tc.want)
+		}
+	}
+}
+
+func highlightMatches(str string, matcher *fuzzy.Matcher) string {
+	matches := matcher.MatchedRanges()
+
+	var buf bytes.Buffer
+	index := 0
+	for i := 0; i < len(matches)-1; i += 2 {
+		s, e := matches[i], matches[i+1]
+		fmt.Fprintf(&buf, "%s[%s]", str[index:s], str[s:e])
+		index = e
+	}
+	buf.WriteString(str[index:])
+	return buf.String()
+}
+
+func BenchmarkMatcher(b *testing.B) {
+	pattern := "Foo"
+	candidates := []string{
+		"F_o_o",
+		"Barfoo",
+		"Faoo",
+		"F__oo",
+		"F_oo",
+		"FaoFooa",
+		"BarFoo",
+		"FooA",
+		"FooBar",
+		"Foo",
+	}
+
+	matcher := fuzzy.NewMatcher(pattern)
+
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		for _, c := range candidates {
+			matcher.Score(c)
+		}
+	}
+	var numBytes int
+	for _, c := range candidates {
+		numBytes += len(c)
+	}
+	b.SetBytes(int64(numBytes))
+}