use anyhow::{Context, Result};
use std::collections::HashMap;
use std::fs::{File, OpenOptions};
use std::io::Write;
use std::path::{Path, PathBuf};
pub type Trigram = u32;
pub(crate) const MAGIC: &[u8; 4] = b"RFTG"; pub(crate) const VERSION: u32 = 4;
pub(crate) const HEADER_SIZE: usize = 32;
pub(crate) const DIR_ENTRY_SIZE: usize = 16;
const NUM_TRIGRAMS_OFFSET: usize = 8;
const NUM_FILES_OFFSET: usize = 16;
pub(crate) const PATHS_OFFSET_OFFSET: usize = 24;
pub(crate) fn write_varint(writer: &mut impl Write, mut value: u32) -> std::io::Result<()> {
loop {
let mut byte = (value & 0x7F) as u8;
value >>= 7;
if value != 0 {
byte |= 0x80; }
writer.write_all(&[byte])?;
if value == 0 {
break;
}
}
Ok(())
}
fn read_varint(data: &[u8]) -> Result<(u32, usize)> {
let mut value: u32 = 0;
let mut shift = 0;
let mut pos = 0;
loop {
if pos >= data.len() {
anyhow::bail!("Truncated varint");
}
let byte = data[pos];
pos += 1;
value |= ((byte & 0x7F) as u32) << shift;
if byte & 0x80 == 0 {
break;
}
shift += 7;
if shift >= 32 {
anyhow::bail!("Varint too large");
}
}
Ok((value, pos))
}
#[inline]
pub(crate) fn skip_varint(data: &[u8]) -> Result<usize> {
let mut pos = 0;
loop {
if pos >= data.len() {
anyhow::bail!("Truncated varint");
}
let byte = data[pos];
pos += 1;
if byte & 0x80 == 0 {
return Ok(pos);
}
if pos >= 5 {
anyhow::bail!("Varint too large");
}
}
}
#[inline]
fn read_u64(data: &[u8], off: usize) -> u64 {
u64::from_le_bytes(data[off..off + 8].try_into().expect("8 bytes"))
}
#[inline]
fn read_u32(data: &[u8], off: usize) -> u32 {
u32::from_le_bytes(data[off..off + 4].try_into().expect("4 bytes"))
}
pub(crate) fn encode_posting_list(locations: &[FileLocation], out: &mut Vec<u8>) -> Result<()> {
let mut prev_file_id = 0u32;
let mut i = 0;
while i < locations.len() {
let file_id = locations[i].file_id;
let mut j = i + 1;
while j < locations.len() && locations[j].file_id == file_id {
j += 1;
}
let block = &locations[i..j];
write_varint(out, file_id.wrapping_sub(prev_file_id))?;
write_varint(out, (block.len() as u32) << 1)?;
let mut prev_line = 0u32;
for loc in block {
write_varint(out, loc.line_no.wrapping_sub(prev_line))?;
prev_line = loc.line_no;
}
prev_file_id = file_id;
i = j;
}
Ok(())
}
pub(crate) fn decode_posting_list(bytes: &[u8]) -> Result<Vec<FileLocation>> {
decompress_posting_list(bytes, 0, bytes.len() as u32)
}
fn decompress_posting_list(mmap: &[u8], offset: u64, size: u32) -> Result<Vec<FileLocation>> {
let start = offset as usize;
let end = start + size as usize;
if end > mmap.len() {
anyhow::bail!(
"Posting list out of bounds: offset={}, size={}, mmap_len={}",
offset,
size,
mmap.len()
);
}
let compressed_data = &mmap[start..end];
let mut locations = Vec::with_capacity(compressed_data.len());
let mut cursor = PostingCursor::new(compressed_data)?;
while let Some(loc) = cursor.current() {
locations.push(loc);
cursor.advance()?;
}
Ok(locations)
}
pub(crate) struct PostingCursor<'a> {
data: &'a [u8],
pos: usize,
file_id: u32,
remaining: u32,
prev_line: u32,
cur: Option<FileLocation>,
}
impl<'a> PostingCursor<'a> {
pub(crate) fn new(data: &'a [u8]) -> Result<Self> {
let mut cursor = Self {
data,
pos: 0,
file_id: 0,
remaining: 0,
prev_line: 0,
cur: None,
};
cursor.advance()?;
Ok(cursor)
}
#[inline]
pub(crate) fn current(&self) -> Option<FileLocation> {
self.cur
}
fn read_block_header(&mut self) -> Result<()> {
let (file_delta, consumed) = read_varint(&self.data[self.pos..])?;
self.pos += consumed;
let (header, consumed) = read_varint(&self.data[self.pos..])?;
self.pos += consumed;
if header & 1 != 0 {
anyhow::bail!("unsupported block encoding (enc=1) in posting list");
}
self.file_id = self.file_id.wrapping_add(file_delta);
self.remaining = header >> 1;
self.prev_line = 0;
Ok(())
}
pub(crate) fn advance(&mut self) -> Result<Option<FileLocation>> {
while self.remaining == 0 {
if self.pos >= self.data.len() {
self.cur = None;
return Ok(None);
}
self.read_block_header()?;
}
let (line_delta, consumed) = read_varint(&self.data[self.pos..])?;
self.pos += consumed;
self.remaining -= 1;
let line_no = self.prev_line.wrapping_add(line_delta);
self.prev_line = line_no;
let loc = FileLocation::new(self.file_id, line_no);
self.cur = Some(loc);
Ok(self.cur)
}
pub(crate) fn seek(&mut self, target: (u32, u32)) -> Result<Option<FileLocation>> {
while let Some(loc) = self.cur {
if key(&loc) >= target {
break;
}
if loc.file_id < target.0 {
for _ in 0..self.remaining {
self.pos += skip_varint(&self.data[self.pos..])?;
}
self.remaining = 0;
}
self.advance()?;
}
Ok(self.cur)
}
}
fn intersect_with_cursor(
cands: &[FileLocation],
cur: &mut PostingCursor,
) -> Result<Vec<FileLocation>> {
let mut out = Vec::new();
for cand in cands {
let k = key(cand);
match cur.seek(k)? {
Some(loc) if key(&loc) == k => out.push(*cand),
Some(_) => {}
None => break,
}
}
Ok(out)
}
fn mark_with_cursor(
cands: &[FileLocation],
cur: &mut PostingCursor,
keep: &mut [bool],
) -> Result<()> {
for (i, cand) in cands.iter().enumerate() {
if keep[i] {
continue;
}
let k = key(cand);
match cur.seek(k)? {
Some(loc) if key(&loc) == k => keep[i] = true,
Some(_) => {}
None => break,
}
}
Ok(())
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct FileLocation {
pub file_id: u32,
pub line_no: u32,
}
impl FileLocation {
pub fn new(file_id: u32, line_no: u32) -> Self {
Self { file_id, line_no }
}
}
const SKIP_BYTES_PER_CANDIDATE: usize = 2;
#[derive(Debug, Clone)]
struct DirectoryEntry {
trigram: Trigram,
data_offset: u64,
compressed_size: u32,
}
pub struct TrigramIndex {
index: Vec<(Trigram, Vec<FileLocation>)>,
files: Vec<PathBuf>,
num_files: usize,
paths_offset: usize,
lazy_paths: std::sync::OnceLock<Vec<PathBuf>>,
temp_index: Option<HashMap<Trigram, Vec<FileLocation>>>,
mmap: Option<memmap2::Mmap>,
num_trigrams: usize,
max_posting_list_entries: usize,
}
impl TrigramIndex {
pub fn new() -> Self {
Self {
index: Vec::new(),
files: Vec::new(),
num_files: 0,
paths_offset: 0,
lazy_paths: std::sync::OnceLock::new(),
temp_index: Some(HashMap::new()),
mmap: None,
num_trigrams: 0,
max_posting_list_entries: 0,
}
}
pub fn set_max_posting_list_entries(&mut self, cap: usize) {
self.max_posting_list_entries = cap;
}
pub fn add_file(&mut self, path: PathBuf) -> u32 {
let file_id = self.files.len() as u32;
self.files.push(path);
file_id
}
pub fn get_file(&self, file_id: u32) -> Option<&PathBuf> {
match &self.mmap {
None => self.files.get(file_id as usize),
Some(mmap) => self
.lazy_paths
.get_or_init(|| {
let mut out = Vec::with_capacity(self.num_files);
let mut pos = self.paths_offset;
for _ in 0..self.num_files {
let Ok((len, consumed)) = read_varint(&mmap[pos..]) else {
break;
};
pos += consumed;
let end = pos + len as usize;
let Some(bytes) = mmap.get(pos..end) else {
break;
};
out.push(PathBuf::from(String::from_utf8_lossy(bytes).into_owned()));
pos = end;
}
out
})
.get(file_id as usize),
}
}
pub fn file_count(&self) -> usize {
if self.mmap.is_some() {
self.num_files
} else {
self.files.len()
}
}
pub fn trigram_count(&self) -> usize {
if self.mmap.is_some() {
self.num_trigrams
} else {
self.index.len()
}
}
fn find_entry(&self, trigram: Trigram) -> Option<DirectoryEntry> {
let mmap = self.mmap.as_ref()?;
let (mut lo, mut hi) = (0usize, self.num_trigrams);
while lo < hi {
let mid = lo + (hi - lo) / 2;
let off = HEADER_SIZE + mid * DIR_ENTRY_SIZE;
match read_u32(mmap, off).cmp(&trigram) {
std::cmp::Ordering::Less => lo = mid + 1,
std::cmp::Ordering::Greater => hi = mid,
std::cmp::Ordering::Equal => {
return Some(DirectoryEntry {
trigram,
data_offset: read_u64(mmap, off + 4),
compressed_size: read_u32(mmap, off + 12),
});
}
}
}
None
}
pub fn index_file(&mut self, file_id: u32, content: &str) {
let trigrams = extract_trigrams_with_locations(content, file_id);
if let Some(ref mut temp_map) = self.temp_index {
for (trigram, location) in trigrams {
temp_map
.entry(trigram)
.or_insert_with(Vec::new)
.push(location);
}
} else {
panic!("Cannot call index_file() after finalize(). Index is read-only.");
}
}
pub fn build_from_trigrams(&mut self, trigrams: Vec<(Trigram, FileLocation)>) {
let mut temp_map: HashMap<Trigram, Vec<FileLocation>> = HashMap::new();
for (trigram, location) in trigrams {
temp_map.entry(trigram).or_default().push(location);
}
self.index = temp_map.into_iter().collect();
self.temp_index = None;
self.finalize();
}
pub fn finalize(&mut self) {
if let Some(temp_map) = self.temp_index.take() {
self.index = temp_map.into_iter().collect();
}
let cap = self.max_posting_list_entries;
for (trigram, list) in self.index.iter_mut() {
list.sort_unstable();
list.dedup(); if cap > 0 && list.len() > cap {
log::warn!(
"Trigram 0x{:06X} posting list has {} entries (cap {}); truncating.",
trigram,
list.len(),
cap
);
list.truncate(cap);
}
}
self.index.sort_unstable_by_key(|(trigram, _)| *trigram);
}
pub fn search(&self, pattern: &str) -> Vec<FileLocation> {
self.search_impl(pattern, false)
}
pub fn search_candidates(&self, pattern: &str) -> Vec<FileLocation> {
self.search_impl(pattern, true)
}
fn search_impl(&self, pattern: &str, allow_skip: bool) -> Vec<FileLocation> {
if pattern.len() < 3 {
return vec![];
}
let mut trigrams = extract_trigrams(pattern);
trigrams.sort_unstable();
trigrams.dedup();
if trigrams.is_empty() {
return vec![];
}
if let Some(ref mmap) = self.mmap {
let mut entries: Vec<DirectoryEntry> = Vec::with_capacity(trigrams.len());
for trigram in &trigrams {
match self.find_entry(*trigram) {
Some(entry) => entries.push(entry),
None => return vec![],
}
}
entries.sort_by_key(|e| e.compressed_size);
let mut cands = match decompress_posting_list(
mmap,
entries[0].data_offset,
entries[0].compressed_size,
) {
Ok(locations) => locations,
Err(e) => {
log::warn!(
"Failed to decompress posting list for trigram {}: {}",
entries[0].trigram,
e
);
return vec![];
}
};
cands.dedup_by_key(|l| key(l));
for entry in &entries[1..] {
if cands.is_empty() {
break;
}
if allow_skip
&& entry.compressed_size as usize
> cands.len().saturating_mul(SKIP_BYTES_PER_CANDIDATE)
{
log::debug!(
"Intersection stopped early: {} candidates, next list {} bytes",
cands.len(),
entry.compressed_size
);
break;
}
let start = entry.data_offset as usize;
let end = start + entry.compressed_size as usize;
if end > mmap.len() {
log::warn!(
"Posting list out of bounds for trigram {}: offset={}, size={}, mmap_len={}",
entry.trigram,
entry.data_offset,
entry.compressed_size,
mmap.len()
);
return vec![];
}
let result = PostingCursor::new(&mmap[start..end])
.and_then(|mut cursor| intersect_with_cursor(&cands, &mut cursor));
match result {
Ok(next) => cands = next,
Err(e) => {
log::warn!(
"Failed to decompress posting list for trigram {}: {}",
entry.trigram,
e
);
return vec![];
}
}
}
cands
} else {
let mut posting_lists: Vec<&[FileLocation]> = Vec::with_capacity(trigrams.len());
for trigram in &trigrams {
match self.index.binary_search_by_key(trigram, |(t, _)| *t) {
Ok(idx) => posting_lists.push(&self.index[idx].1),
Err(_) => return vec![],
}
}
posting_lists.sort_by_key(|list| list.len());
if !allow_skip {
return intersect_sorted(&posting_lists);
}
let mut cands: Vec<FileLocation> = posting_lists[0].to_vec();
cands.dedup_by_key(|l| key(l));
for list in &posting_lists[1..] {
if cands.is_empty() {
break;
}
if list.len().saturating_mul(13) / 10
> cands.len().saturating_mul(SKIP_BYTES_PER_CANDIDATE)
{
break;
}
cands = intersect_two(&cands, list);
}
cands
}
}
pub fn search_candidates_fold(&self, literal: &[u8]) -> Vec<FileLocation> {
if literal.len() < 3 || !literal.is_ascii() {
return vec![];
}
let mut windows: Vec<Vec<Trigram>> = literal.windows(3).map(case_variants).collect();
windows.sort_unstable();
windows.dedup();
if let Some(ref mmap) = self.mmap {
let mut ws: Vec<(usize, Vec<DirectoryEntry>)> = Vec::with_capacity(windows.len());
for variants in &windows {
let entries: Vec<DirectoryEntry> = variants
.iter()
.filter_map(|t| self.find_entry(*t))
.collect();
if entries.is_empty() {
return vec![];
}
let weight = entries.iter().map(|e| e.compressed_size as usize).sum();
ws.push((weight, entries));
}
ws.sort_by_key(|w| w.0);
let t_lookup = std::time::Instant::now();
let mut cands: Vec<FileLocation> = Vec::new();
for entry in &ws[0].1 {
match decompress_posting_list(mmap, entry.data_offset, entry.compressed_size) {
Ok(list) => cands.extend(list),
Err(e) => {
log::warn!(
"Failed to decompress posting list for trigram {}: {}",
entry.trigram,
e
);
return vec![];
}
}
}
let t_decode = t_lookup.elapsed();
let raw = cands.len();
cands.sort_unstable();
cands.dedup_by_key(|l| key(l));
log::debug!(
"Fold first window: {} variants, {} bytes, {} raw postings -> {} keys; decode {:?}, sort+dedup {:?}",
ws[0].1.len(),
ws[0].0,
raw,
cands.len(),
t_decode,
t_lookup.elapsed() - t_decode
);
for (weight, entries) in &ws[1..] {
if cands.is_empty() {
break;
}
let cost = weight.saturating_add(entries.len().saturating_mul(cands.len()));
if cost > cands.len().saturating_mul(SKIP_BYTES_PER_CANDIDATE) {
log::debug!(
"Fold intersection stopped early: {} candidates, next window {} bytes x {} variants",
cands.len(),
weight,
entries.len()
);
break;
}
let mut keep = vec![false; cands.len()];
let mut window_ok = true;
for entry in entries {
let start = entry.data_offset as usize;
let end = start + entry.compressed_size as usize;
let result = if end > mmap.len() {
Err(anyhow::anyhow!("posting list out of bounds"))
} else {
PostingCursor::new(&mmap[start..end])
.and_then(|mut cur| mark_with_cursor(&cands, &mut cur, &mut keep))
};
if let Err(e) = result {
log::warn!(
"Failed to read posting list for trigram {}: {}; window skipped",
entry.trigram,
e
);
window_ok = false;
break;
}
}
if !window_ok {
continue;
}
cands = cands
.iter()
.zip(&keep)
.filter(|(_, k)| **k)
.map(|(c, _)| *c)
.collect();
}
cands
} else {
let mut ws: Vec<(usize, Vec<&[FileLocation]>)> = Vec::with_capacity(windows.len());
for variants in &windows {
let lists: Vec<&[FileLocation]> = variants
.iter()
.filter_map(|t| {
self.index
.binary_search_by_key(t, |(x, _)| *x)
.ok()
.map(|i| self.index[i].1.as_slice())
})
.collect();
if lists.is_empty() {
return vec![];
}
let weight = lists.iter().map(|l| l.len()).sum::<usize>() * 13 / 10;
ws.push((weight, lists));
}
ws.sort_by_key(|w| w.0);
let mut cands: Vec<FileLocation> =
ws[0].1.iter().flat_map(|l| l.iter().copied()).collect();
cands.sort_unstable();
cands.dedup_by_key(|l| key(l));
for (weight, lists) in &ws[1..] {
if cands.is_empty() {
break;
}
let cost = weight.saturating_add(lists.len().saturating_mul(cands.len()));
if cost > cands.len().saturating_mul(SKIP_BYTES_PER_CANDIDATE) {
break;
}
let mut next: Vec<FileLocation> = lists
.iter()
.flat_map(|l| intersect_two(&cands, l))
.collect();
next.sort_unstable();
next.dedup_by_key(|l| key(l));
cands = next;
}
cands
}
}
pub fn exotic_fold_lines(&self) -> Vec<FileLocation> {
const KELVIN: Trigram = 0xE2_84_AA;
const LONG_S_LO: Trigram = 0xC5_BF_00;
const LONG_S_HI: Trigram = 0xC5_BF_FF;
let mut out: Vec<FileLocation> = Vec::new();
if let Some(ref mmap) = self.mmap {
let mut entries: Vec<DirectoryEntry> = Vec::new();
entries.extend(self.find_entry(KELVIN));
entries.extend(self.dir_range(LONG_S_LO, LONG_S_HI));
for first in 0u32..=0xFF {
entries.extend(self.find_entry(first << 16 | 0xC5_BF));
}
for entry in entries {
match decompress_posting_list(mmap, entry.data_offset, entry.compressed_size) {
Ok(list) => out.extend(list),
Err(e) => log::warn!(
"Failed to decompress posting list for trigram {}: {}",
entry.trigram,
e
),
}
}
} else {
let lo = self.index.partition_point(|(t, _)| *t < LONG_S_LO);
let hi = self.index.partition_point(|(t, _)| *t <= LONG_S_HI);
for (_, list) in &self.index[lo..hi] {
out.extend(list.iter().copied());
}
let mut singles: Vec<Trigram> = (0u32..=0xFF).map(|f| f << 16 | 0xC5_BF).collect();
singles.push(KELVIN);
for t in singles {
if let Ok(i) = self.index.binary_search_by_key(&t, |(x, _)| *x) {
out.extend(self.index[i].1.iter().copied());
}
}
}
out.sort_unstable();
out.dedup_by_key(|l| key(l));
out
}
fn dir_range(&self, lo: Trigram, hi: Trigram) -> Vec<DirectoryEntry> {
let Some(mmap) = self.mmap.as_ref() else {
return vec![];
};
let at = |i: usize| read_u32(mmap, HEADER_SIZE + i * DIR_ENTRY_SIZE);
let (mut l, mut h) = (0usize, self.num_trigrams);
while l < h {
let mid = l + (h - l) / 2;
if at(mid) < lo {
l = mid + 1;
} else {
h = mid;
}
}
let mut out = Vec::new();
let mut i = l;
while i < self.num_trigrams {
let off = HEADER_SIZE + i * DIR_ENTRY_SIZE;
let trigram = read_u32(mmap, off);
if trigram > hi {
break;
}
out.push(DirectoryEntry {
trigram,
data_offset: read_u64(mmap, off + 4),
compressed_size: read_u32(mmap, off + 12),
});
i += 1;
}
out
}
pub fn search_files(&self, pattern: &str) -> Vec<u32> {
let mut files: Vec<u32> = self
.search(pattern)
.into_iter()
.map(|l| l.file_id)
.collect();
files.dedup();
files
}
pub fn get_posting_list(&self, trigram: Trigram) -> Option<&Vec<FileLocation>> {
self.index
.binary_search_by_key(&trigram, |(t, _)| *t)
.ok()
.map(|idx| &self.index[idx].1)
}
pub fn write(&mut self, path: impl AsRef<Path>) -> Result<()> {
let path = path.as_ref();
let tmp_path = crate::atomic_write::tmp_path_for(path);
let file = OpenOptions::new()
.create(true)
.write(true)
.truncate(true)
.open(&tmp_path)
.with_context(|| format!("Failed to create {}", tmp_path.display()))?;
let mut writer = std::io::BufWriter::with_capacity(16 * 1024 * 1024, file);
let data_start = (HEADER_SIZE + self.index.len() * DIR_ENTRY_SIZE) as u64;
let mut current_offset = data_start;
let mut directory: Vec<DirectoryEntry> = Vec::with_capacity(self.index.len());
let mut compressed_lists: Vec<Vec<u8>> = Vec::with_capacity(self.index.len());
for (trigram, locations) in &self.index {
let mut compressed = Vec::with_capacity(locations.len() + 16);
encode_posting_list(locations, &mut compressed)?;
directory.push(DirectoryEntry {
trigram: *trigram,
data_offset: current_offset,
compressed_size: compressed.len() as u32,
});
current_offset += compressed.len() as u64;
compressed_lists.push(compressed);
}
let paths_offset = current_offset;
writer.write_all(MAGIC)?;
writer.write_all(&VERSION.to_le_bytes())?;
writer.write_all(&(self.index.len() as u64).to_le_bytes())?; writer.write_all(&(self.files.len() as u64).to_le_bytes())?; writer.write_all(&paths_offset.to_le_bytes())?;
for entry in &directory {
writer.write_all(&entry.trigram.to_le_bytes())?;
writer.write_all(&entry.data_offset.to_le_bytes())?;
writer.write_all(&entry.compressed_size.to_le_bytes())?;
}
for compressed in &compressed_lists {
writer.write_all(compressed)?;
}
for file_path in &self.files {
let path_str = file_path.to_string_lossy();
let path_bytes = path_str.as_bytes();
write_varint(&mut writer, path_bytes.len() as u32)?;
writer.write_all(path_bytes)?;
}
writer.flush()?;
writer.get_ref().sync_all()?;
drop(writer);
crate::atomic_write::atomic_replace(&tmp_path, path)
.with_context(|| format!("Failed to move {} into place", path.display()))?;
log::info!(
"Wrote lazy-loadable trigram index: {} trigrams, {} files to {:?}",
self.index.len(),
self.files.len(),
path
);
Ok(())
}
pub fn load(path: impl AsRef<Path>) -> Result<Self> {
let path = path.as_ref();
let file =
File::open(path).with_context(|| format!("Failed to open {}", path.display()))?;
let mmap = unsafe {
memmap2::Mmap::map(&file)
.with_context(|| format!("Failed to mmap {}", path.display()))?
};
if mmap.len() < 8 {
anyhow::bail!(
"trigrams.bin too small (expected at least {} bytes)",
HEADER_SIZE
);
}
if &mmap[0..4] != MAGIC {
anyhow::bail!("Invalid trigrams.bin (wrong magic bytes)");
}
let version = read_u32(&mmap, 4);
if version != VERSION {
anyhow::bail!(
"Unsupported trigrams.bin version: {} (expected {}). Please re-index with 'reflex index'.",
version,
VERSION
);
}
if mmap.len() < HEADER_SIZE {
anyhow::bail!(
"trigrams.bin too small (expected at least {} bytes)",
HEADER_SIZE
);
}
let num_trigrams = read_u64(&mmap, NUM_TRIGRAMS_OFFSET) as usize;
let num_files = read_u64(&mmap, NUM_FILES_OFFSET) as usize;
let paths_offset = read_u64(&mmap, PATHS_OFFSET_OFFSET);
log::debug!(
"Loading lazy trigram index: {} trigrams, {} files",
num_trigrams,
num_files
);
let directory_end = num_trigrams
.checked_mul(DIR_ENTRY_SIZE)
.and_then(|d| d.checked_add(HEADER_SIZE))
.ok_or_else(|| anyhow::anyhow!("trigrams.bin directory size overflows"))?
as u64;
if directory_end > paths_offset || paths_offset > mmap.len() as u64 {
anyhow::bail!(
"trigrams.bin layout out of bounds: directory_end={}, paths_offset={}, len={}",
directory_end,
paths_offset,
mmap.len()
);
}
let mut pos = paths_offset as usize;
for _ in 0..num_files {
let (path_len, consumed) = read_varint(&mmap[pos..])?;
pos += consumed + path_len as usize;
if pos > mmap.len() {
anyhow::bail!("Truncated file path at pos={}", pos);
}
}
let files = Vec::new();
log::info!(
"Loaded lazy trigram index: {} trigrams, {} files (directory: {} KB, in mmap)",
num_trigrams,
num_files,
num_trigrams * DIR_ENTRY_SIZE / 1024
);
Ok(Self {
index: Vec::new(), files,
num_files,
paths_offset: paths_offset as usize,
lazy_paths: std::sync::OnceLock::new(),
temp_index: None,
mmap: Some(mmap), num_trigrams,
max_posting_list_entries: 0,
})
}
}
impl Default for TrigramIndex {
fn default() -> Self {
Self::new()
}
}
pub fn extract_trigrams(text: &str) -> Vec<Trigram> {
let bytes = text.as_bytes();
let mut trigrams = Vec::new();
for i in 0..bytes.len().saturating_sub(2) {
let trigram = bytes_to_trigram(&bytes[i..i + 3]);
trigrams.push(trigram);
}
trigrams
}
pub fn extract_trigrams_with_locations(text: &str, file_id: u32) -> Vec<(Trigram, FileLocation)> {
let mut result = Vec::with_capacity(text.len().saturating_sub(2));
scan_line_trigrams(text, |line_no, trigrams| {
let location = FileLocation::new(file_id, line_no);
result.extend(trigrams.iter().map(|&t| (t, location)));
});
result
}
pub(crate) fn scan_line_trigrams(text: &str, mut f: impl FnMut(u32, &[Trigram])) {
let bytes = text.as_bytes();
let mut line_trigrams: Vec<Trigram> = Vec::with_capacity(128);
let mut line_no: u32 = 1;
for (i, &byte) in bytes.iter().enumerate() {
if byte == b'\n' {
line_trigrams.sort_unstable();
line_trigrams.dedup();
f(line_no, &line_trigrams);
line_trigrams.clear();
line_no += 1;
}
if i + 2 < bytes.len() {
line_trigrams.push(bytes_to_trigram(&bytes[i..i + 3]));
}
}
line_trigrams.sort_unstable();
line_trigrams.dedup();
f(line_no, &line_trigrams);
}
#[inline]
fn bytes_to_trigram(bytes: &[u8]) -> Trigram {
debug_assert_eq!(bytes.len(), 3);
(bytes[0] as u32) << 16 | (bytes[1] as u32) << 8 | (bytes[2] as u32)
}
fn case_variants(window: &[u8]) -> Vec<Trigram> {
debug_assert_eq!(window.len(), 3);
let forms = |b: u8| -> Vec<u8> {
if b.is_ascii_alphabetic() {
vec![b.to_ascii_lowercase(), b.to_ascii_uppercase()]
} else {
vec![b]
}
};
let mut out = Vec::with_capacity(8);
for a in forms(window[0]) {
for b in forms(window[1]) {
for c in forms(window[2]) {
out.push(bytes_to_trigram(&[a, b, c]));
}
}
}
out.sort_unstable();
out.dedup();
out
}
#[allow(dead_code)]
fn trigram_to_bytes(trigram: Trigram) -> [u8; 3] {
[
((trigram >> 16) & 0xFF) as u8,
((trigram >> 8) & 0xFF) as u8,
(trigram & 0xFF) as u8,
]
}
#[inline]
fn key(l: &FileLocation) -> (u32, u32) {
(l.file_id, l.line_no)
}
fn intersect_two(a: &[FileLocation], b: &[FileLocation]) -> Vec<FileLocation> {
let mut out = Vec::with_capacity(a.len().min(b.len()));
let gallop = b.len() > 8 * a.len();
let (mut i, mut j) = (0, 0);
while i < a.len() && j < b.len() {
let ka = key(&a[i]);
match key(&b[j]).cmp(&ka) {
std::cmp::Ordering::Less => {
if gallop {
j += b[j..].partition_point(|x| key(x) < ka);
} else {
j += 1;
}
}
std::cmp::Ordering::Greater => i += 1,
std::cmp::Ordering::Equal => {
out.push(a[i]);
i += 1;
j += 1;
while j < b.len() && key(&b[j]) == ka {
j += 1;
}
}
}
}
out
}
pub(crate) fn intersect_sorted(lists: &[&[FileLocation]]) -> Vec<FileLocation> {
let Some((first, rest)) = lists.split_first() else {
return vec![];
};
let mut cands = first.to_vec();
cands.dedup_by_key(|l| key(l));
for list in rest {
if cands.is_empty() {
break;
}
cands = intersect_two(&cands, list);
}
cands
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn search_candidates_is_a_superset_of_search() {
let mut index = TrigramIndex::new();
for f in 0..20u32 {
let id = index.add_file(PathBuf::from(format!("f{f}.rs")));
let mut text = String::new();
for i in 0..200 {
text.push_str(&format!("let ident_{} = ident_{}; // filler\n", i, i + 1));
}
text.push_str("let ident_7 = 1;\n");
index.index_file(id, &text);
}
index.finalize();
let exact = index.search("ident_7");
let cands = index.search_candidates("ident_7");
assert!(!exact.is_empty());
let exact_keys: std::collections::HashSet<_> = exact.iter().map(key).collect();
let cand_keys: std::collections::HashSet<_> = cands.iter().map(key).collect();
assert!(
exact_keys.is_subset(&cand_keys),
"candidates must cover every match"
);
let dir = tempfile::tempdir().unwrap();
let path = dir.path().join("trigrams.bin");
index.write(&path).unwrap();
let lazy = TrigramIndex::load(&path).unwrap();
let lazy_exact: std::collections::HashSet<_> =
lazy.search("ident_7").iter().map(key).collect();
let lazy_cands: std::collections::HashSet<_> =
lazy.search_candidates("ident_7").iter().map(key).collect();
assert_eq!(lazy_exact, exact_keys);
assert!(lazy_exact.is_subset(&lazy_cands));
}
#[test]
fn search_candidates_fold_covers_case_insensitive_matches() {
let mut index = TrigramIndex::new();
let mut texts: Vec<String> = Vec::new();
for f in 0..10u32 {
let id = index.add_file(PathBuf::from(format!("f{f}.rs")));
let mut text = String::new();
for i in 0..100 {
text.push_str(&format!("let ident_{} = other_{}; // filler\n", i, i + 1));
}
text.push_str("let RealmId = 1;\n");
text.push_str("let realmId = 2;\n");
text.push_str("let REALMID = 3;\n");
text.push_str("let realm_id = 4;\n");
text.push_str("let kelvin = 5;\n");
text.push_str("let \u{212A}elvin = 6;\n");
text.push_str("let \u{017F}tatus = 7;\n");
text.push_str("let STATUS = 8;\n");
index.index_file(id, &text);
texts.push(text);
}
index.finalize();
let dir = tempfile::tempdir().unwrap();
let path = dir.path().join("trigrams.bin");
index.write(&path).unwrap();
let lazy = TrigramIndex::load(&path).unwrap();
for literal in ["realmid", "kelvin", "status", "REALM_ID"] {
let re = regex::Regex::new(&format!("(?i){}", literal)).unwrap();
let mut expected = std::collections::HashSet::new();
for (f, text) in texts.iter().enumerate() {
for (i, line) in text.lines().enumerate() {
if re.is_match(line) {
expected.insert((f as u32, i as u32 + 1));
}
}
}
assert!(!expected.is_empty(), "{literal}");
let has_ks = literal
.bytes()
.any(|b| matches!(b.to_ascii_lowercase(), b'k' | b's'));
for (name, idx) in [("memory", &index), ("lazy", &lazy)] {
let mut cands: std::collections::HashSet<_> = idx
.search_candidates_fold(literal.as_bytes())
.iter()
.map(key)
.collect();
if has_ks {
cands.extend(idx.exotic_fold_lines().iter().map(key));
}
assert!(
expected.is_subset(&cands),
"{name}: fold candidates for {literal:?} miss {:?}",
expected.difference(&cands).collect::<Vec<_>>()
);
}
}
assert!(
regex::Regex::new("(?i)kelvin")
.unwrap()
.is_match("\u{212A}elvin")
);
assert!(
regex::Regex::new("(?i)status")
.unwrap()
.is_match("\u{017F}tatus")
);
let ascii_only: std::collections::HashSet<_> = lazy
.search_candidates_fold(b"kelvin")
.iter()
.map(key)
.collect();
assert!(
!ascii_only.contains(&(0, 106)),
"line 106 is the Kelvin-sign line"
);
assert_eq!(lazy.exotic_fold_lines().len(), 20);
assert_eq!(index.exotic_fold_lines(), lazy.exotic_fold_lines());
assert!(lazy.search_candidates_fold(b"zzqx_absent").is_empty());
assert!(lazy.search_candidates_fold("straße".as_bytes()).is_empty());
}
use tempfile::TempDir;
#[test]
fn test_extract_trigrams() {
let text = "hello";
let trigrams = extract_trigrams(text);
assert_eq!(trigrams.len(), 3);
let expected = vec![
bytes_to_trigram(b"hel"),
bytes_to_trigram(b"ell"),
bytes_to_trigram(b"llo"),
];
assert_eq!(trigrams, expected);
}
#[test]
fn test_extract_trigrams_short() {
assert_eq!(extract_trigrams("ab").len(), 0);
assert_eq!(extract_trigrams("abc").len(), 1);
}
#[test]
fn test_bytes_to_trigram() {
let trigram1 = bytes_to_trigram(b"abc");
let trigram2 = bytes_to_trigram(b"abc");
let trigram3 = bytes_to_trigram(b"xyz");
assert_eq!(trigram1, trigram2);
assert_ne!(trigram1, trigram3);
}
#[test]
fn test_trigram_roundtrip() {
let original = b"foo";
let trigram = bytes_to_trigram(original);
let recovered = trigram_to_bytes(trigram);
assert_eq!(original, &recovered);
}
#[test]
fn test_extract_with_locations() {
let text = "hello\nworld";
let locs = extract_trigrams_with_locations(text, 0);
assert_eq!(locs.len(), 9);
assert_eq!(locs.iter().filter(|(_, l)| l.line_no == 1).count(), 5);
assert_eq!(locs.iter().filter(|(_, l)| l.line_no == 2).count(), 4);
assert!(locs.iter().all(|(_, l)| l.file_id == 0));
let line_of = |t: &[u8; 3]| {
locs.iter()
.find(|(tri, _)| *tri == bytes_to_trigram(t))
.map(|(_, l)| l.line_no)
};
assert_eq!(line_of(b"hel"), Some(1));
assert_eq!(line_of(b"o\nw"), Some(1));
assert_eq!(line_of(b"\nwo"), Some(2));
assert_eq!(line_of(b"wor"), Some(2));
}
#[test]
fn test_extract_emits_one_posting_per_distinct_trigram_per_line() {
let locs = extract_trigrams_with_locations("aaaa\naaaa", 3);
assert_eq!(locs.len(), 5);
let aaa = bytes_to_trigram(b"aaa");
let aaa_lines: Vec<u32> = locs
.iter()
.filter(|(t, _)| *t == aaa)
.map(|(_, l)| l.line_no)
.collect();
assert_eq!(aaa_lines, vec![1, 2]);
let mut keys: Vec<(Trigram, u32, u32)> = locs
.iter()
.map(|(t, l)| (*t, l.file_id, l.line_no))
.collect();
let n = keys.len();
keys.sort_unstable();
keys.dedup();
assert_eq!(keys.len(), n, "duplicate (trigram, line) postings emitted");
assert!(locs.iter().all(|(_, l)| l.file_id == 3));
let indented = " x\n y\n";
let sp = bytes_to_trigram(b" ");
let spaces = extract_trigrams_with_locations(indented, 0);
assert_eq!(spaces.iter().filter(|(t, _)| *t == sp).count(), 2);
}
#[test]
fn test_trigram_index_basic() {
let mut index = TrigramIndex::new();
let file_id = index.add_file(PathBuf::from("test.txt"));
index.index_file(file_id, "hello world");
index.finalize();
let results = index.search("hello");
assert!(!results.is_empty());
let results = index.search("world");
assert!(!results.is_empty());
let results = index.search("goodbye");
assert!(results.is_empty());
}
#[test]
fn test_search_multifile() {
let mut index = TrigramIndex::new();
let file1 = index.add_file(PathBuf::from("file1.txt"));
let file2 = index.add_file(PathBuf::from("file2.txt"));
index.index_file(file1, "extract_symbols is here");
index.index_file(file2, "extract_symbols is also here");
index.finalize();
let results = index.search("extract_symbols");
assert_eq!(results.len(), 2);
let file_ids: Vec<u32> = results.iter().map(|loc| loc.file_id).collect();
assert!(file_ids.contains(&file1));
assert!(file_ids.contains(&file2));
}
#[test]
fn test_persistence_write_header() {
let temp = TempDir::new().unwrap();
let trigrams_path = temp.path().join("trigrams.bin");
let mut index = TrigramIndex::new();
let file1 = index.add_file(PathBuf::from("src/main.rs"));
let file2 = index.add_file(PathBuf::from("src/lib.rs"));
index.index_file(file1, "fn main() { println!(\"hello\"); }");
index.index_file(
file2,
"pub fn hello() -> String { String::from(\"hello\") }",
);
index.finalize();
let num_trigrams = index.trigram_count() as u64;
index.write(&trigrams_path).unwrap();
let bytes = std::fs::read(&trigrams_path).unwrap();
assert!(bytes.len() > HEADER_SIZE);
assert_eq!(&bytes[0..4], MAGIC);
assert_eq!(read_u32(&bytes, 4), VERSION);
assert_eq!(read_u64(&bytes, NUM_TRIGRAMS_OFFSET), num_trigrams);
assert_eq!(read_u64(&bytes, NUM_FILES_OFFSET), 2);
let paths_offset = read_u64(&bytes, PATHS_OFFSET_OFFSET) as usize;
assert!(paths_offset >= HEADER_SIZE + num_trigrams as usize * DIR_ENTRY_SIZE);
assert!(paths_offset < bytes.len());
let (len, consumed) = read_varint(&bytes[paths_offset..]).unwrap();
let first = &bytes[paths_offset + consumed..paths_offset + consumed + len as usize];
assert_eq!(first, b"src/main.rs");
}
fn loc(file_id: u32, line_no: u32) -> FileLocation {
FileLocation::new(file_id, line_no)
}
fn load_err(path: &Path) -> String {
match TrigramIndex::load(path) {
Ok(_) => panic!("load unexpectedly succeeded"),
Err(e) => e.to_string(),
}
}
#[test]
fn test_intersect_two_empty() {
let a = [loc(0, 1), loc(1, 2)];
assert!(intersect_two(&a, &[]).is_empty());
assert!(intersect_two(&[], &a).is_empty());
assert!(intersect_two(&[], &[]).is_empty());
}
#[test]
fn test_intersect_two_disjoint() {
let a = [loc(0, 1), loc(0, 3), loc(2, 1)];
let b = [loc(0, 2), loc(1, 1), loc(2, 2)];
assert!(intersect_two(&a, &b).is_empty());
assert!(intersect_two(&b, &a).is_empty());
}
#[test]
fn test_intersect_two_duplicate_keys_in_b() {
let a = [loc(0, 1), loc(0, 2), loc(1, 1)];
let b = [
loc(0, 1),
loc(0, 1),
loc(0, 1),
loc(1, 1),
loc(1, 1),
loc(1, 2),
];
assert_eq!(intersect_two(&a, &b), vec![loc(0, 1), loc(1, 1)]);
}
#[test]
fn test_intersect_two_gallop_path() {
let b: Vec<FileLocation> = (0u32..200).map(|i| loc(i / 10, i % 10 + 1)).collect();
assert_eq!(intersect_two(&[loc(7, 4)], &b), vec![loc(7, 4)]);
assert!(intersect_two(&[loc(7, 11)], &b).is_empty());
assert!(intersect_two(&[loc(20, 1)], &b).is_empty());
let a = [loc(0, 1), loc(5, 5), loc(12, 3), loc(19, 10), loc(25, 1)];
assert_eq!(
intersect_two(&a, &b),
vec![loc(0, 1), loc(5, 5), loc(12, 3), loc(19, 10)]
);
}
#[test]
fn test_intersect_two_all_equal() {
let a: Vec<FileLocation> = (0u32..50).map(|i| loc(i, 1)).collect();
let b: Vec<FileLocation> = (0u32..50).map(|i| loc(i, 1)).collect();
assert_eq!(intersect_two(&a, &b), a);
}
struct Lcg(u64);
impl Lcg {
fn next(&mut self) -> u32 {
self.0 = self
.0
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
(self.0 >> 33) as u32
}
}
fn random_sorted_list(rng: &mut Lcg, n: usize) -> Vec<FileLocation> {
let mut list: Vec<FileLocation> = (0..n)
.map(|_| loc(rng.next() % 40, rng.next() % 60 + 1))
.collect();
list.sort_unstable();
list.dedup();
list
}
fn reference_intersection(lists: &[&[FileLocation]]) -> Vec<FileLocation> {
use std::collections::HashSet;
let mut keys: HashSet<(u32, u32)> = lists[0].iter().map(key).collect();
for list in &lists[1..] {
let set: HashSet<(u32, u32)> = list.iter().map(key).collect();
keys.retain(|k| set.contains(k));
}
let mut out: Vec<FileLocation> = keys
.iter()
.map(|k| *lists[0].iter().find(|l| key(l) == *k).unwrap())
.collect();
out.sort_unstable();
out
}
#[test]
fn test_intersect_sorted_matches_reference() {
let mut rng = Lcg(0x5eed);
for _ in 0..5 {
let lists: Vec<Vec<FileLocation>> = (0..3)
.map(|_| random_sorted_list(&mut rng, 2_000))
.collect();
let mut refs: Vec<&[FileLocation]> = lists.iter().map(|l| l.as_slice()).collect();
refs.sort_by_key(|l| l.len());
let expected = reference_intersection(&refs);
assert!(!expected.is_empty(), "test data should overlap");
assert_eq!(intersect_sorted(&refs), expected);
}
}
fn random_word_index(seed: u64) -> TrigramIndex {
let mut rng = Lcg(seed);
let mut index = TrigramIndex::new();
for i in 0..40 {
index.add_file(PathBuf::from(format!("f{i}.txt")));
}
let words = ["realm", "real", "alma", "lmn", "rea", "xyz", "ealm"];
for file_id in 0..40u32 {
let mut content = String::new();
for _ in 0..60 {
for _ in 0..4 {
content.push_str(words[(rng.next() % words.len() as u32) as usize]);
content.push(' ');
}
content.push('\n');
}
index.index_file(file_id, &content);
}
index.finalize();
index
}
#[test]
fn test_lazy_search_matches_in_memory() {
let mut index = random_word_index(0xbeef);
let temp = TempDir::new().unwrap();
let path = temp.path().join("trigrams.bin");
index.write(&path).unwrap();
let lazy = TrigramIndex::load(&path).unwrap();
assert_eq!(lazy.trigram_count(), index.trigram_count());
assert_eq!(lazy.file_count(), 40);
assert_eq!(lazy.get_file(39), Some(&PathBuf::from("f39.txt")));
assert_eq!(lazy.get_file(40), None);
for pattern in ["realm", "alma", "xyz", "lmn r", "ealm x", "nothing", "ab"] {
assert_eq!(
lazy.search(pattern),
index.search(pattern),
"pattern {pattern:?}"
);
assert_eq!(lazy.search_files(pattern), index.search_files(pattern));
}
let files = lazy.search_files("realm");
assert!(!files.is_empty());
assert!(files.windows(2).all(|w| w[0] < w[1]), "sorted, distinct");
}
#[test]
fn test_find_entry_zero_copy_directory() {
let mut index = random_word_index(0xf00d);
let temp = TempDir::new().unwrap();
let path = temp.path().join("trigrams.bin");
index.write(&path).unwrap();
let lazy = TrigramIndex::load(&path).unwrap();
assert!(index.find_entry(bytes_to_trigram(b"rea")).is_none());
let rea = bytes_to_trigram(b"rea");
let entry = lazy.find_entry(rea).expect("rea is indexed");
assert_eq!(entry.trigram, rea);
let expected_len = index.get_posting_list(rea).unwrap().len();
let decoded = decompress_posting_list(
lazy.mmap.as_ref().unwrap(),
entry.data_offset,
entry.compressed_size,
)
.unwrap();
assert_eq!(decoded.len(), expected_len);
assert_eq!(&decoded, index.get_posting_list(rea).unwrap());
assert!(lazy.find_entry(bytes_to_trigram(b"zzz")).is_none());
assert!(lazy.find_entry(0).is_none());
assert!(lazy.find_entry(u32::MAX).is_none());
}
#[test]
fn test_search_repeated_trigram_returns_line_once() {
let mut index = TrigramIndex::new();
let file_id = index.add_file(PathBuf::from("a.txt"));
index.index_file(file_id, "x\naaaa\ny");
index.finalize();
let results = index.search("aaaa");
assert_eq!(results, vec![loc(file_id, 2)]);
let temp = TempDir::new().unwrap();
let path = temp.path().join("trigrams.bin");
index.write(&path).unwrap();
let lazy = TrigramIndex::load(&path).unwrap();
assert_eq!(lazy.search("aaaa"), results);
}
#[test]
fn test_posting_list_block_encoding_roundtrip() {
let locations = vec![
loc(0, 1),
loc(0, 7),
loc(0, 300),
loc(3, 2),
loc(70_000, 1),
loc(70_000, 2),
];
let mut data = Vec::new();
encode_posting_list(&locations, &mut data).unwrap();
assert_eq!(
data,
vec![0, 6, 1, 6, 0xA5, 0x02, 3, 2, 2, 0xED, 0xA2, 0x04, 4, 1, 1]
);
assert_eq!(
decompress_posting_list(&data, 0, data.len() as u32).unwrap(),
locations
);
let mut cursor = PostingCursor::new(&data).unwrap();
assert_eq!(cursor.current(), Some(loc(0, 1)));
assert_eq!(cursor.seek((0, 7)).unwrap(), Some(loc(0, 7)));
assert_eq!(cursor.seek((4, 1)).unwrap(), Some(loc(70_000, 1)));
assert_eq!(cursor.advance().unwrap(), Some(loc(70_000, 2)));
assert_eq!(cursor.seek((70_000, 2)).unwrap(), Some(loc(70_000, 2)));
assert_eq!(cursor.seek((70_001, 0)).unwrap(), None);
assert_eq!(cursor.current(), None);
let mut cursor = PostingCursor::new(&data).unwrap();
assert_eq!(cursor.seek((0, 8)).unwrap(), Some(loc(0, 300)));
assert_eq!(cursor.seek((3, 1)).unwrap(), Some(loc(3, 2)));
}
#[test]
fn test_posting_list_empty_and_malformed() {
let mut data = Vec::new();
encode_posting_list(&[], &mut data).unwrap();
assert!(data.is_empty());
assert!(decompress_posting_list(&data, 0, 0).unwrap().is_empty());
let empty = PostingCursor::new(&[]).unwrap();
assert_eq!(empty.current(), None);
assert!(PostingCursor::new(&[0x80]).is_err());
assert!(PostingCursor::new(&[0, 2]).is_err());
assert!(decompress_posting_list(&[0, 2, 1], 0, 4).is_err());
let enc1 = [0u8, (1 << 1) | 1, 1];
let err = match PostingCursor::new(&enc1) {
Ok(_) => panic!("enc=1 block was accepted"),
Err(e) => e.to_string(),
};
assert!(err.contains("unsupported block encoding"), "{err}");
assert!(decompress_posting_list(&enc1, 0, 3).is_err());
let with_empty_block = [0u8, 0, 2, 1 << 1, 5];
assert_eq!(
decompress_posting_list(&with_empty_block, 0, 5).unwrap(),
vec![loc(2, 5)]
);
}
#[test]
fn test_v4_roundtrip_file_block_boundaries() {
let mut index = TrigramIndex::new();
for i in 0..6 {
index.add_file(PathBuf::from(format!("dir/file{i}.rs")));
}
let with = "needle here\nnothing\nneedle again\n\nneedle\n";
let without = "haystack\nonly\n";
index.index_file(0, with);
index.index_file(1, without);
index.index_file(2, with);
index.index_file(3, without);
index.index_file(4, with);
index.index_file(5, "haystack\nneedle");
index.finalize();
let expected = vec![
loc(0, 1),
loc(0, 3),
loc(0, 5),
loc(2, 1),
loc(2, 3),
loc(2, 5),
loc(4, 1),
loc(4, 3),
loc(4, 5),
loc(5, 2),
];
assert_eq!(index.search("needle"), expected);
let temp = TempDir::new().unwrap();
let path = temp.path().join("trigrams.bin");
index.write(&path).unwrap();
let lazy = TrigramIndex::load(&path).unwrap();
assert_eq!(lazy.search("needle"), expected);
assert_eq!(lazy.search_files("needle"), vec![0, 2, 4, 5]);
assert_eq!(
lazy.search("haystack"),
vec![loc(1, 1), loc(3, 1), loc(5, 1)]
);
assert_eq!(
lazy.search("needle again"),
vec![loc(0, 3), loc(2, 3), loc(4, 3)]
);
assert!(lazy.search("needle haystack").is_empty());
assert_eq!(lazy.file_count(), 6);
assert_eq!(lazy.get_file(5), Some(&PathBuf::from("dir/file5.rs")));
}
#[test]
fn test_v4_roundtrip_empty_index() {
let temp = TempDir::new().unwrap();
let path = temp.path().join("trigrams.bin");
let mut index = TrigramIndex::new();
index.finalize();
index.write(&path).unwrap();
let lazy = TrigramIndex::load(&path).unwrap();
assert_eq!(lazy.trigram_count(), 0);
assert_eq!(lazy.file_count(), 0);
assert!(lazy.search("anything").is_empty());
let mut index = TrigramIndex::new();
let f = index.add_file(PathBuf::from("tiny.txt"));
index.index_file(f, "ab");
index.finalize();
index.write(&path).unwrap();
let lazy = TrigramIndex::load(&path).unwrap();
assert_eq!(lazy.trigram_count(), 0);
assert_eq!(lazy.file_count(), 1);
assert!(lazy.search("abc").is_empty());
}
#[test]
fn test_load_rejects_v3_version() {
let temp = TempDir::new().unwrap();
let path = temp.path().join("trigrams.bin");
let mut bytes = Vec::new();
bytes.extend_from_slice(MAGIC);
bytes.extend_from_slice(&3u32.to_le_bytes());
bytes.extend_from_slice(&0u64.to_le_bytes());
bytes.extend_from_slice(&0u64.to_le_bytes());
std::fs::write(&path, &bytes).unwrap();
let err = load_err(&path);
assert!(
err.contains("Unsupported trigrams.bin version: 3 (expected 4)"),
"{err}"
);
assert!(err.contains("re-index"), "{err}");
std::fs::write(&path, b"NOPE\x04\x00\x00\x00").unwrap();
let err = load_err(&path);
assert!(err.contains("wrong magic"), "{err}");
}
#[test]
fn test_load_rejects_truncated_or_inconsistent_file() {
let mut index = random_word_index(0xd00d);
let temp = TempDir::new().unwrap();
let path = temp.path().join("trigrams.bin");
index.write(&path).unwrap();
let full = std::fs::read(&path).unwrap();
assert!(TrigramIndex::load(&path).is_ok());
std::fs::write(&path, &full[..full.len() / 2]).unwrap();
let err = load_err(&path);
assert!(err.contains("out of bounds"), "{err}");
std::fs::write(&path, &full[..10]).unwrap();
let err = load_err(&path);
assert!(err.contains("too small"), "{err}");
std::fs::write(&path, &full[..full.len() - 3]).unwrap();
let err = load_err(&path);
assert!(err.contains("Truncated"), "{err}");
let mut bad = full.clone();
bad[NUM_TRIGRAMS_OFFSET..NUM_TRIGRAMS_OFFSET + 8]
.copy_from_slice(&(u64::MAX / 32).to_le_bytes());
std::fs::write(&path, &bad).unwrap();
let err = load_err(&path);
assert!(err.contains("out of bounds"), "{err}");
}
#[test]
fn test_posting_list_cap_enforced() {
let cap: usize = 10;
let content = "aaa \n".repeat(200);
let mut index = TrigramIndex::new();
index.set_max_posting_list_entries(cap);
let file_id = index.add_file(PathBuf::from("dense.txt"));
index.index_file(file_id, &content);
index.finalize();
let aaa = bytes_to_trigram(b"aaa");
let list = index
.get_posting_list(aaa)
.expect("aaa trigram should exist");
assert!(list.len() <= cap, "cap exceeded: {} > {}", list.len(), cap);
}
#[test]
fn test_posting_list_cap_zero_means_unlimited() {
let repetitions = 50;
let content = "aaa \n".repeat(repetitions);
let mut index = TrigramIndex::new();
index.set_max_posting_list_entries(0);
let file_id = index.add_file(PathBuf::from("dense.txt"));
index.index_file(file_id, &content);
index.finalize();
let aaa = bytes_to_trigram(b"aaa");
let list = index
.get_posting_list(aaa)
.expect("aaa trigram should exist");
assert!(
list.len() >= repetitions,
"expected >= {} entries, got {}",
repetitions,
list.len()
);
}
}