pub mod dups;
pub mod foreign;
pub mod local;
use std::collections::BTreeMap;
use bumpalo::Bump;
use nash_ast::{Associativity, CtorOpts, ModuleName, Precedence, Type as CanType};
use nash_region::{Located, Region};
use crate::Error;
#[derive(Clone, Debug)]
pub enum Info<'a, T> {
Specific(ModuleName<'a>, T),
Ambiguous(ModuleName<'a>, Vec<ModuleName<'a>>),
}
pub type Exposed<'a, T> = BTreeMap<&'a str, Info<'a, T>>;
pub type Qualified<'a, T> = BTreeMap<&'a str, BTreeMap<&'a str, Info<'a, T>>>;
#[derive(Clone, Copy, Debug)]
pub struct TraitInfo<'a> {
pub home: ModuleName<'a>,
pub name: &'a str,
pub parameters: &'a [&'a str],
pub kinds: &'a [&'a nash_ast::Kind<'a>],
pub supers: &'a [nash_ast::Pred<'a>],
pub methods: &'a [MethodInfo<'a>],
}
#[derive(Clone, Copy, Debug)]
pub struct MethodInfo<'a> {
pub name: &'a str,
pub annotation: &'a nash_ast::Annotation<'a>,
pub has_default: bool,
}
#[derive(Clone, Copy, Debug)]
pub struct ImplInfo<'a> {
pub variables: &'a [&'a str],
pub home: ModuleName<'a>,
pub region: Region,
pub trait_: nash_ast::QualifiedName<'a>,
pub context: &'a [nash_ast::Pred<'a>],
pub heads: &'a [Located<nash_ast::Head<'a>>],
pub methods: &'a [&'a str],
}
pub type ImplTable<'a> = BTreeMap<nash_ast::ImplKey<'a>, &'a ImplInfo<'a>>;
#[derive(Clone, Debug, Default)]
pub struct Tables<'a> {
pub fields: BTreeMap<nash_ast::QualifiedName<'a>, LabeledUnion<'a>>,
pub test_fields: BTreeMap<nash_ast::QualifiedName<'a>, LabeledUnion<'a>>,
pub kinds: crate::kinds::KindEnv<'a>,
pub traits: BTreeMap<nash_ast::QualifiedName<'a>, &'a TraitInfo<'a>>,
pub impls: ImplTable<'a>,
}
#[derive(Clone, Copy, Debug)]
pub struct LabeledUnion<'a> {
pub parameters: &'a [&'a str],
pub fields: &'a [nash_ast::FieldType<'a>],
}
pub fn visible_fields<'a>(
bump: &'a Bump,
env: &Env<'a>,
) -> BTreeMap<nash_ast::QualifiedName<'a>, LabeledUnion<'a>> {
let mut fields = BTreeMap::new();
for info in env
.ctors
.values()
.chain(env.q_ctors.values().flat_map(|ctors| ctors.values()))
{
if let Info::Specific(
_,
Ctor::Union {
home,
type_name,
union,
..
},
) = info
&& let Some(labels) = union.labeled_fields()
{
fields
.entry(nash_ast::QualifiedName {
home: *home,
name: type_name,
})
.or_insert_with(|| LabeledUnion {
parameters: union.parameters,
fields: bump.alloc_slice_fill_iter(labels),
});
}
}
fields
}
impl<'a> Tables<'a> {
pub fn impls_for(
&self,
trait_: nash_ast::QualifiedName<'a>,
) -> impl Iterator<Item = (&nash_ast::ImplKey<'a>, &&'a ImplInfo<'a>)> {
self.impls
.range(nash_ast::ImplKey { trait_, heads: &[] }..)
.take_while(move |(key, _)| key.trait_ == trait_)
}
pub fn has_structural_eq(&self) -> bool {
self.traits.contains_key(&nash_ast::primitives::eq_trait())
}
pub fn has_reflexive_lift(&self) -> bool {
self.traits
.contains_key(&nash_ast::primitives::lift_trait())
}
}
#[derive(Clone, Debug)]
pub enum Var<'a> {
Method {
trait_: nash_ast::QualifiedName<'a>,
annotation: &'a nash_ast::Annotation<'a>,
local_region: Option<Region>,
},
TopLevel(Region),
Foreign(ModuleName<'a>, &'a nash_ast::Annotation<'a>),
Foreigns(ModuleName<'a>, Vec<ModuleName<'a>>),
}
#[derive(Clone, Copy, Debug)]
pub struct QualifiedValue<'a> {
pub annotation: &'a nash_ast::Annotation<'a>,
pub trait_: Option<nash_ast::QualifiedName<'a>>,
}
#[derive(Clone, Copy, Debug)]
pub enum Type<'a> {
Alias {
arity: usize,
home: ModuleName<'a>,
parameters: &'a [&'a str],
typ: &'a Located<CanType<'a>>,
},
Union {
arity: usize,
home: ModuleName<'a>,
},
}
#[derive(Clone, Copy, Debug)]
pub enum Ctor<'a> {
Union {
home: ModuleName<'a>,
type_name: &'a str,
type_vars: &'a [&'a str],
union: &'a nash_ast::Union<'a>,
index: u16,
arity: u16,
arguments: &'a [&'a Located<CanType<'a>>],
options: CtorOpts,
alternatives: u16,
},
Bool {
home: ModuleName<'a>,
union: &'a nash_ast::Union<'a>,
index: u16,
},
RecordCtor {
home: ModuleName<'a>,
alias_name: &'a str,
type_vars: &'a [&'a str],
typ: &'a Located<CanType<'a>>,
fields: &'a [nash_ast::FieldType<'a>],
},
}
pub fn make_record_ctor<'a>(
bump: &'a Bump,
home: ModuleName<'a>,
alias_name: &'a str,
parameters: &'a [&'a str],
record_type: &'a Located<CanType<'a>>,
fields: &'a [nash_ast::FieldType<'a>],
) -> Ctor<'a> {
let arguments =
bump.alloc_slice_fill_iter(parameters.iter().map(|var| nash_ast::AliasArgument {
name: var,
typ: bump.alloc(Located::at(Region::zero(), CanType::Var(var))),
}));
let result: &'a Located<CanType<'a>> = bump.alloc(Located::at(
Region::zero(),
CanType::Alias {
remaining: &[],
reference: nash_ast::QualifiedName {
home,
name: alias_name,
},
arguments,
target: nash_ast::AliasType::Open(record_type),
},
));
let mut fields_in_source_order: Vec<&nash_ast::FieldType<'a>> = fields.iter().collect();
fields_in_source_order.sort_by_key(|f| f.index);
let mut typ = result;
for field in fields_in_source_order.into_iter().rev() {
typ = bump.alloc(Located::at(
Region::zero(),
CanType::Lambda {
from: field.typ,
to: typ,
},
));
}
Ctor::RecordCtor {
home,
alias_name,
type_vars: parameters,
typ,
fields,
}
}
#[derive(Clone, Copy, Debug)]
pub struct Binop<'a> {
pub symbol: &'a str,
pub home: ModuleName<'a>,
pub function: nash_ast::QualifiedName<'a>,
pub annotation: &'a nash_ast::Annotation<'a>,
pub associativity: Associativity,
pub precedence: Precedence,
}
#[derive(Clone)]
pub struct Env<'a> {
pub kinds: crate::kinds::KindEnv<'a>,
pub traits: Exposed<'a, &'a TraitInfo<'a>>,
pub q_traits: Qualified<'a, &'a TraitInfo<'a>>,
pub home: ModuleName<'a>,
pub vars: BTreeMap<&'a str, Var<'a>>,
pub types: Exposed<'a, Type<'a>>,
pub ctors: Exposed<'a, Ctor<'a>>,
pub binops: Exposed<'a, Binop<'a>>,
pub q_vars: Qualified<'a, QualifiedValue<'a>>,
pub q_types: Qualified<'a, Type<'a>>,
pub q_ctors: Qualified<'a, Ctor<'a>>,
}
pub struct Scope<'scope, 'a> {
pub module: &'scope Env<'a>,
parent: Option<&'scope Scope<'scope, 'a>>,
bindings: &'scope BTreeMap<&'a str, Region>,
}
impl<'scope, 'a> Scope<'scope, 'a> {
pub fn new(
module: &'scope Env<'a>,
parent: Option<&'scope Scope<'scope, 'a>>,
bindings: &'scope BTreeMap<&'a str, Region>,
) -> Result<Self, Vec<Error<'a>>> {
let mut errors = Vec::new();
for (&name, ®ion) in bindings {
let original = parent.and_then(|scope| scope.local(name)).or_else(|| {
match module.vars.get(name) {
Some(Var::TopLevel(original))
| Some(Var::Method {
local_region: Some(original),
..
}) => Some(*original),
_ => None,
}
});
if let Some(original) = original {
errors.push(Error::Shadowing {
name,
original,
new: region,
});
}
}
if errors.is_empty() {
Ok(Self {
module,
parent,
bindings,
})
} else {
Err(errors)
}
}
pub fn add_locals<'child>(
&'child self,
bindings: &'child BTreeMap<&'a str, Region>,
) -> Result<Scope<'child, 'a>, Vec<Error<'a>>> {
Scope::new(self.module, Some(self), bindings)
}
pub fn local(&self, name: &str) -> Option<Region> {
let mut scope = Some(self);
while let Some(current) = scope {
if let Some(region) = current.bindings.get(name) {
return Some(*region);
}
scope = current.parent;
}
None
}
pub fn possible_var_names(&self, bump: &'a Bump) -> crate::error::PossibleNames<'a> {
let mut names: std::collections::BTreeSet<_> = self.module.vars.keys().copied().collect();
let mut scope = Some(self);
while let Some(current) = scope {
names.extend(current.bindings.keys().copied());
scope = current.parent;
}
let locals = bump.alloc_slice_fill_iter(names);
let qualified =
bump.alloc_slice_fill_iter(self.module.q_vars.iter().map(|(prefix, inner)| {
let names = bump.alloc_slice_fill_iter(inner.keys().copied());
(*prefix, names as &[&str])
}));
crate::error::PossibleNames { locals, qualified }
}
}
impl<'a> Env<'a> {
pub fn method_annotation(
&self,
trait_: nash_ast::QualifiedName<'a>,
method: &str,
) -> Option<&'a nash_ast::Annotation<'a>> {
self.traits
.values()
.chain(self.q_traits.values().flat_map(|traits| traits.values()))
.find_map(|info| match info {
Info::Specific(_, info) if info.home == trait_.home && info.name == trait_.name => {
info.methods
.iter()
.find(|info| info.name == method)
.map(|info| info.annotation)
}
_ => None,
})
}
pub fn find_trait(
&self,
bump: &'a Bump,
region: Region,
prefix: Option<&'a str>,
name: &'a str,
) -> Result<&'a TraitInfo<'a>, Vec<Error<'a>>> {
let found = match prefix {
Some(prefix) => self
.q_traits
.get(prefix)
.and_then(|traits| traits.get(name)),
None => self.traits.get(name),
};
match found {
Some(Info::Specific(_, info)) => Ok(info),
Some(Info::Ambiguous(first, others)) => Err(vec![Error::AmbiguousTrait {
region,
prefix,
name,
first_module: *first,
other_modules: bump.alloc_slice_copy(others),
}]),
None => Err(vec![Error::NotFoundTrait {
region,
prefix,
name,
}]),
}
}
pub fn insert_local_type(&mut self, name: &'a str, typ: Type<'a>) {
self.types.insert(name, Info::Specific(self.home, typ));
self.q_types
.entry(self.home.name)
.or_default()
.insert(name, Info::Specific(self.home, typ));
}
pub fn insert_local_ctor(&mut self, name: &'a str, ctor: Ctor<'a>) {
self.ctors.insert(name, Info::Specific(self.home, ctor));
self.q_ctors
.entry(self.home.name)
.or_default()
.insert(name, Info::Specific(self.home, ctor));
}
pub fn find_ctor(
&self,
bump: &'a Bump,
region: Region,
name: &'a str,
) -> Result<Ctor<'a>, Vec<Error<'a>>> {
match self.ctors.get(name) {
Some(Info::Specific(_, ctor)) => Ok(*ctor),
Some(Info::Ambiguous(first, others)) => Err(vec![Error::AmbiguousCtor {
region,
prefix: None,
name,
first_module: *first,
other_modules: bump.alloc_slice_fill_iter(others.iter().copied()),
}]),
None => Err(vec![Error::NotFoundCtor {
region,
prefix: None,
name,
suggestions: self.possible_ctor_names(bump),
}]),
}
}
pub fn find_ctor_qual(
&self,
bump: &'a Bump,
region: Region,
prefix: &'a str,
name: &'a str,
) -> Result<Ctor<'a>, Vec<Error<'a>>> {
let info = self
.q_ctors
.get(prefix)
.and_then(|m| m.get(name))
.ok_or_else(|| {
vec![Error::NotFoundCtor {
region,
prefix: Some(prefix),
name,
suggestions: self.possible_ctor_names(bump),
}]
})?;
match info {
Info::Specific(_, ctor) => Ok(*ctor),
Info::Ambiguous(first, others) => Err(vec![Error::AmbiguousCtor {
region,
prefix: Some(prefix),
name,
first_module: *first,
other_modules: bump.alloc_slice_fill_iter(others.iter().copied()),
}]),
}
}
pub fn find_binop(
&self,
bump: &'a Bump,
region: Region,
symbol: &'a str,
) -> Result<Binop<'a>, Vec<Error<'a>>> {
match self.binops.get(symbol) {
Some(Info::Specific(_, binop)) => Ok(*binop),
Some(Info::Ambiguous(first, others)) => Err(vec![Error::AmbiguousBinop {
region,
name: symbol,
first_module: *first,
other_modules: bump.alloc_slice_fill_iter(others.iter().copied()),
}]),
None => Err(vec![Error::NotFoundBinop {
region,
name: symbol,
available: self.available_binops(bump),
}]),
}
}
fn available_binops(&self, bump: &'a Bump) -> &'a [&'a str] {
bump.alloc_slice_fill_iter(self.binops.keys().copied())
}
pub fn possible_type_names(&self, bump: &'a Bump) -> crate::error::PossibleNames<'a> {
let locals = bump.alloc_slice_fill_iter(self.types.keys().copied());
let qualified = bump.alloc_slice_fill_iter(self.q_types.iter().map(|(prefix, inner)| {
let names = bump.alloc_slice_fill_iter(inner.keys().copied());
(*prefix, names as &[&str])
}));
crate::error::PossibleNames { locals, qualified }
}
pub fn possible_ctor_names(&self, bump: &'a Bump) -> crate::error::PossibleNames<'a> {
let locals = bump.alloc_slice_fill_iter(self.ctors.keys().copied());
let qualified = bump.alloc_slice_fill_iter(self.q_ctors.iter().map(|(prefix, inner)| {
let names = bump.alloc_slice_fill_iter(inner.keys().copied());
(*prefix, names as &[&str])
}));
crate::error::PossibleNames { locals, qualified }
}
}
pub(super) fn twin_unions(
left: &str,
left_arity: usize,
left_ctors: &[&nash_ast::Ctor<'_>],
right: &str,
right_arity: usize,
right_ctors: &[&nash_ast::Ctor<'_>],
) -> bool {
let (Some(a), Some(b)) = (left.as_bytes().first(), right.as_bytes().first()) else {
return false;
};
a != b
&& a.eq_ignore_ascii_case(b)
&& left.get(1..) == right.get(1..)
&& left_arity == right_arity
&& left_ctors.len() == right_ctors.len()
&& left_ctors
.iter()
.zip(right_ctors)
.all(|(a, b)| a.name == b.name && a.arity == b.arity && a.labels == b.labels)
}
pub fn merge_exposed<'a, T: Clone>(
table: &mut Exposed<'a, T>,
name: &'a str,
home: ModuleName<'a>,
value: T,
) {
use std::collections::btree_map::Entry;
match table.entry(name) {
Entry::Vacant(e) => {
e.insert(Info::Specific(home, value));
}
Entry::Occupied(mut e) => match e.get() {
Info::Specific(existing, _) if *existing != home => {
let first = *existing;
e.insert(Info::Ambiguous(first, vec![home]));
}
Info::Ambiguous(..) => {
if let Info::Ambiguous(_, others) = e.get_mut() {
others.push(home);
}
}
_ => {}
},
}
}
pub fn merge_qualified<'a, T: Clone>(
table: &mut Qualified<'a, T>,
prefix: &'a str,
name: &'a str,
home: ModuleName<'a>,
value: T,
) {
let inner = table.entry(prefix).or_default();
merge_exposed(inner, name, home, value);
}
#[cfg(test)]
mod tests {
use super::*;
use nash_ast::{Head, ImplKey, PackageName, QualifiedName};
#[test]
fn trait_candidates_match_full_map_filter_in_order() {
let bump = Bump::new();
let mut tables = Tables::default();
let mut traits = Vec::new();
for package in [
None,
Some(PackageName {
author: "a",
project: "b",
}),
] {
for module in ["A", "AA", "B"] {
for name in ["A", "AA", "B"] {
let trait_ = QualifiedName {
home: ModuleName {
package,
name: module,
},
name,
};
traits.push(trait_);
for heads in [
vec![],
vec![Head::Var {
index: 0,
repr: nash_ast::primitives::ReprSet::ALL,
}],
vec![Head::Var {
index: 1,
repr: nash_ast::primitives::ReprSet::ALL,
}],
vec![
Head::Var {
index: 0,
repr: nash_ast::primitives::ReprSet::ALL,
},
Head::Var {
index: 1,
repr: nash_ast::primitives::ReprSet::ALL,
},
],
] {
let key = ImplKey {
trait_,
heads: bump.alloc_slice_copy(&heads),
};
let info = bump.alloc(ImplInfo {
variables: &[],
home: trait_.home,
region: Region::zero(),
trait_,
context: &[],
heads: &[],
methods: &[],
});
tables.impls.insert(key, info);
}
}
}
}
for module in ["", "AB", "Z"] {
traits.push(QualifiedName {
home: ModuleName {
package: None,
name: module,
},
name: "Missing",
});
}
for trait_ in traits {
let expected: Vec<_> = tables
.impls
.iter()
.filter(|(key, _)| key.trait_ == trait_)
.collect();
let actual: Vec<_> = tables.impls_for(trait_).collect();
assert_eq!(
actual.iter().map(|(key, _)| *key).collect::<Vec<_>>(),
expected.iter().map(|(key, _)| *key).collect::<Vec<_>>()
);
for ((_, actual), (_, expected)) in actual.into_iter().zip(expected) {
assert!(std::ptr::eq(*actual, *expected));
}
}
}
}