gopls/internal/fuzzy/matcher_test.go

// 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/gopls/internal/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
	// In `[][]string{{"foo", "bar"}, {"baz"}}`,
	// "foo" and "bar" must have same score, "baz" must be strictly higher scoring.
	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"},
		},
	},
	{
		pattern: "N",
		orderedCandidates: [][]string{
			{"name"},
			{"Name"},
		},
	},
}

func TestCompareCandidateScores(t *testing.T) {
	for _, tc := range compareCandidatesTestCases {
		m := fuzzy.NewMatcher(tc.pattern)

		var prevScore float32
		var prevCandGroup []string
		for i, candGroup := range tc.orderedCandidates {
			var groupScore float32
			for j, cand := range candGroup {
				score := m.Score(cand)
				if j > 0 && score != groupScore {
					t.Fatalf("score %f of %q different than group", score, cand)
				}
				groupScore = score
			}

			if i > 0 && prevScore >= groupScore {
				t.Errorf("%s[=%v] is not scored higher than %s[=%v]", candGroup, groupScore, prevCandGroup, prevScore)
			}
			if groupScore < 0 || groupScore > 1 {
				t.Errorf("%s score is %v; want value between [0, 1]", candGroup, groupScore)
			}
			prevScore = groupScore
			prevCandGroup = candGroup
		}
	}
}

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))
}