use std::collections::{HashMap, HashSet};
use crate::live_index::store::IndexedFile;
pub struct TrigramIndex {
map: HashMap<[u8; 3], Vec<u64>>,
id_to_path: HashMap<u64, String>,
path_to_id: HashMap<String, u64>,
next_id: u64,
}
impl TrigramIndex {
pub fn new() -> Self {
Self {
map: HashMap::new(),
id_to_path: HashMap::new(),
path_to_id: HashMap::new(),
next_id: 0,
}
}
pub fn build_from_files<V>(files: &HashMap<String, V>) -> Self
where
V: AsRef<IndexedFile>,
{
let mut idx = Self::new();
for (path, file) in files {
idx.insert_file(path, &file.as_ref().content);
}
idx
}
pub fn search<V>(&self, query: &[u8], files: &HashMap<String, V>) -> Vec<String>
where
V: AsRef<IndexedFile>,
{
if query.is_empty() {
return Vec::new();
}
if query.len() < 3 {
return self.linear_scan(query, files);
}
let trigrams = extract_trigrams(query);
let mut posting_lists: Vec<&Vec<u64>> =
trigrams.iter().filter_map(|t| self.map.get(t)).collect();
if posting_lists.is_empty() {
return Vec::new();
}
posting_lists.sort_by_key(|l| l.len());
let mut candidates: Vec<u64> = posting_lists[0].clone();
for list in &posting_lists[1..] {
candidates.retain(|id| list.binary_search(id).is_ok());
if candidates.is_empty() {
return Vec::new();
}
}
candidates
.into_iter()
.filter_map(|id| {
let path = self.id_to_path.get(&id)?;
let file = files.get(path)?;
let content_lower: Vec<u8> = file
.as_ref()
.content
.iter()
.map(|b| b.to_ascii_lowercase())
.collect();
let query_lower: Vec<u8> = query.iter().map(|b| b.to_ascii_lowercase()).collect();
if contains_bytes(&content_lower, &query_lower) {
Some(path.clone())
} else {
None
}
})
.collect()
}
pub fn update_file(&mut self, path: &str, content: &[u8]) {
if self.path_to_id.contains_key(path) {
self.remove_trigrams_for_path(path);
}
let file_id = self.get_or_alloc_id(path);
let trigrams = extract_trigrams(content);
for tg in trigrams {
let list = self.map.entry(tg).or_default();
match list.binary_search(&file_id) {
Ok(_) => {} Err(pos) => list.insert(pos, file_id),
}
}
}
pub fn remove_file(&mut self, path: &str) {
if !self.path_to_id.contains_key(path) {
return; }
self.remove_trigrams_for_path(path);
let id = self.path_to_id.remove(path).unwrap();
self.id_to_path.remove(&id);
}
fn linear_scan<V>(&self, query: &[u8], files: &HashMap<String, V>) -> Vec<String>
where
V: AsRef<IndexedFile>,
{
let query_lower: Vec<u8> = query.iter().map(|b| b.to_ascii_lowercase()).collect();
files
.iter()
.filter_map(|(path, file)| {
let content_lower: Vec<u8> = file
.as_ref()
.content
.iter()
.map(|b| b.to_ascii_lowercase())
.collect();
if contains_bytes(&content_lower, &query_lower) {
Some(path.clone())
} else {
None
}
})
.collect()
}
fn remove_trigrams_for_path(&mut self, path: &str) {
let id = match self.path_to_id.get(path) {
Some(&id) => id,
None => return,
};
self.map.retain(|_, list| {
if let Ok(pos) = list.binary_search(&id) {
list.remove(pos);
}
!list.is_empty()
});
}
fn get_or_alloc_id(&mut self, path: &str) -> u64 {
if let Some(&id) = self.path_to_id.get(path) {
return id;
}
let id = self.next_id;
self.next_id += 1;
self.path_to_id.insert(path.to_string(), id);
self.id_to_path.insert(id, path.to_string());
id
}
fn insert_file(&mut self, path: &str, content: &[u8]) {
let file_id = self.get_or_alloc_id(path);
let trigrams = extract_trigrams(content);
for tg in trigrams {
let list = self.map.entry(tg).or_default();
match list.binary_search(&file_id) {
Ok(_) => {}
Err(pos) => list.insert(pos, file_id),
}
}
}
}
impl Default for TrigramIndex {
fn default() -> Self {
Self::new()
}
}
fn extract_trigrams(bytes: &[u8]) -> HashSet<[u8; 3]> {
let bytes_lower: Vec<u8> = bytes.iter().map(|b| b.to_ascii_lowercase()).collect();
if bytes_lower.len() < 3 {
return HashSet::new();
}
bytes_lower.windows(3).map(|w| [w[0], w[1], w[2]]).collect()
}
fn contains_bytes(haystack: &[u8], needle: &[u8]) -> bool {
if needle.is_empty() {
return true;
}
if needle.len() > haystack.len() {
return false;
}
haystack.windows(needle.len()).any(|w| w == needle)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::domain::LanguageId;
use crate::live_index::store::{IndexedFile, ParseStatus};
fn make_file(path: &str, content: &[u8]) -> (String, IndexedFile) {
(
path.to_string(),
IndexedFile {
relative_path: path.to_string(),
language: LanguageId::Rust,
classification: crate::domain::FileClassification::for_code_path(path),
content: content.to_vec(),
symbols: vec![],
parse_status: ParseStatus::Parsed,
parse_diagnostic: None,
byte_len: content.len() as u64,
content_hash: "test".to_string(),
references: vec![],
alias_map: std::collections::HashMap::new(),
mtime_secs: 0,
},
)
}
fn make_files(pairs: &[(&str, &[u8])]) -> HashMap<String, IndexedFile> {
pairs.iter().map(|(p, c)| make_file(p, c)).collect()
}
#[test]
fn test_build_from_files_indexes_all_content() {
let files = make_files(&[
("src/a.rs", b"fn parse_file() {}"),
("src/b.rs", b"fn render() {}"),
]);
let idx = TrigramIndex::build_from_files(&files);
assert_eq!(idx.path_to_id.len(), 2);
let par: [u8; 3] = [b'p', b'a', b'r'];
assert!(
idx.map.contains_key(&par),
"trigram 'par' must be indexed from 'parse'"
);
}
#[test]
fn test_search_returns_files_containing_query() {
let files = make_files(&[
("parser.rs", b"fn parse_source() {}"),
("render.rs", b"fn render_frame() {}"),
]);
let idx = TrigramIndex::build_from_files(&files);
let results = idx.search(b"parse", &files);
assert!(
results.contains(&"parser.rs".to_string()),
"parser.rs should match 'parse'"
);
assert!(
!results.contains(&"render.rs".to_string()),
"render.rs should not match 'parse'"
);
}
#[test]
fn test_search_returns_empty_for_trigram_not_in_any_file() {
let files = make_files(&[("a.rs", b"fn alpha() {}"), ("b.rs", b"fn beta() {}")]);
let idx = TrigramIndex::build_from_files(&files);
let results = idx.search(b"zzz", &files);
assert!(
results.is_empty(),
"should return empty vec for unknown trigram"
);
}
#[test]
fn test_search_short_query_falls_back_to_linear_scan() {
let files = make_files(&[("foo.rs", b"fn abc() {}"), ("bar.rs", b"fn xyz() {}")]);
let idx = TrigramIndex::build_from_files(&files);
let results = idx.search(b"a", &files);
assert!(
results.contains(&"foo.rs".to_string()),
"linear scan: 'a' matches 'abc'"
);
assert!(
!results.contains(&"bar.rs".to_string()),
"linear scan: 'a' does not match 'xyz'"
);
}
#[test]
fn test_search_two_char_query_falls_back_to_linear_scan() {
let files = make_files(&[("a.rs", b"fn fn_alpha() {}"), ("b.rs", b"fn fn_beta() {}")]);
let idx = TrigramIndex::build_from_files(&files);
let results = idx.search(b"al", &files);
assert!(
results.contains(&"a.rs".to_string()),
"linear scan: 'al' in fn_alpha"
);
assert!(
!results.contains(&"b.rs".to_string()),
"linear scan: 'al' not in fn_beta"
);
}
#[test]
fn test_search_empty_query_returns_empty() {
let files = make_files(&[("a.rs", b"fn foo() {}")]);
let idx = TrigramIndex::build_from_files(&files);
let results = idx.search(b"", &files);
assert!(results.is_empty(), "empty query must return empty vec");
}
#[test]
fn test_search_and_intersection_correct() {
let files = make_files(&[
("alpha_only.rs", b"fn alpha() {}"),
("beta_only.rs", b"fn beta() {}"),
("ab.rs", b"fn alpha() {} fn beta() {}"),
]);
let idx = TrigramIndex::build_from_files(&files);
let alpha_results = idx.search(b"alpha", &files);
assert!(alpha_results.contains(&"alpha_only.rs".to_string()));
assert!(alpha_results.contains(&"ab.rs".to_string()));
assert!(!alpha_results.contains(&"beta_only.rs".to_string()));
let beta_results = idx.search(b"beta", &files);
assert!(beta_results.contains(&"beta_only.rs".to_string()));
assert!(beta_results.contains(&"ab.rs".to_string()));
assert!(!beta_results.contains(&"alpha_only.rs".to_string()));
}
#[test]
fn test_search_empty_index_returns_empty() {
let idx = TrigramIndex::new();
let files: HashMap<String, IndexedFile> = HashMap::new();
let results = idx.search(b"anything", &files);
assert!(results.is_empty(), "empty index should return empty vec");
}
#[test]
fn test_update_file_removes_old_trigrams_and_adds_new() {
let files = make_files(&[("src/main.rs", b"fn old_function() {}")]);
let mut idx = TrigramIndex::build_from_files(&files);
let old_results = idx.search(b"old_function", &files);
assert!(old_results.contains(&"src/main.rs".to_string()));
idx.update_file("src/main.rs", b"fn new_function() {}");
let mut new_files = files;
new_files.get_mut("src/main.rs").unwrap().content = b"fn new_function() {}".to_vec();
let old_results = idx.search(b"old_function", &new_files);
assert!(
!old_results.contains(&"src/main.rs".to_string()),
"old trigrams must be removed"
);
let new_results = idx.search(b"new_function", &new_files);
assert!(
new_results.contains(&"src/main.rs".to_string()),
"new trigrams must be indexed"
);
}
#[test]
fn test_update_file_reuses_existing_file_id() {
let files = make_files(&[("src/lib.rs", b"fn alpha() {}")]);
let mut idx = TrigramIndex::build_from_files(&files);
let id_before = *idx.path_to_id.get("src/lib.rs").unwrap();
idx.update_file("src/lib.rs", b"fn beta() {}");
let id_after = *idx.path_to_id.get("src/lib.rs").unwrap();
assert_eq!(
id_before, id_after,
"update_file should reuse the existing file_id"
);
}
#[test]
fn test_remove_file_clears_all_trigrams() {
let files = make_files(&[
("keep.rs", b"fn keep_me() {}"),
("remove.rs", b"fn remove_me() {}"),
]);
let mut idx = TrigramIndex::build_from_files(&files);
idx.remove_file("remove.rs");
assert!(
!idx.path_to_id.contains_key("remove.rs"),
"path_to_id should not contain removed file"
);
let remove_results = idx.search(b"remove_me", &files);
assert!(
!remove_results.contains(&"remove.rs".to_string()),
"removed file should not appear in search"
);
let keep_results = idx.search(b"keep_me", &files);
assert!(
keep_results.contains(&"keep.rs".to_string()),
"other files should still be searchable"
);
}
#[test]
fn test_remove_file_nonexistent_is_noop() {
let files = make_files(&[("a.rs", b"fn foo() {}")]);
let mut idx = TrigramIndex::build_from_files(&files);
idx.remove_file("nonexistent.rs");
let results = idx.search(b"foo", &files);
assert!(results.contains(&"a.rs".to_string()));
}
#[test]
fn test_extract_trigrams_produces_correct_windows() {
let trigrams = extract_trigrams(b"abcd");
assert!(trigrams.contains(b"abc"), "should contain 'abc'");
assert!(trigrams.contains(b"bcd"), "should contain 'bcd'");
assert_eq!(trigrams.len(), 2, "abcd has 2 unique trigrams");
}
#[test]
fn test_extract_trigrams_short_bytes_empty() {
assert!(
extract_trigrams(b"ab").is_empty(),
"< 3 bytes yields no trigrams"
);
assert!(
extract_trigrams(b"").is_empty(),
"empty bytes yields no trigrams"
);
}
}