use std::collections::{BTreeMap, BTreeSet};
use std::error::Error;
use std::fmt;
use crate::semantic::{CollectedSymbol, CollectedSymbolKind, DeclarationIndex};
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct ModuleId(pub u32);
#[derive(Debug, Clone)]
pub struct ModuleDeclarations {
pub id: ModuleId,
pub path: String,
pub declarations: DeclarationIndex,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ResolvedSymbol<'a> {
pub module_id: ModuleId,
pub module_path: &'a str,
pub local_path: &'a str,
pub symbol: &'a CollectedSymbol,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ModuleGraphError {
DuplicateModule { path: String },
MissingDependency { requested_by: String, path: String },
UnknownModule { path: String },
UnknownSymbol { module: String, path: String },
PrivateSymbol { module: String, path: String },
AliasCycle { module: String, path: String },
}
impl fmt::Display for ModuleGraphError {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::DuplicateModule { path } => write!(formatter, "duplicate module `{path}`"),
Self::MissingDependency { requested_by, path } => {
write!(
formatter,
"module `{requested_by}` requires missing module `{path}`"
)
}
Self::UnknownModule { path } => write!(formatter, "unknown module `{path}`"),
Self::UnknownSymbol { module, path } => {
write!(formatter, "unknown symbol `{path}` in module `{module}`")
}
Self::PrivateSymbol { module, path } => {
write!(formatter, "symbol `{path}` in module `{module}` is private")
}
Self::AliasCycle { module, path } => {
write!(formatter, "alias cycle while resolving `{module}::{path}`")
}
}
}
}
impl Error for ModuleGraphError {}
#[derive(Debug, Clone, Default)]
pub struct ModuleGraph {
modules: Vec<ModuleDeclarations>,
module_ids: BTreeMap<String, ModuleId>,
prelude: Option<String>,
}
impl ModuleGraph {
pub fn insert(
&mut self,
path: impl Into<String>,
declarations: DeclarationIndex,
) -> Result<ModuleId, ModuleGraphError> {
let path = path.into();
if self.module_ids.contains_key(&path) {
return Err(ModuleGraphError::DuplicateModule { path });
}
let id = ModuleId(
u32::try_from(self.modules.len()).expect("module count exceeds ModuleId capacity"),
);
self.module_ids.insert(path.clone(), id);
self.modules.push(ModuleDeclarations {
id,
path,
declarations,
});
Ok(id)
}
pub fn remove(&mut self, path: &str) -> Result<(), ModuleGraphError> {
if !self.module_ids.contains_key(path) {
return Err(ModuleGraphError::UnknownModule {
path: path.to_owned(),
});
}
self.modules.retain(|module| module.path != path);
self.module_ids.clear();
for (index, module) in self.modules.iter_mut().enumerate() {
let id =
ModuleId(u32::try_from(index).expect("module count exceeds ModuleId capacity"));
module.id = id;
self.module_ids.insert(module.path.clone(), id);
}
Ok(())
}
pub fn set_prelude(&mut self, path: &str) -> Result<(), ModuleGraphError> {
if !self.module_ids.contains_key(path) {
return Err(ModuleGraphError::UnknownModule {
path: path.to_owned(),
});
}
self.prelude = Some(path.to_owned());
Ok(())
}
pub fn modules(&self) -> impl Iterator<Item = &ModuleDeclarations> {
self.modules.iter()
}
pub fn prelude(&self) -> Option<&str> {
self.prelude.as_deref()
}
pub fn module(&self, path: &str) -> Option<&ModuleDeclarations> {
let id = self.module_ids.get(path)?;
self.modules.get(id.0 as usize)
}
pub fn validate_dependencies(&self) -> Vec<ModuleGraphError> {
let mut errors = Vec::new();
for module in &self.modules {
for dependency in &module.declarations.dependencies {
if !self.module_ids.contains_key(dependency) {
errors.push(ModuleGraphError::MissingDependency {
requested_by: module.path.clone(),
path: dependency.clone(),
});
}
}
}
errors
}
pub fn resolve_declaration(
&self,
requesting_module: &str,
path: &str,
) -> Result<ResolvedSymbol<'_>, ModuleGraphError> {
let module =
self.module(requesting_module)
.ok_or_else(|| ModuleGraphError::UnknownModule {
path: requesting_module.to_owned(),
})?;
let head = path.split_once('.').map_or(path, |(head, _)| head);
let has_local_candidate = module.declarations.symbol(path).is_some()
|| module.declarations.symbol(head).is_some();
let module_path = if has_local_candidate {
requesting_module
} else if let Some(prelude) = &self.prelude {
prelude
} else {
requesting_module
};
self.resolve_declaration_inner(module_path, path, module_path != requesting_module)
}
fn resolve_declaration_inner<'a>(
&'a self,
module_path: &str,
path: &str,
crossing_module_boundary: bool,
) -> Result<ResolvedSymbol<'a>, ModuleGraphError> {
let module = self
.module(module_path)
.ok_or_else(|| ModuleGraphError::UnknownModule {
path: module_path.to_owned(),
})?;
if let Some(symbol) = module.declarations.symbol(path) {
if crossing_module_boundary && !symbol.public {
return Err(ModuleGraphError::PrivateSymbol {
module: module_path.to_owned(),
path: path.to_owned(),
});
}
return Ok(ResolvedSymbol {
module_id: module.id,
module_path: &module.path,
local_path: &symbol.path,
symbol,
});
}
let (head, tail) = path.split_once('.').unwrap_or((path, ""));
let Some(head_symbol) = module.declarations.symbol(head) else {
return Err(ModuleGraphError::UnknownSymbol {
module: module_path.to_owned(),
path: path.to_owned(),
});
};
let CollectedSymbolKind::ModuleAlias { source } = &head_symbol.kind else {
return Err(ModuleGraphError::UnknownSymbol {
module: module_path.to_owned(),
path: path.to_owned(),
});
};
if crossing_module_boundary && !head_symbol.public {
return Err(ModuleGraphError::PrivateSymbol {
module: module_path.to_owned(),
path: head.to_owned(),
});
}
if tail.is_empty() {
return Err(ModuleGraphError::UnknownSymbol {
module: source.clone(),
path: String::new(),
});
}
self.resolve_declaration_inner(source, tail, true)
}
pub fn resolve(
&self,
requesting_module: &str,
path: &str,
) -> Result<ResolvedSymbol<'_>, ModuleGraphError> {
let mut visited = BTreeSet::new();
let module =
self.module(requesting_module)
.ok_or_else(|| ModuleGraphError::UnknownModule {
path: requesting_module.to_owned(),
})?;
let head = path.split_once('.').map_or(path, |(head, _)| head);
let has_local_candidate = module.declarations.symbol(path).is_some()
|| module.declarations.symbol(head).is_some();
if has_local_candidate {
self.resolve_inner(requesting_module, path, false, &mut visited)
} else if let Some(prelude) = &self.prelude
&& prelude != requesting_module
{
self.resolve_inner(prelude, path, true, &mut visited)
} else {
Err(ModuleGraphError::UnknownSymbol {
module: requesting_module.to_owned(),
path: path.to_owned(),
})
}
}
fn resolve_inner<'a>(
&'a self,
module_path: &str,
path: &str,
crossing_module_boundary: bool,
visited: &mut BTreeSet<(String, String)>,
) -> Result<ResolvedSymbol<'a>, ModuleGraphError> {
let key = (module_path.to_owned(), path.to_owned());
if !visited.insert(key) {
return Err(ModuleGraphError::AliasCycle {
module: module_path.to_owned(),
path: path.to_owned(),
});
}
let module = self
.module(module_path)
.ok_or_else(|| ModuleGraphError::UnknownModule {
path: module_path.to_owned(),
})?;
if let Some(symbol) = module.declarations.symbol(path) {
match &symbol.kind {
CollectedSymbolKind::Alias { target, .. } => {
if crossing_module_boundary && !symbol.public {
return Err(ModuleGraphError::PrivateSymbol {
module: module_path.to_owned(),
path: path.to_owned(),
});
}
return self.resolve_inner(module_path, &target.path, false, visited);
}
CollectedSymbolKind::ModuleAlias { source } => {
if crossing_module_boundary && !symbol.public {
return Err(ModuleGraphError::PrivateSymbol {
module: module_path.to_owned(),
path: path.to_owned(),
});
}
return Err(ModuleGraphError::UnknownSymbol {
module: source.clone(),
path: String::new(),
});
}
_ => {
if crossing_module_boundary && !symbol.public {
return Err(ModuleGraphError::PrivateSymbol {
module: module_path.to_owned(),
path: path.to_owned(),
});
}
return Ok(ResolvedSymbol {
module_id: module.id,
module_path: &module.path,
local_path: &symbol.path,
symbol,
});
}
}
}
let (head, tail) = path.split_once('.').unwrap_or((path, ""));
let Some(head_symbol) = module.declarations.symbol(head) else {
return Err(ModuleGraphError::UnknownSymbol {
module: module_path.to_owned(),
path: path.to_owned(),
});
};
match &head_symbol.kind {
CollectedSymbolKind::ModuleAlias { source } => {
if crossing_module_boundary && !head_symbol.public {
return Err(ModuleGraphError::PrivateSymbol {
module: module_path.to_owned(),
path: head.to_owned(),
});
}
if tail.is_empty() {
return Err(ModuleGraphError::UnknownSymbol {
module: source.clone(),
path: String::new(),
});
}
self.resolve_inner(source, tail, true, visited)
}
CollectedSymbolKind::Alias { target, .. } => {
if crossing_module_boundary && !head_symbol.public {
return Err(ModuleGraphError::PrivateSymbol {
module: module_path.to_owned(),
path: head.to_owned(),
});
}
let expanded = if tail.is_empty() {
target.path.clone()
} else {
format!("{}.{tail}", target.path)
};
self.resolve_inner(module_path, &expanded, false, visited)
}
_ => Err(ModuleGraphError::UnknownSymbol {
module: module_path.to_owned(),
path: path.to_owned(),
}),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::parsing::{SourceFile, parse_file};
fn core_graph() -> ModuleGraph {
let mut graph = ModuleGraph::default();
for (path, source) in [
("core://ops.lt", crate::core_lib::OPS_MODULE_FILE_CONTENT),
("core://cmp.lt", crate::core_lib::CMP_MODULE_FILE_CONTENT),
(
"core://clone.lt",
crate::core_lib::CLONE_MODULE_FILE_CONTENT,
),
(
"core://deref.lt",
crate::core_lib::DEREF_MODULE_FILE_CONTENT,
),
("core://drop.lt", crate::core_lib::DROP_MODULE_FILE_CONTENT),
(
"core://non_zero.lt",
crate::core_lib::NON_ZERO_MODULE_FILE_CONTENT,
),
("core://box.lt", crate::core_lib::BOX_MODULE_FILE_CONTENT),
(
"core://option.lt",
crate::core_lib::OPTION_MODULE_FILE_CONTENT,
),
(
"core://primitive.lt",
crate::core_lib::PRIMITIVE_MODULE_FILE_CONTENT,
),
(
"core://prelude.lt",
crate::core_lib::PRELUDE_MODULE_FILE_CONTENT,
),
] {
let parsed = parse_file(SourceFile { path, text: source }).unwrap();
graph
.insert(path, DeclarationIndex::collect(&parsed).unwrap())
.unwrap();
}
graph
.set_prelude(crate::core_lib::PRELUDE_MODULE_FILE_PATH)
.unwrap();
graph
}
#[test]
fn resolves_through_module_and_local_aliases() {
let graph = core_graph();
let add = graph.resolve("core://primitive.lt", "Add").unwrap();
assert_eq!(add.module_path, "core://ops.lt");
assert_eq!(add.local_path, "Add");
let method = graph.resolve("core://primitive.lt", "i8.Add.add").unwrap();
assert_eq!(method.module_path, "core://primitive.lt");
}
#[test]
fn falls_back_to_prelude_but_prefers_local_symbols() {
let mut graph = core_graph();
let empty = parse_file(SourceFile {
path: "app://empty.lt",
text: "",
})
.unwrap();
graph
.insert("app://empty.lt", DeclarationIndex::collect(&empty).unwrap())
.unwrap();
let from_prelude = graph.resolve("app://empty.lt", "i32").unwrap();
assert_eq!(from_prelude.module_path, "core://primitive.lt");
assert_eq!(from_prelude.local_path, "i32");
let local = parse_file(SourceFile {
path: "app://local.lt",
text: "acs i32: fn()",
})
.unwrap();
graph
.insert("app://local.lt", DeclarationIndex::collect(&local).unwrap())
.unwrap();
let resolved_local = graph.resolve("app://local.lt", "i32").unwrap();
assert_eq!(resolved_local.module_path, "app://local.lt");
}
#[test]
fn validates_dependencies() {
let graph = core_graph();
assert!(graph.validate_dependencies().is_empty());
}
#[test]
fn rejects_cross_module_access_to_private_symbols() {
let mut graph = core_graph();
let parsed = parse_file(SourceFile {
path: "app://main.lt",
text: "acs primitive: \"core://primitive.lt\"",
})
.unwrap();
graph
.insert("app://main.lt", DeclarationIndex::collect(&parsed).unwrap())
.unwrap();
let error = graph
.resolve("app://main.lt", "primitive.i8.Add.add")
.unwrap_err();
assert!(matches!(error, ModuleGraphError::PrivateSymbol { .. }));
}
}