use crate::environment::{Env, TraitInfo, dups};
use crate::error::BadHead;
use crate::{Error, kinds, module, types, warning::Warning};
use bumpalo::Bump;
use nash_ast::{Annotation, Head, Impl, ImplKey, Pred, QualifiedName, Type};
use nash_region::Located;
use nash_source::Type as SourceType;
use std::collections::{BTreeMap, BTreeSet};
pub(crate) fn info<'a>(
bump: &'a Bump,
home: nash_ast::ModuleName<'a>,
impl_: &Located<Impl<'a>>,
) -> crate::environment::ImplInfo<'a> {
crate::environment::ImplInfo {
variables: impl_.value.variables,
home,
region: impl_.region,
trait_: impl_.value.trait_,
context: impl_.value.context,
heads: impl_.value.heads,
methods: bump.alloc_slice_fill_iter(impl_.value.methods.iter().map(|m| match m {
nash_ast::Def::Def { name, .. } | nash_ast::Def::TypedDef { name, .. } => name.value,
})),
}
}
pub(crate) fn tables<'a>(
bump: &'a Bump,
interfaces: Option<&BTreeMap<&'a str, crate::Interface<'a>>>,
module: &nash_ast::Module<'a>,
kind_env: &kinds::KindEnv<'a>,
) -> Result<crate::environment::Tables<'a>, Vec<Error<'a>>> {
use crate::environment::{MethodInfo, Tables};
let mut tables = Tables {
kinds: kind_env.clone(),
..Tables::default()
};
for interface in interfaces.into_iter().flat_map(|i| i.values()) {
for trait_ in interface.traits {
let name = QualifiedName {
home: interface.home,
name: trait_.name,
};
tables.traits.insert(
name,
bump.alloc(TraitInfo {
home: name.home,
name: name.name,
parameters: trait_.parameters,
kinds: trait_.kinds,
supers: trait_.supers,
methods: bump.alloc_slice_fill_iter(trait_.methods.iter().map(|m| {
MethodInfo {
name: m.name,
annotation: m.annotation,
has_default: m.has_default,
}
})),
}),
);
}
for impl_ in interface.impls {
insert_impl(bump, kind_env, &mut tables.impls, impl_)?;
}
}
for trait_ in module.traits {
let t = &trait_.value;
let name = QualifiedName {
home: module.name,
name: t.name.value,
};
tables.traits.insert(
name,
bump.alloc(TraitInfo {
home: name.home,
name: name.name,
parameters: t.parameters,
kinds: t.kinds,
supers: t.supers,
methods: bump.alloc_slice_fill_iter(t.methods.iter().map(|m| MethodInfo {
name: m.name.value,
annotation: m.annotation,
has_default: m.default.is_some(),
})),
}),
);
}
for impl_ in module.impls {
insert_impl(
bump,
kind_env,
&mut tables.impls,
bump.alloc(info(bump, module.name, impl_)),
)?;
}
for impl_ in tables.impls.values().filter(|i| i.home == module.name) {
crate::entailment::check(bump, &tables, impl_)?;
}
Ok(tables)
}
fn insert_impl<'a>(
bump: &'a Bump,
kinds: &kinds::KindEnv<'a>,
table: &mut crate::environment::ImplTable<'a>,
impl_: &'a crate::environment::ImplInfo<'a>,
) -> Result<(), Vec<Error<'a>>> {
let key = ImplKey {
trait_: impl_.trait_,
heads: bump.alloc_slice_fill_iter(impl_.heads.iter().map(|h| h.value)),
};
for (candidate, first) in table
.iter()
.filter(|(candidate, _)| candidate.trait_ == key.trait_)
{
let overlaps =
nash_ast::head::overlaps(candidate.heads, key.heads, &|head| head_repr(kinds, head))
.map_err(|_| {
vec![Error::OutOfFuel {
region: impl_.region,
}]
})?;
if overlaps {
return Err(vec![Error::OverlappingImpls {
key: bump.alloc(key),
first: first.region,
second: impl_.region,
first_home: first.home,
second_home: impl_.home,
}]);
}
}
table.insert(key, impl_);
Ok(())
}
pub(crate) fn canonicalize<'a>(
bump: &'a Bump,
env: &Env<'a>,
kind_env: &kinds::KindEnv<'a>,
sources: &'a [&'a Located<nash_source::Impl<'a>>],
warnings: &mut Vec<Warning<'a>>,
) -> Result<&'a [&'a Located<Impl<'a>>], Vec<Error<'a>>> {
let mut result = Vec::new();
for source in sources {
let src = &source.value;
if let Some(attribute) = src.attributes.first() {
return Err(vec![Error::Unsupported {
feature: "attributes",
region: attribute.name.region,
}]);
}
let predicate = &src.head.value;
let info = env.find_trait(
bump,
predicate.class.region,
predicate.module,
predicate.class.value,
)?;
if predicate.args.len() != info.parameters.len() {
return Err(vec![Error::TraitArity {
region: src.head.region,
name: info.name,
expected: info.parameters.len(),
actual: predicate.args.len(),
}]);
}
let trait_ = QualifiedName {
home: info.home,
name: info.name,
};
if nash_ast::primitives::ReprTrait::of(trait_).is_some() {
return Err(vec![Error::ImplOfBuiltinTrait {
region: source.region,
trait_,
}]);
}
let mut variables = Vec::new();
let mut heads = Vec::new();
let mut head_types = Vec::new();
for arg in predicate.args {
let (head, typ) =
canonicalize_head(bump, env, arg, &mut variables, trait_.home == env.home)?;
heads.push(head);
head_types.push(typ);
}
if trait_.home != env.home
&& !heads.iter().any(|h| match &h.value {
Head::Named { reference, .. } => {
reference.home == env.home
|| (reference.home == nash_ast::primitives::primitive_home()
&& reference.name == "unit"
&& env.home.package == Some(nash_ast::primitives::BASE))
}
Head::Tuple(_) => env.home.package == Some(nash_ast::primitives::BASE),
Head::Var { .. } | Head::Function(..) => false,
})
{
return Err(vec![Error::OrphanImpl {
region: source.region,
trait_,
heads: bump.alloc_slice_fill_iter(
heads
.iter()
.map(|h| h.value.con().expect("checked outer head")),
),
}]);
}
let mut context = types::canonicalize_context(bump, env, src.context)?.to_vec();
for arg in predicate.args {
context.extend(types::repr_predicates(bump, env, arg)?);
}
let context = &*bump.alloc_slice_fill_iter(context);
for predicate in context {
for argument in predicate.types() {
let mut free = BTreeSet::new();
types::collect_free_vars(&argument.value, &mut free);
if let Some(name) = free.iter().find(|name| !variables.contains(*name)) {
return Err(vec![Error::ImplContextVarNotInHead {
region: argument.region,
name,
}]);
}
}
}
let context = kinds::check_impl(bump, kind_env, info, &head_types, context)?;
let mut classes = vec![nash_ast::primitives::ReprSet::ALL; variables.len()];
for pred in context {
if let Some(required) = pred
.trait_ref()
.and_then(nash_ast::primitives::ReprTrait::of)
&& let [subject] = pred.args()
&& let Type::Var(name) = subject.value
&& let Some(index) = variables.iter().position(|v| *v == name)
{
classes[index] = classes[index].intersect(required.admits());
}
}
for head in &mut heads {
head.value = classed(bump, head.value, &classes);
}
let known_big = |typ| {
if kinds::repr_of(bump, kind_env, typ) == Some(nash_ast::primitives::Repr::Big) {
return true;
}
let subject = kinds::representation_subject(bump, kind_env, typ);
let big = nash_ast::primitives::ReprTrait::Big.qualified();
let wanted = Pred::Implied {
trait_: big,
args: bump.alloc_slice_copy(&[subject]),
};
context.iter().any(|given| {
given.trait_ref() == Some(big)
&& (Pred::Implied {
trait_: big,
args: bump.alloc_slice_copy(&[kinds::representation_subject(
bump,
kind_env,
given.args()[0],
)]),
})
.key()
== wanted.key()
})
};
if trait_ == nash_ast::primitives::eq_trait()
&& let [head] = head_types.as_slice()
&& (known_big(*head)
|| matches!(heads[0].value, Head::Var { repr, .. } if repr.contains(nash_ast::primitives::Repr::Big)))
{
return Err(vec![Error::StructuralEqOverride { head }]);
}
if trait_ == nash_ast::primitives::lift_trait()
&& let [left, right] = heads.as_slice()
&& nash_ast::head::can_equal(&[left.value], &[right.value], &|head| {
head_repr(kind_env, head)
})
.map_err(|_| {
vec![Error::OutOfFuel {
region: source.region,
}]
})?
{
return Err(vec![Error::ReflexiveLiftOverlap {
heads: bump.alloc_slice_copy(&head_types),
}]);
}
let names = dups::detect(
src.methods.iter().map(|m| {
let nash_source::Def::Define { name, .. } = &m.value else {
unreachable!("named impl method")
};
(name.value, name.region)
}),
|name, first, second| Error::DuplicateMethod {
name,
first,
second,
},
)?;
let mut methods = Vec::new();
for definition in src.methods {
let nash_source::Def::Define { name, .. } = &definition.value else {
unreachable!("named impl method")
};
let method = info
.methods
.iter()
.find(|m| m.name == name.value)
.ok_or_else(|| {
vec![Error::UnknownMethod {
region: name.region,
trait_: info.name,
name: name.value,
}]
})?;
let scheme = instantiate_method(
bump,
kind_env,
info,
method,
&head_types,
context,
&variables,
)?;
methods.push(module::canonicalize_typed_value(
bump, env, definition, scheme, warnings,
)?);
}
for method in info.methods {
if !method.has_default && !names.contains_key(method.name) {
return Err(vec![Error::MissingMethod {
region: source.region,
trait_: info.name,
name: method.name,
}]);
}
}
result.push(&*bump.alloc(Located::at(
source.region,
Impl {
variables: bump.alloc_slice_fill_iter(variables),
trait_,
context,
heads: bump.alloc_slice_fill_iter(heads),
methods: bump.alloc_slice_fill_iter(methods),
},
)));
}
Ok(bump.alloc_slice_fill_iter(result))
}
type CanonicalHead<'a> = (Located<Head<'a>>, &'a Located<Type<'a>>);
fn canonicalize_head<'a>(
bump: &'a Bump,
env: &Env<'a>,
typ: &'a Located<SourceType<'a>>,
variables: &mut Vec<&'a str>,
owns_trait: bool,
) -> Result<CanonicalHead<'a>, Vec<Error<'a>>> {
let reason = match typ.value.unannotated() {
SourceType::Var(_) if !owns_trait => Some(BadHead::BareVariable),
SourceType::Lambda { .. } => Some(BadHead::Function),
SourceType::Record(_) => Some(BadHead::Record),
SourceType::VarApp { .. } => Some(BadHead::VariableApplication),
_ => None,
};
if let Some(reason) = reason {
return Err(vec![Error::BadInstanceHead {
region: typ.region,
reason,
}]);
}
let canonical = types::canonicalize_type(bump, env, typ)?;
let head = canonicalize_pattern(bump, canonical, variables)?;
Ok((Located::at(typ.region, head), canonical))
}
fn canonicalize_pattern<'a>(
bump: &'a Bump,
typ: &'a Located<Type<'a>>,
variables: &mut Vec<&'a str>,
) -> Result<Head<'a>, Vec<Error<'a>>> {
let head = match &typ.value {
Type::Var(name) => {
let index = match variables.iter().position(|existing| existing == name) {
Some(index) => index,
None => {
variables.push(name);
variables.len() - 1
}
};
Head::Var {
index: index.try_into().expect("impl variable count exceeds u16"),
repr: nash_ast::primitives::ReprSet::ALL,
}
}
Type::Named { reference, args } => {
let args = args
.iter()
.map(|arg| canonicalize_pattern(bump, arg, variables))
.collect::<Result<Vec<_>, _>>()?;
Head::Named {
reference: *reference,
args: bump.alloc_slice_fill_iter(args),
}
}
Type::Alias {
reference,
arguments,
..
} => {
let args = arguments
.iter()
.map(|arg| canonicalize_pattern(bump, arg.typ, variables))
.collect::<Result<Vec<_>, _>>()?;
Head::Named {
reference: *reference,
args: bump.alloc_slice_fill_iter(args),
}
}
Type::Tuple {
first,
second,
rest,
} => {
let args = [*first, *second]
.into_iter()
.chain(rest.iter().copied())
.map(|arg| canonicalize_pattern(bump, arg, variables))
.collect::<Result<Vec<_>, _>>()?;
Head::Tuple(bump.alloc_slice_fill_iter(args))
}
Type::Lambda { from, to } => Head::Function(
bump.alloc(canonicalize_pattern(bump, from, variables)?),
bump.alloc(canonicalize_pattern(bump, to, variables)?),
),
Type::App { .. } | Type::Record { .. } => {
return Err(vec![Error::BadInstanceHead {
region: typ.region,
reason: if matches!(typ.value, Type::App { .. }) {
BadHead::VariableApplication
} else {
BadHead::Record
},
}]);
}
};
Ok(head)
}
fn instantiate_method<'a>(
bump: &'a Bump,
kind_env: &kinds::KindEnv<'a>,
info: &TraitInfo<'a>,
method: &crate::environment::MethodInfo<'a>,
heads: &[&'a Located<Type<'a>>],
context: &'a [Pred<'a>],
head_vars: &[&'a str],
) -> Result<&'a Annotation<'a>, Vec<Error<'a>>> {
let annotation = method.annotation;
let mut substitution: BTreeMap<_, _> = info
.parameters
.iter()
.copied()
.zip(heads.iter().copied())
.collect();
let mut used: BTreeSet<_> = annotation
.free_vars
.iter()
.copied()
.chain(head_vars.iter().copied())
.collect();
for var in annotation.free_vars {
if !info.parameters.contains(var) && head_vars.contains(var) {
let mut index = 0;
let fresh = loop {
let candidate = format!("$impl{index}");
if !used.contains(candidate.as_str()) {
break &*bump.alloc_str(&candidate);
}
index += 1;
};
used.insert(fresh);
substitution.insert(var, bump.alloc(Located::at_zero(Type::Var(fresh))));
}
}
let typ = types::substitute_type(bump, &substitution, annotation.typ);
let mut predicates = context.to_vec();
let owner = QualifiedName {
home: info.home,
name: info.name,
};
let owner_key = Pred::Trait {
trait_: owner,
args: bump.alloc_slice_fill_iter(
info.parameters
.iter()
.map(|name| &*bump.alloc(Located::at_zero(Type::Var(name)))),
),
}
.key();
predicates.extend(
annotation
.context
.iter()
.filter(|p| p.key() != owner_key)
.map(|p| kinds::substitute_predicate(bump, &substitution, *p)),
);
let mut free: BTreeSet<_> = head_vars.iter().copied().collect();
types::collect_free_vars(&typ.value, &mut free);
for predicate in &predicates {
for arg in predicate.types() {
types::collect_free_vars(&arg.value, &mut free);
}
}
let annotation = Annotation {
free_vars: bump.alloc_slice_fill_iter(free),
context: bump.alloc_slice_fill_iter(predicates),
typ,
};
kinds::check_annotation(bump, kind_env, method.name, bump.alloc(annotation))
}
fn head_repr(env: &kinds::KindEnv<'_>, head: &Head<'_>) -> Option<nash_ast::primitives::Repr> {
match head {
Head::Var { .. } => None,
Head::Tuple(_) | Head::Function(..) => Some(nash_ast::primitives::Repr::Term),
Head::Named { reference, .. } => match env.constructor(*reference) {
kinds::TypeInfo::Builtin(info) => Some(info.repr),
kinds::TypeInfo::Defined { repr, .. } => repr,
},
}
}
fn classed<'a>(
bump: &'a Bump,
head: Head<'a>,
classes: &[nash_ast::primitives::ReprSet],
) -> Head<'a> {
match head {
Head::Var { index, .. } => Head::Var {
index,
repr: classes[usize::from(index)],
},
Head::Named { reference, args } => Head::Named {
reference,
args: bump.alloc_slice_fill_iter(args.iter().map(|h| classed(bump, *h, classes))),
},
Head::Tuple(args) => {
Head::Tuple(bump.alloc_slice_fill_iter(args.iter().map(|h| classed(bump, *h, classes))))
}
Head::Function(a, b) => Head::Function(
bump.alloc(classed(bump, *a, classes)),
bump.alloc(classed(bump, *b, classes)),
),
}
}