use std::collections::BTreeMap;
use super::*;
#[derive(Debug, Default, Clone, PartialEq, Eq)]
pub struct DemandSubstitution {
pub values: BTreeMap<u32, DemandSignature>,
pub cores: BTreeMap<u32, DemandCoreType>,
pub effects: BTreeMap<u32, DemandEffect>,
}
impl DemandSubstitution {
pub fn apply_signature(&self, signature: &DemandSignature) -> DemandSignature {
match signature {
DemandSignature::Ignored => DemandSignature::Ignored,
DemandSignature::Hole(id) => self
.values
.get(id)
.map(|signature| self.apply_signature(signature))
.unwrap_or(DemandSignature::Hole(*id)),
DemandSignature::Core(ty) => DemandSignature::Core(self.apply_core_type(ty)),
DemandSignature::Fun { param, ret } => DemandSignature::Fun {
param: Box::new(self.apply_signature(param)),
ret: Box::new(self.apply_signature(ret)),
},
DemandSignature::Thunk { effect, value } => DemandSignature::Thunk {
effect: self.apply_effect(effect),
value: Box::new(self.apply_signature(value)),
},
}
}
pub fn apply_core_type(&self, ty: &DemandCoreType) -> DemandCoreType {
match ty {
DemandCoreType::Any => DemandCoreType::Any,
DemandCoreType::Hole(id) => self
.cores
.get(id)
.map(|ty| self.apply_core_type(ty))
.unwrap_or(DemandCoreType::Hole(*id)),
DemandCoreType::Named { path, args } => DemandCoreType::Named {
path: path.clone(),
args: args.iter().map(|arg| self.apply_type_arg(arg)).collect(),
},
DemandCoreType::Fun {
param,
param_effect,
ret_effect,
ret,
} => DemandCoreType::Fun {
param: Box::new(self.apply_core_type(param)),
param_effect: Box::new(self.apply_effect(param_effect)),
ret_effect: Box::new(self.apply_effect(ret_effect)),
ret: Box::new(self.apply_core_type(ret)),
},
DemandCoreType::Tuple(items) => DemandCoreType::Tuple(
items
.iter()
.map(|item| self.apply_core_type(item))
.collect(),
),
DemandCoreType::Record(fields) => DemandCoreType::Record(
fields
.iter()
.map(|field| DemandRecordField {
name: field.name.clone(),
value: self.apply_core_type(&field.value),
optional: field.optional,
})
.collect(),
),
DemandCoreType::Variant(cases) => DemandCoreType::Variant(
cases
.iter()
.map(|case| DemandVariantCase {
name: case.name.clone(),
payloads: case
.payloads
.iter()
.map(|payload| self.apply_core_type(payload))
.collect(),
})
.collect(),
),
DemandCoreType::RowAsValue(items) => DemandCoreType::RowAsValue(
items.iter().map(|item| self.apply_effect(item)).collect(),
),
DemandCoreType::Union(items) => DemandCoreType::Union(
items
.iter()
.map(|item| self.apply_core_type(item))
.collect(),
),
DemandCoreType::Inter(items) => DemandCoreType::Inter(
items
.iter()
.map(|item| self.apply_core_type(item))
.collect(),
),
DemandCoreType::Recursive { var, body } => DemandCoreType::Recursive {
var: var.clone(),
body: Box::new(self.apply_core_type(body)),
},
DemandCoreType::Never => DemandCoreType::Never,
}
}
pub fn apply_effect(&self, effect: &DemandEffect) -> DemandEffect {
match effect {
DemandEffect::Hole(id) => self
.effects
.get(id)
.map(|effect| self.apply_effect(effect))
.unwrap_or(DemandEffect::Hole(*id)),
DemandEffect::Atom(ty) => DemandEffect::Atom(self.apply_core_type(ty)),
DemandEffect::Row(items) => {
DemandEffect::Row(items.iter().map(|item| self.apply_effect(item)).collect())
}
DemandEffect::Empty => DemandEffect::Empty,
}
}
fn apply_type_arg(&self, arg: &DemandTypeArg) -> DemandTypeArg {
match arg {
DemandTypeArg::Type(ty) => DemandTypeArg::Type(self.apply_core_type(ty)),
DemandTypeArg::Bounds { lower, upper } => DemandTypeArg::Bounds {
lower: lower.as_ref().map(|ty| self.apply_core_type(ty)),
upper: upper.as_ref().map(|ty| self.apply_core_type(ty)),
},
}
}
}
#[derive(Debug, Default, Clone)]
pub struct DemandUnifier {
substitutions: DemandSubstitution,
}
impl DemandUnifier {
pub fn new() -> Self {
Self::default()
}
pub fn unify_signature(
mut self,
expected: &DemandSignature,
actual: &DemandSignature,
) -> Result<DemandSubstitution, DemandUnifyError> {
self.unify(expected, actual)?;
Ok(self.substitutions)
}
pub fn unify(
&mut self,
expected: &DemandSignature,
actual: &DemandSignature,
) -> Result<(), DemandUnifyError> {
self.signature(expected, actual)
}
pub fn finish(self) -> DemandSubstitution {
self.substitutions
}
fn signature(
&mut self,
expected: &DemandSignature,
actual: &DemandSignature,
) -> Result<(), DemandUnifyError> {
match (expected, actual) {
(DemandSignature::Ignored, _) | (_, DemandSignature::Ignored) => Ok(()),
(DemandSignature::Hole(id), actual) => self.bind_value(*id, actual.clone()),
(expected, DemandSignature::Hole(id)) => self.bind_value(*id, expected.clone()),
(DemandSignature::Core(expected), DemandSignature::Core(actual)) => {
self.core(expected, actual)
}
(DemandSignature::Core(expected), actual)
if let Some(expected) = core_fun_signature(expected) =>
{
self.signature(&expected, actual)
}
(expected, DemandSignature::Core(actual))
if let Some(actual) = core_fun_signature(actual) =>
{
self.signature(expected, &actual)
}
(
DemandSignature::Fun {
param: expected_param,
ret: expected_ret,
},
DemandSignature::Fun {
param: actual_param,
ret: actual_ret,
},
) => {
self.signature(expected_param, actual_param)?;
self.return_signature(expected_ret, actual_ret)
}
(
DemandSignature::Thunk {
effect: expected_effect,
value: expected_value,
},
DemandSignature::Thunk {
effect: actual_effect,
value: actual_value,
},
) => {
self.effect(expected_effect, actual_effect)?;
self.signature(expected_value, actual_value)
}
(
DemandSignature::Thunk {
effect,
value: expected_value,
},
actual,
) if demand_effect_is_empty(effect) => self.signature(expected_value, actual),
(
expected,
DemandSignature::Thunk {
effect,
value: actual_value,
},
) if demand_effect_is_empty(effect) => self.signature(expected, actual_value),
_ => Err(DemandUnifyError::SignatureMismatch {
expected: expected.clone(),
actual: actual.clone(),
}),
}
}
fn return_signature(
&mut self,
expected: &DemandSignature,
actual: &DemandSignature,
) -> Result<(), DemandUnifyError> {
if let DemandSignature::Thunk { value, .. } = expected
&& !matches!(actual, DemandSignature::Thunk { .. })
{
return self.signature(value, actual);
}
self.signature(expected, actual)
}
fn core(
&mut self,
expected: &DemandCoreType,
actual: &DemandCoreType,
) -> Result<(), DemandUnifyError> {
match (expected, actual) {
(DemandCoreType::Any, _) | (_, DemandCoreType::Any) => Ok(()),
(DemandCoreType::Hole(id), actual) => self.bind_core(*id, actual.clone()),
(expected, DemandCoreType::Hole(id)) => self.bind_core(*id, expected.clone()),
(_, DemandCoreType::Never) => Ok(()),
(
DemandCoreType::Named {
path: expected_path,
args: expected_args,
},
DemandCoreType::Named {
path: actual_path,
args: actual_args,
},
) if expected_path == actual_path && expected_args.len() == actual_args.len() => {
for (expected, actual) in expected_args.iter().zip(actual_args) {
self.type_arg(expected, actual)?;
}
Ok(())
}
(
DemandCoreType::Fun {
param: expected_param,
param_effect: expected_param_effect,
ret_effect: expected_ret_effect,
ret: expected_ret,
},
DemandCoreType::Fun {
param: actual_param,
param_effect: actual_param_effect,
ret_effect: actual_ret_effect,
ret: actual_ret,
},
) => {
self.core(expected_param, actual_param)?;
self.effect(expected_param_effect, actual_param_effect)?;
self.effect(expected_ret_effect, actual_ret_effect)?;
self.core(expected_ret, actual_ret)
}
(DemandCoreType::Tuple(expected), DemandCoreType::Tuple(actual))
| (DemandCoreType::Union(expected), DemandCoreType::Union(actual))
| (DemandCoreType::Inter(expected), DemandCoreType::Inter(actual))
if expected.len() == actual.len() =>
{
for (expected, actual) in expected.iter().zip(actual) {
self.core(expected, actual)?;
}
Ok(())
}
(DemandCoreType::Record(expected), DemandCoreType::Record(actual)) => {
self.record(expected, actual)
}
(DemandCoreType::Variant(expected), DemandCoreType::Variant(actual)) => {
self.variant(expected, actual)
}
(DemandCoreType::RowAsValue(expected), DemandCoreType::RowAsValue(actual))
if expected.len() == actual.len() =>
{
for (expected, actual) in expected.iter().zip(actual) {
self.effect(expected, actual)?;
}
Ok(())
}
_ => Err(DemandUnifyError::CoreMismatch {
expected: expected.clone(),
actual: actual.clone(),
}),
}
}
fn record(
&mut self,
expected: &[DemandRecordField],
actual: &[DemandRecordField],
) -> Result<(), DemandUnifyError> {
if expected.len() != actual.len() {
return Err(DemandUnifyError::CoreMismatch {
expected: DemandCoreType::Record(expected.to_vec()),
actual: DemandCoreType::Record(actual.to_vec()),
});
}
for expected_field in expected {
let Some(actual_field) = actual.iter().find(|field| {
field.name == expected_field.name && field.optional == expected_field.optional
}) else {
return Err(DemandUnifyError::CoreMismatch {
expected: DemandCoreType::Record(expected.to_vec()),
actual: DemandCoreType::Record(actual.to_vec()),
});
};
self.core(&expected_field.value, &actual_field.value)?;
}
Ok(())
}
fn variant(
&mut self,
expected: &[DemandVariantCase],
actual: &[DemandVariantCase],
) -> Result<(), DemandUnifyError> {
if expected.len() != actual.len() {
return Err(DemandUnifyError::CoreMismatch {
expected: DemandCoreType::Variant(expected.to_vec()),
actual: DemandCoreType::Variant(actual.to_vec()),
});
}
for expected_case in expected {
let Some(actual_case) = actual.iter().find(|case| {
case.name == expected_case.name
&& case.payloads.len() == expected_case.payloads.len()
}) else {
return Err(DemandUnifyError::CoreMismatch {
expected: DemandCoreType::Variant(expected.to_vec()),
actual: DemandCoreType::Variant(actual.to_vec()),
});
};
for (expected, actual) in expected_case.payloads.iter().zip(&actual_case.payloads) {
self.core(expected, actual)?;
}
}
Ok(())
}
fn effect(
&mut self,
expected: &DemandEffect,
actual: &DemandEffect,
) -> Result<(), DemandUnifyError> {
match (expected, actual) {
(DemandEffect::Hole(id), actual) => self.bind_effect(*id, actual.clone()),
(expected, DemandEffect::Hole(id)) => self.bind_effect(*id, expected.clone()),
(DemandEffect::Empty, DemandEffect::Empty) => Ok(()),
(DemandEffect::Atom(expected), DemandEffect::Atom(actual)) => {
self.effect_atom(expected, actual)
}
(DemandEffect::Row(expected), DemandEffect::Row(actual)) => {
self.effect_row(expected, actual)
}
(DemandEffect::Row(expected), actual) => {
self.effect_row(expected, std::slice::from_ref(actual))
}
(expected, DemandEffect::Row(actual)) => {
self.effect_row(std::slice::from_ref(expected), actual)
}
_ => Err(DemandUnifyError::EffectMismatch {
expected: expected.clone(),
actual: actual.clone(),
}),
}
}
fn effect_row(
&mut self,
expected: &[DemandEffect],
actual: &[DemandEffect],
) -> Result<(), DemandUnifyError> {
let expected = flatten_effect_row(expected);
let actual = flatten_effect_row(actual);
let mut expected_holes = Vec::new();
let mut expected_fixed = Vec::new();
let mut actual_holes = Vec::new();
let mut actual_fixed = Vec::new();
split_effect_row(expected.clone(), &mut expected_holes, &mut expected_fixed);
split_effect_row(actual.clone(), &mut actual_holes, &mut actual_fixed);
remove_shared_effect_holes(&mut expected_holes, &mut actual_holes);
let mut unmatched_expected = Vec::new();
for expected in expected_fixed {
if let Some(index) = self.find_unifiable_effect(&expected, &actual_fixed) {
actual_fixed.remove(index);
self.remove_redundant_unifiable_effects(&expected, &mut actual_fixed);
} else {
unmatched_expected.push(expected);
}
}
if !unmatched_expected.is_empty() {
if let Some(hole) = actual_holes.pop() {
self.bind_effect(hole, effect_from_row_items(unmatched_expected))?;
}
}
if !actual_fixed.is_empty() {
let Some(hole) = expected_holes.pop() else {
return Err(DemandUnifyError::EffectMismatch {
expected: DemandEffect::Row(expected),
actual: DemandEffect::Row(actual),
});
};
self.bind_effect(hole, effect_from_row_items(actual_fixed))?;
}
for hole in expected_holes {
crate::monomorphize::effect_hole_metrics::record_unifier_expected_collapse();
if crate::monomorphize::effect_hole_metrics::strict_collapse_enabled() {
return Err(DemandUnifyError::EffectMismatch {
expected: DemandEffect::Hole(hole),
actual: DemandEffect::Empty,
});
}
self.bind_effect(hole, DemandEffect::Empty)?;
}
for hole in actual_holes {
crate::monomorphize::effect_hole_metrics::record_unifier_actual_collapse();
if crate::monomorphize::effect_hole_metrics::strict_collapse_enabled() {
return Err(DemandUnifyError::EffectMismatch {
expected: DemandEffect::Empty,
actual: DemandEffect::Hole(hole),
});
}
self.bind_effect(hole, DemandEffect::Empty)?;
}
Ok(())
}
fn effect_atom(
&mut self,
expected: &DemandCoreType,
actual: &DemandCoreType,
) -> Result<(), DemandUnifyError> {
if let Some(with_args) = single_effect_payload_side(expected, actual) {
for arg in with_args {
self.close_effect_payload_holes(arg)?;
}
return Ok(());
}
self.core(expected, actual)
}
fn close_effect_payload_holes(&mut self, arg: &DemandTypeArg) -> Result<(), DemandUnifyError> {
match arg {
DemandTypeArg::Type(DemandCoreType::Hole(id)) => {
self.bind_core(*id, DemandCoreType::Never)
}
DemandTypeArg::Bounds { lower, upper } => {
if let Some(DemandCoreType::Hole(id)) = lower {
self.bind_core(*id, DemandCoreType::Never)?;
}
if let Some(DemandCoreType::Hole(id)) = upper {
self.bind_core(*id, DemandCoreType::Never)?;
}
Ok(())
}
_ => Ok(()),
}
}
fn find_unifiable_effect(
&mut self,
expected: &DemandEffect,
actual: &[DemandEffect],
) -> Option<usize> {
for (index, candidate) in actual.iter().enumerate() {
let snapshot = self.substitutions.clone();
if self.effect(expected, candidate).is_ok() {
return Some(index);
}
self.substitutions = snapshot;
}
None
}
fn remove_redundant_unifiable_effects(
&mut self,
expected: &DemandEffect,
actual: &mut Vec<DemandEffect>,
) {
let mut index = 0;
while index < actual.len() {
let snapshot = self.substitutions.clone();
if self.effect(expected, &actual[index]).is_ok() {
actual.remove(index);
} else {
self.substitutions = snapshot;
index += 1;
}
}
}
fn type_arg(
&mut self,
expected: &DemandTypeArg,
actual: &DemandTypeArg,
) -> Result<(), DemandUnifyError> {
match (expected, actual) {
(DemandTypeArg::Type(expected), DemandTypeArg::Type(actual)) => {
self.core(expected, actual)
}
(
DemandTypeArg::Bounds {
lower: expected_lower,
upper: expected_upper,
},
DemandTypeArg::Bounds {
lower: actual_lower,
upper: actual_upper,
},
) => {
self.optional_core(expected_lower.as_ref(), actual_lower.as_ref())?;
self.optional_core(expected_upper.as_ref(), actual_upper.as_ref())
}
(DemandTypeArg::Bounds { lower, upper }, DemandTypeArg::Type(actual)) => {
self.type_arg_bounds_with_type(lower.as_ref(), upper.as_ref(), actual)
}
(DemandTypeArg::Type(expected), DemandTypeArg::Bounds { lower, upper }) => {
self.type_arg_bounds_with_type(lower.as_ref(), upper.as_ref(), expected)
}
}
}
fn type_arg_bounds_with_type(
&mut self,
lower: Option<&DemandCoreType>,
upper: Option<&DemandCoreType>,
ty: &DemandCoreType,
) -> Result<(), DemandUnifyError> {
if let Some(lower) = lower {
self.core(lower, ty)?;
}
if let Some(upper) = upper {
self.core(upper, ty)?;
}
Ok(())
}
fn optional_core(
&mut self,
expected: Option<&DemandCoreType>,
actual: Option<&DemandCoreType>,
) -> Result<(), DemandUnifyError> {
match (expected, actual) {
(Some(expected), Some(actual)) => self.core(expected, actual),
(None, None) => Ok(()),
_ => Err(DemandUnifyError::OptionalBoundMismatch),
}
}
fn bind_value(&mut self, id: u32, actual: DemandSignature) -> Result<(), DemandUnifyError> {
let actual = self.substitutions.apply_signature(&actual);
if actual == DemandSignature::Hole(id) {
return Ok(());
}
if signature_contains_value_hole(&actual, id) {
return Err(DemandUnifyError::Occurs {
namespace: DemandHoleNamespace::Value,
id,
});
}
if let Some(existing) = self.substitutions.values.get(&id).cloned() {
return self.signature(&existing, &actual);
}
self.substitutions.values.insert(id, actual);
Ok(())
}
fn bind_core(&mut self, id: u32, actual: DemandCoreType) -> Result<(), DemandUnifyError> {
let actual = self.substitutions.apply_core_type(&actual);
if actual == DemandCoreType::Hole(id) {
return Ok(());
}
if core_contains_core_hole(&actual, id) {
return Err(DemandUnifyError::Occurs {
namespace: DemandHoleNamespace::Core,
id,
});
}
if let Some(existing) = self.substitutions.cores.get(&id).cloned() {
return self.core(&existing, &actual);
}
self.substitutions.cores.insert(id, actual);
Ok(())
}
fn bind_effect(&mut self, id: u32, actual: DemandEffect) -> Result<(), DemandUnifyError> {
let actual = self.substitutions.apply_effect(&actual);
if actual == DemandEffect::Hole(id) {
return Ok(());
}
if effect_contains_effect_hole(&actual, id) {
return Err(DemandUnifyError::Occurs {
namespace: DemandHoleNamespace::Effect,
id,
});
}
if let Some(existing) = self.substitutions.effects.get(&id).cloned() {
return self.effect(&existing, &actual);
}
self.substitutions.effects.insert(id, actual);
Ok(())
}
}
fn core_fun_signature(ty: &DemandCoreType) -> Option<DemandSignature> {
let DemandCoreType::Fun {
param,
param_effect,
ret_effect,
ret,
} = ty
else {
return None;
};
Some(DemandSignature::Fun {
param: Box::new(effected_core_signature(
param.as_ref().clone(),
param_effect.as_ref().clone(),
)),
ret: Box::new(effected_core_signature(
ret.as_ref().clone(),
ret_effect.as_ref().clone(),
)),
})
}
fn flatten_effect_row(items: &[DemandEffect]) -> Vec<DemandEffect> {
let mut out = Vec::new();
for item in items {
push_flat_effect(item, &mut out);
}
out
}
fn push_flat_effect(effect: &DemandEffect, out: &mut Vec<DemandEffect>) {
match effect {
DemandEffect::Empty => {}
DemandEffect::Row(items) => {
for item in items {
push_flat_effect(item, out);
}
}
effect if demand_effect_is_impossible(effect) => {}
effect => out.push(effect.clone()),
}
}
fn split_effect_row(items: Vec<DemandEffect>, holes: &mut Vec<u32>, fixed: &mut Vec<DemandEffect>) {
for item in items {
match item {
DemandEffect::Hole(id) => holes.push(id),
item => fixed.push(item),
}
}
}
fn remove_shared_effect_holes(expected: &mut Vec<u32>, actual: &mut Vec<u32>) {
expected.retain(|expected_id| {
if let Some(index) = actual.iter().position(|actual_id| actual_id == expected_id) {
actual.remove(index);
false
} else {
true
}
});
}
fn single_effect_payload_side<'a>(
left: &'a DemandCoreType,
right: &'a DemandCoreType,
) -> Option<&'a [DemandTypeArg]> {
let (
DemandCoreType::Named {
path: left_path,
args: left_args,
},
DemandCoreType::Named {
path: right_path,
args: right_args,
},
) = (left, right)
else {
return None;
};
if left_path != right_path {
return None;
}
match (left_args.as_slice(), right_args.as_slice()) {
([], args) => Some(args),
(args, []) => Some(args),
_ => None,
}
}
fn effect_from_row_items(items: Vec<DemandEffect>) -> DemandEffect {
match items.as_slice() {
[] => DemandEffect::Empty,
[item] => item.clone(),
_ => DemandEffect::Row(items),
}
}
fn signature_contains_value_hole(signature: &DemandSignature, id: u32) -> bool {
match signature {
DemandSignature::Ignored => false,
DemandSignature::Hole(candidate) => *candidate == id,
DemandSignature::Core(_) => false,
DemandSignature::Fun { param, ret } => {
signature_contains_value_hole(param, id) || signature_contains_value_hole(ret, id)
}
DemandSignature::Thunk { value, .. } => signature_contains_value_hole(value, id),
}
}
fn core_contains_core_hole(ty: &DemandCoreType, id: u32) -> bool {
match ty {
DemandCoreType::Any => false,
DemandCoreType::Never => false,
DemandCoreType::Hole(candidate) => *candidate == id,
DemandCoreType::Named { args, .. } => {
args.iter().any(|arg| type_arg_contains_core_hole(arg, id))
}
DemandCoreType::Fun {
param,
ret,
param_effect,
ret_effect,
} => {
core_contains_core_hole(param, id)
|| core_contains_core_hole(ret, id)
|| effect_contains_core_hole(param_effect, id)
|| effect_contains_core_hole(ret_effect, id)
}
DemandCoreType::Tuple(items)
| DemandCoreType::Union(items)
| DemandCoreType::Inter(items) => {
items.iter().any(|item| core_contains_core_hole(item, id))
}
DemandCoreType::Record(fields) => fields
.iter()
.any(|field| core_contains_core_hole(&field.value, id)),
DemandCoreType::Variant(cases) => cases
.iter()
.flat_map(|case| case.payloads.iter())
.any(|payload| core_contains_core_hole(payload, id)),
DemandCoreType::RowAsValue(items) => items
.iter()
.any(|effect| effect_contains_core_hole(effect, id)),
DemandCoreType::Recursive { body, .. } => core_contains_core_hole(body, id),
}
}
fn type_arg_contains_core_hole(arg: &DemandTypeArg, id: u32) -> bool {
match arg {
DemandTypeArg::Type(ty) => core_contains_core_hole(ty, id),
DemandTypeArg::Bounds { lower, upper } => lower
.iter()
.chain(upper)
.any(|ty| core_contains_core_hole(ty, id)),
}
}
fn effect_contains_core_hole(effect: &DemandEffect, id: u32) -> bool {
match effect {
DemandEffect::Empty | DemandEffect::Hole(_) => false,
DemandEffect::Atom(ty) => core_contains_core_hole(ty, id),
DemandEffect::Row(items) => items
.iter()
.any(|effect| effect_contains_core_hole(effect, id)),
}
}
fn effect_contains_effect_hole(effect: &DemandEffect, id: u32) -> bool {
match effect {
DemandEffect::Empty | DemandEffect::Atom(_) => false,
DemandEffect::Hole(candidate) => *candidate == id,
DemandEffect::Row(items) => items
.iter()
.any(|effect| effect_contains_effect_hole(effect, id)),
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum DemandUnifyError {
SignatureMismatch {
expected: DemandSignature,
actual: DemandSignature,
},
CoreMismatch {
expected: DemandCoreType,
actual: DemandCoreType,
},
EffectMismatch {
expected: DemandEffect,
actual: DemandEffect,
},
TypeArgMismatch {
expected: DemandTypeArg,
actual: DemandTypeArg,
},
OptionalBoundMismatch,
Occurs {
namespace: DemandHoleNamespace,
id: u32,
},
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DemandHoleNamespace {
Value,
Core,
Effect,
}
fn demand_effect_is_empty(effect: &DemandEffect) -> bool {
match effect {
DemandEffect::Empty => true,
DemandEffect::Row(items) => items.iter().all(demand_effect_is_empty),
DemandEffect::Hole(_) | DemandEffect::Atom(_) => false,
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn unifier_solves_value_holes_from_function_demand() {
let expected = DemandSignature::Fun {
param: Box::new(DemandSignature::Hole(0)),
ret: Box::new(DemandSignature::Hole(1)),
};
let actual = DemandSignature::Fun {
param: Box::new(DemandSignature::Core(named("int"))),
ret: Box::new(DemandSignature::Core(named("int"))),
};
let substitutions = DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect("unified demand");
assert_eq!(
substitutions.values.get(&0),
Some(&DemandSignature::Core(named("int")))
);
assert_eq!(
substitutions.values.get(&1),
Some(&DemandSignature::Core(named("int")))
);
}
#[test]
fn unifier_treats_empty_thunk_as_value_boundary() {
let substitutions = DemandUnifier::new()
.unify_signature(
&DemandSignature::Thunk {
effect: DemandEffect::Empty,
value: Box::new(DemandSignature::Hole(0)),
},
&DemandSignature::Core(named("int")),
)
.expect("empty thunk unifies with its value");
assert_eq!(
substitutions.values.get(&0),
Some(&DemandSignature::Core(named("int")))
);
}
#[test]
fn unifier_accepts_pure_function_where_effectful_return_is_expected() {
let expected = DemandSignature::Fun {
param: Box::new(DemandSignature::Core(named("int"))),
ret: Box::new(DemandSignature::Thunk {
effect: DemandEffect::Atom(named("io")),
value: Box::new(DemandSignature::Core(named("bool"))),
}),
};
let actual = DemandSignature::Fun {
param: Box::new(DemandSignature::Core(named("int"))),
ret: Box::new(DemandSignature::Core(named("bool"))),
};
DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect("pure return satisfies effectful return demand");
}
#[test]
fn unifier_keeps_effect_holes_in_effect_substitution() {
let expected = DemandSignature::Thunk {
effect: DemandEffect::Hole(0),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let actual = DemandSignature::Thunk {
effect: DemandEffect::Atom(named("io")),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let substitutions = DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect("unified demand");
assert_eq!(
substitutions.effects.get(&0),
Some(&DemandEffect::Atom(named("io")))
);
assert!(substitutions.values.is_empty());
}
#[test]
fn unifier_matches_effect_rows_without_ordering() {
let expected = DemandSignature::Thunk {
effect: DemandEffect::Row(vec![
DemandEffect::Atom(named("io")),
DemandEffect::Atom(named("undet")),
]),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let actual = DemandSignature::Thunk {
effect: DemandEffect::Row(vec![
DemandEffect::Atom(named("undet")),
DemandEffect::Atom(named("io")),
]),
value: Box::new(DemandSignature::Core(named("unit"))),
};
DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect("unified row order");
}
#[test]
fn unifier_matches_single_effect_atom_with_singleton_row() {
let expected = DemandSignature::Thunk {
effect: DemandEffect::Atom(named("io")),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let actual = DemandSignature::Thunk {
effect: DemandEffect::Row(vec![DemandEffect::Atom(named("io"))]),
value: Box::new(DemandSignature::Core(named("unit"))),
};
DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect("unified singleton row");
}
#[test]
fn unifier_matches_payloadless_effect_with_hole_payload_effect() {
let expected = DemandSignature::Thunk {
effect: DemandEffect::Atom(named("local")),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let actual = DemandSignature::Thunk {
effect: DemandEffect::Atom(named_with_args(
"local",
vec![DemandTypeArg::Type(DemandCoreType::Hole(0))],
)),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let substitutions = DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect("unified local effect payload hole");
assert_eq!(substitutions.cores.get(&0), Some(&DemandCoreType::Never));
}
#[test]
fn unifier_matches_payloadless_effect_with_known_payload_effect() {
let expected = DemandSignature::Thunk {
effect: DemandEffect::Atom(named("sub")),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let actual = DemandSignature::Thunk {
effect: DemandEffect::Atom(named_with_args(
"sub",
vec![DemandTypeArg::Type(named("int"))],
)),
value: Box::new(DemandSignature::Core(named("unit"))),
};
DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect("unified effect payload erasure");
}
#[test]
fn unifier_solves_effect_hole_inside_row() {
let expected = DemandSignature::Thunk {
effect: DemandEffect::Row(vec![DemandEffect::Hole(0), DemandEffect::Atom(named("io"))]),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let actual = DemandSignature::Thunk {
effect: DemandEffect::Row(vec![
DemandEffect::Atom(named("undet")),
DemandEffect::Atom(named("io")),
]),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let substitutions = DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect("unified row hole");
assert_eq!(
substitutions.effects.get(&0),
Some(&DemandEffect::Atom(named("undet")))
);
}
#[test]
fn unifier_closes_extra_effect_row_hole_to_empty() {
let expected = DemandSignature::Thunk {
effect: DemandEffect::Row(vec![DemandEffect::Atom(named("io")), DemandEffect::Hole(0)]),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let actual = DemandSignature::Thunk {
effect: DemandEffect::Row(vec![DemandEffect::Atom(named("io"))]),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let substitutions = DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect("unified row hole as empty");
assert_eq!(substitutions.effects.get(&0), Some(&DemandEffect::Empty));
}
#[test]
fn unifier_actual_effect_row_hole_can_absorb_expected_effect() {
let expected = DemandSignature::Thunk {
effect: DemandEffect::Row(vec![
DemandEffect::Atom(named("io")),
DemandEffect::Atom(named("undet")),
]),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let actual = DemandSignature::Thunk {
effect: DemandEffect::Row(vec![DemandEffect::Atom(named("io")), DemandEffect::Hole(0)]),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let substitutions = DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect("unified actual row hole");
assert_eq!(
substitutions.effects.get(&0),
Some(&DemandEffect::Atom(named("undet")))
);
}
#[test]
fn unifier_accepts_actual_effect_subset_of_expected_row() {
let expected = DemandSignature::Thunk {
effect: DemandEffect::Row(vec![
DemandEffect::Atom(named("sub")),
DemandEffect::Atom(named("undet")),
]),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let actual = DemandSignature::Thunk {
effect: DemandEffect::Row(vec![DemandEffect::Atom(named("undet"))]),
value: Box::new(DemandSignature::Core(named("unit"))),
};
DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect("actual effect row is a subset of expected effects");
}
#[test]
fn unifier_accepts_duplicate_actual_effects_covered_by_one_expected_effect() {
let expected = DemandSignature::Thunk {
effect: DemandEffect::Atom(named_with_args(
"sub",
vec![DemandTypeArg::Type(named("int"))],
)),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let actual = DemandSignature::Thunk {
effect: DemandEffect::Row(vec![
DemandEffect::Atom(named_with_args(
"sub",
vec![DemandTypeArg::Type(named("int"))],
)),
DemandEffect::Atom(named_with_args(
"sub",
vec![DemandTypeArg::Type(DemandCoreType::Hole(0))],
)),
]),
value: Box::new(DemandSignature::Core(named("unit"))),
};
DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect("duplicate compatible effects are one row member");
}
#[test]
fn unifier_drops_never_payload_effects_from_rows() {
let expected = DemandSignature::Thunk {
effect: DemandEffect::Atom(named_with_args(
"sub",
vec![DemandTypeArg::Type(named("int"))],
)),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let actual = DemandSignature::Thunk {
effect: DemandEffect::Row(vec![
DemandEffect::Atom(named_with_args(
"sub",
vec![DemandTypeArg::Type(DemandCoreType::Never)],
)),
DemandEffect::Atom(named_with_args(
"sub",
vec![DemandTypeArg::Type(named("int"))],
)),
]),
value: Box::new(DemandSignature::Core(named("unit"))),
};
DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect("never payload effects are impossible");
}
#[test]
fn unifier_rejects_actual_effect_outside_expected_row() {
let expected = DemandSignature::Thunk {
effect: DemandEffect::Row(vec![DemandEffect::Atom(named("io"))]),
value: Box::new(DemandSignature::Core(named("unit"))),
};
let actual = DemandSignature::Thunk {
effect: DemandEffect::Row(vec![
DemandEffect::Atom(named("io")),
DemandEffect::Atom(named("undet")),
]),
value: Box::new(DemandSignature::Core(named("unit"))),
};
DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect_err("actual has an effect that expected does not allow");
}
#[test]
fn unifier_accepts_never_as_bottom_core_type() {
DemandUnifier::new()
.unify_signature(
&DemandSignature::Core(named("unit")),
&DemandSignature::Core(DemandCoreType::Never),
)
.expect("never is a bottom value");
}
#[test]
fn unifier_matches_record_fields_by_name() {
let expected = DemandSignature::Core(DemandCoreType::Record(vec![
field("x", named("int")),
field("y", named("bool")),
]));
let actual = DemandSignature::Core(DemandCoreType::Record(vec![
field("y", named("bool")),
field("x", named("int")),
]));
DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect("record fields unified by name");
}
#[test]
fn unifier_matches_variant_cases_by_name() {
let expected = DemandSignature::Core(DemandCoreType::Variant(vec![
case("nil", Vec::new()),
case("just", vec![named("int")]),
]));
let actual = DemandSignature::Core(DemandCoreType::Variant(vec![
case("just", vec![named("int")]),
case("nil", Vec::new()),
]));
DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect("variant cases unified by name");
}
#[test]
fn unifier_checks_type_arg_bounds_against_concrete_type() {
let expected = DemandSignature::Core(named_with_args(
"box",
vec![DemandTypeArg::Bounds {
lower: Some(named("int")),
upper: Some(DemandCoreType::Hole(0)),
}],
));
let actual = DemandSignature::Core(named_with_args(
"box",
vec![DemandTypeArg::Type(named("int"))],
));
let substitutions = DemandUnifier::new()
.unify_signature(&expected, &actual)
.expect("concrete type satisfies bounds");
assert_eq!(substitutions.cores.get(&0), Some(&named("int")));
}
#[test]
fn unifier_rejects_recursive_value_hole() {
let error = DemandUnifier::new()
.unify_signature(
&DemandSignature::Hole(0),
&DemandSignature::Fun {
param: Box::new(DemandSignature::Hole(0)),
ret: Box::new(DemandSignature::Core(named("int"))),
},
)
.expect_err("recursive value hole");
assert_eq!(
error,
DemandUnifyError::Occurs {
namespace: DemandHoleNamespace::Value,
id: 0,
}
);
}
#[test]
fn unifier_rejects_recursive_core_hole() {
let error = DemandUnifier::new()
.unify_signature(
&DemandSignature::Core(DemandCoreType::Hole(0)),
&DemandSignature::Core(DemandCoreType::Tuple(vec![DemandCoreType::Hole(0)])),
)
.expect_err("recursive core hole");
assert_eq!(
error,
DemandUnifyError::Occurs {
namespace: DemandHoleNamespace::Core,
id: 0,
}
);
}
#[test]
fn unifier_rejects_recursive_effect_hole() {
let error = DemandUnifier::new()
.unify_signature(
&DemandSignature::Thunk {
effect: DemandEffect::Hole(0),
value: Box::new(DemandSignature::Core(named("unit"))),
},
&DemandSignature::Thunk {
effect: DemandEffect::Row(vec![
DemandEffect::Hole(0),
DemandEffect::Atom(named("io")),
]),
value: Box::new(DemandSignature::Core(named("unit"))),
},
)
.expect_err("recursive effect hole");
assert_eq!(
error,
DemandUnifyError::Occurs {
namespace: DemandHoleNamespace::Effect,
id: 0,
}
);
}
fn named(name: &str) -> DemandCoreType {
named_with_args(name, Vec::new())
}
fn named_with_args(name: &str, args: Vec<DemandTypeArg>) -> DemandCoreType {
DemandCoreType::Named {
path: typed_ir::Path::from_name(typed_ir::Name(name.to_string())),
args,
}
}
fn field(name: &str, value: DemandCoreType) -> DemandRecordField {
DemandRecordField {
name: typed_ir::Name(name.to_string()),
value,
optional: false,
}
}
fn case(name: &str, payloads: Vec<DemandCoreType>) -> DemandVariantCase {
DemandVariantCase {
name: typed_ir::Name(name.to_string()),
payloads,
}
}
}