use std::collections::BTreeMap;
use fst::{MapBuilder, Streamer};
use crate::error::IndexError;
use crate::format::{check_header, push_u32, push_u64, Reader, MAGIC, VERSION};
fn fst_guard<T, E>(op: impl FnOnce() -> Result<T, E>) -> Result<T, IndexError>
where
E: std::error::Error + 'static,
IndexError: From<E>,
{
std::panic::catch_unwind(std::panic::AssertUnwindSafe(op))
.map_err(|_| IndexError::Corrupt {
reason: "term dictionary rejected hostile input",
})?
.map_err(IndexError::from)
}
const K1: f64 = 1.2;
const B: f64 = 0.75;
fn terms(text: &str) -> impl Iterator<Item = String> + '_ {
text.split(|c: char| !c.is_alphanumeric())
.filter(|t| !t.is_empty())
.map(|t| t.to_lowercase())
}
type PairList = Vec<(u32, u16)>;
#[cfg(feature = "vectors")]
#[derive(Debug, Clone)]
struct QuantVec {
scale: f32,
norm: f32,
dims: Vec<i8>,
}
#[cfg(feature = "vectors")]
fn quantize(vector: &[f32]) -> QuantVec {
let max_abs = vector.iter().fold(0.0f32, |m, v| m.max(v.abs()));
let scale = if max_abs > 0.0 { 127.0 / max_abs } else { 0.0 };
let dims: Vec<i8> = vector
.iter()
.map(|v| {
let q = (v * scale).round();
if q >= 127.0 {
127
} else if q <= -127.0 {
-127
} else {
q as i8
}
})
.collect();
let norm = dims
.iter()
.map(|q| (*q as f32) * (*q as f32))
.sum::<f32>()
.sqrt();
QuantVec { scale, norm, dims }
}
#[derive(Debug, Default)]
pub struct IndexBuilder {
postings: BTreeMap<String, BTreeMap<u32, u16>>,
doc_lens: Vec<u64>,
#[cfg(feature = "vectors")]
vectors: BTreeMap<u32, QuantVec>,
}
impl IndexBuilder {
pub fn new() -> Self {
Self::default()
}
pub fn add_doc(&mut self, text: &str) -> u64 {
let doc = self.doc_lens.len() as u64;
let mut len = 0u64;
for term in terms(text) {
len += term.len() as u64;
let counts = self.postings.entry(term).or_default();
let tf = counts.entry(doc as u32).or_insert(0);
*tf = tf.saturating_add(1);
}
self.doc_lens.push(len);
doc
}
#[cfg(feature = "vectors")]
pub fn set_vector(&mut self, doc: u32, vector: &[f32]) -> Result<(), IndexError> {
if vector.is_empty() {
return Err(IndexError::Corrupt {
reason: "vector dimension must be at least 1",
});
}
if usize::try_from(doc).map_or(true, |d| d >= self.doc_lens.len()) {
return Err(IndexError::Corrupt {
reason: "vector attached to an unknown doc id",
});
}
if let Some(expected) = self.vectors.values().next().map(|q| q.dims.len() as u32) {
let found = vector.len() as u32;
if expected != found {
return Err(IndexError::VectorDim { expected, found });
}
}
self.vectors.insert(doc, quantize(vector));
Ok(())
}
pub fn build(&self) -> Result<Vec<u8>, IndexError> {
let mut postings = Vec::new();
let mut entries: Vec<(&str, u64)> = Vec::with_capacity(self.postings.len());
for (term, docs) in &self.postings {
let size = u32::try_from(docs.len() * 6).map_err(|_| IndexError::Corrupt {
reason: "postings exceed u32 length",
})?;
entries.push((term, postings.len() as u64));
push_u32(&mut postings, size);
for (doc, tf) in docs {
push_u32(&mut postings, *doc);
postings.extend_from_slice(&tf.to_le_bytes());
}
}
let mut wtr = MapBuilder::new(Vec::new()).map_err(|_| IndexError::Corrupt {
reason: "fst builder init failed",
})?;
for (term, offset) in entries {
wtr.insert(term.as_bytes(), offset)
.map_err(|_| IndexError::Corrupt {
reason: "fst key ordering",
})?;
}
let fst_bytes = wtr.into_inner().map_err(|_| IndexError::Corrupt {
reason: "fst finalize failed",
})?;
#[cfg(feature = "vectors")]
let (vec_bytes, dim): (Vec<u8>, u32) = {
match self.vectors.values().next() {
None => (Vec::new(), 0),
Some(first) => {
let mut vb = Vec::new();
push_u32(&mut vb, self.vectors.len() as u32);
for (doc, q) in &self.vectors {
push_u32(&mut vb, *doc);
vb.extend_from_slice(&q.scale.to_le_bytes());
vb.extend_from_slice(&q.norm.to_le_bytes());
for d in &q.dims {
vb.push(*d as u8);
}
}
(vb, first.dims.len() as u32)
}
}
};
#[cfg(not(feature = "vectors"))]
let (vec_bytes, dim): (Vec<u8>, u32) = (Vec::new(), 0);
let mut out = Vec::new();
out.extend_from_slice(&MAGIC);
push_u32(&mut out, VERSION);
push_u64(&mut out, self.doc_lens.len() as u64);
push_u64(&mut out, fst_bytes.len() as u64);
push_u64(&mut out, vec_bytes.len() as u64);
push_u32(&mut out, dim);
for len in &self.doc_lens {
push_u64(&mut out, *len);
}
out.extend_from_slice(&fst_bytes);
out.extend_from_slice(&postings);
out.extend_from_slice(&vec_bytes);
Ok(out)
}
}
#[derive(Debug, Clone, PartialEq)]
pub struct Hit {
pub doc: u32,
pub score: f64,
}
#[derive(Debug)]
pub struct Index {
fst_map: fst::Map<Vec<u8>>,
postings: Vec<u8>,
doc_lens: Vec<u64>,
#[cfg(feature = "vectors")]
vectors: Vec<(u32, QuantVec)>,
}
impl Index {
pub fn from_bytes(bytes: &[u8]) -> Result<Self, IndexError> {
check_header(bytes)?;
let mut r = Reader::new(bytes);
r.skip(10)?; let doc_count = r.u64()?;
let fst_len = r.u64()?;
let vec_len = r.u64()?;
let dim = r.u32()?;
if vec_len == 0 && dim != 0 {
return Err(IndexError::Corrupt {
reason: "dimension declared with no vectors section",
});
}
#[cfg(not(feature = "vectors"))]
if vec_len > 0 {
return Err(IndexError::VectorsUnsupported);
}
if doc_count > r.rest().len() as u64 / 8 {
return Err(IndexError::Truncated {
section: "doc table",
});
}
let doc_lens = read_doc_lens(&mut r, doc_count)?;
let fst_start = r.pos();
let fst_end = fst_start
.checked_add(usize::try_from(fst_len).map_err(|_| IndexError::Corrupt {
reason: "fst length exceeds address space",
})?)
.ok_or(IndexError::Corrupt {
reason: "fst section overflows",
})?;
let fst_bytes = bytes.get(fst_start..fst_end).ok_or(IndexError::Truncated {
section: "fst dictionary",
})?;
let tail = bytes.get(fst_end..).ok_or(IndexError::Truncated {
section: "postings",
})?;
let vec_len = usize::try_from(vec_len).map_err(|_| IndexError::Corrupt {
reason: "vectors length exceeds address space",
})?;
if vec_len > tail.len() {
return Err(IndexError::Corrupt {
reason: "vectors section overruns the blob",
});
}
let postings_end = tail.len() - vec_len;
let postings = tail.get(0..postings_end).ok_or(IndexError::Corrupt {
reason: "postings section bounds",
})?;
let fst_map = fst_guard(|| fst::Map::new(fst_bytes.to_vec()))?;
validate_postings(postings, doc_count)?;
fst_guard(|| {
let mut terms = fst_map.stream();
while let Some((_, offset)) = terms.next() {
read_pairs_at(postings, offset as usize)?;
}
Ok::<(), IndexError>(())
})?;
#[cfg(feature = "vectors")]
let vectors = if vec_len == 0 {
Vec::new()
} else {
let vec_bytes = tail.get(postings_end..).ok_or(IndexError::Corrupt {
reason: "vectors section bounds",
})?;
parse_vectors(vec_bytes, dim, doc_count)?
};
Ok(Self {
fst_map,
postings: postings.to_vec(),
doc_lens,
#[cfg(feature = "vectors")]
vectors,
})
}
pub fn len(&self) -> u64 {
self.doc_lens.len() as u64
}
pub fn is_empty(&self) -> bool {
self.doc_lens.is_empty()
}
pub fn query(&self, query: &str, limit: usize) -> Vec<Hit> {
let query_terms: Vec<String> = terms(query).collect();
if query_terms.is_empty() {
return Vec::new();
}
let mut lists: Vec<PairList> = Vec::with_capacity(query_terms.len());
for term in &query_terms {
match self.postings_for(term) {
Ok(Some(list)) => lists.push(list),
Ok(None) | Err(_) => return Vec::new(),
}
}
let Some(first) = lists.first() else {
return Vec::new();
};
let n = self.len();
let avgdl = average(&self.doc_lens);
let mut hits: Vec<Hit> = Vec::new();
for &(doc, _) in first {
let Some(dl) = self.doc_lens.get(doc as usize) else {
continue;
};
let in_all = lists
.iter()
.skip(1)
.all(|list| list.binary_search_by_key(&doc, |pair| pair.0).is_ok());
if !in_all {
continue;
}
let mut score = 0.0;
for list in &lists {
let tf = list
.binary_search_by_key(&doc, |pair| pair.0)
.ok()
.and_then(|i| list.get(i))
.map_or(1, |pair| pair.1);
score += idf(n, list.len() as u64) * norm(tf, *dl, avgdl);
}
hits.push(Hit { doc, score });
}
hits.sort_by(|a, b| b.score.total_cmp(&a.score).then(a.doc.cmp(&b.doc)));
hits.truncate(limit);
hits
}
#[cfg(feature = "vectors")]
pub fn query_vector(&self, vector: &[f32], limit: usize) -> Vec<Hit> {
if vector.is_empty() || self.vectors.is_empty() {
return Vec::new();
}
let dim_matches = self
.vectors
.first()
.is_none_or(|(_, q)| q.dims.len() == vector.len());
if !dim_matches {
return Vec::new();
}
let query = quantize(vector);
let mut hits: Vec<Hit> = Vec::new();
for (doc, d) in &self.vectors {
if d.norm == 0.0 || query.norm == 0.0 {
continue; }
let dot: i64 = d
.dims
.iter()
.zip(&query.dims)
.map(|(a, b)| i64::from(*a) * i64::from(*b))
.sum();
let score = dot as f64 / (f64::from(d.norm) * f64::from(query.norm));
hits.push(Hit { doc: *doc, score });
}
hits.sort_by(|a, b| b.score.total_cmp(&a.score).then(a.doc.cmp(&b.doc)));
hits.truncate(limit);
hits
}
fn postings_for(&self, term: &str) -> Result<Option<PairList>, IndexError> {
let lookup = std::panic::catch_unwind(|| self.fst_map.get(term.as_bytes()));
let offset = match lookup {
Ok(Some(offset)) => offset,
Ok(None) => return Ok(None),
Err(_) => {
return Err(IndexError::Corrupt {
reason: "term dictionary rejected hostile input",
})
}
};
read_pairs_at(&self.postings, offset as usize).map(Some)
}
}
fn read_pairs_at(postings: &[u8], start: usize) -> Result<PairList, IndexError> {
let len_pos = start.checked_add(4).ok_or(IndexError::Corrupt {
reason: "postings offset overflows",
})?;
let len_bytes = postings.get(start..len_pos).ok_or(IndexError::Corrupt {
reason: "postings offset out of range",
})?;
let mut raw = [0u8; 4];
raw.copy_from_slice(len_bytes);
let len = usize::try_from(u32::from_le_bytes(raw)).map_err(|_| IndexError::Corrupt {
reason: "postings length exceeds address space",
})?;
let end = len_pos.checked_add(len).ok_or(IndexError::Corrupt {
reason: "postings length overflows",
})?;
let bytes = postings.get(len_pos..end).ok_or(IndexError::Corrupt {
reason: "postings bytes out of range",
})?;
if len % 6 != 0 {
return Err(IndexError::Corrupt {
reason: "postings length is not a multiple of the 6-byte pair",
});
}
let mut out = Vec::with_capacity(len / 6);
for chunk in bytes.chunks_exact(6) {
let doc_bytes = chunk.get(0..4).ok_or(IndexError::Corrupt {
reason: "truncated posting pair",
})?;
let tf_bytes = chunk.get(4..6).ok_or(IndexError::Corrupt {
reason: "truncated posting pair",
})?;
let mut doc_raw = [0u8; 4];
doc_raw.copy_from_slice(doc_bytes);
let mut tf_raw = [0u8; 2];
tf_raw.copy_from_slice(tf_bytes);
out.push((u32::from_le_bytes(doc_raw), u16::from_le_bytes(tf_raw)));
}
Ok(out)
}
fn validate_postings(postings: &[u8], doc_count: u64) -> Result<(), IndexError> {
let mut pos = 0usize;
while pos < postings.len() {
let list = read_pairs_at(postings, pos)?;
let mut prev: Option<u32> = None;
for (doc, tf) in &list {
if *tf == 0 {
return Err(IndexError::Corrupt {
reason: "posting with zero term frequency",
});
}
if u64::from(*doc) >= doc_count {
return Err(IndexError::Corrupt {
reason: "posting doc id out of range",
});
}
if prev.is_some_and(|p| p >= *doc) {
return Err(IndexError::Corrupt {
reason: "postings not strictly increasing by doc id",
});
}
prev = Some(*doc);
}
pos += 4 + list.len() * 6;
}
if pos != postings.len() {
return Err(IndexError::Corrupt {
reason: "postings not fully consumed",
});
}
Ok(())
}
#[cfg(feature = "vectors")]
fn parse_vectors(
bytes: &[u8],
dim: u32,
doc_count: u64,
) -> Result<Vec<(u32, QuantVec)>, IndexError> {
let dim = usize::try_from(dim).map_err(|_| IndexError::Corrupt {
reason: "vector dimension exceeds address space",
})?;
if dim == 0 {
return Err(IndexError::Corrupt {
reason: "vectors section with zero dimension",
});
}
let stride = dim + 12; let mut r = Reader::new(bytes);
let count = r.u32()?;
let count = usize::try_from(count).map_err(|_| IndexError::Corrupt {
reason: "vector count exceeds address space",
})?;
let expected_len = count
.checked_mul(stride)
.and_then(|n| n.checked_add(4))
.ok_or(IndexError::Corrupt {
reason: "vectors section length overflows",
})?;
if expected_len != bytes.len() {
return Err(IndexError::Corrupt {
reason: "vectors section length does not match its count",
});
}
let mut out = Vec::with_capacity(count);
let mut prev: Option<u32> = None;
for _ in 0..count {
let doc = r.u32()?;
if u64::from(doc) >= doc_count {
return Err(IndexError::Corrupt {
reason: "vector doc id out of range",
});
}
if prev.is_some_and(|p| p >= doc) {
return Err(IndexError::Corrupt {
reason: "vectors not strictly increasing by doc id",
});
}
prev = Some(doc);
let scale = r.f32()?;
let norm = r.f32()?;
if !scale.is_finite() || !norm.is_finite() || norm < 0.0 {
return Err(IndexError::Corrupt {
reason: "non-finite or negative vector scale or norm",
});
}
let mut dims = Vec::with_capacity(dim);
for _ in 0..dim {
dims.push(r.i8()?);
}
out.push((doc, QuantVec { scale, norm, dims }));
}
Ok(out)
}
fn read_doc_lens(r: &mut Reader<'_>, doc_count: u64) -> Result<Vec<u64>, IndexError> {
let mut lens = Vec::new();
for _ in 0..doc_count {
lens.push(r.u64()?);
}
Ok(lens)
}
fn average(doc_lens: &[u64]) -> f64 {
if doc_lens.is_empty() {
return 1.0;
}
let total: u64 = doc_lens.iter().sum();
if total == 0 {
1.0
} else {
total as f64 / doc_lens.len() as f64
}
}
fn idf(n_docs: u64, n_matching: u64) -> f64 {
let n = n_docs as f64;
let matching = n_matching as f64;
(1.0 + (n - matching + 0.5) / (matching + 0.5)).ln()
}
fn norm(tf: u16, dl: u64, avgdl: f64) -> f64 {
let tf = f64::from(tf);
let dl = dl as f64;
tf * (K1 + 1.0) / (tf + K1 * (1.0 - B + B * dl / avgdl))
}