use std::collections::{HashMap, HashSet, VecDeque};
use std::path::PathBuf;
use cpp_parser::{CppLexer, CppTokenKind, LexerConfig, SourceRange};
use crate::file::paths::{FileProvider, normalize_path};
use crate::index::ProjectIndex;
use crate::summary::MacroKind;
use crate::symbol::{Known, UnknownReason};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ReferenceBudget {
pub max_files: usize,
}
impl Default for ReferenceBudget {
fn default() -> Self {
ReferenceBudget { max_files: 4096 }
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MacroReferences {
pub name: String,
pub files: Vec<FileReferences>,
pub looked_at: usize,
pub without_the_name: usize,
pub rejected: usize,
pub not_looked_at: usize,
pub unreadable: Vec<PathBuf>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct FileReferences {
pub file: PathBuf,
pub references: Vec<Reference>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Reference {
pub range: SourceRange,
pub kind: ReferenceKind,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ReferenceKind {
Definition,
Declaration,
Undefinition,
Use { resolved_to: PathBuf },
Uncertain(UnknownReason),
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Rename {
pub file: PathBuf,
pub range: SourceRange,
pub replacement: String,
}
impl MacroReferences {
pub fn total(&self) -> usize {
self.files.iter().map(|file| file.references.len()).sum()
}
pub fn candidates(&self) -> usize {
self.looked_at + self.not_looked_at + self.unreadable.len()
}
pub fn lexed(&self) -> usize {
self.looked_at - self.without_the_name
}
pub fn uncertain(&self) -> usize {
self.files
.iter()
.flat_map(|file| &file.references)
.filter(|reference| matches!(reference.kind, ReferenceKind::Uncertain(_)))
.count()
}
pub fn rename(&self, to: &str) -> Vec<Rename> {
let mut edits = Vec::new();
for file in &self.files {
for reference in &file.references {
let certain = matches!(
reference.kind,
ReferenceKind::Definition
| ReferenceKind::Undefinition
| ReferenceKind::Use { .. }
);
if certain {
edits.push(Rename {
file: file.file.clone(),
range: reference.range,
replacement: to.to_string(),
});
}
}
}
edits
}
}
pub fn macro_references<F: FileProvider>(
index: &ProjectIndex,
files: &F,
name: &str,
budget: ReferenceBudget,
) -> Known<MacroReferences> {
let definers = files_defining(index, name);
if definers.is_empty() {
return Known::Unknown(UnknownReason::NotDeclaredHere(Box::from(name)));
}
let mut answer = MacroReferences {
name: name.to_string(),
files: Vec::new(),
looked_at: 0,
without_the_name: 0,
rejected: 0,
not_looked_at: 0,
unreadable: Vec::new(),
};
for path in candidates(index, &definers, budget, &mut answer) {
let mut references: Vec<Reference> = index
.summary(&path)
.map(|summary| {
summary
.macros
.iter()
.filter(|fact| fact.name == name)
.map(|fact| Reference {
range: fact.range,
kind: match fact.kind {
MacroKind::Definition => ReferenceKind::Definition,
MacroKind::Undefinition => ReferenceKind::Undefinition,
},
})
.collect()
})
.unwrap_or_default();
let Some(text) = files.read(&path) else {
answer.unreadable.push(path);
continue;
};
answer.looked_at += 1;
if !text.contains(name) {
answer.without_the_name += 1;
} else {
let claimed: HashSet<(usize, usize)> = references
.iter()
.filter(|reference| reference.kind == ReferenceKind::Definition)
.map(|reference| (reference.range.start_offset, reference.range.end_offset()))
.collect();
let undefinitions: Vec<usize> = references
.iter()
.enumerate()
.filter(|(_, reference)| reference.kind == ReferenceKind::Undefinition)
.map(|(index, _)| index)
.collect();
let environment = index.macro_environment(name, &path);
for range in identifiers(&text, name) {
if claimed.contains(&(range.start_offset, range.end_offset())) {
continue;
}
if let Some(named) = undefinitions
.iter()
.copied()
.find(|index| covers(references[*index].range, range))
{
references[named].range = range;
continue;
}
match environment.is_a_macro_at(range.start_offset) {
Known::Yes(found) => references.push(Reference {
range,
kind: ReferenceKind::Use {
resolved_to: found.file().to_path_buf(),
},
}),
Known::Unknown(reason @ UnknownReason::ConditionalCompilation) => {
references.push(Reference {
range,
kind: ReferenceKind::Uncertain(reason),
});
}
Known::Unknown(_) | Known::No => answer.rejected += 1,
}
}
}
if !references.is_empty() {
references.sort_by_key(|reference| reference.range.start_offset);
answer.files.push(FileReferences {
file: path,
references,
});
}
}
answer.files.sort_by(|one, other| one.file.cmp(&other.file));
Known::Yes(answer)
}
fn files_defining(index: &ProjectIndex, name: &str) -> Vec<PathBuf> {
index.files_defining_macro(name)
}
fn candidates(
index: &ProjectIndex,
definers: &[PathBuf],
budget: ReferenceBudget,
answer: &mut MacroReferences,
) -> Vec<PathBuf> {
let mut found: Vec<PathBuf> = Vec::new();
let mut seen: HashSet<String> = HashSet::new();
let mut pending: VecDeque<PathBuf> = definers.iter().cloned().collect();
while let Some(path) = pending.pop_front() {
if !seen.insert(normalize_path(&path, cfg!(windows))) {
continue;
}
if found.len() >= budget.max_files {
answer.not_looked_at += 1;
continue;
}
found.push(path.clone());
pending.extend(index.includers_of(&path));
}
found.sort();
found
}
fn covers(outer: SourceRange, inner: SourceRange) -> bool {
outer.start_offset <= inner.start_offset && inner.end_offset() <= outer.end_offset()
}
fn identifiers(text: &str, name: &str) -> Vec<SourceRange> {
let mut errors = Vec::new();
let mut lexer = CppLexer::new(text, LexerConfig::default(), &mut errors);
lexer
.tokenize()
.into_iter()
.filter(|token| token.kind == CppTokenKind::Identifier)
.filter(|token| text.get(token.range.start_offset..token.range.end_offset()) == Some(name))
.map(|token| token.range)
.collect()
}
pub fn symbol_references<F: FileProvider>(
index: &ProjectIndex,
files: &F,
symbol: &SymbolToFind,
budget: ReferenceBudget,
) -> Known<SymbolReferences> {
let mut answer = SymbolReferences {
name: symbol.name.clone(),
qualified: symbol.qualified.clone(),
declared_in: symbol.declared_in.clone(),
files: Vec::new(),
looked_at: 0,
without_the_name: 0,
not_looked_at: 0,
unreadable: Vec::new(),
};
let declared_at = declarations_of_the_spelling(index, symbol);
for path in symbol_candidates(index, symbol, budget, &mut answer) {
let Some(text) = files.read(&path) else {
answer.unreadable.push(path);
continue;
};
if !text.contains(&symbol.last_segment) {
answer.without_the_name += 1;
continue;
}
answer.looked_at += 1;
let here = identifiers(&text, &symbol.last_segment);
if here.is_empty() {
answer.without_the_name += 1;
continue;
}
let names_declared_here = declared_at.get(&normalize_path(&path, cfg!(windows)));
let references: Vec<Reference> = here
.into_iter()
.filter(|range| {
match names_declared_here.and_then(|declared| declared.get(&range.start_offset)) {
Some(qualified) => *qualified == symbol.qualified,
None => true,
}
})
.map(|range| {
let is_this_file = normalize_path(&path, cfg!(windows))
== normalize_path(&symbol.declared_in, cfg!(windows));
let kind = if is_this_file && range.start_offset == symbol.name_at {
ReferenceKind::Definition
} else if names_declared_here.is_some_and(|declared| {
declared.get(&range.start_offset) == Some(&symbol.qualified)
}) {
ReferenceKind::Declaration
} else {
ReferenceKind::Use {
resolved_to: symbol.declared_in.clone(),
}
};
Reference { range, kind }
})
.collect();
answer.files.push(FileReferences {
file: path,
references,
});
}
answer
.files
.sort_by(|left, right| left.file.cmp(&right.file));
Known::Yes(answer)
}
fn declarations_of_the_spelling(
index: &ProjectIndex,
symbol: &SymbolToFind,
) -> HashMap<String, HashMap<usize, String>> {
let mut declared: HashMap<String, HashMap<usize, String>> = HashMap::new();
for (path, fact) in index.every_fact_named(&symbol.last_segment) {
declared
.entry(normalize_path(&path, cfg!(windows)))
.or_default()
.insert(fact.name_range.start_offset, fact.qualified_name());
}
declared
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SymbolToFind {
pub name: String,
pub last_segment: String,
pub qualified: String,
pub declared_in: PathBuf,
pub name_at: usize,
pub local: bool,
}
impl SymbolToFind {
pub fn of(fact: &crate::summary::DeclFact, declared_in: PathBuf) -> Self {
let name = fact.name.to_string();
let last_segment = match name.rsplit_once("::") {
Some((_, last)) => last.to_string(),
None => name.to_string(),
};
SymbolToFind {
name,
last_segment,
qualified: fact.qualified_name(),
declared_in,
name_at: fact.name_range.start_offset,
local: fact.local,
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SymbolReferences {
pub name: String,
pub qualified: String,
pub declared_in: PathBuf,
pub files: Vec<FileReferences>,
pub looked_at: usize,
pub without_the_name: usize,
pub not_looked_at: usize,
pub unreadable: Vec<PathBuf>,
}
impl SymbolReferences {
pub fn all(&self) -> impl Iterator<Item = (&PathBuf, &Reference)> {
self.files.iter().flat_map(|file| {
file.references
.iter()
.map(move |reference| (&file.file, reference))
})
}
pub fn count(&self) -> usize {
self.files.iter().map(|file| file.references.len()).sum()
}
}
fn symbol_candidates(
index: &ProjectIndex,
symbol: &SymbolToFind,
budget: ReferenceBudget,
answer: &mut SymbolReferences,
) -> Vec<PathBuf> {
let mut roots: Vec<PathBuf> = vec![symbol.declared_in.clone()];
if !symbol.local {
roots.extend(
index
.files_declaring(&symbol.qualified, &symbol.declared_in)
.into_iter()
.map(|found| found.file),
);
}
if !symbol.local {
roots.extend(index.importers_of_the_module_of(&symbol.declared_in));
}
let mut found: Vec<PathBuf> = Vec::new();
let mut seen: HashSet<String> = HashSet::new();
let mut pending: VecDeque<PathBuf> = roots.into_iter().collect();
while let Some(path) = pending.pop_front() {
if !seen.insert(normalize_path(&path, cfg!(windows))) {
continue;
}
if found.len() >= budget.max_files {
answer.not_looked_at += 1;
continue;
}
found.push(path.clone());
pending.extend(index.includers_of(&path));
}
found.sort();
found
}
#[cfg(test)]
mod tests {
use super::{
ReferenceBudget, ReferenceKind, SymbolToFind, macro_references, symbol_references,
};
use crate::cache::SummaryKey;
use crate::file::paths::{FileProvider, MemoryFiles};
use crate::include::config::CompilerConfig;
use crate::include::graph::Marked;
use crate::index::{FileIndexer, ProjectIndex};
use crate::symbol::{Known, UnknownReason};
use std::path::Path;
fn index_of(files: &MemoryFiles, paths: &[&str]) -> ProjectIndex {
let config = CompilerConfig::default();
let indexer = FileIndexer::new(files, &config);
let mut index = ProjectIndex::new();
for path in paths {
let path = Path::new(path);
let source = files.read(path).expect("the fixture has the file");
index.insert(indexer.index(path, &source, SummaryKey::new(0, 0)));
}
index
}
fn defined(names: &[&str]) -> Marked {
let mut marked = Marked::default();
for name in names {
marked.define_on_the_command_line(name, None);
}
marked
}
fn shown(files: &MemoryFiles, index: &ProjectIndex, name: &str) -> Vec<String> {
match macro_references(index, files, name, ReferenceBudget::default()) {
Known::Yes(found) => found
.files
.iter()
.flat_map(|file| {
let text = files.read(&file.file).unwrap_or_default();
file.references.iter().map(move |reference| {
let kind = match &reference.kind {
ReferenceKind::Definition => "define".to_string(),
ReferenceKind::Declaration => "declare".to_string(),
ReferenceKind::Undefinition => "undef".to_string(),
ReferenceKind::Use { .. } => "use".to_string(),
ReferenceKind::Uncertain(_) => "maybe".to_string(),
};
format!(
"{}:{kind}:{}",
file.file.file_name().unwrap().to_string_lossy(),
&text[reference.range.start_offset..reference.range.end_offset()]
)
})
})
.collect(),
Known::Unknown(reason) => vec![format!("unknown: {}", reason.describe())],
Known::No => vec!["no".to_string()],
}
}
fn fixture() -> MemoryFiles {
MemoryFiles::new()
.with_file("/p/api.h", "#define API int\n")
.with_file("/p/main.cpp", "#include \"api.h\"\nAPI f() { return 0; }\n")
.with_file("/p/guarded.h", "#define GUARDED int\n")
.with_file(
"/p/cond.cpp",
"#if defined(X)\n#include \"guarded.h\"\n#endif\nGUARDED g() { return 0; }\n",
)
}
const FIXTURE_FILES: &[&str] = &["/p/api.h", "/p/main.cpp", "/p/guarded.h", "/p/cond.cpp"];
fn symbol_shown(
files: &MemoryFiles,
index: &ProjectIndex,
symbol: &SymbolToFind,
) -> Vec<String> {
match symbol_references(index, files, symbol, ReferenceBudget::default()) {
Known::Yes(found) => found
.all()
.map(|(file, reference)| {
let text = files.read(file).unwrap_or_default();
let line = text[..reference.range.start_offset.min(text.len())]
.matches('\n')
.count();
format!(
"{}:{line}:{}",
file.file_name().unwrap().to_string_lossy(),
&text[reference.range.start_offset..reference.range.end_offset()]
)
})
.collect(),
Known::Unknown(reason) => vec![format!("unknown: {}", reason.describe())],
Known::No => vec!["no".to_string()],
}
}
#[test]
fn a_declaration_in_a_module_interface_is_referenced_from_the_importer() {
let files = MemoryFiles::new()
.with_file(
"/p/math.cppm",
"export module math;\nnamespace math {\nexport struct Point {\n double length_squared() const;\n};\n}\n",
)
.with_file(
"/p/main.cpp",
"import math;\nvoid f(math::Point p) { p.length_squared(); }\n",
);
let index = index_of(&files, &["/p/math.cppm", "/p/main.cpp"]);
let source = files
.read(Path::new("/p/math.cppm"))
.expect("the interface unit");
let at = source
.find("length_squared")
.expect("the declaration's name");
let symbol = SymbolToFind {
name: "length_squared".to_string(),
last_segment: "length_squared".to_string(),
qualified: "math::Point::length_squared".to_string(),
declared_in: std::path::PathBuf::from("/p/math.cppm"),
name_at: at,
local: false,
};
let shown = symbol_shown(&files, &index, &symbol);
assert!(
shown.iter().any(|line| line.starts_with("main.cpp:")),
"the importer's use is in the list: {shown:?}"
);
assert!(
shown.iter().any(|line| line.starts_with("math.cppm:")),
"and the declaration itself: {shown:?}"
);
}
#[test]
fn a_symbols_references_are_every_place_its_name_is_written() {
let files = MemoryFiles::new()
.with_file("/p/sux.h", "class Sux {\npublic:\n void print();\n};\n")
.with_file(
"/p/main.cpp",
"#include \"sux.h\"\nSux sux;\n// Sux in a comment\nconst char* s = \"Sux\";\nvoid f() { sux.print(); }\n",
);
let index = index_of(&files, &["/p/sux.h", "/p/main.cpp"]);
let class = SymbolToFind {
name: "Sux".to_string(),
last_segment: "Sux".to_string(),
qualified: "Sux".to_string(),
declared_in: std::path::PathBuf::from("/p/sux.h"),
name_at: 6,
local: false,
};
assert_eq!(
symbol_shown(&files, &index, &class),
vec![
"main.cpp:1:Sux".to_string(),
"sux.h:0:Sux".to_string(),
],
"a class is used in the file that includes its header, and in no comment"
);
let object = SymbolToFind {
name: "sux".to_string(),
last_segment: "sux".to_string(),
qualified: "sux".to_string(),
declared_in: std::path::PathBuf::from("/p/main.cpp"),
name_at: 23,
local: false,
};
assert_eq!(
symbol_shown(&files, &index, &object),
vec!["main.cpp:1:sux".to_string(), "main.cpp:4:sux".to_string(),],
"an object declared at file scope is used in the function below it"
);
}
#[test]
fn another_entity_declaration_of_the_same_spelling_is_not_a_reference() {
let files = MemoryFiles::new()
.with_file(
"/p/name.h",
"struct Name {\n void printf(int i);\n};\nvoid Name::printf(int i) { }\n",
)
.with_file("/p/stdio.h", "void printf(const char* format, ...);\n")
.with_file(
"/p/main.cpp",
"#include \"name.h\"\n#include \"stdio.h\"\nvoid f() { printf(\"x\"); }\n",
);
let index = index_of(&files, &["/p/name.h", "/p/stdio.h", "/p/main.cpp"]);
let global = SymbolToFind {
name: "printf".to_string(),
last_segment: "printf".to_string(),
qualified: "printf".to_string(),
declared_in: std::path::PathBuf::from("/p/stdio.h"),
name_at: 5,
local: false,
};
assert_eq!(
symbol_shown(&files, &index, &global),
vec![
"main.cpp:2:printf".to_string(),
"stdio.h:0:printf".to_string(),
],
"`Name::printf`'s declaration and its definition are a different entity"
);
}
#[test]
fn a_use_in_the_file_that_includes_the_definition_is_found() {
let files = fixture();
let index = index_of(&files, FIXTURE_FILES);
assert_eq!(
shown(&files, &index, "API"),
["api.h:define:API", "main.cpp:use:API"],
"the definition and the one use, in path order"
);
}
#[test]
fn a_name_in_a_comment_or_a_string_is_not_a_reference() {
let files = MemoryFiles::new()
.with_file("/p/api.h", "#define API int\n")
.with_file(
"/p/main.cpp",
"#include \"api.h\"\n// API is a macro\nconst char* s = \"API\";\nAPI f() { return 0; }\n",
);
let index = index_of(&files, &["/p/api.h", "/p/main.cpp"]);
assert_eq!(
shown(&files, &index, "API"),
["api.h:define:API", "main.cpp:use:API"]
);
match macro_references(&index, &files, "API", ReferenceBudget::default()) {
Known::Yes(found) => assert_eq!(
found.rejected, 0,
"a comment and a string are not even candidates for rejection: they are not identifiers"
),
other => panic!("the macro is indexed, got {other:?}"),
}
}
#[test]
fn a_name_after_an_undef_is_rejected_rather_than_reported() {
let files = MemoryFiles::new()
.with_file("/p/api.h", "#define API int\n")
.with_file(
"/p/main.cpp",
"#include \"api.h\"\n#undef API\nint API = 1;\n",
);
let index = index_of(&files, &["/p/api.h", "/p/main.cpp"]);
assert_eq!(
shown(&files, &index, "API"),
["api.h:define:API", "main.cpp:undef:API"],
"the `#undef` is a reference, and it points at the *name* — not at the whole line, which is what the \
directive reader recorded and what a rename must not replace"
);
match macro_references(&index, &files, "API", ReferenceBudget::default()) {
Known::Yes(found) => assert_eq!(found.rejected, 1, "and the rejection is counted"),
other => panic!("the macro is indexed, got {other:?}"),
}
}
#[test]
fn a_condition_is_decided_by_a_define_the_closure_wrote_earlier() {
let files = MemoryFiles::new()
.with_file("/p/config.h", "#define ABI 1\n#define FEATURE\n")
.with_file(
"/p/widget.h",
"#include \"config.h\"\n#if ABI == 1\n#include \"modern.h\"\n#endif\n\
#ifdef FEATURE\n#include \"feature.h\"\n#endif\n",
)
.with_file("/p/modern.h", "#define MODERN int\n")
.with_file("/p/feature.h", "#define FEATURE_ONLY int\n")
.with_file(
"/p/main.cpp",
"#include \"widget.h\"\nMODERN a;\nFEATURE_ONLY b;\n",
);
let index = index_of(
&files,
&[
"/p/config.h",
"/p/widget.h",
"/p/modern.h",
"/p/feature.h",
"/p/main.cpp",
],
);
assert_eq!(
shown(&files, &index, "MODERN"),
["main.cpp:use:MODERN", "modern.h:define:MODERN"],
"the value is read out of `config.h`, so the `#if` is taken and the include is certain"
);
assert_eq!(
shown(&files, &index, "FEATURE_ONLY"),
["feature.h:define:FEATURE_ONLY", "main.cpp:use:FEATURE_ONLY"],
"and a name defined with no body at all is enough for an `#ifdef`"
);
}
#[test]
fn a_condition_about_a_define_that_comes_later_after_the_include_is_not_decided() {
let files = MemoryFiles::new()
.with_file("/p/config.h", "#define ABI 1\n")
.with_file(
"/p/widget.h",
"#if ABI == 1\n#include \"modern.h\"\n#endif\n#include \"config.h\"\n",
)
.with_file("/p/modern.h", "#define MODERN int\n")
.with_file("/p/main.cpp", "#include \"widget.h\"\nMODERN a;\n");
let index = index_of(
&files,
&["/p/config.h", "/p/widget.h", "/p/modern.h", "/p/main.cpp"],
);
assert_eq!(
shown(&files, &index, "MODERN"),
["main.cpp:maybe:MODERN", "modern.h:define:MODERN"],
"at the `#if` the name was not defined yet: the include may or may not have happened"
);
}
#[test]
fn a_define_inside_a_region_the_walk_cannot_decide_does_not_decide_a_later_condition() {
let files = MemoryFiles::new()
.with_file(
"/p/widget.h",
"#ifdef SETTING\n#define WIDE 1\n#endif\n#if WIDE == 1\n#include \"wide.h\"\n#endif\n",
)
.with_file("/p/wide.h", "#define WIDE_ONLY int\n")
.with_file("/p/main.cpp", "#include \"widget.h\"\nWIDE_ONLY a;\n");
let index = index_of(&files, &["/p/widget.h", "/p/wide.h", "/p/main.cpp"]);
assert_eq!(
shown(&files, &index, "WIDE_ONLY"),
["main.cpp:maybe:WIDE_ONLY", "wide.h:define:WIDE_ONLY"],
"the value came from a branch nobody can decide"
);
}
#[test]
fn a_define_inside_a_settled_region_is_in_force_without_its_value() {
let files = MemoryFiles::new()
.with_file(
"/p/widget.h",
"int early;\n#ifndef WIDE\n#define WIDE 1\n#endif\n\
#ifdef WIDE\n#include \"named.h\"\n#endif\n#if WIDE == 1\n#include \"valued.h\"\n#endif\n",
)
.with_file("/p/named.h", "#define NAMED int\n")
.with_file("/p/valued.h", "#define VALUED int\n")
.with_file("/p/main.cpp", "#include \"widget.h\"\nNAMED a;\nVALUED b;\n");
let index = index_of(
&files,
&["/p/widget.h", "/p/named.h", "/p/valued.h", "/p/main.cpp"],
);
assert_eq!(
shown(&files, &index, "NAMED"),
["main.cpp:use:NAMED", "named.h:define:NAMED"],
"definedness is settled by the shape"
);
assert_eq!(
shown(&files, &index, "VALUED"),
["main.cpp:maybe:VALUED", "valued.h:define:VALUED"],
"the value is not: the other branch could have defined it as anything"
);
}
#[test]
fn a_guard_on_a_name_nothing_defines_is_taken_when_the_caller_declares_the_inputs_complete() {
let files = MemoryFiles::new()
.with_file("/p/winnt.h", "#define WIN_ONLY int\n")
.with_file(
"/p/windef.cpp",
"int early;\n#ifndef NT_INCLUDED\n#include \"winnt.h\"\n#endif\nWIN_ONLY x;\n",
);
let index =
index_of(&files, &["/p/winnt.h", "/p/windef.cpp"]).with_macros(Marked::default());
assert_eq!(
shown(&files, &index, "WIN_ONLY"),
["windef.cpp:use:WIN_ONLY", "winnt.h:define:WIN_ONLY"],
"the guard is not taken, so the include is in the translation unit"
);
}
#[test]
fn an_include_that_did_not_resolve_takes_the_completeness_claim_back() {
let files = MemoryFiles::new()
.with_file(
"/p/windef.cpp",
"#include \"nowhere_to_be_found.h\"\nint early;\n\
#ifndef NT_INCLUDED\n#include \"winnt.h\"\n#endif\nWIN_ONLY x;\n",
)
.with_file("/p/winnt.h", "#define WIN_ONLY int\n");
let index =
index_of(&files, &["/p/winnt.h", "/p/windef.cpp"]).with_macros(Marked::default());
assert_eq!(
shown(&files, &index, "WIN_ONLY"),
["windef.cpp:maybe:WIN_ONLY", "winnt.h:define:WIN_ONLY"],
"the unresolved include could have defined `NT_INCLUDED`, so the guard is undecided"
);
}
#[test]
fn a_use_reached_through_a_conditional_include_is_certain_when_the_environment_decides_it() {
let files = fixture();
let index = index_of(&files, FIXTURE_FILES).with_macros(defined(&["X"]));
assert_eq!(
shown(&files, &index, "GUARDED"),
["cond.cpp:use:GUARDED", "guarded.h:define:GUARDED"],
"no `maybe`: the include is in the translation unit"
);
}
#[test]
fn a_use_reached_through_an_include_the_environment_rules_out_is_not_a_use() {
let files = MemoryFiles::new()
.with_file("/p/skipped.h", "#define SKIPPED int\n")
.with_file(
"/p/never.cpp",
"#if 0\n#include \"skipped.h\"\n#endif\nSKIPPED x;\n",
);
let index = index_of(&files, &["/p/skipped.h", "/p/never.cpp"]);
assert_eq!(
shown(&files, &index, "SKIPPED"),
["skipped.h:define:SKIPPED"],
"only the definition: the include is not in the translation unit"
);
}
#[test]
fn a_guard_on_a_name_nothing_defines_is_still_unknown_rather_than_untaken() {
let files = MemoryFiles::new()
.with_file("/p/winnt.h", "#define WIN_ONLY int\n")
.with_file(
"/p/windef.cpp",
"int early;\n#ifndef NT_INCLUDED\n#include \"winnt.h\"\n#endif\nWIN_ONLY x;\n",
);
let index = index_of(&files, &["/p/winnt.h", "/p/windef.cpp"]);
assert_eq!(
shown(&files, &index, "WIN_ONLY"),
["windef.cpp:maybe:WIN_ONLY", "winnt.h:define:WIN_ONLY"],
"the include may have happened, so the use may be a use"
);
}
#[test]
fn a_definition_the_environment_rules_out_is_not_a_candidate() {
let files = MemoryFiles::new()
.with_file("/p/api.h", "#if 0\n#define API int\n#endif\n")
.with_file("/p/main.cpp", "#include \"api.h\"\nAPI f();\n");
let index = index_of(&files, &["/p/api.h", "/p/main.cpp"]);
assert_eq!(
shown(&files, &index, "API"),
["api.h:define:API"],
"the `#define` is a fact about the text, and the use is not a use"
);
}
#[test]
fn a_use_reached_through_a_conditional_include_is_uncertain() {
let files = fixture();
let index = index_of(&files, FIXTURE_FILES);
assert_eq!(
shown(&files, &index, "GUARDED"),
["cond.cpp:maybe:GUARDED", "guarded.h:define:GUARDED"],
"path order, so `cond.cpp` comes first"
);
match macro_references(&index, &files, "GUARDED", ReferenceBudget::default()) {
Known::Yes(found) => {
assert_eq!(found.uncertain(), 1);
assert_eq!(
found.rename("OTHER").len(),
1,
"only the definition is certain"
);
}
other => panic!("the macro is indexed, got {other:?}"),
}
}
#[test]
fn a_file_that_cannot_see_the_macro_is_not_even_read() {
let files = fixture().with_file("/p/other.cpp", "API f() { return 0; }\n");
let index = index_of(
&files,
&[
"/p/api.h",
"/p/main.cpp",
"/p/other.cpp",
"/p/guarded.h",
"/p/cond.cpp",
],
);
assert_eq!(
shown(&files, &index, "API"),
["api.h:define:API", "main.cpp:use:API"]
);
assert_eq!(
files.reads_of("/p/other.cpp"),
1,
"read once, by the indexer — and never by the query"
);
}
#[test]
fn a_candidate_whose_text_has_no_such_name_is_filtered_before_the_lexer() {
let files = fixture().with_file("/p/quiet.cpp", "#include \"api.h\"\nint x;\n");
let index = index_of(&files, &["/p/api.h", "/p/main.cpp", "/p/quiet.cpp"]);
match macro_references(&index, &files, "API", ReferenceBudget::default()) {
Known::Yes(found) => {
assert_eq!(
found.looked_at, 3,
"three candidates: both files and the definition"
);
assert_eq!(
found.without_the_name, 1,
"and one of them has no `API` in it"
);
}
other => panic!("the macro is indexed, got {other:?}"),
}
}
#[test]
fn a_name_no_file_defines_is_unknown_rather_than_empty() {
let files = fixture();
let index = index_of(&files, FIXTURE_FILES);
assert_eq!(
macro_references(&index, &files, "NOTHING", ReferenceBudget::default()),
Known::Unknown(UnknownReason::NotDeclaredHere(Box::from("NOTHING")))
);
}
#[test]
fn a_candidate_that_cannot_be_read_is_reported_rather_than_dropped() {
let files = fixture();
let index = index_of(&files, FIXTURE_FILES);
let nothing = MemoryFiles::new();
match macro_references(&index, ¬hing, "API", ReferenceBudget::default()) {
Known::Yes(found) => {
assert_eq!(found.looked_at, 0);
assert_eq!(
found.unreadable.len(),
2,
"the definer and the file that includes it — the closure comes from the index, not from reading"
);
assert_eq!(found.candidates(), 2, "and they are still the candidates");
assert_eq!(found.total(), 0);
}
other => panic!("the macro is indexed, got {other:?}"),
}
}
#[test]
fn the_counters_add_up_to_the_ladder_they_describe() {
let files = fixture().with_file("/p/quiet.cpp", "#include \"api.h\"\nint x;\n");
let index = index_of(&files, &["/p/api.h", "/p/main.cpp", "/p/quiet.cpp"]);
let Known::Yes(found) = macro_references(&index, &files, "API", ReferenceBudget::default())
else {
panic!("the macro is indexed");
};
assert_eq!(
found.candidates(),
3,
"the definer and the two files that include it"
);
assert_eq!(found.looked_at, 3, "all three were read");
assert_eq!(found.without_the_name, 1, "one of them has no `API` in it");
assert_eq!(found.lexed(), 2, "so two were lexed");
assert_eq!(found.not_looked_at, 0);
assert!(found.unreadable.is_empty());
}
#[test]
fn the_budget_stops_the_answer_and_says_how_much_it_missed() {
let files = fixture();
let index = index_of(&files, FIXTURE_FILES);
match macro_references(&index, &files, "API", ReferenceBudget { max_files: 1 }) {
Known::Yes(found) => {
assert_eq!(found.looked_at, 1);
assert_eq!(found.not_looked_at, 1, "one candidate was left unread");
assert_eq!(
found.candidates(),
2,
"and it is still counted as a candidate"
);
assert!(
found.total() < 2,
"the answer is short because of it: {} references",
found.total()
);
}
other => panic!("the macro is indexed, got {other:?}"),
}
}
#[test]
fn renaming_edits_exactly_the_ranges_that_hold_the_name() {
let files = fixture();
let index = index_of(&files, FIXTURE_FILES);
let Known::Yes(found) = macro_references(&index, &files, "API", ReferenceBudget::default())
else {
panic!("the macro is indexed");
};
let edits = found.rename("INT_TYPE");
assert_eq!(edits.len(), 2, "the definition and the one use");
let mut text = files
.read(Path::new("/p/main.cpp"))
.expect("the file reads");
for edit in edits
.iter()
.filter(|edit| edit.file == Path::new("/p/main.cpp"))
{
text.replace_range(
edit.range.start_offset..edit.range.end_offset(),
&edit.replacement,
);
}
assert_eq!(text, "#include \"api.h\"\nINT_TYPE f() { return 0; }\n");
}
#[test]
fn the_answer_is_in_path_order_whatever_order_the_graph_reaches_files_in() {
let files = fixture();
let index = index_of(
&files,
&["/p/cond.cpp", "/p/main.cpp", "/p/guarded.h", "/p/api.h"],
);
match macro_references(&index, &files, "API", ReferenceBudget::default()) {
Known::Yes(found) => {
let names: Vec<String> = found
.files
.iter()
.map(|file| file.file.file_name().unwrap().to_string_lossy().to_string())
.collect();
assert_eq!(names, ["api.h", "main.cpp"]);
}
other => panic!("the macro is indexed, got {other:?}"),
}
}
}
pub fn name_references(
index: &crate::ProjectIndex,
read: &dyn Fn(&std::path::Path) -> Option<String>,
name: &str,
declaring: &[std::path::PathBuf],
budget: usize,
) -> NameReferences {
use std::collections::{HashSet, VecDeque};
let mut found = NameReferences::default();
let mut seen: HashSet<std::path::PathBuf> = HashSet::new();
let mut queue: VecDeque<std::path::PathBuf> = declaring.iter().cloned().collect();
while let Some(path) = queue.pop_front() {
if !seen.insert(path.clone()) {
continue;
}
for includer in index.includers_of(&path) {
if !seen.contains(&includer) {
queue.push_back(includer);
}
}
}
for path in seen {
if found.looked_at >= budget {
found.not_looked_at.push(path);
continue;
}
let Some(text) = read(&path) else {
found.not_looked_at.push(path);
continue;
};
if !text.contains(name) {
found.looked_at += 1;
continue;
}
found.looked_at += 1;
let (tokens, _) = cpp_parser::lex(&text, &cpp_parser::LexerConfig::default());
let at: Vec<cpp_parser::SourceRange> = tokens
.iter()
.filter(|token| {
token.kind == cpp_parser::CppTokenKind::Identifier
&& text
.get(token.range.start_offset..token.range.end_offset())
.is_some_and(|spelled| spelled == name)
})
.map(|token| token.range)
.collect();
if !at.is_empty() {
found.found.push((path, at));
}
}
found
}
#[derive(Debug, Default)]
pub struct NameReferences {
pub found: Vec<(std::path::PathBuf, Vec<cpp_parser::SourceRange>)>,
pub looked_at: usize,
pub not_looked_at: Vec<std::path::PathBuf>,
}