Matching

Purpose

The matching layer turns the user's query into a Pattern and runs that pattern against the ChunkList to produce scored results. It's the heart of why fzf is fast.

The work is split across three files:

• src/algo/algo.go — pluggable matching algorithms (V1, V2, Exact, Prefix, Suffix, Equal, ExactBoundary). Pure functions, no shared state.
• src/pattern.go — the query compiler. Parses the user input into a tree of termSets and terms, picks the right algorithm for each term, and provides a MatchItem(item) entry point.
• src/matcher.go — the scan orchestrator. Partitions chunk snapshots across goroutines, applies the pattern, sorts via Merger, and reports MatchResult events.

Directory layout

src/
├── matcher.go               # Matcher, MatchRequest, MatchResult; the scan loop
├── pattern.go               # Pattern, term, termSet; query parsing
├── result.go                # Result struct + tiebreaker comparisons
├── result_x86.go            # SIMD-accelerated result helpers (build constraint)
├── result_others.go         # Portable fallback
├── merger.go                # Merger: heap-merges per-partition results in score order
└── algo/
    ├── algo.go              # FuzzyMatchV1, FuzzyMatchV2, ExactMatch*, PrefixMatch, SuffixMatch
    ├── normalize.go         # Latin-script case-insensitive folding
    ├── indexbyte2_*.go      # SIMD IndexByteTwo (amd64 / arm64 / fallback)
    └── *_test.go            # Heavy unit + fuzz coverage

Key abstractions

Type / function	File	Description
algo.Algo	src/algo/algo.go	Function type func(caseSensitive, normalize bool, forward bool, text *util.Chars, pattern []rune, withPos bool, slab *util.Slab) (Result, *[]int).
algo.FuzzyMatchV1, algo.FuzzyMatchV2	src/algo/algo.go	The two fuzzy algorithms. V2 (default) is Smith-Waterman-derived; V1 is single-pass.
algo.ExactMatchNaive, algo.PrefixMatch, algo.SuffixMatch, algo.EqualMatch, algo.ExactMatchBoundary	src/algo/algo.go	The non-fuzzy variants.
algo.Result	src/algo/algo.go	Start, End, Score returned by every algo.
term, termSet, Pattern	src/pattern.go	The compiled query representation.
BuildPattern(...)	src/pattern.go	Compiles a query ([]rune) into a Pattern, caching by string for repeat presses of the same key.
Pattern.MatchItem(item, withPos, slab)	src/pattern.go	Runs the pattern against a single item.
Matcher, MatchRequest, MatchResult	src/matcher.go	The scan orchestrator.
Matcher.scan(req)	src/matcher.go	Partitions the chunk slice across runtime.NumCPU() (or --threads) goroutines and merges results.
Merger	src/merger.go	Heap-merges per-partition Result slices in score-then-tiebreaker order.
Slab	src/util/slab.go	Pre-allocated 16-bit + 32-bit scratch arrays reused across scans.

How it works

graph LR
    Q[Query string] --> BUILD[BuildPattern<br/>src/pattern.go]
    BUILD --> TS[termSet OR groups]
    TS --> PARTS[Per-partition scans]
    PARTS --> ALGO[Algo]
    ALGO --> RES[Result + score]
    RES --> MERGE[Merger sort<br/>src/merger.go]
    MERGE --> OUT[MatchResult]

Query compilation

In extended-search mode (the default), the query is split on whitespace into terms. Each token is classified by its prefix/suffix:

Token shape	termType
foo	termFuzzy
'foo	termExact
^foo	termPrefix
foo$	termSuffix
'foo$	termExactBoundary
=foo	termEqual
!foo, !'foo, !^foo, !foo$	inverse versions of the above
|	OR separator (creates a new termSet)

The header comment of src/pattern.go shows the canonical form. termSets is a list of OR groups, each containing one or more terms that must all match. Negation (!) flips the result of a single term.

BuildPattern also picks the right algo.Algo for each term type and packages it into the Pattern's procFun array, so the inner loop is one indirect call rather than a switch.

Scoring

The doc comment at the top of src/algo/algo.go is the authoritative reference for the scoring scheme. Highlights:

• Bonus positions: start of word, after non-alnum delimiters (/, ,, :, ;, |), camelCase boundaries.
• First-character multiplier: the bonus for the first matched character is multiplied because the user usually puts effort into typing it precisely.
• Gap penalty: linear in the distance between consecutive matched characters.
• Consecutive-match bonus: extra score for runs of consecutive matches, scaled by the bonus of the first character in the run.

The scheme is tuned so the bonus is canceled at gap size ~8.

Algorithm choice

Mode	Algorithm	Why
Default	FuzzyMatchV2	Best result quality across all positions of the pattern. O(nm) worst case.
--algo=v1	FuzzyMatchV1	Single forward+backward pass; faster but can miss the optimal occurrence. O(n).
--exact (or 'foo term)	ExactMatchNaive	Substring search. Boyer-Moore is overkill for short patterns.
--scheme=path	V2 with extra bonus for /	Better ranking for path-like inputs.
--scheme=history	V2 with adjusted weights	Tuned for history-style input where recent items should win.

Parallel scan

Matcher.scan (in src/matcher.go) divides the chunk slice into partitions = runtime.NumCPU() (or --threads N) buckets and runs each bucket in its own goroutine using a dedicated Slab. Each goroutine writes into a pre-allocated []Result (kept in Matcher.sortBuf), and the goroutines never cross. The Merger then heap-merges them.

MatcherCancelScan and ResumeScan are used by core.go when the coordinator needs to mutate items in place (change-with-nth).

Caching

Matcher.mergerCache keys completed MatchResults on the pattern string (when the pattern is cacheable) and the chunk-list snapshot. Re-typing the same query, or going back to a previous prefix, returns instantly.

Tiebreakers

src/result.go implements the Result comparison used by the Merger. The default tiebreaker is length; other options are chunk, pathname, begin, end, index. They are applied left-to-right as listed in --tiebreak.

Integration points

• Read from: the ChunkList snapshot produced by core.go. Snapshot semantics are described in Reader and chunk list.
• Output to: an EvtSearchFin event on the shared EventBox, carrying a MatchResult with a Merger of sorted results.
• Cancellation: Matcher.CancelScan is invoked by core.go when the coordinator needs to mutate items.

Entry points for modification

• Add a new term type: add a termType constant in src/pattern.go, parsing logic in the term tokenizer, and a corresponding algo.Algo (or reuse one). Update Pattern.MatchItem and the cache key.
• Tweak the scoring scheme: the constants live at the top of src/algo/algo.go (bonusBoundary, bonusCamel123, scoreMatch, scoreGapStart, scoreGapExtension, etc.). Add tests in src/algo/algo_test.go that pin the new behavior.
• Add a new tiebreaker: add a criterion constant in src/options.go, plumb it through result.go (the Result.Less chain), and document in man/man1/fzf.1.
• SIMD work: IndexByteTwo has amd64 and arm64 assembly variants in src/algo/indexbyte2_*.s. The fuzz tests (FuzzIndexByteTwo, FuzzLastIndexByteTwo) exist specifically to keep the asm honest. See also src/algo/SIMD.md.