Skip to main content

docs_search/
index.rs

1//! Builder, reader, and query half of the index.
2
3use std::collections::BTreeMap;
4
5use fst::{MapBuilder, Streamer};
6use roaring::RoaringBitmap;
7
8use crate::error::IndexError;
9use crate::format::{check_header, push_u32, push_u64, Reader, MAGIC, VERSION};
10
11/// Run one dictionary operation with an unwind boundary.
12///
13/// fst 0.4.7 panics internally on hostile dictionaries (raw/node.rs
14/// out-of-bounds and subtraction overflow; found by the corruption property
15/// test). The estate decoder pattern requires this crate to be total on
16/// untrusted input, so every fst entry point is guarded and an unwind
17/// surfaces as a typed error. Panic = unwind in this crate's profiles;
18/// do not introduce `panic = "abort"`.
19fn fst_guard<T, E>(op: impl FnOnce() -> Result<T, E>) -> Result<T, IndexError>
20where
21    E: std::error::Error + 'static,
22    IndexError: From<E>,
23{
24    std::panic::catch_unwind(std::panic::AssertUnwindSafe(op))
25        .map_err(|_| IndexError::Corrupt {
26            reason: "term dictionary rejected hostile input",
27        })?
28        .map_err(IndexError::from)
29}
30
31/// BM25 k1 saturation parameter; ranking is documented as unit-tf (0.1 scope).
32const K1: f64 = 1.2;
33/// BM25 length-normalization parameter.
34const B: f64 = 0.75;
35
36/// Split text into index terms: lowercase, contiguous alphanumeric runs.
37/// Owned terms, so builders and queries can hold them freely.
38fn terms(text: &str) -> impl Iterator<Item = String> + '_ {
39    text.split(|c: char| !c.is_alphanumeric())
40        .filter(|t| !t.is_empty())
41        .map(|t| t.to_lowercase())
42}
43
44/// Collects documents into a deterministic, serialized index.
45///
46/// Document ids are assigned in insertion order; serialization is
47/// byte-for-byte reproducible for the same input (BTreeMap postings,
48/// stable counter order).
49#[derive(Debug, Default)]
50pub struct IndexBuilder {
51    postings: BTreeMap<String, RoaringBitmap>,
52    doc_lens: Vec<u64>,
53}
54
55impl IndexBuilder {
56    /// A fresh builder.
57    pub fn new() -> Self {
58        Self::default()
59    }
60
61    /// Add one document; its id is the insertion ordinal.
62    pub fn add_doc(&mut self, text: &str) {
63        let doc = self.doc_lens.len() as u64;
64        let mut len = 0u64;
65        for term in terms(text) {
66            len += term.len() as u64;
67            self.postings.entry(term).or_default().insert(doc as u32);
68        }
69        self.doc_lens.push(len);
70    }
71
72    /// Serialize the index to its binary format.
73    ///
74    /// The only failure modes are serialization-layer bugs (an FST key
75    /// ordering violation or a bitmap encode error); they surface as typed
76    /// errors, never panics.
77    pub fn build(&self) -> Result<Vec<u8>, IndexError> {
78        let mut out = Vec::new();
79        out.extend_from_slice(&MAGIC);
80        push_u32(&mut out, VERSION);
81        push_u64(&mut out, self.doc_lens.len() as u64);
82
83        // Postings blob first so the FST offsets are known before the
84        // dictionary is serialized.
85        let mut postings = Vec::new();
86        let mut entries: Vec<(&str, u64)> = Vec::with_capacity(self.postings.len());
87        for (term, bitmap) in &self.postings {
88            let size =
89                u32::try_from(bitmap.serialized_size()).map_err(|_| IndexError::Corrupt {
90                    reason: "bitmap exceeds u32 length",
91                })?;
92            entries.push((term, postings.len() as u64));
93            push_u32(&mut postings, size);
94            bitmap
95                .serialize_into(&mut postings)
96                .map_err(|_| IndexError::Corrupt {
97                    reason: "bitmap serialization failed",
98                })?;
99        }
100
101        let mut wtr = MapBuilder::new(Vec::new()).map_err(|_| IndexError::Corrupt {
102            reason: "fst builder init failed",
103        })?;
104        for (term, offset) in entries {
105            // Builder insert only fails on out-of-order keys; BTreeMap
106            // iteration is byte-sorted, which is the order FST requires.
107            wtr.insert(term.as_bytes(), offset)
108                .map_err(|_| IndexError::Corrupt {
109                    reason: "fst key ordering",
110                })?;
111        }
112        let fst_bytes = wtr.into_inner().map_err(|_| IndexError::Corrupt {
113            reason: "fst finalize failed",
114        })?;
115
116        push_u64(&mut out, fst_bytes.len() as u64);
117        for len in &self.doc_lens {
118            push_u64(&mut out, *len);
119        }
120        out.extend_from_slice(&fst_bytes);
121        out.extend_from_slice(&postings);
122        Ok(out)
123    }
124}
125
126/// One scored query result.
127#[derive(Debug, Clone, PartialEq)]
128pub struct Hit {
129    /// Document id (insertion ordinal).
130    pub doc: u32,
131    /// BM25-shaped relevance score; higher is better.
132    pub score: f64,
133}
134
135/// A loaded search index: queryable, wasm-clean, fully read-only.
136#[derive(Debug)]
137pub struct Index {
138    fst_map: fst::Map<Vec<u8>>,
139    postings: Vec<u8>,
140    doc_lens: Vec<u64>,
141}
142
143impl Index {
144    /// Decode an index blob. Total: malformed input yields a typed error,
145    /// never a panic (the index is untrusted input, per the estate decoder
146    /// pattern).
147    pub fn from_bytes(bytes: &[u8]) -> Result<Self, IndexError> {
148        check_header(bytes)?;
149        let mut r = Reader::new(bytes);
150        r.skip(10)?; // magic + version, already validated
151        let doc_count = r.u64()?;
152        let fst_len = r.u64()?;
153
154        // A doc table entry costs at least 8 bytes; a larger count than the
155        // remaining bytes can express is truncation, not an allocation bomb.
156        if doc_count > r.rest().len() as u64 / 8 {
157            return Err(IndexError::Truncated {
158                section: "doc table",
159            });
160        }
161        let doc_lens = read_doc_lens(&mut r, doc_count)?;
162
163        let fst_start = r.pos();
164        let fst_end = fst_start
165            .checked_add(usize::try_from(fst_len).map_err(|_| IndexError::Corrupt {
166                reason: "fst length exceeds address space",
167            })?)
168            .ok_or(IndexError::Corrupt {
169                reason: "fst section overflows",
170            })?;
171        let fst_bytes = bytes.get(fst_start..fst_end).ok_or(IndexError::Truncated {
172            section: "fst dictionary",
173        })?;
174        let postings = bytes.get(fst_end..).ok_or(IndexError::Truncated {
175            section: "postings",
176        })?;
177
178        let fst_map = fst_guard(|| fst::Map::new(fst_bytes.to_vec()))?;
179        validate_postings(postings)?;
180        // Cross-section coherence: every dictionary offset must resolve to
181        // a bitmap inside the postings area, so a decoded index can never
182        // produce a silent empty query from an unresolvable term. Streaming
183        // the whole dictionary here also exercises every node, which is
184        // what makes query-time reads panic-free in practice.
185        fst_guard(|| {
186            let mut terms = fst_map.stream();
187            while let Some((_, offset)) = terms.next() {
188                read_bitmap_at(postings, offset as usize)?;
189            }
190            Ok::<(), IndexError>(())
191        })?;
192        Ok(Self {
193            fst_map,
194            postings: postings.to_vec(),
195            doc_lens,
196        })
197    }
198
199    /// Number of documents.
200    pub fn len(&self) -> u64 {
201        self.doc_lens.len() as u64
202    }
203
204    /// Whether there are no documents.
205    pub fn is_empty(&self) -> bool {
206        self.doc_lens.is_empty()
207    }
208
209    /// AND-query the index, ranked by BM25-shaped score (unit term
210    /// frequency), best first, at most `limit` hits.
211    ///
212    /// A query term missing from the dictionary yields no hits (AND
213    /// semantics). Corrupt postings for a queried term also yield no hits:
214    /// query is a read path and reports emptiness rather than erroring.
215    pub fn query(&self, query: &str, limit: usize) -> Vec<Hit> {
216        let query_terms: Vec<String> = terms(query).collect();
217        if query_terms.is_empty() {
218            return Vec::new();
219        }
220
221        let mut matched: Vec<RoaringBitmap> = Vec::new();
222        for term in &query_terms {
223            match self.postings_for(term) {
224                Ok(Some(bm)) => matched.push(bm),
225                Ok(None) | Err(_) => return Vec::new(),
226            }
227        }
228        let Some(first) = matched.first() else {
229            return Vec::new();
230        };
231        let mut docs = first.clone();
232        for bm in &matched {
233            docs &= bm;
234        }
235
236        let n = self.len();
237        let avgdl = average(&self.doc_lens);
238        let mut hits: Vec<Hit> = Vec::new();
239        for doc in docs {
240            let Some(dl) = self.doc_lens.get(doc as usize) else {
241                continue;
242            };
243            let mut score = 0.0;
244            for term in &query_terms {
245                if let Ok(Some(bm)) = self.postings_for(term) {
246                    if bm.contains(doc) {
247                        let idf = idf(n, bm.len());
248                        score += idf * norm(*dl, avgdl);
249                    }
250                }
251            }
252            hits.push(Hit { doc, score });
253        }
254        hits.sort_by(|a, b| b.score.total_cmp(&a.score).then(a.doc.cmp(&b.doc)));
255        hits.truncate(limit);
256        hits
257    }
258
259    fn postings_for(&self, term: &str) -> Result<Option<RoaringBitmap>, IndexError> {
260        // The dictionary was fully streamed at decode, so reads cannot
261        // panic on a decoded index; the guard is defense-in-depth so the
262        // query path stays total regardless.
263        let lookup = std::panic::catch_unwind(|| self.fst_map.get(term.as_bytes()));
264        let offset = match lookup {
265            Ok(Some(offset)) => offset,
266            Ok(None) => return Ok(None),
267            Err(_) => {
268                return Err(IndexError::Corrupt {
269                    reason: "term dictionary rejected hostile input",
270                })
271            }
272        };
273        read_bitmap_at(&self.postings, offset as usize).map(Some)
274    }
275}
276
277/// Bounds-checked bitmap read at `start`: `u32` length prefix + roaring
278/// bytes. Shared by decode-time validation and query-time lookups.
279fn read_bitmap_at(postings: &[u8], start: usize) -> Result<RoaringBitmap, IndexError> {
280    let len_pos = start.checked_add(4).ok_or(IndexError::Corrupt {
281        reason: "postings offset overflows",
282    })?;
283    let len_bytes = postings.get(start..len_pos).ok_or(IndexError::Corrupt {
284        reason: "postings offset out of range",
285    })?;
286    let mut raw = [0u8; 4];
287    raw.copy_from_slice(len_bytes);
288    let len = usize::try_from(u32::from_le_bytes(raw)).map_err(|_| IndexError::Corrupt {
289        reason: "bitmap length exceeds address space",
290    })?;
291    let end = len_pos.checked_add(len).ok_or(IndexError::Corrupt {
292        reason: "bitmap length overflows",
293    })?;
294    let bytes = postings.get(len_pos..end).ok_or(IndexError::Corrupt {
295        reason: "bitmap bytes out of range",
296    })?;
297    RoaringBitmap::deserialize_from(bytes).map_err(|_| IndexError::Corrupt {
298        reason: "bitmap deserialization",
299    })
300}
301
302/// Walk the entire postings area: every entry's length must fit and every
303/// bitmap must deserialize, and the entries must exactly cover the area
304/// (no trailing garbage, no silently-empty truncation). Decode-time
305/// validation means a decoded index can always answer queries; corruption
306/// is never deferred to a silent empty result later.
307fn validate_postings(postings: &[u8]) -> Result<(), IndexError> {
308    let mut pos = 0usize;
309    while pos < postings.len() {
310        let len_pos = pos.checked_add(4).ok_or(IndexError::Corrupt {
311            reason: "postings offset overflows",
312        })?;
313        let len_bytes = postings.get(pos..len_pos).ok_or(IndexError::Corrupt {
314            reason: "truncated bitmap length",
315        })?;
316        let mut raw = [0u8; 4];
317        raw.copy_from_slice(len_bytes);
318        let len = usize::try_from(u32::from_le_bytes(raw)).map_err(|_| IndexError::Corrupt {
319            reason: "bitmap length exceeds address space",
320        })?;
321        let end = len_pos.checked_add(len).ok_or(IndexError::Corrupt {
322            reason: "bitmap length overflows",
323        })?;
324        if end > postings.len() {
325            return Err(IndexError::Corrupt {
326                reason: "bitmap bytes out of range",
327            });
328        }
329        let _ = read_bitmap_at(postings, pos)?;
330        pos = end;
331    }
332    if pos != postings.len() {
333        return Err(IndexError::Corrupt {
334            reason: "postings not fully consumed",
335        });
336    }
337    Ok(())
338}
339
340fn read_doc_lens(r: &mut Reader<'_>, doc_count: u64) -> Result<Vec<u64>, IndexError> {
341    let mut lens = Vec::new();
342    for _ in 0..doc_count {
343        lens.push(r.u64()?);
344    }
345    Ok(lens)
346}
347
348fn average(doc_lens: &[u64]) -> f64 {
349    if doc_lens.is_empty() {
350        return 1.0;
351    }
352    let total: u64 = doc_lens.iter().sum();
353    if total == 0 {
354        1.0
355    } else {
356        total as f64 / doc_lens.len() as f64
357    }
358}
359
360fn idf(n_docs: u64, n_matching: u64) -> f64 {
361    let n = n_docs as f64;
362    let matching = n_matching as f64;
363    (1.0 + (n - matching + 0.5) / (matching + 0.5)).ln()
364}
365
366/// Length normalization: `(k1 + 1) / (tf + k1 * (1 - b + b * dl / avgdl))`
367/// with unit term frequency (tf = 1), per the 0.1 scope note.
368fn norm(dl: u64, avgdl: f64) -> f64 {
369    let dl = dl as f64;
370    (K1 + 1.0) / (1.0 + K1 * (1.0 - B + B * dl / avgdl))
371}