use alloc::{collections::BTreeSet, vec::Vec};
use crate::{
error::{CheckError, Limit, Meter},
types::{Field, Tag, TypeId, Types},
};
pub(crate) const GENERAL: u8 = 0;
pub(crate) const INT: u8 = 1;
pub(crate) const FLOAT: u8 = 2;
#[derive(Clone, Copy, Debug)]
enum Undo {
Parent(u32, u32),
Rank(u32, u8),
Repr(u32, u32),
Class(u32, u8),
}
pub(crate) struct UnifyCfg<'a> {
pub(crate) int_to_float: bool,
pub(crate) structural: bool,
pub(crate) record_fields: &'a [Option<(u32, u32)>],
pub(crate) field_pool: &'a [Field],
}
impl UnifyCfg<'_> {
fn fields_of_item(&self, item: u32) -> Option<&[Field]> {
let (start, len) = (*self.record_fields.get(item as usize)?)?;
self.field_pool
.get(start as usize..(start as usize).saturating_add(len as usize))
}
}
#[derive(Debug, Default)]
pub(crate) struct Infer {
parent: Vec<u32>,
rank: Vec<u8>,
repr: Vec<u32>,
class: Vec<u8>,
journal: Vec<Undo>,
open: u32,
stamp: Vec<u32>,
epoch: u32,
work: Vec<(TypeId, TypeId)>,
stack: Vec<TypeId>,
assumed: BTreeSet<(u32, u32)>,
walk: Vec<(TypeId, bool)>,
kids: Vec<TypeId>,
pub(crate) vars: Vec<TypeId>,
}
impl Infer {
fn sync(&mut self, types: &Types) {
let n = types.len();
let mut i = self.parent.len();
while i < n {
let raw = u32::try_from(i).unwrap_or(u32::MAX);
self.parent.push(raw);
self.rank.push(0);
self.repr.push(raw);
self.class
.push(types.node(TypeId::from_raw(raw)).small.min(FLOAT));
i += 1;
}
}
pub(crate) fn fresh(&mut self, types: &mut Types, class: u8) -> TypeId {
let v = types.fresh_var(class);
self.sync(types);
self.vars.push(v);
v
}
pub(crate) fn find(&self, t: TypeId) -> u32 {
let mut x = t.raw();
loop {
match self.parent.get(x as usize) {
Some(&p) if p != x => x = p,
_ => return x,
}
}
}
pub(crate) fn resolve(&self, t: TypeId) -> TypeId {
let root = self.find(t);
TypeId::from_raw(self.repr.get(root as usize).copied().unwrap_or(root))
}
pub(crate) fn class_of(&self, t: TypeId) -> u8 {
let root = self.find(t);
self.class.get(root as usize).copied().unwrap_or(GENERAL)
}
fn write_parent(&mut self, i: u32, v: u32) {
if let Some(slot) = self.parent.get_mut(i as usize) {
self.journal.push(Undo::Parent(i, *slot));
*slot = v;
}
}
fn write_rank(&mut self, i: u32, v: u8) {
if let Some(slot) = self.rank.get_mut(i as usize) {
self.journal.push(Undo::Rank(i, *slot));
*slot = v;
}
}
fn write_repr(&mut self, i: u32, v: u32) {
if let Some(slot) = self.repr.get_mut(i as usize) {
self.journal.push(Undo::Repr(i, *slot));
*slot = v;
}
}
fn write_class(&mut self, i: u32, v: u8) {
if let Some(slot) = self.class.get_mut(i as usize) {
self.journal.push(Undo::Class(i, *slot));
*slot = v;
}
}
fn link(&mut self, a: u32, b: u32, repr: u32, class: u8) {
let ra = self.rank.get(a as usize).copied().unwrap_or(0);
let rb = self.rank.get(b as usize).copied().unwrap_or(0);
let (root, child) = if ra >= rb { (a, b) } else { (b, a) };
self.write_parent(child, root);
if ra == rb {
self.write_rank(root, ra.saturating_add(1));
}
self.write_repr(root, repr);
self.write_class(root, class);
}
pub(crate) fn snapshot(&mut self) -> usize {
self.open += 1;
self.journal.len()
}
pub(crate) fn rollback(&mut self, snap: usize) {
self.undo_to(snap);
self.close();
}
pub(crate) fn commit(&mut self) {
self.close();
}
fn close(&mut self) {
self.open = self.open.saturating_sub(1);
if self.open == 0 {
self.journal.clear();
}
}
fn undo_to(&mut self, snap: usize) {
while self.journal.len() > snap {
match self.journal.pop() {
Some(Undo::Parent(i, v)) => set(&mut self.parent, i, v),
Some(Undo::Rank(i, v)) => set(&mut self.rank, i, v),
Some(Undo::Repr(i, v)) => set(&mut self.repr, i, v),
Some(Undo::Class(i, v)) => set(&mut self.class, i, v),
None => break,
}
}
}
pub(crate) fn unify(
&mut self,
types: &Types,
cfg: &UnifyCfg<'_>,
meter: &mut Meter,
a: TypeId,
b: TypeId,
) -> Result<bool, CheckError> {
if a == b || self.find(a) == self.find(b) {
return Ok(true);
}
self.sync(types);
let snap = self.snapshot();
let result = self.unify_inner(types, cfg, meter, a, b);
match result {
Ok(true) => self.commit(),
_ => self.rollback(snap),
}
result
}
fn unify_inner(
&mut self,
types: &Types,
cfg: &UnifyCfg<'_>,
meter: &mut Meter,
a: TypeId,
b: TypeId,
) -> Result<bool, CheckError> {
self.work.clear();
self.assumed.clear();
self.work.push((a, b));
while let Some((a, b)) = self.work.pop() {
meter.tick(1)?;
let (ra, rb) = (self.find(a), self.find(b));
if ra == rb {
continue;
}
let ta = TypeId::from_raw(self.repr.get(ra as usize).copied().unwrap_or(ra));
let tb = TypeId::from_raw(self.repr.get(rb as usize).copied().unwrap_or(rb));
let (na, nb) = (types.node(ta), types.node(tb));
match (na.tag, nb.tag) {
(Tag::Var, Tag::Var) => {
let (ca, cb) = (self.class_of(ta), self.class_of(tb));
let merged = match (ca, cb) {
(x, y) if x == y => x,
(GENERAL, y) => y,
(x, GENERAL) => x,
_ if cfg.int_to_float => FLOAT,
_ => return Ok(false),
};
self.link(ra, rb, ta.raw(), merged);
}
(Tag::Var, _) => {
if !self.bind(types, cfg, meter, ra, ta, tb)? {
return Ok(false);
}
}
(_, Tag::Var) => {
if !self.bind(types, cfg, meter, rb, tb, ta)? {
return Ok(false);
}
}
(Tag::Error, _) | (_, Tag::Error) => {
let other = if na.tag == Tag::Error { tb } else { ta };
if types.node(other).has_var
&& self.assumed.insert((other.raw(), TypeId::ERROR.raw()))
{
let work = &mut self.work;
types.for_each_child(other, |k| work.push((k, TypeId::ERROR)));
}
}
(Tag::Adt, Tag::Adt) if na.x == nb.x => {
if !self.decompose(types, cfg, ta, tb)? {
return Ok(false);
}
self.link(ra, rb, prefer_ground(types, ta, tb).raw(), GENERAL);
}
(Tag::Adt, _) | (_, Tag::Adt) => {
let pair = (ta.raw().min(tb.raw()), ta.raw().max(tb.raw()));
if self.assumed.insert(pair) && !self.decompose(types, cfg, ta, tb)? {
return Ok(false);
}
}
_ => {
if !self.decompose(types, cfg, ta, tb)? {
return Ok(false);
}
self.link(ra, rb, prefer_ground(types, ta, tb).raw(), GENERAL);
}
}
}
Ok(true)
}
fn bind(
&mut self,
types: &Types,
cfg: &UnifyCfg<'_>,
meter: &mut Meter,
root: u32,
var: TypeId,
term: TypeId,
) -> Result<bool, CheckError> {
let n = types.node(term);
let ok = match self.class_of(var) {
_ if n.tag == Tag::Error => true,
INT => {
n.tag == Tag::Prim
&& (is_int_code(n.small) || (cfg.int_to_float && is_float_code(n.small)))
}
FLOAT => n.tag == Tag::Prim && is_float_code(n.small),
_ => !self.occurs(types, meter, root, term)?,
};
if ok {
let term_root = self.find(term);
self.link(root, term_root, term.raw(), GENERAL);
}
Ok(ok)
}
fn decompose(
&mut self,
types: &Types,
cfg: &UnifyCfg<'_>,
a: TypeId,
b: TypeId,
) -> Result<bool, CheckError> {
let (na, nb) = (types.node(a), types.node(b));
let same_adt = na.tag == Tag::Adt && nb.tag == Tag::Adt && na.x == nb.x;
if !same_adt
&& (na.tag == Tag::Adt
|| nb.tag == Tag::Adt
|| na.tag == Tag::Record
|| nb.tag == Tag::Record)
{
return Ok(self.decompose_records(types, cfg, a, b));
}
if na.tag != nb.tag || na.small != nb.small || na.len != nb.len {
return Ok(false);
}
match na.tag {
Tag::Adt
| Tag::Foreign
| Tag::Extern
| Tag::Trait
| Tag::Proj
| Tag::Opaque
| Tag::Union
| Tag::Inter
| Tag::Dyn => {
if na.x != nb.x || na.y != nb.y || na.z != nb.z {
return Ok(false);
}
let (ka, kb) = (types.kids_of(&na), types.kids_of(&nb));
self.work.extend(ka.iter().copied().zip(kb.iter().copied()));
Ok(true)
}
Tag::Tuple | Tag::Fn => {
let (ka, kb) = (types.kids_of(&na), types.kids_of(&nb));
self.work.extend(ka.iter().copied().zip(kb.iter().copied()));
if na.tag == Tag::Fn {
self.work
.push((TypeId::from_raw(na.z), TypeId::from_raw(nb.z)));
}
Ok(true)
}
Tag::Array | Tag::Map => {
self.work
.push((TypeId::from_raw(na.x), TypeId::from_raw(nb.x)));
self.work
.push((TypeId::from_raw(na.y), TypeId::from_raw(nb.y)));
Ok(true)
}
Tag::Slice
| Tag::Ref
| Tag::Ptr
| Tag::Nullable
| Tag::Async
| Tag::Task
| Tag::Gen
| Tag::AsyncGen => {
self.work
.push((TypeId::from_raw(na.x), TypeId::from_raw(nb.x)));
Ok(true)
}
_ => Ok(a == b),
}
}
fn decompose_records(
&mut self,
types: &Types,
cfg: &UnifyCfg<'_>,
a: TypeId,
b: TypeId,
) -> bool {
let fields = |t: TypeId| -> Option<&[Field]> {
let n = types.node(t);
match n.tag {
Tag::Record => Some(types.fields_of(&n)),
Tag::Adt if cfg.structural => cfg.fields_of_item(n.x),
_ => None,
}
};
let (Some(fa), Some(fb)) = (fields(a), fields(b)) else {
return false;
};
if fa.len() != fb.len() || fa.iter().zip(fb).any(|(x, y)| x.name != y.name) {
return false;
}
self.work
.extend(fa.iter().zip(fb).map(|(x, y)| (x.ty, y.ty)));
true
}
fn occurs(
&mut self,
types: &Types,
meter: &mut Meter,
var_root: u32,
term: TypeId,
) -> Result<bool, CheckError> {
self.epoch = self.epoch.wrapping_add(1);
if self.epoch == 0 {
self.stamp.iter_mut().for_each(|s| *s = 0);
self.epoch = 1;
}
if self.stamp.len() < types.len() {
self.stamp.resize(types.len(), 0);
}
self.stack.clear();
self.stack.push(term);
while let Some(t) = self.stack.pop() {
meter.tick(1)?;
let root = self.find(t);
if root == var_root {
return Ok(true);
}
let rep = TypeId::from_raw(self.repr.get(root as usize).copied().unwrap_or(root));
match self.stamp.get_mut(rep.index()) {
Some(s) if *s == self.epoch => continue,
Some(s) => *s = self.epoch,
None => {}
}
if !types.node(rep).has_var {
continue;
}
let stack = &mut self.stack;
types.for_each_child(rep, |k| stack.push(k));
}
Ok(false)
}
pub(crate) fn force(&mut self, types: &Types, var: TypeId, term: TypeId) {
self.sync(types);
let (rv, rt) = (self.find(var), self.find(term));
if rv != rt {
let _ = self.snapshot();
self.link(rv, rt, term.raw(), GENERAL);
self.commit();
}
}
pub(crate) fn zonk(
&mut self,
types: &mut Types,
memo: &mut Vec<u32>,
meter: &mut Meter,
t: TypeId,
) -> Result<TypeId, CheckError> {
const UNKNOWN: u32 = u32::MAX;
const BUSY: u32 = u32::MAX - 1;
fn get(memo: &[u32], t: TypeId, len: usize) -> u32 {
if t.index() >= len {
TypeId::ERROR.raw()
} else {
memo.get(t.index()).copied().unwrap_or(UNKNOWN)
}
}
fn set(memo: &mut Vec<u32>, t: TypeId, v: u32, len: usize) {
if t.index() >= len {
return;
}
if t.index() >= memo.len() {
memo.resize(t.index() + 1, UNKNOWN);
}
if let Some(slot) = memo.get_mut(t.index()) {
*slot = v;
}
}
if t.index() < types.len() {
let rep = self.resolve(t);
if !types.node(rep).has_var {
return Ok(rep);
}
}
let mut stack = core::mem::take(&mut self.walk);
let mut kids = core::mem::take(&mut self.kids);
stack.clear();
stack.push((t, false));
while let Some((x, expanded)) = stack.pop() {
meter.tick(1)?;
let len = types.len();
if !expanded && get(memo, x, len) != UNKNOWN {
continue;
}
let rep = self.resolve(x);
let n = types.node(rep);
if !n.has_var {
set(memo, x, rep.raw(), len);
continue;
}
if n.tag == Tag::Var {
set(memo, x, TypeId::ERROR.raw(), len);
continue;
}
if !expanded {
set(memo, x, BUSY, len);
stack.push((x, true));
types.for_each_child(rep, |k| {
if get(memo, k, len) == UNKNOWN {
stack.push((k, false));
}
});
continue;
}
kids.clear();
types.for_each_child(rep, |k| {
let v = get(memo, k, len);
kids.push(if v >= BUSY {
TypeId::ERROR
} else {
TypeId::from_raw(v)
});
});
let rebuilt = types.rebuild(rep, &kids);
let len = types.len();
set(memo, x, rebuilt.raw(), len);
set(memo, rep, rebuilt.raw(), len);
}
self.walk = stack;
self.kids = kids;
let v = get(memo, t, types.len());
Ok(if v >= BUSY {
TypeId::ERROR
} else {
TypeId::from_raw(v)
})
}
pub(crate) fn first_free(
&mut self,
types: &Types,
memo: &mut Vec<u32>,
meter: &mut Meter,
t: TypeId,
) -> Result<Option<u32>, CheckError> {
const UNKNOWN: u32 = u32::MAX;
const NONE: u32 = u32::MAX - 1;
if memo.len() < types.len() {
memo.resize(types.len(), UNKNOWN);
}
let get = |memo: &Vec<u32>, t: TypeId| memo.get(t.index()).copied().unwrap_or(NONE);
if !types.node(self.resolve(t)).has_var {
return Ok(None);
}
let mut stack = core::mem::take(&mut self.walk);
stack.clear();
stack.push((t, false));
while let Some((x, expanded)) = stack.pop() {
meter.tick(1)?;
if !expanded && get(memo, x) != UNKNOWN {
continue;
}
let rep = self.resolve(x);
let n = types.node(rep);
let value = if !n.has_var {
NONE
} else if n.tag == Tag::Var {
if self.class_of(rep) == GENERAL {
self.find(rep)
} else {
NONE
}
} else if !expanded {
if let Some(slot) = memo.get_mut(x.index()) {
*slot = NONE; }
stack.push((x, true));
types.for_each_child(rep, |k| {
if get(memo, k) == UNKNOWN {
stack.push((k, false));
}
});
continue;
} else {
let mut found = NONE;
types.for_each_child(rep, |k| {
let v = get(memo, k);
if found == NONE && v < NONE {
found = v;
}
});
found
};
if let Some(slot) = memo.get_mut(x.index()) {
*slot = value;
}
}
self.walk = stack;
let v = get(memo, t);
Ok((v < NONE).then_some(v))
}
pub(crate) fn check_size(types: &Types, meter: &Meter) -> Result<(), CheckError> {
if types.footprint() > meter.budget.type_nodes {
Err(CheckError::BudgetExceeded {
limit: Limit::TypeNodes,
})
} else {
Ok(())
}
}
}
fn prefer_ground(types: &Types, a: TypeId, b: TypeId) -> TypeId {
if types.node(a).has_var && !types.node(b).has_var {
b
} else {
a
}
}
fn set<T: Copy>(table: &mut [T], i: u32, v: T) {
if let Some(slot) = table.get_mut(i as usize) {
*slot = v;
}
}
pub(crate) const fn is_int_code(code: u8) -> bool {
matches!(code, 1..=10)
}
pub(crate) const fn is_float_code(code: u8) -> bool {
matches!(code, 11 | 12)
}
#[cfg(test)]
mod tests {
use hir_lang::{Effects, Prim};
use super::*;
use crate::error::Budget;
fn cfg() -> UnifyCfg<'static> {
UnifyCfg {
int_to_float: false,
structural: false,
record_fields: &[],
field_pool: &[],
}
}
#[test]
fn test_var_binds_and_resolves() {
let mut types = Types::new();
let mut inf = Infer::default();
let mut meter = Meter::new(Budget::default());
let v = inf.fresh(&mut types, GENERAL);
let i32_ = TypeId::prim(Prim::I32);
assert_eq!(inf.unify(&types, &cfg(), &mut meter, v, i32_), Ok(true));
assert_eq!(inf.resolve(v), i32_);
}
#[test]
fn test_mismatch_rolls_back_partial_merges() {
let mut types = Types::new();
let mut inf = Infer::default();
let mut meter = Meter::new(Budget::default());
let v = inf.fresh(&mut types, GENERAL);
let a = types.tuple(&[v, TypeId::prim(Prim::Bool)]);
let b = types.tuple(&[TypeId::prim(Prim::I32), TypeId::prim(Prim::I32)]);
assert_eq!(inf.unify(&types, &cfg(), &mut meter, a, b), Ok(false));
assert_eq!(inf.resolve(v), v, "binding rolled back");
assert_ne!(inf.find(a), inf.find(b), "class merge rolled back");
}
#[test]
fn test_occurs_check_rejects_cycles() {
let mut types = Types::new();
let mut inf = Infer::default();
let mut meter = Meter::new(Budget::default());
let v = inf.fresh(&mut types, GENERAL);
let s = types.slice(v);
assert_eq!(inf.unify(&types, &cfg(), &mut meter, v, s), Ok(false));
}
#[test]
fn test_int_literal_class() {
let mut types = Types::new();
let mut inf = Infer::default();
let mut meter = Meter::new(Budget::default());
let v = inf.fresh(&mut types, INT);
let f = TypeId::prim(Prim::F64);
assert_eq!(inf.unify(&types, &cfg(), &mut meter, v, f), Ok(false));
let widen = UnifyCfg {
int_to_float: true,
..cfg()
};
assert_eq!(inf.unify(&types, &widen, &mut meter, v, f), Ok(true));
}
#[test]
fn test_error_unifies_without_poisoning() {
let mut types = Types::new();
let mut inf = Infer::default();
let mut meter = Meter::new(Budget::default());
let t = types.tuple(&[TypeId::prim(Prim::I32)]);
assert_eq!(
inf.unify(&types, &cfg(), &mut meter, t, TypeId::ERROR),
Ok(true)
);
assert_eq!(
inf.resolve(t),
t,
"a shared term is never merged with {{error}}"
);
}
#[test]
fn test_doubling_chain_is_linear() {
let mut types = Types::new();
let mut inf = Infer::default();
let depth = 20_000;
let (mut a, mut b) = (
inf.fresh(&mut types, GENERAL),
inf.fresh(&mut types, GENERAL),
);
let (a0, b0) = (a, b);
for _ in 0..depth {
a = types.tuple(&[a, a]);
b = types.tuple(&[b, b]);
}
let mut meter = Meter::new(Budget::default());
assert_eq!(inf.unify(&types, &cfg(), &mut meter, a, b), Ok(true));
assert!(meter.used <= 3 * depth + 4, "steps {}", meter.used);
assert_eq!(inf.find(a0), inf.find(b0));
assert_eq!(
inf.unify(&types, &cfg(), &mut meter, a0, TypeId::prim(Prim::U8)),
Ok(true)
);
let before = meter.used;
let mut memo = Vec::new();
let z = inf
.zonk(&mut types, &mut memo, &mut meter, b)
.unwrap_or(TypeId::ERROR);
assert!(meter.used - before <= 4 * depth + 8);
assert!(!types.node(z).has_var);
}
#[test]
fn test_fn_types_unify_componentwise() {
let mut types = Types::new();
let mut inf = Infer::default();
let mut meter = Meter::new(Budget::default());
let v = inf.fresh(&mut types, GENERAL);
let f1 = types.func(&[v], TypeId::UNIT, Effects::NONE);
let f2 = types.func(&[TypeId::prim(Prim::Char)], TypeId::UNIT, Effects::NONE);
assert_eq!(inf.unify(&types, &cfg(), &mut meter, f1, f2), Ok(true));
assert_eq!(inf.resolve(v), TypeId::prim(Prim::Char));
let f3 = types.func(&[TypeId::prim(Prim::Char)], TypeId::UNIT, Effects::ASYNC);
assert_eq!(inf.unify(&types, &cfg(), &mut meter, f2, f3), Ok(false));
}
#[test]
fn test_budget_stops_unification() {
let mut types = Types::new();
let mut inf = Infer::default();
let v = inf.fresh(&mut types, GENERAL);
let (mut a, mut b) = (TypeId::UNIT, v);
for _ in 0..100 {
a = types.slice(a);
b = types.slice(b);
}
let mut meter = Meter::new(Budget {
steps: 3,
..Budget::default()
});
let r = inf.unify(&types, &cfg(), &mut meter, a, b);
assert_eq!(
r,
Err(CheckError::BudgetExceeded {
limit: Limit::Steps
})
);
assert_eq!(inf.resolve(v), v, "nothing kept after a budget stop");
}
}