All 42 libraries

SugarFuzzy

Fuzzy string matching with matched character indices plus the match score

foundation-package fuzzy filter

SugarFuzzy code coverage

Fuzzy string matching that returns matched character indices plus the match score. Two algorithms: Smith-Waterman (local alignment) and Sahilm (gum-style scoring with separator/camel-case bonuses). The matched indices enable filter-highlighting UIs that were impossible with score-only matchers. Extracted from sugar-forms; back-compat shims remain in sugar-forms and sugar-treelist for existing consumers, while new code depends on sugar-fuzzy directly.

Install

composer require sugarcraft/sugar-fuzzy

Quickstart

use SugarCraft\Fuzzy\Matcher\SmithWatermanMatcher;
use SugarCraft\Fuzzy\Highlighter;

$matcher = new SmithWatermanMatcher();

// Single match — returns null when no match
$result = $matcher->match('foo', 'foobar');
// $result->score     === 19   (3 × matchScore + 2 × adjacentBonus = 19)
// $result->indices() === [0, 1, 2]  (0-based character positions)
// $result->haystack  === 'foobar'

// Match all candidates, sorted by score desc then candidate asc
$results = $matcher->matchAll('ab', ['apple', 'banana', 'cabbage']);
// cabbage (11, the adjacent "ab") before apple (3) and banana (3)

// Opt in to full-query mode for type-to-filter pickers: every query
// character must land, in order
$picker = SmithWatermanMatcher::new()->withRequireFullQuery();
$picker->match('bxz', 'abcdef');               // null — "x" and "z" never land
$picker->match('gst', 'git status')->indices(); // [0, 4, 5]

// Use Highlighter to mark matched runs with ANSI codes
$highlighter = new Highlighter();
echo $highlighter->highlight($result, fn($s) => "\e[1;31m{$s}\e[0m");
// Output: 'foobar' with positions [0,1,2] highlighted in bold red
// The highlighter is presentation-neutral: sanitize candidate text (strip
// \x1b/control bytes) before display — see Security below

FuzzyMatcher interface

match(string $query, string $candidate): ?MatchResultReturns null when no match, MatchResult with score + indices otherwise.
matchAll(string $query, iterable $candidates, ?int $limit = null, int $minScore = 1): list<MatchResult>Returns all matches sorted by score desc, then candidate asc as tiebreak (compared with <=>, so digit-only candidates order numerically); perfect ties keep input order (usort is stable as of PHP 8.0); limit: 0 yields none, a negative limit is unlimited. matchAllGenerator() yields the same ranked results — it drains and sorts the whole input before the first yield (ranking is global), a streaming API rather than per-candidate laziness.

MatchResult

$score: intReadonly match quality score — higher is better; isMatched() is score > 0.
indices(): list<int>0-based code-point offsets into the original haystack (UTF-8 safe — indices are at character boundaries, not bytes).
$needle / $haystack: stringReadonly query and candidate the result was computed for.
$matchedIndices: arrayReadonly list of 0-based code-point offsets of the matched characters — the same data indices() returns.

Algorithms

SmithWatermanMatcherLocal sequence alignment — optimal for finding best subsequence match within a candidate. Weights come from an immutable ScoringProfile; ScoringProfile::canonical() (the default) is bit-equivalent to the original sugar-forms FuzzyMatcher for ASCII input (legacy deviations documented in the README), with strict() / lenient() presets. withRequireFullQuery() keeps only candidates that contain the whole query as an in-order subsequence, scoring the best alignment forced to cover every query character (floored at 1). Over-cap input is truncated, never handed to another algorithm: only the first maxQueryLength (128) query and maxCandidateLength (1000) candidate characters take part. Candidates truncate; under full-query mode an over-cap query is rejected — it never matches. SahilmMatcher is single-pass linear and intentionally uncapped — bound hostile-size candidates host-side.
SahilmMatcherAdapts the sahilm/fuzzy scoring algorithm — separator bonus (_, -, space, ., /, \, :), camelCase bonus, first-character bonus. Good for file/path matching. Weights are injectable via the immutable SahilmScoring; SahilmScoring::canonical() mirrors the bonus-constant shape of sahilm/fuzzy — the values are this port's historical constants, pinned by the characterization suites.

