use std::collections::BTreeSet;
use std::path::{Path, PathBuf};
use std::sync::Arc;
const MAX_HEADER_DEPTH: usize = 6;
const MAX_HEADERS: usize = 12_000;
const HEADER_EXTENSIONS: &[&str] = &[
"h", "hh", "hpp", "hxx", "h++", "inl", "ipp", "tcc", "tpp", "inc", "def", "cppm", "ixx", "mpp",
"cuh",
];
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct Header {
pub name: String,
pub directory: usize,
pub depth: usize,
pub kind: HeaderKind,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum HeaderKind {
StandardLibrary,
Project,
System,
}
const STANDARD_LIBRARY_MARKER: &str = "vector";
fn is_the_standard_library(directory: &Path) -> bool {
directory.join(STANDARD_LIBRARY_MARKER).is_file()
}
#[derive(Debug, Clone, Default)]
pub struct HeaderIndex {
headers: Vec<Header>,
project: Vec<PathBuf>,
root: PathBuf,
unread: usize,
truncated: bool,
}
pub type SharedHeaders = Arc<std::sync::RwLock<HeaderIndex>>;
impl HeaderIndex {
pub const PROJECT: usize = usize::MAX;
pub fn read<I>(directories: I, root: &Path) -> HeaderIndex
where
I: IntoIterator<Item = PathBuf>,
{
let mut headers: Vec<Header> = Vec::new();
let mut names: BTreeSet<(String, usize)> = BTreeSet::new();
let mut unread = 0usize;
let mut truncated = false;
for (directory, root) in directories.into_iter().enumerate() {
let kind = if is_the_standard_library(&root) {
HeaderKind::StandardLibrary
} else {
HeaderKind::System
};
let mut pending: std::collections::VecDeque<(PathBuf, String, usize)> =
std::collections::VecDeque::from([(root.clone(), String::new(), 0)]);
while let Some((path, prefix, depth)) = pending.pop_front() {
if headers.len() >= MAX_HEADERS {
truncated = true;
break;
}
let Ok(entries) = std::fs::read_dir(&path) else {
unread += 1;
continue;
};
for entry in entries.flatten() {
let Ok(entry_kind) = entry.file_type() else {
continue;
};
if entry_kind.is_symlink() {
continue;
}
let Some(file_name) = entry.file_name().to_str().map(str::to_string) else {
continue;
};
let name = if prefix.is_empty() {
file_name.clone()
} else {
format!("{prefix}/{file_name}")
};
if entry_kind.is_dir() {
if depth < MAX_HEADER_DEPTH {
pending.push_back((entry.path(), name, depth + 1));
}
continue;
}
if !entry_kind.is_file() || !is_a_header(&file_name) {
continue;
}
if headers.len() >= MAX_HEADERS {
truncated = true;
break;
}
if names.insert((name.clone(), directory)) {
headers.push(Header {
name,
directory,
depth,
kind,
});
}
}
}
}
headers.sort_by(|one, other| {
one.name
.cmp(&other.name)
.then_with(|| one.directory.cmp(&other.directory))
});
HeaderIndex {
headers,
project: Vec::new(),
root: root.to_path_buf(),
unread,
truncated,
}
}
pub fn with_project(mut self, files: impl IntoIterator<Item = PathBuf>) -> HeaderIndex {
self.project = files
.into_iter()
.filter(|file| is_a_header(&file_name_of(file)))
.collect();
self.project.sort();
self.project.dedup();
self
}
pub fn matching(&self, prefix: &str, limit: usize) -> Vec<Header> {
let mut ranked: Vec<(HeaderKind, u8, u8, usize, String, usize)> = Vec::new();
for (name, directory, kind) in self.spellings() {
let Some(rank) = match_rank(&name, prefix) else {
continue;
};
let is_a_cxx_name =
u8::from(!(kind == HeaderKind::StandardLibrary && is_a_cxx_header(&name)));
let depth = if kind == HeaderKind::Project {
0
} else {
name.matches('/').count()
};
ranked.push((kind, rank, is_a_cxx_name, depth, name, directory));
}
ranked.sort();
ranked
.into_iter()
.take(limit)
.map(|(kind, _, _, _, name, directory)| Header {
depth: name.matches('/').count(),
name,
directory,
kind,
})
.collect()
}
fn spellings(&self) -> Vec<(String, usize, HeaderKind)> {
let mut found: Vec<(String, usize, HeaderKind)> = self
.project
.iter()
.map(|file| {
let spelling = file
.strip_prefix(&self.root)
.map(|relative| relative.to_string_lossy().replace('\\', "/"))
.unwrap_or_else(|_| file.to_string_lossy().replace('\\', "/"));
(spelling, Self::PROJECT, HeaderKind::Project)
})
.collect();
found.extend(
self.headers
.iter()
.map(|header| (header.name.clone(), header.directory, header.kind)),
);
found
}
pub fn len(&self) -> usize {
self.headers.len() + self.project.len()
}
pub fn is_empty(&self) -> bool {
self.headers.is_empty() && self.project.is_empty()
}
pub fn unread(&self) -> usize {
self.unread
}
pub fn truncated(&self) -> bool {
self.truncated
}
}
fn file_name_of(path: &Path) -> String {
path.file_name()
.map(|name| name.to_string_lossy().to_string())
.unwrap_or_default()
}
fn match_rank(name: &str, prefix: &str) -> Option<u8> {
if prefix.is_empty() {
return Some(0);
}
let prefix = prefix.to_ascii_lowercase();
let lowered = name.to_ascii_lowercase();
if lowered.split('/').any(|segment| segment == prefix) {
return Some(0);
}
if lowered
.split('/')
.any(|segment| segment.starts_with(&prefix))
{
return Some(1);
}
if lowered.split('/').any(|segment| segment.contains(&prefix)) {
return Some(2);
}
lowered.contains(&prefix).then_some(3)
}
fn is_a_header(file_name: &str) -> bool {
let Some((stem, extension)) = file_name.rsplit_once('.') else {
return !file_name.is_empty() && !file_name.starts_with('.');
};
if stem.is_empty() {
return false;
}
HEADER_EXTENSIONS
.iter()
.any(|known| extension.eq_ignore_ascii_case(known))
}
fn is_a_cxx_header(name: &str) -> bool {
!name.rsplit('/').next().unwrap_or(name).contains('.')
}
pub fn search_directories(config: &crate::CompilerConfig) -> Vec<PathBuf> {
config
.include_paths
.iter()
.map(|path| path.directory.clone())
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
fn index_of(names: &[&str]) -> HeaderIndex {
index_of_kind(names, HeaderKind::StandardLibrary)
}
fn index_of_kind(names: &[&str], kind: HeaderKind) -> HeaderIndex {
HeaderIndex {
headers: names
.iter()
.map(|name| Header {
name: name.to_string(),
directory: 0,
depth: name.matches('/').count(),
kind,
})
.collect(),
project: Vec::new(),
root: PathBuf::from("/p"),
unread: 0,
truncated: false,
}
}
#[test]
fn the_standard_library_comes_before_the_platform() {
let index = index_of_kind(&["bits/stl_vector.h", "sys/types.h"], HeaderKind::System);
let mut both = index;
both.headers.push(Header {
name: "vector".to_string(),
directory: 0,
depth: 0,
kind: HeaderKind::StandardLibrary,
});
let found: Vec<String> = both
.matching("v", 10)
.into_iter()
.map(|header| header.name)
.collect();
assert_eq!(
found,
vec!["vector", "bits/stl_vector.h"],
"measured on a real toolchain"
);
}
#[test]
fn a_standard_header_that_merely_contains_the_letters_beats_a_system_one_that_is_named_for_it()
{
let mut index = index_of_kind(&["STRALIGN.H"], HeaderKind::System);
index.headers.push(Header {
name: "string_view".to_string(),
directory: 0,
depth: 0,
kind: HeaderKind::StandardLibrary,
});
let found: Vec<String> = index
.matching("str", 10)
.into_iter()
.map(|header| header.name)
.collect();
assert_eq!(found, vec!["string_view", "STRALIGN.H"]);
}
#[test]
fn the_nearest_match_comes_first() {
let index = index_of(&[
"experimental/vector",
"bits/stl_vector.h",
"sys/types.h",
"vector",
"experimental/vector_thing.h",
]);
let found: Vec<String> = index
.matching("vector", 10)
.into_iter()
.map(|header| header.name)
.collect();
assert_eq!(
found,
vec![
"vector",
"experimental/vector",
"experimental/vector_thing.h",
"bits/stl_vector.h",
],
"the header named for the word, then the shallower of the two that begin with it, \
then the one that merely contains it"
);
}
#[test]
fn a_segment_that_starts_with_the_prefix_matches() {
let index = index_of(&["sys/types.h", "linux/types.h", "ctype.h"]);
let found: Vec<String> = index
.matching("types", 10)
.into_iter()
.map(|header| header.name)
.collect();
assert_eq!(found, vec!["linux/types.h", "sys/types.h"]);
}
#[test]
fn an_empty_prefix_offers_the_search_path_shallowest_first() {
let index = index_of(&["bits/stl_vector.h", "vector", "cstddef"]);
let found: Vec<String> = index
.matching("", 3)
.into_iter()
.map(|header| header.name)
.collect();
assert_eq!(
found,
vec!["cstddef", "vector", "bits/stl_vector.h"],
"the top level in spelling order, then the depth below it"
);
}
#[test]
fn a_wrong_prefix_matches_nothing() {
let index = index_of(&["vector"]);
assert!(index.matching("widget", 10).is_empty());
}
#[test]
fn a_header_without_an_extension_is_a_header() {
assert!(is_a_header("iostream"));
assert!(is_a_header("vector.hpp"));
assert!(is_a_header("stl_vector.h"));
assert!(!is_a_header(".gitignore"));
assert!(!is_a_header("main.cpp2"));
}
#[test]
fn a_directory_that_cannot_be_read_is_counted_rather_than_ignored() {
let index = HeaderIndex::read(
[PathBuf::from("/no/such/directory/exists/here")],
Path::new("/p"),
);
assert!(index.is_empty());
assert_eq!(index.unread(), 1, "the gap is recorded");
assert!(!index.truncated());
}
#[test]
fn the_standard_library_is_recognised_by_what_is_in_it() {
let here = Path::new(env!("CARGO_MANIFEST_DIR"));
assert!(
!is_the_standard_library(here),
"a crate directory does not hold the standard library"
);
assert!(
!is_the_standard_library(Path::new("/no/such/directory/exists/here")),
"and neither does one that does not exist"
);
}
#[test]
fn the_projects_own_headers_are_spelled_from_the_root_and_offered_first() {
let index = index_of_kind(&["version"], HeaderKind::System).with_project([
PathBuf::from("/p/config/version.h"),
PathBuf::from("/p/main.cpp"),
PathBuf::from("/p/vector"),
]);
let found: Vec<(String, usize)> = index
.matching("version", 10)
.into_iter()
.map(|header| (header.name, header.directory))
.collect();
assert_eq!(
found,
vec![
("config/version.h".to_string(), HeaderIndex::PROJECT),
("version".to_string(), 0),
],
"the project's own file first — a reader typing in a project means its own headers — and the \
search path's `version` beside it"
);
assert!(
index
.matching("", 10)
.iter()
.any(|header| header.name == "vector"),
"a header with no extension is a header of the project too"
);
assert!(
!index
.matching("", 10)
.iter()
.any(|header| header.name == "main.cpp"),
"and a source file is not"
);
}
}