use std::collections::{BTreeMap, BTreeSet};
use std::error::Error;
use std::fmt;
use crate::semantic::{
ActiveExtension, CanonicalSymbolPath, CollectedAliasArgument, CollectedSymbolKind,
ExtensionEnvironment, FunctionRegistry, GlobalFunctionId, ModuleGraph, SemanticGenericArgument,
SemanticNamedType, SemanticType,
};
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum MethodSource {
Inherent,
Extension {
origin_module: String,
symbol: Option<String>,
},
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MethodCandidate {
pub name: String,
pub relative_path: String,
pub declaration: CanonicalSymbolPath,
pub source: MethodSource,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct VisibleTraitImplementation {
pub trait_path: String,
pub source: MethodSource,
pub associated_types: BTreeMap<String, String>,
pub concrete_associated_types: BTreeMap<String, SemanticType>,
}
#[derive(Debug, Clone, Default)]
pub struct MethodTable {
methods: BTreeMap<String, Vec<MethodCandidate>>,
pub trait_implementations: Vec<VisibleTraitImplementation>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum MethodLookupError {
UnknownType {
module: String,
path: String,
},
UnknownMethod {
type_: CanonicalSymbolPath,
name: String,
},
AmbiguousMethod {
type_: CanonicalSymbolPath,
name: String,
candidates: Vec<CanonicalSymbolPath>,
},
UnregisteredMethod {
declaration: CanonicalSymbolPath,
},
UnknownAssociatedType {
type_: CanonicalSymbolPath,
name: String,
},
AmbiguousAssociatedType {
type_: CanonicalSymbolPath,
name: String,
candidates: Vec<CanonicalSymbolPath>,
},
}
impl fmt::Display for MethodLookupError {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::UnknownType { module, path } => {
write!(formatter, "unknown type `{module}::{path}`")
}
Self::UnknownMethod { type_, name } => write!(
formatter,
"type `{}::{}` has no visible method `{name}`",
type_.module, type_.local
),
Self::AmbiguousMethod { type_, name, .. } => write!(
formatter,
"method `{name}` is ambiguous for `{}::{}`",
type_.module, type_.local
),
Self::UnregisteredMethod { declaration } => write!(
formatter,
"method `{}::{}` is absent from the global function registry",
declaration.module, declaration.local
),
Self::UnknownAssociatedType { type_, name } => write!(
formatter,
"type `{}::{}` has no visible associated type binding `{name}`",
type_.module, type_.local
),
Self::AmbiguousAssociatedType { type_, name, .. } => write!(
formatter,
"associated type `{name}` is ambiguous for `{}::{}`",
type_.module, type_.local
),
}
}
}
impl Error for MethodLookupError {}
impl MethodTable {
pub fn build(
graph: &ModuleGraph,
target: &CanonicalSymbolPath,
extensions: &ExtensionEnvironment,
) -> Result<Self, MethodLookupError> {
Self::build_inner(graph, target, None, extensions)
}
pub fn build_named(
graph: &ModuleGraph,
target: &SemanticNamedType,
extensions: &ExtensionEnvironment,
) -> Result<Self, MethodLookupError> {
Self::build_inner(graph, &target.path, Some(target), extensions)
}
fn build_inner(
graph: &ModuleGraph,
target: &CanonicalSymbolPath,
concrete_target: Option<&SemanticNamedType>,
extensions: &ExtensionEnvironment,
) -> Result<Self, MethodLookupError> {
let module =
graph
.module(&target.module)
.ok_or_else(|| MethodLookupError::UnknownType {
module: target.module.clone(),
path: target.local.clone(),
})?;
if module.declarations.symbol(&target.local).is_none() {
return Err(MethodLookupError::UnknownType {
module: target.module.clone(),
path: target.local.clone(),
});
}
let mut table = Self::default();
let prefix = format!("{}.", target.local);
for symbol in module.declarations.symbols.values() {
let CollectedSymbolKind::Declaration(ids) = &symbol.kind else {
continue;
};
if ids.function.is_none() {
continue;
}
let Some(relative_path) = symbol.path.strip_prefix(&prefix) else {
continue;
};
table.insert(MethodCandidate {
name: method_name(relative_path).to_owned(),
relative_path: relative_path.to_owned(),
declaration: CanonicalSymbolPath {
module: target.module.clone(),
local: symbol.path.clone(),
},
source: MethodSource::Inherent,
});
}
for implementation in &module.declarations.trait_implementations {
if implementation.owner == target.local {
table
.trait_implementations
.push(VisibleTraitImplementation {
trait_path: implementation.trait_path.clone(),
source: MethodSource::Inherent,
associated_types: associated_types_for(
&module.declarations.symbols,
&format!("{}.{}", implementation.owner, implementation.trait_path),
),
concrete_associated_types: BTreeMap::new(),
});
}
}
for extension in &extensions.extensions {
if &extension.target != target {
continue;
}
table.add_extension(extension, concrete_target);
}
table.trait_implementations.sort_by(|left, right| {
left.trait_path
.cmp(&right.trait_path)
.then_with(|| source_name(&left.source).cmp(&source_name(&right.source)))
});
Ok(table)
}
pub fn candidates(&self, name: &str) -> &[MethodCandidate] {
self.methods.get(name).map(Vec::as_slice).unwrap_or(&[])
}
pub fn resolve(
&self,
target: &CanonicalSymbolPath,
name: &str,
) -> Result<&MethodCandidate, MethodLookupError> {
let candidates = self.candidates(name);
if candidates.is_empty() {
return Err(MethodLookupError::UnknownMethod {
type_: target.clone(),
name: name.to_owned(),
});
}
let direct = candidates
.iter()
.filter(|candidate| candidate.relative_path == name)
.collect::<Vec<_>>();
match direct.as_slice() {
[candidate] => return Ok(candidate),
[] if candidates.len() == 1 => return Ok(&candidates[0]),
_ => {}
}
let unique = candidates
.iter()
.map(|candidate| candidate.declaration.clone())
.collect::<BTreeSet<_>>()
.into_iter()
.collect();
Err(MethodLookupError::AmbiguousMethod {
type_: target.clone(),
name: name.to_owned(),
candidates: unique,
})
}
pub fn resolve_associated_type(
&self,
graph: &ModuleGraph,
target: &CanonicalSymbolPath,
constraint_module: &str,
constraints: &[String],
name: &str,
) -> Result<CanonicalSymbolPath, MethodLookupError> {
let canonical_constraints = constraints
.iter()
.filter_map(|constraint| graph.resolve(constraint_module, constraint).ok())
.map(|resolved| CanonicalSymbolPath::from_resolved(&resolved))
.collect::<BTreeSet<_>>();
let mut candidates = BTreeSet::new();
for implementation in &self.trait_implementations {
let origin = match &implementation.source {
MethodSource::Inherent => target.module.as_str(),
MethodSource::Extension { origin_module, .. } => origin_module.as_str(),
};
let Ok(resolved_trait) = graph.resolve(origin, &implementation.trait_path) else {
continue;
};
let canonical_trait = CanonicalSymbolPath::from_resolved(&resolved_trait);
if !canonical_constraints.contains(&canonical_trait) {
continue;
}
let Some(binding) = implementation.associated_types.get(name) else {
continue;
};
let Ok(resolved_binding) = graph.resolve(origin, binding) else {
continue;
};
candidates.insert(CanonicalSymbolPath::from_resolved(&resolved_binding));
}
match candidates.len() {
0 => Err(MethodLookupError::UnknownAssociatedType {
type_: target.clone(),
name: name.to_owned(),
}),
1 => Ok(candidates.into_iter().next().expect("one candidate")),
_ => Err(MethodLookupError::AmbiguousAssociatedType {
type_: target.clone(),
name: name.to_owned(),
candidates: candidates.into_iter().collect(),
}),
}
}
pub fn resolve_function(
&self,
registry: &FunctionRegistry,
target: &CanonicalSymbolPath,
name: &str,
) -> Result<GlobalFunctionId, MethodLookupError> {
let candidate = self.resolve(target, name)?;
registry.function_id(&candidate.declaration).ok_or_else(|| {
MethodLookupError::UnregisteredMethod {
declaration: candidate.declaration.clone(),
}
})
}
fn add_extension(
&mut self,
extension: &ActiveExtension,
concrete_target: Option<&SemanticNamedType>,
) {
let source = MethodSource::Extension {
origin_module: extension.origin_module.clone(),
symbol: extension.symbol.clone(),
};
for function in &extension.functions {
self.insert(MethodCandidate {
name: method_name(&function.relative_path).to_owned(),
relative_path: function.relative_path.clone(),
declaration: function.declaration.clone(),
source: source.clone(),
});
}
let substitutions = concrete_target
.map(|target| extension_substitutions(extension, target))
.unwrap_or_default();
for implementation in &extension.trait_implementations {
let concrete_associated_types = implementation
.associated_types
.iter()
.filter_map(|(name, binding)| {
substitutions
.get(binding)
.cloned()
.map(|type_| (name.clone(), type_))
})
.collect();
self.trait_implementations.push(VisibleTraitImplementation {
trait_path: implementation.trait_path.clone(),
source: source.clone(),
associated_types: implementation.associated_types.clone(),
concrete_associated_types,
});
}
}
fn insert(&mut self, candidate: MethodCandidate) {
self.methods
.entry(candidate.name.clone())
.or_default()
.push(candidate);
}
}
fn extension_substitutions(
extension: &ActiveExtension,
target: &SemanticNamedType,
) -> BTreeMap<String, SemanticType> {
extension
.target_arguments
.iter()
.zip(&target.generic_arguments)
.filter_map(|(template, concrete)| match (template, concrete) {
(
CollectedAliasArgument::TypeParameter(parameter),
SemanticGenericArgument::Type(type_),
) => Some((parameter.clone(), type_.clone())),
_ => None,
})
.collect()
}
fn associated_types_for(
symbols: &BTreeMap<String, crate::semantic::CollectedSymbol>,
implementation_path: &str,
) -> BTreeMap<String, String> {
let prefix = format!("{implementation_path}.");
symbols
.values()
.filter_map(|symbol| {
let CollectedSymbolKind::AssociatedType {
binding: Some(binding),
} = &symbol.kind
else {
return None;
};
let name = symbol.path.strip_prefix(&prefix)?;
(!name.contains('.')).then_some((name.to_owned(), binding.clone()))
})
.collect()
}
fn method_name(relative_path: &str) -> &str {
relative_path.rsplit('.').next().unwrap_or(relative_path)
}
fn source_name(source: &MethodSource) -> String {
match source {
MethodSource::Inherent => String::new(),
MethodSource::Extension {
origin_module,
symbol,
} => format!("{origin_module}::{}", symbol.as_deref().unwrap_or("<file>")),
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::parsing::{SourceFile, parse_file};
use crate::semantic::{DeclarationIndex, ExtensionEnvironment};
fn insert(graph: &mut ModuleGraph, path: &str, source: &str) {
let parsed = parse_file(SourceFile { path, text: source }).unwrap();
graph
.insert(path, DeclarationIndex::collect(&parsed).unwrap())
.unwrap();
}
#[test]
fn combines_inherent_and_only_visible_extension_methods() {
let mut graph = ModuleGraph::default();
insert(
&mut graph,
"lib://types.lt",
"pub acs Target: { acs own: fn() impl Trait { acs trait_method: fn() } }",
);
insert(
&mut graph,
"lib://extension.lt",
"acs types: \"lib://types.lt\" as extension for types.Target acs extra: fn()",
);
insert(&mut graph, "app://without.lt", "");
insert(
&mut graph,
"app://with.lt",
"acs ext_module: \"lib://extension.lt\"",
);
let target = CanonicalSymbolPath {
module: "lib://types.lt".into(),
local: "Target".into(),
};
let without_environment = ExtensionEnvironment::build(&graph, "app://without.lt").unwrap();
let without = MethodTable::build(&graph, &target, &without_environment).unwrap();
assert!(without.resolve(&target, "own").is_ok());
assert!(without.resolve(&target, "trait_method").is_ok());
assert!(matches!(
without.resolve(&target, "extra"),
Err(MethodLookupError::UnknownMethod { .. })
));
let with_environment = ExtensionEnvironment::build(&graph, "app://with.lt").unwrap();
let with = MethodTable::build(&graph, &target, &with_environment).unwrap();
assert!(matches!(
with.resolve(&target, "extra").unwrap().source,
MethodSource::Extension { .. }
));
}
#[test]
fn visible_extensions_carry_associated_type_bindings() {
let mut graph = ModuleGraph::default();
insert(
&mut graph,
"lib://types.lt",
"pub acs Trait: trait { acs Item: type }
pub acs Target: struct",
);
insert(
&mut graph,
"lib://extension.lt",
"acs types: \"lib://types.lt\"
pub acs ext: extension for types.Target {
impl types.Trait {
acs Item: type = types.Target
}
}",
);
insert(
&mut graph,
"app://main.lt",
"acs ext: \"lib://extension.lt\"
acs target_extension: ext.ext",
);
let target = CanonicalSymbolPath {
module: "lib://types.lt".into(),
local: "Target".into(),
};
let environment = ExtensionEnvironment::build(&graph, "app://main.lt").unwrap();
let table = MethodTable::build(&graph, &target, &environment).unwrap();
let implementation = table
.trait_implementations
.iter()
.find(|implementation| implementation.trait_path == "types.Trait")
.expect("visible trait implementation");
assert_eq!(
implementation
.associated_types
.get("Item")
.map(String::as_str),
Some("types.Target")
);
assert_eq!(
table
.resolve_associated_type(
&graph,
&target,
"lib://types.lt",
&["Trait".into()],
"Item",
)
.unwrap(),
target
);
}
#[test]
fn direct_method_shadows_trait_candidates() {
let mut graph = ModuleGraph::default();
insert(
&mut graph,
"lib://types.lt",
"pub acs Target: { acs call: fn() impl Trait { acs call: fn() } }",
);
insert(&mut graph, "app://main.lt", "");
let target = CanonicalSymbolPath {
module: "lib://types.lt".into(),
local: "Target".into(),
};
let environment = ExtensionEnvironment::build(&graph, "app://main.lt").unwrap();
let table = MethodTable::build(&graph, &target, &environment).unwrap();
assert_eq!(
table.resolve(&target, "call").unwrap().relative_path,
"call"
);
}
#[test]
fn reports_ambiguous_trait_methods() {
let mut graph = ModuleGraph::default();
insert(
&mut graph,
"lib://types.lt",
"pub acs Target: { impl First { acs call: fn() } impl Second { acs call: fn() } }",
);
insert(&mut graph, "app://main.lt", "");
let target = CanonicalSymbolPath {
module: "lib://types.lt".into(),
local: "Target".into(),
};
let environment = ExtensionEnvironment::build(&graph, "app://main.lt").unwrap();
let table = MethodTable::build(&graph, &target, &environment).unwrap();
assert!(matches!(
table.resolve(&target, "call"),
Err(MethodLookupError::AmbiguousMethod { .. })
));
}
}