+++ /dev/null
-// 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/lsp/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))
-}
projects / dotfiles / .git / blobdiff