Documentation
¶
Overview ¶
Package fuzzy is the one quick-search scorer for every picker on the chat surface: fzf's FuzzyMatchV2 — a modified Smith-Waterman local alignment — with the corrections helix's nucleo documents for the same algorithm.
THE ALIGNMENT, NOT THE FIRST OCCURRENCE. The query must appear in the item as a subsequence: no substitutions, no skipped query characters, and text characters may be skipped between two query characters at a gap price. The dynamic program finds the highest-scoring alignment, not the first one that happens to fit — which is the whole difference between this and a greedy subsequence walk, and the reason a port that only finds A match is not this package.
SOURCES AND DIVERGENENCES. The algorithm and its constants are ported from junegunn/fzf's src/algo/algo.go (MIT) as corrected by helix-editor/nucleo's matcher/src/fuzzy_optimal.rs (MPL-2.0). What this port takes from nucleo:
- TWO MATRICES. The match matrix carries each cell's score and the running consecutive bonus along the diagonal; the gap matrix runs as two scalars per row (the value carried into this column, and the diagonal one column further back). fzf's single matrix conflates the gap state with the bonus state and is provably not optimal under its own scoring: query "foo" against "xf foo" picks the span "xf_oo" when "x__foo" scores higher — the alignment repro test pins that case.
- THE WHOLE MATRIX IS KEPT, NOT OVERWRITTEN. Row i's cells live in the buffer's i-th slice rather than shearing onto the one before them, because the pass is worth more than its last row: TermHit reads the alignment back off the cells that produced the score, walking the decision bits the pass records as it goes. fzf rebuilds positions with a second, reversed pass and can return a span the forward pass never scored; this port backtracks the one DP that ran.
- MATRIX WIDTH n−m+1. The p-th query byte needs p−1 bytes before it and m−p after it, so m+1 haystack cells can never match; the rows are sheared into the same window either way, and width is the one dimension the matrix needs.
- THE CAMEL RETUNE. bonusCamel123 is 5, not fzf's 7: fzf's 7 lets a camelCase hit beat a hyphenated word, and nucleo lowered it to balance camel, snake and consecutive forms against each other.
- NO PENALTY FOR A LATE START, none for candidate length either. A match beginning later in the item scores the same as one beginning earlier with the same shape; length is a tie-break callers may apply, never a score term here.
What it keeps from fzf: the constants (scoreMatch 16, gap start 3, extension 1, boundary 8, white boundary 10, delimiter boundary 9, consecutive floor 4, first-character multiplier 2), the delimiter set "/,:;|", the whitespace set " \t\n\v\f\r", and the prefilter that walks the query in order and fails fast when the first byte never appears.
CASE. Smart-case, per term: a word typed with no uppercase letter matches case-insensitively, any uppercase makes that word case-sensitive. Over pure-ASCII text the fold is done byte-wise on the spot so the character classes — and with them the camelCase bonuses — are still read from the original casing. Over text with non-ASCII bytes the field is case-folded once with strings.ToLower and matched byte-wise from the fold, and non-ASCII bytes carry no character class: no boundary, no camel — the byte-at-a-time convention this program's pickers already keep. That fold is the one place a matched item allocates on the hot path.
ARITHMETIC. Scores are uint16 and penalties subtract saturating, which is Smith-Waterman's floor-at-zero had for free and keeps the hot path free of allocation and of overflow guards. A term longer than [maxNeedle] bytes is beyond what a typed search word can be; the prefilter still answers whether it matches, at score 0.
THE SLAB. One matcher — the matrix, the bonus line and the backtrack's scratch — is pooled and reused across calls, so a keystroke that re-ranks a thousand rows touches no allocator. DIRECTION: a higher score is a better match, the one convention for the whole repo.
Index ¶
- func Score(haystack string, terms []Term) (int, bool)
- func ScoreFields(fields []string, terms []Term) (int, bool)
- func ScoreFieldsHits(fields []string, terms []Term, hits *[]TermHit, span *[]int) (int, bool)
- func ScoreHits(haystack string, terms []Term, hits *[]TermHit, span *[]int) (int, bool)
- type Term
- type TermHit
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Score ¶
Score is one haystack against the terms: every term must match, and the result is the sum of what each scored. Higher is better; false means some term matched nothing and the row is out.
func ScoreFields ¶
ScoreFields is Score over a row that answers in several fields: per term, the best-scoring field wins, and the total is the sum over terms — so "yolo" finds a settings row by the value it carries even when the label says something else entirely. An empty field list matches nothing but the empty query.
func ScoreFieldsHits ¶
ScoreFieldsHits is ScoreFields that also answers where each term landed: per term, the field it won and the matched indices in that field — so a list that draws one of the fields can highlight a term exactly where it matched, and only there. The score is ScoreFields' answer unchanged, field for field and tie for tie. The buffers are the caller's, as ScoreHits holds them.
func ScoreHits ¶
ScoreHits is Score that also answers where each term landed, as byte indices into the haystack: one field, so every TermHit's Field is zero. The score is Score's answer unchanged; hits and span are the caller's own buffers, reused across calls so a list re-ranked per keystroke allocates nothing per row — hits is rewritten from its start and span holds each call's positions back to back, with every TermHit.Pos a subslice of it.
Types ¶
type Term ¶
type Term struct {
// contains filtered or unexported fields
}
Term is one whitespace-separated word of a query, prepared once per keystroke by Terms and then scored against every row: a row matches when every term matches it, and ranks by the sum of what each term scored.
func Terms ¶
Terms splits a query into its terms. Whitespace separates; every term has to match (Score). An empty query is no terms, and no terms match everything at score 0 — an untyped filter is not a filter, just the list.
The scan is rune-wise over the query itself and allocates the one slice it returns: terms are built once per keystroke, and the pickers hold allocation budgets per keystroke that count them.
type TermHit ¶
type TermHit struct {
// Field is the index of the field the term won — best-scoring, and the
// earliest on ties, exactly as [ScoreFields] ranks them.
Field int
// Pos is the matched byte indices in that field, ascending and with no
// duplicates. It points into the span slice the call filled — a caller
// buffer, rewritten by the next call, so copy what must survive one.
Pos []int
}
TermHit is where one term of a query landed: the field it won, and the ascending byte indices of the alignment that won it — the OPTIMAL span, read back off the pass that scored it, not a second guess at one (fzf's reversed pass can return a span its own forward pass never scored; "foo" against "xf foo" hits the f at 3, 4 and 5 — the whole word — and not fzf's f at 1).
Pos IS EMPTY WHEN THE TERM MATCHED WITHOUT A SPAN WORTH VOUCHING FOR, and the match and its score stand unchanged — the caller simply has nothing to draw. Three ways that happens: a term past the needle guard, which the prefilter answers at score zero; a field that had to be case-folded as a whole (non-ASCII, case-insensitive), whose folded bytes are not the field's; and a lineage whose prefix was floored by its own gap costs — a gap longer than the whole prefix it swallowed — where the score the DP kept belongs to the suffix alone and no full alignment stands behind it.
Source Files