blob: bac81c0981decc36bc92431dcab0aa530b4611d8 [file] [log] [blame]
// 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))
}