use std::collections::HashSet;
use std::path::{Path, PathBuf};
use cpp_parser::CppSyntaxTree;
use crate::{
config::CompilerConfig,
directive::{Directive, DirectiveKind, IncludeForm, SpannedDirective},
guards::{Guard, detect_guard_from_tokens},
include::{FoundIn, IncludeResolver, Resolution},
paths::{FileId, FileProvider, PathInterner, parent_normalized},
};
pub const MAX_INCLUDE_DEPTH: usize = 64;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SkipReason {
Cycle,
TooDeep,
AlreadyVisited,
OutOfScope,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Visit {
Analysed,
Skipped(SkipReason),
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Edge {
pub from: FileId,
pub to: FileId,
pub name: Box<str>,
pub is_angle: bool,
pub found_in: FoundIn,
pub visit: Visit,
pub range: cpp_parser::SourceRange,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct UnresolvedInclude {
pub from: FileId,
pub name: Box<str>,
pub searched: Vec<PathBuf>,
pub range: cpp_parser::SourceRange,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct FileEntry {
pub path: PathBuf,
pub guard: Guard,
pub defines: Vec<Box<str>>,
pub depth: usize,
pub macros: Vec<Box<str>>,
pub missing_context: bool,
}
impl FileEntry {
pub fn context_is_complete(&self) -> bool {
!self.missing_context
}
pub fn is_file_only(&self) -> bool {
self.depth == 0 && self.missing_context
}
}
#[derive(Debug, Clone, Default)]
pub struct FileGraph {
pub files: Vec<FileEntry>,
pub edges: Vec<Edge>,
pub unresolved: Vec<UnresolvedInclude>,
pub analysed: Vec<FileId>,
}
impl FileGraph {
pub fn entry(&self, file: FileId) -> Option<&FileEntry> {
self.files.get(file.index())
}
pub fn path(&self, file: FileId) -> Option<&Path> {
self.entry(file).map(|entry| entry.path.as_path())
}
pub fn includers_of(&self, file: FileId) -> Vec<FileId> {
let mut includers: Vec<FileId> = self
.edges
.iter()
.filter(|edge| edge.to == file)
.map(|edge| edge.from)
.collect();
includers.sort_unstable();
includers.dedup();
includers
}
pub fn includes_of(&self, file: FileId) -> Vec<FileId> {
let mut includes: Vec<FileId> = self
.edges
.iter()
.filter(|edge| edge.from == file)
.map(|edge| edge.to)
.collect();
includes.sort_unstable();
includes.dedup();
includes
}
pub fn dependents_of(&self, file: FileId) -> Vec<FileId> {
let mut seen: HashSet<FileId> = HashSet::new();
let mut pending = vec![file];
while let Some(current) = pending.pop() {
if !seen.insert(current) {
continue;
}
pending.extend(self.includers_of(current));
}
let mut result: Vec<FileId> = seen.into_iter().collect();
result.sort_unstable();
result
}
pub fn analysed_files(&self) -> &[FileId] {
&self.analysed
}
pub fn unresolved_includes(&self) -> &[UnresolvedInclude] {
&self.unresolved
}
}
#[derive(Debug, Default)]
struct WalkState {
visited: HashSet<FileId>,
on_path: Vec<FileId>,
root_missing_context: bool,
follows_includes: bool,
}
impl WalkState {
fn missing_context(&self) -> bool {
self.root_missing_context || !self.follows_includes
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum WalkScope {
#[default]
FollowIncludes,
FileOnly,
}
impl WalkScope {
fn follows_includes(self) -> bool {
matches!(self, WalkScope::FollowIncludes)
}
}
pub fn walk<F: FileProvider>(
source: &str,
tree: &CppSyntaxTree,
root_path: &Path,
files: &F,
config: &CompilerConfig,
interner: &mut PathInterner,
) -> FileGraph {
walk_scoped(
source,
tree,
root_path,
files,
config,
interner,
WalkScope::FollowIncludes,
)
}
pub fn walk_scoped<F: FileProvider>(
source: &str,
tree: &CppSyntaxTree,
root_path: &Path,
files: &F,
config: &CompilerConfig,
interner: &mut PathInterner,
scope: WalkScope,
) -> FileGraph {
let mut graph = FileGraph::default();
let mut state = WalkState {
root_missing_context: is_probably_a_header(root_path),
follows_includes: scope.follows_includes(),
..WalkState::default()
};
let mut starting = Marked::from_config(config);
if state.missing_context() {
starting = starting.incomplete();
}
let root = interner.intern(root_path);
graph.analysed.push(root);
let mut tokens = tree.get_tokens().to_vec();
let directives = Directives::of(source, &mut tokens);
visit(
&directives,
root,
&starting,
&mut graph,
&mut state,
files,
config,
interner,
0,
);
graph
}
pub fn file_only<F: FileProvider>(
source: &str,
tree: &CppSyntaxTree,
path: &Path,
files: &F,
config: &CompilerConfig,
interner: &mut PathInterner,
) -> FileGraph {
walk_scoped(
source,
tree,
path,
files,
config,
interner,
WalkScope::FileOnly,
)
}
fn is_probably_a_header(path: &Path) -> bool {
let Some(extension) = path.extension().and_then(|extension| extension.to_str()) else {
return false;
};
matches!(
extension.to_ascii_lowercase().as_str(),
"h" | "hh" | "hpp" | "hxx" | "h++" | "inc" | "ipp" | "tpp" | "tcc" | "inl"
)
}
pub(crate) struct Directives {
pub(crate) preprocessing: crate::preprocess::FilePreprocessing,
pub(crate) guard: Guard,
pub(crate) defines: Vec<Box<str>>,
}
impl Directives {
pub(crate) fn of(source: &str, tokens: &mut [cpp_parser::CppTokenData]) -> Self {
crate::preprocess::directive::fold_quoted_header_names(source, tokens);
let preprocessing = crate::preprocess::preprocess(source, tokens);
let guard = detect_guard_from_tokens(&preprocessing.directives, tokens);
let defines = preprocessing
.directives
.iter()
.filter_map(|spanned| spanned.directive.defines())
.map(|definition| definition.name.clone())
.collect();
Directives {
preprocessing,
guard,
defines,
}
}
}
#[allow(clippy::too_many_arguments)]
fn visit<F: FileProvider>(
directives: &Directives,
file: FileId,
inherited: &Marked,
graph: &mut FileGraph,
state: &mut WalkState,
files: &F,
config: &CompilerConfig,
interner: &mut PathInterner,
depth: usize,
) -> Marked {
let preprocessing = &directives.preprocessing;
let mut macros = inherited.clone();
let inherited_names = macros.defined_names();
let path = interner
.path(file)
.map(Path::to_path_buf)
.unwrap_or_default();
record(
graph,
file,
FileEntry {
path: path.clone(),
guard: directives.guard.clone(),
defines: directives.defines.clone(),
depth,
macros: inherited_names,
missing_context: state.missing_context(),
},
);
state.visited.insert(file);
state.on_path.push(file);
let per_file = config.for_file(&path);
let resolver = IncludeResolver::new(files, &per_file);
let including = parent_normalized(&path, files.is_case_insensitive());
let visibilities = directive_visibilities(¯os, &preprocessing.directives);
for (index, spanned) in preprocessing.directives.iter().enumerate() {
if visibilities[index] == Some(false) {
continue;
}
match &spanned.directive {
Directive::Define(define) => {
if let Some(definition) = &define.macro_def {
macros.define(definition.clone());
}
}
Directive::Undef { name: Some(name) } => macros.undefine(name),
_ => {}
}
let Some(include) = spanned.directive.as_include() else {
continue;
};
let resolution = resolver.resolve(include, &including, None, interner);
match resolution {
Resolution::Unresolved(unresolved) => graph.unresolved.push(UnresolvedInclude {
from: file,
name: unresolved.name,
searched: unresolved.searched,
range: spanned.range,
}),
Resolution::Resolved(resolved) => {
let visit = decide_visit(resolved.file, graph, state, depth);
graph.edges.push(Edge {
from: file,
to: resolved.file,
name: include.target.clone(),
is_angle: include.form == IncludeForm::Angle,
found_in: resolved.found_in,
visit,
range: spanned.range,
});
if visit == Visit::Analysed {
let reached_with = macros.clone();
let after = follow(
resolved.file,
&resolved.path,
&reached_with,
graph,
state,
files,
config,
interner,
depth + 1,
);
if let Some(after) = after {
macros = after;
}
}
}
}
}
state.on_path.pop();
macros
}
fn directive_visibilities(state: &Marked, directives: &[SpannedDirective]) -> Vec<Option<bool>> {
let mut open: Vec<OpenRegion> = Vec::new();
let mut visibilities: Vec<Option<bool>> = Vec::with_capacity(directives.len());
for (position, spanned) in directives.iter().enumerate() {
visibilities.push(inside_active_arm(&open, position));
let Some(branch) = branches_at(spanned) else {
continue;
};
let holds = branch.decide(state);
match branch.kind {
DirectiveKind::If | DirectiveKind::Ifdef | DirectiveKind::Ifndef => {
open.push(OpenRegion {
starts: vec![position],
holds: vec![holds],
active: if holds == Some(true) { Some(0) } else { None },
})
}
DirectiveKind::Elif | DirectiveKind::Else => {
if let Some(region) = open.last_mut() {
let eligible = region.holds.iter().all(|holds| *holds == Some(false));
region.starts.push(position);
region.holds.push(holds);
let this = region.holds.len() - 1;
if eligible && holds != Some(false) {
region.active = Some(this);
}
}
}
DirectiveKind::Endif => {
open.pop();
}
_ => {}
}
}
visibilities
}
fn branches_at(spanned: &SpannedDirective) -> Option<BranchAt> {
let kind = spanned.directive.kind();
if !(kind.opens_a_condition() || kind.closes_a_condition()) {
return None;
}
let (tokens, name) = match &spanned.directive {
Directive::Conditional { condition, .. } => (condition.clone(), None),
Directive::Ifdef { name, .. } => (Vec::new(), Some(name.clone())),
_ => (Vec::new(), None),
};
Some(BranchAt { kind, tokens, name })
}
fn inside_active_arm(open: &[OpenRegion], position: usize) -> Option<bool> {
let mut undecided = false;
for region in open {
let Some(current) = region.starts.iter().rposition(|start| *start <= position) else {
continue;
};
match region.active {
Some(active) if active == current => continue,
Some(_) => return Some(false),
None => {
if region.holds.iter().all(|holds| *holds == Some(false)) {
return Some(false);
}
undecided = true;
}
}
}
if undecided { None } else { Some(true) }
}
#[derive(Debug)]
struct OpenRegion {
starts: Vec<usize>,
holds: Vec<Option<bool>>,
active: Option<usize>,
}
#[derive(Debug, Clone)]
pub struct BranchAt {
pub kind: DirectiveKind,
pub tokens: Vec<crate::token::Token>,
pub name: Option<Box<str>>,
}
impl BranchAt {
pub fn decide(&self, state: &Marked) -> Option<bool> {
match self.kind {
DirectiveKind::If | DirectiveKind::Elif => {
crate::condition::evaluate(&self.tokens, state).is_true()
}
DirectiveKind::Ifdef => self.named_status(state),
DirectiveKind::Ifndef => self.named_status(state).map(|defined| !defined),
DirectiveKind::Else => Some(true),
_ => None,
}
}
fn named_status(&self, state: &Marked) -> Option<bool> {
let name = self.name.as_deref()?;
if state.is_unknown(name) {
return None;
}
Some(state.is_defined(name))
}
}
fn decide_visit(file: FileId, graph: &FileGraph, state: &WalkState, depth: usize) -> Visit {
if !state.follows_includes {
return Visit::Skipped(SkipReason::OutOfScope);
}
if state.on_path.contains(&file) {
return Visit::Skipped(SkipReason::Cycle);
}
if depth + 1 > MAX_INCLUDE_DEPTH {
return Visit::Skipped(SkipReason::TooDeep);
}
let guarded = graph
.entry(file)
.is_some_and(|entry| entry.guard.is_guarded());
if guarded && state.visited.contains(&file) {
return Visit::Skipped(SkipReason::AlreadyVisited);
}
Visit::Analysed
}
#[allow(clippy::too_many_arguments)]
fn follow<F: FileProvider>(
file: FileId,
path: &Path,
inherited: &Marked,
graph: &mut FileGraph,
state: &mut WalkState,
files: &F,
config: &CompilerConfig,
interner: &mut PathInterner,
depth: usize,
) -> Option<Marked> {
let Some(source) = files.read(path) else {
record(
graph,
file,
FileEntry {
path: path.to_path_buf(),
guard: Guard::None,
defines: Vec::new(),
depth,
macros: inherited.defined_names(),
missing_context: state.missing_context(),
},
);
return None;
};
graph.analysed.push(file);
let (mut tokens, _errors) = cpp_parser::lex(&source, &cpp_parser::LexerConfig::default());
let directives = Directives::of(&source, &mut tokens);
Some(visit(
&directives,
file,
inherited,
graph,
state,
files,
config,
interner,
depth,
))
}
fn record(graph: &mut FileGraph, file: FileId, entry: FileEntry) {
while graph.files.len() <= file.index() {
graph.files.push(FileEntry {
path: PathBuf::new(),
guard: Guard::None,
defines: Vec::new(),
depth: usize::MAX,
macros: Vec::new(),
missing_context: false,
});
}
graph.files[file.index()] = entry;
}
#[derive(Debug, Clone, Default)]
pub struct Marked {
bindings: Vec<(Box<str>, bool)>,
mentioned: std::collections::HashSet<Box<str>>,
command_line: Vec<crate::macros::MacroDef>,
incomplete: bool,
uncertain: HashSet<Box<str>>,
}
impl PartialEq for Marked {
fn eq(&self, other: &Self) -> bool {
self.bindings == other.bindings
&& self.command_line == other.command_line
&& self.incomplete == other.incomplete
&& self.uncertain == other.uncertain
}
}
impl Eq for Marked {}
impl crate::condition::MacroValues for Marked {
fn lookup(&self, name: &str) -> crate::condition::Lookup<'_> {
use crate::condition::Lookup;
if crate::preprocess::condition::is_a_builtin_operator(name) {
return Lookup::DefinedWithoutAValue;
}
if self.is_unknown(name) {
return Lookup::Unanswered;
}
if !self.is_defined(name) {
return Lookup::Undefined;
}
self.get(name)
.map_or(Lookup::DefinedWithoutAValue, Lookup::Defined)
}
fn builtin_operator(&self, name: &str, operand: &str) -> Option<crate::condition::Value> {
if name == "__has_cpp_attribute" {
let msvc = self.is_defined("_MSC_VER") && !self.is_defined("__clang__");
return crate::preprocess::cooked::attribute_support_in(operand, msvc)
.map(crate::condition::Value::Known);
}
None
}
}
impl Marked {
pub fn incomplete(mut self) -> Self {
self.incomplete = true;
self
}
pub fn mark_incomplete(&mut self) {
self.incomplete = true;
}
pub fn is_incomplete(&self) -> bool {
self.incomplete
}
pub fn mark_uncertain(&mut self, name: &str) {
self.uncertain.insert(name.into());
}
pub fn is_unknown(&self, name: &str) -> bool {
self.is_uncertain(name) || (self.incomplete && !self.mentions(name))
}
fn mentions(&self, name: &str) -> bool {
self.mentioned.contains(name)
}
pub fn names_the_compilation(&self, name: &str) -> bool {
self.mentions(name)
}
pub fn is_uncertain(&self, name: &str) -> bool {
self.uncertain.contains(name)
}
pub fn from_config(config: &CompilerConfig) -> Self {
let mut marked = Marked::default();
for definition in &config.defines {
marked.define_on_the_command_line(&definition.name, definition.value.as_deref());
}
for name in &config.undefines {
marked.bindings.push((name.clone(), false));
marked.mentioned.insert(name.clone());
}
marked
}
pub fn define_on_the_command_line(&mut self, name: &str, value: Option<&str>) {
let source = match value {
Some(value) => format!("#define {name} {value}\n"),
None => format!("#define {name} 1\n"),
};
let Some(parsed) = parse_define_source(&source) else {
return;
};
self.bindings.push((parsed.name.clone(), true));
self.mentioned.insert(parsed.name.clone());
self.command_line
.retain(|existing| existing.name != parsed.name);
self.command_line.push(parsed);
}
pub fn define(&mut self, definition: crate::macros::MacroDef) {
self.bindings.push((definition.name.clone(), true));
self.mentioned.insert(definition.name.clone());
self.command_line
.retain(|existing| existing.name != definition.name);
self.command_line.push(definition);
}
pub fn observe(&mut self, fact: &crate::MacroFact) {
match fact.kind {
crate::MacroKind::Undefinition => self.undefine(&fact.name),
crate::MacroKind::Definition => match fact.value.as_deref() {
Some(value) => self.define(crate::macros::MacroDef {
name: fact.name.as_str().into(),
params: None,
body: crate::macros::MacroBody {
tokens: vec![crate::Token::new(
cpp_parser::CppTokenKind::IntegerLiteral,
value,
fact.range,
)],
stringize: Vec::new(),
paste: Vec::new(),
},
range: fact.range,
name_range: fact.range,
written_in: Some(crate::macros::MacroFile::Here),
value: std::sync::OnceLock::new(),
}),
None => match fact.alias.as_deref() {
Some(alias) => self.define(crate::macros::MacroDef {
name: fact.name.as_str().into(),
params: None,
body: crate::macros::MacroBody {
tokens: vec![crate::Token::new(
cpp_parser::CppTokenKind::Identifier,
alias,
fact.range,
)],
stringize: Vec::new(),
paste: Vec::new(),
},
range: fact.range,
name_range: fact.range,
written_in: Some(crate::macros::MacroFile::Here),
value: std::sync::OnceLock::new(),
}),
None => self.define_name(&fact.name),
},
},
}
}
pub fn define_name(&mut self, name: &str) {
self.bindings.push((name.into(), true));
self.mentioned.insert(name.into());
self.command_line.retain(|existing| &*existing.name != name);
}
pub fn undefine(&mut self, name: &str) {
self.bindings.push((name.into(), false));
self.mentioned.insert(name.into());
self.command_line.retain(|existing| &*existing.name != name);
}
pub fn is_defined(&self, name: &str) -> bool {
if !self.mentioned.contains(name) {
return false;
}
self.bindings
.iter()
.rev()
.find(|(bound, _)| &**bound == name)
.is_some_and(|(_, defined)| *defined)
}
pub fn get(&self, name: &str) -> Option<&crate::macros::MacroDef> {
if !self.is_defined(name) {
return None;
}
self.command_line
.iter()
.rev()
.find(|definition| &*definition.name == name)
}
pub fn defined_names(&self) -> Vec<Box<str>> {
let mut seen: HashSet<&str> = HashSet::new();
let mut names: Vec<Box<str>> = Vec::new();
for (name, defined) in self.bindings.iter().rev() {
if !seen.insert(name) {
continue;
}
if *defined {
names.push(name.clone());
}
}
names.sort_unstable();
names
}
pub fn len(&self) -> usize {
self.defined_names().len()
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
}
fn parse_define_source(source: &str) -> Option<crate::macros::MacroDef> {
let tree = cpp_parser::CppParser::parse(source, cpp_parser::ParserConfig::default());
let preprocessing = crate::preprocess::preprocess(source, tree.get_tokens());
preprocessing.macros.iter().next().cloned()
}
#[cfg(test)]
mod tests {
use super::{CompilerConfig, Marked, Path, is_probably_a_header};
#[test]
fn a_later_binding_shadows_an_earlier_one() {
let mut marked = Marked::default();
marked.define_name("REDEFINED");
marked.define_name("REMOVED");
marked.define_name("REDEFINED");
marked.undefine("REMOVED");
assert_eq!(
marked
.defined_names()
.iter()
.map(|n| &**n)
.collect::<Vec<_>>(),
vec!["REDEFINED"],
"the later bindings are the ones in force"
);
let mut marked = Marked::default();
marked.define_name("BACK");
marked.undefine("BACK");
marked.define_name("BACK");
assert_eq!(
marked
.defined_names()
.iter()
.map(|n| &**n)
.collect::<Vec<_>>(),
vec!["BACK"]
);
}
#[test]
fn defined_names_is_sorted_and_deduplicated() {
let mut marked = Marked::default();
marked.define_name("ZED");
marked.define_name("ALPHA");
marked.define_name("ZED");
marked.define_name("MID");
assert_eq!(
marked
.defined_names()
.iter()
.map(|n| &**n)
.collect::<Vec<_>>(),
vec!["ALPHA", "MID", "ZED"]
);
assert_eq!(marked.len(), 3);
}
#[test]
fn an_empty_state_has_no_names() {
let marked = Marked::default();
assert!(marked.is_empty());
assert!(marked.defined_names().is_empty());
assert!(!marked.is_defined("ANYTHING"));
}
#[test]
fn a_complete_state_reports_an_unmentioned_name_as_undefined() {
let marked = Marked::from_config(&CompilerConfig::new());
assert!(!marked.is_unknown("ANYTHING"));
assert!(!marked.is_defined("ANYTHING"));
}
#[test]
fn an_incomplete_state_reports_an_unmentioned_name_as_unknown() {
let marked = Marked::default().incomplete();
assert!(marked.is_unknown("FROM_THE_INCLUDER"));
assert!(!marked.is_defined("FROM_THE_INCLUDER"));
let mut seen = Marked::default().incomplete();
seen.define_name("DEFINED_HERE");
seen.undefine("UNDEFINED_HERE");
assert!(!seen.is_unknown("DEFINED_HERE"));
assert!(!seen.is_unknown("UNDEFINED_HERE"));
assert!(seen.is_defined("DEFINED_HERE"));
assert!(!seen.is_defined("UNDEFINED_HERE"));
}
#[test]
fn a_header_is_recognised_by_its_extension() {
for header in [
"a.h",
"a.hh",
"a.hpp",
"a.hxx",
"a.h++",
"a.inc",
"a.ipp",
"a.tpp",
"a.tcc",
"a.inl",
"A.H",
"dir/sub/a.hpp",
] {
assert!(
is_probably_a_header(Path::new(header)),
"{header} is a header"
);
}
for source in [
"a.cpp",
"a.cc",
"a.cxx",
"a.c",
"a.c++",
"a.m",
"a.mm",
"a",
"a.hpp.cpp",
"a.txt",
"Makefile",
] {
assert!(
!is_probably_a_header(Path::new(source)),
"{source} is not a header"
);
}
}
}