Fuzzy matching and typo tolerance

Step 8 of 12, and the index starts answering questions that were asked slightly wrong. Step 7 left haystack with phrase and boolean queries over terms it knows exactly, and with one silent failure mode: a typo in a query misses, because the dictionary has no such key, and a missing key is an empty list rather than an error. This step searches the dictionary itself by edit distance and gives the query grammar a ~ for it, so borow~ finds what borrow finds.

The starting state is tag search-ch07, the end of step 7: postings that carry positions, a grammar with AND, OR and NOT, and the BM25 ranker from step 6. The end state of this step is tagged search-ch08. The index file does not change — the same corpus still saves to 2619 bytes at version 3 — because nothing about what is stored changes. What changes is what happens when the term a reader typed is not in the dictionary.

A typo is a missing key

search is a HashMap lookup, and a lookup has two outcomes: the key is there, or it is not. So “borow” is not a badly asked question about “borrow” — it is a different question, about a term no document ever contributed, and it gets the same empty answer “zzzzz” gets. The engine cannot tell a typo from a word it has never seen, because both are absent keys.

The fix is to stop looking the term up and search the dictionary instead: for every term the index holds, measure how far it is from what the reader typed, and keep the ones that are close. The measure is Levenshtein’s edit distance.

The distance between two terms

The Levenshtein distance between two strings is the smallest number of single-character insertions, deletions and substitutions that turn one into the other. “borow” is one edit from “borrow” — an insertion. “cheker” is one from “checker” — a deletion. “teh” is two from “the”, because swapping two characters is not one of the three operations.

/// The Levenshtein distance between `a` and `b`: the fewest
/// single-character insertions, deletions and substitutions that turn
/// one into the other.
fn edit_distance(a: &str, b: &str) -> usize {
    let a: Vec<char> = a.chars().collect();
    let b: Vec<char> = b.chars().collect();
    let mut previous: Vec<usize> = (0..=b.len()).collect();
    let mut current = vec![0usize; b.len() + 1];
    for (i, ca) in a.iter().enumerate() {
        current[0] = i + 1;
        for (j, cb) in b.iter().enumerate() {
            let cost = usize::from(ca != cb);
            current[j + 1] = (previous[j + 1] + 1) // a deletion
                .min(current[j] + 1) // an insertion
                .min(previous[j] + cost); // a match, or a substitution
        }
        std::mem::swap(&mut previous, &mut current);
    }
    previous[b.len()]
}

fn main() {
    let pairs = [
        ("borrow", "borrow"),
        ("borow", "borrow"),
        ("cheker", "checker"),
        ("teh", "the"),
        ("kitten", "sitting"),
        ("saturday", "sunday"),
        ("flaw", "lawn"),
        ("owner", "ownership"),
        ("arger", "ärger"),
        ("", "abc"),
    ];
    for (a, b) in pairs {
        println!("{a:<10} -> {b:<12} distance {}", edit_distance(a, b));
    }
}

▶Run this in the Rust Playground

borrow     -> borrow       distance 0
borow      -> borrow       distance 1
cheker     -> checker      distance 1
teh        -> the          distance 2
kitten     -> sitting      distance 3
saturday   -> sunday       distance 3
flaw       -> lawn         distance 2
owner      -> ownership    distance 4
arger      -> ärger        distance 1
           -> abc          distance 3

The classic way to compute it fills a table where cell (i, j) is the distance between the first i characters of one term and the first j of the other. Each cell comes from three neighbours: the cell above plus one for a deletion, the cell to the left plus one for an insertion, the diagonal plus one for a substitution — or plus zero, when the two characters already match. The answer is the bottom-right cell.

Two rows are enough, because row i+1 only ever reads row i. The first row counts insertions into an empty prefix, the first column counts deletions, and the rest follows. The whole computation is O(m × n) time and O(n) memory, which for terms of ordinary length is cheap enough to run against the entire dictionary once per query.

One difference from Lucene is worth naming. Lucene’s default fuzzy query counts a transposition — “teh” for “the” — as a single edit, using Damerau-Levenshtein’s optimal string alignment. This engine knows three operations, not four, so “teh” costs two. Both are defensible; the three-operation version is the one that fits in two rows.

Scanning the dictionary

The block below is the engine’s dictionary scan over the demo corpus’s real terms, with the positions left out — this step searches the dictionary, and the dictionary does not care where a term sat. The documents are the six corpus files, their terms already normalised the way step 3’s tokeniser leaves them:

use std::collections::HashMap;

/// A tiny inverted index: term -> the documents that hold it. The
/// positions are left out — this step searches the dictionary, and
/// the dictionary does not care where a term sat.
struct Index {
    postings: HashMap<String, Vec<u32>>,
}

impl Index {
    fn new() -> Self {
        Index {
            postings: HashMap::new(),
        }
    }

    /// Index one document's terms. They arrive already normalised —
    /// lowercased, stop words dropped, stemmed — the way the engine's
    /// tokeniser leaves them.
    fn add(&mut self, doc: u32, terms: &[&str]) {
        for term in terms {
            let ids = self.postings.entry(term.to_string()).or_default();
            if ids.last() != Some(&doc) {
                ids.push(doc);
            }
        }
    }

    fn search(&self, term: &str) -> &[u32] {
        self.postings.get(term).map(Vec::as_slice).unwrap_or(&[])
    }

    /// Every dictionary term within `max` edits of `term`, nearest
    /// first, each with its distance.
    fn fuzzy(&self, term: &str, max: usize) -> Vec<(&str, usize)> {
        let mut hits: Vec<(&str, usize)> = self
            .postings
            .keys()
            .filter_map(|candidate| {
                let distance = edit_distance_within(term, candidate, max)?;
                Some((candidate.as_str(), distance))
            })
            .collect();
        // HashMap order is random; sort so the answer is not.
        hits.sort_unstable_by(|a, b| a.1.cmp(&b.1).then_with(|| a.0.cmp(b.0)));
        hits
    }
}

/// The Levenshtein distance between `a` and `b`, counted over
/// characters: the fewest insertions, deletions and substitutions
/// that turn one into the other.
fn edit_distance(a: &str, b: &str) -> usize {
    let a: Vec<char> = a.chars().collect();
    let b: Vec<char> = b.chars().collect();
    let mut previous: Vec<usize> = (0..=b.len()).collect();
    let mut current = vec![0usize; b.len() + 1];
    for (i, ca) in a.iter().enumerate() {
        current[0] = i + 1;
        for (j, cb) in b.iter().enumerate() {
            let cost = usize::from(ca != cb);
            current[j + 1] = (previous[j + 1] + 1)
                .min(current[j] + 1)
                .min(previous[j] + cost);
        }
        std::mem::swap(&mut previous, &mut current);
    }
    previous[b.len()]
}

/// The distance when it is at most `max`, and `None` when it is not.
/// The length check comes first: the distance can never be smaller
/// than the difference in lengths, so a candidate too different in
/// length is out without a table being filled.
fn edit_distance_within(a: &str, b: &str, max: usize) -> Option<usize> {
    if a.chars().count().abs_diff(b.chars().count()) > max {
        return None;
    }
    let distance = edit_distance(a, b);
    (distance <= max).then_some(distance)
}

fn main() {
    let mut index = Index::new();
    // The demo corpus, document by document, its terms already
    // normalised: 0 is docs/ownership.md, 1 docs/borrow-checker.md,
    // 2 docs/lifetimes.md, 3 docs/iterators.md, 4
    // docs/error-handling.md, 5 docs/style-guide.md.
    index.add(
        0,
        &[
            "ownership", "borrow", "two", "idea", "rust", "built", "every", "value", "one", "owner",
            "owner", "going", "out", "scope", "drop",
        ],
    );
    index.add(
        1,
        &[
            "borrow", "checker", "enforce", "borrow", "rule", "compile", "time", "borrow", "outlive",
            "owner", "borrow", "value",
        ],
    );
    index.add(
        2,
        &[
            "lifetime", "region", "code", "reference", "valid", "borrow", "checker", "use",
            "lifetime", "keep", "every", "reference", "scope",
        ],
    );
    index.add(
        3,
        &[
            "iterator", "lazy", "each", "call", "next", "advance", "iterator", "one", "adapter",
            "map", "borrow", "iterator", "wrap",
        ],
    );
    index.add(
        4,
        &[
            "recoverable", "error", "value", "type", "result", "question", "mark", "operator",
            "return", "error", "caller", "early",
        ],
    );
    index.add(
        5,
        &[
            "house", "style", "page", "prefer", "short", "sentence", "name", "thing", "mean",
            "function", "borrow", "value", "say", "borrow", "long", "struct", "borrow", "input",
            "say", "name", "test", "borrow", "fixture", "module", "above", "example", "borrow",
            "code", "another", "chapter", "say", "came", "prefer", "active", "voice", "cut", "word",
            "like", "simply", "just", "keep", "paragraph", "under", "six", "line", "one", "idea",
            "per", "paragraph", "head", "every", "screenful", "exception", "rule", "written",
            "next", "rule",
        ],
    );

    println!("{} terms in the dictionary", index.postings.len());
    for typo in ["borow", "cheker", "liefetime", "valu", "zzzzz"] {
        println!(
            "{typo:<12} within 1: {:?}   within 2: {:?}",
            index.fuzzy(typo, 1),
            index.fuzzy(typo, 2)
        );
    }
}

▶Run this in the Rust Playground

84 terms in the dictionary
borow        within 1: [("borrow", 1)]   within 2: [("borrow", 1)]
cheker       within 1: [("checker", 1)]   within 2: [("checker", 1)]
liefetime    within 1: [("lifetime", 1)]   within 2: [("lifetime", 1)]
valu         within 1: [("value", 1)]   within 2: [("value", 1), ("call", 2), ("valid", 2)]
zzzzz        within 1: []   within 2: []

The dictionary is only 84 terms on this corpus, so the scan is trivial to run, but the shape of the cost is worth stating: one distance computation per dictionary term, each O(m × n). An engine with millions of terms does not fill a table per candidate — Lucene builds a Levenshtein automaton once per query and walks the dictionary through it. The cheap filter that is already here is the length check: the distance can never be smaller than the difference in lengths, so a candidate that differs in length by more than the radius is out before any table is filled. “ownership” against “owner” at a radius of three never reaches the DP.

The order of the hits is not the order of the dictionary. HashMap iteration order is random, so the hits are sorted by distance and then by term: nearest first, alphabetical within a distance. The query scores them in that order.

The tilde in the grammar

A tilde at the end of a bare word makes that word fuzzy. borow~ uses the default radius of two, borow~1 asks for one, and borow~0 is an exact match — a strange thing to write, a consistent thing to mean. The cap at two is Lucene’s as well: past two edits a radius stops correcting typos and starts matching half the dictionary, which is why its documentation points anyone who wants more at n-gram techniques instead.

/// The largest radius the tilde accepts, and the one a bare tilde
/// means. Two, which is also Lucene's default.
const MAX_EDITS: usize = 2;
const DEFAULT_MAX_EDITS: usize = 2;

/// What can be wrong with a query.
#[derive(Debug)]
enum QueryError {
    /// A tilde followed by anything that is not a radius this engine
    /// has.
    BadFuzzy(String),
}

