package fuzzy

import "golang.org/x/pkgsite/internal/fuzzy"

Index ¶

• type SymbolMatcher
• func NewSymbolMatcher(pattern string) *SymbolMatcher
• func (m *SymbolMatcher) Match(chunks []string) (int, float64)

Types ¶

type SymbolMatcher ¶

type SymbolMatcher struct {
	// contains filtered or unexported fields
}

SymbolMatcher implements a fuzzy matching algorithm optimized for Go symbols of the form:

example.com/path/to/package.object.field

Knowing that we are matching symbols like this allows us to make the following optimizations:

• We can incorporate right-to-left relevance directly into the score calculation.
• We can match from right to left, discarding leading bytes if the input is too long.
• We just take the right-most match without losing too much precision. This allows us to use an O(n) algorithm.
• We can operate directly on chunked strings; in many cases we will be storing the package path and/or package name separately from the symbol or identifiers, so doing this avoids allocating strings.
• We can return the index of the right-most match, allowing us to trim irrelevant qualification.

This implementation is experimental, serving as a reference fast algorithm to compare to the fuzzy algorithm implemented by Matcher.

func NewSymbolMatcher ¶

func NewSymbolMatcher(pattern string) *SymbolMatcher

NewSymbolMatcher creates a SymbolMatcher that may be used to match the given search pattern.

Currently this matcher only accepts case-insensitive fuzzy patterns.

An empty pattern matches no input.

func (*SymbolMatcher) Match ¶

func (m *SymbolMatcher) Match(chunks []string) (int, float64)

Match looks for the right-most match of the search pattern within the symbol represented by concatenating the given chunks, returning its offset and score.

If a match is found, the first return value will hold the absolute byte offset within all chunks for the start of the symbol. In other words, the index of the match within strings.Join(chunks, ""). If no match is found, the first return value will be -1.

The second return value will be the score of the match, which is always between 0 and 1, inclusive. A score of 0 indicates no match.

Source Files ¶

fuzzy.go