1use 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
10fn 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
30const K1: f64 = 1.2;
32const B: f64 = 0.75;
34
35fn 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
43type PairList = Vec<(u32, u16)>;
48
49#[cfg(feature = "vectors")]
52#[derive(Debug, Clone)]
53struct QuantVec {
54 scale: f32,
56 norm: f32,
58 dims: Vec<i8>,
60}
61
62#[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#[derive(Debug, Default)]
95pub struct IndexBuilder {
96 postings: BTreeMap<String, BTreeMap<u32, u16>>,
97 doc_lens: Vec<u64>,
98 #[cfg(feature = "vectors")]
100 vectors: BTreeMap<u32, QuantVec>,
101}
102
103impl IndexBuilder {
104 pub fn new() -> Self {
106 Self::default()
107 }
108
109 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 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 #[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 pub fn build(&self) -> Result<Vec<u8>, IndexError> {
156 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 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 #[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#[derive(Debug, Clone, PartialEq)]
229pub struct Hit {
230 pub doc: u32,
232 pub score: f64,
235}
236
237#[derive(Debug)]
239pub struct Index {
240 fst_map: fst::Map<Vec<u8>>,
241 postings: Vec<u8>,
242 doc_lens: Vec<u64>,
243 #[cfg(feature = "vectors")]
245 vectors: Vec<(u32, QuantVec)>,
246}
247
248impl Index {
249 pub fn from_bytes(bytes: &[u8]) -> Result<Self, IndexError> {
254 check_header(bytes)?;
255 let mut r = Reader::new(bytes);
256 r.skip(10)?; 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 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 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 pub fn len(&self) -> u64 {
344 self.doc_lens.len() as u64
345 }
346
347 pub fn is_empty(&self) -> bool {
349 self.doc_lens.is_empty()
350 }
351
352 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 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 #[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; }
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 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
463fn 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
508fn 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#[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; 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
638fn 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}