impl std::fmt::Display for QueryError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            QueryError::BadFuzzy(token) => write!(
                f,
                "the fuzzy operator on {token:?} needs an edit count between 0 and {MAX_EDITS}"
            ),
        }
    }
}

/// Split a fuzzy token: "borow~2" is the word "borow" with a radius
/// of 2, and "borow~" is the same word with the default radius.
/// `Ok(None)` means the token carries no tilde at all.
fn parse_fuzzy(token: &str) -> Result<Option<(&str, usize)>, QueryError> {
    let Some((word, rest)) = token.split_once('~') else {
        return Ok(None);
    };
    let max = if rest.is_empty() {
        DEFAULT_MAX_EDITS
    } else {
        match rest.parse::<usize>() {
            Ok(max) if max <= MAX_EDITS => max,
            _ => return Err(QueryError::BadFuzzy(token.to_string())),
        }
    };
    Ok(Some((word, max)))
}

fn main() {
    for token in [
        "borrow",
        "borow~",
        "borow~1",
        "borow~0",
        "borow~2",
        "borow~3",
        "borow~x",
        "borow~-1",
    ] {
        match parse_fuzzy(token) {
            Ok(None) => println!("{token:<10} an exact term"),
            Ok(Some((word, max))) => {
                println!("{token:<10} the word {word:?} within {max} edits")
            }
            Err(e) => println!("{token:<10} refused: {e}"),
        }
    }
}

▶Run this in the Rust Playground

borrow     an exact term
borow~     the word "borow" within 2 edits
borow~1    the word "borow" within 1 edits
borow~0    the word "borow" within 0 edits
borow~2    the word "borow" within 2 edits
borow~3    refused: the fuzzy operator on "borow~3" needs an edit count between 0 and 2
borow~x    refused: the fuzzy operator on "borow~x" needs an edit count between 0 and 2
borow~-1   refused: the fuzzy operator on "borow~-1" needs an edit count between 0 and 2

A malformed fuzzy token is refused rather than guessed at, the same way a dangling operator is. borow~3 asks for a radius this engine does not have, and borow~x is not a radius at all; both come back with an error naming the token. The radius is the only thing the tilde takes.

The fuzzy word goes through the same tokeniser the index used before the scan, so FOx~1 looks for “fox”. A stop word with a tilde matches nothing, exactly as it does without one. A hyphenated word with a tilde — “borrow-checker~” — normalises to two terms, which is a phrase, and this operator does not do phrases: it matches nothing rather than guessing which half the typo was in.

What a fuzzy operand matches is the union of its variants’ documents, and what it scores by is the variants themselves, each contributing its own BM25 score the way an OR’s terms do. valu~2 on the demo corpus reaches three terms — “value” at one edit, “call” and “valid” at two — so the answer is six documents: the four that hold “value”, plus docs/lifetimes.md for “valid” and docs/iterators.md for “call”. “call” being two substitutions away from “valu” is the radius doing what it says. A radius of two is wide, and the engine does not second-guess it:

"borow~" and "borrow" answer the same:
  true

query "valu~2":
   2.1019  docs/lifetimes.md
   2.1019  docs/iterators.md
   0.4871  docs/borrow-checker.md
   0.4871  docs/error-handling.md
   0.4542  docs/ownership.md
   0.2333  docs/style-guide.md

NOT applies to a fuzzy operand like any other: fox~1 NOT dog is the documents within one edit of “fox”, minus the ones holding “dog”.

The mistake this step invites is the type of the radius. Document ids, positions and lengths are all u32 in this engine, so a radius parsed as a u32 is the natural slip — and the distance the DP produces is a usize, because that is what chars().count() returns:

/// Does the distance fit the radius? The distance the DP produced is
/// a usize; the radius, following the u32 habit of everything around
/// it, is not.
fn within(distance: usize, max: u32) -> bool {
    distance <= max
}

fn main() {
    println!("{}", within(1, 2));
}

▶Run this in the Rust Playground

error[E0308]: mismatched types
 --> src/main.rs:5:17
  |
5 |     distance <= max
  |     --------    ^^^ expected `usize`, found `u32`
  |     |
  |     expected because this is `usize`
  |
help: you can convert a `u32` to a `usize` and panic if the converted value doesn't fit
  |
5 |     distance <= max.try_into().unwrap()
  |                    ++++++++++++++++++++

For more information about this error, try `rustc --explain E0308`.

The engine parses the radius as a usize and the comparison never comes up.

The whole file

One file: the two-row DP, the dictionary scan, the tilde in the query grammar, and the tests. The block below is the file at tag search-ch08, byte for byte.

src/main.rs

use std::collections::BTreeSet;
use std::collections::HashMap;
use std::error::Error;
use std::fmt;
use std::fs;
use std::io;
use std::path::Path;

/// One entry in a term's postings list: the document, and where each
/// occurrence of the term sits in it.
#[derive(Debug, PartialEq)]
struct Posting {
    /// The document this posting refers to.
    doc: u32,
    /// Where each occurrence sits in the document's term sequence,
    /// ascending. One position per occurrence, so the term frequency
    /// is the length of this list.
    positions: Vec<u32>,
}

/// One document the index has seen: the path it was indexed under,
/// and how many terms the tokeniser took out of it.
#[derive(Debug)]
struct Document {
    path: String,
    /// The document's length in terms, stop words excluded.
    length: u32,
}

/// An inverted index: for each term, the documents that contain it.
#[derive(Debug)]
struct Index {
    /// term -> its postings. Each list is ascending in document id,
    /// with one entry per document that contains the term.
    postings: HashMap<String, Vec<Posting>>,
    /// document id -> the document itself.
    documents: Vec<Document>,
}

impl Index {
    fn new() -> Self {
        Index {
            postings: HashMap::new(),
            documents: Vec::new(),
        }
    }

    /// Index one document. `path` is its id; `text` is its contents.
    /// Returns the id the document was given.
    fn add_document(&mut self, path: &str, text: &str) -> u32 {
        // The terms this document contributes, each tagged with its
        // position: the index of the term in the sequence the
        // tokeniser produced. Positions are attached before the sort,
        // because the sort is about the dictionary and the positions
        // are about the document.
        let mut terms: Vec<(u32, String)> = tokenize(text)
            .enumerate()
            .map(|(position, term)| (position as u32, term))
            .collect();
        // Sorted by term, then position, so one term's occurrences sit
        // next to each other in position order.
        terms.sort_unstable_by(|a, b| a.1.cmp(&b.1).then_with(|| a.0.cmp(&b.0)));

        let id = self.documents.len() as u32;
        self.documents.push(Document {
            path: path.to_string(),
            length: terms.len() as u32,
        });

        // Each distinct term becomes one posting, carrying its run's
        // positions — the count of which is the term frequency.
        for (term, run) in count_terms(&terms) {
            self.postings
                .entry(term.to_string())
                .or_default()
                .push(Posting {
                    doc: id,
                    positions: run,
                });
        }

        id
    }

    /// The postings for `term`. Empty when the index has never seen
    /// the term.
    ///
    /// The term has to be normalised the way the tokeniser normalises
    /// text: `search("borrowing")` finds nothing, because the dictionary
    /// holds "borrow". Normalising the query is the caller's job.
    fn search(&self, term: &str) -> &[Posting] {
        self.postings.get(term).map(Vec::as_slice).unwrap_or(&[])
    }

    /// The posting for `term` in `doc`, when the document contains
    /// the term. The postings list is ascending in document id, so
    /// this is a binary search rather than a scan.
    fn posting(&self, term: &str, doc: u32) -> Option<&Posting> {
        let postings = self.search(term);
        let found = postings.binary_search_by_key(&doc, |p| p.doc);
        found.ok().map(|i| &postings[i])
    }

    /// Where each occurrence of `term` sits in document `doc`'s term
    /// sequence. Empty when the document does not contain the term.
    fn positions(&self, term: &str, doc: u32) -> &[u32] {
        match self.posting(term, doc) {
            Some(p) => &p.positions,
            None => &[],
        }
    }

    /// Every dictionary term within `max` edits of `term`, nearest
    /// first, each with its distance.
    ///
    /// This step's whole idea: the query term is not in the dictionary
    /// — a typo guarantees it — so the dictionary is searched instead
    /// of looked up. The exact term is its own neighbour, at distance
    /// zero.
    ///
    /// The order is deterministic. HashMap iteration is not, so the
    /// hits are sorted by distance and then by term.
    fn fuzzy(&self, term: &str, max: usize) -> Vec<(&str, usize)> {
        let mut hits: Vec<(&str, usize)> = self
            .postings
            .keys()
            .filter_map(|candidate| {
                let distance = edit_distance_within(term, candidate, max)?;
                Some((candidate.as_str(), distance))
            })
            .collect();
        hits.sort_unstable_by(|a, b| a.1.cmp(&b.1).then_with(|| a.0.cmp(b.0)));
        hits
    }

