fuzzy-matcher

fuzzy-matcher is a Rust library that scores and ranks how well a short pattern matches a longer string, the core operation behind fuzzy finders, command palettes, and type-ahead search. It provides two algorithm families: a Smith-Waterman-based Skim matcher (the engine behind the popular skim fuzzy finder) and a clangd-inspired matcher, both returning match scores and the exact character indices that matched.

All matchers implement a single FuzzyMatcher trait, so you can swap algorithms without touching call sites. The library is dependency-light, thread-safe, and offers a compact feature that shrinks its score/index integer types to reduce memory when matching against large candidate lists.

What You Get

• A FuzzyMatcher trait with fuzzy_match (score only) and fuzzy_indices (score plus matched character positions)
• SkimMatcherV2, a Smith-Waterman-based matcher tuned for interactive fuzzy finding with configurable scoring and matrix-size limits
• A clangd-inspired matcher as an alternative ranking algorithm
• A compact build feature that narrows score and index integer types to cut memory usage on large inputs
• Thread-safe (Send + Sync) matchers suitable for use across worker threads

Common Use Cases

• Ranking and filtering candidates in a fuzzy finder or command palette
• Powering type-ahead / autocomplete search over lists of files, commands, or symbols
• Highlighting the specific characters that matched a user’s query in search results

Under The Hood

Architecture - The crate centers on a single FuzzyMatcher trait in src/lib.rs exposing fuzzy_indices (score plus matched indices) with fuzzy_match provided as a default that discards the indices. Concrete matchers live in src/skim.rs (the deprecated V1 plus the primary SkimMatcherV2) and src/clangd.rs, while src/util.rs holds shared primitives like cheap_matches, char_role, and result-highlighting helpers. Score and index integer widths are aliased (ScoreType, IndexType) and switched at compile time via the compact feature.

Tech Stack - Pure Rust on the 2018 edition with a single runtime dependency, thread_local, used to cache per-thread scratch buffers for the dynamic-programming matrices; termion is a dev-only dependency for the example. The V2 matcher implements a Smith-Waterman alignment with tuned bonus/penalty constants (adjacency, camel-case, separator, leading-character penalties) and caps the score-matrix element count, falling back to a linear scan when a pattern/input pair is too large.

Code Quality - Code is idiomatic and readable, with the scoring constants named and documented and the character-role logic annotated against its clangd origin. Tests are embedded as #[cfg(test)] modules (roughly seven in the Skim matcher and two in clangd) covering ordering and matching behavior via helpers like assert_order. The single external dependency keeps the supply chain small.

API Design - The public surface is deliberately minimal: construct a matcher (SkimMatcherV2::default()) and call fuzzy_match or fuzzy_indices. Trait-based polymorphism lets callers switch algorithms without changing call sites, and returning Option cleanly signals non-matches. The README’s copy-paste examples get a new user productive quickly, though deeper scoring-tuning options are documented mainly through the source and docs.rs.