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};
6
7use crate::error::IndexError;
8use crate::format::{check_header, push_u32, push_u64, Reader, MAGIC, VERSION};
9
10/// Run one dictionary operation with an unwind boundary.
11///
12/// fst 0.4.7 panics internally on hostile dictionaries (raw/node.rs
13/// out-of-bounds and subtraction overflow; found by the corruption property
14/// test). The estate decoder pattern requires this crate to be total on
15/// untrusted input, so every fst entry point is guarded and an unwind
16/// surfaces as a typed error. Panic = unwind in this crate's profiles;
17/// do not introduce `panic = "abort"`.
18fn fst_guard<T, E>(op: impl FnOnce() -> Result<T, E>) -> Result<T, IndexError>
19where
20    E: std::error::Error + 'static,
21    IndexError: From<E>,
22{
23    std::panic::catch_unwind(std::panic::AssertUnwindSafe(op))
24        .map_err(|_| IndexError::Corrupt {
25            reason: "term dictionary rejected hostile input",
26        })?
27        .map_err(IndexError::from)
28}
29
30/// BM25 saturation parameter `k1`.
31const K1: f64 = 1.2;
32/// BM25 length-normalization parameter `b`.
33const B: f64 = 0.75;
34
35/// Split text into index terms: lowercase, contiguous alphanumeric runs.
36/// Owned terms, so builders and queries can hold them freely.
37fn terms(text: &str) -> impl Iterator<Item = String> + '_ {
38    text.split(|c: char| !c.is_alphanumeric())
39        .filter(|t| !t.is_empty())
40        .map(|t| t.to_lowercase())
41}
42
43/// One term's postings: (doc id, term frequency) pairs, doc ids strictly
44/// increasing, tf at least 1. The ordering is an invariant of both the
45/// builder (BTreeMap iteration) and the decoder (validation rejects
46/// anything else), so queries may binary-search.
47type PairList = Vec<(u32, u16)>;
48
49/// A quantized vector: fixed max-abs i8 components with the scale needed
50/// to dequantize, and the L2 norm of the quantized vector for cosine.
51#[cfg(feature = "vectors")]
52#[derive(Debug, Clone)]
53struct QuantVec {
54    /// Per-vector scale: `dim * scale` reconstructs the approximate f32.
55    scale: f32,
56    /// L2 norm of the quantized vector; 0.0 marks the zero vector.
57    norm: f32,
58    /// Quantized components, one per dimension.
59    dims: Vec<i8>,
60}
61
62/// Quantize one f32 vector: max-abs scaling into [-127, 127] i8.
63/// Deterministic by construction (round, clamp, integer-summable norms).
64#[cfg(feature = "vectors")]
65fn quantize(vector: &[f32]) -> QuantVec {
66    let max_abs = vector.iter().fold(0.0f32, |m, v| m.max(v.abs()));
67    let scale = if max_abs > 0.0 { 127.0 / max_abs } else { 0.0 };
68    let dims: Vec<i8> = vector
69        .iter()
70        .map(|v| {
71            let q = (v * scale).round();
72            if q >= 127.0 {
73                127
74            } else if q <= -127.0 {
75                -127
76            } else {
77                q as i8
78            }
79        })
80        .collect();
81    let norm = dims
82        .iter()
83        .map(|q| (*q as f32) * (*q as f32))
84        .sum::<f32>()
85        .sqrt();
86    QuantVec { scale, norm, dims }
87}
88
89/// Collects documents into a deterministic, serialized index.
90///
91/// Document ids are assigned in insertion order; serialization is
92/// byte-for-byte reproducible for the same input (BTreeMap postings,
93/// stable counter order).
94#[derive(Debug, Default)]
95pub struct IndexBuilder {
96    postings: BTreeMap<String, BTreeMap<u32, u16>>,
97    doc_lens: Vec<u64>,
98    /// Doc id -> quantized vector, insertion-time quantization.
99    #[cfg(feature = "vectors")]
100    vectors: BTreeMap<u32, QuantVec>,
101}
102
103impl IndexBuilder {
104    /// A fresh builder.
105    pub fn new() -> Self {
106        Self::default()
107    }
108
109    /// Add one document; returns its id (the insertion ordinal).
110    pub fn add_doc(&mut self, text: &str) -> u64 {
111        let doc = self.doc_lens.len() as u64;
112        let mut len = 0u64;
113        for term in terms(text) {
114            len += term.len() as u64;
115            let counts = self.postings.entry(term).or_default();
116            // Saturate rather than overflow: a document repeating a term
117            // past u16::MAX has long since exhausted the ranking signal.
118            let tf = counts.entry(doc as u32).or_insert(0);
119            *tf = tf.saturating_add(1);
120        }
121        self.doc_lens.push(len);
122        doc
123    }
124
125    /// Attach a quantized embedding to a document already added (`vectors`
126    /// feature). The first vector fixes the index's dimension; later
127    /// vectors must match it or this returns [`IndexError::VectorDim`].
128    #[cfg(feature = "vectors")]
129    pub fn set_vector(&mut self, doc: u32, vector: &[f32]) -> Result<(), IndexError> {
130        if vector.is_empty() {
131            return Err(IndexError::Corrupt {
132                reason: "vector dimension must be at least 1",
133            });
134        }
135        if usize::try_from(doc).map_or(true, |d| d >= self.doc_lens.len()) {
136            return Err(IndexError::Corrupt {
137                reason: "vector attached to an unknown doc id",
138            });
139        }
140        if let Some(expected) = self.vectors.values().next().map(|q| q.dims.len() as u32) {
141            let found = vector.len() as u32;
142            if expected != found {
143                return Err(IndexError::VectorDim { expected, found });
144            }
145        }
146        self.vectors.insert(doc, quantize(vector));
147        Ok(())
148    }
149
150    /// Serialize the index to its binary format.
151    ///
152    /// The only failure modes are serialization-layer bugs (an FST key
153    /// ordering violation or a count that cannot be represented); they
154    /// surface as typed errors, never panics.
155    pub fn build(&self) -> Result<Vec<u8>, IndexError> {
156        // Postings blob first so the FST offsets are known before the
157        // dictionary is serialized.
158        let mut postings = Vec::new();
159        let mut entries: Vec<(&str, u64)> = Vec::with_capacity(self.postings.len());
160        for (term, docs) in &self.postings {
161            let size = u32::try_from(docs.len() * 6).map_err(|_| IndexError::Corrupt {
162                reason: "postings exceed u32 length",
163            })?;
164            entries.push((term, postings.len() as u64));
165            push_u32(&mut postings, size);
166            for (doc, tf) in docs {
167                push_u32(&mut postings, *doc);
168                postings.extend_from_slice(&tf.to_le_bytes());
169            }
170        }
171
172        let mut wtr = MapBuilder::new(Vec::new()).map_err(|_| IndexError::Corrupt {
173            reason: "fst builder init failed",
174        })?;
175        for (term, offset) in entries {
176            // Builder insert only fails on out-of-order keys; BTreeMap
177            // iteration is byte-sorted, which is the order FST requires.
178            wtr.insert(term.as_bytes(), offset)
179                .map_err(|_| IndexError::Corrupt {
180                    reason: "fst key ordering",
181                })?;
182        }
183        let fst_bytes = wtr.into_inner().map_err(|_| IndexError::Corrupt {
184            reason: "fst finalize failed",
185        })?;
186
187        // The vectors section: count-prefixed entries sorted by doc id.
188        #[cfg(feature = "vectors")]
189        let (vec_bytes, dim): (Vec<u8>, u32) = {
190            match self.vectors.values().next() {
191                None => (Vec::new(), 0),
192                Some(first) => {
193                    let mut vb = Vec::new();
194                    push_u32(&mut vb, self.vectors.len() as u32);
195                    for (doc, q) in &self.vectors {
196                        push_u32(&mut vb, *doc);
197                        vb.extend_from_slice(&q.scale.to_le_bytes());
198                        vb.extend_from_slice(&q.norm.to_le_bytes());
199                        for d in &q.dims {
200                            vb.push(*d as u8);
201                        }
202                    }
203                    (vb, first.dims.len() as u32)
204                }
205            }
206        };
207        #[cfg(not(feature = "vectors"))]
208        let (vec_bytes, dim): (Vec<u8>, u32) = (Vec::new(), 0);
209
210        let mut out = Vec::new();
211        out.extend_from_slice(&MAGIC);
212        push_u32(&mut out, VERSION);
213        push_u64(&mut out, self.doc_lens.len() as u64);
214        push_u64(&mut out, fst_bytes.len() as u64);
215        push_u64(&mut out, vec_bytes.len() as u64);
216        push_u32(&mut out, dim);
217        for len in &self.doc_lens {
218            push_u64(&mut out, *len);
219        }
220        out.extend_from_slice(&fst_bytes);
221        out.extend_from_slice(&postings);
222        out.extend_from_slice(&vec_bytes);
223        Ok(out)
224    }
225}
226
227/// One scored query result.
228#[derive(Debug, Clone, PartialEq)]
229pub struct Hit {
230    /// Document id (insertion ordinal).
231    pub doc: u32,
232    /// Relevance score: BM25 for [`Index::query`], approximate cosine for
233    /// [`Index::query_vector`]. Higher is better.
234    pub score: f64,
235}
236
237/// A loaded search index: queryable, wasm-clean, fully read-only.
238#[derive(Debug)]
239pub struct Index {
240    fst_map: fst::Map<Vec<u8>>,
241    postings: Vec<u8>,
242    doc_lens: Vec<u64>,
243    /// Doc-id-sorted quantized vectors, decoded when the section exists.
244    #[cfg(feature = "vectors")]
245    vectors: Vec<(u32, QuantVec)>,
246}
247
248impl Index {
249    /// Decode an index blob. Total: malformed input yields a typed error,
250    /// never a panic (the index is untrusted input, per the estate decoder
251    /// pattern). An index carrying vectors decodes only with the
252    /// `vectors` feature compiled in.
253    pub fn from_bytes(bytes: &[u8]) -> Result<Self, IndexError> {
254        check_header(bytes)?;
255        let mut r = Reader::new(bytes);
256        r.skip(10)?; // magic + version, already validated
257        let doc_count = r.u64()?;
258        let fst_len = r.u64()?;
259        let vec_len = r.u64()?;
260        let dim = r.u32()?;
261
262        if vec_len == 0 && dim != 0 {
263            return Err(IndexError::Corrupt {
264                reason: "dimension declared with no vectors section",
265            });
266        }
267        #[cfg(not(feature = "vectors"))]
268        if vec_len > 0 {
269            return Err(IndexError::VectorsUnsupported);
270        }
271
272        // A doc table entry costs at least 8 bytes; a larger count than the
273        // remaining bytes can express is truncation, not an allocation bomb.
274        if doc_count > r.rest().len() as u64 / 8 {
275            return Err(IndexError::Truncated {
276                section: "doc table",
277            });
278        }
279        let doc_lens = read_doc_lens(&mut r, doc_count)?;
280
281        let fst_start = r.pos();
282        let fst_end = fst_start
283            .checked_add(usize::try_from(fst_len).map_err(|_| IndexError::Corrupt {
284                reason: "fst length exceeds address space",
285            })?)
286            .ok_or(IndexError::Corrupt {
287                reason: "fst section overflows",
288            })?;
289        let fst_bytes = bytes.get(fst_start..fst_end).ok_or(IndexError::Truncated {
290            section: "fst dictionary",
291        })?;
292        let tail = bytes.get(fst_end..).ok_or(IndexError::Truncated {
293            section: "postings",
294        })?;
295        let vec_len = usize::try_from(vec_len).map_err(|_| IndexError::Corrupt {
296            reason: "vectors length exceeds address space",
297        })?;
298        if vec_len > tail.len() {
299            return Err(IndexError::Corrupt {
300                reason: "vectors section overruns the blob",
301            });
302        }
303        let postings_end = tail.len() - vec_len;
304        let postings = tail.get(0..postings_end).ok_or(IndexError::Corrupt {
305            reason: "postings section bounds",
306        })?;
307
308        let fst_map = fst_guard(|| fst::Map::new(fst_bytes.to_vec()))?;
309        validate_postings(postings, doc_count)?;
310
311        // Cross-section coherence: every dictionary offset must resolve to
312        // a postings list inside the area, so a decoded index can never
313        // produce a silent empty query from an unresolvable term. Streaming
314        // the whole dictionary here also exercises every node, which is
315        // what makes query-time reads panic-free in practice.
316        fst_guard(|| {
317            let mut terms = fst_map.stream();
318            while let Some((_, offset)) = terms.next() {
319                read_pairs_at(postings, offset as usize)?;
320            }
321            Ok::<(), IndexError>(())
322        })?;
323
324        #[cfg(feature = "vectors")]
325        let vectors = if vec_len == 0 {
326            Vec::new()
327        } else {
328            let vec_bytes = tail.get(postings_end..).ok_or(IndexError::Corrupt {
329                reason: "vectors section bounds",
330            })?;
331            parse_vectors(vec_bytes, dim, doc_count)?
332        };
333        Ok(Self {
334            fst_map,
335            postings: postings.to_vec(),
336            doc_lens,
337            #[cfg(feature = "vectors")]
338            vectors,
339        })
340    }
341
342    /// Number of documents.
343    pub fn len(&self) -> u64 {
344        self.doc_lens.len() as u64
345    }
346
347    /// Whether there are no documents.
348    pub fn is_empty(&self) -> bool {
349        self.doc_lens.is_empty()
350    }
351
352    /// AND-query the index, ranked by BM25 over true term frequencies,
353    /// best first, at most `limit` hits.
354    ///
355    /// A query term missing from the dictionary yields no hits (AND
356    /// semantics). Corrupt postings for a queried term also yield no hits:
357    /// query is a read path and reports emptiness rather than erroring.
358    pub fn query(&self, query: &str, limit: usize) -> Vec<Hit> {
359        let query_terms: Vec<String> = terms(query).collect();
360        if query_terms.is_empty() {
361            return Vec::new();
362        }
363
364        let mut lists: Vec<PairList> = Vec::with_capacity(query_terms.len());
365        for term in &query_terms {
366            match self.postings_for(term) {
367                Ok(Some(list)) => lists.push(list),
368                Ok(None) | Err(_) => return Vec::new(),
369            }
370        }
371        let Some(first) = lists.first() else {
372            return Vec::new();
373        };
374
375        let n = self.len();
376        let avgdl = average(&self.doc_lens);
377        let mut hits: Vec<Hit> = Vec::new();
378        for &(doc, _) in first {
379            let Some(dl) = self.doc_lens.get(doc as usize) else {
380                continue;
381            };
382            // AND: the candidate must appear in every other list.
383            let in_all = lists
384                .iter()
385                .skip(1)
386                .all(|list| list.binary_search_by_key(&doc, |pair| pair.0).is_ok());
387            if !in_all {
388                continue;
389            }
390            let mut score = 0.0;
391            for list in &lists {
392                let tf = list
393                    .binary_search_by_key(&doc, |pair| pair.0)
394                    .ok()
395                    .and_then(|i| list.get(i))
396                    .map_or(1, |pair| pair.1);
397                score += idf(n, list.len() as u64) * norm(tf, *dl, avgdl);
398            }
399            hits.push(Hit { doc, score });
400        }
401        hits.sort_by(|a, b| b.score.total_cmp(&a.score).then(a.doc.cmp(&b.doc)));
402        hits.truncate(limit);
403        hits
404    }
405
406    /// Nearest-neighbor query over the index's quantized vectors
407    /// (`vectors` feature): approximate cosine similarity, best first, at
408    /// most `limit` hits. Documents without vectors never match; a query
409    /// dimension different from the index's yields no hits (read paths
410    /// report emptiness, not errors). Scores are approximate: i8
411    /// quantization trades a bounded, fixed error for a format that is a
412    /// fraction of the f32 size.
413    #[cfg(feature = "vectors")]
414    pub fn query_vector(&self, vector: &[f32], limit: usize) -> Vec<Hit> {
415        if vector.is_empty() || self.vectors.is_empty() {
416            return Vec::new();
417        }
418        let dim_matches = self
419            .vectors
420            .first()
421            .is_none_or(|(_, q)| q.dims.len() == vector.len());
422        if !dim_matches {
423            return Vec::new();
424        }
425        let query = quantize(vector);
426        let mut hits: Vec<Hit> = Vec::new();
427        for (doc, d) in &self.vectors {
428            if d.norm == 0.0 || query.norm == 0.0 {
429                continue; // zero vectors carry no direction
430            }
431            let dot: i64 = d
432                .dims
433                .iter()
434                .zip(&query.dims)
435                .map(|(a, b)| i64::from(*a) * i64::from(*b))
436                .sum();
437            let score = dot as f64 / (f64::from(d.norm) * f64::from(query.norm));
438            hits.push(Hit { doc: *doc, score });
439        }
440        hits.sort_by(|a, b| b.score.total_cmp(&a.score).then(a.doc.cmp(&b.doc)));
441        hits.truncate(limit);
442        hits
443    }
444
445    fn postings_for(&self, term: &str) -> Result<Option<PairList>, IndexError> {
446        // The dictionary was fully streamed at decode, so reads cannot
447        // panic on a decoded index; the guard is defense-in-depth so the
448        // query path stays total regardless.
449        let lookup = std::panic::catch_unwind(|| self.fst_map.get(term.as_bytes()));
450        let offset = match lookup {
451            Ok(Some(offset)) => offset,
452            Ok(None) => return Ok(None),
453            Err(_) => {
454                return Err(IndexError::Corrupt {
455                    reason: "term dictionary rejected hostile input",
456                })
457            }
458        };
459        read_pairs_at(&self.postings, offset as usize).map(Some)
460    }
461}
462
463/// Bounds-checked postings-list read at `start`: `u32` byte-length prefix
464/// plus (doc u32, tf u16) pairs. Shared by decode-time validation and
465/// query-time lookups. Pairs are returned in stored order; the length
466/// prefix is exact (`4 + 6 * count` bytes are consumed), which the caller
467/// can use to advance a walk.
468fn read_pairs_at(postings: &[u8], start: usize) -> Result<PairList, IndexError> {
469    let len_pos = start.checked_add(4).ok_or(IndexError::Corrupt {
470        reason: "postings offset overflows",
471    })?;
472    let len_bytes = postings.get(start..len_pos).ok_or(IndexError::Corrupt {
473        reason: "postings offset out of range",
474    })?;
475    let mut raw = [0u8; 4];
476    raw.copy_from_slice(len_bytes);
477    let len = usize::try_from(u32::from_le_bytes(raw)).map_err(|_| IndexError::Corrupt {
478        reason: "postings length exceeds address space",
479    })?;
480    let end = len_pos.checked_add(len).ok_or(IndexError::Corrupt {
481        reason: "postings length overflows",
482    })?;
483    let bytes = postings.get(len_pos..end).ok_or(IndexError::Corrupt {
484        reason: "postings bytes out of range",
485    })?;
486    if len % 6 != 0 {
487        return Err(IndexError::Corrupt {
488            reason: "postings length is not a multiple of the 6-byte pair",
489        });
490    }
491    let mut out = Vec::with_capacity(len / 6);
492    for chunk in bytes.chunks_exact(6) {
493        let doc_bytes = chunk.get(0..4).ok_or(IndexError::Corrupt {
494            reason: "truncated posting pair",
495        })?;
496        let tf_bytes = chunk.get(4..6).ok_or(IndexError::Corrupt {
497            reason: "truncated posting pair",
498        })?;
499        let mut doc_raw = [0u8; 4];
500        doc_raw.copy_from_slice(doc_bytes);
501        let mut tf_raw = [0u8; 2];
502        tf_raw.copy_from_slice(tf_bytes);
503        out.push((u32::from_le_bytes(doc_raw), u16::from_le_bytes(tf_raw)));
504    }
505    Ok(out)
506}
507
508/// Walk the entire postings area: every entry's length must fit, every
509/// pair list must parse, docs must be strictly increasing with tf >= 1
510/// and in range, and the entries must exactly cover the area (no trailing
511/// garbage, no silently-empty truncation). Decode-time validation means a
512/// decoded index can always answer queries; corruption is never deferred
513/// to a silent empty result later.
514fn validate_postings(postings: &[u8], doc_count: u64) -> Result<(), IndexError> {
515    let mut pos = 0usize;
516    while pos < postings.len() {
517        let list = read_pairs_at(postings, pos)?;
518        let mut prev: Option<u32> = None;
519        for (doc, tf) in &list {
520            if *tf == 0 {
521                return Err(IndexError::Corrupt {
522                    reason: "posting with zero term frequency",
523                });
524            }
525            if u64::from(*doc) >= doc_count {
526                return Err(IndexError::Corrupt {
527                    reason: "posting doc id out of range",
528                });
529            }
530            if prev.is_some_and(|p| p >= *doc) {
531                return Err(IndexError::Corrupt {
532                    reason: "postings not strictly increasing by doc id",
533                });
534            }
535            prev = Some(*doc);
536        }
537        pos += 4 + list.len() * 6;
538    }
539    if pos != postings.len() {
540        return Err(IndexError::Corrupt {
541            reason: "postings not fully consumed",
542        });
543    }
544    Ok(())
545}
546
547/// Parse and validate the quantized-vector section (`vectors` feature):
548/// exact stride coverage, doc ids strictly increasing and in range,
549/// finite scale and norm metadata.
550#[cfg(feature = "vectors")]
551fn parse_vectors(
552    bytes: &[u8],
553    dim: u32,
554    doc_count: u64,
555) -> Result<Vec<(u32, QuantVec)>, IndexError> {
556    let dim = usize::try_from(dim).map_err(|_| IndexError::Corrupt {
557        reason: "vector dimension exceeds address space",
558    })?;
559    if dim == 0 {
560        return Err(IndexError::Corrupt {
561            reason: "vectors section with zero dimension",
562        });
563    }
564    let stride = dim + 12; // doc u32 + scale f32 + norm f32 + dim i8s
565    let mut r = Reader::new(bytes);
566    let count = r.u32()?;
567    let count = usize::try_from(count).map_err(|_| IndexError::Corrupt {
568        reason: "vector count exceeds address space",
569    })?;
570    let expected_len = count
571        .checked_mul(stride)
572        .and_then(|n| n.checked_add(4))
573        .ok_or(IndexError::Corrupt {
574            reason: "vectors section length overflows",
575        })?;
576    if expected_len != bytes.len() {
577        return Err(IndexError::Corrupt {
578            reason: "vectors section length does not match its count",
579        });
580    }
581    let mut out = Vec::with_capacity(count);
582    let mut prev: Option<u32> = None;
583    for _ in 0..count {
584        let doc = r.u32()?;
585        if u64::from(doc) >= doc_count {
586            return Err(IndexError::Corrupt {
587                reason: "vector doc id out of range",
588            });
589        }
590        if prev.is_some_and(|p| p >= doc) {
591            return Err(IndexError::Corrupt {
592                reason: "vectors not strictly increasing by doc id",
593            });
594        }
595        prev = Some(doc);
596        let scale = r.f32()?;
597        let norm = r.f32()?;
598        if !scale.is_finite() || !norm.is_finite() || norm < 0.0 {
599            return Err(IndexError::Corrupt {
600                reason: "non-finite or negative vector scale or norm",
601            });
602        }
603        let mut dims = Vec::with_capacity(dim);
604        for _ in 0..dim {
605            dims.push(r.i8()?);
606        }
607        out.push((doc, QuantVec { scale, norm, dims }));
608    }
609    Ok(out)
610}
611
612fn read_doc_lens(r: &mut Reader<'_>, doc_count: u64) -> Result<Vec<u64>, IndexError> {
613    let mut lens = Vec::new();
614    for _ in 0..doc_count {
615        lens.push(r.u64()?);
616    }
617    Ok(lens)
618}
619
620fn average(doc_lens: &[u64]) -> f64 {
621    if doc_lens.is_empty() {
622        return 1.0;
623    }
624    let total: u64 = doc_lens.iter().sum();
625    if total == 0 {
626        1.0
627    } else {
628        total as f64 / doc_lens.len() as f64
629    }
630}
631
632fn idf(n_docs: u64, n_matching: u64) -> f64 {
633    let n = n_docs as f64;
634    let matching = n_matching as f64;
635    (1.0 + (n - matching + 0.5) / (matching + 0.5)).ln()
636}
637
638/// BM25 term-frequency component with length normalization:
639/// `tf * (k1 + 1) / (tf + k1 * (1 - b + b * dl / avgdl))`.
640fn norm(tf: u16, dl: u64, avgdl: f64) -> f64 {
641    let tf = f64::from(tf);
642    let dl = dl as f64;
643    tf * (K1 + 1.0) / (tf + K1 * (1.0 - B + B * dl / avgdl))
644}