use std::collections::BTreeMap;
use fst::{MapBuilder, Streamer};
use roaring::RoaringBitmap;
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())
}
#[derive(Debug, Default)]
pub struct IndexBuilder {
postings: BTreeMap<String, RoaringBitmap>,
doc_lens: Vec<u64>,
}
impl IndexBuilder {
pub fn new() -> Self {
Self::default()
}
pub fn add_doc(&mut self, text: &str) {
let doc = self.doc_lens.len() as u64;
let mut len = 0u64;
for term in terms(text) {
len += term.len() as u64;
self.postings.entry(term).or_default().insert(doc as u32);
}
self.doc_lens.push(len);
}
pub fn build(&self) -> Result<Vec<u8>, IndexError> {
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);
let mut postings = Vec::new();
let mut entries: Vec<(&str, u64)> = Vec::with_capacity(self.postings.len());
for (term, bitmap) in &self.postings {
let size =
u32::try_from(bitmap.serialized_size()).map_err(|_| IndexError::Corrupt {
reason: "bitmap exceeds u32 length",
})?;
entries.push((term, postings.len() as u64));
push_u32(&mut postings, size);
bitmap
.serialize_into(&mut postings)
.map_err(|_| IndexError::Corrupt {
reason: "bitmap serialization failed",
})?;
}
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",
})?;
push_u64(&mut out, fst_bytes.len() as u64);
for len in &self.doc_lens {
push_u64(&mut out, *len);
}
out.extend_from_slice(&fst_bytes);
out.extend_from_slice(&postings);
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>,
}
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()?;
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 postings = bytes.get(fst_end..).ok_or(IndexError::Truncated {
section: "postings",
})?;
let fst_map = fst_guard(|| fst::Map::new(fst_bytes.to_vec()))?;
validate_postings(postings)?;
fst_guard(|| {
let mut terms = fst_map.stream();
while let Some((_, offset)) = terms.next() {
read_bitmap_at(postings, offset as usize)?;
}
Ok::<(), IndexError>(())
})?;
Ok(Self {
fst_map,
postings: postings.to_vec(),
doc_lens,
})
}
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 matched: Vec<RoaringBitmap> = Vec::new();
for term in &query_terms {
match self.postings_for(term) {
Ok(Some(bm)) => matched.push(bm),
Ok(None) | Err(_) => return Vec::new(),
}
}
let Some(first) = matched.first() else {
return Vec::new();
};
let mut docs = first.clone();
for bm in &matched {
docs &= bm;
}
let n = self.len();
let avgdl = average(&self.doc_lens);
let mut hits: Vec<Hit> = Vec::new();
for doc in docs {
let Some(dl) = self.doc_lens.get(doc as usize) else {
continue;
};
let mut score = 0.0;
for term in &query_terms {
if let Ok(Some(bm)) = self.postings_for(term) {
if bm.contains(doc) {
let idf = idf(n, bm.len());
score += idf * norm(*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
}
fn postings_for(&self, term: &str) -> Result<Option<RoaringBitmap>, 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_bitmap_at(&self.postings, offset as usize).map(Some)
}
}
fn read_bitmap_at(postings: &[u8], start: usize) -> Result<RoaringBitmap, 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: "bitmap length exceeds address space",
})?;
let end = len_pos.checked_add(len).ok_or(IndexError::Corrupt {
reason: "bitmap length overflows",
})?;
let bytes = postings.get(len_pos..end).ok_or(IndexError::Corrupt {
reason: "bitmap bytes out of range",
})?;
RoaringBitmap::deserialize_from(bytes).map_err(|_| IndexError::Corrupt {
reason: "bitmap deserialization",
})
}
fn validate_postings(postings: &[u8]) -> Result<(), IndexError> {
let mut pos = 0usize;
while pos < postings.len() {
let len_pos = pos.checked_add(4).ok_or(IndexError::Corrupt {
reason: "postings offset overflows",
})?;
let len_bytes = postings.get(pos..len_pos).ok_or(IndexError::Corrupt {
reason: "truncated bitmap length",
})?;
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: "bitmap length exceeds address space",
})?;
let end = len_pos.checked_add(len).ok_or(IndexError::Corrupt {
reason: "bitmap length overflows",
})?;
if end > postings.len() {
return Err(IndexError::Corrupt {
reason: "bitmap bytes out of range",
});
}
let _ = read_bitmap_at(postings, pos)?;
pos = end;
}
if pos != postings.len() {
return Err(IndexError::Corrupt {
reason: "postings not fully consumed",
});
}
Ok(())
}
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(dl: u64, avgdl: f64) -> f64 {
let dl = dl as f64;
(K1 + 1.0) / (1.0 + K1 * (1.0 - B + B * dl / avgdl))
}