use std::collections::HashMap;
use std::path::{Path, PathBuf};
use std::sync::{Arc, Mutex, OnceLock};
const MAX_DEPTH: usize = 8;
const MAX_FILES: usize = 200_000;
#[derive(Debug, Default)]
pub struct FuzzyIndex {
by_name: HashMap<String, Vec<PathBuf>>,
root: PathBuf,
}
fn cache() -> &'static Mutex<HashMap<PathBuf, Arc<FuzzyIndex>>> {
static CACHE: OnceLock<Mutex<HashMap<PathBuf, Arc<FuzzyIndex>>>> = OnceLock::new();
CACHE.get_or_init(|| Mutex::new(HashMap::new()))
}
pub fn index_for(root: &Path) -> Option<Arc<FuzzyIndex>> {
if let Ok(held) = cache().lock()
&& let Some(found) = held.get(root)
{
return Some(Arc::clone(found));
}
let built = Arc::new(FuzzyIndex::build(root));
if built.by_name.is_empty() {
return None;
}
if let Ok(mut held) = cache().lock() {
held.insert(root.to_path_buf(), Arc::clone(&built));
}
Some(built)
}
pub fn forget_everything() {
if let Ok(mut held) = cache().lock() {
held.clear();
}
}
impl FuzzyIndex {
fn build(root: &Path) -> FuzzyIndex {
let mut by_name: HashMap<String, Vec<PathBuf>> = HashMap::new();
let mut stack = vec![(root.to_path_buf(), 0usize)];
let mut files = 0usize;
while let Some((directory, depth)) = stack.pop() {
if depth > MAX_DEPTH || files >= MAX_FILES {
continue;
}
let Ok(entries) = std::fs::read_dir(&directory) else {
continue;
};
for entry in entries.flatten() {
let path = entry.path();
let Ok(kind) = entry.file_type() else {
continue;
};
if kind.is_dir() {
if is_generated(&path) {
continue;
}
stack.push((path, depth + 1));
} else if kind.is_file() {
let Some(name) = path
.file_name()
.map(|name| name.to_string_lossy().to_lowercase())
else {
continue;
};
files += 1;
by_name.entry(name).or_default().push(path);
}
}
}
FuzzyIndex {
by_name,
root: root.to_path_buf(),
}
}
pub fn matching(&self, written: &str) -> Vec<PathBuf> {
let Some(components) = wanted_components(written) else {
return Vec::new();
};
let Some(last) = components.last() else {
return Vec::new();
};
let Some(candidates) = self.by_name.get(last.as_str()) else {
return Vec::new();
};
let mut found: Vec<(usize, &PathBuf)> = candidates
.iter()
.filter(|candidate| ends_with_components(candidate, &components))
.map(|candidate| (candidate.components().count(), candidate))
.collect();
found
.sort_unstable_by(|left, right| left.0.cmp(&right.0).then_with(|| left.1.cmp(right.1)));
found.into_iter().map(|(_, path)| path.clone()).collect()
}
pub fn the_only_file_named(&self, written: &str) -> Option<PathBuf> {
let candidates = self.by_name.get(&written.to_lowercase())?;
if candidates.len() == 1 {
return candidates.first().cloned();
}
None
}
pub fn root(&self) -> &Path {
&self.root
}
pub fn len(&self) -> usize {
self.by_name.values().map(Vec::len).sum()
}
pub fn is_empty(&self) -> bool {
self.by_name.is_empty()
}
}
fn wanted_components(written: &str) -> Option<Vec<String>> {
let parts: Vec<String> = written
.split(['/', '\\'])
.filter(|part| !part.is_empty() && *part != ".")
.map(str::to_lowercase)
.collect();
if parts.len() < 2 {
return None;
}
Some(parts)
}
fn ends_with_components(candidate: &Path, components: &[String]) -> bool {
let parts: Vec<String> = candidate
.components()
.map(|part| part.as_os_str().to_string_lossy().to_lowercase())
.collect();
if parts.len() < components.len() {
return false;
}
let tail = &parts[parts.len() - components.len()..];
tail == components
}
fn is_generated(path: &Path) -> bool {
const GENERATED: [&str; 9] = [
"build",
"out",
".git",
".svn",
"cmakefiles",
"node_modules",
"target",
".cache",
"cmake-build-debug",
];
path.file_name()
.map(|name| name.to_string_lossy().to_lowercase())
.is_some_and(|name| GENERATED.contains(&name.as_str()))
}
#[cfg(test)]
mod tests {
use super::*;
fn root_with(name: &str, files: &[&str]) -> PathBuf {
let root = std::env::temp_dir().join("cppls-fuzzy-tests").join(name);
let _ = std::fs::remove_dir_all(&root);
for file in files {
let path = root.join(file);
std::fs::create_dir_all(path.parent().expect("a file has a parent"))
.expect("a directory");
std::fs::write(&path, "// a header\n").expect("a file");
}
root
}
#[test]
fn a_bare_file_name_is_never_matched() {
let root = root_with("bare", &["include/vector", "detail/vector"]);
let index = index_for(&root).expect("a root with files has an index");
assert!(index.matching("vector").is_empty());
assert!(index.matching("stdio.h").is_empty());
assert_eq!(index.matching("detail/vector").len(), 1);
}
#[test]
fn the_tail_is_matched_component_by_component() {
let root = root_with(
"tail",
&[
"CodeFormatServer/include/Session/StandardIOSession.h",
"other/Session/StandardIOSession.h",
"Session/StandardIOSession.h",
"not/Session/Other.h",
],
);
let index = index_for(&root).expect("an index");
let found = index.matching("Session/StandardIOSession.h");
assert_eq!(found.len(), 3);
assert!(
found
.iter()
.all(|path| path.ends_with("Session/StandardIOSession.h"))
);
}
#[test]
fn the_shallowest_match_comes_first() {
let root = root_with(
"shallow",
&[
"deep/nested/very/far/down/detail/config.h",
"detail/config.h",
],
);
let index = index_for(&root).expect("an index");
let found = index.matching("detail/config.h");
assert_eq!(found.len(), 2);
assert!(
found[0].ends_with("detail/config.h") && !found[0].to_string_lossy().contains("nested"),
"expected the shallow one first, got {:?}",
found[0]
);
}
#[test]
fn a_directory_that_merely_contains_the_word_does_not_match() {
let root = root_with("suffix", &["MySession/StandardIOSession.h"]);
let index = index_for(&root).expect("an index");
assert!(index.matching("Session/StandardIOSession.h").is_empty());
assert_eq!(index.matching("MySession/StandardIOSession.h").len(), 1);
}
#[test]
fn a_build_tree_is_not_indexed() {
let root = root_with(
"generated",
&[
"include/Widget.h",
"build/include/Widget.h",
"out/include/Widget.h",
],
);
let index = index_for(&root).expect("an index");
let found = index.matching("include/Widget.h");
assert_eq!(
found.len(),
1,
"expected only the written header, got {found:?}"
);
assert!(!found[0].to_string_lossy().contains("build"));
assert!(!found[0].to_string_lossy().contains("out"));
}
#[test]
fn a_root_with_nothing_in_it_has_no_index() {
let root = std::env::temp_dir().join("cppls-fuzzy-tests").join("empty");
let _ = std::fs::remove_dir_all(&root);
std::fs::create_dir_all(&root).expect("a directory");
assert!(index_for(&root).is_none());
}
}