    /// The documents where `terms` appear one after another, in
    /// order: the phrase "borrow checker" matches "the borrow checker
    /// enforces" and not "the checker borrows".
    ///
    /// The terms are the normalised ones — what the index holds, not
    /// what the reader typed. An empty phrase matches nothing: there
    /// is no adjacency to find.
    fn phrase(&self, terms: &[&str]) -> Vec<u32> {
        // A document can only match if it holds every term, so the
        // candidates are the first term's postings: every document
        // the phrase matches is in that list.
        let Some(first) = terms.first() else {
            return Vec::new();
        };
        let mut matches = Vec::new();
        'postings: for posting in self.search(first) {
            // One occurrence of the first term has to be followed by
            // the second one position later, the third two later,
            // and so on.
            for &start in &posting.positions {
                let consecutive = terms[1..]
                    .iter()
                    .enumerate()
                    .all(|(offset, term)| {
                        self.positions(term, posting.doc)
                            .contains(&(start + 1 + offset as u32))
                    });
                if consecutive {
                    matches.push(posting.doc);
                    continue 'postings;
                }
            }
        }
        matches
    }

    /// The path a document was indexed under.
    fn path(&self, id: u32) -> &str {
        &self.documents[id as usize].path
    }

    /// How many terms a document holds, stop words excluded. They are
    /// not in the index, so they are not in the length either.
    fn length(&self, id: u32) -> u32 {
        self.documents[id as usize].length
    }

    /// The average document length in terms — the reference point BM25
    /// measures every document against. An empty index has no average
    /// and says 0.
    fn average_length(&self) -> f64 {
        if self.documents.is_empty() {
            return 0.0;
        }
        let total: u32 = self.documents.iter().map(|d| d.length).sum();
        total as f64 / self.documents.len() as f64
    }

    fn documents(&self) -> usize {
        self.documents.len()
    }

    fn terms(&self) -> usize {
        self.postings.len()
    }

    /// Every term with its postings, in sorted order — the order `save`
    /// writes them in.
    fn postings(&self) -> Vec<(&str, &[Posting])> {
        let mut entries: Vec<(&str, &[Posting])> = self
            .postings
            .iter()
            .map(|(term, postings)| (term.as_str(), postings.as_slice()))
            .collect();
        entries.sort_unstable_by(|a, b| a.0.cmp(b.0));
        entries
    }

    /// Rank the documents containing `term` by BM25, best first. Each
    /// result is (document, term frequency, score).
    ///
    /// The score is the term's weight — the inverse document frequency
    /// from step 5 — times BM25's term-frequency component: a count that
    /// saturates as it grows, over a length measured against the
    /// collection average. A query with several terms sums one
    /// contribution per term; this method asks about one at a time.
    ///
    /// Equal scores keep the input order, and postings arrive in
    /// ascending document order, so ties come out in document order.
    fn rank(&self, term: &str) -> Vec<(u32, u32, f64)> {
        let postings = self.search(term);
        let weight = idf(postings.len(), self.documents());
        let avgdl = self.average_length();
        let mut ranked: Vec<(u32, u32, f64)> = postings
            .iter()
            .map(|p| {
                let tf = p.positions.len() as u32;
                (
                    p.doc,
                    tf,
                    weight * tf_score(tf, self.length(p.doc) as f64, avgdl, K1, B),
                )
            })
            .collect();
        // f64 is not Ord, because of NaN. total_cmp gives every float a
        // place in a total order, and sort_by is stable, so equal scores
        // keep the order they arrived in.
        ranked.sort_by(|a, b| b.2.total_cmp(&a.2));
        ranked
    }

    /// BM25 for every document in `docs`, summing one contribution per
    /// term in `terms`: a query about two terms scores a document by
    /// both, which is what makes a multi-term query rank.
    ///
    /// Best first. Equal scores keep the input order — and the input is
    /// ascending document ids, from the set operations below — so ties
    /// come out in document order, the same rule `rank` follows.
    fn score(&self, docs: &[u32], terms: &[&str]) -> Vec<(u32, f64)> {
        let avgdl = self.average_length();
        // One weight per term, worked out once: the idf depends on how
        // many documents hold the term, not on which document is being
        // scored.
        let weights: Vec<f64> = terms
            .iter()
            .map(|term| idf(self.search(term).len(), self.documents()))
            .collect();
        let mut scored: Vec<(u32, f64)> = docs
            .iter()
            .map(|&doc| {
                let total: f64 = terms
                    .iter()
                    .zip(&weights)
                    .map(|(term, weight)| {
                        let tf = self.positions(term, doc).len() as u32;
                        weight * tf_score(tf, self.length(doc) as f64, avgdl, K1, B)
                    })
                    .sum();
                (doc, total)
            })
            .collect();
        scored.sort_by(|a, b| b.1.total_cmp(&a.1));
        scored
    }

    /// The documents one query token matches, and the terms it scores
    /// by.
    ///
    /// A quoted token is a phrase: its words go through the tokeniser,
    /// so stop words drop out and what is left has to be adjacent. A
    /// bare word is one word, normalised the same way — and a word
    /// that normalises to several terms ("borrow-checker") is the
    /// phrase they form, because that is what the hyphen meant in the
    /// text.
    fn operand(&self, token: &str) -> Result<(BTreeSet<u32>, Vec<String>), QueryError> {
        let text = token
            .strip_prefix('"')
            .map(|inside| inside.strip_suffix('"').unwrap_or(inside))
            .unwrap_or(token);
        // A quoted token is a phrase, and a phrase is exact: the tilde
        // applies to bare words only.
        if !token.starts_with('"') {
            if let Some((word, max)) = parse_fuzzy(text)? {
                return Ok(self.fuzzy_operand(word, max));
            }
        }
        let terms: Vec<String> = tokenize(text).collect();
        let refs: Vec<&str> = terms.iter().map(String::as_str).collect();
        let docs = match refs.as_slice() {
            [] => BTreeSet::new(),
            [only] => self.search(only).iter().map(|p| p.doc).collect(),
            phrase => self.phrase(phrase).into_iter().collect(),
        };
        Ok((docs, terms))
    }

    /// The documents one fuzzy word matches, and the terms they score
    /// by: every dictionary term within the radius, and the union of
    /// their postings.
    ///
    /// The word the reader typed is not in the dictionary — that is
    /// what makes it fuzzy — so it cannot score anything. Each variant
    /// contributes its own BM25 score, exactly as the terms of an OR
    /// do; a nearer variant is not boosted over a farther one, which
    /// is a simplification of Lucene's distance-blended rewrite.
    ///
    /// The word is normalised first, by the tokeniser the index used.
    /// A stop word matches nothing, exactly as it does without the
    /// tilde. A word that normalises to several terms —
    /// "borrow-checker", say — is a phrase this operator does not
    /// cover: it matches nothing rather than guessing which half the
    /// typo was in.
    fn fuzzy_operand(&self, word: &str, max: usize) -> (BTreeSet<u32>, Vec<String>) {
        let terms: Vec<String> = tokenize(word).collect();
        if terms.len() != 1 {
            return (BTreeSet::new(), Vec::new());
        }
        let hits = self.fuzzy(&terms[0], max);
        let docs: BTreeSet<u32> = hits
            .iter()
            .flat_map(|&(term, _)| self.search(term).iter().map(|p| p.doc))
            .collect();
        let scored_by: Vec<String> = hits.iter().map(|&(term, _)| term.to_string()).collect();
        (docs, scored_by)
    }

    /// Evaluate a boolean query: the documents that match, and the
    /// terms their scores come from.
    ///
    /// The grammar is terms, "quoted phrases", and the operators AND,
    /// OR and NOT, evaluated left to right with equal precedence —
    /// "a OR b AND c" is "(a OR b) AND c", which is not how Lucene
    /// reads it. NOT applies to the operand that follows it, and
    /// between two operands it reads as AND: "borrow NOT checker" is
    /// "borrow AND NOT checker". Two operands with no operator
    /// between them mean AND as well, so "borrow checker" and
    /// "borrow AND checker" ask the same question.
    fn evaluate(&self, query: &str) -> Result<Matches, QueryError> {
        let tokens = query_tokens(query);
        if tokens.is_empty() {
            return Err(QueryError::Empty);
        }

        let mut matched: Option<BTreeSet<u32>> = None;
        let mut terms: Vec<String> = Vec::new();
        // The operator waiting for its right-hand operand. AND is the
        // default: two operands in a row are ANDed.
        let mut op = Operator::And;
        let mut negate = false;
        // Whether the next token has to be an operand. True at the
        // start — a query opens with an operand, NOT may come first —
        // and true again after every operator.
        let mut want_operand = true;

        for token in tokens {
            if !token.starts_with('"') {
                match token.as_str() {
                    "AND" | "OR" => {
                        if want_operand {
                            // Two operators in a row, or a query that
                            // opens with one.
                            return Err(QueryError::DanglingOperator);
                        }
                        op = if token == "AND" {
                            Operator::And
                        } else {
                            Operator::Or
                        };
                        want_operand = true;
                        continue;
                    }
                    "NOT" => {
                        negate = !negate;
                        want_operand = true;
                        continue;
                    }
                    _ => {}
                }
            }

            let (docs, operand_terms) = self.operand(&token)?;
            let negated = negate;
            negate = false;
            let docs = if negated {
                // NOT is the complement inside the collection: every
                // document the index has, minus the operand's.
                let all: BTreeSet<u32> = (0..self.documents() as u32).collect();
                all.difference(&docs).copied().collect()
            } else {
                docs
            };
            matched = Some(match matched {
                None => docs,
                Some(so_far) => match op {
                    Operator::And => so_far.intersection(&docs).copied().collect(),
                    Operator::Or => so_far.union(&docs).copied().collect(),
                },
            });
            if !negated {
                terms.extend(operand_terms);
            }
            op = Operator::And;
            want_operand = false;
        }

        if want_operand {
            // The query ended on an operator, or on a NOT.
            return Err(QueryError::DanglingOperator);
        }
        Ok(Matches {
            docs: matched.into_iter().flatten().collect(),
            terms,
        })
    }

    /// The documents a boolean query matches, ascending.
    fn boolean(&self, query: &str) -> Result<Vec<u32>, QueryError> {
        Ok(self.evaluate(query)?.docs)
    }

    /// Run a query and rank what it matched by BM25 over the query's
    /// positive terms.
    ///
    /// A query with no positive terms — "NOT checker", say — still
    /// returns its documents, but every score is zero and the order is
    /// document order: there is nothing to rank on.
    fn query(&self, query: &str) -> Result<Vec<(u32, f64)>, QueryError> {
        let matches = self.evaluate(query)?;
        let refs: Vec<&str> = matches.terms.iter().map(String::as_str).collect();
        Ok(self.score(&matches.docs, &refs))
    }

    /// Write the index to `path` as one binary file: the magic and the
    /// version, the documents with their lengths, then the dictionary
    /// with its postings lists, terms in sorted order.
    ///
    /// The file is built in memory and written in one call. At this size
    /// that is cheaper than a buffered writer, and it makes the whole
    /// file one value that can be compared, hashed or diffed.
    fn save(&self, path: impl AsRef<Path>) -> io::Result<()> {
        let mut out: Vec<u8> = Vec::new();
        out.extend_from_slice(MAGIC);
        out.extend_from_slice(&VERSION.to_le_bytes());
        out.extend_from_slice(&(self.documents.len() as u32).to_le_bytes());
        for document in &self.documents {
            put_str(&mut out, &document.path);
            out.extend_from_slice(&document.length.to_le_bytes());
        }
        out.extend_from_slice(&(self.terms() as u32).to_le_bytes());
        for (term, postings) in self.postings() {
            put_str(&mut out, term);
            out.extend_from_slice(&(postings.len() as u32).to_le_bytes());
            for posting in postings {
                out.extend_from_slice(&posting.doc.to_le_bytes());
                out.extend_from_slice(&(posting.positions.len() as u32).to_le_bytes());
                for position in &posting.positions {
                    out.extend_from_slice(&position.to_le_bytes());
                }
            }
        }
        fs::write(path, out)
    }

    /// Read an index back from `path`. Reading the file and interpreting
    /// it are two steps that fail differently: the first with an io
    /// error, the second with a `LoadError`.
    fn load(path: impl AsRef<Path>) -> Result<Index, LoadError> {
        let bytes = fs::read(path).map_err(LoadError::Io)?;
        Index::load_bytes(&bytes)
    }

    /// Parse the bytes of an index file. Every field is length-prefixed,
    /// so the reader never has to guess where one field ends and the
    /// next begins — and a file that ends early is a `LoadError`, not a
    /// panic.
    fn load_bytes(bytes: &[u8]) -> Result<Index, LoadError> {
        let mut reader = Reader::new(bytes);
        if reader.take(MAGIC.len())? != MAGIC {
            return Err(LoadError::BadMagic);
        }
        let version = reader.u32()?;
        if version != VERSION {
            return Err(LoadError::BadVersion(version));
        }

        let mut index = Index::new();
        for _ in 0..reader.u32()? {
            let path = reader.string()?;
            let length = reader.u32()?;
            index.documents.push(Document { path, length });
        }
        for _ in 0..reader.u32()? {
            let term = reader.string()?;
            let mut postings = Vec::new();
            let mut previous: Option<u32> = None;
            for _ in 0..reader.u32()? {
                let doc = reader.u32()?;
                let count = reader.u32()? as usize;
                let mut positions = Vec::with_capacity(count);
                for _ in 0..count {
                    positions.push(reader.u32()?);
                }
                // Step 2 promised ascending, duplicate-free lists, and
                // the ranker assumes it: a hand-edited file that breaks
                // the order is refused here rather than trusted.
                if previous.is_some_and(|last| doc <= last) {
                    return Err(LoadError::BadPostings(term));
                }
                previous = Some(doc);
                postings.push(Posting { doc, positions });
            }
            index.postings.insert(term, postings);
        }
        if reader.pos != reader.data.len() {
            return Err(LoadError::TrailingBytes);
        }
        Ok(index)
    }
}

