use std::collections::HashMap;
use crate::macros::MacroDef;
use crate::preprocess::condition::{self, Lookup, MacroValues, Value};
use crate::surface::{ConditionFlavour, Event, Surface};
use crate::token::Token;
#[derive(Debug, Clone, Default)]
pub struct Macros {
definitions: HashMap<String, MacroDef>,
signature: u64,
}
impl Macros {
pub fn new() -> Self {
Self::default()
}
pub fn define(&mut self, definition: MacroDef) {
let name = definition.name.to_string();
self.signature = fold(self.signature, 1, &name);
self.signature = fold(self.signature, 2, &body_text(&definition));
self.definitions.insert(name, definition);
}
pub fn undefine(&mut self, name: &str) {
self.signature = fold(self.signature, 3, name);
self.definitions.remove(name);
}
pub fn signature(&self) -> u64 {
self.signature
}
pub fn get(&self, name: &str) -> Option<&MacroDef> {
self.definitions.get(name)
}
pub fn len(&self) -> usize {
self.definitions.len()
}
pub fn is_empty(&self) -> bool {
self.definitions.is_empty()
}
pub fn values_of(&self, names: &[String]) -> Vec<Option<String>> {
names
.iter()
.map(|name| self.definitions.get(name).map(body_text))
.collect()
}
}
impl MacroValues for Macros {
fn lookup(&self, name: &str) -> Lookup<'_> {
match self.definitions.get(name) {
Some(definition) => Lookup::Defined(definition),
None => Lookup::Undefined,
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Fold {
Define(MacroDef),
Undef(String),
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Effect {
pub folds: Vec<Fold>,
pub certain: bool,
}
impl Effect {
pub fn key(signature: u64, values: &[Option<&str>]) -> u64 {
let mut hash: u64 = 0xcbf2_9ce4_8422_2325;
let mut eat = |byte: u8| {
hash ^= u64::from(byte);
hash = hash.wrapping_mul(0x100_0000_01b3);
};
for byte in signature.to_le_bytes() {
eat(byte);
}
for value in values {
match value {
Some(text) => {
for byte in text.as_bytes() {
eat(*byte);
}
}
None => eat(0xff),
}
eat(0xfe);
}
hash
}
pub fn apply(&self, table: &mut Macros) {
for fold in &self.folds {
match fold {
Fold::Define(definition) => table.define(definition.clone()),
Fold::Undef(name) => table.undefine(name),
}
}
}
pub fn touched(&self) -> Vec<&str> {
self.folds
.iter()
.map(|fold| match fold {
Fold::Define(definition) => definition.name.as_ref(),
Fold::Undef(name) => name.as_str(),
})
.collect()
}
}
pub fn effect_of(surface: &Surface, environment: &Macros) -> Effect {
let mut effect = Effect {
folds: Vec::new(),
certain: true,
};
struct Region {
outer_active: bool,
taken: bool,
active: bool,
}
let mut regions: Vec<Region> = Vec::new();
let active = |regions: &[Region]| regions.last().is_none_or(|region| region.active);
for event in &surface.events {
match event {
Event::If {
tokens, flavour, ..
} => {
let outer_active = active(®ions);
let decided = outer_active.then(|| decide(*flavour, tokens, environment));
let holds = match decided {
Some(Value::Known(value)) => value != 0,
Some(_) => {
effect.certain = false;
false
}
None => false,
};
regions.push(Region {
outer_active,
taken: holds,
active: outer_active && holds,
});
}
Event::Elif {
tokens, flavour, ..
} => {
let Some(region) = regions.last_mut() else {
continue;
};
if region.taken || !region.outer_active {
region.active = false;
continue;
}
let holds = match decide(*flavour, tokens, environment) {
Value::Known(value) => value != 0,
_ => {
effect.certain = false;
false
}
};
region.taken = holds;
region.active = holds;
}
Event::Else { .. } => {
if let Some(region) = regions.last_mut() {
region.active = region.outer_active && !region.taken;
region.taken = true;
}
}
Event::Endif { .. } => {
regions.pop();
}
Event::Define { definition } => {
if active(®ions) {
effect.folds.push(Fold::Define(definition.clone()));
}
}
Event::Undef { name, .. } => {
if active(®ions) {
effect.folds.push(Fold::Undef(name.clone()));
}
}
Event::Include { .. } | Event::Other { .. } => {}
}
}
effect
}
fn decide(flavour: ConditionFlavour, tokens: &[Token], environment: &Macros) -> Value {
match flavour {
ConditionFlavour::Expression => condition::evaluate(tokens, environment),
ConditionFlavour::Defined | ConditionFlavour::NotDefined => {
let Some(name) = tokens
.iter()
.find(|token| token.kind == cpp_parser::CppTokenKind::Identifier)
else {
return Value::Unknown;
};
match environment.lookup(name.text.as_ref()).is_defined() {
Some(defined) => {
Value::Known(i128::from(if flavour == ConditionFlavour::Defined {
defined
} else {
!defined
}))
}
None => Value::Unknown,
}
}
}
}
fn body_text(definition: &MacroDef) -> String {
let mut out = String::new();
for token in &definition.body.tokens {
out.push_str(&token.text);
}
out.trim().to_string()
}
fn fold(mut hash: u64, tag: u8, text: &str) -> u64 {
let mut eat = |byte: u8| {
hash ^= u64::from(byte);
hash = hash.wrapping_mul(0x100_0000_01b3);
};
eat(tag);
for byte in text.as_bytes() {
eat(*byte);
}
eat(0xff);
hash
}
pub fn values_for(surface: &Surface, environment: &Macros) -> Vec<Option<String>> {
surface
.tests()
.into_iter()
.map(|name| {
environment
.get(&name)
.map(|definition| body_text(definition).to_string())
})
.collect()
}
pub fn condition_tokens(tokens: &[Token]) -> &[Token] {
tokens
}
pub const SURFACES_HELD: usize = 512;
#[derive(Default)]
pub struct Surfaces {
held: std::sync::Mutex<HashMap<u64, std::sync::Arc<Surface>>>,
}
impl Surfaces {
pub fn new() -> Self {
Self::default()
}
pub fn of(&self, path: &std::path::Path, text: &str) -> std::sync::Arc<Surface> {
let key = crate::cache::content_hash(text);
let mut held = self
.held
.lock()
.unwrap_or_else(|poisoned| poisoned.into_inner());
if held.len() >= SURFACES_HELD {
held.clear();
}
if let Some(found) = held.get(&key) {
return std::sync::Arc::clone(found);
}
let made = std::sync::Arc::new(crate::surface::surface_of(path, text));
held.insert(key, std::sync::Arc::clone(&made));
made
}
pub fn len(&self) -> usize {
self.held.lock().map(|held| held.len()).unwrap_or(0)
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
}
pub trait Reads {
fn read(&self, path: &std::path::Path) -> Option<String>;
fn resolve(&self, from: &std::path::Path, spelling: &str) -> Option<std::path::PathBuf>;
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct Walked {
pub files: usize,
pub inclusions: usize,
pub evaluated: usize,
pub reused: usize,
pub uncertain: usize,
pub unresolved: usize,
}
pub struct Chain<'a, R: Reads> {
reader: &'a R,
effects: &'a mut HashMap<u64, Effect>,
tables: HashMap<std::path::PathBuf, Macros>,
signatures: HashMap<std::path::PathBuf, u64>,
surfaces: Option<&'a Surfaces>,
keep_tables: bool,
walked: Walked,
}
impl<'a, R: Reads> Chain<'a, R> {
pub fn new(reader: &'a R, effects: &'a mut HashMap<u64, Effect>) -> Self {
Self {
reader,
effects,
tables: HashMap::new(),
signatures: HashMap::new(),
keep_tables: true,
surfaces: None,
walked: Walked::default(),
}
}
pub fn with_surfaces(mut self, surfaces: &'a Surfaces) -> Self {
self.surfaces = Some(surfaces);
self
}
pub fn without_tables(mut self) -> Self {
self.keep_tables = false;
self
}
pub fn at_signatures(
mut self,
root: &std::path::Path,
seed: &Macros,
) -> (HashMap<std::path::PathBuf, u64>, Walked) {
self.keep_tables = false;
let mut table = seed.clone();
self.enter(root, &mut table, 0);
(self.signatures, self.walked)
}
pub fn at(
mut self,
root: &std::path::Path,
seed: &Macros,
) -> (HashMap<std::path::PathBuf, Macros>, Walked) {
let mut table = seed.clone();
self.enter(root, &mut table, 0);
(self.tables, self.walked)
}
fn enter(&mut self, path: &std::path::Path, table: &mut Macros, depth: usize) {
if depth > 64 {
return;
}
let Some(text) = self.reader.read(path) else {
return;
};
self.walked.files += 1;
let surface = match self.surfaces {
Some(surfaces) => surfaces.of(path, &text),
None => std::sync::Arc::new(crate::surface::surface_of(path, &text)),
};
if surface.events.is_empty() {
return;
}
let mut seen: Option<Macros> = None;
let has_includes = surface
.events
.iter()
.any(|event| matches!(event, Event::Include { .. }));
if !has_includes {
let values = values_for(&surface, table);
let values: Vec<Option<&str>> = values.iter().map(|value| value.as_deref()).collect();
let key = Effect::key(surface.signature(), &values);
let effect = match self.effects.get(&key) {
Some(known) => {
self.walked.reused += 1;
known.clone()
}
None => {
let made = effect_of(&surface, table);
self.walked.evaluated += 1;
self.effects.insert(key, made.clone());
made
}
};
if !effect.certain {
self.walked.uncertain += 1;
}
self.tables
.entry(path.to_path_buf())
.or_insert_with(|| table.clone());
effect.apply(table);
return;
}
self.walked.evaluated += 1;
let mut regions: Vec<(bool, bool, bool)> = Vec::new();
let active =
|regions: &Vec<(bool, bool, bool)>| regions.last().is_none_or(|region| region.2);
for event in &surface.events {
match event {
Event::If {
tokens, flavour, ..
} => {
let outer = active(®ions);
let holds = outer
&& matches!(decide(*flavour, tokens, table), Value::Known(value) if value != 0);
regions.push((outer, holds, outer && holds));
}
Event::Elif {
tokens, flavour, ..
} => {
if let Some(region) = regions.last_mut() {
if region.1 || !region.0 {
region.2 = false;
} else {
let holds = matches!(
decide(*flavour, tokens, table),
Value::Known(value) if value != 0
);
region.1 = holds;
region.2 = holds;
}
}
}
Event::Else { .. } => {
if let Some(region) = regions.last_mut() {
region.2 = region.0 && !region.1;
region.1 = true;
}
}
Event::Endif { .. } => {
regions.pop();
}
Event::Include { spelling, .. } => {
if !active(®ions) {
continue;
}
self.walked.inclusions += 1;
match self.reader.resolve(path, spelling) {
Some(included) => {
let included = included.clone();
self.enter(&included, table, depth + 1);
}
None => self.walked.unresolved += 1,
}
}
Event::Define { definition } => {
if seen.is_none() {
seen = Some(table.clone());
}
if active(®ions) {
table.define(definition.clone());
}
}
Event::Undef { name, .. } => {
if seen.is_none() {
seen = Some(table.clone());
}
if active(®ions) {
table.undefine(name);
}
}
Event::Other { .. } => {}
}
}
self.signatures
.entry(path.to_path_buf())
.or_insert_with(|| seen.as_ref().unwrap_or(table).signature());
if self.keep_tables {
self.tables
.entry(path.to_path_buf())
.or_insert_with(|| seen.unwrap_or_else(|| table.clone()));
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::path::Path;
fn surface(text: &str) -> Surface {
crate::surface::surface_of(Path::new("/p/a.h"), text)
}
fn table(defines: &[(&str, &str)]) -> Macros {
let mut macros = Macros::new();
for (name, body) in defines {
let definition = crate::preprocess::macros::parse_define(
&[
Token::new(
cpp_parser::CppTokenKind::Identifier,
*name,
cpp_parser::SourceRange::new(0, 0),
),
Token::new(
cpp_parser::CppTokenKind::Whitespace,
" ",
cpp_parser::SourceRange::new(0, 0),
),
Token::new(
cpp_parser::CppTokenKind::Identifier,
*body,
cpp_parser::SourceRange::new(0, 0),
),
],
cpp_parser::SourceRange::new(0, 0),
);
if let Some(definition) = definition {
macros.define(definition);
}
}
macros
}
#[test]
fn an_unconditional_define_is_an_export_in_every_environment() {
let surface = surface("#define A 1\n");
let empty = Macros::new();
let effect = effect_of(&surface, &empty);
assert_eq!(effect.touched(), vec!["A"]);
assert!(effect.certain);
let mut applied = Macros::new();
effect.apply(&mut applied);
assert!(applied.get("A").is_some(), "the define reached the table");
}
#[test]
fn a_conditional_define_follows_the_environment() {
let surface = surface("#ifdef WIN32\n#define API __stdcall\n#endif\n");
let without = Macros::new();
let effect = effect_of(&surface, &without);
assert!(effect.touched().is_empty(), "WIN32 is not defined here");
let with = table(&[("WIN32", "1")]);
let effect = effect_of(&surface, &with);
assert_eq!(
effect.touched(),
vec!["API"],
"certain={} folds={:?} tokens={:?}",
effect.certain,
effect.folds.len(),
surface.events
);
}
#[test]
fn the_guarded_second_inclusion_is_empty() {
let surface = surface("#ifndef GUARD_H\n#define GUARD_H\n#define INSIDE 1\n#endif\n");
let fresh = Macros::new();
let first = effect_of(&surface, &fresh);
assert_eq!(first.touched(), vec!["GUARD_H", "INSIDE"]);
let mut table = Macros::new();
first.apply(&mut table);
let second = effect_of(&surface, &table);
assert!(
second.touched().is_empty(),
"the guard is defined, so nothing is exported again: {:?}",
second.touched()
);
}
#[test]
fn an_undef_takes_a_name_away() {
let surface = surface("#define A 1\n#undef A\n");
let mut table = Macros::new();
effect_of(&surface, &Macros::new()).apply(&mut table);
assert!(table.get("A").is_none(), "defined and then undefined");
}
#[test]
fn a_condition_that_cannot_be_decided_is_not_certain() {
let surface = surface("#if __has_include(<vector>)\n#define A 1\n#endif\n");
let effect = effect_of(&surface, &Macros::new());
assert!(!effect.certain, "the condition cannot be decided here");
}
#[test]
fn the_value_of_a_macro_is_its_whole_body() {
let surface = surface("#define WITH_ARGS(x) ((x) + 1)\n#define PLAIN (1)\n");
let mut applied = Macros::new();
effect_of(&surface, &Macros::new()).apply(&mut applied);
assert_eq!(
applied.get("WITH_ARGS").map(body_text),
Some("((x) + 1)".to_string())
);
assert_eq!(applied.get("PLAIN").map(body_text), Some("(1)".to_string()));
}
struct Fixture(std::collections::HashMap<std::path::PathBuf, String>);
impl Fixture {
fn new(files: &[(&str, &str)]) -> Self {
let mut held = std::collections::HashMap::new();
for (path, text) in files {
held.insert(std::path::PathBuf::from(*path), text.to_string());
}
Self(held)
}
}
impl Reads for Fixture {
fn read(&self, path: &std::path::Path) -> Option<String> {
self.0.get(path).cloned()
}
fn resolve(&self, _from: &std::path::Path, spelling: &str) -> Option<std::path::PathBuf> {
let name = spelling.trim_matches(|c| c == '"' || c == '<' || c == '>');
let path = std::path::PathBuf::from("/p").join(name);
self.0.contains_key(&path).then_some(path)
}
}
#[test]
fn a_chain_folds_what_the_includes_define() {
let files = Fixture::new(&[
("/p/a.h", "#define A 1\n"),
(
"/p/b.h",
"#include \"a.h\"\n#ifdef A\n#define B 2\n#endif\n",
),
]);
let mut cache = std::collections::HashMap::new();
let chain = Chain::new(&files, &mut cache);
let (tables, walked) = chain.at(std::path::Path::new("/p/b.h"), &Macros::new());
let at_b = tables
.get(std::path::Path::new("/p/b.h"))
.expect("b was entered");
assert!(at_b.get("A").is_some(), "a.h`s define is in b.h`s table");
assert_eq!(walked.files, 2, "a.h and b.h");
assert_eq!(walked.inclusions, 1);
}
#[test]
fn a_guarded_header_included_twice_exports_once() {
let files = Fixture::new(&[
(
"/p/g.h",
"#ifndef G_H\n#define G_H\n#define INSIDE 1\n#endif\n",
),
("/p/root.cpp", "#include \"g.h\"\n#include \"g.h\"\n"),
]);
let mut cache = std::collections::HashMap::new();
let chain = Chain::new(&files, &mut cache);
let (tables, walked) = chain.at(std::path::Path::new("/p/root.cpp"), &Macros::new());
let at_root = tables
.get(std::path::Path::new("/p/root.cpp"))
.expect("root was entered");
assert!(at_root.get("G_H").is_some());
assert_eq!(walked.inclusions, 2, "both includes are walked");
assert_eq!(
walked.evaluated, 3,
"the root and both inclusions — two different environments for g.h, one effect each"
);
assert_eq!(walked.reused, 0);
}
#[test]
fn a_define_before_an_include_is_in_the_table_that_include_reads() {
let files = Fixture::new(&[
("/p/c.h", "#ifdef C\n#define SEEN 1\n#endif\n"),
("/p/root.cpp", "#define C 1\n#include \"c.h\"\n"),
]);
let mut cache = std::collections::HashMap::new();
let chain = Chain::new(&files, &mut cache);
let (tables, _) = chain.at(std::path::Path::new("/p/root.cpp"), &Macros::new());
let at_c = tables
.get(std::path::Path::new("/p/c.h"))
.expect("c was entered");
assert!(
at_c.get("C").is_some(),
"the host`s define comes before the include that reads it"
);
}
#[test]
fn the_key_of_an_environment_insensitive_file_does_not_depend_on_it() {
let plain = surface("#define A 1\n#include <vector>\n");
assert!(plain.tests().is_empty());
assert_eq!(
Effect::key(plain.signature(), &[]),
Effect::key(plain.signature(), &[])
);
let sensitive = surface("#ifdef WIN32\n#define A 1\n#endif\n");
let key_without = Effect::key(sensitive.signature(), &[None]);
let key_with = Effect::key(sensitive.signature(), &[Some("1")]);
assert_ne!(key_without, key_with);
}
#[test]
fn the_chain_agrees_with_the_walk_on_every_file() {
use crate::summary::MacroDefinitions;
use crate::{CompilerConfig, FileIndexer, MemoryFiles, SummaryKey, TranslationUnit};
use cpp_parser::MacroFacts;
let files: &[(&str, &str)] = &[
(
"/p/base.h",
"#define BASE 1\n#define WITH_ARGS(x) ((x) + 1)\n",
),
(
"/p/guarded.h",
"#ifndef GUARDED_H\n#define GUARDED_H\n#include \"base.h\"\n#ifdef BASE\n#define FROM_INSIDE 2\n#endif\n#endif\n",
),
(
"/p/deep.h",
"#include \"guarded.h\"\n#define AFTER 3\n#if AFTER == 3\n#define READS_ITS_OWN 4\n#endif\n",
),
(
"/p/root.cpp",
"#include \"deep.h\"\n#include \"guarded.h\"\n#ifndef UNDEFINED_HERE\n#define FALLBACK 5\n#endif\n",
),
];
let fixture = Fixture::new(files);
let mut cache = std::collections::HashMap::new();
let (tables, walked) = Chain::new(&fixture, &mut cache)
.at(std::path::Path::new("/p/root.cpp"), &Macros::new());
let mut provider = MemoryFiles::new();
for (path, text) in files {
provider.insert(*path, *text);
}
let config = CompilerConfig::default().with_include_path(std::path::PathBuf::from("/p"));
let indexer = FileIndexer::new(&provider, &config);
let mut summaries: std::collections::HashMap<std::path::PathBuf, crate::FileSummary> =
std::collections::HashMap::new();
let mut texts: std::collections::HashMap<std::path::PathBuf, String> =
std::collections::HashMap::new();
for (path, text) in files {
let path = std::path::PathBuf::from(*path);
summaries.insert(
path.clone(),
indexer.index(&path, text, SummaryKey::new(0, 0)),
);
texts.insert(path, text.to_string());
}
let mut definitions = MacroDefinitions::default();
let unit = TranslationUnit::walk(
summaries
.get(std::path::Path::new("/p/root.cpp"))
.expect("the root was indexed"),
|wanted| {
summaries
.get(wanted)
.map(|summary| (summary, texts.get(wanted).map(String::as_str).unwrap_or("")))
},
&crate::include::graph::Marked::default(),
&mut definitions,
false,
&crate::WalkCache::new(),
);
let mut compared = 0usize;
let mut pathless = 0usize;
let mut disagreements: Vec<String> = Vec::new();
for (path, table) in &tables {
let Some(view) = unit.environment_of(path) else {
pathless += 1;
continue;
};
let mut names: Vec<&String> = table.definitions.keys().collect();
names.sort();
for name in names {
let from_chain = table
.get(name)
.map(body_text)
.map(|text| text.trim().to_string());
let from_walk = view
.body_text_of(name, usize::MAX)
.map(|text| text.trim().to_string());
compared += 1;
if from_walk != from_chain {
disagreements.push(format!(
"{}: {name} walk={from_walk:?} chain={from_chain:?}",
path.display()
));
}
}
}
assert!(
disagreements.is_empty(),
"{} of {compared} name(s) disagree ({pathless} file(s) the walk does not reach): {:?}",
disagreements.len(),
&disagreements[..disagreements.len().min(6)]
);
assert!(compared > 0, "the two readings share at least one file");
assert!(
walked.files >= 4,
"the chain entered every file: {walked:?}"
);
}
}