use std::collections::BTreeMap;
use bumpalo::Bump;
use nash_ast::fuel::{OutOfFuel, tick};
use nash_ast::{Pred, QualifiedName, Type};
use nash_region::Located;
use crate::Error;
use crate::environment::{ImplInfo, Tables};
#[derive(Clone, Copy, Debug)]
pub enum Failure {
Missing,
Cycle,
}
#[derive(Clone, Copy)]
enum Stop {
Failed(Failure),
OutOfFuel,
}
impl From<Failure> for Stop {
fn from(failure: Failure) -> Self {
Self::Failed(failure)
}
}
impl From<OutOfFuel> for Stop {
fn from(OutOfFuel: OutOfFuel) -> Self {
Self::OutOfFuel
}
}
#[derive(Clone, Copy, PartialEq, Eq)]
enum Constructor<'a> {
Var(&'a str),
Named(QualifiedName<'a>),
Tuple(usize),
Function,
Record { fields: &'a [&'a str] },
}
struct Term<'a> {
con: Constructor<'a>,
args: &'a [&'a Term<'a>],
}
#[derive(Clone, Copy)]
struct Predicate<'a> {
trait_: Option<QualifiedName<'a>>,
args: &'a [&'a Term<'a>],
}
type Substitution<'a> = BTreeMap<&'a str, &'a Term<'a>>;
struct Resolver<'t, 'a> {
bump: &'a Bump,
tables: &'t Tables<'a>,
}
impl<'a> Resolver<'_, 'a> {
fn canonical(&mut self, term: &'a Term<'a>) -> Result<&'a Located<Type<'a>>, Stop> {
tick()?;
let mut args = Vec::new();
for arg in term.args {
args.push(self.canonical(arg)?);
}
let args = self.bump.alloc_slice_fill_iter(args);
let typ = match term.con {
Constructor::Named(reference) => Type::Named { reference, args },
Constructor::Var(name) if args.is_empty() => Type::Var(name),
Constructor::Var(name) => Type::App {
head: self.bump.alloc(Located::at_zero(Type::Var(name))),
args,
},
Constructor::Tuple(_) => Type::Tuple {
first: args[0],
second: args[1],
rest: &args[2..],
},
Constructor::Function => Type::Lambda {
from: args[0],
to: args[1],
},
Constructor::Record { fields } => Type::Record {
fields: self.bump.alloc_slice_fill_iter(
fields
.iter()
.zip(args.iter())
.enumerate()
.map(|(index, (field, typ))| nash_ast::FieldType {
index: index as u16,
field,
typ,
}),
),
},
};
Ok(self.bump.alloc(Located::at_zero(typ)))
}
fn term(
&mut self,
typ: &'a Located<Type<'a>>,
subst: &Substitution<'a>,
) -> Result<&'a Term<'a>, Stop> {
tick()?;
let (con, args): (_, Vec<_>) = match &typ.value {
Type::Var(name) => {
if let Some(term) = subst.get(name) {
return Ok(term);
}
(Constructor::Var(name), Vec::new())
}
Type::Named { reference, args } => (Constructor::Named(*reference), args.to_vec()),
Type::Alias {
reference,
arguments,
..
} => (
Constructor::Named(*reference),
arguments.iter().map(|a| a.typ).collect(),
),
Type::Tuple {
first,
second,
rest,
} => (
Constructor::Tuple(2 + rest.len()),
[*first, *second]
.into_iter()
.chain(rest.iter().copied())
.collect(),
),
Type::Lambda { from, to } => (Constructor::Function, vec![*from, *to]),
Type::Record { fields } => (
Constructor::Record {
fields: self
.bump
.alloc_slice_fill_iter(fields.iter().map(|f| f.field)),
},
fields.iter().map(|f| f.typ).collect(),
),
Type::App { head, args } => {
let head = self.term(head, subst)?;
let mut applied = head.args.to_vec();
for arg in *args {
applied.push(self.term(arg, subst)?);
}
return Ok(self.bump.alloc(Term {
con: head.con,
args: self.bump.alloc_slice_fill_iter(applied),
}));
}
};
let mut terms = Vec::new();
for arg in args {
terms.push(self.term(arg, subst)?);
}
Ok(self.bump.alloc(Term {
con,
args: self.bump.alloc_slice_fill_iter(terms),
}))
}
fn predicate(
&mut self,
pred: &Pred<'a>,
subst: &Substitution<'a>,
) -> Result<Predicate<'a>, Stop> {
tick()?;
let mut args = Vec::new();
for arg in pred.types() {
args.push(self.term(arg, subst)?);
}
Ok(Predicate {
trait_: pred.trait_ref(),
args: self.bump.alloc_slice_fill_iter(args),
})
}
fn equal(&mut self, a: Predicate<'a>, b: Predicate<'a>) -> Result<bool, Stop> {
tick()?;
if a.trait_ != b.trait_ || a.args.len() != b.args.len() {
return Ok(false);
}
let mut left = a.args.to_vec();
let mut right = b.args.to_vec();
if a.trait_
.and_then(nash_ast::primitives::ReprTrait::of)
.is_some()
{
for term in left.iter_mut().chain(&mut right) {
let canonical = self.canonical(term)?;
let subject =
crate::kinds::representation_subject(self.bump, &self.tables.kinds, canonical);
*term = self.term(subject, &BTreeMap::new())?;
}
}
let mut pending: Vec<_> = left.into_iter().zip(right).collect();
while let Some((a, b)) = pending.pop() {
tick()?;
if a.con != b.con || a.args.len() != b.args.len() {
return Ok(false);
}
pending.extend(a.args.iter().copied().zip(b.args.iter().copied()));
}
Ok(true)
}
fn givens(&mut self, context: &[Pred<'a>]) -> Result<Vec<Predicate<'a>>, Stop> {
let mut pending = Vec::new();
for pred in context {
pending.push(self.predicate(pred, &BTreeMap::new())?);
}
let mut result = Vec::new();
while let Some(pred) = pending.pop() {
tick()?;
let mut seen = false;
for old in &result {
if self.equal(pred, *old)? {
seen = true;
break;
}
}
if seen {
continue;
}
result.push(pred);
let Some(name) = pred.trait_ else {
continue;
};
if let Some(repr) = nash_ast::primitives::ReprTrait::of(name) {
for superclass in repr.supers() {
pending.push(Predicate {
trait_: Some(superclass.qualified()),
args: pred.args,
});
}
continue;
}
let trait_ = self.tables.traits[&name];
let subst = trait_
.parameters
.iter()
.copied()
.zip(pred.args.iter().copied())
.collect();
for sup in trait_.supers {
pending.push(self.predicate(sup, &subst)?);
}
}
Ok(result)
}
fn resolve(
&mut self,
given: &[Predicate<'a>],
wanted: Predicate<'a>,
active: &mut Vec<Predicate<'a>>,
) -> Result<(), Stop> {
tick()?;
for pred in given {
if self.equal(*pred, wanted)? {
return Ok(());
}
}
let mut class_givens = Vec::new();
for pred in given {
if let Some(trait_) = pred
.trait_
.filter(|name| nash_ast::primitives::ReprTrait::of(*name).is_some())
{
let args = pred
.args
.iter()
.map(|arg| self.canonical(arg))
.collect::<Result<Vec<_>, _>>()?;
class_givens.push(Pred::Implied {
trait_,
args: self.bump.alloc_slice_fill_iter(args),
});
}
}
if let Some(required) = wanted.trait_.and_then(nash_ast::primitives::ReprTrait::of) {
let typ = self.canonical(wanted.args[0])?;
return match crate::kinds::in_class(
self.bump,
&self.tables.kinds,
typ,
required.admits(),
&class_givens,
) {
nash_ast::head::Match::Yes(()) => Ok(()),
_ => Err(Failure::Missing.into()),
};
}
if wanted.trait_.is_none() {
let head = self.canonical(wanted.args[0])?;
let args: Vec<_> = wanted.args[1..]
.iter()
.map(|arg| self.canonical(arg))
.collect::<Result<_, _>>()?;
let group = Default::default();
let mut formation = crate::kinds::Formation::new(self.bump, &self.tables.kinds, &group);
formation
.reduce(Pred::Apply {
head,
args: self.bump.alloc_slice_fill_iter(args),
})
.map_err(|_| Failure::Missing)?;
for pred in formation.predicates {
let child = self.predicate(&pred, &BTreeMap::new())?;
if self.equal(child, wanted)? {
return Err(Failure::Missing.into());
}
self.resolve(given, child, active)?;
}
return Ok(());
}
if self.tables.has_structural_eq()
&& wanted.trait_ == Some(nash_ast::primitives::eq_trait())
&& wanted.args.len() == 1
{
let big = Predicate {
trait_: Some(nash_ast::primitives::ReprTrait::Big.qualified()),
args: &wanted.args[..1],
};
match self.resolve(given, big, active) {
Ok(()) => return Ok(()),
Err(Stop::Failed(Failure::Missing)) => {}
Err(stop) => return Err(stop),
}
}
if self.tables.has_reflexive_lift()
&& wanted.trait_ == Some(nash_ast::primitives::lift_trait())
&& wanted.args.len() == 2
&& self.equal(
Predicate {
trait_: wanted.trait_,
args: &wanted.args[..1],
},
Predicate {
trait_: wanted.trait_,
args: &wanted.args[1..],
},
)?
{
return Ok(());
}
for pred in active.iter() {
if self.equal(*pred, wanted)? {
return Err(Failure::Cycle.into());
}
}
let canonical_args: Vec<_> = wanted
.args
.iter()
.map(|arg| self.canonical(arg))
.collect::<Result<_, _>>()?;
let candidates = self
.tables
.impls_for(wanted.trait_.ok_or(Failure::Missing)?)
.map(|(key, info)| (key.heads, info.variables.len(), *info));
let selection = nash_ast::head::select_impl(
&mut nash_ast::head::Canonical(&|typ, class| {
crate::kinds::in_class(self.bump, &self.tables.kinds, typ, class, &class_givens)
}),
candidates,
&canonical_args,
nash_ast::head::SelectPolicy::Exact,
)?;
let nash_ast::head::ImplSelection::Selected {
info: impl_,
arguments,
} = selection
else {
return Err(Failure::Missing.into());
};
let mut subst = BTreeMap::new();
for (name, argument) in impl_.variables.iter().zip(arguments) {
subst.insert(*name, self.term(argument, &BTreeMap::new())?);
}
active.push(wanted);
for pred in impl_.context {
let wanted = self.predicate(pred, &subst)?;
self.resolve(given, wanted, active)?;
}
active.pop();
Ok(())
}
}
pub(crate) fn check<'a>(
bump: &'a Bump,
tables: &Tables<'a>,
impl_: &ImplInfo<'a>,
) -> Result<(), Vec<Error<'a>>> {
let trait_ = tables.traits[&impl_.trait_];
if trait_.supers.is_empty() {
return Ok(());
}
let canonical_subst: BTreeMap<_, _> = trait_
.parameters
.iter()
.zip(impl_.heads)
.map(|(parameter, head)| {
(
*parameter,
head.value.to_type(bump, impl_.variables, head.region),
)
})
.collect();
let mut resolver = Resolver { bump, tables };
let givens = resolver.givens(impl_.context);
for (index, superclass) in trait_.supers.iter().enumerate() {
let checked: Result<(), Stop> = (|| {
let givens = givens.as_ref().map_err(|stop| *stop)?;
let mut subst = BTreeMap::new();
for (parameter, typ) in &canonical_subst {
subst.insert(*parameter, resolver.term(typ, &BTreeMap::new())?);
}
let wanted = resolver.predicate(superclass, &subst)?;
resolver.resolve(givens, wanted, &mut Vec::new())
})();
if let Err(stop) = checked {
let Stop::Failed(reason) = stop else {
return Err(vec![Error::OutOfFuel {
region: impl_.region,
}]);
};
return Err(vec![Error::MissingSuperclass {
region: impl_.region,
trait_: impl_.trait_,
heads: impl_.heads,
superclass: bump.alloc(crate::kinds::substitute_predicate(
bump,
&canonical_subst,
*superclass,
)),
index: index as u16,
reason,
}]);
}
}
Ok(())
}