1 // Copyright 2019 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
7 // BenchmarkMatcher-12 1000000 1615 ns/op 30.95 MB/s 0 B/op 0 allocs/op
17 "golang.org/x/tools/internal/lsp/fuzzy"
20 type comparator struct {
21 f func(val, ref float32) bool
27 f: func(val, ref float32) bool {
33 f: func(val, ref float32) bool {
39 f: func(val, ref float32) bool {
46 func (c comparator) eval(val, ref float32) bool {
50 func (c comparator) String() string {
54 type scoreTest struct {
60 var matcherTests = []struct {
68 {"Ab stuff c", eq, 1},
78 {"Ab stuff c", ge, 0},
88 {"Ab stuff c", ge, 0},
94 {"ErrUnexpectedEOF", gt, 0},
95 {"ErrUnexpectedEOF.Error", eq, 0},
100 func TestScore(t *testing.T) {
101 for _, tc := range matcherTests {
102 m := fuzzy.NewMatcher(tc.pattern)
103 for _, sct := range tc.tests {
104 score := m.Score(sct.candidate)
105 if !sct.comparator.eval(score, sct.ref) {
106 t.Errorf("m.Score(%q) = %.2g, want %s %v", sct.candidate, score, sct.comparator, sct.ref)
112 var compareCandidatesTestCases = []struct {
114 orderedCandidates []string
118 orderedCandidates: []string{
133 orderedCandidates: []string{
134 "ErrUnexpectedEOF.Error",
140 func TestCompareCandidateScores(t *testing.T) {
141 for _, tc := range compareCandidatesTestCases {
142 m := fuzzy.NewMatcher(tc.pattern)
144 var prevScore float32
145 prevCand := "MIN_SCORE"
146 for _, cand := range tc.orderedCandidates {
147 score := m.Score(cand)
148 if prevScore > score {
149 t.Errorf("%s[=%v] is scored lower than %s[=%v]", cand, score, prevCand, prevScore)
151 if score < -1 || score > 1 {
152 t.Errorf("%s score is %v; want value between [-1, 1]", cand, score)
160 var fuzzyMatcherTestCases = []struct {
165 {p: "foo", str: "abc::foo", want: "abc::[foo]"},
166 {p: "foo", str: "foo.foo", want: "foo.[foo]"},
167 {p: "foo", str: "fo_oo.o_oo", want: "[fo]_oo.[o]_oo"},
168 {p: "foo", str: "fo_oo.fo_oo", want: "fo_oo.[fo]_[o]o"},
169 {p: "fo_o", str: "fo_oo.o_oo", want: "[f]o_oo.[o_o]o"},
170 {p: "fOO", str: "fo_oo.o_oo", want: "[f]o_oo.[o]_[o]o"},
171 {p: "tedit", str: "foo.TextEdit", want: "foo.[T]ext[Edit]"},
172 {p: "TEdit", str: "foo.TextEdit", want: "foo.[T]ext[Edit]"},
173 {p: "Tedit", str: "foo.TextEdit", want: "foo.[T]ext[Edit]"},
174 {p: "Tedit", str: "foo.Textedit", want: "foo.[Te]xte[dit]"},
175 {p: "TEdit", str: "foo.Textedit", want: ""},
176 {p: "te", str: "foo.Textedit", want: "foo.[Te]xtedit"},
177 {p: "ee", str: "foo.Textedit", want: ""}, // short middle of the word match
178 {p: "ex", str: "foo.Textedit", want: "foo.T[ex]tedit"},
179 {p: "exdi", str: "foo.Textedit", want: ""}, // short middle of the word match
180 {p: "exdit", str: "foo.Textedit", want: ""}, // short middle of the word match
181 {p: "extdit", str: "foo.Textedit", want: "foo.T[ext]e[dit]"},
182 {p: "e", str: "foo.Textedit", want: "foo.T[e]xtedit"},
183 {p: "E", str: "foo.Textedit", want: "foo.T[e]xtedit"},
184 {p: "ed", str: "foo.Textedit", want: "foo.Text[ed]it"},
185 {p: "edt", str: "foo.Textedit", want: ""}, // short middle of the word match
186 {p: "edit", str: "foo.Textedit", want: "foo.Text[edit]"},
187 {p: "edin", str: "foo.TexteditNum", want: "foo.Text[edi]t[N]um"},
188 {p: "n", str: "node.GoNodeMax", want: "[n]ode.GoNodeMax"},
189 {p: "N", str: "node.GoNodeMax", want: "[n]ode.GoNodeMax"},
190 {p: "completio", str: "completion", want: "[completio]n"},
191 {p: "completio", str: "completion.None", want: "[completio]n.None"},
194 func TestFuzzyMatcherRanges(t *testing.T) {
195 for _, tc := range fuzzyMatcherTestCases {
196 matcher := fuzzy.NewMatcher(tc.p)
197 score := matcher.Score(tc.str)
200 t.Errorf("Score(%s, %s) = %v; want: <= 0", tc.p, tc.str, score)
205 t.Errorf("Score(%s, %s) = %v, want: > 0", tc.p, tc.str, score)
208 got := highlightMatches(tc.str, matcher)
210 t.Errorf("highlightMatches(%s, %s) = %v, want: %v", tc.p, tc.str, got, tc.want)
215 var scoreTestCases = []struct {
220 // Score precision up to five digits. Modify if changing the score, but make sure the new values
222 {p: "abc", str: "abc", want: 1},
223 {p: "abc", str: "Abc", want: 1},
224 {p: "abc", str: "Abcdef", want: 1},
225 {p: "strc", str: "StrCat", want: 1},
226 {p: "abc_def", str: "abc_def_xyz", want: 1},
227 {p: "abcdef", str: "abc_def_xyz", want: 0.91667},
228 {p: "abcxyz", str: "abc_def_xyz", want: 0.91667},
229 {p: "sc", str: "StrCat", want: 0.75},
230 {p: "abc", str: "AbstrBasicCtor", want: 0.83333},
231 {p: "foo", str: "abc::foo", want: 0.91667},
232 {p: "afoo", str: "abc::foo", want: 0.9375},
233 {p: "abr", str: "abc::bar", want: 0.5},
234 {p: "br", str: "abc::bar", want: 0.25},
235 {p: "aar", str: "abc::bar", want: 0.41667},
236 {p: "edin", str: "foo.TexteditNum", want: 0.125},
237 {p: "ediu", str: "foo.TexteditNum", want: 0},
238 // We want the next two items to have roughly similar scores.
239 {p: "up", str: "unique_ptr", want: 0.75},
240 {p: "up", str: "upper_bound", want: 1},
243 func TestScores(t *testing.T) {
244 for _, tc := range scoreTestCases {
245 matcher := fuzzy.NewMatcher(tc.p)
246 got := math.Round(float64(matcher.Score(tc.str))*1e5) / 1e5
248 t.Errorf("Score(%s, %s) = %v, want: %v", tc.p, tc.str, got, tc.want)
253 func highlightMatches(str string, matcher *fuzzy.Matcher) string {
254 matches := matcher.MatchedRanges()
258 for i := 0; i < len(matches)-1; i += 2 {
259 s, e := matches[i], matches[i+1]
260 fmt.Fprintf(&buf, "%s[%s]", str[index:s], str[s:e])
263 buf.WriteString(str[index:])
267 func BenchmarkMatcher(b *testing.B) {
269 candidates := []string{
282 matcher := fuzzy.NewMatcher(pattern)
285 for i := 0; i < b.N; i++ {
286 for _, c := range candidates {
291 for _, c := range candidates {
294 b.SetBytes(int64(numBytes))