matchsorter 0.2.0

# matchsorter

Fuzzy string matching and sorting for Rust, inspired by Kent C. Dodds'
[match-sorter](https://github.com/kentcdodds/match-sorter) for JavaScript.

[![crates.io](https://img.shields.io/crates/v/matchsorter.svg)](https://crates.io/crates/matchsorter)
[![docs.rs](https://docs.rs/matchsorter/badge.svg)](https://docs.rs/matchsorter)
[![license](https://img.shields.io/crates/l/matchsorter.svg)](LICENSE-MIT)

## Overview

`matchsorter` ranks candidate strings against a search query using an **8-tier
ranking system**, then returns them sorted from best to worst match. It handles
everything from exact equality down to fuzzy character-by-character matching,
with optional diacritics normalization, key extraction for structs, and
per-key ranking controls.

Key differences from the JS library:

- Native Rust performance (4-7x faster on equivalent workloads)
- Zero-copy ranking in no-keys mode (borrows directly from input)
- SIMD-accelerated substring search via `memchr`
- Amortized allocations through reusable buffers and `PreparedQuery`

## Quick Start

Add to your `Cargo.toml`:

```sh
cargo add matchsorter
```

```rust
use matchsorter::{match_sorter, MatchSorterOptions};

let items = ["apple", "banana", "grape", "pineapple"];
let results = match_sorter(&items, "ap", MatchSorterOptions::default());
// "apple" (StartsWith), "grape" (Contains), "pineapple" (Contains); "banana" is dropped
assert_eq!(results, vec![&"apple", &"grape", &"pineapple"]);
```

## Ranking Tiers

Every candidate is classified into one of 8 tiers, checked in order from best
to worst. The first matching tier is used.

| Tier | Name | Example (query `"app"`) |
|------|------|-------------------------|
| 7 | **CaseSensitiveEqual** | `"app"` matches `"app"` exactly |
| 6 | **Equal** | `"app"` matches `"APP"` (case-insensitive) |
| 5 | **StartsWith** | `"app"` matches `"apple"` |
| 4 | **WordStartsWith** | `"app"` matches `"pine apple"` (word boundary) |
| 3 | **Contains** | `"app"` matches `"pineapple"` (substring) |
| 2 | **Acronym** | `"nwa"` matches `"North-West Airlines"` |
| 1..2 | **Matches** | `"plgnd"` fuzzy-matches `"playground"` |
| 0 | **NoMatch** | No match found |

## Features

- **8-tier ranking** from exact match to fuzzy character matching
- **Diacritics normalization** -- `"cafe"` matches `"cafe"` by default (toggle with `keep_diacritics`)
- **Key extraction** -- match against struct fields with `Key::new`, `Key::from_fn`, or `Key::from_fn_multi`
- **Per-key controls** -- `threshold`, `min_ranking`, and `max_ranking` per key
- **Custom sorting** -- replace the tiebreaker (`base_sort`) or the entire sort (`sorter`)
- **Zero-copy no-keys mode** -- `&str`, `String`, and `Cow<str>` work out of the box via `AsMatchStr`

## Advanced Usage

### Keys mode with structs

```rust
use matchsorter::{match_sorter, MatchSorterOptions, AsMatchStr};
use matchsorter::key::Key;

struct User { name: String, email: String }

// Required for compilation; unused in keys mode.
impl AsMatchStr for User {
    fn as_match_str(&self) -> &str { &self.name }
}

let users = vec![
    User { name: "Alice".into(), email: "alice@example.com".into() },
    User { name: "Bob".into(),   email: "bob@example.com".into() },
    User { name: "Malika".into(), email: "malika@example.com".into() },
];

let opts = MatchSorterOptions {
    keys: vec![
        Key::from_fn(|u: &User| u.name.as_str()),
        Key::from_fn(|u: &User| u.email.as_str()),
    ],
    ..Default::default()
};

let results = match_sorter(&users, "ali", opts);
// "Alice" (StartsWith on name), "Malika" (Contains "ali" in name); "Bob" is dropped
assert_eq!(results.len(), 2);
assert_eq!(results[0].name, "Alice");
assert_eq!(results[1].name, "Malika");
```

### Custom threshold

```rust
use matchsorter::{match_sorter, MatchSorterOptions, Ranking};

let items = ["apple", "banana", "playground"];
let opts = MatchSorterOptions {
    threshold: Ranking::Contains,
    ..Default::default()
};
// Only items with a Contains ranking or better are returned.
// Fuzzy-only matches are excluded.
let results = match_sorter(&items, "pl", opts);
assert_eq!(results.len(), 2); // "apple" (Contains) and "playground" (StartsWith)
```

### Per-key clamping

```rust
use matchsorter::{match_sorter, MatchSorterOptions, AsMatchStr, Ranking};
use matchsorter::key::Key;

struct Item { name: String, description: String }

impl AsMatchStr for Item {
    fn as_match_str(&self) -> &str { &self.name }
}

let items = vec![
    Item { name: "Rust".into(), description: "A systems programming language".into() },
    Item { name: "Trust".into(), description: "Build with trust and safety".into() },
];

let opts = MatchSorterOptions {
    keys: vec![
        Key::from_fn(|i: &Item| i.name.as_str()),
        // Cap description matches to Contains so name matches always win
        Key::from_fn(|i: &Item| i.description.as_str())
            .max_ranking(Ranking::Contains),
    ],
    ..Default::default()
};

let results = match_sorter(&items, "rust", opts);
// "Rust" (Equal on name), "Trust" (Contains on name); description caps don't outrank name
assert_eq!(results.len(), 2);
assert_eq!(results[0].name, "Rust");
assert_eq!(results[1].name, "Trust");
```

## Performance

Benchmarked against the JS `match-sorter` library (Node.js v22) on 10,000
items. All times are median microseconds.

| Benchmark | Rust | JS | Speedup |
|-----------|-----:|---:|--------:|
| Throughput (10k items) | 455 us | 2,671 us | **5.9x** |
| Exact match | 351 us | 2,126 us | **6.1x** |
| Prefix match | 298 us | 2,214 us | **7.4x** |
| Substring match | 356 us | 1,915 us | **5.4x** |
| Fuzzy match | 460 us | 2,705 us | **5.9x** |
| No match (early exit) | 327 us | 1,706 us | **5.2x** |
| Diacritics strip (10k) | 761 us | 2,935 us | **3.9x** |

See [`bench-compare/`](bench-compare/) for reproduction instructions.

## License

Licensed under either of

- [Apache License, Version 2.0](LICENSE-APACHE)
- [MIT License](LICENSE-MIT)

at your option.