/// How the next operand combines with the documents matched so far.
/// Two operands in a row mean AND, so this is also the default.
#[derive(Clone, Copy, PartialEq)]
enum Operator {
    And,
    Or,
}

/// What can be wrong with a query. A query is typed by a person, so it
/// can be malformed in ways an index file cannot.
#[derive(Debug)]
enum QueryError {
    /// Nothing to ask: the query holds no operands at all.
    Empty,
    /// An operator with nothing on one side of it: the query opens
    /// with AND or OR, ends with an operator or a NOT, or has two
    /// operators in a row.
    DanglingOperator,
    /// A tilde with no radius after it that this engine has:
    /// "borow~3" asks for more edits than the cap allows, and
    /// "borow~x" is not a radius at all.
    BadFuzzy(String),
}

impl fmt::Display for QueryError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            QueryError::Empty => write!(f, "the query is empty"),
            QueryError::DanglingOperator => {
                write!(f, "an operator in this query is missing its operand")
            }
            QueryError::BadFuzzy(token) => {
                write!(f, "the fuzzy operator on {token:?} needs an edit count between 0 and {MAX_EDITS}")
            }
        }
    }
}

impl Error for QueryError {}

/// What a query matched: the documents, and the terms their scores are
/// built from. A NOT'ed operand's terms are left out — they selected
/// documents to remove, not documents to rank.
struct Matches {
    docs: Vec<u32>,
    terms: Vec<String>,
}

/// Split a query into tokens: bare words, "quoted phrases", and the
/// operators AND, OR and NOT. The operators are capitals only, so a
/// document about the word "and" stays searchable. Whitespace between
/// tokens is dropped; whitespace inside quotes is kept, and the quotes
/// stay on the token so the parser can tell `"borrow checker"` — one
/// phrase — from `borrow checker` — two terms with AND between them.
fn query_tokens(query: &str) -> Vec<String> {
    let mut tokens = Vec::new();
    let mut token = String::new();
    let mut in_quotes = false;
    for c in query.chars() {
        if c == '"' {
            in_quotes = !in_quotes;
            token.push(c);
            if !in_quotes {
                // A closing quote ends the token even mid-word.
                tokens.push(std::mem::take(&mut token));
            }
        } else if c.is_whitespace() && !in_quotes {
            if !token.is_empty() {
                tokens.push(std::mem::take(&mut token));
            }
        } else {
            token.push(c);
        }
    }
    if !token.is_empty() {
        tokens.push(token);
    }
    tokens
}

/// The largest radius the `~` operator accepts. Lucene caps its fuzzy
/// edits at two for the same reason: past two edits a radius stops
/// correcting typos and starts matching half the dictionary.
const MAX_EDITS: usize = 2;

/// The radius a bare `~` means when no number follows it. Two, which
/// is Lucene's default too.
const DEFAULT_MAX_EDITS: usize = 2;

/// Split a fuzzy token: "borow~2" is the word "borow" with a radius
/// of 2, and "borow~" is the same word with the default radius.
/// `Ok(None)` means the token carries no tilde at all, and the
/// caller's ordinary exact path applies.
///
/// A tilde followed by anything that is not a radius this engine has
/// is an error, the way a dangling operator is: the query said
/// something the grammar does not cover, and guessing is worse than
/// refusing.
fn parse_fuzzy(token: &str) -> Result<Option<(&str, usize)>, QueryError> {
    let Some((word, rest)) = token.split_once('~') else {
        return Ok(None);
    };
    let max = if rest.is_empty() {
        DEFAULT_MAX_EDITS
    } else {
        match rest.parse::<usize>() {
            Ok(max) if max <= MAX_EDITS => max,
            _ => return Err(QueryError::BadFuzzy(token.to_string())),
        }
    };
    Ok(Some((word, max)))
}

/// The Levenshtein distance between `a` and `b`: the fewest
/// single-character insertions, deletions and substitutions that turn
/// one into the other. Counted over characters, not bytes, because
/// the tokeniser is Unicode-aware and a distance that is not would be
/// its own kind of wrong.
///
/// Transpositions are not edits here, so "teh" is two edits from
/// "the" — two substitutions. Lucene's default counts a transposition
/// as one, and that gap is a known difference.
fn edit_distance(a: &str, b: &str) -> usize {
    let a: Vec<char> = a.chars().collect();
    let b: Vec<char> = b.chars().collect();
    // Two rows of the table. Row i holds the distance between the
    // first i characters of `a` and every prefix of `b`, and row i+1
    // is computed from row i alone, so m * n entries are filled with
    // n + 1 of them alive at a time.
    //
    // The first row is the empty prefix of `a`: turning it into the
    // first j characters of `b` takes j insertions.
    let mut previous: Vec<usize> = (0..=b.len()).collect();
    let mut current = vec![0usize; b.len() + 1];
    for (i, ca) in a.iter().enumerate() {
        // The first column is the empty prefix of `b`: turning the
        // first i + 1 characters of `a` into nothing takes i + 1
        // deletions.
        current[0] = i + 1;
        for (j, cb) in b.iter().enumerate() {
            let cost = usize::from(ca != cb);
            current[j + 1] = (previous[j + 1] + 1) // a deletion
                .min(current[j] + 1) // an insertion
                .min(previous[j] + cost); // a match, or a substitution
        }
        std::mem::swap(&mut previous, &mut current);
    }
    // The last swap left the final row in `previous`.
    previous[b.len()]
}

/// The distance between `a` and `b` when it is at most `max`, and
/// `None` when it is not.
///
/// The length check comes first because it is O(1) against the DP's
/// O(m * n): the distance can never be smaller than the difference in
/// lengths, so a candidate that differs in length by more than the
/// radius is out without a table being filled.
fn edit_distance_within(a: &str, b: &str, max: usize) -> Option<usize> {
    if a.chars().count().abs_diff(b.chars().count()) > max {
        return None;
    }
    let distance = edit_distance(a, b);
    (distance <= max).then_some(distance)
}

/// Count a sorted term list in runs: each distinct term once, with the
/// positions of its occurrences. [("fox", 0), ("dog", 1), ("fox", 2)]
/// counts "fox" at positions 0 and 2, and "dog" at 1.
fn count_terms(sorted: &[(u32, String)]) -> Vec<(&str, Vec<u32>)> {
    let mut counts = Vec::new();
    let mut start = 0;
    while start < sorted.len() {
        let mut end = start + 1;
        while end < sorted.len() && sorted[end].1 == sorted[start].1 {
            end += 1;
        }
        // The run is in position order — the sort put it there — so the
        // positions come out ascending.
        let positions: Vec<u32> = sorted[start..end].iter().map(|(pos, _)| *pos).collect();
        counts.push((sorted[start].1.as_str(), positions));
        start = end;
    }
    counts
}

/// How much information a term carries: the natural log of the document
/// count over the number of documents containing the term.
///
/// A term in every document scores zero — it cannot tell two documents
/// apart. A term in one document scores the most. The zero for an empty
/// postings list is for callers that pass one: a term in no document is
/// not in the dictionary at all.
fn idf(df: usize, n: usize) -> f64 {
    if df == 0 {
        return 0.0;
    }
    (n as f64 / df as f64).ln()
}

/// BM25's two constants, at the values Lucene ships. They are the only
/// numbers in the formula that are not counted from the corpus.
///
/// k1 saturates term frequency: the higher it is, the longer extra
/// mentions keep mattering, with the ceiling at k1 + 1. b divides out
/// document length: 0 ignores length, 1 scales the whole k1 by the
/// document's length against the average.
const K1: f64 = 1.2;
const B: f64 = 0.75;

/// BM25's term-frequency component: how much a term's `tf` occurrences
/// in a document of `dl` terms are worth in a collection whose average
/// document is `avgdl` terms long.
///
/// The numerator grows with tf; so does the denominator, and faster —
/// which is what saturates the curve. As tf grows the score approaches
/// k1 + 1 and stops: at Lucene's k1 the ceiling is 2.2, so the twentieth
/// mention of a term adds very little to the tenth. k1 = 0 makes every
/// match worth the same, however often the term repeats.
///
/// b sets how much of the length difference is divided out. At b = 0
/// length is ignored and the bias step 5 demonstrated comes straight
/// back; at b = 1 the whole k1 scales with dl / avgdl, which punishes
/// long documents even when the repetition is genuine.
///
/// `avgdl` must be positive. A posting exists because its term is in
/// the document, so any document with a posting has length at least
/// one, and an index with postings averages above zero.
fn tf_score(tf: u32, dl: f64, avgdl: f64, k1: f64, b: f64) -> f64 {
    tf as f64 * (k1 + 1.0) / (tf as f64 + k1 * (1.0 - b + b * dl / avgdl))
}

/// Append a length-prefixed UTF-8 string: a u32 byte count, then the
/// bytes. A binary file has no separator to scan for, so the length is
/// the separator.
fn put_str(out: &mut Vec<u8>, text: &str) {
    out.extend_from_slice(&(text.len() as u32).to_le_bytes());
    out.extend_from_slice(text.as_bytes());
}

/// Everything that can be wrong with an index file. The disk it sits on
/// is a separate concern, carried along as `Io`.
#[derive(Debug)]
enum LoadError {
    /// The file does not start with the magic this engine writes.
    BadMagic,
    /// The magic is right, but the version is not one this build reads.
    BadVersion(u32),
    /// The file ends where another field was expected.
    Truncated,
    /// A length-prefixed field holds bytes that are not UTF-8.
    BadUtf8,
    /// Bytes were left over after the last field the format describes.
    TrailingBytes,
    /// A postings list whose document ids are not ascending.
    BadPostings(String),
    /// The file could not be read at all.
    Io(io::Error),
}

impl fmt::Display for LoadError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            LoadError::BadMagic => write!(f, "not a haystack index: the magic bytes are wrong"),
            LoadError::BadVersion(v) => write!(f, "unsupported index version {v}"),
            LoadError::Truncated => write!(f, "the file ends where another field was expected"),
            LoadError::BadUtf8 => write!(f, "a length-prefixed field is not valid UTF-8"),
            LoadError::TrailingBytes => write!(f, "the file has bytes after the last field"),
            LoadError::BadPostings(term) => {
                write!(f, "the postings list for {term:?} is not in ascending document order")
            }
            LoadError::Io(e) => write!(f, "{e}"),
        }
    }
}

impl Error for LoadError {
    fn source(&self) -> Option<&(dyn Error + 'static)> {
        match self {
            LoadError::Io(e) => Some(e),
            _ => None,
        }
    }
}

/// A cursor over an index file's bytes. Every read checks the end first,
/// so a truncated file is a `LoadError` instead of a panic.
struct Reader<'a> {
    data: &'a [u8],
    pos: usize,
}

