Skip to main content

reflex/
trigram.rs

1//! Trigram-based inverted index for fast full-text code search
2//!
3//! This module implements the core trigram indexing algorithm used by Reflex.
4//! A trigram is a sequence of 3 consecutive bytes. By building an inverted index
5//! mapping trigrams to file locations, we can quickly narrow down search candidates
6//! and achieve sub-100ms query times even on large codebases.
7//!
8//! # Algorithm
9//!
10//! 1. **Indexing**: Extract all trigrams from each file, store locations
11//! 2. **Querying**: Extract trigrams from query, intersect posting lists
12//! 3. **Verification**: Check actual matches at candidate locations
13//!
14//! See `.context/TRIGRAM_RESEARCH.md` for detailed algorithm documentation.
15
16use anyhow::{Context, Result};
17use std::collections::HashMap;
18use std::fs::{File, OpenOptions};
19use std::io::Write;
20use std::path::{Path, PathBuf};
21
22/// A trigram is 3 consecutive bytes, packed into a u32 for efficient hashing
23pub type Trigram = u32;
24
25// Binary format constants for trigrams.bin
26pub(crate) const MAGIC: &[u8; 4] = b"RFTG"; // ReFlex TriGrams
27/// V4: per-line postings grouped into per-file blocks, no byte offsets,
28/// `paths_offset` in the header so `load` never walks the directory.
29pub(crate) const VERSION: u32 = 4;
30/// Header: magic(4) + version(4) + num_trigrams(8) + num_files(8) + paths_offset(8) = 32 bytes
31pub(crate) const HEADER_SIZE: usize = 32;
32/// Directory entry: trigram(4) + data_offset(8) + compressed_size(4)
33pub(crate) const DIR_ENTRY_SIZE: usize = 16;
34/// Header field offsets (bytes 8..16 are also read by `cli/misc.rs`; keep them stable)
35const NUM_TRIGRAMS_OFFSET: usize = 8;
36const NUM_FILES_OFFSET: usize = 16;
37pub(crate) const PATHS_OFFSET_OFFSET: usize = 24;
38
39/// Write a u32 as a varint (variable-length integer)
40/// Uses 1-5 bytes depending on magnitude (smaller numbers = fewer bytes)
41pub(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; // Set continuation bit
47        }
48        writer.write_all(&[byte])?;
49        if value == 0 {
50            break;
51        }
52    }
53    Ok(())
54}
55
56/// Read a varint from a byte slice, returns (value, bytes_consumed)
57fn 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/// Skip one varint without decoding it, returning the bytes consumed
83#[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/// Read a little-endian u64 at `off` (caller guarantees bounds)
102#[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/// Read a little-endian u32 at `off` (caller guarantees bounds)
108#[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
113/// Encode a sorted, key-unique posting list into V4 file blocks.
114///
115/// Layout, per distinct `file_id` in `locations`:
116///
117/// ```text
118/// varint(file_id - prev_file_id)   // first block: delta from 0
119/// varint(n_lines << 1 | enc)       // enc bit reserved; always 0 here
120/// n_lines × varint(line - prev_line)   // prev_line restarts at 0 per block
121/// ```
122///
123/// Line deltas never cross a file boundary, so every block starts with two
124/// small varints instead of the ~5-byte wrapped deltas V3 paid per file.
125pub(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)?; // enc = 0
138
139        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
151/// Decode a complete V4 posting list held in `bytes`.
152pub(crate) fn decode_posting_list(bytes: &[u8]) -> Result<Vec<FileLocation>> {
153    decompress_posting_list(bytes, 0, bytes.len() as u32)
154}
155
156/// Decompress a posting list from memory-mapped data
157///
158/// Reads a compressed posting list (V4 file blocks) from the given offset
159/// and decompresses it into a Vec<FileLocation>.
160///
161/// # Arguments
162/// * `mmap` - Memory-mapped file data
163/// * `offset` - Absolute byte offset where compressed data starts
164/// * `size` - Number of bytes to read
165fn 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    // Rough capacity guess: a typical line entry is one 1-byte varint plus
181    // amortised block headers.
182    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
192/// Streaming decoder over a V4 posting list (see [`encode_posting_list`]).
193///
194/// Decodes one `FileLocation` per line at a time so a large posting list can
195/// be intersected against a small candidate set without materialising it.
196/// Block headers are consumed transparently by [`advance`](Self::advance);
197/// [`seek`](Self::seek) skips the remainder of a block without decoding line
198/// values when the target lies in a later file.
199pub(crate) struct PostingCursor<'a> {
200    /// Compressed posting list bytes
201    data: &'a [u8],
202    /// Read position in `data`
203    pos: usize,
204    /// File id of the block being decoded
205    file_id: u32,
206    /// Lines left to decode in the current block
207    remaining: u32,
208    /// Last decoded line in the current block (delta base)
209    prev_line: u32,
210    /// Current location, `None` once exhausted
211    cur: Option<FileLocation>,
212}
213
214impl<'a> PostingCursor<'a> {
215    /// Create a cursor and decode the first entry (if any)
216    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    /// The entry the cursor is positioned on, or `None` if exhausted
230    #[inline]
231    pub(crate) fn current(&self) -> Option<FileLocation> {
232        self.cur
233    }
234
235    /// Consume a block header: `varint(file delta) varint(n_lines << 1 | enc)`
236    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    /// Decode the next entry, returning it (or `None` at end of list)
253    pub(crate) fn advance(&mut self) -> Result<Option<FileLocation>> {
254        // A block with n_lines == 0 is never written, but tolerate it
255        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    /// Advance until the current key is `>= target` (or the list is exhausted)
275    ///
276    /// When the target file id is beyond the current block, the rest of the
277    /// block is skipped by scanning varint continuation bits only.
278    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
295/// Intersect a sorted, key-deduplicated candidate set with a streamed posting list.
296///
297/// For each candidate, seeks the cursor to its key and keeps the candidate when
298/// the keys match. Runs in O(|cands| + |list|) without materialising the list.
299fn 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
315/// Mark every candidate present in a streamed posting list.
316///
317/// Same walk as [`intersect_with_cursor`], but sets `keep[i]` for each hit
318/// instead of building a new vector, so several lists (the case variants of
319/// one trigram) can be OR-ed into one mask over the same candidate slice.
320fn 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/// Location of a trigram occurrence in the codebase: one entry per
340/// (file, line) a trigram appears on. Derived `Ord` is the intersection key.
341#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
342pub struct FileLocation {
343    /// File ID (index into file list)
344    pub file_id: u32,
345    /// Line number (1-indexed)
346    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
355/// Directory entry for lazy-loaded trigram index
356///
357/// Maps each trigram to its compressed posting list location in the data section.
358/// Total size: 16 bytes per entry (4 + 8 + 4)
359/// Compressed posting bytes worth decoding per surviving candidate line.
360///
361/// Measured on the synthetic 30 MB corpus (16 cores): streaming a V4 list costs
362/// ~7 ns per byte on one thread; verifying one extra candidate line costs
363/// ~0.14 µs of CPU spread over the query pool, i.e. ~10–15 ns of wall time.
364/// Past this ratio the next list is not worth reading — `ident_7` spent 21 ms
365/// streaming four ~750 KB lists that removed no candidate.
366const SKIP_BYTES_PER_CANDIDATE: usize = 2;
367
368/// Length in bytes of `v` as a varint.
369#[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
380/// Planning size of one file's block: `1 + len(varint(n_lines << 1))` plus the
381/// line-delta varints. That is the block's V4 encoding with the file-id delta
382/// counted as one byte, whatever its real length.
383pub(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
395/// Planning size of a sorted posting list: the sum of its blocks' planning sizes.
396///
397/// The early-stop planner orders and stops by this, not by on-disk bytes. On-disk
398/// bytes include each block's file-id delta, which depends on file ids; this
399/// does not, and it adds up per file. So an index made of a base, a delta and
400/// tombstones plans exactly like a full build of the same tree. It equals the
401/// on-disk size whenever every file-id delta is below 128.
402pub(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
421/// `trigrams.<g>.plan`: the planning size of each directory entry, in directory
422/// order. Header: magic `RFPL`, version u32, entry count u64; then one u32 each.
423pub(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
459/// Write a planning-size file (tmp + fsync + rename).
460pub(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
479/// Dead file ids (one bit per id) of one segment.
480pub(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/// One segment's part of a trigram's posting list.
491#[derive(Clone, Copy)]
492pub(crate) struct ListPart<'a> {
493    /// The V4-encoded list.
494    pub data: &'a [u8],
495    /// Added to every decoded file id (the segment's first global id).
496    pub id_offset: u32,
497    /// Global ids to leave out (superseded or deleted files of this segment).
498    pub dead: Option<&'a DeadIds>,
499}
500
501/// A trigram's posting list over the segments of an index, as the planner sees it.
502pub(crate) struct TrigramList<'a> {
503    pub trigram: Trigram,
504    /// Planning size of the live postings; 0 means no live posting.
505    pub plan: u64,
506    /// Parts in ascending id order (each part's ids lie above the previous part's).
507    pub parts: Vec<ListPart<'a>>,
508}
509
510/// Every live posting of `list`, ascending.
511fn 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
526/// The slice of `cands` whose ids fall in `parts[k]`'s range.
527fn 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
536/// Candidates shifted into a part's own id space.
537fn 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
544/// The candidates (sorted, key-unique, never dead) present in `list`.
545fn 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
564/// Set `keep[i]` for every candidate present in `list`.
565fn 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
579/// Candidate lines for a pattern's trigrams (sorted, deduplicated), each given as
580/// its list or `None` when absent. Smallest planning size first; with
581/// `allow_skip`, stop once the next list is much larger than the candidates left.
582pub(crate) fn plan_intersection(
583    lists: Vec<Option<TrigramList>>,
584    allow_skip: bool,
585) -> Vec<FileLocation> {
586    // Any missing (or fully dead) list means the pattern cannot match.
587    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    // Smallest list first: it is the only one fully decoded.
596    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    // Stream the remaining lists against the shrinking candidate set.
612    for list in &lists[1..] {
613        if cands.is_empty() {
614            break;
615        }
616        // Lists are ascending, so once one is too big to be worth decoding, all
617        // the remaining ones are too.
618        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
641/// Case-insensitive candidate lines: `windows[w]` holds the lists of window `w`'s
642/// case variants that are present. See [`TrigramIndex::search_candidates_fold`].
643pub(crate) fn plan_fold_intersection(windows: Vec<Vec<TrigramList>>) -> Vec<FileLocation> {
644    // A window with no live variant cannot match in any casing.
645    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    // Cheapest window: decode every variant and merge.
661    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        // Each variant walks the whole candidate set once (one seek per
694        // candidate, about the cost of decoding one byte), on top of decoding its
695        // list. Kubernetes, `(?i)kubernetes`: the second window cost 20 ms to drop
696        // 20k of 134k candidates, which the verifier would have handled in 0.3 ms.
697        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                // Skipping a window keeps the result a superset.
712                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
734/// A list held by one segment.
735pub(crate) fn single_list(trigram: Trigram, part: ListPart<'_>, plan: u64) -> TrigramList<'_> {
736    TrigramList {
737        trigram,
738        plan,
739        parts: vec![part],
740    }
741}
742
743/// A pattern's distinct trigrams, sorted; empty when it is too short (the caller
744/// then scans).
745pub(crate) fn pattern_trigrams(pattern: &str) -> Vec<Trigram> {
746    if pattern.len() < 3 {
747        // Pattern too short for trigrams - caller must fall back to full scan
748        return vec![];
749    }
750    let mut trigrams = extract_trigrams(pattern);
751    // A repeated trigram (e.g. "aaaa") would otherwise be intersected with itself
752    trigrams.sort_unstable();
753    trigrams.dedup();
754    trigrams
755}
756
757/// The case variants of each 3-byte window of an ASCII literal (identical windows
758/// once, sorted); `None` when the literal is too short or not ASCII.
759pub(crate) fn fold_windows(literal: &[u8]) -> Option<Vec<Vec<Trigram>>> {
760    if literal.len() < 3 || !literal.is_ascii() {
761        return None;
762    }
763    // Variant set per window; identical windows are intersected once.
764    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
770/// The trigrams whose lines hold a Kelvin sign (`E2 84 AA`) or a long s
771/// (`C5 BF`), for [`TrigramIndex::exotic_fold_lines`]: every `C5 BF ?` trigram
772/// (one range), and the Kelvin sign and every `? C5 BF` trigram (singles).
773pub(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
779/// Every live posting of `lists`, merged, sorted and deduplicated.
780pub(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    /// Position in the directory (the planning-size file is indexed the same way)
800    index: usize,
801    /// The trigram value (for binary search)
802    trigram: Trigram,
803    /// Absolute byte offset in the file where compressed data starts
804    data_offset: u64,
805    /// Size of compressed posting list in bytes
806    compressed_size: u32,
807}
808
809/// Trigram-based inverted index
810///
811/// Maps each trigram to a sorted list of locations where it appears.
812/// Posting lists are kept sorted by (file_id, line_no) for efficient intersection.
813/// The index itself is kept sorted by trigram for O(log n) binary search.
814///
815/// Supports three modes:
816/// 1. **In-memory mode** (during indexing): All posting lists in RAM
817/// 2. **Batch-flush mode** (large codebases): Periodically flushes partial indices to disk to limit RAM
818/// 3. **Lazy-loaded mode** (after loading): Compressed posting lists in mmap, decompressed on-demand
819pub struct TrigramIndex {
820    /// Inverted index: sorted Vec of (trigram, locations) for binary search
821    /// Used in in-memory mode (during indexing)
822    index: Vec<(Trigram, Vec<FileLocation>)>,
823    /// File ID to file path mapping (in-memory mode). Empty in lazy mode: the
824    /// paths section stays in the mmap undecoded and `num_files` carries the
825    /// count, because content.bin already answers `file_id → path` in O(1).
826    files: Vec<PathBuf>,
827    /// File count in lazy mode.
828    num_files: usize,
829    /// Start of the paths section in the mmap (lazy mode).
830    paths_offset: usize,
831    /// Paths decoded from the mmap on first request (lazy mode).
832    lazy_paths: std::sync::OnceLock<Vec<PathBuf>>,
833    /// Temporary HashMap used during batch indexing (None when finalized)
834    temp_index: Option<HashMap<Trigram, Vec<FileLocation>>>,
835    /// Memory-mapped index file (for lazy loading)
836    mmap: Option<memmap2::Mmap>,
837    /// Number of directory entries in the mmap (lazy mode). The directory is
838    /// binary-searched in place; it is never decoded into a Vec.
839    num_trigrams: usize,
840    /// Cap on posting list size; 0 = unlimited. Enforced at finalize time.
841    /// Bounds query latency for high-frequency trigrams (trigram-density lens).
842    max_posting_list_entries: usize,
843    /// Planning size of every directory entry (lazy mode), when the index was
844    /// written with one; see [`plan_size`].
845    plan: Option<PlanSizes>,
846}
847
848impl TrigramIndex {
849    /// Create a new empty trigram index
850    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    /// Set maximum posting list entries per trigram (0 = unlimited).
866    pub fn set_max_posting_list_entries(&mut self, cap: usize) {
867        self.max_posting_list_entries = cap;
868    }
869
870    /// Add a file to the index and return its file_id
871    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    /// Get file path for a file_id
878    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    /// Get total number of files
905    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    /// Get total number of unique trigrams
914    pub fn trigram_count(&self) -> usize {
915        if self.mmap.is_some() {
916            // Lazy-loaded mode
917            self.num_trigrams
918        } else {
919            // In-memory mode
920            self.index.len()
921        }
922    }
923
924    /// Binary-search the mmapped directory for `trigram` (lazy mode only).
925    ///
926    /// Reads only the 4-byte trigram at each probe; the full 16-byte entry is
927    /// decoded once, on a hit. `load` has already checked that the whole
928    /// directory lies inside the mmap.
929    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    /// Index a file's content
952    ///
953    /// Extracts all trigrams from the content and adds them to the inverted index.
954    /// Must call finalize() after indexing all files to prepare for searching.
955    pub fn index_file(&mut self, file_id: u32, content: &str) {
956        let trigrams = extract_trigrams_with_locations(content, file_id);
957
958        // Use the persistent HashMap for O(1) updates during batch processing
959        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    /// Build index from a collection of pre-extracted trigrams (bulk operation)
972    ///
973    /// This is much more efficient than calling index_file() multiple times,
974    /// as it builds the HashMap once instead of rebuilding it for each file.
975    pub fn build_from_trigrams(&mut self, trigrams: Vec<(Trigram, FileLocation)>) {
976        let mut temp_map: HashMap<Trigram, Vec<FileLocation>> = HashMap::new();
977
978        // Group trigrams into posting lists
979        for (trigram, location) in trigrams {
980            temp_map.entry(trigram).or_default().push(location);
981        }
982
983        // Convert to sorted Vec for binary search
984        self.index = temp_map.into_iter().collect();
985
986        // Clear temp_index since we're using the Vec directly
987        self.temp_index = None;
988
989        // Finalize immediately (sort and deduplicate)
990        self.finalize();
991    }
992
993    /// Finalize the index by sorting all posting lists and the index itself
994    ///
995    /// Must be called after all files are indexed, before querying.
996    /// Converts the HashMap to a sorted Vec for fast binary search.
997    ///
998    /// If batch flushing was enabled, finalization will be deferred until write()
999    /// is called, which will perform streaming merge directly to disk.
1000    pub fn finalize(&mut self) {
1001        // Standard finalization (no batch flushing)
1002        // Convert HashMap to Vec if we have a temp index
1003        if let Some(temp_map) = self.temp_index.take() {
1004            self.index = temp_map.into_iter().collect();
1005        }
1006
1007        // Sort, deduplicate, and cap posting lists
1008        let cap = self.max_posting_list_entries;
1009        for (trigram, list) in self.index.iter_mut() {
1010            list.sort_unstable();
1011            list.dedup(); // Remove duplicates (same trigram appearing multiple times on same line)
1012            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        // Sort the index by trigram for binary search
1024        self.index.sort_unstable_by_key(|(trigram, _)| *trigram);
1025    }
1026
1027    /// Search for a plain text pattern
1028    ///
1029    /// Returns candidate file locations that could contain the pattern.
1030    /// Caller must verify actual matches.
1031    ///
1032    /// In lazy-loaded mode: Decompresses posting lists on-demand from mmap.
1033    /// In in-memory mode: Uses pre-loaded posting lists.
1034    pub fn search(&self, pattern: &str) -> Vec<FileLocation> {
1035        self.search_impl(pattern, false)
1036    }
1037
1038    /// Candidate lines for `pattern`, allowing the intersection to stop early.
1039    ///
1040    /// Every posting list of a common trigram (`ide`, `ent`, `nt_` …) is streamed
1041    /// in full on every query, and on a pattern like `ident_7` the four largest
1042    /// lists cost ~45 ms without removing a single candidate that the smallest
1043    /// list (`t_7`) had not already narrowed to. The caller verifies every
1044    /// candidate line anyway — exactly, and on a thread pool — so once the next
1045    /// list is much larger than the surviving candidate set, decoding it costs
1046    /// more than verifying the extra candidates would. This method stops there;
1047    /// the result is a superset of [`Self::search`] and never misses a match.
1048    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        // Check if we're in lazy-loaded mode or in-memory mode
1059        if self.mmap.is_some() {
1060            // Lazy-loaded mode: look up every directory entry first; any miss
1061            // means the pattern cannot match.
1062            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            // In-memory mode: use pre-loaded index
1075            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                    // Trigram missing - pattern cannot match
1080                    Err(_) => return vec![],
1081                }
1082            }
1083
1084            // Sort by list size (smallest first for efficient intersection)
1085            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                // ~1.3 bytes per posting on disk; same rule as the lazy path.
1097                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    /// Case-insensitive candidate lines for an ASCII literal.
1109    ///
1110    /// Every 3-byte window of `literal` is looked up under all of its ASCII
1111    /// case variants (≤ 8 trigrams: each letter byte has two forms) and the
1112    /// variants' posting lists are OR-ed; windows are then AND-ed, cheapest
1113    /// first, with the same early stop as [`search_candidates`](Self::search_candidates).
1114    /// The result is a superset of every line that contains the literal in any
1115    /// ASCII casing; callers verify with a `(?i)` regex.
1116    ///
1117    /// Only ASCII case is folded here. Unicode simple case folding also maps
1118    /// `k` to U+212A KELVIN SIGN and `s` to U+017F LATIN SMALL LETTER LONG S;
1119    /// a caller whose literal contains `k` or `s` must union
1120    /// [`exotic_fold_lines`](Self::exotic_fold_lines) into the result to keep
1121    /// parity with the regex engine. A non-ASCII literal is not supported:
1122    /// the caller must fall back to a scan.
1123    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            // The present variants of each window; a window with no present
1130            // variant cannot match in any casing.
1131            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                // ~1.3 bytes per posting on disk; same rule as the lazy path.
1163                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    /// Every line that contains U+212A KELVIN SIGN or U+017F LONG S.
1194    ///
1195    /// Under Unicode simple case folding a `(?i)` regex lets `k` match the
1196    /// Kelvin sign and `s` match the long s. Their UTF-8 forms (`E2 84 AA` and
1197    /// `C5 BF`) never align with the ASCII windows of
1198    /// [`search_candidates_fold`](Self::search_candidates_fold), so a line whose
1199    /// only match uses one of them would be missed. The Kelvin sign is its own
1200    /// trigram; the long s appears in a `C5 BF ?` or `? C5 BF` trigram of any
1201    /// line long enough to hold a ≥3-byte literal. On code corpora every lookup
1202    /// misses, so this costs a few hundred directory probes and returns nothing.
1203    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    /// Directory entries with `lo <= trigram <= hi` (lazy mode only).
1236    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    /// Search for a plain text pattern and return the distinct candidate file IDs
1270    ///
1271    /// Output is sorted ascending. Same caveats as [`search`](Self::search):
1272    /// callers must verify actual matches, and short patterns yield nothing.
1273    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        // `search` output is sorted by (file_id, line_no), so duplicates are adjacent
1280        files.dedup();
1281        files
1282    }
1283
1284    /// Get posting list for a specific trigram (for debugging)
1285    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    /// Write the trigram index to disk
1293    ///
1294    /// Binary format V4 (lazy-loadable with directory + data separation):
1295    /// - Header (32 bytes): magic, version, num_trigrams, num_files, paths_offset
1296    /// - Directory Section (16 bytes per trigram, sorted by trigram):
1297    ///   - trigram: u32 (4 bytes)
1298    ///   - data_offset: u64 (8 bytes) - absolute offset in file
1299    ///   - compressed_size: u32 (4 bytes) - size of compressed posting list
1300    /// - Data Section (variable size):
1301    ///   - Posting lists as per-file blocks (see [`encode_posting_list`])
1302    /// - File Paths Section at `paths_offset` (variable size):
1303    ///   - path_len: varint
1304    ///   - path_bytes: [u8; path_len]
1305    pub fn write(&mut self, path: impl AsRef<Path>) -> Result<()> {
1306        let path = path.as_ref();
1307
1308        // Standard write path (no batch flushing).
1309        // Crash-safe: stream into `<path>.tmp`, sync, then rename over `path`.
1310        // A crash mid-write leaves the previous trigrams.bin intact (or no file
1311        // at all), never a short file with valid magic bytes.
1312        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        // Use a large buffer (16MB) for streaming writes
1321        let mut writer = std::io::BufWriter::with_capacity(16 * 1024 * 1024, file);
1322
1323        // Step 1: Compress all posting lists and build the directory. Data
1324        // offsets are known up front because the directory has a fixed size.
1325        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        // Step 2: Write header
1346        writer.write_all(MAGIC)?;
1347        writer.write_all(&VERSION.to_le_bytes())?;
1348        writer.write_all(&(self.index.len() as u64).to_le_bytes())?; // num_trigrams
1349        writer.write_all(&(self.files.len() as u64).to_le_bytes())?; // num_files
1350        writer.write_all(&paths_offset.to_le_bytes())?; // paths_offset
1351
1352        // Step 3: Write directory
1353        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        // Step 4: Write data section (compressed posting lists)
1360        for compressed in &compressed_lists {
1361            writer.write_all(compressed)?;
1362        }
1363
1364        // Step 5: Write file paths
1365        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        // Flush and sync, then publish atomically
1373        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    /// Load trigram index from disk using memory-mapped I/O with lazy loading
1390    ///
1391    /// Binary format V4: validates the header, bounds-checks the directory
1392    /// against `paths_offset`, and decodes only the file paths. The directory
1393    /// stays in the mmap and is binary-searched in place; posting lists are
1394    /// decompressed on demand during search. Cost is O(files), not O(trigrams).
1395    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        // Memory-map the file (keep it alive for lazy access)
1402        let mmap = unsafe {
1403            memmap2::Mmap::map(&file)
1404                .with_context(|| format!("Failed to mmap {}", path.display()))?
1405        };
1406
1407        // Validate magic + version before the size check so an older (shorter
1408        // header) format still reports the version mismatch callers key on.
1409        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        // Layout check: header + directory must end at or before the paths
1447        // section, which must lie inside the file. This is the only guard the
1448        // in-place directory search relies on.
1449        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        // The paths section is validated (bounds only, no allocation) and left in
1464        // the mmap. Decoding 24k paths into a Vec<PathBuf> was part of every CLI
1465        // open; the query side reads paths from content.bin, O(1) per id since
1466        // its V2, and `get_file` decodes this section on first request.
1467        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(), // Empty in lazy mode
1486            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), // Keep mmap alive for lazy decompression!
1492            num_trigrams,
1493            max_posting_list_entries: 0,
1494            plan: None,
1495        })
1496    }
1497
1498    /// Attach the planning sizes written next to this index (`trigrams.<g>.plan`).
1499    /// The early-stop planner then orders and stops by planning size instead of
1500    /// on-disk bytes (see [`plan_size`]).
1501    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    /// Whether planning sizes are attached.
1516    pub fn has_plan(&self) -> bool {
1517        self.plan.is_some()
1518    }
1519
1520    /// Every trigram of the directory, ascending (lazy mode).
1521    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    /// One trigram's list as the planner sees it (lazy mode): its bytes and its
1528    /// planning size (on-disk bytes when no planning sizes are attached).
1529    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    /// Every list with `lo <= trigram <= hi` (lazy mode).
1535    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
1581/// Extract all trigrams from text
1582///
1583/// Returns a vector of trigrams (without location info).
1584pub 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
1596/// Extract trigrams with file location information
1597///
1598/// Returns one `(trigram, location)` pair per **distinct trigram per line**,
1599/// for building the inverted index. Emitting every byte position (as V3 did)
1600/// only produced duplicate `(file, line)` keys that the intersection threw
1601/// away; deduplicating here is what makes `finalize`'s `dedup()` a no-op.
1602///
1603/// A trigram that spans a newline is attributed to the line of its first
1604/// byte, except that a trigram *starting* on `\n` belongs to the next line
1605/// (unchanged from V3, so `"lo\n"`-style queries keep matching).
1606pub 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
1615/// Walk `text` line by line and hand each line's distinct trigrams, sorted, to `f`.
1616///
1617/// This is the one place the newline rule lives: a trigram that spans a newline
1618/// belongs to the line of its first byte, except that a trigram *starting* on
1619/// `\n` belongs to the next line. Both the extractor above and the indexer's
1620/// parallel builder (`trigram_build`) are built on it, so the two can never
1621/// disagree about which line a trigram is on.
1622pub(crate) fn scan_line_trigrams(text: &str, mut f: impl FnMut(u32, &[Trigram])) {
1623    let bytes = text.as_bytes();
1624    // Trigrams of the line being scanned; sorted + deduplicated on flush
1625    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        // Track newlines
1630        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        // Extract trigram
1639        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/// Convert 3 bytes to a trigram (packed u32)
1649#[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
1655/// All ASCII case variants of a 3-byte window, sorted and deduplicated.
1656///
1657/// Each ASCII letter byte contributes two forms, every other byte one, so the
1658/// result has 1, 2, 4 or 8 trigrams.
1659fn 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/// Convert trigram back to bytes (for debugging)
1682#[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/// Intersection key: posting lists are matched on (file_id, line_no)
1692#[inline]
1693fn key(l: &FileLocation) -> (u32, u32) {
1694    (l.file_id, l.line_no)
1695}
1696
1697/// Sorted two-pointer intersection of `a` and `b` on `key`.
1698///
1699/// `a` is the running candidate set (sorted, deduplicated by key). `b` is a sorted
1700/// posting list; should it hold several entries per key, all of them are
1701/// consumed on a match. When `b` is much larger
1702/// than `a`, the scan of `b` gallops via `partition_point`. Output keeps the
1703/// `FileLocation` from `a`, so it stays sorted and key-unique.
1704fn 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                // Consume every entry in `b` with this key
1724                j += 1;
1725                while j < b.len() && key(&b[j]) == ka {
1726                    j += 1;
1727                }
1728            }
1729        }
1730    }
1731
1732    out
1733}
1734
1735/// Intersect sorted posting lists by (file_id, line_no).
1736///
1737/// Returns locations where ALL trigrams appear on the SAME line (not just in the
1738/// same file), keeping the `FileLocation` from the first list. Callers should
1739/// pass lists smallest-first: the first list is copied and deduplicated by key,
1740/// then folded against the rest in linear time.
1741pub(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    /// `search_candidates` may stop intersecting once the next list is much larger
1764    /// than the candidate set; it must then return a superset of the exact
1765    /// intersection, never a subset, in both lazy and in-memory modes.
1766    #[test]
1767    fn search_candidates_is_a_superset_of_search() {
1768        let mut index = TrigramIndex::new();
1769        // Many lines share the common trigrams of "ident_"; only a few carry "t_7".
1770        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        // Same contract through the on-disk (lazy) path.
1792        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    /// `search_candidates_fold` plus `exotic_fold_lines` must cover every line a
1804    /// `(?i)` regex matches, in both modes, including the Kelvin-sign and long-s
1805    /// folds the regex crate applies to `k` and `s`.
1806    #[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        // The regex crate really does fold these (Unicode simple case folding),
1867        // and the ASCII windows alone do not reach them.
1868        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        // Exotic lines are exactly the two lines per file that carry the folds.
1889        assert_eq!(lazy.exotic_fold_lines().len(), 20);
1890        assert_eq!(index.exotic_fold_lines(), lazy.exotic_fold_lines());
1891
1892        // A window absent in every casing is a definite miss.
1893        assert!(lazy.search_candidates_fold(b"zzqx_absent").is_empty());
1894        // Non-ASCII is not folded here.
1895        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        // "hello" → "hel", "ell", "llo"
1906        assert_eq!(trigrams.len(), 3);
1907
1908        // Verify trigrams are unique
1909        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        // "hello\nworld" has 9 distinct trigrams:
1947        // line 1: "hel", "ell", "llo", "lo\n", "o\nw"
1948        // line 2: "\nwo", "wor", "orl", "rld"   (a trigram starting on '\n' is line 2)
1949        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        // "aaaa" alone yields "aaa" twice at byte level; per line it must be once.
1968        let locs = extract_trigrams_with_locations("aaaa\naaaa", 3);
1969        // line 1: "aaa", "aa\n", "a\na"   line 2: "\naa", "aaa"
1970        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        // Every (trigram, file, line) key is unique and each line's run is sorted
1980        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        // Heavy indentation: 16 spaces → "   " appears 14 times per line, emitted once
1991        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        // Search for "hello"
2006        let results = index.search("hello");
2007        assert!(!results.is_empty());
2008
2009        // Search for "world"
2010        let results = index.search("world");
2011        assert!(!results.is_empty());
2012
2013        // Search for "goodbye" (not in text)
2014        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); // One result per file
2031
2032        // Verify we got both files
2033        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        // Build and write index
2044        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        // paths_offset points just past header + directory + data, and the
2066        // paths section decodes to the files we added.
2067        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    /// `unwrap_err` without requiring `Debug` on the success type
2080    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        // Repeated keys in `b` are all consumed; result keeps `a`'s entry once
2106        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        // 1 vs 200 entries forces the gallop branch (b.len() > 8 * a.len())
2121        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        // A few shared keys spread through a large `b`
2127        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    /// Minimal LCG so the property test is deterministic without extra crates
2142    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        // Keys from a small range (40 files x 60 lines) to force heavy overlap
2156        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    /// Build a 40-file index whose posting lists differ widely in size
2196    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        // In-memory index has no directory to search
2255        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        // Three file blocks; the middle one has a single line, the last is far away
2295        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        // Expected bytes: block(0): fd=0, n=3<<1, lines 1,6,293(2 B)
2307        //                 block(3): fd=3, n=1<<1, line 2
2308        //                 block(70000): fd=69997 (3 B), n=2<<1, lines 1,1
2309        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        // Target in a later file: skips the rest of block 0 and block 3
2323        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        // Seeking within the first block by line only
2330        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        // Truncated varint surfaces as an error rather than a panic
2346        assert!(PostingCursor::new(&[0x80]).is_err());
2347        // Block header present, line varint missing
2348        assert!(PostingCursor::new(&[0, 2]).is_err());
2349        // Out-of-bounds slice request
2350        assert!(decompress_posting_list(&[0, 2, 1], 0, 4).is_err());
2351
2352        // Reserved enc=1 blocks are rejected, not misread
2353        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        // A zero-length block is tolerated and skipped
2362        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        // "needle" sits on several lines of files 0, 2 and 4, on none of 1 and 3,
2372        // and file 5 has it only on its last line. Every block boundary shape:
2373        // consecutive files, gaps, single-line block.
2374        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        // Files but no indexable content (every file shorter than a trigram)
2437        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        // A V3 header: magic, version 3, num_trigrams, num_files (24 bytes)
2454        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        // Wrong magic is a different error
2469        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        // Cut in the middle of the data section: paths_offset now lies past EOF
2484        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        // Cut inside the header
2489        std::fs::write(&path, &full[..10]).unwrap();
2490        let err = load_err(&path);
2491        assert!(err.contains("too small"), "{err}");
2492
2493        // Cut inside the paths section
2494        std::fs::write(&path, &full[..full.len() - 3]).unwrap();
2495        let err = load_err(&path);
2496        assert!(err.contains("Truncated"), "{err}");
2497
2498        // Directory claims more entries than fit before paths_offset
2499        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        // One line per repetition: postings are per line, not per byte
2527        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}