symbol_test.go

Documentation: golang.org/x/tools/internal/fuzzy

     1  // Copyright 2021 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  package fuzzy_test
     6  
     7  import (
     8  	"go/ast"
     9  	"go/token"
    10  	"sort"
    11  	"testing"
    12  
    13  	"golang.org/x/tools/go/packages"
    14  	. "golang.org/x/tools/internal/fuzzy"
    15  )
    16  
    17  func TestSymbolMatchIndex(t *testing.T) {
    18  	tests := []struct {
    19  		pattern, input string
    20  		want           int
    21  	}{
    22  		{"test", "foo.TestFoo", 4},
    23  		{"test", "test", 0},
    24  		{"test", "Test", 0},
    25  		{"test", "est", -1},
    26  		{"t", "shortest", 7},
    27  		{"", "foo", -1},
    28  		{"", string([]rune{0}), -1}, // verify that we don't default to an empty pattern.
    29  		{"anything", "", -1},
    30  	}
    31  
    32  	for _, test := range tests {
    33  		matcher := NewSymbolMatcher(test.pattern)
    34  		if got, _ := matcher.Match([]string{test.input}); got != test.want {
    35  			t.Errorf("NewSymbolMatcher(%q).Match(%q) = %v, _, want %v, _", test.pattern, test.input, got, test.want)
    36  		}
    37  	}
    38  }
    39  
    40  func TestSymbolRanking(t *testing.T) {
    41  
    42  	// query -> symbols to match, in ascending order of score
    43  	queryRanks := map[string][]string{
    44  		"test": {
    45  			"this.is.better.than.most",
    46  			"test.foo.bar",
    47  			"thebest",
    48  			"atest",
    49  			"test.foo",
    50  			"testage",
    51  			"tTest",
    52  			"foo.test",
    53  		},
    54  		"parseside": { // golang/go#60201
    55  			"yaml_PARSE_FLOW_SEQUENCE_ENTRY_MAPPING_END_STATE",
    56  			"parseContext.parse_sidebyside",
    57  		},
    58  		"cvb": {
    59  			"filecache_test.testIPCValueB",
    60  			"cover.Boundary",
    61  		},
    62  		"dho": {
    63  			"gocommand.DebugHangingGoCommands",
    64  			"protocol.DocumentHighlightOptions",
    65  		},
    66  		"flg": {
    67  			"completion.FALLTHROUGH",
    68  			"main.flagGoCmd",
    69  		},
    70  		"fvi": {
    71  			"godoc.fileIndexVersion",
    72  			"macho.FlagSubsectionsViaSymbols",
    73  		},
    74  	}
    75  
    76  	for query, symbols := range queryRanks {
    77  		t.Run(query, func(t *testing.T) {
    78  			matcher := NewSymbolMatcher(query)
    79  			prev := 0.0
    80  			for _, sym := range symbols {
    81  				_, score := matcher.Match([]string{sym})
    82  				t.Logf("Match(%q) = %v", sym, score)
    83  				if score <= prev {
    84  					t.Errorf("Match(%q) = _, %v, want > %v", sym, score, prev)
    85  				}
    86  				prev = score
    87  			}
    88  		})
    89  	}
    90  }
    91  
    92  func TestMatcherSimilarities(t *testing.T) {
    93  	// This test compares the fuzzy matcher with the symbol matcher on a corpus
    94  	// of qualified identifiers extracted from x/tools.
    95  	//
    96  	// These two matchers are not expected to agree, but inspecting differences
    97  	// can be useful for finding interesting ranking edge cases.
    98  	t.Skip("unskip this test to compare matchers")
    99  
   100  	idents := collectIdentifiers(t)
   101  	t.Logf("collected %d unique identifiers", len(idents))
   102  
   103  	// TODO: use go1.21 slices.MaxFunc.
   104  	topMatch := func(score func(string) float64) string {
   105  		top := ""
   106  		topScore := 0.0
   107  		for _, cand := range idents {
   108  			if s := score(cand); s > topScore {
   109  				top = cand
   110  				topScore = s
   111  			}
   112  		}
   113  		return top
   114  	}
   115  
   116  	agreed := 0
   117  	total := 0
   118  	bad := 0
   119  	patterns := generatePatterns()
   120  	for _, pattern := range patterns {
   121  		total++
   122  
   123  		fm := NewMatcher(pattern)
   124  		topFuzzy := topMatch(func(input string) float64 {
   125  			return float64(fm.Score(input))
   126  		})
   127  		sm := NewSymbolMatcher(pattern)
   128  		topSymbol := topMatch(func(input string) float64 {
   129  			_, score := sm.Match([]string{input})
   130  			return score
   131  		})
   132  		switch {
   133  		case topFuzzy == "" && topSymbol != "":
   134  			if false {
   135  				// The fuzzy matcher has a bug where it misses some matches; for this
   136  				// test we only care about the symbol matcher.
   137  				t.Logf("%q matched %q but no fuzzy match", pattern, topSymbol)
   138  			}
   139  			total--
   140  			bad++
   141  		case topFuzzy != "" && topSymbol == "":
   142  			t.Fatalf("%q matched %q but no symbol match", pattern, topFuzzy)
   143  		case topFuzzy == topSymbol:
   144  			agreed++
   145  		default:
   146  			// Enable this log to see mismatches.
   147  			if false {
   148  				t.Logf("mismatch for %q: fuzzy: %q, symbol: %q", pattern, topFuzzy, topSymbol)
   149  			}
   150  		}
   151  	}
   152  	t.Logf("fuzzy matchers agreed on %d out of %d queries (%d bad)", agreed, total, bad)
   153  }
   154  
   155  func collectIdentifiers(tb testing.TB) []string {
   156  	cfg := &packages.Config{
   157  		Mode:  packages.NeedName | packages.NeedSyntax | packages.NeedFiles,
   158  		Tests: true,
   159  	}
   160  	pkgs, err := packages.Load(cfg, "golang.org/x/tools/...")
   161  	if err != nil {
   162  		tb.Fatal(err)
   163  	}
   164  	uniqueIdents := make(map[string]bool)
   165  	decls := 0
   166  	for _, pkg := range pkgs {
   167  		for _, f := range pkg.Syntax {
   168  			for _, decl := range f.Decls {
   169  				decls++
   170  				switch decl := decl.(type) {
   171  				case *ast.GenDecl:
   172  					for _, spec := range decl.Specs {
   173  						switch decl.Tok {
   174  						case token.IMPORT:
   175  						case token.TYPE:
   176  							name := spec.(*ast.TypeSpec).Name.Name
   177  							qualified := pkg.Name + "." + name
   178  							uniqueIdents[qualified] = true
   179  						case token.CONST, token.VAR:
   180  							for _, n := range spec.(*ast.ValueSpec).Names {
   181  								qualified := pkg.Name + "." + n.Name
   182  								uniqueIdents[qualified] = true
   183  							}
   184  						}
   185  					}
   186  				}
   187  			}
   188  		}
   189  	}
   190  	var idents []string
   191  	for k := range uniqueIdents {
   192  		idents = append(idents, k)
   193  	}
   194  	sort.Strings(idents)
   195  	return idents
   196  }
   197  
   198  func generatePatterns() []string {
   199  	var patterns []string
   200  	for x := 'a'; x <= 'z'; x++ {
   201  		for y := 'a'; y <= 'z'; y++ {
   202  			for z := 'a'; z <= 'z'; z++ {
   203  				patterns = append(patterns, string(x)+string(y)+string(z))
   204  			}
   205  		}
   206  	}
   207  	return patterns
   208  }
   209  
   210  // Test that we strongly prefer exact matches.
   211  //
   212  // In golang/go#60027, we preferred "Runner" for the query "rune" over several
   213  // results containing the word "rune" exactly. Following this observation,
   214  // scoring was tweaked to more strongly emphasize sequential characters and
   215  // exact matches.
   216  func TestSymbolRanking_Issue60027(t *testing.T) {
   217  	matcher := NewSymbolMatcher("rune")
   218  
   219  	// symbols to match, in ascending order of ranking.
   220  	symbols := []string{
   221  		"Runner",
   222  		"singleRuneParam",
   223  		"Config.ifsRune",
   224  		"Parser.rune",
   225  	}
   226  	prev := 0.0
   227  	for _, sym := range symbols {
   228  		_, score := matcher.Match([]string{sym})
   229  		t.Logf("Match(%q) = %v", sym, score)
   230  		if score < prev {
   231  			t.Errorf("Match(%q) = _, %v, want > %v", sym, score, prev)
   232  		}
   233  		prev = score
   234  	}
   235  }
   236  
   237  func TestChunkedMatch(t *testing.T) {
   238  	matcher := NewSymbolMatcher("test")
   239  	_, want := matcher.Match([]string{"test"})
   240  	chunked := [][]string{
   241  		{"", "test"},
   242  		{"test", ""},
   243  		{"te", "st"},
   244  	}
   245  
   246  	for _, chunks := range chunked {
   247  		offset, score := matcher.Match(chunks)
   248  		if offset != 0 || score != want {
   249  			t.Errorf("Match(%v) = %v, %v, want 0, 1.0", chunks, offset, score)
   250  		}
   251  	}
   252  }
   253
View as plain text