impl<'a> Reader<'a> {
    fn new(data: &'a [u8]) -> Self {
        Reader { data, pos: 0 }
    }

    /// The next `len` bytes, or `Truncated` when the file ends first.
    fn take(&mut self, len: usize) -> Result<&'a [u8], LoadError> {
        let end = self.pos.checked_add(len).ok_or(LoadError::Truncated)?;
        let bytes = self.data.get(self.pos..end).ok_or(LoadError::Truncated)?;
        self.pos = end;
        Ok(bytes)
    }

    /// The next four bytes, as a little-endian u32.
    fn u32(&mut self) -> Result<u32, LoadError> {
        let bytes: [u8; 4] = self.take(4)?.try_into().unwrap();
        Ok(u32::from_le_bytes(bytes))
    }

    /// The next length-prefixed UTF-8 string.
    fn string(&mut self) -> Result<String, LoadError> {
        let len = self.u32()? as usize;
        let bytes = self.take(len)?;
        std::str::from_utf8(bytes)
            .map(str::to_owned)
            .map_err(|_| LoadError::BadUtf8)
    }
}

/// The first eight bytes of every index file: eight ASCII bytes that no
/// file this engine reads by accident starts with.
const MAGIC: &[u8] = b"haystack";

/// The format version. A file announcing any other number is refused.
/// Version 2 added a length to every document and a term frequency to
/// every posting; version 3 keeps the lengths and replaces the
/// frequency with the positions of each occurrence — the frequency is
/// their count, and a file carrying both could disagree with itself.
const VERSION: u32 = 3;

/// Where the demo writes its index. The file is output, not source: it
/// is gitignored and rebuilt by every run.
const INDEX_PATH: &str = "haystack.idx";

/// The demo corpus: one file is one document, and the path is the id.
///
/// The last entry is deliberately long and mentions "borrow" five times
/// in passing. It is the document length bias in one file: more terms
/// to say less.
fn corpus() -> [(&'static str, &'static str); 6] {
    [
        (
            "docs/ownership.md",
            "Ownership and borrowing are the two ideas Rust is built on. Every value has one owner, and the owner going out of scope drops it.",
        ),
        (
            "docs/borrow-checker.md",
            "The borrow checker enforces the borrowing rules at compile time. A borrow must not outlive the owner of the borrowed value.",
        ),
        (
            "docs/lifetimes.md",
            "A lifetime is the region of code for which a reference is valid. The borrow checker uses lifetimes to keep every reference in scope.",
        ),
        (
            "docs/iterators.md",
            "Iterators are lazy: each call to next advances the iterator by one. An adapter such as map borrows the iterator it wraps.",
        ),
        (
            "docs/error-handling.md",
            "Recoverable errors are values of type Result. The question mark operator returns an error to the caller early.",
        ),
        (
            "docs/style-guide.md",
            "House style for these pages: prefer short sentences, and name the thing you mean. When a function borrows a value, say what it borrows and for how long. A struct that borrows from its input should say so in its name. Tests borrow fixtures from the module above them, and an example that borrows code from another chapter says where it came from. Prefer the active voice, cut words like simply and just, and keep paragraphs under six lines. One idea per paragraph, a heading every screenful, and the exception to a rule written next to the rule.",
        ),
    ]
}

fn main() -> Result<(), Box<dyn Error>> {
    let mut index = Index::new();
    for (path, text) in &corpus() {
        index.add_document(path, text);
    }
    println!(
        "{} documents, {} distinct terms",
        index.documents(),
        index.terms()
    );

    index.save(INDEX_PATH)?;
    let written = fs::read(INDEX_PATH)?;
    println!("\nsaved to {INDEX_PATH}: {} bytes", written.len());

    // The dictionary is written in sorted order, so the same index
    // always produces the same bytes.
    index.save(INDEX_PATH)?;
    let rewritten = fs::read(INDEX_PATH)?;
    println!(
        "saved again: {} bytes, byte-identical: {}",
        rewritten.len(),
        rewritten == written
    );

    let loaded = Index::load(INDEX_PATH)?;
    println!(
        "\nloaded back: {} documents, {} terms",
        loaded.documents(),
        loaded.terms()
    );

    // What a posting carries now: the document, and where each
    // occurrence sits in it.
    println!("\npostings for \"borrow\" — count, then positions:");
    for posting in loaded.search("borrow") {
        println!(
            "  {:<26} tf={}  positions={:?}",
            loaded.path(posting.doc),
            posting.positions.len(),
            posting.positions
        );
    }

    // The single-term ranker from step 6, unchanged: the scores are
    // the same, now read off the position counts.
    println!("\nquery \"borrow\", ranked by BM25:");
    for (doc, tf, score) in loaded.rank("borrow") {
        println!(
            "  {score:>7.4}  {:<26} tf={tf}  len={}",
            loaded.path(doc),
            loaded.length(doc)
        );
    }

    // A phrase is a different question from its terms: the words have
    // to be next to each other, in order.
    println!("\nphrase \"borrow checker\":");
    for doc in loaded.phrase(&["borrow", "checker"]) {
        println!("  {}", loaded.path(doc));
    }
    println!("phrase \"checker borrow\" — the other order:");
    if loaded.phrase(&["checker", "borrow"]).is_empty() {
        println!("  no documents");
    }

    // AND only asks whether both terms are there. The phrase also
    // asks where: "value" and "owner" share two documents, but sit
    // next to each other in neither.
    println!("\n\"value AND owner\":");
    for doc in loaded.boolean("value AND owner").unwrap() {
        println!("  {}", loaded.path(doc));
    }
    println!("phrase \"value owner\":");
    if loaded.phrase(&["value", "owner"]).is_empty() {
        println!("  no documents");
    }

    for query in ["borrow AND checker", "borrow OR value", "borrow NOT lifetime"] {
        println!("\nquery \"{query}\":");
        match loaded.query(query) {
            Ok(ranked) => {
                for (doc, score) in ranked {
                    println!("  {score:>7.4}  {}", loaded.path(doc));
                }
            }
            Err(e) => println!("  {e}"),
        }
    }

    // Step 8: a typo in a query used to miss, because the dictionary
    // has no such key. Now the dictionary itself is searched by edit
    // distance.
    println!("\nfuzzy \"borow\" within 1 edit:");
    for (term, distance) in loaded.fuzzy("borow", 1) {
        println!("  {term:<12} distance {distance}");
    }
    println!("fuzzy \"liefetime\" within 2 edits:");
    for (term, distance) in loaded.fuzzy("liefetime", 2) {
        println!("  {term:<12} distance {distance}");
    }
    println!("fuzzy \"valu\" within 2 edits — the radius reaches further than you would think:");
    for (term, distance) in loaded.fuzzy("valu", 2) {
        println!("  {term:<12} distance {distance}");
    }
    println!("fuzzy \"zzzzz\" within 2 edits:");
    if loaded.fuzzy("zzzzz", 2).is_empty() {
        println!("  no terms");
    }

    // The typo'd query answers what the reader meant, and ranks it
    // the way the correct spelling does: "borrow" is the only variant
    // within reach, so it is the only term it scores by.
    println!("\n\"borow~\" and \"borrow\" answer the same:");
    println!(
        "  {}",
        loaded.query("borow~").unwrap() == loaded.query("borrow").unwrap()
    );

    // A radius that reaches two terms scores by both, the way an OR
    // does: "valu" is one edit from "value" and two from "valid", and
    // each document scores by the one it holds.
    println!("\nquery \"valu~2\":");
    for (doc, score) in loaded.query("valu~2").unwrap() {
        println!("  {score:>7.4}  {}", loaded.path(doc));
    }

    // What the operator refuses to guess at.
    println!("\nquery \"the~\" — a stop word:");
    if loaded.query("the~").unwrap().is_empty() {
        println!("  no documents");
    }
    println!("query \"borrow-checker~\" — a hyphenated word:");
    if loaded.query("borrow-checker~").unwrap().is_empty() {
        println!("  no documents");
    }
    println!("\nquery \"borow~3\" — a radius past the cap:");
    if let Err(e) = loaded.query("borow~3") {
        println!("  {e}");
    }
    println!("query \"borow~x\" — not a radius at all:");
    if let Err(e) = loaded.query("borow~x") {
        println!("  {e}");
    }

    // The query grammar refuses an operator with nothing on one side
    // of it, rather than guessing what was meant.
    println!("\nquery \"borrow AND\":");
    if let Err(e) = loaded.query("borrow AND") {
        println!("  {e}");
    }

    // The version field, doing its job: the same file with the version
    // patched to 2 — the format this step replaced — is a file this
    // build does not read.
    let mut stale = written.clone();
    stale[8..12].copy_from_slice(&2u32.to_le_bytes());
    if let Err(e) = Index::load_bytes(&stale) {
        println!("\na version 2 file: {e}");
    }

    Ok(())
}

/// The stop words: terms so common that indexing them costs memory and
/// buys nothing. This is the classic short English list; a production
/// engine keeps a longer one, and one per language.
const STOP_WORDS: &[&str] = &[
    "a", "am", "an", "and", "are", "as", "at", "be", "been", "being", "but", "by", "can", "could",
    "did", "do", "does", "for", "from", "had", "has", "have", "he", "her", "his", "how", "i", "if",
    "in", "into", "is", "it", "its", "may", "might", "must", "no", "nor", "not", "of", "on", "or",
    "our", "shall", "she", "should", "so", "such", "than", "that", "the", "their", "them", "then",
    "there", "these", "they", "this", "those", "through", "to", "us", "was", "we", "were", "what",
    "when", "where", "which", "while", "who", "whom", "will", "with", "would", "you", "your",
];

fn is_stop_word(word: &str) -> bool {
    STOP_WORDS.contains(&word)
}

/// Shortest stem worth keeping. Without the guard "ring" stems to "r".
const MIN_STEM: usize = 3;

/// Strip `suffix`, but only when a stem of at least `MIN_STEM`
/// characters is left.
fn strip_suffix(word: &str, suffix: &str) -> Option<String> {
    let base = word.strip_suffix(suffix)?;
    (base.chars().count() >= MIN_STEM).then_some(base.to_string())
}

/// "runn" -> "run", "dropp" -> "drop": a doubled final consonant is
/// usually the suffix's doing. l, s and z double naturally, so
/// "class", "fall" and "buzz" keep both letters.
fn undouble(stem: String) -> String {
    let mut chars: Vec<char> = stem.chars().collect();
    if chars.len() >= 2 {
        let (last, before) = (chars[chars.len() - 1], chars[chars.len() - 2]);
        if last == before && !matches!(last, 'l' | 's' | 'z') {
            chars.pop();
        }
    }
    chars.into_iter().collect()
}

/// "boxes" -> "box", "watches" -> "watch", "classes" -> "class":
/// after a sibilant that is not a bare "s", the plural's "es" detaches.
/// Everywhere else the "s" alone is the marker, so "causes" -> "cause"
/// and "buses" -> "buse", which is a known miss.
fn strip_sibilant_es(word: &str) -> Option<String> {
    let base = word.strip_suffix("es")?;
    let sibilant = base.ends_with('x')
        || base.ends_with('z')
        || base.ends_with("ss")
        || base.ends_with("ch")
        || base.ends_with("sh");
    if !sibilant || base.chars().count() < MIN_STEM {
        return None;
    }
    Some(base.to_string())
}

