| 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. |
| 4 | |
| 5 | // Benchmark results: |
| 6 | // |
| 7 | // BenchmarkMatcher-12 1000000 1615 ns/op 30.95 MB/s 0 B/op 0 allocs/op |
| 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: ""}, // short middle of the word match |
| 177 | {p: "ex", str: "foo.Textedit", want: "foo.T[ex]tedit"}, |
| 178 | {p: "exdi", str: "foo.Textedit", want: ""}, // short middle of the word match |
| 179 | {p: "exdit", str: "foo.Textedit", want: ""}, // short middle of the word match |
| 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: ""}, // short middle of the word match |
| 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 | // Score precision up to five digits. Modify if changing the score, but make sure the new values |
| 220 | // are reasonable. |
| 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 | // We want the next two items to have roughly similar scores. |
| 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 |
Members