Documentation
¶
Overview ¶
Package fuzzy ranks candidate strings against a short query typed by a user.
Matching is subsequence-based: the query's runes must appear in the candidate in order but need not be adjacent, so "fwc" finds "forward-char". Scoring rewards matches that land at the start of a word and runs of adjacent runes, and charges for the gaps between them, so the ranking reflects how a reader would judge the match rather than merely whether one exists.
A query is read as fzf reads its extended search syntax. Spaces separate terms, and a candidate must match every one. A term is fuzzy, as above, unless it is marked:
'abc exact: abc appears, contiguous
^abc prefix: the candidate starts with abc
abc$ suffix: the candidate ends with abc
^abc$ the candidate is abc
!abc the candidate does not contain abc; !^abc and !abc$ say it does
not start or end with it, and !'abc is !abc
a | b either: a lone | joins the terms each side into one that
matches when any of them does, so "a | b c" is (a or b) and c
A backslash before a space makes the space part of a term. Case is smart per term: a term with an upper-case letter is exact about case, and one without ignores it. A marker with no word after it yet - the ' typed before one, or a | with no term after it - is ignored rather than matched, so the list does not empty and refill as the user types. A query far longer than anyone types was yanked into the prompt, and is read as text, not syntax.
A candidate scores the sum of its terms' scores. An exact or anchored term is scored as the same runes matched in a row would be, word starts and all, and a negated one adds nothing. So a query of one plain word ranks exactly as it would if there were no syntax at all.
Ordering is total and stable, and pinned by test against a fixed candidate set: predictability is a feature here, because a menu that reorders for reasons the user cannot see is worse than one that ranks imperfectly.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Narrows ¶ added in v0.12.0
Narrows reports whether every candidate next matches is one prev matches too. A prompt can then rank next over only prev's matches rather than every candidate, as fzf does while a query is typed: nearly every keystroke adds to the query, and the list it filters shrinks as it goes.
It is conservative. True is a promise; false says only that it could not tell. It is true, for the keystrokes that matter, when next is prev; when prev matches everything, being empty or a marker alone; when next adds to prev's last word, if that word is fuzzy, exact or a prefix - not a suffix, which is anchored where the addition goes, nor a negation, which excludes less as it grows; and when next adds a word to prev, unless the word joins prev's last group with a |.
Those are cases of one rule, and the rule is what is checked: every group of prev's terms is implied by one of next's, taken from the parsed queries rather than their text. So "b\" to "b\ " is not a narrowing, though it adds to the word, because the escape turns the backslash into a space; and "a | b" to "a | bc" is, though it adds to a group, because a or bc implies a or b.
Rank breaks its last ties by input order, so to rank next exactly as over every candidate, pass prev's matches in the order they were first given, not the order prev ranked them in.
func Same ¶ added in v0.12.0
Same reports whether a and b are one query as Rank reads them, and so rank any list alike: "abc" and "abc ", or "abc '", whose ' has no word after it yet. A prompt need not rank again for such a keystroke, and while a query is typed, every space before a word, and every marker, is one.
Types ¶
type Match ¶
type Match struct {
// Score is higher for a better match. It is comparable only between
// candidates scored against the same query.
Score int
// Indices are the RUNE offsets in the candidate that the query matched,
// strictly ascending. For a plain query there is one per query rune; for
// one of several terms they are every term's together, each offset once,
// and a negated term contributes none. Callers emphasise exactly these
// positions, which is why they are rune offsets and not byte offsets.
Indices []int
}
Match describes how a query matched one candidate.
func Score ¶
Score reports how well query matches candidate, and whether it matches at all.
An empty query matches every candidate with score 0 and no indices, so a prompt showing everything before the user types needs no special case. So does a query of markers alone, such as a ' with no word after it yet.
type Ranked ¶
type Ranked struct {
Candidate string
Match Match
// Index is the candidate's place in the list given to Rank, so what
// matched can be put back in the list's own order: for a list kept in
// its order, or for the next keystroke's Rank to narrow.
Index int
}
Ranked is one candidate and how it matched.
Source Files