/// A small rule-based stemmer: strip one inflectional suffix, then fix
/// the doubling it left behind. "borrow", "borrows", "borrowed" and
/// "borrowing" all come out as "borrow".
///
/// It produces terms, not lemmas: "built" ends in no suffix it knows
/// and stays whole, and "ownership" does not stem at all. Porter's
/// algorithm is the full version of this idea; this is its small
/// cousin.
fn stem(word: &str) -> String {
    if let Some(base) = strip_suffix(word, "ing") {
        return undouble(base);
    }
    if let Some(base) = strip_suffix(word, "ed") {
        return undouble(base);
    }
    if let Some(base) = strip_sibilant_es(word) {
        return base;
    }
    if let Some(base) = strip_suffix(word, "s") {
        return base;
    }
    word.to_string()
}

/// Split text into terms: lowercase, split on anything that is not a
/// letter or a digit, drop stop words, and stem what is left.
///
/// The terms are owned. Step 2's version handed back slices of the text
/// it was given; lowercasing a word builds a new String, and so does
/// stemming one, so the output cannot borrow `text` any more.
fn tokenize(text: &str) -> impl Iterator<Item = String> {
    text.split(|c: char| !c.is_alphanumeric())
        .filter(|word| !word.is_empty())
        .map(str::to_lowercase)
        .filter(|word| !is_stop_word(word))
        .map(|word| stem(&word))
}

#[cfg(test)]
mod tests {
    use super::*;

    fn sample() -> Index {
        let mut index = Index::new();
        index.add_document("a.md", "The Quick Brown Fox");
        index.add_document("b.md", "the lazy dog, the quick cat");
        index
    }

    /// Three documents: "fox" alone, "dog" alone, and both.
    fn three_docs() -> Index {
        let mut index = Index::new();
        index.add_document("a.md", "fox");
        index.add_document("b.md", "dog");
        index.add_document("c.md", "fox dog");
        index
    }

    /// The document ids in a term's postings, for the tests that only
    /// care which documents matched.
    fn ids(index: &Index, term: &str) -> Vec<u32> {
        index.search(term).iter().map(|p| p.doc).collect()
    }

    #[test]
    fn add_document_returns_the_id_it_gave() {
        let mut index = Index::new();
        assert_eq!(index.add_document("a.md", "fox"), 0);
        assert_eq!(index.add_document("b.md", "fox"), 1);
    }

    #[test]
    fn a_term_in_two_documents_lists_both() {
        let index = sample();
        assert_eq!(ids(&index, "quick"), [0, 1]);
    }

    #[test]
    fn a_term_repeated_in_one_document_lists_it_once() {
        let mut index = Index::new();
        index.add_document("a.md", "fox fox fox");
        assert_eq!(ids(&index, "fox"), [0]);
    }

    #[test]
    fn a_repeated_term_records_where_each_copy_sits() {
        let mut index = Index::new();
        index.add_document("a.md", "fox fox fox");
        assert_eq!(
            index.search("fox"),
            &[Posting {
                doc: 0,
                positions: vec![0, 1, 2],
            }]
        );
    }

    #[test]
    fn distinct_terms_in_one_document_get_one_posting_each() {
        let mut index = Index::new();
        index.add_document("a.md", "fox dog fox");
        assert_eq!(
            index.search("fox"),
            &[Posting {
                doc: 0,
                positions: vec![0, 2],
            }]
        );
        assert_eq!(
            index.search("dog"),
            &[Posting {
                doc: 0,
                positions: vec![1],
            }]
        );
    }

    #[test]
    fn the_term_frequency_is_the_position_count() {
        let mut index = Index::new();
        index.add_document("a.md", "fox dog fox bird fox");
        assert_eq!(index.positions("fox", 0), [0, 2, 4]);
    }

    #[test]
    fn positions_are_ascending() {
        let mut index = Index::new();
        index.add_document("a.md", "fox dog cat fox bird fox");
        let positions = index.positions("fox", 0);
        assert!(positions.windows(2).all(|pair| pair[0] < pair[1]));
    }

    #[test]
    fn positions_skip_the_stop_words_around_them() {
        let mut index = Index::new();
        // "the" is dropped, so "fox" is the first term the index sees
        // and sits at position 0.
        index.add_document("a.md", "the fox and the dog");
        assert_eq!(index.positions("fox", 0), [0]);
        assert_eq!(index.positions("dog", 0), [1]);
    }

    #[test]
    fn document_length_counts_the_terms_the_tokeniser_kept() {
        let mut index = Index::new();
        index.add_document("a.md", "The Quick Brown Fox");
        assert_eq!(index.length(0), 3); // "the" is a stop word
    }

    #[test]
    fn ids_are_in_insertion_order() {
        let index = sample();
        assert_eq!(index.path(0), "a.md");
        assert_eq!(index.path(1), "b.md");
        assert_eq!(ids(&index, "dog"), [1]);
    }

    #[test]
    fn a_missing_term_is_empty_not_an_error() {
        let index = sample();
        assert!(index.search("wolf").is_empty());
    }

    #[test]
    fn casing_and_punctuation_are_folded_away() {
        let index = sample();
        assert_eq!(ids(&index, "fox"), [0]);
        assert_eq!(ids(&index, "dog"), [1]);
    }

    #[test]
    fn stop_words_are_not_indexed() {
        let index = sample();
        assert!(index.search("the").is_empty());
        assert_eq!(ids(&index, "quick"), [0, 1]);
    }

    #[test]
    fn inflections_share_one_term() {
        let mut index = Index::new();
        index.add_document("a.md", "borrowing");
        index.add_document("b.md", "borrowed");
        index.add_document("c.md", "borrows");
        assert_eq!(ids(&index, "borrow"), [0, 1, 2]);
    }

    #[test]
    fn a_doubled_consonant_from_the_suffix_is_collapsed() {
        let mut index = Index::new();
        index.add_document("a.md", "running dropped");
        assert_eq!(ids(&index, "run"), [0]);
        assert_eq!(ids(&index, "drop"), [0]);
    }

    #[test]
    fn doubling_that_is_not_the_suffixs_fault_survives() {
        let mut index = Index::new();
        index.add_document("a.md", "classes");
        index.add_document("b.md", "boxes");
        index.add_document("c.md", "buzzes");
        assert_eq!(ids(&index, "class"), [0]);
        assert_eq!(ids(&index, "box"), [1]);
        assert_eq!(ids(&index, "buzz"), [2]);
    }

    #[test]
    fn a_stem_needs_three_characters() {
        let mut index = Index::new();
        index.add_document("a.md", "ring");
        assert_eq!(ids(&index, "ring"), [0]);
        assert!(index.search("r").is_empty());
    }

    #[test]
    fn case_folding_is_unicode_aware() {
        let mut index = Index::new();
        index.add_document("a.md", "Ärger");
        assert_eq!(ids(&index, "ärger"), [0]);
    }

    #[test]
    fn idf_is_zero_for_a_term_in_every_document() {
        assert_eq!(idf(2, 2), 0.0);
    }

    #[test]
    fn idf_falls_as_the_document_frequency_rises() {
        assert!(idf(1, 6) > idf(2, 6));
        assert!(idf(2, 6) > idf(5, 6));
        assert_eq!(idf(1, 6), 6.0f64.ln());
    }

    #[test]
    fn bm25_puts_the_highest_score_first() {
        let mut index = Index::new();
        index.add_document("a.md", "fox");
        index.add_document("b.md", "fox fox fox fox fox");
        index.add_document("c.md", "dog");
        let ranked = index.rank("fox");
        assert_eq!(ranked[0].0, 1);
        assert!(ranked[0].2 > ranked[1].2);
    }

    #[test]
    fn equal_documents_keep_document_order() {
        let mut index = Index::new();
        index.add_document("a.md", "fox");
        index.add_document("b.md", "fox");
        let ranked = index.rank("fox");
        // "fox" is in every document, so its weight is zero and the
        // scores are equal — and the stable sort keeps document order.
        assert_eq!(ranked.iter().map(|r| r.0).collect::<Vec<_>>(), [0, 1]);
        assert!(ranked.iter().all(|(_, _, score)| *score == 0.0));
    }

    /// The bias step 5 demonstrated, now fixed: on the demo corpus
    /// "borrow" ranks the short page about borrowing above the long
    /// page that mentions it in passing.
    #[test]
    fn bm25_lets_the_shorter_document_win() {
        let mut index = Index::new();
        for (path, text) in &corpus() {
            index.add_document(path, text);
        }
        let ranked = index.rank("borrow");
        assert_eq!(index.path(ranked[0].0), "docs/borrow-checker.md");
        assert_eq!(index.path(ranked[1].0), "docs/style-guide.md");
        // The gap is not a rounding error.
        assert!(ranked[0].2 > ranked[1].2 + 0.05);
    }

    /// Term frequency still does honest work when the more frequent
    /// document is also the more relevant one.
    #[test]
    fn a_frequent_term_in_a_relevant_document_still_wins() {
        let mut index = Index::new();
        for (path, text) in &corpus() {
            index.add_document(path, text);
        }
        let ranked = index.rank("owner");
        assert_eq!(index.path(ranked[0].0), "docs/ownership.md");
    }

    #[test]
    fn term_frequency_saturates() {
        let avg = 20.0;
        // Each doubling of the count adds less than the last...
        let once = tf_score(1, avg, avg, K1, B);
        let twice = tf_score(2, avg, avg, K1, B);
        let four = tf_score(4, avg, avg, K1, B);
        assert!(twice - once > four - twice);
        // ...and the ceiling is k1 + 1, never above it.
        let huge = tf_score(1_000_000, avg, avg, K1, B);
        assert!(huge < K1 + 1.0);
        assert!(huge > K1 + 0.99);
    }

    #[test]
    fn k1_of_zero_makes_frequency_irrelevant() {
        let avg = 20.0;
        assert_eq!(tf_score(1, avg, avg, 0.0, B), 1.0);
        assert_eq!(tf_score(50, avg, avg, 0.0, B), 1.0);
    }

    #[test]
    fn length_normalisation_off_leaves_length_alone() {
        // Same count, very different lengths, b = 0: equal scores.
        let short = tf_score(3, 10.0, 20.0, K1, 0.0);
        let long = tf_score(3, 40.0, 20.0, K1, 0.0);
        assert_eq!(short, long);
    }

    #[test]
    fn length_normalisation_on_favours_the_short_document() {
        let short = tf_score(3, 10.0, 20.0, K1, 1.0);
        let long = tf_score(3, 40.0, 20.0, K1, 1.0);
        assert!(short > long);
    }

    #[test]
    fn average_length_is_the_mean_of_the_document_lengths() {
        let index = sample();
        assert_eq!(index.average_length(), 3.5); // 3 and 4 terms
    }

    #[test]
    fn an_empty_index_has_no_average_length() {
        assert_eq!(Index::new().average_length(), 0.0);
    }

    // --- phrase queries ---

