Phrase and boolean queries
Step 7 of 12, and the index starts remembering where words sit. Step 6 left
haystack with a BM25 ranker that answers one term at a time and has no way to
ask about two together. This step gives every posting the positions of its
occurrences, moves the index file to version 3, and builds two kinds of query on
top: phrases, which ask for words next to each other in order, and boolean
queries with AND, OR and NOT.
The starting state is tag search-ch06, the end of
step 6: postings that carry term
frequencies, documents that carry lengths, and a scorer that uses both. The end
state of this step is tagged search-ch07. The corpus, the tokeniser and the
scorer are untouched — the single-term ranking in the demo below prints the same
scores step 6 did. What changes is what a posting holds, and what can be asked
of it.
Where each word sat
Section titled “Where each word sat”A position is the index of a term in the sequence the tokeniser produced for a document. That sequence is what survives step 3: lowercased, split on anything that is not a letter or a digit, stop words dropped, inflections stemmed. A document’s length is the size of the sequence, and a term’s positions are the slots it occupies in it.
Take docs/borrow-checker.md. Its first sentence, “The borrow checker enforces
the borrowing rules at compile time”, contributes seven terms — “the” is a stop
word, so “borrow” is the first term the index sees and sits at position 0, with
“checker” at 1. The second sentence adds five more, two of them “borrow”, at 7
and 10. Nothing of the original text survives: casing, punctuation and the stop
words are gone before the first position is counted.
Positions fall out of the run counting step 2 already did. Each term is tagged with its index before the sort, the sort groups one term’s occurrences together, and each run becomes a posting carrying its positions. The term frequency step 5 added is the length of that list — which is why a posting does not carry a frequency any more.
The block below is the engine’s indexing path with the tokeniser replaced by
terms that are already normalised, so the positions are the only machinery on
screen. Document 0 is docs/borrow-checker.md in full, document 1 is
docs/ownership.md:
use std::collections::HashMap;
/// One posting: the document, and where each occurrence of the term/// sits in it.#[derive(Debug, PartialEq)]struct Posting { doc: u32, positions: Vec<u32>,}
/// A tiny inverted index that takes its terms already normalised —/// lowercased, stop words dropped, stemmed.struct Index { postings: HashMap<String, Vec<Posting>>,}
impl Index { fn new() -> Self { Index { postings: HashMap::new(), } }
/// Index one document. A term's position is its index in the /// sequence the tokeniser produced. fn add(&mut self, doc: u32, terms: &[&str]) { // Tag each term with its position before sorting: the sort is // about the dictionary, the positions are about the document. let mut tagged: Vec<(u32, &str)> = terms .iter() .enumerate() .map(|(position, term)| (position as u32, *term)) .collect(); tagged.sort_unstable_by(|a, b| a.1.cmp(b.1).then_with(|| a.0.cmp(&b.0))); // Each run of equal terms becomes one posting, and the run's // positions come out ascending. for (term, positions) in runs(&tagged) { self.postings .entry(term.to_string()) .or_default() .push(Posting { doc, positions }); } }
/// The positions of `term` in `doc`. fn positions(&self, term: &str, doc: u32) -> &[u32] { self.postings .get(term) .and_then(|list| list.iter().find(|p| p.doc == doc)) .map_or(&[], |p| &p.positions) }}
/// Group a tagged, sorted term list into runs: each distinct term/// once, with its positions.fn runs<'a>(tagged: &[(u32, &'a str)]) -> Vec<(&'a str, Vec<u32>)> { let mut out = Vec::new(); let mut start = 0; while start < tagged.len() { let mut end = start + 1; while end < tagged.len() && tagged[end].1 == tagged[start].1 { end += 1; } let positions = tagged[start..end].iter().map(|(p, _)| *p).collect(); out.push((tagged[start].1, positions)); start = end; } out}
fn main() { let mut index = Index::new(); index.add( 0, &[ "borrow", "checker", "enforc", "borrow", "rule", "compil", "time", "borrow", "outlive", "owner", "borrow", "value", ], ); index.add( 1, &[ "ownership", "borrow", "two", "idea", "rust", "built", "every", "value", "one", "owner", "owner", "going", "out", "scope", "drop", ], ); for term in ["borrow", "checker", "value", "owner"] { for doc in 0..2 { println!("{term:<8} doc {doc}: {:?}", index.positions(term, doc)); } }}Run this in the Rust Playground
borrow doc 0: [0, 3, 7, 10]borrow doc 1: [1]checker doc 0: [1]checker doc 1: []value doc 0: [11]value doc 1: [7]owner doc 0: [9]owner doc 1: [9, 10]The file goes to version 3
Section titled “The file goes to version 3”A posting is now two fields where it was three:
/// 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>,}Version 2 wrote a document id and a term frequency in eight bytes per posting. Version 3 writes the document id, a position count and the positions themselves. The frequency is gone as a field: it was always the number of positions, and a file that carried both could disagree with itself. On disk one posting is now the id, the count, and four bytes per position.
The corpus grows from 2131 bytes to 2619: four bytes for each of the 122 term occurrences across the 103 postings. The count per posting costs nothing new, because it sits where the frequency used to. A version 2 file is refused like every other version this build does not write, and the demo says so:
a version 2 file: unsupported index version 2Phrase queries
Section titled “Phrase queries”With positions in the index, “borrow checker” becomes a different question from “borrow” and “checker” anywhere in the text. The algorithm is short. A document can only match if it holds every term, so the candidates are the first term’s postings. For each candidate, one occurrence of the first term has to be followed by the second one position later, the third two later, and so on.
The block below is that algorithm over the corpus’s real postings — document 0
is docs/borrow-checker.md, document 1 docs/ownership.md:
use std::collections::HashMap;
/// One posting: the document, and where each occurrence sits in it.#[derive(Debug, PartialEq)]struct Posting { doc: u32, positions: Vec<u32>,}
/// The posting for `term` in `doc`, when the document holds it.fn posting<'a>(index: &'a HashMap<String, Vec<Posting>>, term: &str, doc: u32) -> Option<&'a Posting> { index.get(term)?.iter().find(|p| p.doc == doc)}
/// Does the phrase `terms` appear in `doc`? One occurrence of the/// first term has to be followed by the second one position later,/// the third two later, and so on.fn phrase_matches(index: &HashMap<String, Vec<Posting>>, terms: &[&str], doc: u32) -> bool { let Some((first, rest)) = terms.split_first() else { return false; }; let Some(first_posting) = posting(index, first, doc) else { return false; }; first_posting.positions.iter().any(|&start| { rest.iter().enumerate().all(|(offset, term)| { posting(index, term, doc) .is_some_and(|p| p.positions.contains(&(start + 1 + offset as u32))) }) })}
fn main() { let mut index: HashMap<String, Vec<Posting>> = HashMap::new(); index.insert( "borrow".to_string(), vec![ Posting { doc: 0, positions: vec![0, 3, 7, 10], }, Posting { doc: 1, positions: vec![1], }, ], ); index.insert( "checker".to_string(), vec![Posting { doc: 0, positions: vec![1], }], ); index.insert( "value".to_string(), vec![ Posting { doc: 0, positions: vec![11], }, Posting { doc: 1, positions: vec![7], }, ], ); index.insert( "owner".to_string(), vec![ Posting { doc: 0, positions: vec![9], }, Posting { doc: 1, positions: vec![9, 10], }, ], );
for terms in [ ["borrow", "checker"], ["checker", "borrow"], ["value", "owner"], ] { println!( "{terms:?}: doc 0 {}, doc 1 {}", phrase_matches(&index, &terms, 0), phrase_matches(&index, &terms, 1) ); }}Run this in the Rust Playground
["borrow", "checker"]: doc 0 true, doc 1 false["checker", "borrow"]: doc 0 false, doc 1 false["value", "owner"]: doc 0 false, doc 1 falseOn the corpus, “borrow checker” matches two documents: docs/borrow-checker.md,
where the words open the first sentence, and docs/lifetimes.md, which contains
“The borrow checker uses lifetimes”. The phrase is the same question in both.
Reversed — “checker borrow” — it matches nothing anywhere.
AND does not ask where. “value AND owner” finds two documents, because both
words are in both; the phrase “value owner” finds none, because in
docs/ownership.md “value” sits at 7 and the first “owner” at 9, and in
docs/borrow-checker.md the order is the other way round. Co-occurrence
against adjacency is the whole of what positions buy.
One trade-off arrives from step 3 and lands here. Stop words are dropped before positions are counted, so a phrase can match across one: “owner value” finds “the owner of the value”, where the words are three apart in the text. Lucene’s default stop filter behaves the same way, and its documentation says why: with a position increment of one per kept token, “blue is the sky” indexes as blue and sky next to each other, so the phrase “blue sky” finds it. Leaving a gap for each removed stop word is possible there and is not done here, which means a phrase containing a stop word is asking a question this index cannot answer precisely.
The mistake this step invites is the offset. enumerate hands back a usize
and the positions are u32, so the offset needs a cast:
fn main() { let positions = vec![0u32, 3, 7]; let offset = 1usize; let start = 0u32; // The offset from enumerate() is a usize; the positions are u32. println!("{}", positions.contains(&(start + 1 + offset)));}Run this in the Rust Playground
error[E0308]: mismatched types --> src/main.rs:6:53 |6 | println!("{}", positions.contains(&(start + 1 + offset))); | ^^^^^^ expected `u32`, found `usize`
error[E0277]: cannot add `usize` to `u32` --> src/main.rs:6:51 | 6 | println!("{}", positions.contains(&(start + 1 + offset))); | ^ no implementation for `u32 + usize` | = help: the trait `Add<usize>` is not implemented for `u32`help: the following other types implement trait `Add<Rhs>` --> /Users/rango/.rustup/toolchains/1.99.0-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/ops/arith.rs:98:9 | 98 | const impl Add for $t { | ^^^^^^^^^^^^^^^^^^^^^ `u32` implements `Add`...113 | add_impl! { usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 f16 f32 f64 f128 } | ---------------------------------------------------------------------------------- in this macro invocation | ::: /Users/rango/.rustup/toolchains/1.99.0-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/internal_macros.rs:22:9 | 22 | const impl $imp<$u> for &$t { | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ `&u32` implements `Add<u32>`... 33 | const impl $imp<&$u> for $t { | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ `u32` implements `Add<&u32>`... 44 | const impl $imp<&$u> for &$t { | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ `&u32` implements `Add` = note: this error originates in the macro `add_impl` (in Nightly builds, run with -Z macro-backtrace for more info)
Some errors have detailed explanations: E0277, E0308.For more information about an error, try `rustc --explain E0277`.Boolean queries
Section titled “Boolean queries”The query language is small. A query is whitespace-separated 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. Operators evaluate left to right with equal precedence — “fox OR dog AND cat” is “(fox OR dog) AND cat”, 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.
Every operand is normalised by the same tokeniser the index uses. A stop word in a query matches nothing, exactly as it does in a single-term search; a hyphenated word is one word that normalises to two terms, so “borrow-checker” is the phrase they form, which is what the hyphen meant in the text.
The block below is the evaluation loop with the postings replaced by a fixed table, so the set algebra is the only thing on screen. It splits on whitespace; the engine’s tokeniser also keeps quoted phrases together, and it is in the full file at the end of this page:
use std::collections::BTreeSet;
/// 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,}
/// Split a query into its tokens. The engine's version also keeps/// "quoted phrases" together; this one splits on whitespace.fn query_tokens(query: &str) -> Vec<String> { query.split_whitespace().map(str::to_string).collect()}
/// Which documents hold each term. In the engine this is the term's/// postings; here it is a fixed table.fn postings(term: &str) -> BTreeSet<u32> { match term { "fox" => BTreeSet::from([0, 2]), "dog" => BTreeSet::from([1, 2]), "cat" => BTreeSet::from([2]), _ => BTreeSet::new(), }}
/// Every document the collection holds — what NOT subtracts from.fn every_document() -> BTreeSet<u32> { BTreeSet::from([0, 1, 2])}
/// Evaluate a boolean query left to right, with equal precedence./// NOT applies to the operand that follows it.fn evaluate(query: &str) -> Result<BTreeSet<u32>, String> { let mut matched: Option<BTreeSet<u32>> = None; let mut op = Operator::And; let mut negate = false; // Whether the next token has to be an operand. let mut want_operand = true;
for token in query_tokens(query) { match token.as_str() { "AND" | "OR" => { if want_operand { return Err("an operator is missing its operand".to_string()); } op = if token == "AND" { Operator::And } else { Operator::Or }; want_operand = true; } "NOT" => { negate = !negate; want_operand = true; } _ => { let docs = postings(&token); let docs = if negate { negate = false; every_document().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(), }, }); op = Operator::And; want_operand = false; } } } if want_operand { return Err("an operator is missing its operand".to_string()); } Ok(matched.unwrap_or_default())}
fn main() { for query in [ "fox AND dog", "fox OR dog", "fox NOT dog", "fox dog", "fox OR dog AND cat", "fox AND", ] { match evaluate(query) { Ok(docs) => println!("{query:<18} -> {docs:?}"), Err(e) => println!("{query:<18} -> refused: {e}"), } }}Run this in the Rust Playground
fox AND dog -> {2}fox OR dog -> {0, 1, 2}fox NOT dog -> {0}fox dog -> {2}fox OR dog AND cat -> {2}fox AND -> refused: an operator is missing its operandThe last line is the grammar refusing to guess: an operator with nothing on one
side of it is an error, not a query with a missing half. The engine reports it
the same way on the corpus — query "borrow AND" prints “an operator in this
query is missing its operand”.
What a query scores
Section titled “What a query scores”Step 6’s rank stays for the single-term case. A boolean query ranks its
matches by summing one BM25 contribution per positive term — the terms that
selected documents, with NOT’s operands left out. 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.
The sum is pinned by a test: on three documents holding “fox”, “dog” and both,
the document with both scores exactly what each term alone gives it, added
together. In the demo below, “borrow OR value” scores docs/borrow-checker.md
by both terms — 0.3321 for “borrow” plus what “value” adds — which is why it
sits above the documents that hold only one of them.
The whole file
Section titled “The whole file”One file: the positions in the postings, the phrase matcher, the query grammar
and its evaluator, the scorer over several terms, and the tests. The block
below is the file at tag search-ch07, byte for byte.
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 => &[], } }
/// 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) -> (BTreeSet<u32>, Vec<String>) { let text = token .strip_prefix('"') .map(|inside| inside.strip_suffix('"').unwrap_or(inside)) .unwrap_or(token); 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(), }; (docs, terms) }
/// 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,}
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") } } }}
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}
/// 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}"), } }
// 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); }
/// 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
See it run
Section titled “See it run”From the haystack directory:
cargo run6 documents, 84 distinct terms
saved to haystack.idx: 2619 bytessaved again: 2619 bytes, byte-identical: true
loaded back: 6 documents, 84 terms
postings for "borrow" — count, then positions: docs/ownership.md tf=1 positions=[1] docs/borrow-checker.md tf=4 positions=[0, 3, 7, 10] docs/lifetimes.md tf=1 positions=[5] docs/iterators.md tf=1 positions=[10] docs/style-guide.md tf=5 positions=[10, 13, 16, 21, 26]
query "borrow", ranked by BM25: 0.3321 docs/borrow-checker.md tf=4 len=12 0.2564 docs/style-guide.md tf=5 len=57 0.2139 docs/lifetimes.md tf=1 len=13 0.2139 docs/iterators.md tf=1 len=13 0.2042 docs/ownership.md tf=1 len=15
phrase "borrow checker": docs/borrow-checker.md docs/lifetimes.mdphrase "checker borrow" — the other order: no documents
"value AND owner": docs/ownership.md docs/borrow-checker.mdphrase "value owner": no documents
query "borrow AND checker": 1.6520 docs/borrow-checker.md 1.5026 docs/lifetimes.md
query "borrow OR value": 0.8192 docs/borrow-checker.md 0.6584 docs/ownership.md 0.4897 docs/style-guide.md 0.4871 docs/error-handling.md 0.2139 docs/lifetimes.md 0.2139 docs/iterators.md
query "borrow NOT lifetime": 0.3321 docs/borrow-checker.md 0.2564 docs/style-guide.md 0.2139 docs/iterators.md 0.2042 docs/ownership.md
query "borrow AND": an operator in this query is missing its operand
a version 2 file: unsupported index version 2The tests:
cargo testrunning 64 teststest tests::a_newer_version_is_refused ... oktest tests::a_missing_file_is_an_io_error ... oktest tests::a_one_word_phrase_is_that_words_postings ... oktest tests::a_phrase_can_match_across_a_dropped_stop_word ... oktest tests::a_doubled_consonant_from_the_suffix_is_collapsed ... oktest tests::a_missing_term_is_empty_not_an_error ... oktest tests::a_phrase_matches_adjacent_terms_in_order ... oktest tests::a_phrase_across_several_documents ... oktest tests::a_phrase_matches_inside_a_longer_document ... oktest tests::a_hyphenated_word_is_a_phrase_in_disguise ... oktest tests::a_multi_term_query_sums_one_contribution_per_term ... oktest tests::a_phrase_needs_the_terms_next_to_each_other ... oktest tests::a_postings_list_that_is_not_ascending_is_refused ... oktest tests::a_query_that_breaks_the_grammar_is_refused ... oktest tests::a_query_with_no_positive_terms_scores_zero ... oktest tests::a_quoted_phrase_needs_adjacency_but_the_same_words_do_not ... oktest tests::a_repeated_term_records_where_each_copy_sits ... oktest tests::a_frequent_term_in_a_relevant_document_still_wins ... oktest tests::a_stem_needs_three_characters ... oktest tests::a_stop_word_in_a_query_matches_nothing ... oktest tests::a_term_in_two_documents_lists_both ... oktest tests::a_term_repeated_in_one_document_lists_it_once ... oktest tests::a_term_that_is_not_utf8_is_refused ... oktest tests::a_saved_index_loads_back_identical ... oktest tests::a_version_1_file_is_refused ... oktest tests::a_version_2_file_is_refused ... oktest tests::a_terms_positions_survive_a_reload ... oktest tests::a_wrong_magic_is_refused ... oktest tests::a_truncated_file_is_refused ... oktest tests::add_document_returns_the_id_it_gave ... oktest tests::an_empty_index_has_no_average_length ... oktest tests::an_empty_phrase_matches_nothing ... oktest tests::an_empty_query_is_refused ... oktest tests::an_empty_index_round_trips ... oktest tests::and_keeps_the_documents_with_both_terms ... oktest tests::average_length_is_the_mean_of_the_document_lengths ... oktest tests::bm25_puts_the_highest_score_first ... oktest tests::case_folding_is_unicode_aware ... oktest tests::casing_and_punctuation_are_folded_away ... oktest tests::distinct_terms_in_one_document_get_one_posting_each ... oktest tests::document_length_counts_the_terms_the_tokeniser_kept ... oktest tests::double_negation_cancels ... oktest tests::doubling_that_is_not_the_suffixs_fault_survives ... oktest tests::equal_documents_keep_document_order ... oktest tests::idf_falls_as_the_document_frequency_rises ... oktest tests::idf_is_zero_for_a_term_in_every_document ... oktest tests::bm25_lets_the_shorter_document_win ... oktest tests::ids_are_in_insertion_order ... oktest tests::inflections_share_one_term ... oktest tests::k1_of_zero_makes_frequency_irrelevant ... oktest tests::length_normalisation_off_leaves_length_alone ... oktest tests::length_normalisation_on_favours_the_short_document ... oktest tests::not_removes_the_documents_with_the_term ... oktest tests::operators_evaluate_left_to_right ... oktest tests::or_keeps_the_documents_with_either_term ... oktest tests::positions_are_ascending ... oktest tests::positions_skip_the_stop_words_around_them ... oktest tests::stop_words_are_not_indexed ... oktest tests::term_frequency_saturates ... oktest tests::the_term_frequency_is_the_position_count ... oktest tests::the_dictionary_is_written_in_sorted_order ... oktest tests::two_terms_with_no_operator_mean_and ... oktest tests::saving_twice_writes_the_same_bytes ... oktest tests::trailing_bytes_are_refused ... ok
test result: ok. 64 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00sSixty-four tests: the forty from step 6, and twenty-four around the new machinery — positions in order, phrases across documents and across dropped stop words, each operator, the evaluation order, the refusals, and the version 3 round trip. The order is shuffled on every run, so nothing should be read into it.
Where this lands
Section titled “Where this lands”This step’s state is tagged search-ch07 in
the examples repository:
git clone https://github.com/hackingwithrust/examplescd examples/search-enginegit checkout search-ch07The 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. The track overview keeps
the step list current.
Step 8, Fuzzy matching and typo tolerance, searches the dictionary itself by edit distance, so a query with a typo in it finds the term the reader meant.