1use anyhow::{Context, Result};
17use std::collections::HashMap;
18use std::fs::{File, OpenOptions};
19use std::io::Write;
20use std::path::{Path, PathBuf};
21
22pub type Trigram = u32;
24
25pub(crate) const MAGIC: &[u8; 4] = b"RFTG"; pub(crate) const VERSION: u32 = 4;
30pub(crate) const HEADER_SIZE: usize = 32;
32pub(crate) const DIR_ENTRY_SIZE: usize = 16;
34const NUM_TRIGRAMS_OFFSET: usize = 8;
36const NUM_FILES_OFFSET: usize = 16;
37pub(crate) const PATHS_OFFSET_OFFSET: usize = 24;
38
39pub(crate) fn write_varint(writer: &mut impl Write, mut value: u32) -> std::io::Result<()> {
42 loop {
43 let mut byte = (value & 0x7F) as u8;
44 value >>= 7;
45 if value != 0 {
46 byte |= 0x80; }
48 writer.write_all(&[byte])?;
49 if value == 0 {
50 break;
51 }
52 }
53 Ok(())
54}
55
56fn read_varint(data: &[u8]) -> Result<(u32, usize)> {
58 let mut value: u32 = 0;
59 let mut shift = 0;
60 let mut pos = 0;
61
62 loop {
63 if pos >= data.len() {
64 anyhow::bail!("Truncated varint");
65 }
66 let byte = data[pos];
67 pos += 1;
68
69 value |= ((byte & 0x7F) as u32) << shift;
70 if byte & 0x80 == 0 {
71 break;
72 }
73 shift += 7;
74 if shift >= 32 {
75 anyhow::bail!("Varint too large");
76 }
77 }
78
79 Ok((value, pos))
80}
81
82#[inline]
84pub(crate) fn skip_varint(data: &[u8]) -> Result<usize> {
85 let mut pos = 0;
86 loop {
87 if pos >= data.len() {
88 anyhow::bail!("Truncated varint");
89 }
90 let byte = data[pos];
91 pos += 1;
92 if byte & 0x80 == 0 {
93 return Ok(pos);
94 }
95 if pos >= 5 {
96 anyhow::bail!("Varint too large");
97 }
98 }
99}
100
101#[inline]
103fn read_u64(data: &[u8], off: usize) -> u64 {
104 u64::from_le_bytes(data[off..off + 8].try_into().expect("8 bytes"))
105}
106
107#[inline]
109fn read_u32(data: &[u8], off: usize) -> u32 {
110 u32::from_le_bytes(data[off..off + 4].try_into().expect("4 bytes"))
111}
112
113pub(crate) fn encode_posting_list(locations: &[FileLocation], out: &mut Vec<u8>) -> Result<()> {
126 let mut prev_file_id = 0u32;
127 let mut i = 0;
128 while i < locations.len() {
129 let file_id = locations[i].file_id;
130 let mut j = i + 1;
131 while j < locations.len() && locations[j].file_id == file_id {
132 j += 1;
133 }
134 let block = &locations[i..j];
135
136 write_varint(out, file_id.wrapping_sub(prev_file_id))?;
137 write_varint(out, (block.len() as u32) << 1)?; let mut prev_line = 0u32;
140 for loc in block {
141 write_varint(out, loc.line_no.wrapping_sub(prev_line))?;
142 prev_line = loc.line_no;
143 }
144
145 prev_file_id = file_id;
146 i = j;
147 }
148 Ok(())
149}
150
151pub(crate) fn decode_posting_list(bytes: &[u8]) -> Result<Vec<FileLocation>> {
153 decompress_posting_list(bytes, 0, bytes.len() as u32)
154}
155
156fn decompress_posting_list(mmap: &[u8], offset: u64, size: u32) -> Result<Vec<FileLocation>> {
166 let start = offset as usize;
167 let end = start + size as usize;
168
169 if end > mmap.len() {
170 anyhow::bail!(
171 "Posting list out of bounds: offset={}, size={}, mmap_len={}",
172 offset,
173 size,
174 mmap.len()
175 );
176 }
177
178 let compressed_data = &mmap[start..end];
179
180 let mut locations = Vec::with_capacity(compressed_data.len());
183 let mut cursor = PostingCursor::new(compressed_data)?;
184 while let Some(loc) = cursor.current() {
185 locations.push(loc);
186 cursor.advance()?;
187 }
188
189 Ok(locations)
190}
191
192pub(crate) struct PostingCursor<'a> {
200 data: &'a [u8],
202 pos: usize,
204 file_id: u32,
206 remaining: u32,
208 prev_line: u32,
210 cur: Option<FileLocation>,
212}
213
214impl<'a> PostingCursor<'a> {
215 pub(crate) fn new(data: &'a [u8]) -> Result<Self> {
217 let mut cursor = Self {
218 data,
219 pos: 0,
220 file_id: 0,
221 remaining: 0,
222 prev_line: 0,
223 cur: None,
224 };
225 cursor.advance()?;
226 Ok(cursor)
227 }
228
229 #[inline]
231 pub(crate) fn current(&self) -> Option<FileLocation> {
232 self.cur
233 }
234
235 fn read_block_header(&mut self) -> Result<()> {
237 let (file_delta, consumed) = read_varint(&self.data[self.pos..])?;
238 self.pos += consumed;
239 let (header, consumed) = read_varint(&self.data[self.pos..])?;
240 self.pos += consumed;
241
242 if header & 1 != 0 {
243 anyhow::bail!("unsupported block encoding (enc=1) in posting list");
244 }
245
246 self.file_id = self.file_id.wrapping_add(file_delta);
247 self.remaining = header >> 1;
248 self.prev_line = 0;
249 Ok(())
250 }
251
252 pub(crate) fn advance(&mut self) -> Result<Option<FileLocation>> {
254 while self.remaining == 0 {
256 if self.pos >= self.data.len() {
257 self.cur = None;
258 return Ok(None);
259 }
260 self.read_block_header()?;
261 }
262
263 let (line_delta, consumed) = read_varint(&self.data[self.pos..])?;
264 self.pos += consumed;
265 self.remaining -= 1;
266
267 let line_no = self.prev_line.wrapping_add(line_delta);
268 self.prev_line = line_no;
269 let loc = FileLocation::new(self.file_id, line_no);
270 self.cur = Some(loc);
271 Ok(self.cur)
272 }
273
274 pub(crate) fn seek(&mut self, target: (u32, u32)) -> Result<Option<FileLocation>> {
279 while let Some(loc) = self.cur {
280 if key(&loc) >= target {
281 break;
282 }
283 if loc.file_id < target.0 {
284 for _ in 0..self.remaining {
285 self.pos += skip_varint(&self.data[self.pos..])?;
286 }
287 self.remaining = 0;
288 }
289 self.advance()?;
290 }
291 Ok(self.cur)
292 }
293}
294
295fn intersect_with_cursor(
300 cands: &[FileLocation],
301 cur: &mut PostingCursor,
302) -> Result<Vec<FileLocation>> {
303 let mut out = Vec::new();
304 for cand in cands {
305 let k = key(cand);
306 match cur.seek(k)? {
307 Some(loc) if key(&loc) == k => out.push(*cand),
308 Some(_) => {}
309 None => break,
310 }
311 }
312 Ok(out)
313}
314
315fn mark_with_cursor(
321 cands: &[FileLocation],
322 cur: &mut PostingCursor,
323 keep: &mut [bool],
324) -> Result<()> {
325 for (i, cand) in cands.iter().enumerate() {
326 if keep[i] {
327 continue;
328 }
329 let k = key(cand);
330 match cur.seek(k)? {
331 Some(loc) if key(&loc) == k => keep[i] = true,
332 Some(_) => {}
333 None => break,
334 }
335 }
336 Ok(())
337}
338
339#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
342pub struct FileLocation {
343 pub file_id: u32,
345 pub line_no: u32,
347}
348
349impl FileLocation {
350 pub fn new(file_id: u32, line_no: u32) -> Self {
351 Self { file_id, line_no }
352 }
353}
354
355const SKIP_BYTES_PER_CANDIDATE: usize = 2;
367
368#[inline]
370pub(crate) fn varint_len(v: u32) -> u32 {
371 match v {
372 0..=0x7F => 1,
373 0x80..=0x3FFF => 2,
374 0x4000..=0x1F_FFFF => 3,
375 0x20_0000..=0xFFF_FFFF => 4,
376 _ => 5,
377 }
378}
379
380pub(crate) fn block_plan_size(lines: impl IntoIterator<Item = u32>) -> u32 {
384 let mut n = 0u32;
385 let mut size = 0u32;
386 let mut prev = 0u32;
387 for line in lines {
388 size += varint_len(line.wrapping_sub(prev));
389 prev = line;
390 n += 1;
391 }
392 1 + varint_len(n << 1) + size
393}
394
395pub(crate) fn plan_size(locations: &[FileLocation]) -> u32 {
403 let mut total = 0u32;
404 let mut i = 0;
405 while i < locations.len() {
406 let file_id = locations[i].file_id;
407 let mut j = i + 1;
408 while j < locations.len() && locations[j].file_id == file_id {
409 j += 1;
410 }
411 total += block_plan_size(locations[i..j].iter().map(|l| l.line_no));
412 i = j;
413 }
414 total
415}
416
417const PLAN_MAGIC: &[u8; 4] = b"RFPL";
418const PLAN_VERSION: u32 = 1;
419const PLAN_HEADER: usize = 16;
420
421pub(crate) struct PlanSizes {
424 mmap: memmap2::Mmap,
425 count: usize,
426}
427
428impl PlanSizes {
429 fn load(path: &Path) -> Result<Self> {
430 let file =
431 File::open(path).with_context(|| format!("Failed to open {}", path.display()))?;
432 let mmap = unsafe {
433 memmap2::Mmap::map(&file)
434 .with_context(|| format!("Failed to mmap {}", path.display()))?
435 };
436 if mmap.len() < PLAN_HEADER || &mmap[0..4] != PLAN_MAGIC {
437 anyhow::bail!("{} is not a planning-size file", path.display());
438 }
439 if read_u32(&mmap, 4) != PLAN_VERSION {
440 anyhow::bail!("{} has an unsupported version", path.display());
441 }
442 let count = read_u64(&mmap, 8) as usize;
443 if mmap.len() != PLAN_HEADER + count * 4 {
444 anyhow::bail!("{} is truncated", path.display());
445 }
446 Ok(Self { mmap, count })
447 }
448
449 fn len(&self) -> usize {
450 self.count
451 }
452
453 #[inline]
454 fn get(&self, index: usize) -> u32 {
455 read_u32(&self.mmap, PLAN_HEADER + index * 4)
456 }
457}
458
459pub(crate) fn write_plan_file(path: &Path, sizes: &[u32]) -> Result<()> {
461 let tmp = crate::atomic_write::tmp_path_for(path);
462 {
463 let mut w = std::io::BufWriter::new(
464 File::create(&tmp).with_context(|| format!("Failed to create {}", tmp.display()))?,
465 );
466 w.write_all(PLAN_MAGIC)?;
467 w.write_all(&PLAN_VERSION.to_le_bytes())?;
468 w.write_all(&(sizes.len() as u64).to_le_bytes())?;
469 for size in sizes {
470 w.write_all(&size.to_le_bytes())?;
471 }
472 w.flush()?;
473 w.get_ref().sync_all()?;
474 }
475 crate::atomic_write::atomic_replace(&tmp, path)
476 .with_context(|| format!("Failed to move {} into place", path.display()))
477}
478
479pub(crate) type DeadIds = [u64];
481
482#[inline]
483fn is_dead(dead: Option<&DeadIds>, id: u32) -> bool {
484 dead.is_some_and(|bits| {
485 bits.get((id / 64) as usize)
486 .is_some_and(|w| w & (1u64 << (id % 64)) != 0)
487 })
488}
489
490#[derive(Clone, Copy)]
492pub(crate) struct ListPart<'a> {
493 pub data: &'a [u8],
495 pub id_offset: u32,
497 pub dead: Option<&'a DeadIds>,
499}
500
501pub(crate) struct TrigramList<'a> {
503 pub trigram: Trigram,
504 pub plan: u64,
506 pub parts: Vec<ListPart<'a>>,
508}
509
510fn decode_list(list: &TrigramList) -> Result<Vec<FileLocation>> {
512 let mut out = Vec::new();
513 for part in &list.parts {
514 let mut cursor = PostingCursor::new(part.data)?;
515 while let Some(loc) = cursor.current() {
516 let id = loc.file_id + part.id_offset;
517 if !is_dead(part.dead, id) {
518 out.push(FileLocation::new(id, loc.line_no));
519 }
520 cursor.advance()?;
521 }
522 }
523 Ok(out)
524}
525
526fn part_range(cands: &[FileLocation], parts: &[ListPart], k: usize) -> std::ops::Range<usize> {
528 let lo = cands.partition_point(|c| c.file_id < parts[k].id_offset);
529 let hi = match parts.get(k + 1) {
530 Some(next) => cands.partition_point(|c| c.file_id < next.id_offset),
531 None => cands.len(),
532 };
533 lo..hi
534}
535
536fn to_local(cands: &[FileLocation], offset: u32) -> Vec<FileLocation> {
538 cands
539 .iter()
540 .map(|c| FileLocation::new(c.file_id - offset, c.line_no))
541 .collect()
542}
543
544fn intersect_list(cands: &[FileLocation], list: &TrigramList) -> Result<Vec<FileLocation>> {
546 if let [part] = list.parts.as_slice()
547 && part.id_offset == 0
548 {
549 let mut cursor = PostingCursor::new(part.data)?;
550 return intersect_with_cursor(cands, &mut cursor);
551 }
552 let mut out = Vec::new();
553 for (k, part) in list.parts.iter().enumerate() {
554 let range = part_range(cands, &list.parts, k);
555 let local = to_local(&cands[range], part.id_offset);
556 let mut cursor = PostingCursor::new(part.data)?;
557 for hit in intersect_with_cursor(&local, &mut cursor)? {
558 out.push(FileLocation::new(hit.file_id + part.id_offset, hit.line_no));
559 }
560 }
561 Ok(out)
562}
563
564fn mark_list(cands: &[FileLocation], list: &TrigramList, keep: &mut [bool]) -> Result<()> {
566 for (k, part) in list.parts.iter().enumerate() {
567 let range = part_range(cands, &list.parts, k);
568 let mut cursor = PostingCursor::new(part.data)?;
569 if part.id_offset == 0 {
570 mark_with_cursor(&cands[range.clone()], &mut cursor, &mut keep[range])?;
571 } else {
572 let local = to_local(&cands[range.clone()], part.id_offset);
573 mark_with_cursor(&local, &mut cursor, &mut keep[range])?;
574 }
575 }
576 Ok(())
577}
578
579pub(crate) fn plan_intersection(
583 lists: Vec<Option<TrigramList>>,
584 allow_skip: bool,
585) -> Vec<FileLocation> {
586 let mut lists: Vec<TrigramList> = match lists.into_iter().collect::<Option<Vec<_>>>() {
588 Some(l) => l,
589 None => return vec![],
590 };
591 if lists.is_empty() || lists.iter().any(|l| l.plan == 0) {
592 return vec![];
593 }
594
595 lists.sort_by_key(|l| l.plan);
597
598 let mut cands = match decode_list(&lists[0]) {
599 Ok(locations) => locations,
600 Err(e) => {
601 log::warn!(
602 "Failed to decompress posting list for trigram {}: {}",
603 lists[0].trigram,
604 e
605 );
606 return vec![];
607 }
608 };
609 cands.dedup_by_key(|l| key(l));
610
611 for list in &lists[1..] {
613 if cands.is_empty() {
614 break;
615 }
616 if allow_skip && list.plan as usize > cands.len().saturating_mul(SKIP_BYTES_PER_CANDIDATE) {
619 log::debug!(
620 "Intersection stopped early: {} candidates, next list {} bytes",
621 cands.len(),
622 list.plan
623 );
624 break;
625 }
626 match intersect_list(&cands, list) {
627 Ok(next) => cands = next,
628 Err(e) => {
629 log::warn!(
630 "Failed to decompress posting list for trigram {}: {}",
631 list.trigram,
632 e
633 );
634 return vec![];
635 }
636 }
637 }
638 cands
639}
640
641pub(crate) fn plan_fold_intersection(windows: Vec<Vec<TrigramList>>) -> Vec<FileLocation> {
644 let mut ws: Vec<(u64, Vec<TrigramList>)> = Vec::with_capacity(windows.len());
646 for variants in windows {
647 let live: Vec<TrigramList> = variants.into_iter().filter(|l| l.plan > 0).collect();
648 if live.is_empty() {
649 return vec![];
650 }
651 let weight = live.iter().map(|l| l.plan).sum();
652 ws.push((weight, live));
653 }
654 if ws.is_empty() {
655 return vec![];
656 }
657 ws.sort_by_key(|w| w.0);
658 let t_lookup = std::time::Instant::now();
659
660 let mut cands: Vec<FileLocation> = Vec::new();
662 for list in &ws[0].1 {
663 match decode_list(list) {
664 Ok(l) => cands.extend(l),
665 Err(e) => {
666 log::warn!(
667 "Failed to decompress posting list for trigram {}: {}",
668 list.trigram,
669 e
670 );
671 return vec![];
672 }
673 }
674 }
675 let t_decode = t_lookup.elapsed();
676 let raw = cands.len();
677 cands.sort_unstable();
678 cands.dedup_by_key(|l| key(l));
679 log::debug!(
680 "Fold first window: {} variants, {} bytes, {} raw postings -> {} keys; decode {:?}, sort+dedup {:?}",
681 ws[0].1.len(),
682 ws[0].0,
683 raw,
684 cands.len(),
685 t_decode,
686 t_lookup.elapsed() - t_decode
687 );
688
689 for (weight, lists) in &ws[1..] {
690 if cands.is_empty() {
691 break;
692 }
693 let cost = (*weight as usize).saturating_add(lists.len().saturating_mul(cands.len()));
698 if cost > cands.len().saturating_mul(SKIP_BYTES_PER_CANDIDATE) {
699 log::debug!(
700 "Fold intersection stopped early: {} candidates, next window {} bytes x {} variants",
701 cands.len(),
702 weight,
703 lists.len()
704 );
705 break;
706 }
707 let mut keep = vec![false; cands.len()];
708 let mut window_ok = true;
709 for list in lists {
710 if let Err(e) = mark_list(&cands, list, &mut keep) {
711 log::warn!(
713 "Failed to read posting list for trigram {}: {}; window skipped",
714 list.trigram,
715 e
716 );
717 window_ok = false;
718 break;
719 }
720 }
721 if !window_ok {
722 continue;
723 }
724 cands = cands
725 .iter()
726 .zip(&keep)
727 .filter(|(_, k)| **k)
728 .map(|(c, _)| *c)
729 .collect();
730 }
731 cands
732}
733
734pub(crate) fn single_list(trigram: Trigram, part: ListPart<'_>, plan: u64) -> TrigramList<'_> {
736 TrigramList {
737 trigram,
738 plan,
739 parts: vec![part],
740 }
741}
742
743pub(crate) fn pattern_trigrams(pattern: &str) -> Vec<Trigram> {
746 if pattern.len() < 3 {
747 return vec![];
749 }
750 let mut trigrams = extract_trigrams(pattern);
751 trigrams.sort_unstable();
753 trigrams.dedup();
754 trigrams
755}
756
757pub(crate) fn fold_windows(literal: &[u8]) -> Option<Vec<Vec<Trigram>>> {
760 if literal.len() < 3 || !literal.is_ascii() {
761 return None;
762 }
763 let mut windows: Vec<Vec<Trigram>> = literal.windows(3).map(case_variants).collect();
765 windows.sort_unstable();
766 windows.dedup();
767 Some(windows)
768}
769
770pub(crate) const EXOTIC_LONG_S_RANGE: (Trigram, Trigram) = (0xC5_BF_00, 0xC5_BF_FF);
774pub(crate) fn exotic_singles() -> impl Iterator<Item = Trigram> {
775 const KELVIN: Trigram = 0xE2_84_AA;
776 std::iter::once(KELVIN).chain((0u32..=0xFF).map(|first| first << 16 | 0xC5_BF))
777}
778
779pub(crate) fn union_lists(lists: &[TrigramList]) -> Vec<FileLocation> {
781 let mut out = Vec::new();
782 for list in lists {
783 match decode_list(list) {
784 Ok(l) => out.extend(l),
785 Err(e) => log::warn!(
786 "Failed to decompress posting list for trigram {}: {}",
787 list.trigram,
788 e
789 ),
790 }
791 }
792 out.sort_unstable();
793 out.dedup_by_key(|l| key(l));
794 out
795}
796
797#[derive(Debug, Clone)]
798struct DirectoryEntry {
799 index: usize,
801 trigram: Trigram,
803 data_offset: u64,
805 compressed_size: u32,
807}
808
809pub struct TrigramIndex {
820 index: Vec<(Trigram, Vec<FileLocation>)>,
823 files: Vec<PathBuf>,
827 num_files: usize,
829 paths_offset: usize,
831 lazy_paths: std::sync::OnceLock<Vec<PathBuf>>,
833 temp_index: Option<HashMap<Trigram, Vec<FileLocation>>>,
835 mmap: Option<memmap2::Mmap>,
837 num_trigrams: usize,
840 max_posting_list_entries: usize,
843 plan: Option<PlanSizes>,
846}
847
848impl TrigramIndex {
849 pub fn new() -> Self {
851 Self {
852 index: Vec::new(),
853 files: Vec::new(),
854 num_files: 0,
855 paths_offset: 0,
856 lazy_paths: std::sync::OnceLock::new(),
857 temp_index: Some(HashMap::new()),
858 mmap: None,
859 num_trigrams: 0,
860 max_posting_list_entries: 0,
861 plan: None,
862 }
863 }
864
865 pub fn set_max_posting_list_entries(&mut self, cap: usize) {
867 self.max_posting_list_entries = cap;
868 }
869
870 pub fn add_file(&mut self, path: PathBuf) -> u32 {
872 let file_id = self.files.len() as u32;
873 self.files.push(path);
874 file_id
875 }
876
877 pub fn get_file(&self, file_id: u32) -> Option<&PathBuf> {
879 match &self.mmap {
880 None => self.files.get(file_id as usize),
881 Some(mmap) => self
882 .lazy_paths
883 .get_or_init(|| {
884 let mut out = Vec::with_capacity(self.num_files);
885 let mut pos = self.paths_offset;
886 for _ in 0..self.num_files {
887 let Ok((len, consumed)) = read_varint(&mmap[pos..]) else {
888 break;
889 };
890 pos += consumed;
891 let end = pos + len as usize;
892 let Some(bytes) = mmap.get(pos..end) else {
893 break;
894 };
895 out.push(PathBuf::from(String::from_utf8_lossy(bytes).into_owned()));
896 pos = end;
897 }
898 out
899 })
900 .get(file_id as usize),
901 }
902 }
903
904 pub fn file_count(&self) -> usize {
906 if self.mmap.is_some() {
907 self.num_files
908 } else {
909 self.files.len()
910 }
911 }
912
913 pub fn trigram_count(&self) -> usize {
915 if self.mmap.is_some() {
916 self.num_trigrams
918 } else {
919 self.index.len()
921 }
922 }
923
924 fn find_entry(&self, trigram: Trigram) -> Option<DirectoryEntry> {
930 let mmap = self.mmap.as_ref()?;
931 let (mut lo, mut hi) = (0usize, self.num_trigrams);
932 while lo < hi {
933 let mid = lo + (hi - lo) / 2;
934 let off = HEADER_SIZE + mid * DIR_ENTRY_SIZE;
935 match read_u32(mmap, off).cmp(&trigram) {
936 std::cmp::Ordering::Less => lo = mid + 1,
937 std::cmp::Ordering::Greater => hi = mid,
938 std::cmp::Ordering::Equal => {
939 return Some(DirectoryEntry {
940 index: mid,
941 trigram,
942 data_offset: read_u64(mmap, off + 4),
943 compressed_size: read_u32(mmap, off + 12),
944 });
945 }
946 }
947 }
948 None
949 }
950
951 pub fn index_file(&mut self, file_id: u32, content: &str) {
956 let trigrams = extract_trigrams_with_locations(content, file_id);
957
958 if let Some(ref mut temp_map) = self.temp_index {
960 for (trigram, location) in trigrams {
961 temp_map
962 .entry(trigram)
963 .or_insert_with(Vec::new)
964 .push(location);
965 }
966 } else {
967 panic!("Cannot call index_file() after finalize(). Index is read-only.");
968 }
969 }
970
971 pub fn build_from_trigrams(&mut self, trigrams: Vec<(Trigram, FileLocation)>) {
976 let mut temp_map: HashMap<Trigram, Vec<FileLocation>> = HashMap::new();
977
978 for (trigram, location) in trigrams {
980 temp_map.entry(trigram).or_default().push(location);
981 }
982
983 self.index = temp_map.into_iter().collect();
985
986 self.temp_index = None;
988
989 self.finalize();
991 }
992
993 pub fn finalize(&mut self) {
1001 if let Some(temp_map) = self.temp_index.take() {
1004 self.index = temp_map.into_iter().collect();
1005 }
1006
1007 let cap = self.max_posting_list_entries;
1009 for (trigram, list) in self.index.iter_mut() {
1010 list.sort_unstable();
1011 list.dedup(); if cap > 0 && list.len() > cap {
1013 log::warn!(
1014 "Trigram 0x{:06X} posting list has {} entries (cap {}); truncating.",
1015 trigram,
1016 list.len(),
1017 cap
1018 );
1019 list.truncate(cap);
1020 }
1021 }
1022
1023 self.index.sort_unstable_by_key(|(trigram, _)| *trigram);
1025 }
1026
1027 pub fn search(&self, pattern: &str) -> Vec<FileLocation> {
1035 self.search_impl(pattern, false)
1036 }
1037
1038 pub fn search_candidates(&self, pattern: &str) -> Vec<FileLocation> {
1049 self.search_impl(pattern, true)
1050 }
1051
1052 fn search_impl(&self, pattern: &str, allow_skip: bool) -> Vec<FileLocation> {
1053 let trigrams = pattern_trigrams(pattern);
1054 if trigrams.is_empty() {
1055 return vec![];
1056 }
1057
1058 if self.mmap.is_some() {
1060 let lists = trigrams
1063 .iter()
1064 .map(|&t| {
1065 self.list_part(t).map(|(part, plan)| TrigramList {
1066 trigram: t,
1067 plan,
1068 parts: vec![part],
1069 })
1070 })
1071 .collect();
1072 plan_intersection(lists, allow_skip)
1073 } else {
1074 let mut posting_lists: Vec<&[FileLocation]> = Vec::with_capacity(trigrams.len());
1076 for trigram in &trigrams {
1077 match self.index.binary_search_by_key(trigram, |(t, _)| *t) {
1078 Ok(idx) => posting_lists.push(&self.index[idx].1),
1079 Err(_) => return vec![],
1081 }
1082 }
1083
1084 posting_lists.sort_by_key(|list| list.len());
1086
1087 if !allow_skip {
1088 return intersect_sorted(&posting_lists);
1089 }
1090 let mut cands: Vec<FileLocation> = posting_lists[0].to_vec();
1091 cands.dedup_by_key(|l| key(l));
1092 for list in &posting_lists[1..] {
1093 if cands.is_empty() {
1094 break;
1095 }
1096 if list.len().saturating_mul(13) / 10
1098 > cands.len().saturating_mul(SKIP_BYTES_PER_CANDIDATE)
1099 {
1100 break;
1101 }
1102 cands = intersect_two(&cands, list);
1103 }
1104 cands
1105 }
1106 }
1107
1108 pub fn search_candidates_fold(&self, literal: &[u8]) -> Vec<FileLocation> {
1124 let Some(windows) = fold_windows(literal) else {
1125 return vec![];
1126 };
1127
1128 if self.mmap.is_some() {
1129 let lists = windows
1132 .iter()
1133 .map(|variants| {
1134 variants
1135 .iter()
1136 .filter_map(|&t| {
1137 self.list_part(t).map(|(part, plan)| TrigramList {
1138 trigram: t,
1139 plan,
1140 parts: vec![part],
1141 })
1142 })
1143 .collect()
1144 })
1145 .collect();
1146 plan_fold_intersection(lists)
1147 } else {
1148 let mut ws: Vec<(usize, Vec<&[FileLocation]>)> = Vec::with_capacity(windows.len());
1149 for variants in &windows {
1150 let lists: Vec<&[FileLocation]> = variants
1151 .iter()
1152 .filter_map(|t| {
1153 self.index
1154 .binary_search_by_key(t, |(x, _)| *x)
1155 .ok()
1156 .map(|i| self.index[i].1.as_slice())
1157 })
1158 .collect();
1159 if lists.is_empty() {
1160 return vec![];
1161 }
1162 let weight = lists.iter().map(|l| l.len()).sum::<usize>() * 13 / 10;
1164 ws.push((weight, lists));
1165 }
1166 ws.sort_by_key(|w| w.0);
1167
1168 let mut cands: Vec<FileLocation> =
1169 ws[0].1.iter().flat_map(|l| l.iter().copied()).collect();
1170 cands.sort_unstable();
1171 cands.dedup_by_key(|l| key(l));
1172
1173 for (weight, lists) in &ws[1..] {
1174 if cands.is_empty() {
1175 break;
1176 }
1177 let cost = weight.saturating_add(lists.len().saturating_mul(cands.len()));
1178 if cost > cands.len().saturating_mul(SKIP_BYTES_PER_CANDIDATE) {
1179 break;
1180 }
1181 let mut next: Vec<FileLocation> = lists
1182 .iter()
1183 .flat_map(|l| intersect_two(&cands, l))
1184 .collect();
1185 next.sort_unstable();
1186 next.dedup_by_key(|l| key(l));
1187 cands = next;
1188 }
1189 cands
1190 }
1191 }
1192
1193 pub fn exotic_fold_lines(&self) -> Vec<FileLocation> {
1204 let (long_s_lo, long_s_hi) = EXOTIC_LONG_S_RANGE;
1205
1206 let mut out: Vec<FileLocation> = Vec::new();
1207 if self.mmap.is_some() {
1208 let mut lists: Vec<TrigramList> = Vec::new();
1209 lists.extend(
1210 self.list_parts_in(long_s_lo, long_s_hi)
1211 .into_iter()
1212 .map(|(t, part, plan)| single_list(t, part, plan)),
1213 );
1214 for t in exotic_singles() {
1215 lists.extend(self.list_part(t).map(|(p, plan)| single_list(t, p, plan)));
1216 }
1217 out = union_lists(&lists);
1218 } else {
1219 let lo = self.index.partition_point(|(t, _)| *t < long_s_lo);
1220 let hi = self.index.partition_point(|(t, _)| *t <= long_s_hi);
1221 for (_, list) in &self.index[lo..hi] {
1222 out.extend(list.iter().copied());
1223 }
1224 for t in exotic_singles() {
1225 if let Ok(i) = self.index.binary_search_by_key(&t, |(x, _)| *x) {
1226 out.extend(self.index[i].1.iter().copied());
1227 }
1228 }
1229 }
1230 out.sort_unstable();
1231 out.dedup_by_key(|l| key(l));
1232 out
1233 }
1234
1235 fn dir_range(&self, lo: Trigram, hi: Trigram) -> Vec<DirectoryEntry> {
1237 let Some(mmap) = self.mmap.as_ref() else {
1238 return vec![];
1239 };
1240 let at = |i: usize| read_u32(mmap, HEADER_SIZE + i * DIR_ENTRY_SIZE);
1241 let (mut l, mut h) = (0usize, self.num_trigrams);
1242 while l < h {
1243 let mid = l + (h - l) / 2;
1244 if at(mid) < lo {
1245 l = mid + 1;
1246 } else {
1247 h = mid;
1248 }
1249 }
1250 let mut out = Vec::new();
1251 let mut i = l;
1252 while i < self.num_trigrams {
1253 let off = HEADER_SIZE + i * DIR_ENTRY_SIZE;
1254 let trigram = read_u32(mmap, off);
1255 if trigram > hi {
1256 break;
1257 }
1258 out.push(DirectoryEntry {
1259 index: i,
1260 trigram,
1261 data_offset: read_u64(mmap, off + 4),
1262 compressed_size: read_u32(mmap, off + 12),
1263 });
1264 i += 1;
1265 }
1266 out
1267 }
1268
1269 pub fn search_files(&self, pattern: &str) -> Vec<u32> {
1274 let mut files: Vec<u32> = self
1275 .search(pattern)
1276 .into_iter()
1277 .map(|l| l.file_id)
1278 .collect();
1279 files.dedup();
1281 files
1282 }
1283
1284 pub fn get_posting_list(&self, trigram: Trigram) -> Option<&Vec<FileLocation>> {
1286 self.index
1287 .binary_search_by_key(&trigram, |(t, _)| *t)
1288 .ok()
1289 .map(|idx| &self.index[idx].1)
1290 }
1291
1292 pub fn write(&mut self, path: impl AsRef<Path>) -> Result<()> {
1306 let path = path.as_ref();
1307
1308 let tmp_path = crate::atomic_write::tmp_path_for(path);
1313 let file = OpenOptions::new()
1314 .create(true)
1315 .write(true)
1316 .truncate(true)
1317 .open(&tmp_path)
1318 .with_context(|| format!("Failed to create {}", tmp_path.display()))?;
1319
1320 let mut writer = std::io::BufWriter::with_capacity(16 * 1024 * 1024, file);
1322
1323 let data_start = (HEADER_SIZE + self.index.len() * DIR_ENTRY_SIZE) as u64;
1326 let mut current_offset = data_start;
1327 let mut directory: Vec<DirectoryEntry> = Vec::with_capacity(self.index.len());
1328 let mut compressed_lists: Vec<Vec<u8>> = Vec::with_capacity(self.index.len());
1329
1330 for (trigram, locations) in &self.index {
1331 let mut compressed = Vec::with_capacity(locations.len() + 16);
1332 encode_posting_list(locations, &mut compressed)?;
1333
1334 directory.push(DirectoryEntry {
1335 index: directory.len(),
1336 trigram: *trigram,
1337 data_offset: current_offset,
1338 compressed_size: compressed.len() as u32,
1339 });
1340 current_offset += compressed.len() as u64;
1341 compressed_lists.push(compressed);
1342 }
1343 let paths_offset = current_offset;
1344
1345 writer.write_all(MAGIC)?;
1347 writer.write_all(&VERSION.to_le_bytes())?;
1348 writer.write_all(&(self.index.len() as u64).to_le_bytes())?; writer.write_all(&(self.files.len() as u64).to_le_bytes())?; writer.write_all(&paths_offset.to_le_bytes())?; for entry in &directory {
1354 writer.write_all(&entry.trigram.to_le_bytes())?;
1355 writer.write_all(&entry.data_offset.to_le_bytes())?;
1356 writer.write_all(&entry.compressed_size.to_le_bytes())?;
1357 }
1358
1359 for compressed in &compressed_lists {
1361 writer.write_all(compressed)?;
1362 }
1363
1364 for file_path in &self.files {
1366 let path_str = file_path.to_string_lossy();
1367 let path_bytes = path_str.as_bytes();
1368 write_varint(&mut writer, path_bytes.len() as u32)?;
1369 writer.write_all(path_bytes)?;
1370 }
1371
1372 writer.flush()?;
1374 writer.get_ref().sync_all()?;
1375 drop(writer);
1376 crate::atomic_write::atomic_replace(&tmp_path, path)
1377 .with_context(|| format!("Failed to move {} into place", path.display()))?;
1378
1379 log::info!(
1380 "Wrote lazy-loadable trigram index: {} trigrams, {} files to {:?}",
1381 self.index.len(),
1382 self.files.len(),
1383 path
1384 );
1385
1386 Ok(())
1387 }
1388
1389 pub fn load(path: impl AsRef<Path>) -> Result<Self> {
1396 let path = path.as_ref();
1397
1398 let file =
1399 File::open(path).with_context(|| format!("Failed to open {}", path.display()))?;
1400
1401 let mmap = unsafe {
1403 memmap2::Mmap::map(&file)
1404 .with_context(|| format!("Failed to mmap {}", path.display()))?
1405 };
1406
1407 if mmap.len() < 8 {
1410 anyhow::bail!(
1411 "trigrams.bin too small (expected at least {} bytes)",
1412 HEADER_SIZE
1413 );
1414 }
1415
1416 if &mmap[0..4] != MAGIC {
1417 anyhow::bail!("Invalid trigrams.bin (wrong magic bytes)");
1418 }
1419
1420 let version = read_u32(&mmap, 4);
1421 if version != VERSION {
1422 anyhow::bail!(
1423 "Unsupported trigrams.bin version: {} (expected {}). Please re-index with 'reflex index'.",
1424 version,
1425 VERSION
1426 );
1427 }
1428
1429 if mmap.len() < HEADER_SIZE {
1430 anyhow::bail!(
1431 "trigrams.bin too small (expected at least {} bytes)",
1432 HEADER_SIZE
1433 );
1434 }
1435
1436 let num_trigrams = read_u64(&mmap, NUM_TRIGRAMS_OFFSET) as usize;
1437 let num_files = read_u64(&mmap, NUM_FILES_OFFSET) as usize;
1438 let paths_offset = read_u64(&mmap, PATHS_OFFSET_OFFSET);
1439
1440 log::debug!(
1441 "Loading lazy trigram index: {} trigrams, {} files",
1442 num_trigrams,
1443 num_files
1444 );
1445
1446 let directory_end = num_trigrams
1450 .checked_mul(DIR_ENTRY_SIZE)
1451 .and_then(|d| d.checked_add(HEADER_SIZE))
1452 .ok_or_else(|| anyhow::anyhow!("trigrams.bin directory size overflows"))?
1453 as u64;
1454 if directory_end > paths_offset || paths_offset > mmap.len() as u64 {
1455 anyhow::bail!(
1456 "trigrams.bin layout out of bounds: directory_end={}, paths_offset={}, len={}",
1457 directory_end,
1458 paths_offset,
1459 mmap.len()
1460 );
1461 }
1462
1463 let mut pos = paths_offset as usize;
1468 for _ in 0..num_files {
1469 let (path_len, consumed) = read_varint(&mmap[pos..])?;
1470 pos += consumed + path_len as usize;
1471 if pos > mmap.len() {
1472 anyhow::bail!("Truncated file path at pos={}", pos);
1473 }
1474 }
1475 let files = Vec::new();
1476
1477 log::info!(
1478 "Loaded lazy trigram index: {} trigrams, {} files (directory: {} KB, in mmap)",
1479 num_trigrams,
1480 num_files,
1481 num_trigrams * DIR_ENTRY_SIZE / 1024
1482 );
1483
1484 Ok(Self {
1485 index: Vec::new(), files,
1487 num_files,
1488 paths_offset: paths_offset as usize,
1489 lazy_paths: std::sync::OnceLock::new(),
1490 temp_index: None,
1491 mmap: Some(mmap), num_trigrams,
1493 max_posting_list_entries: 0,
1494 plan: None,
1495 })
1496 }
1497
1498 pub fn attach_plan(&mut self, path: impl AsRef<Path>) -> Result<()> {
1502 let plan = PlanSizes::load(path.as_ref())?;
1503 if plan.len() != self.num_trigrams {
1504 anyhow::bail!(
1505 "{} lists {} trigrams, the index {}",
1506 path.as_ref().display(),
1507 plan.len(),
1508 self.num_trigrams
1509 );
1510 }
1511 self.plan = Some(plan);
1512 Ok(())
1513 }
1514
1515 pub fn has_plan(&self) -> bool {
1517 self.plan.is_some()
1518 }
1519
1520 pub(crate) fn trigrams(&self) -> impl Iterator<Item = Trigram> + '_ {
1522 let mmap = self.mmap.as_ref();
1523 (0..if mmap.is_some() { self.num_trigrams } else { 0 })
1524 .map(move |i| read_u32(mmap.expect("lazy"), HEADER_SIZE + i * DIR_ENTRY_SIZE))
1525 }
1526
1527 pub(crate) fn list_part(&self, trigram: Trigram) -> Option<(ListPart<'_>, u64)> {
1530 let entry = self.find_entry(trigram)?;
1531 self.part_of(&entry)
1532 }
1533
1534 pub(crate) fn list_parts_in(
1536 &self,
1537 lo: Trigram,
1538 hi: Trigram,
1539 ) -> Vec<(Trigram, ListPart<'_>, u64)> {
1540 self.dir_range(lo, hi)
1541 .into_iter()
1542 .filter_map(|e| self.part_of(&e).map(|(part, plan)| (e.trigram, part, plan)))
1543 .collect()
1544 }
1545
1546 fn part_of(&self, entry: &DirectoryEntry) -> Option<(ListPart<'_>, u64)> {
1547 let mmap = self.mmap.as_ref()?;
1548 let start = entry.data_offset as usize;
1549 let end = start + entry.compressed_size as usize;
1550 if end > mmap.len() {
1551 log::warn!(
1552 "Posting list out of bounds for trigram {}: offset={}, size={}, mmap_len={}",
1553 entry.trigram,
1554 entry.data_offset,
1555 entry.compressed_size,
1556 mmap.len()
1557 );
1558 return None;
1559 }
1560 let plan = match &self.plan {
1561 Some(p) => p.get(entry.index) as u64,
1562 None => entry.compressed_size as u64,
1563 };
1564 Some((
1565 ListPart {
1566 data: &mmap[start..end],
1567 id_offset: 0,
1568 dead: None,
1569 },
1570 plan,
1571 ))
1572 }
1573}
1574
1575impl Default for TrigramIndex {
1576 fn default() -> Self {
1577 Self::new()
1578 }
1579}
1580
1581pub fn extract_trigrams(text: &str) -> Vec<Trigram> {
1585 let bytes = text.as_bytes();
1586 let mut trigrams = Vec::new();
1587
1588 for i in 0..bytes.len().saturating_sub(2) {
1589 let trigram = bytes_to_trigram(&bytes[i..i + 3]);
1590 trigrams.push(trigram);
1591 }
1592
1593 trigrams
1594}
1595
1596pub fn extract_trigrams_with_locations(text: &str, file_id: u32) -> Vec<(Trigram, FileLocation)> {
1607 let mut result = Vec::with_capacity(text.len().saturating_sub(2));
1608 scan_line_trigrams(text, |line_no, trigrams| {
1609 let location = FileLocation::new(file_id, line_no);
1610 result.extend(trigrams.iter().map(|&t| (t, location)));
1611 });
1612 result
1613}
1614
1615pub(crate) fn scan_line_trigrams(text: &str, mut f: impl FnMut(u32, &[Trigram])) {
1623 let bytes = text.as_bytes();
1624 let mut line_trigrams: Vec<Trigram> = Vec::with_capacity(128);
1626 let mut line_no: u32 = 1;
1627
1628 for (i, &byte) in bytes.iter().enumerate() {
1629 if byte == b'\n' {
1631 line_trigrams.sort_unstable();
1632 line_trigrams.dedup();
1633 f(line_no, &line_trigrams);
1634 line_trigrams.clear();
1635 line_no += 1;
1636 }
1637
1638 if i + 2 < bytes.len() {
1640 line_trigrams.push(bytes_to_trigram(&bytes[i..i + 3]));
1641 }
1642 }
1643 line_trigrams.sort_unstable();
1644 line_trigrams.dedup();
1645 f(line_no, &line_trigrams);
1646}
1647
1648#[inline]
1650fn bytes_to_trigram(bytes: &[u8]) -> Trigram {
1651 debug_assert_eq!(bytes.len(), 3);
1652 (bytes[0] as u32) << 16 | (bytes[1] as u32) << 8 | (bytes[2] as u32)
1653}
1654
1655fn case_variants(window: &[u8]) -> Vec<Trigram> {
1660 debug_assert_eq!(window.len(), 3);
1661 let forms = |b: u8| -> Vec<u8> {
1662 if b.is_ascii_alphabetic() {
1663 vec![b.to_ascii_lowercase(), b.to_ascii_uppercase()]
1664 } else {
1665 vec![b]
1666 }
1667 };
1668 let mut out = Vec::with_capacity(8);
1669 for a in forms(window[0]) {
1670 for b in forms(window[1]) {
1671 for c in forms(window[2]) {
1672 out.push(bytes_to_trigram(&[a, b, c]));
1673 }
1674 }
1675 }
1676 out.sort_unstable();
1677 out.dedup();
1678 out
1679}
1680
1681#[allow(dead_code)]
1683fn trigram_to_bytes(trigram: Trigram) -> [u8; 3] {
1684 [
1685 ((trigram >> 16) & 0xFF) as u8,
1686 ((trigram >> 8) & 0xFF) as u8,
1687 (trigram & 0xFF) as u8,
1688 ]
1689}
1690
1691#[inline]
1693fn key(l: &FileLocation) -> (u32, u32) {
1694 (l.file_id, l.line_no)
1695}
1696
1697fn intersect_two(a: &[FileLocation], b: &[FileLocation]) -> Vec<FileLocation> {
1705 let mut out = Vec::with_capacity(a.len().min(b.len()));
1706 let gallop = b.len() > 8 * a.len();
1707 let (mut i, mut j) = (0, 0);
1708
1709 while i < a.len() && j < b.len() {
1710 let ka = key(&a[i]);
1711 match key(&b[j]).cmp(&ka) {
1712 std::cmp::Ordering::Less => {
1713 if gallop {
1714 j += b[j..].partition_point(|x| key(x) < ka);
1715 } else {
1716 j += 1;
1717 }
1718 }
1719 std::cmp::Ordering::Greater => i += 1,
1720 std::cmp::Ordering::Equal => {
1721 out.push(a[i]);
1722 i += 1;
1723 j += 1;
1725 while j < b.len() && key(&b[j]) == ka {
1726 j += 1;
1727 }
1728 }
1729 }
1730 }
1731
1732 out
1733}
1734
1735pub(crate) fn intersect_sorted(lists: &[&[FileLocation]]) -> Vec<FileLocation> {
1742 let Some((first, rest)) = lists.split_first() else {
1743 return vec![];
1744 };
1745
1746 let mut cands = first.to_vec();
1747 cands.dedup_by_key(|l| key(l));
1748
1749 for list in rest {
1750 if cands.is_empty() {
1751 break;
1752 }
1753 cands = intersect_two(&cands, list);
1754 }
1755
1756 cands
1757}
1758
1759#[cfg(test)]
1760mod tests {
1761 use super::*;
1762
1763 #[test]
1767 fn search_candidates_is_a_superset_of_search() {
1768 let mut index = TrigramIndex::new();
1769 for f in 0..20u32 {
1771 let id = index.add_file(PathBuf::from(format!("f{f}.rs")));
1772 let mut text = String::new();
1773 for i in 0..200 {
1774 text.push_str(&format!("let ident_{} = ident_{}; // filler\n", i, i + 1));
1775 }
1776 text.push_str("let ident_7 = 1;\n");
1777 index.index_file(id, &text);
1778 }
1779 index.finalize();
1780
1781 let exact = index.search("ident_7");
1782 let cands = index.search_candidates("ident_7");
1783 assert!(!exact.is_empty());
1784 let exact_keys: std::collections::HashSet<_> = exact.iter().map(key).collect();
1785 let cand_keys: std::collections::HashSet<_> = cands.iter().map(key).collect();
1786 assert!(
1787 exact_keys.is_subset(&cand_keys),
1788 "candidates must cover every match"
1789 );
1790
1791 let dir = tempfile::tempdir().unwrap();
1793 let path = dir.path().join("trigrams.bin");
1794 index.write(&path).unwrap();
1795 let lazy = TrigramIndex::load(&path).unwrap();
1796 let lazy_exact: std::collections::HashSet<_> =
1797 lazy.search("ident_7").iter().map(key).collect();
1798 let lazy_cands: std::collections::HashSet<_> =
1799 lazy.search_candidates("ident_7").iter().map(key).collect();
1800 assert_eq!(lazy_exact, exact_keys);
1801 assert!(lazy_exact.is_subset(&lazy_cands));
1802 }
1803 #[test]
1807 fn search_candidates_fold_covers_case_insensitive_matches() {
1808 let mut index = TrigramIndex::new();
1809 let mut texts: Vec<String> = Vec::new();
1810 for f in 0..10u32 {
1811 let id = index.add_file(PathBuf::from(format!("f{f}.rs")));
1812 let mut text = String::new();
1813 for i in 0..100 {
1814 text.push_str(&format!("let ident_{} = other_{}; // filler\n", i, i + 1));
1815 }
1816 text.push_str("let RealmId = 1;\n");
1817 text.push_str("let realmId = 2;\n");
1818 text.push_str("let REALMID = 3;\n");
1819 text.push_str("let realm_id = 4;\n");
1820 text.push_str("let kelvin = 5;\n");
1821 text.push_str("let \u{212A}elvin = 6;\n");
1822 text.push_str("let \u{017F}tatus = 7;\n");
1823 text.push_str("let STATUS = 8;\n");
1824 index.index_file(id, &text);
1825 texts.push(text);
1826 }
1827 index.finalize();
1828
1829 let dir = tempfile::tempdir().unwrap();
1830 let path = dir.path().join("trigrams.bin");
1831 index.write(&path).unwrap();
1832 let lazy = TrigramIndex::load(&path).unwrap();
1833
1834 for literal in ["realmid", "kelvin", "status", "REALM_ID"] {
1835 let re = regex::Regex::new(&format!("(?i){}", literal)).unwrap();
1836 let mut expected = std::collections::HashSet::new();
1837 for (f, text) in texts.iter().enumerate() {
1838 for (i, line) in text.lines().enumerate() {
1839 if re.is_match(line) {
1840 expected.insert((f as u32, i as u32 + 1));
1841 }
1842 }
1843 }
1844 assert!(!expected.is_empty(), "{literal}");
1845 let has_ks = literal
1846 .bytes()
1847 .any(|b| matches!(b.to_ascii_lowercase(), b'k' | b's'));
1848
1849 for (name, idx) in [("memory", &index), ("lazy", &lazy)] {
1850 let mut cands: std::collections::HashSet<_> = idx
1851 .search_candidates_fold(literal.as_bytes())
1852 .iter()
1853 .map(key)
1854 .collect();
1855 if has_ks {
1856 cands.extend(idx.exotic_fold_lines().iter().map(key));
1857 }
1858 assert!(
1859 expected.is_subset(&cands),
1860 "{name}: fold candidates for {literal:?} miss {:?}",
1861 expected.difference(&cands).collect::<Vec<_>>()
1862 );
1863 }
1864 }
1865
1866 assert!(
1869 regex::Regex::new("(?i)kelvin")
1870 .unwrap()
1871 .is_match("\u{212A}elvin")
1872 );
1873 assert!(
1874 regex::Regex::new("(?i)status")
1875 .unwrap()
1876 .is_match("\u{017F}tatus")
1877 );
1878 let ascii_only: std::collections::HashSet<_> = lazy
1879 .search_candidates_fold(b"kelvin")
1880 .iter()
1881 .map(key)
1882 .collect();
1883 assert!(
1884 !ascii_only.contains(&(0, 106)),
1885 "line 106 is the Kelvin-sign line"
1886 );
1887
1888 assert_eq!(lazy.exotic_fold_lines().len(), 20);
1890 assert_eq!(index.exotic_fold_lines(), lazy.exotic_fold_lines());
1891
1892 assert!(lazy.search_candidates_fold(b"zzqx_absent").is_empty());
1894 assert!(lazy.search_candidates_fold("straße".as_bytes()).is_empty());
1896 }
1897
1898 use tempfile::TempDir;
1899
1900 #[test]
1901 fn test_extract_trigrams() {
1902 let text = "hello";
1903 let trigrams = extract_trigrams(text);
1904
1905 assert_eq!(trigrams.len(), 3);
1907
1908 let expected = vec![
1910 bytes_to_trigram(b"hel"),
1911 bytes_to_trigram(b"ell"),
1912 bytes_to_trigram(b"llo"),
1913 ];
1914 assert_eq!(trigrams, expected);
1915 }
1916
1917 #[test]
1918 fn test_extract_trigrams_short() {
1919 assert_eq!(extract_trigrams("ab").len(), 0);
1920 assert_eq!(extract_trigrams("abc").len(), 1);
1921 }
1922
1923 #[test]
1924 fn test_bytes_to_trigram() {
1925 let trigram1 = bytes_to_trigram(b"abc");
1926 let trigram2 = bytes_to_trigram(b"abc");
1927 let trigram3 = bytes_to_trigram(b"xyz");
1928
1929 assert_eq!(trigram1, trigram2);
1930 assert_ne!(trigram1, trigram3);
1931 }
1932
1933 #[test]
1934 fn test_trigram_roundtrip() {
1935 let original = b"foo";
1936 let trigram = bytes_to_trigram(original);
1937 let recovered = trigram_to_bytes(trigram);
1938 assert_eq!(original, &recovered);
1939 }
1940
1941 #[test]
1942 fn test_extract_with_locations() {
1943 let text = "hello\nworld";
1944 let locs = extract_trigrams_with_locations(text, 0);
1945
1946 assert_eq!(locs.len(), 9);
1950 assert_eq!(locs.iter().filter(|(_, l)| l.line_no == 1).count(), 5);
1951 assert_eq!(locs.iter().filter(|(_, l)| l.line_no == 2).count(), 4);
1952 assert!(locs.iter().all(|(_, l)| l.file_id == 0));
1953
1954 let line_of = |t: &[u8; 3]| {
1955 locs.iter()
1956 .find(|(tri, _)| *tri == bytes_to_trigram(t))
1957 .map(|(_, l)| l.line_no)
1958 };
1959 assert_eq!(line_of(b"hel"), Some(1));
1960 assert_eq!(line_of(b"o\nw"), Some(1));
1961 assert_eq!(line_of(b"\nwo"), Some(2));
1962 assert_eq!(line_of(b"wor"), Some(2));
1963 }
1964
1965 #[test]
1966 fn test_extract_emits_one_posting_per_distinct_trigram_per_line() {
1967 let locs = extract_trigrams_with_locations("aaaa\naaaa", 3);
1969 assert_eq!(locs.len(), 5);
1971 let aaa = bytes_to_trigram(b"aaa");
1972 let aaa_lines: Vec<u32> = locs
1973 .iter()
1974 .filter(|(t, _)| *t == aaa)
1975 .map(|(_, l)| l.line_no)
1976 .collect();
1977 assert_eq!(aaa_lines, vec![1, 2]);
1978
1979 let mut keys: Vec<(Trigram, u32, u32)> = locs
1981 .iter()
1982 .map(|(t, l)| (*t, l.file_id, l.line_no))
1983 .collect();
1984 let n = keys.len();
1985 keys.sort_unstable();
1986 keys.dedup();
1987 assert_eq!(keys.len(), n, "duplicate (trigram, line) postings emitted");
1988 assert!(locs.iter().all(|(_, l)| l.file_id == 3));
1989
1990 let indented = " x\n y\n";
1992 let sp = bytes_to_trigram(b" ");
1993 let spaces = extract_trigrams_with_locations(indented, 0);
1994 assert_eq!(spaces.iter().filter(|(t, _)| *t == sp).count(), 2);
1995 }
1996
1997 #[test]
1998 fn test_trigram_index_basic() {
1999 let mut index = TrigramIndex::new();
2000
2001 let file_id = index.add_file(PathBuf::from("test.txt"));
2002 index.index_file(file_id, "hello world");
2003 index.finalize();
2004
2005 let results = index.search("hello");
2007 assert!(!results.is_empty());
2008
2009 let results = index.search("world");
2011 assert!(!results.is_empty());
2012
2013 let results = index.search("goodbye");
2015 assert!(results.is_empty());
2016 }
2017
2018 #[test]
2019 fn test_search_multifile() {
2020 let mut index = TrigramIndex::new();
2021
2022 let file1 = index.add_file(PathBuf::from("file1.txt"));
2023 let file2 = index.add_file(PathBuf::from("file2.txt"));
2024
2025 index.index_file(file1, "extract_symbols is here");
2026 index.index_file(file2, "extract_symbols is also here");
2027 index.finalize();
2028
2029 let results = index.search("extract_symbols");
2030 assert_eq!(results.len(), 2); let file_ids: Vec<u32> = results.iter().map(|loc| loc.file_id).collect();
2034 assert!(file_ids.contains(&file1));
2035 assert!(file_ids.contains(&file2));
2036 }
2037
2038 #[test]
2039 fn test_persistence_write_header() {
2040 let temp = TempDir::new().unwrap();
2041 let trigrams_path = temp.path().join("trigrams.bin");
2042
2043 let mut index = TrigramIndex::new();
2045 let file1 = index.add_file(PathBuf::from("src/main.rs"));
2046 let file2 = index.add_file(PathBuf::from("src/lib.rs"));
2047
2048 index.index_file(file1, "fn main() { println!(\"hello\"); }");
2049 index.index_file(
2050 file2,
2051 "pub fn hello() -> String { String::from(\"hello\") }",
2052 );
2053 index.finalize();
2054 let num_trigrams = index.trigram_count() as u64;
2055
2056 index.write(&trigrams_path).unwrap();
2057
2058 let bytes = std::fs::read(&trigrams_path).unwrap();
2059 assert!(bytes.len() > HEADER_SIZE);
2060 assert_eq!(&bytes[0..4], MAGIC);
2061 assert_eq!(read_u32(&bytes, 4), VERSION);
2062 assert_eq!(read_u64(&bytes, NUM_TRIGRAMS_OFFSET), num_trigrams);
2063 assert_eq!(read_u64(&bytes, NUM_FILES_OFFSET), 2);
2064
2065 let paths_offset = read_u64(&bytes, PATHS_OFFSET_OFFSET) as usize;
2068 assert!(paths_offset >= HEADER_SIZE + num_trigrams as usize * DIR_ENTRY_SIZE);
2069 assert!(paths_offset < bytes.len());
2070 let (len, consumed) = read_varint(&bytes[paths_offset..]).unwrap();
2071 let first = &bytes[paths_offset + consumed..paths_offset + consumed + len as usize];
2072 assert_eq!(first, b"src/main.rs");
2073 }
2074
2075 fn loc(file_id: u32, line_no: u32) -> FileLocation {
2076 FileLocation::new(file_id, line_no)
2077 }
2078
2079 fn load_err(path: &Path) -> String {
2081 match TrigramIndex::load(path) {
2082 Ok(_) => panic!("load unexpectedly succeeded"),
2083 Err(e) => e.to_string(),
2084 }
2085 }
2086
2087 #[test]
2088 fn test_intersect_two_empty() {
2089 let a = [loc(0, 1), loc(1, 2)];
2090 assert!(intersect_two(&a, &[]).is_empty());
2091 assert!(intersect_two(&[], &a).is_empty());
2092 assert!(intersect_two(&[], &[]).is_empty());
2093 }
2094
2095 #[test]
2096 fn test_intersect_two_disjoint() {
2097 let a = [loc(0, 1), loc(0, 3), loc(2, 1)];
2098 let b = [loc(0, 2), loc(1, 1), loc(2, 2)];
2099 assert!(intersect_two(&a, &b).is_empty());
2100 assert!(intersect_two(&b, &a).is_empty());
2101 }
2102
2103 #[test]
2104 fn test_intersect_two_duplicate_keys_in_b() {
2105 let a = [loc(0, 1), loc(0, 2), loc(1, 1)];
2107 let b = [
2108 loc(0, 1),
2109 loc(0, 1),
2110 loc(0, 1),
2111 loc(1, 1),
2112 loc(1, 1),
2113 loc(1, 2),
2114 ];
2115 assert_eq!(intersect_two(&a, &b), vec![loc(0, 1), loc(1, 1)]);
2116 }
2117
2118 #[test]
2119 fn test_intersect_two_gallop_path() {
2120 let b: Vec<FileLocation> = (0u32..200).map(|i| loc(i / 10, i % 10 + 1)).collect();
2122 assert_eq!(intersect_two(&[loc(7, 4)], &b), vec![loc(7, 4)]);
2123 assert!(intersect_two(&[loc(7, 11)], &b).is_empty());
2124 assert!(intersect_two(&[loc(20, 1)], &b).is_empty());
2125
2126 let a = [loc(0, 1), loc(5, 5), loc(12, 3), loc(19, 10), loc(25, 1)];
2128 assert_eq!(
2129 intersect_two(&a, &b),
2130 vec![loc(0, 1), loc(5, 5), loc(12, 3), loc(19, 10)]
2131 );
2132 }
2133
2134 #[test]
2135 fn test_intersect_two_all_equal() {
2136 let a: Vec<FileLocation> = (0u32..50).map(|i| loc(i, 1)).collect();
2137 let b: Vec<FileLocation> = (0u32..50).map(|i| loc(i, 1)).collect();
2138 assert_eq!(intersect_two(&a, &b), a);
2139 }
2140
2141 struct Lcg(u64);
2143
2144 impl Lcg {
2145 fn next(&mut self) -> u32 {
2146 self.0 = self
2147 .0
2148 .wrapping_mul(6364136223846793005)
2149 .wrapping_add(1442695040888963407);
2150 (self.0 >> 33) as u32
2151 }
2152 }
2153
2154 fn random_sorted_list(rng: &mut Lcg, n: usize) -> Vec<FileLocation> {
2155 let mut list: Vec<FileLocation> = (0..n)
2157 .map(|_| loc(rng.next() % 40, rng.next() % 60 + 1))
2158 .collect();
2159 list.sort_unstable();
2160 list.dedup();
2161 list
2162 }
2163
2164 fn reference_intersection(lists: &[&[FileLocation]]) -> Vec<FileLocation> {
2165 use std::collections::HashSet;
2166 let mut keys: HashSet<(u32, u32)> = lists[0].iter().map(key).collect();
2167 for list in &lists[1..] {
2168 let set: HashSet<(u32, u32)> = list.iter().map(key).collect();
2169 keys.retain(|k| set.contains(k));
2170 }
2171 let mut out: Vec<FileLocation> = keys
2172 .iter()
2173 .map(|k| *lists[0].iter().find(|l| key(l) == *k).unwrap())
2174 .collect();
2175 out.sort_unstable();
2176 out
2177 }
2178
2179 #[test]
2180 fn test_intersect_sorted_matches_reference() {
2181 let mut rng = Lcg(0x5eed);
2182 for _ in 0..5 {
2183 let lists: Vec<Vec<FileLocation>> = (0..3)
2184 .map(|_| random_sorted_list(&mut rng, 2_000))
2185 .collect();
2186 let mut refs: Vec<&[FileLocation]> = lists.iter().map(|l| l.as_slice()).collect();
2187 refs.sort_by_key(|l| l.len());
2188
2189 let expected = reference_intersection(&refs);
2190 assert!(!expected.is_empty(), "test data should overlap");
2191 assert_eq!(intersect_sorted(&refs), expected);
2192 }
2193 }
2194
2195 fn random_word_index(seed: u64) -> TrigramIndex {
2197 let mut rng = Lcg(seed);
2198 let mut index = TrigramIndex::new();
2199 for i in 0..40 {
2200 index.add_file(PathBuf::from(format!("f{i}.txt")));
2201 }
2202 let words = ["realm", "real", "alma", "lmn", "rea", "xyz", "ealm"];
2203 for file_id in 0..40u32 {
2204 let mut content = String::new();
2205 for _ in 0..60 {
2206 for _ in 0..4 {
2207 content.push_str(words[(rng.next() % words.len() as u32) as usize]);
2208 content.push(' ');
2209 }
2210 content.push('\n');
2211 }
2212 index.index_file(file_id, &content);
2213 }
2214 index.finalize();
2215 index
2216 }
2217
2218 #[test]
2219 fn test_lazy_search_matches_in_memory() {
2220 let mut index = random_word_index(0xbeef);
2221
2222 let temp = TempDir::new().unwrap();
2223 let path = temp.path().join("trigrams.bin");
2224 index.write(&path).unwrap();
2225 let lazy = TrigramIndex::load(&path).unwrap();
2226
2227 assert_eq!(lazy.trigram_count(), index.trigram_count());
2228 assert_eq!(lazy.file_count(), 40);
2229 assert_eq!(lazy.get_file(39), Some(&PathBuf::from("f39.txt")));
2230 assert_eq!(lazy.get_file(40), None);
2231
2232 for pattern in ["realm", "alma", "xyz", "lmn r", "ealm x", "nothing", "ab"] {
2233 assert_eq!(
2234 lazy.search(pattern),
2235 index.search(pattern),
2236 "pattern {pattern:?}"
2237 );
2238 assert_eq!(lazy.search_files(pattern), index.search_files(pattern));
2239 }
2240
2241 let files = lazy.search_files("realm");
2242 assert!(!files.is_empty());
2243 assert!(files.windows(2).all(|w| w[0] < w[1]), "sorted, distinct");
2244 }
2245
2246 #[test]
2247 fn test_find_entry_zero_copy_directory() {
2248 let mut index = random_word_index(0xf00d);
2249 let temp = TempDir::new().unwrap();
2250 let path = temp.path().join("trigrams.bin");
2251 index.write(&path).unwrap();
2252 let lazy = TrigramIndex::load(&path).unwrap();
2253
2254 assert!(index.find_entry(bytes_to_trigram(b"rea")).is_none());
2256
2257 let rea = bytes_to_trigram(b"rea");
2258 let entry = lazy.find_entry(rea).expect("rea is indexed");
2259 assert_eq!(entry.trigram, rea);
2260 let expected_len = index.get_posting_list(rea).unwrap().len();
2261 let decoded = decompress_posting_list(
2262 lazy.mmap.as_ref().unwrap(),
2263 entry.data_offset,
2264 entry.compressed_size,
2265 )
2266 .unwrap();
2267 assert_eq!(decoded.len(), expected_len);
2268 assert_eq!(&decoded, index.get_posting_list(rea).unwrap());
2269
2270 assert!(lazy.find_entry(bytes_to_trigram(b"zzz")).is_none());
2271 assert!(lazy.find_entry(0).is_none());
2272 assert!(lazy.find_entry(u32::MAX).is_none());
2273 }
2274
2275 #[test]
2276 fn test_search_repeated_trigram_returns_line_once() {
2277 let mut index = TrigramIndex::new();
2278 let file_id = index.add_file(PathBuf::from("a.txt"));
2279 index.index_file(file_id, "x\naaaa\ny");
2280 index.finalize();
2281
2282 let results = index.search("aaaa");
2283 assert_eq!(results, vec![loc(file_id, 2)]);
2284
2285 let temp = TempDir::new().unwrap();
2286 let path = temp.path().join("trigrams.bin");
2287 index.write(&path).unwrap();
2288 let lazy = TrigramIndex::load(&path).unwrap();
2289 assert_eq!(lazy.search("aaaa"), results);
2290 }
2291
2292 #[test]
2293 fn test_posting_list_block_encoding_roundtrip() {
2294 let locations = vec![
2296 loc(0, 1),
2297 loc(0, 7),
2298 loc(0, 300),
2299 loc(3, 2),
2300 loc(70_000, 1),
2301 loc(70_000, 2),
2302 ];
2303 let mut data = Vec::new();
2304 encode_posting_list(&locations, &mut data).unwrap();
2305
2306 assert_eq!(
2310 data,
2311 vec![0, 6, 1, 6, 0xA5, 0x02, 3, 2, 2, 0xED, 0xA2, 0x04, 4, 1, 1]
2312 );
2313
2314 assert_eq!(
2315 decompress_posting_list(&data, 0, data.len() as u32).unwrap(),
2316 locations
2317 );
2318
2319 let mut cursor = PostingCursor::new(&data).unwrap();
2320 assert_eq!(cursor.current(), Some(loc(0, 1)));
2321 assert_eq!(cursor.seek((0, 7)).unwrap(), Some(loc(0, 7)));
2322 assert_eq!(cursor.seek((4, 1)).unwrap(), Some(loc(70_000, 1)));
2324 assert_eq!(cursor.advance().unwrap(), Some(loc(70_000, 2)));
2325 assert_eq!(cursor.seek((70_000, 2)).unwrap(), Some(loc(70_000, 2)));
2326 assert_eq!(cursor.seek((70_001, 0)).unwrap(), None);
2327 assert_eq!(cursor.current(), None);
2328
2329 let mut cursor = PostingCursor::new(&data).unwrap();
2331 assert_eq!(cursor.seek((0, 8)).unwrap(), Some(loc(0, 300)));
2332 assert_eq!(cursor.seek((3, 1)).unwrap(), Some(loc(3, 2)));
2333 }
2334
2335 #[test]
2336 fn test_posting_list_empty_and_malformed() {
2337 let mut data = Vec::new();
2338 encode_posting_list(&[], &mut data).unwrap();
2339 assert!(data.is_empty());
2340 assert!(decompress_posting_list(&data, 0, 0).unwrap().is_empty());
2341
2342 let empty = PostingCursor::new(&[]).unwrap();
2343 assert_eq!(empty.current(), None);
2344
2345 assert!(PostingCursor::new(&[0x80]).is_err());
2347 assert!(PostingCursor::new(&[0, 2]).is_err());
2349 assert!(decompress_posting_list(&[0, 2, 1], 0, 4).is_err());
2351
2352 let enc1 = [0u8, (1 << 1) | 1, 1];
2354 let err = match PostingCursor::new(&enc1) {
2355 Ok(_) => panic!("enc=1 block was accepted"),
2356 Err(e) => e.to_string(),
2357 };
2358 assert!(err.contains("unsupported block encoding"), "{err}");
2359 assert!(decompress_posting_list(&enc1, 0, 3).is_err());
2360
2361 let with_empty_block = [0u8, 0, 2, 1 << 1, 5];
2363 assert_eq!(
2364 decompress_posting_list(&with_empty_block, 0, 5).unwrap(),
2365 vec![loc(2, 5)]
2366 );
2367 }
2368
2369 #[test]
2370 fn test_v4_roundtrip_file_block_boundaries() {
2371 let mut index = TrigramIndex::new();
2375 for i in 0..6 {
2376 index.add_file(PathBuf::from(format!("dir/file{i}.rs")));
2377 }
2378 let with = "needle here\nnothing\nneedle again\n\nneedle\n";
2379 let without = "haystack\nonly\n";
2380 index.index_file(0, with);
2381 index.index_file(1, without);
2382 index.index_file(2, with);
2383 index.index_file(3, without);
2384 index.index_file(4, with);
2385 index.index_file(5, "haystack\nneedle");
2386 index.finalize();
2387
2388 let expected = vec![
2389 loc(0, 1),
2390 loc(0, 3),
2391 loc(0, 5),
2392 loc(2, 1),
2393 loc(2, 3),
2394 loc(2, 5),
2395 loc(4, 1),
2396 loc(4, 3),
2397 loc(4, 5),
2398 loc(5, 2),
2399 ];
2400 assert_eq!(index.search("needle"), expected);
2401
2402 let temp = TempDir::new().unwrap();
2403 let path = temp.path().join("trigrams.bin");
2404 index.write(&path).unwrap();
2405 let lazy = TrigramIndex::load(&path).unwrap();
2406
2407 assert_eq!(lazy.search("needle"), expected);
2408 assert_eq!(lazy.search_files("needle"), vec![0, 2, 4, 5]);
2409 assert_eq!(
2410 lazy.search("haystack"),
2411 vec![loc(1, 1), loc(3, 1), loc(5, 1)]
2412 );
2413 assert_eq!(
2414 lazy.search("needle again"),
2415 vec![loc(0, 3), loc(2, 3), loc(4, 3)]
2416 );
2417 assert!(lazy.search("needle haystack").is_empty());
2418 assert_eq!(lazy.file_count(), 6);
2419 assert_eq!(lazy.get_file(5), Some(&PathBuf::from("dir/file5.rs")));
2420 }
2421
2422 #[test]
2423 fn test_v4_roundtrip_empty_index() {
2424 let temp = TempDir::new().unwrap();
2425 let path = temp.path().join("trigrams.bin");
2426
2427 let mut index = TrigramIndex::new();
2428 index.finalize();
2429 index.write(&path).unwrap();
2430
2431 let lazy = TrigramIndex::load(&path).unwrap();
2432 assert_eq!(lazy.trigram_count(), 0);
2433 assert_eq!(lazy.file_count(), 0);
2434 assert!(lazy.search("anything").is_empty());
2435
2436 let mut index = TrigramIndex::new();
2438 let f = index.add_file(PathBuf::from("tiny.txt"));
2439 index.index_file(f, "ab");
2440 index.finalize();
2441 index.write(&path).unwrap();
2442 let lazy = TrigramIndex::load(&path).unwrap();
2443 assert_eq!(lazy.trigram_count(), 0);
2444 assert_eq!(lazy.file_count(), 1);
2445 assert!(lazy.search("abc").is_empty());
2446 }
2447
2448 #[test]
2449 fn test_load_rejects_v3_version() {
2450 let temp = TempDir::new().unwrap();
2451 let path = temp.path().join("trigrams.bin");
2452
2453 let mut bytes = Vec::new();
2455 bytes.extend_from_slice(MAGIC);
2456 bytes.extend_from_slice(&3u32.to_le_bytes());
2457 bytes.extend_from_slice(&0u64.to_le_bytes());
2458 bytes.extend_from_slice(&0u64.to_le_bytes());
2459 std::fs::write(&path, &bytes).unwrap();
2460
2461 let err = load_err(&path);
2462 assert!(
2463 err.contains("Unsupported trigrams.bin version: 3 (expected 4)"),
2464 "{err}"
2465 );
2466 assert!(err.contains("re-index"), "{err}");
2467
2468 std::fs::write(&path, b"NOPE\x04\x00\x00\x00").unwrap();
2470 let err = load_err(&path);
2471 assert!(err.contains("wrong magic"), "{err}");
2472 }
2473
2474 #[test]
2475 fn test_load_rejects_truncated_or_inconsistent_file() {
2476 let mut index = random_word_index(0xd00d);
2477 let temp = TempDir::new().unwrap();
2478 let path = temp.path().join("trigrams.bin");
2479 index.write(&path).unwrap();
2480 let full = std::fs::read(&path).unwrap();
2481 assert!(TrigramIndex::load(&path).is_ok());
2482
2483 std::fs::write(&path, &full[..full.len() / 2]).unwrap();
2485 let err = load_err(&path);
2486 assert!(err.contains("out of bounds"), "{err}");
2487
2488 std::fs::write(&path, &full[..10]).unwrap();
2490 let err = load_err(&path);
2491 assert!(err.contains("too small"), "{err}");
2492
2493 std::fs::write(&path, &full[..full.len() - 3]).unwrap();
2495 let err = load_err(&path);
2496 assert!(err.contains("Truncated"), "{err}");
2497
2498 let mut bad = full.clone();
2500 bad[NUM_TRIGRAMS_OFFSET..NUM_TRIGRAMS_OFFSET + 8]
2501 .copy_from_slice(&(u64::MAX / 32).to_le_bytes());
2502 std::fs::write(&path, &bad).unwrap();
2503 let err = load_err(&path);
2504 assert!(err.contains("out of bounds"), "{err}");
2505 }
2506
2507 #[test]
2508 fn test_posting_list_cap_enforced() {
2509 let cap: usize = 10;
2510 let content = "aaa \n".repeat(200);
2511 let mut index = TrigramIndex::new();
2512 index.set_max_posting_list_entries(cap);
2513 let file_id = index.add_file(PathBuf::from("dense.txt"));
2514 index.index_file(file_id, &content);
2515 index.finalize();
2516 let aaa = bytes_to_trigram(b"aaa");
2517 let list = index
2518 .get_posting_list(aaa)
2519 .expect("aaa trigram should exist");
2520 assert!(list.len() <= cap, "cap exceeded: {} > {}", list.len(), cap);
2521 }
2522
2523 #[test]
2524 fn test_posting_list_cap_zero_means_unlimited() {
2525 let repetitions = 50;
2526 let content = "aaa \n".repeat(repetitions);
2528 let mut index = TrigramIndex::new();
2529 index.set_max_posting_list_entries(0);
2530 let file_id = index.add_file(PathBuf::from("dense.txt"));
2531 index.index_file(file_id, &content);
2532 index.finalize();
2533 let aaa = bytes_to_trigram(b"aaa");
2534 let list = index
2535 .get_posting_list(aaa)
2536 .expect("aaa trigram should exist");
2537 assert!(
2538 list.len() >= repetitions,
2539 "expected >= {} entries, got {}",
2540 repetitions,
2541 list.len()
2542 );
2543 }
2544}