    #[test]
    fn a_phrase_matches_adjacent_terms_in_order() {
        let mut index = Index::new();
        index.add_document("a.md", "the quick brown fox");
        assert_eq!(index.phrase(&["quick", "brown"]), [0]);
        // The other order is a different phrase.
        assert_eq!(index.phrase(&["brown", "quick"]), []);
    }

    #[test]
    fn a_phrase_needs_the_terms_next_to_each_other() {
        let mut index = Index::new();
        index.add_document("a.md", "quick brown fox");
        assert!(index.phrase(&["quick", "fox"]).is_empty());
    }

    #[test]
    fn a_phrase_matches_inside_a_longer_document() {
        let mut index = Index::new();
        index.add_document("a.md", "one two borrow checker three four");
        assert_eq!(index.phrase(&["borrow", "checker"]), [0]);
    }

    #[test]
    fn a_phrase_across_several_documents() {
        let mut index = Index::new();
        index.add_document("a.md", "borrow checker");
        index.add_document("b.md", "checker borrow");
        index.add_document("c.md", "nothing here");
        assert_eq!(index.phrase(&["borrow", "checker"]), [0]);
    }

    /// Stop words are dropped before positions are counted, so a
    /// phrase can match across one: "owner value" finds "owner of the
    /// value". That is the trade-off step 3's tokeniser made, showing
    /// up here.
    #[test]
    fn a_phrase_can_match_across_a_dropped_stop_word() {
        let mut index = Index::new();
        index.add_document("a.md", "the owner of the value");
        assert_eq!(index.phrase(&["owner", "value"]), [0]);
    }

    #[test]
    fn an_empty_phrase_matches_nothing() {
        let index = Index::new();
        assert!(index.phrase(&[]).is_empty());
    }

    #[test]
    fn a_one_word_phrase_is_that_words_postings() {
        let mut index = Index::new();
        index.add_document("a.md", "fox");
        index.add_document("b.md", "dog fox");
        assert_eq!(index.phrase(&["fox"]), [0, 1]);
    }

    // --- boolean queries ---

    #[test]
    fn and_keeps_the_documents_with_both_terms() {
        let index = three_docs();
        assert_eq!(index.boolean("fox AND dog").unwrap(), [2]);
    }

    #[test]
    fn or_keeps_the_documents_with_either_term() {
        let index = three_docs();
        assert_eq!(index.boolean("fox OR dog").unwrap(), [0, 1, 2]);
    }

    #[test]
    fn not_removes_the_documents_with_the_term() {
        let index = three_docs();
        assert_eq!(index.boolean("fox NOT dog").unwrap(), [0]);
        assert_eq!(index.boolean("NOT fox").unwrap(), [1]);
    }

    #[test]
    fn two_terms_with_no_operator_mean_and() {
        let index = three_docs();
        assert_eq!(
            index.boolean("fox dog").unwrap(),
            index.boolean("fox AND dog").unwrap()
        );
    }

    /// The documented evaluation order: left to right, equal
    /// precedence. "fox OR dog AND cat" is "(fox OR dog) AND cat".
    #[test]
    fn operators_evaluate_left_to_right() {
        let mut index = Index::new();
        index.add_document("a.md", "fox");
        index.add_document("b.md", "dog");
        index.add_document("c.md", "cat");
        index.add_document("d.md", "fox cat");
        // (fox OR dog) AND cat: a and b drop out for want of "cat",
        // d has both. The other reading would also return a.
        assert_eq!(index.boolean("fox OR dog AND cat").unwrap(), [3]);
    }

    #[test]
    fn a_quoted_phrase_needs_adjacency_but_the_same_words_do_not() {
        let mut index = Index::new();
        index.add_document("a.md", "borrow checker");
        index.add_document("b.md", "checker and borrow far apart");
        // b holds both terms, but not next to each other.
        assert_eq!(index.boolean("\"borrow checker\"").unwrap(), [0]);
        assert_eq!(index.boolean("borrow checker").unwrap(), [0, 1]);
    }

    /// A hyphenated word is one word that normalises to two terms, so
    /// the query treats it as the phrase they form — which is what
    /// the hyphen meant in the text.
    #[test]
    fn a_hyphenated_word_is_a_phrase_in_disguise() {
        let mut index = Index::new();
        index.add_document("a.md", "borrow checker");
        index.add_document("b.md", "checker borrow");
        assert_eq!(index.boolean("borrow-checker").unwrap(), [0]);
    }

    #[test]
    fn a_stop_word_in_a_query_matches_nothing() {
        let index = three_docs();
        assert!(index.boolean("the").unwrap().is_empty());
        // An empty set on the right of an OR changes nothing.
        assert_eq!(index.boolean("fox OR the").unwrap(), [0, 2]);
    }

    #[test]
    fn double_negation_cancels() {
        let index = three_docs();
        assert_eq!(index.boolean("NOT NOT fox").unwrap(), [0, 2]);
    }

    #[test]
    fn a_query_that_breaks_the_grammar_is_refused() {
        let index = three_docs();
        assert!(index.boolean("fox AND").is_err());
        assert!(index.boolean("AND fox").is_err());
        assert!(index.boolean("fox NOT").is_err());
        assert!(index.boolean("fox AND OR dog").is_err());
    }

    #[test]
    fn an_empty_query_is_refused() {
        let index = three_docs();
        assert!(index.boolean("").is_err());
        assert!(index.boolean("   ").is_err());
    }

    #[test]
    fn a_multi_term_query_sums_one_contribution_per_term() {
        let index = three_docs();
        let both = index.query("fox AND dog").unwrap();
        let fox = index.query("fox").unwrap();
        let dog = index.query("dog").unwrap();
        // The document with both terms scores the sum of what each
        // term alone gives it.
        let both_score = both.iter().find(|(doc, _)| *doc == 2).unwrap().1;
        let fox_score = fox.iter().find(|(doc, _)| *doc == 2).unwrap().1;
        let dog_score = dog.iter().find(|(doc, _)| *doc == 2).unwrap().1;
        assert!((both_score - (fox_score + dog_score)).abs() < 1e-12);
    }

    #[test]
    fn a_query_with_no_positive_terms_scores_zero() {
        let index = three_docs();
        // "NOT fox" removes the documents to rank by, so the one that
        // is left has nothing to score on.
        let ranked = index.query("NOT fox").unwrap();
        assert_eq!(ranked.iter().map(|(doc, _)| *doc).collect::<Vec<_>>(), [1]);
        assert_eq!(ranked[0].1, 0.0);
    }

    // --- fuzzy matching ---

    #[test]
    fn the_distance_between_equal_terms_is_zero() {
        assert_eq!(edit_distance("borrow", "borrow"), 0);
        assert_eq!(edit_distance("", ""), 0);
    }

    #[test]
    fn the_distance_counts_each_kind_of_edit() {
        assert_eq!(edit_distance("fox", "foxes"), 2); // two insertions
        assert_eq!(edit_distance("foxes", "fox"), 2); // two deletions
        assert_eq!(edit_distance("fox", "box"), 1); // one substitution
    }

    #[test]
    fn the_classic_examples_come_out_right() {
        assert_eq!(edit_distance("kitten", "sitting"), 3);
        assert_eq!(edit_distance("saturday", "sunday"), 3);
        assert_eq!(edit_distance("flaw", "lawn"), 2);
    }

    /// A transposition is two edits here — two substitutions — because
    /// the DP knows three operations, not four. Lucene's default
    /// counts it as one, and that is a known difference.
    #[test]
    fn a_transposition_costs_two_edits() {
        assert_eq!(edit_distance("teh", "the"), 2);
    }

    #[test]
    fn the_distance_is_counted_over_characters_not_bytes() {
        // One substitution each, though both are two bytes in UTF-8.
        assert_eq!(edit_distance("arger", "ärger"), 1);
        assert_eq!(edit_distance("strase", "straße"), 1);
    }

    #[test]
    fn an_empty_term_is_all_insertions() {
        assert_eq!(edit_distance("", "abc"), 3);
        assert_eq!(edit_distance("abc", ""), 3);
    }

    #[test]
    fn a_candidate_too_different_in_length_is_out_without_a_table() {
        // The length check: "ownership" is four edits from "owner",
        // so it is out at any radius below four.
        assert_eq!(edit_distance_within("owner", "ownership", 3), None);
        assert_eq!(edit_distance_within("owner", "ownership", 4), Some(4));
    }

    #[test]
    fn the_radius_caps_the_distance() {
        assert_eq!(edit_distance_within("kitten", "sitting", 2), None);
        assert_eq!(edit_distance_within("kitten", "sitting", 3), Some(3));
    }

    #[test]
    fn fuzzy_finds_the_term_a_typo_was_aiming_at() {
        let mut index = Index::new();
        for (path, text) in &corpus() {
            index.add_document(path, text);
        }
        assert_eq!(index.fuzzy("borow", 1), [("borrow", 1)]);
    }

    /// One typo can reach several terms: "valu" is one edit from
    /// "value" and two from both "call" (v->c, u->l) and "valid".
    /// That is a radius of two doing what it says — it is wide.
    #[test]
    fn one_typo_can_reach_several_terms() {
        let mut index = Index::new();
        for (path, text) in &corpus() {
            index.add_document(path, text);
        }
        assert_eq!(
            index.fuzzy("valu", 2),
            [("value", 1), ("call", 2), ("valid", 2)]
        );
    }

    #[test]
    fn fuzzy_lists_the_exact_term_at_distance_zero() {
        let mut index = Index::new();
        for (path, text) in &corpus() {
            index.add_document(path, text);
        }
        assert_eq!(index.fuzzy("borrow", 1).first(), Some(&("borrow", 0)));
    }

    #[test]
    fn fuzzy_returns_nothing_when_no_term_is_close() {
        let mut index = Index::new();
        for (path, text) in &corpus() {
            index.add_document(path, text);
        }
        assert!(index.fuzzy("zzzzz", 2).is_empty());
    }

    #[test]
    fn fuzzy_hits_are_ordered_by_distance_then_term() {
        let mut index = Index::new();
        index.add_document("a.md", "fox fog dog");
        // "fx" is one edit from "fox" and two from "fog"; "dog" is
        // three away and out at a radius of two.
        assert_eq!(index.fuzzy("fx", 2), [("fox", 1), ("fog", 2)]);
    }

    #[test]
    fn a_fuzzy_query_scores_by_every_variant_it_matched() {
        let mut index = Index::new();
        index.add_document("a.md", "fox");
        index.add_document("b.md", "fog");
        index.add_document("c.md", "fox fog");
        // "fx~2" matches fox and fog, and the document holding both
        // scores by both — the way an OR's does.
        let ranked = index.query("fx~2").unwrap();
        assert_eq!(ranked[0].0, 2);
        let fox = index.query("fox").unwrap();
        let fog = index.query("fog").unwrap();
        let both = ranked.iter().find(|(doc, _)| *doc == 2).unwrap().1;
        let fox_score = fox.iter().find(|(doc, _)| *doc == 2).unwrap().1;
        let fog_score = fog.iter().find(|(doc, _)| *doc == 2).unwrap().1;
        assert!((both - (fox_score + fog_score)).abs() < 1e-12);
    }