Highlighter

Takes a MatchResult and a styler \Closure(string): string, returns the candidate string with matched runs passed through the styler. Non-matched runs are returned unchanged.

Highlighting is visual by default: pair color with bold/underline cues for color-blind users, and expose the matchedIndices + the deterministic matchAll() ranking for non-visual/screen-reader channels.

Security

The highlighter is presentation-neutral and forwards unmatched haystack segments verbatim. Callers must sanitize candidate text (strip \x1b/control bytes) before display — the styler callback receives raw matched substrings only and does not sanitize; sanitization belongs to the TUI render layer. Case folding maps malformed UTF-8 bytes to ?, so a literal ? in a query can forge a match against untrusted text — validate UTF-8 on either side when inputs are hostile.

Use it for

  • Filter-as-you-type with highlighted matches — know exactly which characters triggered the match for underline/bold/color highlighting.
  • Ranked autocomplete — matchAll sorts results by relevance score, not alphabetical order.
  • File/path fuzzy finding — SahilmMatcher bonus for separators and camelCase makes it ideal for IDE-style file openers.
  • Foundation for sugar-quickpick — the fuzzy finder overlay uses matched indices to paint the matched characters in each ranked row (match styling opt-in; selection is the formatter's $isSelected flag).

Source & demos

Try the quickstart →

API

ClassMethodDescription
FuzzyMatchermatch(string $query, string $candidate): ?MatchResultSingle match or null
FuzzyMatchermatchAll(string $query, iterable $candidates, ?int $limit = null, int $minScore = 1): list<MatchResult>All matches sorted by score desc, then haystack asc (numeric-string aware); limit 0 yields none, negative limit is unlimited
FuzzyMatchermatchAllGenerator(string $query, iterable $candidates, ?int $limit = null, int $minScore = 1): GeneratorRanked-order generator; drains and sorts before the first yield (same output as matchAll())
MatchResult$score / $needle / $haystack / $matchedIndices (readonly)Match quality score (higher = better), the query and the candidate, and the matched code-point offsets
MatchResultindices(): list<int>0-based matched code-point offsets into the original haystack
MatchResultisMatched(): bool / isEmpty(): boolscore > 0 / no matched indices
SmithWatermanMatchernew(?ScoringProfile $profile = null, int $maxQueryLength = 128, int $maxCandidateLength = 1000, bool $requireFullQuery = false)Local sequence alignment; over-cap candidates truncate, and under full-query mode an over-cap query is rejected
SmithWatermanMatcherscore(string $query, string $candidate): intAlignment score without building a full result (0 = no match) — SmithWatermanMatcher only, not part of the FuzzyMatcher contract
SmithWatermanMatcherwithRequireFullQuery(bool $require = true): self / requiresFullQuery(): boolFull-query mode: every query character must land, in order
SmithWatermanMatcherprofile() / maxQueryLength() / maxCandidateLength()Configured weights and length caps
ScoringProfilecanonical() / strict() / lenient()Smith-Waterman weight presets
ScoringProfilewithMatchScore() / withMismatchPenalty() / withGapOpen() / withGapExtend() / withAdjacentBonus()Immutable weight setters
SahilmMatchernew(bool $caseSensitive = false, ?SahilmScoring $scoring = null)Separator/camelCase bonus algorithm; scoring() / caseSensitive() accessors
SahilmScoringcanonical() / withMatchScore() / withConsecutiveBonus() / withSeparatorBonus() / withCamelBonus() / withFirstCharBonus() / withLowerCaseBonus()Immutable Sahilm weights (canonical 1 / 5 / 10 / 10 / 15 / 1)
FuzzyMatcherFactorynamed(string $type, ScoringProfile|SahilmScoring|null $scoring = null): FuzzyMatcher'smith-waterman' or 'sahilm'; a mismatched weight type or unknown name throws
Highlighterhighlight(MatchResult, \Closure(string): string): stringApply styler to matched runs
CharFoldfoldSplit(string): list<string> / fold(string): stringPer-codepoint case fold that stays 1:1 with the original string — keeps matched code-point indices truthful where whole-string lowercase would expand (U+0130, final sigma); malformed bytes fold to ? without desync