use std::collections::HashMap;
use std::path::{Path, PathBuf};
use cpp_parser::CppSyntaxTree;
use crate::{
config::CompilerConfig,
directive::IncludeForm,
include::{IncludeResolver, Resolution},
module_info::{ImportTarget, ModuleInfo, ModuleUnit},
paths::{FileId, FileProvider, PathInterner, join_normalized},
};
pub const INTERFACE_UNIT_EXTENSIONS: &[&str] = &["cppm", "ixx", "ccm", "cxxm", "cpp", "cc", "cxx"];
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ModuleUnitEntry {
pub file: FileId,
pub path: PathBuf,
pub module_name: Box<str>,
pub partition_name: Option<Box<str>>,
pub unit: ModuleUnit,
}
impl ModuleUnitEntry {
pub fn qualified_name(&self) -> String {
match &self.partition_name {
Some(partition) => format!("{}:{}", self.module_name, partition),
None => self.module_name.to_string(),
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ImportOutcome {
Resolved(FileId),
UnknownModule { name: Box<str> },
UnknownPartition {
module: Box<str>,
partition: Box<str>,
},
UnknownHeaderUnit {
name: Box<str>,
searched: Vec<PathBuf>,
},
NotDeclaredHere { name: Box<str>, tried: PathBuf },
NoModuleToPartition,
PartitionMismatch {
module: Box<str>,
partition: Box<str>,
tried: PathBuf,
},
}
impl ImportOutcome {
pub fn file(&self) -> Option<FileId> {
match self {
ImportOutcome::Resolved(file) => Some(*file),
_ => None,
}
}
pub fn is_resolved(&self) -> bool {
matches!(self, ImportOutcome::Resolved(_))
}
pub fn may_provide_names(&self) -> bool {
self.is_resolved()
}
pub fn describe(&self) -> String {
match self {
ImportOutcome::Resolved(_) => "resolved".to_string(),
ImportOutcome::UnknownModule { name } => {
format!("no file in this project declares module `{name}`")
}
ImportOutcome::UnknownPartition { module, partition } => {
format!("module `{module}` declares no partition `:{partition}`")
}
ImportOutcome::UnknownHeaderUnit { name, searched } if searched.is_empty() => format!(
"cannot build a header unit for `{name}`: no include directories are configured to search"
),
ImportOutcome::UnknownHeaderUnit { name, searched } => format!(
"cannot find a header for unit `{name}` (looked in {} place(s))",
searched.len()
),
ImportOutcome::NotDeclaredHere { name, tried } => format!(
"`{}` was tried for module `{name}` but does not declare it",
tried.display()
),
ImportOutcome::NoModuleToPartition => {
"`import :partition;` in a file that declares no module".to_string()
}
ImportOutcome::PartitionMismatch {
module,
partition,
tried,
} => format!(
"`{}` is a unit of `{module}` but is not partition `:{partition}`",
tried.display()
),
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ImportEdge {
pub from: FileId,
pub from_module: Option<Box<str>>,
pub target: ImportTarget,
pub is_reexport: bool,
pub outcome: ImportOutcome,
pub range: cpp_parser::SourceRange,
}
#[derive(Debug, Clone, Default)]
pub struct ModuleGraph {
pub units: Vec<ModuleUnitEntry>,
pub edges: Vec<ImportEdge>,
pub analysed: Vec<FileId>,
}
impl ModuleGraph {
pub fn interface_unit(&self, module: &str) -> Option<&ModuleUnitEntry> {
self.units
.iter()
.find(|unit| &*unit.module_name == module && unit.unit.exports_to_importers())
}
pub fn partition_unit(&self, module: &str, partition: &str) -> Option<&ModuleUnitEntry> {
self.units.iter().find(|unit| {
&*unit.module_name == module
&& unit.partition_name.as_deref() == Some(partition)
&& unit.unit.is_interface()
})
}
pub fn units_of(&self, module: &str) -> Vec<&ModuleUnitEntry> {
self.units
.iter()
.filter(|unit| &*unit.module_name == module)
.collect()
}
pub fn imports_of(&self, file: FileId) -> impl Iterator<Item = &ImportEdge> {
self.edges.iter().filter(move |edge| edge.from == file)
}
pub fn needs_of(&self, file: FileId) -> Vec<FileId> {
self.imports_of(file)
.filter_map(|edge| edge.outcome.file())
.collect()
}
pub fn importers_of(&self, file: FileId) -> Vec<FileId> {
let mut importers: Vec<FileId> = self
.edges
.iter()
.filter(|edge| edge.outcome.file() == Some(file))
.map(|edge| edge.from)
.collect();
importers.sort_unstable_by_key(|file| file.index());
importers.dedup();
importers
}
pub fn dependents_of(&self, file: FileId) -> Vec<FileId> {
let mut out = Vec::new();
let mut seen: std::collections::HashSet<FileId> = std::collections::HashSet::new();
let mut stack = vec![file];
while let Some(current) = stack.pop() {
for importer in self.importers_of(current) {
if seen.insert(importer) {
out.push(importer);
stack.push(importer);
}
}
}
out
}
pub fn unresolved_imports(&self) -> Vec<&ImportEdge> {
self.edges
.iter()
.filter(|edge| !edge.outcome.is_resolved())
.collect()
}
pub fn unit_of(&self, file: FileId) -> Option<&ModuleUnitEntry> {
self.units.iter().find(|unit| unit.file == file)
}
}
pub struct ModuleScanner<'a, F: FileProvider> {
files: &'a F,
config: &'a CompilerConfig,
index: HashMap<Box<str>, Vec<ModuleUnitEntry>>,
scanned_units: Vec<ModuleUnitEntry>,
manifests: std::cell::RefCell<HashMap<PathBuf, Option<String>>>,
}
impl<'a, F: FileProvider> ModuleScanner<'a, F> {
pub fn new(files: &'a F, config: &'a CompilerConfig) -> Self {
ModuleScanner {
files,
config,
index: HashMap::new(),
scanned_units: Vec::new(),
manifests: std::cell::RefCell::new(HashMap::new()),
}
}
pub fn add_file(&mut self, file: FileId, path: &Path, tree: &CppSyntaxTree) -> ModuleInfo {
let info = ModuleInfo::from_tree(&tree.get_red_root());
if let (Some(unit), Some(module_name)) = (info.unit, info.module_name.clone()) {
let entry = ModuleUnitEntry {
file,
path: path.to_path_buf(),
module_name: module_name.clone(),
partition_name: info.partition_name.clone(),
unit,
};
self.index
.entry(module_name)
.or_default()
.push(entry.clone());
if !self.scanned_units.iter().any(|unit| unit.file == file) {
self.scanned_units.push(entry);
}
}
info
}
pub fn units(&self) -> &[ModuleUnitEntry] {
&self.scanned_units
}
pub fn resolve_module(
&mut self,
name: &str,
directory: &Path,
interner: &mut PathInterner,
) -> ImportOutcome {
if let Some(entry) = self
.index
.get(name)
.and_then(|units| units.iter().find(|unit| unit.unit.exports_to_importers()))
{
return ImportOutcome::Resolved(entry.file);
}
for candidate in self.candidate_paths(name, directory) {
let Some(source) = self.files.read(&candidate) else {
continue;
};
let tree = cpp_parser::CppParser::parse(&source, cpp_parser::ParserConfig::default());
let info = ModuleInfo::from_tree(&tree.get_red_root());
if info.module_name.as_deref() != Some(name) {
return ImportOutcome::NotDeclaredHere {
name: name.into(),
tried: candidate,
};
}
if info.unit != Some(ModuleUnit::InterfaceUnit) {
return ImportOutcome::NotDeclaredHere {
name: name.into(),
tried: candidate,
};
}
let file = interner.intern(&candidate);
self.add_file(file, &candidate, &tree);
return ImportOutcome::Resolved(file);
}
ImportOutcome::UnknownModule { name: name.into() }
}
pub fn resolve_partition(
&mut self,
module: Option<&str>,
partition: &str,
directory: &Path,
interner: &mut PathInterner,
) -> ImportOutcome {
let Some(module) = module else {
return ImportOutcome::NoModuleToPartition;
};
if let Some(entry) = self.index.get(module).and_then(|units| {
units.iter().find(|unit| {
unit.partition_name.as_deref() == Some(partition) && unit.unit.is_interface()
})
}) {
return ImportOutcome::Resolved(entry.file);
}
let qualified = format!("{module}:{partition}");
for candidate in self.candidate_paths(&qualified, directory) {
let Some(source) = self.files.read(&candidate) else {
continue;
};
let tree = cpp_parser::CppParser::parse(&source, cpp_parser::ParserConfig::default());
let info = ModuleInfo::from_tree(&tree.get_red_root());
let matches = info.module_name.as_deref() == Some(module)
&& info.partition_name.as_deref() == Some(partition);
if !matches {
return ImportOutcome::PartitionMismatch {
module: module.into(),
partition: partition.into(),
tried: candidate,
};
}
let file = interner.intern(&candidate);
self.add_file(file, &candidate, &tree);
return ImportOutcome::Resolved(file);
}
ImportOutcome::UnknownPartition {
module: module.into(),
partition: partition.into(),
}
}
pub fn resolve_header_unit(
&mut self,
name: &str,
is_angle: bool,
directory: &Path,
interner: &mut PathInterner,
) -> ImportOutcome {
let include = crate::directive::Include {
target: name.into(),
form: if is_angle {
IncludeForm::Angle
} else {
IncludeForm::Quote
},
is_next: false,
};
let resolver = IncludeResolver::new(self.files, self.config);
let outcome = resolver.resolve(&include, directory, None, interner);
match outcome {
Resolution::Resolved(resolved) => ImportOutcome::Resolved(resolved.file),
Resolution::Unresolved(unresolved) => ImportOutcome::UnknownHeaderUnit {
name: name.into(),
searched: unresolved.searched,
},
}
}
fn candidate_paths(&self, name: &str, including: &Path) -> Vec<PathBuf> {
let mut candidates = Vec::new();
let case_insensitive = self.files.is_case_insensitive();
let dotted = name.replace(':', ".");
let stems = [
name.replace(':', "-").replace('.', "/"),
name.replace(':', "-"),
dotted.replace('.', "/"),
dotted.clone(),
name.replace(':', "_").replace('.', "/"),
name.replace(':', "_"),
];
for directory in self.search_directories(including) {
for stem in &stems {
for extension in INTERFACE_UNIT_EXTENSIONS {
let candidate = join_normalized(
&directory,
Path::new(&format!("{stem}.{extension}")),
case_insensitive,
);
if !candidates.contains(&candidate) {
candidates.push(candidate);
}
}
}
}
if matches!(name, "std" | "std.compat") {
for directory in self.search_directories(including) {
for template in STANDARD_MODULE_SOURCES {
let candidate = join_normalized(
&directory,
Path::new(&template.replace("{name}", name)),
case_insensitive,
);
if !candidates.contains(&candidate) {
candidates.push(candidate);
}
}
}
}
for candidate in self.the_files_a_libcxx_manifest_names(name, including) {
if !candidates.contains(&candidate) {
candidates.push(candidate);
}
}
candidates
}
fn the_files_a_libcxx_manifest_names(&self, name: &str, including: &Path) -> Vec<PathBuf> {
let case_insensitive = self.files.is_case_insensitive();
let mut found: Vec<PathBuf> = Vec::new();
for directory in self.search_directories(including) {
for relative in LIBCXX_MANIFEST_DIRECTORIES {
let manifest = join_normalized(
&directory,
&Path::new(relative).join(LIBCXX_MANIFEST),
case_insensitive,
);
let Some(text) = self.the_text_of(&manifest) else {
continue;
};
let Some(written) = the_file_a_manifest_names(&text, name) else {
continue;
};
for candidate in the_paths_the_manifest_may_mean(&manifest, &written) {
if !found.contains(&candidate) {
found.push(candidate);
}
}
}
}
found
}
fn the_text_of(&self, path: &Path) -> Option<String> {
if let Some(remembered) = self.manifests.borrow().get(path) {
return remembered.clone();
}
let text = self.files.read(path);
self.manifests
.borrow_mut()
.insert(path.to_path_buf(), text.clone());
text
}
fn search_directories(&self, including: &Path) -> Vec<PathBuf> {
let mut directories = vec![including.to_path_buf()];
for directory in self
.config
.user_include_paths()
.chain(self.config.system_include_paths())
{
directories.push(directory.to_path_buf());
if let Some(parent) = directory.parent() {
let modules = parent.join("modules");
if !directories.contains(&modules) {
directories.push(modules);
}
}
}
directories
}
}
pub const STANDARD_MODULE_SOURCES: &[&str] = &[
"bits/{name}.cc",
"bits/{name}.cppm",
"share/libc++/v1/{name}.cppm",
"../share/libc++/v1/{name}.cppm",
"../../share/libc++/v1/{name}.cppm",
"../../../share/libc++/v1/{name}.cppm",
];
const LIBCXX_MANIFEST: &str = "libc++.modules.json";
const LIBCXX_MANIFEST_DIRECTORIES: &[&str] = &[
"",
"../share/libc++/v1",
"../../share/libc++/v1",
"../../../share/libc++/v1",
];
fn the_file_a_manifest_names(text: &str, name: &str) -> Option<String> {
let mut rest = text;
while let Some(at) = rest.find("\"name\"") {
rest = &rest[at + "\"name\"".len()..];
let Some(value) = the_first_string_after(rest) else {
continue;
};
if value != name {
continue;
}
let path_at = rest.find("\"path\"")?;
if rest[..path_at].contains('}') {
return None;
}
return the_first_string_after(&rest[path_at + "\"path\"".len()..]);
}
None
}
fn the_first_string_after(text: &str) -> Option<String> {
let start = text.find('"')?;
let rest = &text[start + 1..];
let end = rest.find('"')?;
Some(rest[..end].to_string())
}
fn the_paths_the_manifest_may_mean(manifest: &Path, written: &str) -> Vec<PathBuf> {
let written = Path::new(written);
let mut candidates: Vec<PathBuf> = Vec::new();
if written.is_absolute() {
candidates.push(written.to_path_buf());
return candidates;
}
let Some(directory) = manifest.parent() else {
return candidates;
};
candidates.push(directory.join(written));
for ancestor in directory.ancestors().take(4) {
let candidate = ancestor.join(written);
if !candidates.contains(&candidate) {
candidates.push(candidate);
}
}
if let Some(name) = written.file_name() {
let beside = directory.join(name);
if !candidates.contains(&beside) {
candidates.push(beside);
}
}
candidates
}
pub const MAX_IMPORT_DEPTH: usize = 64;
pub fn scan_imports<F: FileProvider>(
tree: &CppSyntaxTree,
root_path: &Path,
files: &F,
config: &CompilerConfig,
interner: &mut PathInterner,
) -> ModuleGraph {
let mut graph = ModuleGraph::default();
let mut state = ScanState::default();
let mut scanner = ModuleScanner::new(files, config);
let root = interner.intern(root_path);
graph.analysed.push(root);
let root_info = scanner.add_file(root, root_path, tree);
follow_imports(
&root_info,
root,
root_path,
&mut scanner,
&mut graph,
&mut state,
interner,
0,
);
graph.units = scanner.units().to_vec();
graph
}
#[derive(Debug, Default)]
struct ScanState {
visited: std::collections::HashSet<FileId>,
on_path: Vec<FileId>,
}
#[allow(clippy::too_many_arguments)]
fn follow_imports<F: FileProvider>(
info: &ModuleInfo,
file: FileId,
path: &Path,
scanner: &mut ModuleScanner<'_, F>,
graph: &mut ModuleGraph,
state: &mut ScanState,
interner: &mut PathInterner,
depth: usize,
) {
state.visited.insert(file);
state.on_path.push(file);
let including = crate::paths::parent_normalized(path, scanner.files.is_case_insensitive());
for declaration in &info.imports {
let outcome = match &declaration.target {
ImportTarget::Module(name) => scanner.resolve_module(name, &including, interner),
ImportTarget::Partition(partition) => scanner.resolve_partition(
info.module_name.as_deref(),
partition,
&including,
interner,
),
ImportTarget::HeaderUnit { name, is_angle } => {
scanner.resolve_header_unit(name, *is_angle, &including, interner)
}
};
graph.edges.push(ImportEdge {
from: file,
from_module: info.module_name.clone(),
target: declaration.target.clone(),
is_reexport: declaration.is_reexport,
outcome: outcome.clone(),
range: declaration.range,
});
let Some(target) = outcome.file() else {
continue;
};
if state.on_path.contains(&target) || depth + 1 > MAX_IMPORT_DEPTH {
continue;
}
if state.visited.contains(&target) {
continue;
}
let Some(target_path) = interner.path(target).map(Path::to_path_buf) else {
continue;
};
let Some(target_source) = scanner.files.read(&target_path) else {
continue;
};
let target_tree =
cpp_parser::CppParser::parse(&target_source, cpp_parser::ParserConfig::default());
let target_info = scanner.add_file(target, &target_path, &target_tree);
if !graph.analysed.contains(&target) {
graph.analysed.push(target);
}
follow_imports(
&target_info,
target,
&target_path,
scanner,
graph,
state,
interner,
depth + 1,
);
}
state.on_path.pop();
}