    #[test]
    fn a_typo_query_answers_what_the_correct_spelling_answers() {
        let mut index = Index::new();
        for (path, text) in &corpus() {
            index.add_document(path, text);
        }
        assert_eq!(
            index.query("borow~").unwrap(),
            index.query("borrow").unwrap()
        );
        assert_eq!(
            index.boolean("ower~1").unwrap(),
            index.boolean("owner").unwrap()
        );
    }

    #[test]
    fn a_bare_tilde_means_the_default_radius() {
        let mut index = Index::new();
        index.add_document("a.md", "fox fog");
        assert_eq!(
            index.boolean("fx~").unwrap(),
            index.boolean("fx~2").unwrap()
        );
    }

    #[test]
    fn a_radius_of_zero_is_an_exact_match() {
        let mut index = Index::new();
        index.add_document("a.md", "fox");
        assert_eq!(index.boolean("fox~0").unwrap(), [0]);
        assert!(index.boolean("fx~0").unwrap().is_empty());
    }

    #[test]
    fn a_stop_word_with_a_tilde_matches_nothing() {
        let index = three_docs();
        assert!(index.boolean("the~").unwrap().is_empty());
    }

    /// The fuzzy word goes through the tokeniser before the scan, so
    /// casing and punctuation fold away exactly as they do for an
    /// exact term.
    #[test]
    fn an_uppercase_fuzzy_word_is_lowercased() {
        let mut index = Index::new();
        index.add_document("a.md", "fox");
        assert_eq!(index.boolean("FOx~1").unwrap(), [0]);
    }

    /// The tilde covers one word. A word that normalises to two terms
    /// is a phrase, and this operator does not do phrases.
    #[test]
    fn a_hyphenated_word_with_a_tilde_matches_nothing() {
        let mut index = Index::new();
        index.add_document("a.md", "borrow checker");
        assert!(index.boolean("borrow-checker~").unwrap().is_empty());
    }

    #[test]
    fn not_applies_to_a_fuzzy_operand() {
        let mut index = Index::new();
        index.add_document("a.md", "fox");
        index.add_document("b.md", "fox dog");
        index.add_document("c.md", "dog");
        // "fox~1" matches a and b; NOT dog leaves a.
        assert_eq!(index.boolean("fox~1 NOT dog").unwrap(), [0]);
    }

    #[test]
    fn a_radius_past_the_cap_is_refused() {
        let index = three_docs();
        assert!(index.query("fox~3").is_err());
    }

    #[test]
    fn a_tilde_with_no_radius_after_it_is_refused() {
        let index = three_docs();
        assert!(index.query("fox~x").is_err());
        assert!(index.query("fox~-1").is_err());
        assert!(index.query("fox~1~2").is_err());
    }

    #[test]
    fn the_refusal_names_the_token() {
        let index = three_docs();
        assert_eq!(
            index.query("fox~3").unwrap_err().to_string(),
            "the fuzzy operator on \"fox~3\" needs an edit count between 0 and 2"
        );
    }

    /// A scratch path in the OS temp directory. Each test picks its own
    /// name, so the tests can run in parallel.
    fn scratch(name: &str) -> std::path::PathBuf {
        std::env::temp_dir().join(format!("haystack-{name}.idx"))
    }

    #[test]
    fn a_saved_index_loads_back_identical() {
        let index = sample();
        let path = scratch("roundtrip");
        index.save(&path).unwrap();
        let loaded = Index::load(&path).unwrap();
        assert_eq!(loaded.documents(), index.documents());
        assert_eq!(loaded.terms(), index.terms());
        for (term, postings) in index.postings() {
            assert_eq!(loaded.search(term), postings, "postings for {term:?}");
        }
        for id in 0..index.documents() as u32 {
            assert_eq!(loaded.path(id), index.path(id));
            assert_eq!(loaded.length(id), index.length(id));
        }
    }

    #[test]
    fn a_terms_positions_survive_a_reload() {
        let mut index = Index::new();
        index.add_document("a.md", "fox fox fox");
        index.add_document("b.md", "fox");
        let path = scratch("positions");
        index.save(&path).unwrap();
        let loaded = Index::load(&path).unwrap();
        assert_eq!(
            loaded.search("fox"),
            &[
                Posting {
                    doc: 0,
                    positions: vec![0, 1, 2],
                },
                Posting {
                    doc: 1,
                    positions: vec![0],
                },
            ]
        );
        // A document that does not hold the term has no positions.
        assert!(loaded.positions("fox", 2).is_empty());
    }

    #[test]
    fn saving_twice_writes_the_same_bytes() {
        let index = sample();
        let path = scratch("determinism");
        index.save(&path).unwrap();
        let first = fs::read(&path).unwrap();
        index.save(&path).unwrap();
        assert_eq!(fs::read(&path).unwrap(), first);
    }

    #[test]
    fn the_dictionary_is_written_in_sorted_order() {
        let index = sample();
        let path = scratch("sorted");
        index.save(&path).unwrap();
        let bytes = fs::read(&path).unwrap();

        // Walk the saved file the way the loader does, collecting the
        // terms as they appear on disk.
        let mut reader = Reader::new(&bytes);
        reader.take(MAGIC.len()).unwrap();
        reader.u32().unwrap();
        for _ in 0..reader.u32().unwrap() {
            reader.string().unwrap();
            reader.u32().unwrap(); // the document's length
        }
        let mut terms = Vec::new();
        for _ in 0..reader.u32().unwrap() {
            let term = reader.string().unwrap();
            for _ in 0..reader.u32().unwrap() {
                reader.u32().unwrap(); // the document
                let count = reader.u32().unwrap(); // how many positions
                reader.take(count as usize * 4).unwrap(); // the positions
            }
            terms.push(term);
        }
        assert!(
            terms.windows(2).all(|pair| pair[0] < pair[1]),
            "not sorted: {terms:?}"
        );
    }

    #[test]
    fn a_truncated_file_is_refused() {
        let index = sample();
        let path = scratch("truncated");
        index.save(&path).unwrap();
        let bytes = fs::read(&path).unwrap();
        let error = Index::load_bytes(&bytes[..20]).unwrap_err();
        assert_eq!(
            error.to_string(),
            "the file ends where another field was expected"
        );
    }

    #[test]
    fn a_wrong_magic_is_refused() {
        let mut bytes = Vec::new();
        bytes.extend_from_slice(b"haystacs"); // one letter off
        bytes.extend_from_slice(&VERSION.to_le_bytes());
        let error = Index::load_bytes(&bytes).unwrap_err();
        assert_eq!(
            error.to_string(),
            "not a haystack index: the magic bytes are wrong"
        );
    }

    #[test]
    fn a_newer_version_is_refused() {
        let mut bytes = Vec::new();
        bytes.extend_from_slice(MAGIC);
        bytes.extend_from_slice(&4u32.to_le_bytes());
        let error = Index::load_bytes(&bytes).unwrap_err();
        assert_eq!(error.to_string(), "unsupported index version 4");
    }

    #[test]
    fn a_version_1_file_is_refused() {
        let mut bytes = Vec::new();
        bytes.extend_from_slice(MAGIC);
        bytes.extend_from_slice(&1u32.to_le_bytes());
        let error = Index::load_bytes(&bytes).unwrap_err();
        assert_eq!(error.to_string(), "unsupported index version 1");
    }

    /// The format this step replaced. A version 2 file has term
    /// frequencies where the positions are now, and this build does
    /// not read it.
    #[test]
    fn a_version_2_file_is_refused() {
        let mut bytes = Vec::new();
        bytes.extend_from_slice(MAGIC);
        bytes.extend_from_slice(&2u32.to_le_bytes());
        let error = Index::load_bytes(&bytes).unwrap_err();
        assert_eq!(error.to_string(), "unsupported index version 2");
    }

    #[test]
    fn a_postings_list_that_is_not_ascending_is_refused() {
        let mut bytes = Vec::new();
        bytes.extend_from_slice(MAGIC);
        bytes.extend_from_slice(&VERSION.to_le_bytes());
        bytes.extend_from_slice(&0u32.to_le_bytes()); // no documents
        bytes.extend_from_slice(&1u32.to_le_bytes()); // one term
        bytes.extend_from_slice(&1u32.to_le_bytes()); // one byte long
        bytes.push(b'x');
        bytes.extend_from_slice(&2u32.to_le_bytes()); // two postings
        bytes.extend_from_slice(&2u32.to_le_bytes()); // document 2
        bytes.extend_from_slice(&1u32.to_le_bytes()); // one position
        bytes.extend_from_slice(&0u32.to_le_bytes()); // position 0
        bytes.extend_from_slice(&1u32.to_le_bytes()); // document 1 — out of order
        bytes.extend_from_slice(&1u32.to_le_bytes()); // one position
        bytes.extend_from_slice(&0u32.to_le_bytes()); // position 0
        let error = Index::load_bytes(&bytes).unwrap_err();
        assert_eq!(
            error.to_string(),
            "the postings list for \"x\" is not in ascending document order"
        );
    }

    #[test]
    fn trailing_bytes_are_refused() {
        let index = sample();
        let path = scratch("trailing");
        index.save(&path).unwrap();
        let mut bytes = fs::read(&path).unwrap();
        bytes.push(0);
        let error = Index::load_bytes(&bytes).unwrap_err();
        assert_eq!(error.to_string(), "the file has bytes after the last field");
    }

    #[test]
    fn a_term_that_is_not_utf8_is_refused() {
        let mut bytes = Vec::new();
        bytes.extend_from_slice(MAGIC);
        bytes.extend_from_slice(&VERSION.to_le_bytes());
        bytes.extend_from_slice(&0u32.to_le_bytes()); // no documents
        bytes.extend_from_slice(&1u32.to_le_bytes()); // one term
        bytes.extend_from_slice(&1u32.to_le_bytes()); // one byte long
        bytes.push(0xFF); // and not UTF-8
        let error = Index::load_bytes(&bytes).unwrap_err();
        assert_eq!(
            error.to_string(),
            "a length-prefixed field is not valid UTF-8"
        );
    }

    #[test]
    fn a_missing_file_is_an_io_error() {
        let path = scratch("never-written");
        assert!(matches!(Index::load(&path), Err(LoadError::Io(_))));
    }

    #[test]
    fn an_empty_index_round_trips() {
        let index = Index::new();
        let path = scratch("empty");
        index.save(&path).unwrap();
        let loaded = Index::load(&path).unwrap();
        assert_eq!(loaded.documents(), 0);
        assert_eq!(loaded.terms(), 0);
    }
}

▶Run this in the Rust Playground

Eighty-eight tests: the sixty-four from step 7, and twenty-four around the new machinery — the distance on known pairs, the transposition gap, the character counting, the radius cap and its refusals, the normalisation of the fuzzy word, and what a fuzzy query scores. The order is shuffled on every run, so nothing should be read into it:

test result: ok. 88 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.01s

Where this lands

This step’s state is tagged search-ch08 in the examples repository:

git clone https://github.com/hackingwithrust/examples
cd examples/search-engine
git checkout search-ch08

The tag contains Cargo.toml, the README and src/main.rs in full. If your build misbehaves, diff your files against the tag’s — the drifting line is usually findable that way. cargo run prints the whole demo, and cargo test runs the eighty-eight tests. The track overview keeps the step list current.

Next

Step 9, An HTTP query API, serves these same queries over HTTP, and it is the first step that reaches for a crate outside the standard library.