1use 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
11fn 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
31const K1: f64 = 1.2;
33const B: f64 = 0.75;
35
36fn 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#[derive(Debug, Default)]
50pub struct IndexBuilder {
51 postings: BTreeMap<String, RoaringBitmap>,
52 doc_lens: Vec<u64>,
53}
54
55impl IndexBuilder {
56 pub fn new() -> Self {
58 Self::default()
59 }
60
61 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 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 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 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#[derive(Debug, Clone, PartialEq)]
128pub struct Hit {
129 pub doc: u32,
131 pub score: f64,
133}
134
135#[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 pub fn from_bytes(bytes: &[u8]) -> Result<Self, IndexError> {
148 check_header(bytes)?;
149 let mut r = Reader::new(bytes);
150 r.skip(10)?; let doc_count = r.u64()?;
152 let fst_len = r.u64()?;
153
154 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 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 pub fn len(&self) -> u64 {
201 self.doc_lens.len() as u64
202 }
203
204 pub fn is_empty(&self) -> bool {
206 self.doc_lens.is_empty()
207 }
208
209 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 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
277fn 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
302fn 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
366fn 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}