.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201105173854-bc9fc8d8c4bc/internal/lsp/fuzzy/matcher_test.go

   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 //
   9 package fuzzy_test
  10
  11 import (
  12         "bytes"
  13         "fmt"
  14         "math"
  15         "testing"
  16
  17         "golang.org/x/tools/internal/lsp/fuzzy"
  18 )
  19
  20 type comparator struct {
  21         f     func(val, ref float32) bool
  22         descr string
  23 }
  24
  25 var (
  26         eq = comparator{
  27                 f: func(val, ref float32) bool {
  28                         return val == ref
  29                 },
  30                 descr: "==",
  31         }
  32         ge = comparator{
  33                 f: func(val, ref float32) bool {
  34                         return val >= ref
  35                 },
  36                 descr: ">=",
  37         }
  38         gt = comparator{
  39                 f: func(val, ref float32) bool {
  40                         return val > ref
  41                 },
  42                 descr: ">",
  43         }
  44 )
  45
  46 func (c comparator) eval(val, ref float32) bool {
  47         return c.f(val, ref)
  48 }
  49
  50 func (c comparator) String() string {
  51         return c.descr
  52 }
  53
  54 type scoreTest struct {
  55         candidate string
  56         comparator
  57         ref float32
  58 }
  59
  60 var matcherTests = []struct {
  61         pattern string
  62         tests   []scoreTest
  63 }{
  64         {
  65                 pattern: "",
  66                 tests: []scoreTest{
  67                         {"def", eq, 1},
  68                         {"Ab stuff c", eq, 1},
  69                 },
  70         },
  71         {
  72                 pattern: "abc",
  73                 tests: []scoreTest{
  74                         {"def", eq, 0},
  75                         {"abd", eq, 0},
  76                         {"abc", ge, 0},
  77                         {"Abc", ge, 0},
  78                         {"Ab stuff c", ge, 0},
  79                 },
  80         },
  81         {
  82                 pattern: "Abc",
  83                 tests: []scoreTest{
  84                         {"def", eq, 0},
  85                         {"abd", eq, 0},
  86                         {"abc", ge, 0},
  87                         {"Abc", ge, 0},
  88                         {"Ab stuff c", ge, 0},
  89                 },
  90         },
  91         {
  92                 pattern: "U",
  93                 tests: []scoreTest{
  94                         {"ErrUnexpectedEOF", gt, 0},
  95                         {"ErrUnexpectedEOF.Error", eq, 0},
  96                 },
  97         },
  98 }
  99
 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)
 107                         }
 108                 }
 109         }
 110 }
 111
 112 var compareCandidatesTestCases = []struct {
 113         pattern           string
 114         orderedCandidates []string
 115 }{
 116         {
 117                 pattern: "Foo",
 118                 orderedCandidates: []string{
 119                         "Barfoo",
 120                         "Faoo",
 121                         "F_o_o",
 122                         "FaoFooa",
 123                         "BarFoo",
 124                         "F__oo",
 125                         "F_oo",
 126                         "FooA",
 127                         "FooBar",
 128                         "Foo",
 129                 },
 130         },
 131         {
 132                 pattern: "U",
 133                 orderedCandidates: []string{
 134                         "ErrUnexpectedEOF.Error",
 135                         "ErrUnexpectedEOF",
 136                 },
 137         },
 138 }
 139
 140 func TestCompareCandidateScores(t *testing.T) {
 141         for _, tc := range compareCandidatesTestCases {
 142                 m := fuzzy.NewMatcher(tc.pattern)
 143
 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)
 150                         }
 151                         if score < -1 || score > 1 {
 152                                 t.Errorf("%s score is %v; want value between [-1, 1]", cand, score)
 153                         }
 154                         prevScore = score
 155                         prevCand = cand
 156                 }
 157         }
 158 }
 159
 160 var fuzzyMatcherTestCases = []struct {
 161         p    string
 162         str  string
 163         want string
 164 }{
 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"},
 192 }
 193
 194 func TestFuzzyMatcherRanges(t *testing.T) {
 195         for _, tc := range fuzzyMatcherTestCases {
 196                 matcher := fuzzy.NewMatcher(tc.p)
 197                 score := matcher.Score(tc.str)
 198                 if tc.want == "" {
 199                         if score > 0 {
 200                                 t.Errorf("Score(%s, %s) = %v; want: <= 0", tc.p, tc.str, score)
 201                         }
 202                         continue
 203                 }
 204                 if score < 0 {
 205                         t.Errorf("Score(%s, %s) = %v, want: > 0", tc.p, tc.str, score)
 206                         continue
 207                 }
 208                 got := highlightMatches(tc.str, matcher)
 209                 if tc.want != got {
 210                         t.Errorf("highlightMatches(%s, %s) = %v, want: %v", tc.p, tc.str, got, tc.want)
 211                 }
 212         }
 213 }
 214
 215 var scoreTestCases = []struct {
 216         p    string
 217         str  string
 218         want float64
 219 }{
 220         // Score precision up to five digits. Modify if changing the score, but make sure the new values
 221         // are reasonable.
 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},
 241 }
 242
 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
 247                 if got != tc.want {
 248                         t.Errorf("Score(%s, %s) = %v, want: %v", tc.p, tc.str, got, tc.want)
 249                 }
 250         }
 251 }
 252
 253 func highlightMatches(str string, matcher *fuzzy.Matcher) string {
 254         matches := matcher.MatchedRanges()
 255
 256         var buf bytes.Buffer
 257         index := 0
 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])
 261                 index = e
 262         }
 263         buf.WriteString(str[index:])
 264         return buf.String()
 265 }
 266
 267 func BenchmarkMatcher(b *testing.B) {
 268         pattern := "Foo"
 269         candidates := []string{
 270                 "F_o_o",
 271                 "Barfoo",
 272                 "Faoo",
 273                 "F__oo",
 274                 "F_oo",
 275                 "FaoFooa",
 276                 "BarFoo",
 277                 "FooA",
 278                 "FooBar",
 279                 "Foo",
 280         }
 281
 282         matcher := fuzzy.NewMatcher(pattern)
 283
 284         b.ResetTimer()
 285         for i := 0; i < b.N; i++ {
 286                 for _, c := range candidates {
 287                         matcher.Score(c)
 288                 }
 289         }
 290         var numBytes int
 291         for _, c := range candidates {
 292                 numBytes += len(c)
 293         }
 294         b.SetBytes(int64(numBytes))
 295 }