1
2
3
4
5
6
7
8 package fuzzy_test
9
10 import (
11 "bytes"
12 "fmt"
13 "math"
14 "testing"
15
16 "golang.org/x/tools/internal/fuzzy"
17 )
18
19 type comparator struct {
20 f func(val, ref float32) bool
21 descr string
22 }
23
24 var (
25 eq = comparator{
26 f: func(val, ref float32) bool {
27 return val == ref
28 },
29 descr: "==",
30 }
31 ge = comparator{
32 f: func(val, ref float32) bool {
33 return val >= ref
34 },
35 descr: ">=",
36 }
37 gt = comparator{
38 f: func(val, ref float32) bool {
39 return val > ref
40 },
41 descr: ">",
42 }
43 )
44
45 func (c comparator) eval(val, ref float32) bool {
46 return c.f(val, ref)
47 }
48
49 func (c comparator) String() string {
50 return c.descr
51 }
52
53 type scoreTest struct {
54 candidate string
55 comparator
56 ref float32
57 }
58
59 var matcherTests = []struct {
60 pattern string
61 tests []scoreTest
62 }{
63 {
64 pattern: "",
65 tests: []scoreTest{
66 {"def", eq, 1},
67 {"Ab stuff c", eq, 1},
68 },
69 },
70 {
71 pattern: "abc",
72 tests: []scoreTest{
73 {"def", eq, 0},
74 {"abd", eq, 0},
75 {"abc", ge, 0},
76 {"Abc", ge, 0},
77 {"Ab stuff c", ge, 0},
78 },
79 },
80 {
81 pattern: "Abc",
82 tests: []scoreTest{
83 {"def", eq, 0},
84 {"abd", eq, 0},
85 {"abc", ge, 0},
86 {"Abc", ge, 0},
87 {"Ab stuff c", ge, 0},
88 },
89 },
90 {
91 pattern: "U",
92 tests: []scoreTest{
93 {"ErrUnexpectedEOF", gt, 0},
94 {"ErrUnexpectedEOF.Error", eq, 0},
95 },
96 },
97 }
98
99 func TestScore(t *testing.T) {
100 for _, tc := range matcherTests {
101 m := fuzzy.NewMatcher(tc.pattern)
102 for _, sct := range tc.tests {
103 score := m.Score(sct.candidate)
104 if !sct.comparator.eval(score, sct.ref) {
105 t.Errorf("m.Score(%q) = %.2g, want %s %v", sct.candidate, score, sct.comparator, sct.ref)
106 }
107 }
108 }
109 }
110
111 var compareCandidatesTestCases = []struct {
112 pattern string
113 orderedCandidates []string
114 }{
115 {
116 pattern: "Foo",
117 orderedCandidates: []string{
118 "Barfoo",
119 "Faoo",
120 "F_o_o",
121 "FaoFooa",
122 "BarFoo",
123 "F__oo",
124 "F_oo",
125 "FooA",
126 "FooBar",
127 "Foo",
128 },
129 },
130 {
131 pattern: "U",
132 orderedCandidates: []string{
133 "ErrUnexpectedEOF.Error",
134 "ErrUnexpectedEOF",
135 },
136 },
137 }
138
139 func TestCompareCandidateScores(t *testing.T) {
140 for _, tc := range compareCandidatesTestCases {
141 m := fuzzy.NewMatcher(tc.pattern)
142
143 var prevScore float32
144 prevCand := "MIN_SCORE"
145 for _, cand := range tc.orderedCandidates {
146 score := m.Score(cand)
147 if prevScore > score {
148 t.Errorf("%s[=%v] is scored lower than %s[=%v]", cand, score, prevCand, prevScore)
149 }
150 if score < -1 || score > 1 {
151 t.Errorf("%s score is %v; want value between [-1, 1]", cand, score)
152 }
153 prevScore = score
154 prevCand = cand
155 }
156 }
157 }
158
159 var fuzzyMatcherTestCases = []struct {
160 p string
161 str string
162 want string
163 }{
164 {p: "foo", str: "abc::foo", want: "abc::[foo]"},
165 {p: "foo", str: "foo.foo", want: "foo.[foo]"},
166 {p: "foo", str: "fo_oo.o_oo", want: "[fo]_oo.[o]_oo"},
167 {p: "foo", str: "fo_oo.fo_oo", want: "fo_oo.[fo]_[o]o"},
168 {p: "fo_o", str: "fo_oo.o_oo", want: "[f]o_oo.[o_o]o"},
169 {p: "fOO", str: "fo_oo.o_oo", want: "[f]o_oo.[o]_[o]o"},
170 {p: "tedit", str: "foo.TextEdit", want: "foo.[T]ext[Edit]"},
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.[Te]xte[dit]"},
174 {p: "TEdit", str: "foo.Textedit", want: ""},
175 {p: "te", str: "foo.Textedit", want: "foo.[Te]xtedit"},
176 {p: "ee", str: "foo.Textedit", want: ""},
177 {p: "ex", str: "foo.Textedit", want: "foo.T[ex]tedit"},
178 {p: "exdi", str: "foo.Textedit", want: ""},
179 {p: "exdit", str: "foo.Textedit", want: ""},
180 {p: "extdit", str: "foo.Textedit", want: "foo.T[ext]e[dit]"},
181 {p: "e", str: "foo.Textedit", want: "foo.T[e]xtedit"},
182 {p: "E", str: "foo.Textedit", want: "foo.T[e]xtedit"},
183 {p: "ed", str: "foo.Textedit", want: "foo.Text[ed]it"},
184 {p: "edt", str: "foo.Textedit", want: ""},
185 {p: "edit", str: "foo.Textedit", want: "foo.Text[edit]"},
186 {p: "edin", str: "foo.TexteditNum", want: "foo.Text[edi]t[N]um"},
187 {p: "n", str: "node.GoNodeMax", want: "[n]ode.GoNodeMax"},
188 {p: "N", str: "node.GoNodeMax", want: "[n]ode.GoNodeMax"},
189 {p: "completio", str: "completion", want: "[completio]n"},
190 {p: "completio", str: "completion.None", want: "[completio]n.None"},
191 }
192
193 func TestFuzzyMatcherRanges(t *testing.T) {
194 for _, tc := range fuzzyMatcherTestCases {
195 matcher := fuzzy.NewMatcher(tc.p)
196 score := matcher.Score(tc.str)
197 if tc.want == "" {
198 if score > 0 {
199 t.Errorf("Score(%s, %s) = %v; want: <= 0", tc.p, tc.str, score)
200 }
201 continue
202 }
203 if score < 0 {
204 t.Errorf("Score(%s, %s) = %v, want: > 0", tc.p, tc.str, score)
205 continue
206 }
207 got := highlightMatches(tc.str, matcher)
208 if tc.want != got {
209 t.Errorf("highlightMatches(%s, %s) = %v, want: %v", tc.p, tc.str, got, tc.want)
210 }
211 }
212 }
213
214 var scoreTestCases = []struct {
215 p string
216 str string
217 want float64
218 }{
219
220
221 {p: "abc", str: "abc", want: 1},
222 {p: "abc", str: "Abc", want: 1},
223 {p: "abc", str: "Abcdef", want: 1},
224 {p: "strc", str: "StrCat", want: 1},
225 {p: "abc_def", str: "abc_def_xyz", want: 1},
226 {p: "abcdef", str: "abc_def_xyz", want: 0.91667},
227 {p: "abcxyz", str: "abc_def_xyz", want: 0.91667},
228 {p: "sc", str: "StrCat", want: 0.75},
229 {p: "abc", str: "AbstrBasicCtor", want: 0.83333},
230 {p: "foo", str: "abc::foo", want: 0.91667},
231 {p: "afoo", str: "abc::foo", want: 0.9375},
232 {p: "abr", str: "abc::bar", want: 0.5},
233 {p: "br", str: "abc::bar", want: 0.25},
234 {p: "aar", str: "abc::bar", want: 0.41667},
235 {p: "edin", str: "foo.TexteditNum", want: 0.125},
236 {p: "ediu", str: "foo.TexteditNum", want: 0},
237
238 {p: "up", str: "unique_ptr", want: 0.75},
239 {p: "up", str: "upper_bound", want: 1},
240 }
241
242 func TestScores(t *testing.T) {
243 for _, tc := range scoreTestCases {
244 matcher := fuzzy.NewMatcher(tc.p)
245 got := math.Round(float64(matcher.Score(tc.str))*1e5) / 1e5
246 if got != tc.want {
247 t.Errorf("Score(%s, %s) = %v, want: %v", tc.p, tc.str, got, tc.want)
248 }
249 }
250 }
251
252 func highlightMatches(str string, matcher *fuzzy.Matcher) string {
253 matches := matcher.MatchedRanges()
254
255 var buf bytes.Buffer
256 index := 0
257 for i := 0; i < len(matches)-1; i += 2 {
258 s, e := matches[i], matches[i+1]
259 fmt.Fprintf(&buf, "%s[%s]", str[index:s], str[s:e])
260 index = e
261 }
262 buf.WriteString(str[index:])
263 return buf.String()
264 }
265
266 func BenchmarkMatcher(b *testing.B) {
267 pattern := "Foo"
268 candidates := []string{
269 "F_o_o",
270 "Barfoo",
271 "Faoo",
272 "F__oo",
273 "F_oo",
274 "FaoFooa",
275 "BarFoo",
276 "FooA",
277 "FooBar",
278 "Foo",
279 }
280
281 matcher := fuzzy.NewMatcher(pattern)
282
283 b.ResetTimer()
284 for i := 0; i < b.N; i++ {
285 for _, c := range candidates {
286 matcher.Score(c)
287 }
288 }
289 var numBytes int
290 for _, c := range candidates {
291 numBytes += len(c)
292 }
293 b.SetBytes(int64(numBytes))
294 }
295
View as plain text