use std::sync::Arc;
use crate::Error;
use crate::compare;
use crate::handle::Handle;
use crate::heap::{Cursor, Heap};
use crate::int::{IntMode, IntOp};
use crate::memo::{MAX_KEY, Memo};
use crate::node::Kind;
use crate::opts::Opts;
use crate::plan::{Arith, Bind, Cmp, Code, LibArg, Node, P, Quant, SetOp, StdFn, Update};
use crate::store::Store;
#[path = "eval_product.rs"]
mod product;
#[path = "eval_work.rs"]
mod work;
const MAX_CALL_DEPTH: usize = 64;
pub const WORK_POLL_UNITS: u64 = 32;
#[derive(Clone, Copy, Debug, Default)]
pub struct EvalStats {
pub forced: u64,
pub cached: u64,
pub transient_thunks: u64,
}
pub trait WorkControl: std::fmt::Debug + Send + Sync {
fn proceed(&self) -> bool;
}
#[derive(Debug)]
pub struct Machine {
pub heap: Heap,
pub frame: Vec<Handle>,
pub base: usize,
pub s0: Vec<Handle>,
pub s1: Vec<Handle>,
pub assigned: usize,
pub opts: Opts,
pub memo: Memo,
pub stats: EvalStats,
pub warn: bool,
pub warnings: Vec<(u16, u32)>,
pub printed: Vec<String>,
output_limits: Option<(usize, usize)>,
output_used: (usize, usize),
output_failure: Option<&'static str>,
pub(crate) checker_access: CheckerAccess,
pub draw: Option<Box<dyn crate::random::DrawStream>>,
pub draws: u64,
pub level: i64,
pub(crate) conts: Vec<crate::generate::ContNode>,
pub(crate) cvals: Vec<Handle>,
pub(crate) saved: Vec<Handle>,
scratch: Vec<Vec<Handle>>,
transient_slots: Vec<usize>,
depth: usize,
pub(crate) fuel: u64,
refuse_unrecorded_warnings: bool,
proven_s0: Vec<Handle>,
proven_s1: Vec<Handle>,
proven: Vec<Handle>,
work_control: Option<Arc<dyn WorkControl>>,
work_countdown: u64,
bounded_countdown: u64,
pub(crate) debugger: Option<Arc<dyn crate::debug::Observer>>,
pub(crate) calls: Option<CallCache>,
pub(crate) transient_bound: usize,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum CheckerAccess {
Full,
Level,
Denied,
}
#[derive(Debug, Default)]
pub(crate) struct CallCache {
revision: (u64, u64),
results: std::collections::HashMap<Box<[u64]>, Handle>,
key: Vec<u64>,
pub(crate) hits: u64,
}
const CALL_CACHE_ENTRIES: usize = 1 << 16;
fn eval_err(what: &str) -> Error {
Error::eval(what)
}
fn general(what: &str) -> Error {
Error::eval_class(crate::TlcClass::GENERAL, what)
}
fn eval_exc(code: u32, what: &str) -> Error {
Error::eval_class(crate::TlcClass::eval_exception(code), what)
}
pub(crate) fn cardinality_error() -> Error {
eval_exc(2181, "Attempted to compute cardinality of the value")
}
fn one_arg(op: &str, what: &str) -> Error {
eval_exc(
2283,
&format!("The argument of {op} should be a {what}, but instead it is not"),
)
}
fn speculative(e: Error) -> Error {
if e.kind() == crate::ErrorKind::Eval {
Error::unsupported(format!(
"an evaluation error in an expression TLC evaluates lazily, where it may not fail: {}",
e.message()
))
} else {
e
}
}
fn int_of(h: Handle) -> Result<i64, Error> {
h.as_int().ok_or_else(|| eval_err("expected an integer"))
}
fn bool_of(h: Handle) -> Result<bool, Error> {
h.as_bool().ok_or_else(|| eval_err("expected a boolean"))
}
fn mk_int(v: i64) -> Result<Handle, Error> {
Handle::int(v).ok_or_else(|| Error::unsupported("integer outside the M0 core's 61-bit range"))
}
impl Machine {
#[must_use]
pub fn new(store: Arc<Store>, nvars: usize, opts: Opts, mut memo: Memo) -> Self {
memo.set_cap(opts.memo_cap);
memo.reserve_members(opts.memo && store.semantics().tlc_comparisons);
memo.reserve_member_index(opts.member_index && !store.semantics().tlc_comparisons);
Self {
heap: Heap::new(store, !opts.arena, !opts.delta_hash),
frame: Vec::new(),
base: 0,
s0: vec![Handle::EMPTY; nvars],
s1: vec![Handle::EMPTY; nvars],
assigned: 0,
opts,
memo,
stats: EvalStats::default(),
warn: true,
warnings: Vec::new(),
printed: Vec::new(),
output_limits: None,
output_used: (0, 0),
output_failure: None,
checker_access: CheckerAccess::Full,
draw: None,
draws: 0,
level: 0,
conts: Vec::new(),
cvals: Vec::new(),
saved: Vec::new(),
scratch: Vec::new(),
transient_slots: Vec::new(),
depth: 0,
fuel: u64::MAX,
refuse_unrecorded_warnings: false,
proven_s0: Vec::new(),
proven_s1: Vec::new(),
proven: Vec::new(),
work_control: None,
work_countdown: 0,
bounded_countdown: 0,
debugger: None,
calls: None,
transient_bound: usize::MAX,
}
}
pub fn set_fuel(&mut self, units: u64) {
self.disarm_inline_charge();
self.fuel = units;
self.memo.reserve_member_index(
units == u64::MAX
&& self.opts.member_index
&& !self.heap.store.semantics().tlc_comparisons,
);
}
#[must_use]
pub const fn fuel_exhausted(&self) -> bool {
self.fuel == 0
}
pub fn set_refuse_unrecorded_warnings(&mut self, enabled: bool) {
self.refuse_unrecorded_warnings = enabled;
}
pub fn set_proven_materialized(
&mut self,
s0: &[Handle],
s1: &[Handle],
others: impl IntoIterator<Item = Handle>,
) {
let keep = |h: &Handle| {
if h.is_persistent() && h.is_compound() {
*h
} else {
Handle::EMPTY
}
};
self.proven_s0.clear();
self.proven_s0.extend(s0.iter().map(keep));
self.proven_s1.clear();
self.proven_s1.extend(s1.iter().map(keep));
self.proven.clear();
self.proven.extend(
others
.into_iter()
.filter(|h| h.is_persistent() && h.is_compound()),
);
}
fn proven(&self, h: Handle) -> bool {
h.is_compound()
&& (self.proven_s0.contains(&h)
|| self.proven_s1.contains(&h)
|| self.proven.contains(&h))
}
#[inline]
fn proven_at(&self, v: usize, primed: bool, h: Handle) -> bool {
let row = if primed {
&self.proven_s1
} else {
&self.proven_s0
};
(h.is_compound() && row.get(v) == Some(&h)) || self.proven(h)
}
pub fn set_work_control(&mut self, control: Option<Arc<dyn WorkControl>>) {
self.heap.set_work_control(control.clone());
self.work_control = control;
self.work_countdown = 0;
self.bounded_countdown = 0;
}
pub fn set_debugger(&mut self, observer: Option<Arc<dyn crate::debug::Observer>>) {
self.debugger = observer;
}
pub fn with_deferred_reclamation<T>(&mut self, work: impl FnOnce(&mut Self) -> T) -> T {
let previous = std::mem::replace(&mut self.heap.defer_reclamation, true);
let result = work(self);
self.heap.defer_reclamation = previous;
result
}
pub fn deny_checker_access(&mut self) {
self.checker_access = CheckerAccess::Denied;
}
pub fn allow_finite_level(&mut self) {
if self.checker_access == CheckerAccess::Denied {
self.checker_access = CheckerAccess::Level;
}
}
fn check_finite_access(&self, op: dive_ir::StdOp) -> Result<(), Error> {
let allowed = match self.checker_access {
CheckerAccess::Full => true,
CheckerAccess::Level => op == dive_ir::StdOp::TlcTLCGet,
CheckerAccess::Denied => false,
};
if !allowed
&& op.impure()
&& !matches!(op, dive_ir::StdOp::TlcPrint | dive_ir::StdOp::TlcPrintT)
{
return Err(Error::unsupported(format!(
"{}: native finite mode runtime effect is unsupported",
op.qualified_name()
)));
}
Ok(())
}
pub fn set_output_limits(&mut self, events: usize, bytes: usize) {
self.output_limits = Some((events, bytes));
}
#[must_use]
pub const fn output_failure(&self) -> Option<&'static str> {
self.output_failure
}
pub(crate) fn print(&mut self, text: String) -> Result<(), Error> {
if let Some((events, bytes)) = self.output_limits {
let total = self.output_used.1.checked_add(text.len());
let failure = if self.output_used.0 >= events {
Some("simulation output event bound")
} else if total.is_none_or(|total| total > bytes) {
Some("simulation output byte bound")
} else {
None
};
if let Some(failure) = failure {
self.output_failure.get_or_insert(failure);
return Err(Error::unsupported(failure));
}
self.output_used = (self.output_used.0 + 1, total.unwrap_or(bytes));
}
self.printed.push(text);
Ok(())
}
#[inline]
pub(crate) fn charge(&mut self, n: usize) -> Result<(), Error> {
let units = (n as u64).max(1);
if units < self.work_countdown {
self.work_countdown -= units;
return Ok(());
}
self.charge_slow(units, n)
}
#[inline(never)]
fn charge_slow(&mut self, units: u64, n: usize) -> Result<(), Error> {
let left = self.work_countdown.max(self.bounded_countdown);
self.work_countdown = 0;
self.bounded_countdown = 0;
if units < left {
self.bounded_countdown = left - units;
} else if self
.work_control
.as_ref()
.is_some_and(|control| !control.proceed())
{
self.heap.mark_work_interrupted();
return Err(Error::stop());
} else {
self.bounded_countdown = WORK_POLL_UNITS;
}
if self.transient_bound != usize::MAX && self.heap.arena.footprint() > self.transient_bound
{
return Err(Error::unsupported("the start-up evaluation memory bound"));
}
if self.fuel == u64::MAX {
if self.transient_bound == usize::MAX {
self.work_countdown = std::mem::take(&mut self.bounded_countdown);
}
return Ok(());
}
let n = n as u64;
if self.fuel < n {
self.fuel = 0;
return Err(Error::unsupported("the constant-folding budget"));
}
self.fuel -= n;
Ok(())
}
fn disarm_inline_charge(&mut self) {
self.bounded_countdown = self
.bounded_countdown
.max(std::mem::take(&mut self.work_countdown));
}
pub(crate) fn set_transient_bound(&mut self, bytes: usize) {
self.disarm_inline_charge();
self.transient_bound = bytes;
}
fn take_scratch(&mut self) -> Vec<Handle> {
let mut v = self.scratch.pop().unwrap_or_default();
v.clear();
v
}
fn give_scratch(&mut self, v: Vec<Handle>) {
self.scratch.push(v);
}
pub fn enter(&mut self, size: u32) -> usize {
let old = self.base;
self.base = self.frame.len();
self.frame.resize(self.base + size as usize, Handle::EMPTY);
old
}
pub fn leave(&mut self, old: usize) {
self.frame.truncate(self.base);
self.base = old;
if self.frame.is_empty() {
self.transient_slots.clear();
}
}
#[must_use]
pub fn thunk_mark(&self) -> usize {
self.transient_slots.len()
}
pub fn thunks_released(&mut self, since: usize) -> bool {
let len = self.transient_slots.len();
if since >= len {
return true;
}
let live = self.frame.len();
let mut kept = since;
let mut i = since;
while i < len {
let slot = self.transient_slots[i];
if slot < live {
self.transient_slots[kept] = slot;
kept += 1;
}
i += 1;
}
self.transient_slots.truncate(kept);
kept == since
}
#[inline]
pub(crate) fn slot(&self, s: u32) -> Handle {
self.frame
.get(self.base + s as usize)
.copied()
.unwrap_or(Handle::EMPTY)
}
#[inline]
pub(crate) fn set_slot(&mut self, s: u32, v: Handle) {
if let Some(x) = self.frame.get_mut(self.base + s as usize) {
*x = v;
}
}
pub fn eval_bool(&mut self, code: &Code, p: P) -> Result<bool, Error> {
let v = self.eval(code, p)?;
bool_of(v)
}
pub fn eval_norm(&mut self, code: &Code, p: P) -> Result<Handle, Error> {
let v = self.eval(code, p)?;
self.work_norm(v)
}
fn same_vars_direct(&self, leaves: &[(u16, u8)], thunks: &[u32]) -> Result<bool, Error> {
if self.debugger.is_some()
|| self.heap.store().semantics().tlc_comparisons
|| thunks.iter().any(|&slot| !self.slot(slot).is_empty())
{
return Ok(false);
}
for &(v, depth) in leaves {
let v = usize::from(v);
let (Some(&a), Some(&b)) = (self.s0.get(v), self.s1.get(v)) else {
return Ok(false);
};
if !(self.proven_at(v, false, a) || compare::materialized(&self.heap, a, depth)?)
|| (a != b
&& !(self.proven_at(v, true, b)
|| compare::materialized(&self.heap, b, depth)?))
{
return Ok(false);
}
}
Ok(true)
}
pub(crate) fn demand_equals(&mut self, a: Handle, b: Handle) -> Result<bool, Error> {
let a = self.work_norm(a)?;
let b = self.work_norm(b)?;
compare::equals(&self.heap, a, b)
}
pub(crate) fn eval_component(&mut self, code: &Code, p: P) -> Result<Handle, Error> {
let value = self.eval(code, p)?;
if self.heap.kind(value) == Some(Kind::Product) {
Ok(value)
} else {
self.work_norm(value)
}
}
pub fn eval(&mut self, code: &Code, p: P) -> Result<Handle, Error> {
let Some(observer) = &self.debugger else {
return self.eval_inner(code, p);
};
let instruction = crate::debug::Instruction::Value(p);
let guard = crate::debug::Guard::enter(observer, instruction, code, self)?;
let result = self.eval_inner(code, p);
let returned = match &result {
Ok(value) => crate::debug::Returned::Value(*value),
Err(error) => crate::debug::Returned::Failed(error),
};
guard.returned(instruction, code, self, returned)?;
result
}
#[allow(
clippy::too_many_lines,
clippy::many_single_char_names,
reason = "one arm per node kind, with operand names as in the semantics"
)]
fn eval_inner(&mut self, code: &Code, p: P) -> Result<Handle, Error> {
if self.fuel != u64::MAX {
self.charge(1)?;
}
let Some(node) = code.nodes.get(p as usize) else {
return Err(Error::internal("plan node out of range"));
};
match node {
Node::Const(h) => Ok(*h),
Node::Slot(s) => {
let v = self.slot(*s);
if v.is_empty() {
return Err(Error::internal("read of an unbound slot"));
}
Ok(v)
}
Node::Lazy { slot, body } => {
let v = self.slot(*slot);
if !v.is_empty() {
self.stats.cached += 1;
return Ok(v);
}
self.stats.forced += 1;
let v = self.eval(code, *body)?;
if v.is_transient() {
self.stats.transient_thunks += 1;
self.transient_slots.push(self.base + *slot as usize);
}
self.set_slot(*slot, v);
Ok(v)
}
Node::Var(i) => {
let v = self
.s0
.get(usize::from(*i))
.copied()
.unwrap_or(Handle::EMPTY);
if v.is_empty() {
return Err(eval_err("read of an unassigned variable"));
}
Ok(v)
}
Node::Primed(i) => {
let v = self
.s1
.get(usize::from(*i))
.copied()
.unwrap_or(Handle::EMPTY);
if v.is_empty() {
return Err(eval_err("read of an unassigned primed variable"));
}
Ok(v)
}
Node::Not(a) => Ok(Handle::bool(!self.eval_bool(code, *a)?)),
Node::And(items) => {
for &i in items {
if !self.eval_bool(code, i)? {
return Ok(Handle::FALSE);
}
}
Ok(Handle::TRUE)
}
Node::Or(items) => {
for &i in items {
if self.eval_bool(code, i)? {
return Ok(Handle::TRUE);
}
}
Ok(Handle::FALSE)
}
Node::Implies(a, b) => {
if self.eval_bool(code, *a)? {
Ok(Handle::bool(self.eval_bool(code, *b)?))
} else {
Ok(Handle::TRUE)
}
}
Node::Equiv(a, b) => {
let x = self.eval_bool(code, *a)?;
let y = self.eval_bool(code, *b)?;
Ok(Handle::bool(x == y))
}
Node::If(c, a, b) => {
if self.eval_bool(code, *c)? {
self.eval(code, *a)
} else {
self.eval(code, *b)
}
}
Node::Case(arms, other) => {
for &(g, v) in arms {
if self.eval_bool(code, g)? {
return self.eval(code, v);
}
}
match other {
Some(o) => self.eval(code, *o),
None => Err(eval_err("TLC encountered a CASE with no conditions true")),
}
}
Node::Eq(a, b) => {
let x = self.eval_norm(code, *a)?;
let y = self.eval_norm(code, *b)?;
Ok(Handle::bool(compare::equals(&self.heap, x, y)?))
}
Node::SameVars { eq, leaves, thunks } => {
if self.same_vars_direct(leaves, thunks)? {
let same = leaves.iter().all(|&(v, _)| {
let v = usize::from(v);
match (self.s0.get(v), self.s1.get(v)) {
(Some(&a), Some(&b)) => self.heap.eq(a, b),
_ => false,
}
});
return Ok(Handle::bool(same));
}
self.eval(code, *eq)
}
Node::Neq(a, b) => {
let x = self.eval_norm(code, *a)?;
let y = self.eval_norm(code, *b)?;
Ok(Handle::bool(!compare::equals(&self.heap, x, y)?))
}
Node::In(a, s) => {
let x = self.eval_norm(code, *a)?;
let set = self.eval(code, *s)?;
Ok(Handle::bool(self.member(x, set)?))
}
Node::NotIn(a, s) => {
let x = self.eval_norm(code, *a)?;
let set = self.eval(code, *s)?;
Ok(Handle::bool(!self.member(x, set)?))
}
Node::Subseteq(a, b) => {
let x = self.eval(code, *a)?;
let x = self.work_norm(x)?;
let y = self.eval(code, *b)?;
let elems = self.work_elements(x)?;
self.charge(elems.len())?;
for e in elems {
if !self.member(e, y)? {
return Ok(Handle::FALSE);
}
}
Ok(Handle::TRUE)
}
Node::Arith(op, a, b) => {
let x = self.eval(code, *a)?;
let y = self.eval(code, *b)?;
if let (Some(i), Some(j)) = (x.as_int(), y.as_int())
&& let Some(h) = fast_arith(*op, i, j, self.heap.int_mode())
{
return Ok(h);
}
if *op == Arith::Pow && self.fuel != u64::MAX {
let words = self.heap.pow_result_words(x, y);
self.charge(usize::try_from(words).unwrap_or(usize::MAX))?;
}
self.heap.int_arith(int_op(*op), x, y)
}
Node::Cmp(op, a, b) => {
let x = self.eval(code, *a)?;
let y = self.eval(code, *b)?;
let o = match (x.as_int(), y.as_int()) {
(Some(i), Some(j)) => i.cmp(&j),
_ => self
.heap
.int_cmp(x, y)
.ok_or_else(|| eval_err("expected an integer"))?,
};
Ok(Handle::bool(match op {
Cmp::Lt => o.is_lt(),
Cmp::Le => o.is_le(),
Cmp::Gt => o.is_gt(),
Cmp::Ge => o.is_ge(),
}))
}
Node::Neg(a) => {
let x = self.eval(code, *a)?;
if self.heap.int_mode() == IntMode::Big
&& let Some(h) = x.as_int().and_then(i64::checked_neg).and_then(Handle::int)
{
return Ok(h);
}
self.heap.int_neg(x)
}
Node::Range(a, b) => {
let x = int_of(self.eval(code, *a)?)?;
let y = int_of(self.eval(code, *b)?)?;
Ok(self.heap.interval(x, y))
}
Node::SetEnum(items) => {
let mut v = self.take_scratch();
for &i in items {
match self.eval_component(code, i) {
Ok(e) => v.push(e),
Err(e) => {
self.give_scratch(v);
return Err(e);
}
}
}
for value in &mut v {
*value = self.work_norm(*value)?;
}
if let Err(error) = compare::require_materialized(&self.heap, &v) {
self.give_scratch(v);
return Err(error);
}
let r = self.heap.set_from(&mut v);
self.give_scratch(v);
self.checked_set(r)
}
Node::SetBin(op, a, b) => {
let x = self.eval(code, *a)?;
let y = self.eval(code, *b)?;
self.set_bin(*op, x, y)
}
Node::Powerset(a) => {
let x = self.eval(code, *a)?;
Ok(self.heap.symbolic(Kind::Subset, 0, &[x]))
}
Node::BigUnion(a) => {
let x = self.eval_norm(code, *a)?;
let members = self.work_elements(x)?;
let mut normed = Vec::with_capacity(members.len());
for m in members {
normed.push(self.work_norm(m)?);
}
if normed.iter().any(|&m| !self.heap.is_finite(m)) {
let mut it = normed.into_iter();
let Some(first) = it.next() else {
return Err(Error::internal("an empty UNION with an infinite member"));
};
return Ok(it.fold(first, |acc, m| self.heap.union(acc, m)));
}
let mut out = Vec::new();
for m in normed {
let m = self.work_norm(m)?;
let es = self.work_elements(m)?;
self.charge(es.len())?;
out.extend(es);
}
let r = self.heap.set_from(&mut out);
self.checked_set(r)
}
Node::Product(items) => {
let mut v = Vec::with_capacity(items.len());
for &i in items {
v.push(self.eval(code, i)?);
}
Ok(self.heap.symbolic(Kind::Product, 0, &v))
}
Node::FcnSet(d, r) => {
let x = self.eval_component(code, *d)?;
let y = self.eval(code, *r)?;
Ok(self.heap.symbolic(Kind::FcnSet, 0, &[x, y]))
}
Node::RecSet(fields) => {
let mut v: Vec<Handle> = fields.iter().map(|f| f.0).collect();
for &(_, s) in fields {
v.push(self.eval(code, s)?);
}
Ok(self.heap.symbolic(Kind::RecSet, 0, &v))
}
Node::Filter { bind, pred, subset } => self.filter(code, bind, *pred, *subset),
Node::Map { binds, body } => {
let mut out = Vec::new();
self.for_each_binding(code, binds, &mut |m: &mut Self| {
let v = m.eval_component(code, *body)?;
let v = m.work_norm(v)?;
m.charge(1)?;
out.try_reserve(1)
.map_err(|_| Error::unsupported("MAP construction allocation"))?;
out.push(v);
Ok(true)
})?;
compare::require_materialized(&self.heap, &out)?;
let r = self.heap.set_from(&mut out);
self.checked_set(r)
}
Node::FcnCons { binds, body } => self.fcn_cons(code, binds, *body),
Node::Quant { kind, binds, body } => self.quant(code, *kind, binds, *body),
Node::Apply(f, a) => {
let fv = self.eval(code, *f)?;
let av = self.eval_norm(code, *a)?;
self.apply(fv, av)
}
Node::Select(r, field) => {
let rv = self.eval(code, *r)?;
self.select(rv, *field)
}
Node::Domain(f) => {
let fv = self.eval(code, *f)?;
self.domain(fv)
}
Node::Except { base, updates } => {
let mut f = self.eval_norm(code, *base)?;
for u in updates {
f = self.except(code, f, u, 0)?;
}
Ok(f)
}
Node::Tuple(items) => {
let mut v = self.take_scratch();
for &i in items {
match self.eval_component(code, i) {
Ok(e) => v.push(e),
Err(e) => {
self.give_scratch(v);
return Err(e);
}
}
}
let r = self.heap.tuple_literal(&v);
self.give_scratch(v);
Ok(r)
}
Node::Record(fields) => {
let mut keys = self.take_scratch();
let mut vals = self.take_scratch();
for &(k, e) in fields {
keys.push(k);
match self.eval_component(code, e) {
Ok(v) => vals.push(v),
Err(e) => {
self.give_scratch(keys);
self.give_scratch(vals);
return Err(e);
}
}
}
let r = self.heap.record(&keys, &vals);
self.give_scratch(keys);
self.give_scratch(vals);
Ok(r)
}
Node::Scope { reset, body } => {
for &s in reset {
self.set_slot(s, Handle::EMPTY);
}
self.eval(code, *body)
}
Node::Call { fun, args } => self.call(code, *fun, args),
Node::Std(f, args) => self.std(code, *f, args),
Node::Lib {
op,
args,
repeatable_args,
} => {
self.check_finite_access(*op)?;
if crate::stdlib::deferred(*op) {
return Err(crate::stdlib::deferred_refusal(*op));
}
let prints = matches!(
op,
dive_ir::StdOp::TlcPrint
| dive_ir::StdOp::TlcPrintT
| dive_ir::StdOp::TlcToString
| dive_ir::StdOp::TlcRandomElement
);
let mut a = Vec::with_capacity(args.len());
for &x in args {
a.push(if prints {
self.eval(code, x)?
} else if *op == dive_ir::StdOp::TlcMakeFcn {
self.eval_component(code, x)?
} else {
let value = self.eval_component(code, x)?;
self.work_norm(value)?
});
}
if !repeatable_args
&& matches!(
op,
dive_ir::StdOp::SequencesExtReplaceFirstSubSeq
| dive_ir::StdOp::SequencesExtReplaceAllSubSeqs
)
&& a.iter().any(|h| h.as_str_id().is_none())
{
return Err(Error::unsupported(format!(
"{} with sequence arguments whose repeated fallback demand is not proven effect-free",
op.qualified_name()
)));
}
crate::stdlib::call(self, *op, &a)
}
Node::LibHo(op, args) => {
self.check_finite_access(*op)?;
let mut a = Vec::with_capacity(args.len());
for x in args {
a.push(match x {
LibArg::Value(p) => {
let value = self.eval_component(code, *p)?;
crate::stdlib::Ho::Value(self.work_norm(value)?)
}
LibArg::Op { params, body } => {
crate::stdlib::Ho::Op(crate::stdlib::OpFn::new(code, params, *body))
}
});
}
crate::stdlib::call_ho(self, *op, &a)
}
Node::Enabled { g, .. } => self.enabled(code, *g),
Node::Composition {
first, then, reset, ..
} => self.composition_holds(code, *first, *then, reset),
Node::Memo { site, body } => self.memo_eval(code, *site, *body),
Node::Spec(b) => self.eval(code, *b).map_err(speculative),
Node::Beta { chain, fc, arg } => self.beta(code, *chain, *fc, *arg),
Node::DomCheck { slot, domain, body } => {
let d = self.eval(code, *domain).map_err(speculative)?;
let x = self.slot(*slot);
if !self.member(x, d)? {
return Err(general(
"In applying the function\na recursive function, the argument is not in its domain",
));
}
self.eval(code, *body)
}
Node::InLazy { elem, set, neg } => {
let x = self.eval_norm(code, *elem)?;
let r = self.member_lazy(code, x, *set)?;
Ok(Handle::bool(r != *neg))
}
}
}
fn beta(&mut self, code: &Code, chain: P, fc: P, arg: P) -> Result<Handle, Error> {
match code.nodes.get(chain as usize) {
Some(Node::Lazy { slot, body }) => {
let v = self.slot(*slot);
if v.is_empty() {
self.beta(code, *body, fc, arg)
} else {
let a = self.eval_norm(code, arg)?;
self.apply(v, a)
}
}
Some(Node::Scope { reset, body }) => {
for &s in reset {
self.set_slot(s, Handle::EMPTY);
}
self.beta(code, *body, fc, arg)
}
Some(Node::Spec(b)) => self.beta(code, *b, fc, arg),
Some(Node::FcnCons { binds, body }) if chain == fc => {
if let [bind] = &binds[..]
&& let [slot] = bind.slots[..]
{
return self.beta_one(code, bind.domain, slot, arg, *body);
}
self.beta_many(code, chain, binds, arg, *body)
}
_ => Err(Error::internal("a lazy application of a non-function node")),
}
}
fn beta_one(
&mut self,
code: &Code,
domain: P,
slot: u32,
arg: P,
body: P,
) -> Result<Handle, Error> {
let dom = self.eval(code, domain)?;
let x = self.eval_norm(code, arg)?;
if !self.member(x, dom)? {
return Err(general(
"In applying the function\na function, the argument is not in its domain",
));
}
let old = self.slot(slot);
self.set_slot(slot, x);
let out = self.eval(code, body);
self.set_slot(slot, old);
out
}
fn beta_many(
&mut self,
code: &Code,
fc: P,
binds: &[Bind],
arg: P,
body: P,
) -> Result<Handle, Error> {
if binds.iter().any(|b| b.tuple || b.slots.is_empty()) {
return Err(Error::internal(
"a lazy application with a tuple pattern or no bound variable",
));
}
let mut doms = Vec::with_capacity(binds.len());
for b in binds {
doms.push(self.eval(code, b.domain)?);
}
let x = self.eval_norm(code, arg)?;
let arity: usize = binds.iter().map(|b| b.slots.len()).sum();
let parts = if x.is_compound() {
let v = self.heap.view(x);
(v.kind == Kind::IntFcn && v.lo == 1 && v.data.len() == arity).then(|| v.data.to_vec())
} else {
None
};
let Some(parts) = parts else {
let f = self.eval(code, fc).map_err(speculative)?;
return self.apply(f, x);
};
let mut k = 0;
for (b, &dom) in binds.iter().zip(&doms) {
for _ in &b.slots {
if !self.member(parts[k], dom)? {
return Err(general(
"In applying the function\na function, the argument is not in its domain",
));
}
k += 1;
}
}
let mark = self.saved.len();
for &s in binds.iter().flat_map(|b| b.slots.iter()) {
let v = self.slot(s);
self.saved.push(v);
}
for (&s, &p) in binds.iter().flat_map(|b| b.slots.iter()).zip(&parts) {
self.set_slot(s, p);
}
let out = self.eval(code, body);
for (k, &s) in binds.iter().flat_map(|b| b.slots.iter()).enumerate() {
let v = self.saved.get(mark + k).copied().unwrap_or(Handle::EMPTY);
self.set_slot(s, v);
}
self.saved.truncate(mark);
out
}
fn member_lazy(&mut self, code: &Code, x: Handle, set: P) -> Result<bool, Error> {
match code.nodes.get(set as usize) {
Some(Node::Filter { bind, pred, .. }) => {
if !self.member_lazy(code, x, bind.domain)? {
return Ok(false);
}
let mark = self.saved.len();
for &s in &bind.slots {
let v = self.slot(s);
self.saved.push(v);
}
let r = self
.bind_one(bind, x)
.and_then(|()| self.eval_bool(code, *pred));
for (k, &s) in bind.slots.iter().enumerate() {
let v = self.saved.get(mark + k).copied().unwrap_or(Handle::EMPTY);
self.set_slot(s, v);
}
self.saved.truncate(mark);
r
}
Some(Node::SetBin(op, a, b)) => {
let (op, a, b) = (*op, *a, *b);
let left = self.member_lazy(code, x, a)?;
match op {
SetOp::Cup if left => Ok(true),
SetOp::Cap | SetOp::Minus if !left => Ok(false),
SetOp::Cup | SetOp::Cap => self.member_lazy(code, x, b),
SetOp::Minus => Ok(!self.member_lazy(code, x, b)?),
}
}
Some(Node::Lazy { slot, body }) => {
let v = self.slot(*slot);
if v.is_empty() {
self.member_lazy(code, x, *body)
} else {
self.member(x, v)
}
}
Some(Node::Scope { reset, body }) => {
for &s in reset {
self.set_slot(s, Handle::EMPTY);
}
self.member_lazy(code, x, *body)
}
Some(Node::Spec(b)) => self.member_lazy(code, x, *b),
Some(Node::Memo { site, body })
if code.sites.get(*site as usize).is_some_and(|s| s.candidate) =>
{
self.member_lazy(code, x, *body)
}
_ => {
let s = self.eval(code, set)?;
self.member(x, s)
}
}
}
fn memo_eval(&mut self, code: &Code, site: u32, body: P) -> Result<Handle, Error> {
if self.heap.speculative {
return self.eval(code, body);
}
let Some(s) = code.sites.get(site as usize) else {
return self.eval(code, body);
};
if !(self.opts.memo || s.step) || !self.memo.active(site) {
return self.eval(code, body);
}
if s.candidate && !self.memo.may_keep() {
self.memo.charge_kept(site, 0);
return self.eval(code, body);
}
let added = self.heap.cache.added;
let mut key = [Handle::EMPTY; MAX_KEY];
let mut n = 0;
for &v in &s.vars {
let h = self
.s0
.get(usize::from(v))
.copied()
.unwrap_or(Handle::EMPTY);
if h.is_transient() || h.is_empty() || n >= MAX_KEY {
self.memo.bypass(site);
return self.eval(code, body);
}
key[n] = h;
n += 1;
}
for &v in &s.primed {
let h = self
.s1
.get(usize::from(v))
.copied()
.unwrap_or(Handle::EMPTY);
let h = match self.heap.intern_exact(h) {
Ok(k) if !h.is_empty() && n < MAX_KEY => k,
_ => {
if s.candidate {
self.charge_kept(site, added);
}
self.memo.bypass(site);
return self.eval(code, body);
}
};
key[n] = h;
n += 1;
}
for &sl in &s.slots {
let h = self.slot(sl);
if h.is_transient() || h.is_empty() || n >= MAX_KEY {
self.memo.bypass(site);
return self.eval(code, body);
}
key[n] = h;
n += 1;
}
if s.candidate {
self.charge_kept(site, added);
}
if let Some(r) = self.memo.get(site, &key[..n]) {
return Ok(r);
}
let r = self.eval(code, body)?;
let added = self.heap.cache.added;
let kept = if s.step && r.is_transient() {
self.heap.intern_exact(r).unwrap_or(r)
} else {
r
};
if s.candidate {
self.charge_kept(site, added);
}
if !kept.is_transient() {
self.memo.put(site, &key[..n], kept);
}
Ok(kept)
}
fn charge_kept(&mut self, site: u32, since: u64) {
let bytes = self.heap.cache.added.saturating_sub(since);
self.memo.charge_kept(site, bytes);
}
fn call(&mut self, code: &Code, fun: u32, args: &[P]) -> Result<Handle, Error> {
self.charge(1)?;
if self.depth >= MAX_CALL_DEPTH {
return Err(Error::unsupported(
"Core recursive-call depth limit (64 activations)",
));
}
self.depth += 1;
let result = self.call_inner(code, fun, args);
self.depth -= 1;
result
}
fn call_inner(&mut self, code: &Code, fun: u32, args: &[P]) -> Result<Handle, Error> {
let Some(f) = code.funs.get(fun as usize) else {
return Err(Error::internal("call of an unknown function"));
};
let mut vals = self.take_scratch();
for &a in args {
match self.eval_norm(code, a) {
Ok(v) => vals.push(v),
Err(e) => {
self.give_scratch(vals);
return Err(e);
}
}
}
let cached = match &mut self.calls {
Some(cache) if !self.heap.speculative => {
let revision = self.heap.arena.cache_revision();
if cache.revision != revision {
cache.results.clear();
cache.revision = revision;
}
cache.key.clear();
cache.key.push(u64::from(fun));
cache.key.extend(vals.iter().map(|h| h.0));
if let Some(&r) = cache.results.get(cache.key.as_slice()) {
cache.hits += 1;
self.give_scratch(vals);
return Ok(r);
}
Some(cache.key.clone().into_boxed_slice())
}
_ => None,
};
let old = self.enter(f.frame);
for (i, &v) in vals.iter().enumerate() {
#[allow(
clippy::cast_possible_truncation,
reason = "parameter counts are small"
)]
let i = i as u32;
let s = match i.checked_sub(f.params) {
None => i,
Some(c) => f.caps.get(c as usize).copied().unwrap_or(i),
};
self.set_slot(s, v);
}
self.give_scratch(vals);
let r = self.eval(code, f.body);
self.leave(old);
if let (Some(key), Ok(h), Some(cache)) = (cached, &r, &mut self.calls)
&& cache.revision == self.heap.arena.cache_revision()
{
if cache.results.len() >= CALL_CACHE_ENTRIES {
cache.results.clear();
}
cache.results.insert(key, *h);
}
r
}
fn checked_set(&self, s: Handle) -> Result<Handle, Error> {
compare::require_materialized(&self.heap, &[s])?;
if self.heap.store().semantics().tlc_comparisons && s.is_compound() {
compare::check_set(&self.heap, self.heap.view(s).data)?;
}
Ok(s)
}
fn non_fcn_member(&self, x: Handle, what: &str) -> Result<bool, Error> {
if x.is_compound() && self.heap.view(x).kind.is_fcn() {
return Ok(false);
}
if x.as_model_id().is_some() {
return self.mv_member(x);
}
Err(eval_err(&format!(
"Attempted to check if a value that is not a function is in {what}"
)))
}
fn mv_member(&self, x: Handle) -> Result<bool, Error> {
if compare::mv_type(&self.heap, x).is_none() {
return Ok(false);
}
Err(general(
"Attempted to check if the typed model value is an element of a set of another kind",
))
}
#[allow(clippy::too_many_lines, reason = "one arm per set kind")]
pub fn member(&mut self, x: Handle, set: Handle) -> Result<bool, Error> {
if self.fuel != u64::MAX && set.is_compound() && self.heap.view(set).kind == Kind::SetEnum {
self.domain_work(set, false, 0)?;
}
if !set.is_compound() {
return Err(eval_err("membership in a value that is not a set"));
}
let kind = self.heap.view(set).kind;
if kind != Kind::Set
&& kind != Kind::Product
&& kind != Kind::Subset
&& !self.opts.symbolic_member
&& self.heap.is_finite(set)
&& !self.heap.is_lazy(set)
{
let m = self.work_materialize_cached(set)?;
return self.member(x, m);
}
let v = self.heap.view(set);
match v.kind {
Kind::Set => {
let indexed = if self.fuel == u64::MAX && !v.is_lazy() {
self.memo.member_index.search(&self.heap, set, x, v.data)?
} else {
None
};
if indexed.is_none() {
for h in [x, set] {
if !h.is_compound()
|| self.heap.view(h).flags & crate::node::flags::CONCRETE != 0
|| !self.proven(h)
{
compare::require_materialized(&self.heap, &[h])?;
}
}
}
if indexed
.unwrap_or_else(|| v.data.binary_search_by(|&e| self.heap.cmp(e, x)).is_ok())
{
return Ok(true);
}
compare::miss_cached(&self.heap, &mut self.memo, x, set, v.data)?;
Ok(false)
}
Kind::Interval => {
let hi = v.data[0].as_int().unwrap_or(v.lo - 1);
let lo = v.lo;
match x.as_int() {
Some(i) => Ok(lo <= i && i <= hi),
None if lo > hi => Ok(false),
None if x.as_model_id().is_some()
&& compare::mv_type(&self.heap, x).is_none() =>
{
Ok(false)
}
None if self.heap.is_int(x) => Ok(false),
None => Err(general(
"Attempted to check if the value:\na value that is not an integer\nis in the integer interval",
)),
}
}
Kind::Nat | Kind::Int if self.heap.is_int(x) => Ok(match x.as_int() {
Some(i) => v.kind == Kind::Int || i >= 0,
None => {
v.kind == Kind::Int
|| self
.heap
.int_cmp(x, Handle::int(0).unwrap_or(Handle::EMPTY))
== Some(std::cmp::Ordering::Greater)
}
}),
Kind::Nat | Kind::Int if x.as_model_id().is_some() => self.mv_member(x),
Kind::Nat | Kind::Int => Err(eval_exc(
2158,
"Attempted to check if the value:\na value that is not an integer\nis an element of Nat or Int.",
)),
Kind::Subset => {
let base = v.data[0];
let query_kind = self.heap.kind(x);
if !matches!(query_kind, Some(Kind::Set | Kind::SetEnum | Kind::Interval)) {
return Err(eval_err(
"Attempted to check if a non-enumerable value is an element of SUBSET",
));
}
let mut elements = self.work_cursor(x)?;
while let Some(e) = self.work_next(&mut elements)? {
if !self.member(e, base)? {
return Ok(false);
}
}
Ok(true)
}
Kind::SeqSet => {
let base = v.data[0];
if !x.is_compound() || !self.heap.view(x).kind.is_fcn() {
return self.non_fcn_member(x, "a set of sequences");
}
let xv = self.heap.view(x);
if xv.kind != Kind::IntFcn || xv.lo != 1 {
compare::guard_kind_member(
&self.heap,
"a membership test of a function that is not a sequence in Seq(S)",
)?;
return Ok(false);
}
let vals = xv.data.to_vec();
for e in vals {
if !self.member(e, base)? {
return Ok(false);
}
}
Ok(true)
}
Kind::FcnSet => {
let (dom, rng) = (v.data[0], v.data[1]);
if !x.is_compound() || !self.heap.view(x).kind.is_fcn() {
return self.non_fcn_member(x, "a set of functions");
}
let d = self.domain(x)?;
let d = self.work_norm(d)?;
let dom = self.work_norm(dom)?;
if !self.heap.eq(d, dom) {
if self.heap.store().semantics().tlc_comparisons {
compare::equals(&self.heap, d, dom)?;
}
return Ok(false);
}
let vals = self.heap.view(x).values().to_vec();
for e in vals {
if !self.member(e, rng)? {
return Ok(false);
}
}
Ok(true)
}
Kind::RecSet => {
let n = v.data.len() / 2;
let (names, sets) = (v.data[..n].to_vec(), v.data[n..].to_vec());
if !x.is_compound() || !self.heap.view(x).kind.is_fcn() {
return self.non_fcn_member(x, "a set of records");
}
let xv = self.heap.view(x);
if xv.kind != Kind::Fcn || xv.keys().iter().any(|k| k.as_str_id().is_none()) {
compare::guard_kind_member(
&self.heap,
"a membership test of a function that is not a record in a set of records",
)?;
return Ok(false);
}
if xv.keys() != names.as_slice() {
return Ok(false);
}
let vals = xv.values().to_vec();
for (e, s) in vals.into_iter().zip(sets) {
if !self.member(e, s)? {
return Ok(false);
}
}
Ok(true)
}
Kind::Product => {
let sets = v.data.to_vec();
if !x.is_compound() || !self.heap.view(x).kind.is_fcn() {
return self.non_fcn_member(x, "a set of tuples");
}
let xv = self.heap.view(x);
if xv.kind == Kind::Fcn && xv.keys().iter().any(|k| k.as_int().is_none()) {
compare::guard_kind_member(
&self.heap,
"a membership test of a function over non-integers in a set of tuples",
)?;
}
if xv.kind != Kind::IntFcn || xv.lo != 1 || xv.data.len() != sets.len() {
return Ok(false);
}
let vals = xv.data.to_vec();
for (e, s) in vals.into_iter().zip(sets) {
if !self.member(e, s)? {
return Ok(false);
}
}
Ok(true)
}
Kind::IntFcn | Kind::Fcn | Kind::Lambda => Err(eval_err("membership in a function")),
Kind::BigInt => Err(eval_err("membership in a value that is not a set")),
Kind::Union => {
let (a, b) = (v.data[0], v.data[1]);
Ok(self.member(x, a)? || self.member(x, b)?)
}
Kind::SetPred => Err(Error::unsupported(
"membership in a lazy set predicate (the evaluator side is not built)",
)),
Kind::SetEnum => Err(Error::unsupported(
"membership in a set enumeration TLC has not normalized (--compat=tlc)",
)),
}
}
fn set_bin(&mut self, op: SetOp, x: Handle, y: Handle) -> Result<Handle, Error> {
let (x, y) = (self.work_norm(x)?, self.work_norm(y)?);
let fx = self.heap.is_finite(x);
let fy = self.heap.is_finite(y);
for (s, finite) in [(x, fx), (y, fy)] {
if finite && s.is_compound() {
let n = self.heap.view(s).len();
self.charge(n)?;
}
}
match op {
SetOp::Cup => {
if !fx || !fy {
return Ok(self.heap.union(x, y));
}
if let Some(union) = self.union_concrete(x, y)? {
return self.checked_set(union);
}
let mut v = self.work_elements(x)?;
v.extend(self.work_elements(y)?);
let r = self.heap.set_from(&mut v);
self.checked_set(r)
}
SetOp::Cap => {
let (a, b) = if fx {
(x, y)
} else if fy {
(y, x)
} else {
return Err(Error::unsupported("intersection of infinite sets"));
};
let mut out = Vec::new();
for e in self.work_elements(a)? {
if self.member(e, b)? {
out.push(e);
}
}
Ok(self.heap.set_sorted(&out))
}
SetOp::Minus => {
if !fx {
return Err(Error::unsupported("difference of an infinite set"));
}
if let Some(r) = self.minus_small(x, y)? {
return Ok(r);
}
let mut out = Vec::new();
for e in self.work_elements(x)? {
if !self.member(e, y)? {
out.push(e);
}
}
Ok(self.heap.set_sorted(&out))
}
}
}
fn union_concrete(&mut self, x: Handle, y: Handle) -> Result<Option<Handle>, Error> {
if !x.is_compound() || !y.is_compound() {
return Ok(None);
}
let (left_view, right_view) = (self.heap.view(x), self.heap.view(y));
if left_view.kind != Kind::Set
|| right_view.kind != Kind::Set
|| left_view.is_lazy()
|| right_view.is_lazy()
{
return Ok(None);
}
let capacity = left_view
.data
.len()
.checked_add(right_view.data.len())
.ok_or_else(|| Error::unsupported("set union address space"))?;
let mut out = Vec::new();
out.try_reserve_exact(capacity)
.map_err(|_| Error::unsupported("set union allocation"))?;
let (mut i, mut j) = (0, 0);
while i < left_view.data.len() || j < right_view.data.len() {
self.heap.work_poll()?;
let value = match (left_view.data.get(i), right_view.data.get(j)) {
(Some(&left), Some(&right)) => match self.heap.cmp(left, right) {
std::cmp::Ordering::Less => {
i += 1;
left
}
std::cmp::Ordering::Greater => {
j += 1;
right
}
std::cmp::Ordering::Equal => {
i += 1;
j += 1;
left
}
},
(Some(&left), None) => {
i += 1;
left
}
(None, Some(&right)) => {
j += 1;
right
}
(None, None) => return Err(Error::internal("union cursor past both operands")),
};
out.push(value);
}
Ok(Some(self.heap.set_sorted(&out)))
}
fn minus_small(&mut self, x: Handle, y: Handle) -> Result<Option<Handle>, Error> {
if !x.is_compound() || !y.is_compound() {
return Ok(None);
}
let (vx, vy) = (self.heap.view(x), self.heap.view(y));
if vx.kind != Kind::Set || vy.kind != Kind::Set || vy.data.len() >= vx.data.len() {
return Ok(None);
}
let (xs, ys) = (vx.data, vy.data);
let mut drop = Vec::with_capacity(ys.len());
for &z in ys {
if let Ok(i) = xs.binary_search_by(|&e| self.heap.cmp(e, z)) {
drop.push(i);
}
}
drop.sort_unstable();
let mut out = Vec::with_capacity(xs.len() - drop.len());
for (i, &e) in xs.iter().enumerate() {
if drop.binary_search(&i).is_err() {
compare::miss(&self.heap, e, ys)?;
out.push(e);
}
}
Ok(Some(self.heap.set_sorted(&out)))
}
fn filter(
&mut self,
code: &Code,
bind: &Bind,
pred: P,
subset: Option<P>,
) -> Result<Handle, Error> {
if let Some(mut cur) = self.subset_cursor(code, subset)? {
let mut out = Vec::new();
while let Some(e) = self.work_next(&mut cur)? {
self.charge(1)?;
out.push(e);
}
return Ok(self.heap.set_sorted(&out));
}
let dom = self.eval(code, bind.domain)?;
let mut cur = self.work_cursor(dom)?;
let mut out = Vec::new();
loop {
let before = self.heap.mark();
let Some(e) = self.work_next(&mut cur)? else {
break;
};
self.charge(1)?;
let after = self.heap.mark();
let forced = self.thunk_mark();
self.bind_one(bind, e)?;
let keep = self.eval_bool(code, pred)?;
if self.thunks_released(forced) {
if keep {
self.heap.rollback(after);
} else {
self.heap.rollback(before);
}
}
if keep {
out.push(e);
}
}
Ok(self.heap.set_sorted(&out))
}
pub(crate) fn subset_cursor(
&mut self,
code: &Code,
subset: Option<P>,
) -> Result<Option<Cursor>, Error> {
let Some(set) = subset else {
return Ok(None);
};
let before = self.heap.mark();
let forced = self.thunk_mark();
match self.eval_norm(code, set) {
Ok(f) => {
let powerset = self.heap.symbolic(Kind::Subset, 0, &[f]);
self.work_cursor(powerset).map(Some)
}
Err(e) if e.kind() == crate::ErrorKind::Eval => {
if self.thunks_released(forced) {
self.heap.rollback(before);
}
Ok(None)
}
Err(e) => Err(e),
}
}
pub(crate) fn bind_one(&mut self, bind: &Bind, e: Handle) -> Result<(), Error> {
if bind.tuple {
let v = self.heap.view(e);
if v.kind != Kind::IntFcn || v.lo != 1 || v.data.len() != bind.slots.len() {
return Err(eval_err("a tuple pattern does not match the element"));
}
let parts = v.data.to_vec();
for (&s, p) in bind.slots.iter().zip(parts) {
self.set_slot(s, p);
}
} else if let Some(&s) = bind.slots.first() {
self.set_slot(s, e);
}
Ok(())
}
pub(crate) fn units(
&mut self,
code: &Code,
binds: &[Bind],
) -> Result<Vec<(Unit, Vec<Handle>)>, Error> {
let mut out = Vec::new();
for (bi, b) in binds.iter().enumerate() {
let d = match code.nodes.get(b.domain as usize) {
Some(Node::Const(h)) if self.fuel == u64::MAX => {
self.heap.enumerate_constant(*h)?
}
_ => {
let d = self.eval(code, b.domain)?;
self.work_norm(d)?
}
};
let elems = self.work_elements(d)?;
if b.tuple {
out.push((
Unit {
bind: bi,
var: None,
},
elems,
));
} else {
for vi in 0..b.slots.len() {
self.charge(elems.len() + 1)?;
out.push((
Unit {
bind: bi,
var: Some(vi),
},
elems.clone(),
));
}
}
}
Ok(out)
}
pub(crate) fn bind_unit(&mut self, binds: &[Bind], u: Unit, e: Handle) -> Result<(), Error> {
let b = &binds[u.bind];
match u.var {
Some(vi) => {
self.set_slot(b.slots[vi], e);
Ok(())
}
None => self.bind_one(b, e),
}
}
pub(crate) fn for_each_binding(
&mut self,
code: &Code,
binds: &[Bind],
f: &mut dyn FnMut(&mut Self) -> Result<bool, Error>,
) -> Result<bool, Error> {
if self.fuel != u64::MAX {
return self.binding_stream(code, binds, f);
}
let units = self.units(code, binds)?;
if units.iter().any(|(_, e)| e.is_empty()) {
return Ok(true);
}
let mut idx = vec![0usize; units.len()];
loop {
self.charge(1)?;
for (k, (u, elems)) in units.iter().enumerate() {
self.bind_unit(binds, *u, elems[idx[k]])?;
}
if !f(self)? {
return Ok(false);
}
let mut k = 0;
loop {
if k == units.len() {
return Ok(true);
}
idx[k] += 1;
if idx[k] < units[k].1.len() {
break;
}
idx[k] = 0;
k += 1;
}
}
}
fn quant(
&mut self,
code: &Code,
kind: Quant,
binds: &[Bind],
body: P,
) -> Result<Handle, Error> {
match kind {
Quant::Exists => {
let mut found = false;
self.for_each_binding(code, binds, &mut |m: &mut Self| {
if m.eval_bool(code, body)? {
found = true;
return Ok(false);
}
Ok(true)
})?;
Ok(Handle::bool(found))
}
Quant::Forall => {
let all = self
.for_each_binding(code, binds, &mut |m: &mut Self| m.eval_bool(code, body))?;
Ok(Handle::bool(all))
}
Quant::Choose => {
if binds.len() != 1 || (!binds[0].tuple && binds[0].slots.len() != 1) {
return Err(Error::unsupported("CHOOSE with several bound variables"));
}
let d = self.eval(code, binds[0].domain)?;
let mut cur = self.work_cursor(d)?;
loop {
let before = self.heap.mark();
let Some(e) = self.work_next(&mut cur)? else {
break;
};
self.charge(1)?;
let forced = self.thunk_mark();
self.bind_one(&binds[0], e)?;
if self.eval_bool(code, body)? {
return Ok(e);
}
if self.thunks_released(forced) {
self.heap.rollback(before);
}
}
Err(general(
"Attempted to compute the value of an expression of form\nCHOOSE x \\in S: P, but no element of S satisfied P.",
))
}
}
}
fn fcn_cons(&mut self, code: &Code, binds: &[Bind], body: P) -> Result<Handle, Error> {
let units = self.units(code, binds)?;
if units.len() == 1 {
let (u, keys) = units
.into_iter()
.next()
.unwrap_or((Unit { bind: 0, var: None }, Vec::new()));
self.charge(keys.len())?;
let mut vals = Vec::with_capacity(keys.len());
for &k in &keys {
self.bind_unit(binds, u, k)?;
vals.push(self.eval_component(code, body)?);
}
return Ok(self.heap.fcn_sorted(&keys, &vals));
}
if units.iter().any(|(u, _)| u.var.is_none()) {
return Err(Error::unsupported(
"a function constructor mixing tuple patterns and several bounds",
));
}
let mut keys = Vec::new();
let mut vals = Vec::new();
if units.iter().any(|(_, e)| e.is_empty()) {
return Ok(self.heap.fcn_sorted(&[], &[]));
}
let mut idx = vec![0usize; units.len()];
'outer: loop {
self.charge(1)?;
let comps: Vec<Handle> = idx.iter().zip(&units).map(|(&i, (_, e))| e[i]).collect();
for (k, (u, _)) in units.iter().enumerate() {
self.bind_unit(binds, *u, comps[k])?;
}
keys.push(self.heap.tuple(&comps));
vals.push(self.eval_component(code, body)?);
let mut k = units.len();
loop {
if k == 0 {
break 'outer;
}
k -= 1;
idx[k] += 1;
if idx[k] < units[k].1.len() {
break;
}
idx[k] = 0;
}
}
Ok(self.heap.fcn_sorted(&keys, &vals))
}
pub(crate) fn fcn_index(&self, f: Handle, key: Handle) -> Result<Option<usize>, Error> {
if !f.is_compound() {
return Err(eval_err("application of a value that is not a function"));
}
let v = self.heap.view(f);
match v.kind {
Kind::IntFcn => Ok(key.as_int().and_then(|k| {
let i = k.checked_sub(v.lo)?;
usize::try_from(i).ok().filter(|&i| i < v.data.len())
})),
Kind::Fcn => {
let keys = v.keys();
if key.as_str_id().is_some() || keys.len() <= 8 {
Ok(keys.iter().position(|&k| self.heap.eq(k, key)))
} else if let Some(i) = self.grid_index(keys, key) {
Ok(Some(i))
} else {
Ok(keys.binary_search_by(|&k| self.heap.cmp(k, key)).ok())
}
}
_ => Err(eval_err("application of a set as a function")),
}
}
fn grid_index(&self, keys: &[Handle], key: Handle) -> Option<usize> {
let (row, col) = self.int_pair(key)?;
let (l1, l2) = self.int_pair(*keys.first()?)?;
let (h1, h2) = self.int_pair(*keys.last()?)?;
let rows = usize::try_from(h1.checked_sub(l1)?.checked_add(1)?).ok()?;
let width = usize::try_from(h2.checked_sub(l2)?.checked_add(1)?).ok()?;
if rows.checked_mul(width)? != keys.len()
|| !(l1..=h1).contains(&row)
|| !(l2..=h2).contains(&col)
{
return None;
}
let at = usize::try_from(row - l1).ok()? * width + usize::try_from(col - l2).ok()?;
let k = *keys.get(at)?;
self.heap.eq(k, key).then_some(at)
}
fn int_pair(&self, h: Handle) -> Option<(i64, i64)> {
if !h.is_compound() {
return None;
}
let v = self.heap.view(h);
match (v.kind, v.lo, v.data) {
(Kind::IntFcn, 1, &[a, b]) => Some((a.as_int()?, b.as_int()?)),
_ => None,
}
}
pub fn apply(&mut self, f: Handle, a: Handle) -> Result<Handle, Error> {
if let Some(i) = self.fcn_index(f, a)? {
return Ok(self.heap.view(f).values()[i]);
}
let msg = "Attempted to apply function to an argument not in its domain";
let v = self.heap.view(f);
match v.kind {
Kind::Fcn => {
compare::miss(&self.heap, a, v.keys())?;
Err(general(msg))
}
Kind::IntFcn if a.as_int().is_some() => Err(general(msg)),
_ => Err(eval_err(msg)),
}
}
fn select(&mut self, r: Handle, field: Handle) -> Result<Handle, Error> {
if !r.is_compound() {
return Err(eval_err("field selection on a value that is not a record"));
}
let v = self.heap.view(r);
if v.kind == Kind::Fcn
&& let Some(i) = v.keys().iter().position(|&k| k == field)
{
return Ok(v.values()[i]);
}
Err(eval_err(
"Attempted to access a record field that does not exist",
))
}
fn domain(&mut self, f: Handle) -> Result<Handle, Error> {
if !f.is_compound() {
return Err(eval_err("DOMAIN of a value that is not a function"));
}
let len = self.heap.view(f).len();
self.charge(len.saturating_mul(2))?;
let v = self.heap.view(f);
match v.kind {
#[allow(clippy::cast_possible_wrap, reason = "domains fit in i64")]
Kind::IntFcn => {
let (lo, n) = (v.lo, v.data.len() as i64);
if n == 0 {
return Ok(self.heap.empty_set());
}
let mut out = Vec::with_capacity(v.data.len());
for k in lo..lo + n {
out.push(mk_int(k)?);
}
Ok(self.heap.set_sorted(&out))
}
Kind::Fcn => {
let keys = v.keys().to_vec();
Ok(self.heap.set_sorted(&keys))
}
_ => Err(eval_err("DOMAIN of a set")),
}
}
fn except(
&mut self,
code: &Code,
f: Handle,
u: &Update,
depth: usize,
) -> Result<Handle, Error> {
let Some(&step) = u.path.get(depth) else {
return Err(Error::internal("EXCEPT path out of range"));
};
let key = self.eval_norm(code, step)?;
if !f.is_compound() || !self.heap.view(f).kind.is_fcn() {
return Err(eval_err("EXCEPT on a value that is not a function"));
}
self.charge(self.heap.view(f).len())?;
let Some(i) = self.fcn_index(f, key)? else {
let v = self.heap.view(f);
if v.kind == Kind::IntFcn {
if key.as_int().is_none() && !v.data.is_empty() {
return Err(eval_err(
"Attempted to apply EXCEPT to a tuple at a non-integral index",
));
}
} else {
compare::miss(&self.heap, key, v.keys())?;
}
if self.refuse_unrecorded_warnings {
return Err(Error::unsupported(
"an EXCEPT key outside the function's domain, where the reference prints warning 2144",
));
}
return Ok(f);
};
let old = self.heap.view(f).values()[i];
let new = if depth + 1 == u.path.len() {
self.set_slot(u.at, old);
self.eval_component(code, u.value)?
} else {
self.except(code, old, u, depth + 1)?
};
if new == old {
return Ok(f);
}
self.charge(self.heap.view(f).data.len())?;
Ok(self.heap.fcn_with(f, i, new))
}
fn seq_vals(&mut self, s: Handle) -> Result<Vec<Handle>, Error> {
if !s.is_compound() {
return Err(eval_err("expected a sequence"));
}
let v = self.heap.view(s);
if v.kind != Kind::IntFcn || v.lo != 1 {
return Err(eval_err("expected a sequence"));
}
let len = v.data.len();
self.charge(len)?;
Ok(self.heap.view(s).data.to_vec())
}
fn bag(&mut self, op: StdFn, args: &[Handle]) -> Result<Handle, Error> {
let arg = |i: usize| {
args.get(i)
.copied()
.ok_or_else(|| Error::internal("missing argument"))
};
match op {
StdFn::EmptyBag => Ok(self.heap.fcn_sorted(&[], &[])),
StdFn::SetToBag => {
let set = arg(0)?;
if !set.is_compound()
|| matches!(self.heap.view(set).kind, Kind::Fcn | Kind::IntFcn)
{
return Err(eval_err(
"The argument of SetToBag should be a finite set, but instead it is not",
));
}
let keys = self.work_elements(set)?;
let one = mk_int(1)?;
let ones = vec![one; keys.len()];
Ok(self.heap.fcn_sorted(&keys, &ones))
}
StdFn::BagToSet => {
let bag = arg(0)?;
if !bag.is_compound()
|| !matches!(self.heap.view(bag).kind, Kind::Fcn | Kind::IntFcn)
{
return Err(eval_err(
"The argument of BagToSet should be a function with a finite domain",
));
}
self.domain(bag)
}
StdFn::BagIn | StdFn::CopiesIn => {
let (elem, bag) = (arg(0)?, arg(1)?);
if !bag.is_compound()
|| !matches!(self.heap.view(bag).kind, Kind::Fcn | Kind::IntFcn)
{
return Err(eval_err("BagIn or CopiesIn of a value that is not a bag"));
}
let dom = self.domain(bag)?;
if !self.member(elem, dom)? {
return Ok(if op == StdFn::BagIn {
Handle::bool(false)
} else {
mk_int(0)?
});
}
let count = self.apply(bag, elem)?;
let n = count
.as_int()
.ok_or_else(|| eval_err("The second argument of BagIn should be a bag"))?;
Ok(if op == StdFn::BagIn {
Handle::bool(n > 0)
} else {
count
})
}
_ => Err(Error::internal("not a Bags operator")),
}
}
fn len(&mut self, s: Handle) -> Result<Handle, Error> {
if let Some(id) = s.as_str_id() {
let text = self
.heap
.store()
.strings()
.text(id)
.ok_or_else(|| Error::internal("unknown string"))?;
self.charge(text.len())?;
return mk_int(i64::try_from(text.encode_utf16().count()).unwrap_or(i64::MAX));
}
if !s.is_compound() {
return Err(one_arg("Len", "sequence"));
}
let v = self.heap.view(s);
if v.kind != Kind::IntFcn || v.lo != 1 {
return Err(one_arg("Len", "sequence"));
}
mk_int(i64::try_from(v.data.len()).unwrap_or(i64::MAX))
}
fn std_arg(&mut self, code: &Code, f: StdFn, index: usize, x: P) -> Result<Handle, Error> {
let value = if matches!(f, StdFn::IsFiniteSet | StdFn::Cardinality | StdFn::Seq) {
self.eval(code, x)?
} else {
self.eval_component(code, x)?
};
let product = self.heap.kind(value) == Some(Kind::Product);
if matches!(f, StdFn::Seq | StdFn::IsFiniteSet)
|| (f == StdFn::Append && index == 1)
|| (product && matches!(f, StdFn::Cardinality | StdFn::IsFiniteSet | StdFn::Seq))
{
Ok(value)
} else {
self.work_norm(value)
}
}
fn std(&mut self, code: &Code, f: StdFn, args: &[P]) -> Result<Handle, Error> {
let mut a = Vec::with_capacity(args.len());
for (index, &x) in args.iter().enumerate() {
a.push(self.std_arg(code, f, index, x)?);
}
let arg = |i: usize| {
a.get(i)
.copied()
.ok_or_else(|| Error::internal("missing argument"))
};
match f {
StdFn::Len => self.len(arg(0)?),
StdFn::Head => {
let vals = self.seq_vals(arg(0)?)?;
vals.first()
.copied()
.ok_or_else(|| eval_exc(2184, "Attempted to apply Head to the empty sequence."))
}
StdFn::Tail => {
let vals = self.seq_vals(arg(0)?)?;
if vals.is_empty() {
return Err(eval_exc(
2184,
"Attempted to apply Tail to the empty sequence.",
));
}
Ok(self.heap.tuple(&vals[1..]))
}
StdFn::Append => {
let mut vals = self.seq_vals(arg(0)?)?;
vals.push(arg(1)?);
Ok(self.heap.tuple(&vals))
}
StdFn::Concat => {
let mut vals = self.seq_vals(arg(0)?)?;
vals.extend(self.seq_vals(arg(1)?)?);
Ok(self.heap.tuple(&vals))
}
StdFn::SubSeq => {
let vals = self.seq_vals(arg(0)?)?;
let m = int_of(arg(1)?)?;
let n = int_of(arg(2)?)?;
if m > n {
return Ok(self.heap.tuple(&[]));
}
let len = i64::try_from(vals.len()).unwrap_or(i64::MAX);
if m < 1 || n > len {
return Err(eval_err("SubSeq indices out of range"));
}
#[allow(
clippy::cast_sign_loss,
clippy::cast_possible_truncation,
reason = "checked range"
)]
Ok(self.heap.tuple(&vals[(m - 1) as usize..n as usize]))
}
StdFn::Cardinality => {
let s = arg(0)?;
if self.heap.kind(s) == Some(Kind::Set) {
compare::require_materialized(&self.heap, &[s])?;
}
if self.heap.kind(s) == Some(Kind::Product) {
return self.product_cardinality(s);
}
let kind = self.heap.kind(s);
match kind {
None | Some(Kind::IntFcn | Kind::Fcn | Kind::Nat | Kind::Int) => {
return Err(cardinality_error());
}
Some(Kind::SeqSet) => {
return Err(Error::unsupported("Cardinality of Seq(S) (M1 core)"));
}
Some(_) if !self.heap.is_finite(s) => return Err(cardinality_error()),
Some(_) => {}
}
let n = self.work_cardinality(s)?;
mk_int(i64::try_from(n).unwrap_or(i64::MAX))
}
StdFn::Seq => {
let s = arg(0)?;
Ok(self.heap.symbolic(Kind::SeqSet, 0, &[s]))
}
StdFn::IsFiniteSet => self.symbolic_finiteness(arg(0)?).map(Handle::bool),
StdFn::EmptyBag
| StdFn::SetToBag
| StdFn::BagToSet
| StdFn::BagIn
| StdFn::CopiesIn => self.bag(f, &a),
}
}
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct Unit {
pub(crate) bind: usize,
pub(crate) var: Option<usize>,
}
const fn int_op(op: Arith) -> IntOp {
match op {
Arith::Add => IntOp::Add,
Arith::Sub => IntOp::Sub,
Arith::Mul => IntOp::Mul,
Arith::Div => IntOp::Div,
Arith::DivNaturals => IntOp::DivNaturals,
Arith::Mod => IntOp::Mod,
Arith::Pow => IntOp::Pow,
}
}
fn fast_arith(op: Arith, x: i64, y: i64, mode: IntMode) -> Option<Handle> {
let r = match op {
Arith::Add => x.checked_add(y)?,
Arith::Sub => x.checked_sub(y)?,
Arith::Mul => x.checked_mul(y)?,
Arith::Div | Arith::DivNaturals if y > 0 && (mode == IntMode::Big || x >= 0) => {
x.div_euclid(y)
}
Arith::Mod if y > 0 => x.rem_euclid(y),
_ => return None,
};
if mode == IntMode::Tlc && i32::try_from(r).is_err() {
return None;
}
Handle::int(r)
}
#[cfg(test)]
#[path = "eval_union_tests.rs"]
mod union_tests;
#[cfg(test)]
mod tests {
#![allow(clippy::unwrap_used, reason = "tests")]
use super::*;
use crate::TlcClass;
#[test]
fn candidate_site_copies_stay_within_the_memo_cap() {
use crate::plan::{Code, MemoSite};
let cap = 64 << 10;
let store = Arc::new(Store::new(true));
let opts = Opts {
memo_cap: cap,
..Opts::default()
};
let mut m = Machine::new(Arc::clone(&store), 1, opts, Memo::new(&[1]));
let code = Code {
nodes: vec![
Node::Primed(0),
Node::Tuple(vec![0, 0].into()),
Node::Memo { site: 0, body: 1 },
],
sites: vec![MemoSite {
name: "F (Primed, action)".into(),
vars: vec![].into(),
slots: vec![].into(),
primed: vec![0].into(),
step: true,
candidate: true,
}],
..Code::default()
};
let before = store.stats().nodes;
let candidates: i64 = 20_000;
for i in 0..candidates {
let items: Vec<Handle> = (0..6).map(|k| Handle::int(i * 8 + k).unwrap()).collect();
let x = m.heap.tuple(&items);
m.s1[0] = x;
let expected = m.heap.tuple(&[x, x]);
for _ in 0..4 {
let r = m.eval(&code, 2).unwrap();
assert!(
compare::equals(&m.heap, r, expected).unwrap(),
"candidate {i}"
);
}
m.s1[0] = Handle::EMPTY;
m.heap.reset();
}
let added = store.stats().nodes - before;
assert!(
added < 2 * candidates.unsigned_abs() / 4,
"{added} persistent nodes"
);
assert!(!m.memo.may_keep());
assert!(m.memo.stats()[0].off);
assert!(m.memo.stats()[0].hits > 0);
}
#[test]
fn a_transient_bound_stops_an_evaluation_by_name() {
let mut m = Machine::new(
Arc::new(Store::with_semantics(true, crate::Semantics::default())),
0,
Opts::default(),
Memo::new(&[]),
);
let one = Handle::int(1).unwrap();
assert_eq!(m.charge(1), Ok(()));
m.set_transient_bound(4096);
while m.heap.arena.footprint() <= 4096 {
m.heap.tuple(&[one, one, one, one]);
}
let error = m.charge(1).unwrap_err();
assert_eq!(error.kind(), crate::ErrorKind::Unsupported);
assert!(error.message().contains("start-up evaluation memory bound"));
m.set_transient_bound(usize::MAX);
assert_eq!(m.charge(1), Ok(()));
m.heap.reset();
m.heap.arena.release();
assert_eq!(m.heap.arena.footprint(), 0);
}
#[test]
fn sequences_keep_the_original_product_range_and_its_member_demand() {
for tlc in [false, true] {
let semantics = if tlc {
crate::Semantics::tlc()
} else {
crate::Semantics::default()
};
let mut m = Machine::new(
Arc::new(Store::with_semantics(true, semantics)),
1,
Opts::default(),
Memo::new(&[]),
);
let zero = Handle::int(0).unwrap();
let empty = m.heap.interval(0, -1);
let product = m.heap.symbolic(Kind::Product, 0, &[empty, zero]);
let code = Code {
nodes: vec![Node::Const(product), Node::Std(StdFn::Seq, vec![0].into())],
..Code::default()
};
let sequences = m.eval(&code, 1).unwrap();
assert_eq!(m.heap.view(sequences).kind, Kind::SeqSet);
assert_eq!(m.heap.view(sequences).data, &[product]);
assert_eq!(m.heap.view(product).data, &[empty, zero]);
let empty_sequence = m.heap.tuple(&[]);
assert_eq!(m.member(empty_sequence, sequences), Ok(true));
let scalar_sequence = m.heap.tuple(&[zero]);
let error = m.member(scalar_sequence, sequences).unwrap_err();
assert_eq!(error.kind(), crate::ErrorKind::Eval);
assert!(error.message().contains("not a function"));
assert_eq!(m.heap.view(sequences).data, &[product]);
let mut values = vec![zero];
let nonempty = m.heap.set_from(&mut values);
let malformed = m.heap.symbolic(Kind::Product, 0, &[nonempty, zero]);
let code = Code {
nodes: vec![
Node::Const(malformed),
Node::Std(StdFn::Seq, vec![0].into()),
],
..Code::default()
};
let sequences = m.eval(&code, 1).unwrap();
assert_eq!(m.member(empty_sequence, sequences), Ok(true));
let element = m.heap.tuple(&[zero, zero]);
let nonempty_sequence = m.heap.tuple(&[element]);
let error = m.member(nonempty_sequence, sequences).unwrap_err();
assert_eq!(error.kind(), crate::ErrorKind::Eval);
assert!(error.message().contains("not a set"));
assert_eq!(m.heap.view(sequences).data, &[malformed]);
}
}
#[test]
fn public_cap_shrink_and_memo_move_cannot_add_over_budget_certificates() {
let one = Handle::int(1).unwrap();
let two = Handle::int(2).unwrap();
for warm_first in [false, true] {
let store = Arc::new(Store::with_semantics(true, crate::Semantics::tlc()));
let mut m = Machine::new(
store.clone(),
0,
Opts {
memo_cap: 2048,
..Opts::default()
},
Memo::new(&[]),
);
let vertex = m.heap.tuple(&[one]);
let set = m.heap.set_from(&mut vec![vertex]);
let set = m.heap.intern_exact(set).unwrap();
let query = m.heap.tuple(&[two]);
if warm_first {
assert_eq!(m.member(query, set), Ok(false));
assert_eq!(m.memo.bytes(), 128);
assert_eq!(Arc::weak_count(&store), 1);
}
m.memo.set_cap(64);
assert_eq!(m.memo.bytes(), 0);
assert_eq!(Arc::weak_count(&store), 0, "release the certificate owner");
let expected = compare::miss(&m.heap, query, m.heap.view(set).data).map(|()| false);
assert_eq!(m.member(query, set), expected);
assert!(m.memo.bytes() <= 64);
assert!(!m.memo.members_active());
let memo = std::mem::take(&mut m.memo);
let mut moved = Machine::new(
store,
0,
Opts {
memo_cap: 64,
..Opts::default()
},
memo,
);
let query = moved.heap.tuple(&[two]);
assert_eq!(moved.member(query, set), expected);
assert!(moved.memo.bytes() <= 64);
assert!(!moved.heap.poisoned());
}
}
#[test]
fn prepopulated_public_memo_keeps_membership_allocation_within_its_cap() {
let one = Handle::int(1).unwrap();
let two = Handle::int(2).unwrap();
for cap in [2048, 2079, 2112, 4096, 1 << 20, crate::memo::DEFAULT_CAP] {
for (semantics, memo_enabled) in [
(crate::Semantics::tlc(), true),
(crate::Semantics::default(), true),
(crate::Semantics::tlc(), false),
] {
let mut memo = Memo::new(&[1]);
memo.set_cap(cap);
memo.put(0, &[one], two);
assert_eq!(memo.bytes(), 2048);
let body_bytes = memo.bytes();
let store = Arc::new(Store::with_semantics(true, semantics));
let opts = Opts {
memo_cap: cap,
memo: memo_enabled,
..Opts::default()
};
let mut m = Machine::new(store, 0, opts, memo);
let vertex = m.heap.tuple(&[one]);
let set = m.heap.set_from(&mut vec![vertex]);
let set = m.heap.intern_exact(set).unwrap();
let query = m.heap.tuple(&[two]);
assert_eq!(m.member(query, set), Ok(false));
assert!(m.memo.bytes() <= cap);
assert_eq!(m.memo.get(0, &[one]), Some(two), "keep the body result");
if cap == 2048 || cap == 2079 || !memo_enabled || !semantics.tlc_comparisons {
assert!(!m.memo.members_active());
assert_eq!(m.memo.bytes(), body_bytes);
} else {
assert!(m.memo.members_active());
assert!(m.memo.bytes() > body_bytes);
if cap == 2112 {
assert_eq!(m.memo.bytes(), 2112, "only 64 bytes remain");
}
}
if cap == 2048 {
m.memo.set_cap(64);
assert_eq!(m.memo.bytes(), body_bytes, "retain existing body storage");
assert_eq!(m.memo.get(0, &[one]), Some(two));
assert_eq!(m.member(query, set), Ok(false));
assert_eq!(m.memo.bytes(), body_bytes, "add no certificate bytes");
}
for i in 1..1000 {
m.memo.put(0, &[Handle::int(i).unwrap()], two);
assert!(m.memo.bytes() <= cap);
}
assert!(!m.heap.poisoned());
}
}
}
#[test]
fn public_heap_replacement_cannot_reuse_another_stores_membership_proof() {
fn values(heap: &mut Heap, name: &str) -> (Handle, Handle) {
let one = Handle::int(1).unwrap();
let model = Handle::model(heap.store().strings().intern(name).unwrap());
let witness = heap.tuple(&[one]);
let witness = heap.intern_exact(witness).unwrap();
let other = heap.tuple(&[model]);
let other = heap.intern_exact(other).unwrap();
let set = heap.set_from(&mut vec![witness, other]);
let set = heap.intern_exact(set).unwrap();
(set, witness)
}
for hashcons in [true, false] {
let store = Arc::new(Store::with_semantics(hashcons, crate::Semantics::tlc()));
let old_owner = Arc::downgrade(&store);
let mut m = Machine::new(store, 0, Opts::default(), Memo::new(&[]));
let (old_set, old_witness) = values(&mut m.heap, "u");
let two = Handle::int(2).unwrap();
let query = m.heap.tuple(&[two]);
assert_eq!(m.member(query, old_set), Ok(false));
assert!(m.memo.bytes() > 0);
let store = Arc::new(Store::with_semantics(hashcons, crate::Semantics::tlc()));
let mut replacement = Heap::new(store, false, false);
let (set, witness) = values(&mut replacement, "T_x");
assert_eq!(old_set, set, "complete set handles collide across stores");
assert_eq!(old_witness, witness, "witness handles also collide");
m.heap = replacement;
assert!(
old_owner.upgrade().is_none(),
"a certificate does not retain Store"
);
let query = m.heap.tuple(&[two]);
let expected = compare::miss(&m.heap, query, m.heap.view(set).data).map(|()| false);
assert!(expected.is_err(), "typed versus integer constraints refuse");
assert_eq!(m.member(query, set), expected, "warm equals the full miss");
assert_eq!(m.memo.bytes(), 0, "rebind drops the old entries");
m.memo.clear();
assert_eq!(m.member(query, set), expected, "cold equals the full miss");
assert!(!m.heap.poisoned());
}
}
#[test]
fn membership_certificates_respect_profiles_epochs_and_machine_stores() {
let one = Handle::int(1).unwrap();
let two = Handle::int(2).unwrap();
for hashcons in [false, true] {
let store = Arc::new(Store::with_semantics(hashcons, crate::Semantics::tlc()));
let opts = Opts {
memo_cap: 512,
..Opts::default()
};
let mut m = Machine::new(store.clone(), 0, opts, Memo::new(&[]));
let u = Handle::model(store.strings().intern("u").unwrap());
let genesis = m.heap.tuple(&[]);
let vertex = m.heap.tuple(&[u, one]);
let set = m.heap.set_from(&mut vec![genesis, vertex]);
let set = m.heap.intern_exact(set).unwrap();
let query = m.heap.tuple(&[u, two]);
assert_eq!(m.member(query, set), Ok(false));
let vertex = m.memo.member_witness(m.heap.store(), set).unwrap();
assert_eq!(m.memo.bytes(), 32);
m.heap.reset();
let mark = m.heap.mark();
let query = m.heap.tuple(&[u, two]);
assert_eq!(m.member(query, set), Ok(false));
m.heap.rollback(mark);
let query = m.heap.tuple(&[u, two]);
assert_eq!(m.member(query, set), Ok(false));
let ephemeral = m.heap.set_from(&mut vec![query]);
assert_eq!(m.member(vertex, ephemeral), Ok(false));
assert_eq!(m.memo.member_witness(m.heap.store(), ephemeral), None);
assert!(!m.heap.poisoned());
let mut worker = Machine::new(store, 0, opts, Memo::new(&[]));
assert_eq!(worker.memo.member_witness(worker.heap.store(), set), None);
let query = worker.heap.tuple(&[u, two]);
assert_eq!(worker.member(query, set), Ok(false));
assert!(
worker
.memo
.member_witness(worker.heap.store(), set)
.is_some()
);
let reused = std::mem::take(&mut worker.memo);
let other = Arc::new(Store::with_semantics(hashcons, crate::Semantics::tlc()));
let mut worker = Machine::new(other, 0, opts, reused);
assert_eq!(worker.memo.member_witness(worker.heap.store(), set), None);
assert_eq!(worker.memo.bytes(), 0);
}
for (semantics, memo_enabled) in [
(crate::Semantics::default(), true),
(crate::Semantics::tlc(), false),
] {
let store = Arc::new(Store::with_semantics(true, semantics));
let mut m = Machine::new(
store,
0,
Opts {
memo: memo_enabled,
..Opts::default()
},
Memo::new(&[]),
);
assert!(!m.memo.members_active());
let vertex = m.heap.tuple(&[one]);
let set = m.heap.set_from(&mut vec![vertex]);
let set = m.heap.intern_exact(set).unwrap();
let query = m.heap.tuple(&[two]);
assert_eq!(m.member(query, set), Ok(false));
assert_eq!(m.memo.bytes(), 0);
}
}
#[test]
fn arithmetic_errors_carry_tlc_classes() {
let exc = |c| Some(TlcClass::eval_exception(c));
for mode in [crate::int::IntMode::Big, crate::int::IntMode::Tlc] {
let mut h =
crate::Heap::new(std::sync::Arc::new(crate::Store::default()), false, false);
h.set_int_mode(mode);
let n = |v| Handle::int(v).unwrap();
let mut class = |op, x, y| h.int_arith(op, n(x), n(y)).unwrap_err().tlc();
assert_eq!(class(IntOp::Div, 1, 0), exc(2179));
assert_eq!(class(IntOp::Mod, 1, 0), exc(2169));
assert_eq!(class(IntOp::Pow, 2, -1), exc(2169));
assert_eq!(class(IntOp::Pow, 0, 0), exc(2180));
}
let mut h = crate::Heap::new(std::sync::Arc::new(crate::Store::default()), false, false);
h.set_int_mode(crate::int::IntMode::Tlc);
let big = h
.int_arith(
IntOp::Mul,
Handle::int(1 << 20).unwrap(),
Handle::int(1 << 20).unwrap(),
)
.unwrap_err();
assert_eq!(big.tlc(), exc(2178));
}
}
#[cfg(test)]
mod recursive_call_bounds {
use super::*;
use std::sync::atomic::{AtomicUsize, Ordering};
#[derive(Debug)]
struct StopAfterOne(AtomicUsize);
impl WorkControl for StopAfterOne {
fn proceed(&self) -> bool {
self.0.fetch_add(1, Ordering::Relaxed) == 0
}
}
#[test]
fn recursive_calls_poll_work_and_restore_depth_and_frames_after_stops()
-> Result<(), Box<dyn std::error::Error>> {
let code = Code {
nodes: vec![Node::Call {
fun: 0,
args: Box::new([]),
}],
funs: vec![crate::plan::Fun {
name: "loop".into(),
params: 0,
frame: 0,
body: 0,
caps: Box::new([]),
}],
..Default::default()
};
let mut m = Machine::new(
Arc::new(Store::default()),
0,
Opts::default(),
Memo::default(),
);
let control = Arc::new(StopAfterOne(AtomicUsize::new(0)));
m.set_work_control(Some(control.clone()));
let stopped = m.eval(&code, 0).err().ok_or("expected cooperative stop")?;
assert_eq!(stopped.kind(), crate::ErrorKind::Stop);
assert_eq!(control.0.load(Ordering::Relaxed), 2);
assert_eq!(m.depth, 0);
assert_eq!(m.frame, Vec::<Handle>::new());
m.set_work_control(None);
let bounded = m.eval(&code, 0).err().ok_or("expected depth refusal")?;
assert_eq!(bounded.kind(), crate::ErrorKind::Unsupported);
assert!(bounded.message().contains("recursive-call depth limit"));
assert_eq!(m.depth, 0);
assert_eq!(m.frame, Vec::<Handle>::new());
Ok(())
}
}
#[cfg(test)]
mod thunk_rollback {
#![allow(clippy::unwrap_used, reason = "tests")]
use super::*;
fn code() -> Code {
Code {
nodes: vec![
Node::Var(0),
Node::Tuple(Box::new([0, 0])),
Node::Lazy { slot: 0, body: 1 },
],
..Default::default()
}
}
fn machine() -> Machine {
let mut m = Machine::new(
Arc::new(Store::default()),
1,
Opts::default(),
Memo::default(),
);
m.s0[0] = Handle::int(1).unwrap();
m
}
#[test]
fn a_thunk_forced_in_a_left_frame_releases_the_rollback() {
let code = code();
let mut m = machine();
let outer = m.enter(1);
let before = m.heap.mark();
let since = m.thunk_mark();
let inner = m.enter(1);
let v = m.eval(&code, 2).unwrap();
assert!(v.is_transient());
assert!(!m.thunks_released(since));
m.leave(inner);
assert!(m.thunks_released(since));
m.heap.rollback(before);
assert!(!m.heap.poisoned());
let w = m.eval(&code, 2).unwrap();
assert!(compare::equals(&m.heap, w, w).unwrap());
assert!(!m.heap.poisoned());
m.leave(outer);
}
#[test]
fn a_thunk_forced_in_a_live_frame_keeps_the_values_it_holds() {
let code = code();
let mut m = machine();
let outer = m.enter(1);
let since = m.thunk_mark();
let v = m.eval(&code, 2).unwrap();
let inner = m.enter(1);
m.leave(inner);
assert!(!m.thunks_released(since));
assert!(!m.thunks_released(0));
let later = m.thunk_mark();
assert!(m.thunks_released(later));
assert_eq!(m.eval(&code, 2).unwrap(), v);
assert!(!m.heap.poisoned());
m.leave(outer);
assert!(m.thunks_released(0));
}
#[test]
fn a_released_inner_scope_keeps_the_enclosing_scopes_live_slots() {
let code = code();
let mut m = machine();
let outer = m.enter(1);
let since = m.thunk_mark();
m.eval(&code, 2).unwrap();
let inner_since = m.thunk_mark();
let inner = m.enter(1);
m.eval(&code, 2).unwrap();
m.leave(inner);
assert!(m.thunks_released(inner_since));
assert!(!m.thunks_released(since));
m.leave(outer);
}
}
#[cfg(test)]
mod work_poll_bound {
use super::*;
use std::sync::atomic::{AtomicUsize, Ordering};
#[derive(Debug)]
struct Allow {
allow: usize,
polls: AtomicUsize,
}
impl WorkControl for Allow {
fn proceed(&self) -> bool {
self.polls.fetch_add(1, Ordering::Relaxed) < self.allow
}
}
fn machine(allow: usize) -> (Machine, Arc<Allow>) {
let mut m = Machine::new(
Arc::new(Store::default()),
0,
Opts::default(),
Memo::default(),
);
let control = Arc::new(Allow {
allow,
polls: AtomicUsize::new(0),
});
m.set_work_control(Some(control.clone()));
(m, control)
}
fn polls(control: &Allow) -> usize {
control.polls.load(Ordering::Relaxed)
}
#[test]
fn the_first_charge_after_installation_polls() {
let (mut m, control) = machine(0);
let error = m.charge(1).err();
assert!(error.is_some_and(|e| e.kind() == crate::ErrorKind::Stop));
assert_eq!(polls(&control), 1);
assert!(m.heap.work_interrupted());
}
#[test]
fn a_stop_is_seen_within_the_documented_unit_bound() {
let units = usize::try_from(WORK_POLL_UNITS).unwrap_or(usize::MAX);
for n in [0, 1, 3] {
let (mut m, control) = machine(1);
let mut charged = 0usize;
let mut calls = 0usize;
let stopped = loop {
let result = m.charge(n);
calls += 1;
if let Err(error) = result {
break error;
}
charged += n.max(1);
assert!(calls <= units + 1, "no stop within the bound (n={n})");
};
assert_eq!(stopped.kind(), crate::ErrorKind::Stop);
assert_eq!(polls(&control), 2);
assert!(charged < units + n.max(1), "n={n} charged={charged}");
assert!(calls <= units + 1, "n={n} calls={calls}");
for _ in 0..3 {
assert!(m.charge(1).is_err());
}
assert_eq!(polls(&control), 5);
}
}
#[test]
fn a_large_charge_polls_before_its_work() {
let (mut m, control) = machine(1);
assert_eq!(m.charge(1), Ok(()));
let big = usize::try_from(WORK_POLL_UNITS).unwrap_or(usize::MAX);
let error = m.charge(big).err();
assert!(error.is_some_and(|e| e.kind() == crate::ErrorKind::Stop));
assert_eq!(polls(&control), 2);
}
#[test]
fn bounded_fuel_and_transients_are_checked_on_every_charge_and_polled_on_the_bound() {
let units = usize::try_from(WORK_POLL_UNITS).unwrap_or(usize::MAX);
let (mut m, control) = machine(usize::MAX);
assert_eq!(m.charge(1), Ok(()));
m.set_fuel(10);
for spent in 1..=10 {
assert_eq!(m.charge(1), Ok(()));
assert_eq!(m.fuel, 10 - spent);
}
let error = m.charge(1).err();
assert!(error.is_some_and(|e| e.kind() == crate::ErrorKind::Unsupported));
assert_eq!(polls(&control), 1);
m.set_fuel(u64::MAX);
m.heap.tuple(&[Handle::TRUE]);
m.set_transient_bound(0);
let error = m.charge(1).err();
assert!(error.is_some_and(|e| e.kind() == crate::ErrorKind::Unsupported));
m.set_transient_bound(usize::MAX);
for _ in 13..units {
assert_eq!(m.charge(1), Ok(()));
}
assert_eq!(polls(&control), 1);
assert_eq!(m.charge(1), Ok(()));
assert_eq!(polls(&control), 2);
m.set_fuel(u64::MAX - 1);
for _ in 1..units {
assert_eq!(m.charge(1), Ok(()));
}
assert_eq!(polls(&control), 2);
assert_eq!(m.charge(1), Ok(()));
assert_eq!(polls(&control), 3);
}
#[test]
fn reinstalling_a_control_polls_at_once() {
let (mut m, control) = machine(usize::MAX);
assert_eq!(m.charge(1), Ok(()));
assert_eq!(polls(&control), 1);
let deny = Arc::new(Allow {
allow: 0,
polls: AtomicUsize::new(0),
});
m.set_work_control(Some(deny.clone()));
assert!(m.charge(1).is_err());
assert_eq!(polls(&deny), 1);
}
}
#[cfg(test)]
mod bounded_analysis_machine {
#![allow(clippy::unwrap_used, reason = "tests")]
use super::*;
use crate::plan::MemoSite;
fn memo_code(step: bool) -> Code {
Code {
nodes: vec![
Node::Const(Handle::int(7).unwrap()),
Node::Memo { site: 0, body: 0 },
],
sites: vec![MemoSite {
name: "site".into(),
vars: Box::new([0]),
slots: Box::new([]),
primed: Box::new([]),
step,
candidate: false,
}],
..Default::default()
}
}
fn machine(memo_on: bool, memo: Memo) -> Machine {
let opts = Opts {
memo: memo_on,
step_memo: memo_on,
..Opts::default()
};
let mut m = Machine::new(Arc::new(Store::default()), 1, opts, memo);
m.s0[0] = Handle::int(1).unwrap();
m
}
#[test]
fn memo_off_machines_evaluate_memo_bodies_without_reading_or_filling_a_site() {
let mut on = machine(true, Memo::new(&[1]));
assert_eq!(
on.eval(&memo_code(false), 1).unwrap(),
Handle::int(7).unwrap()
);
assert_eq!(on.memo.stats()[0].lookups, 1);
assert!(on.memo.bytes() > 0);
let mut off = machine(false, Memo::new(&[1]));
for _ in 0..2 {
assert_eq!(
off.eval(&memo_code(false), 1).unwrap(),
Handle::int(7).unwrap()
);
}
assert_eq!(off.memo.stats()[0].lookups, 0);
assert_eq!(off.memo.bytes(), 0);
let mut analysis = machine(false, Memo::default());
for step in [false, true] {
assert_eq!(
analysis.eval(&memo_code(step), 1).unwrap(),
Handle::int(7).unwrap()
);
}
assert_eq!(analysis.memo.stats(), Vec::new());
assert_eq!(analysis.memo.bytes(), 0);
}
#[test]
fn bounded_machines_precharge_big_powers_before_allocating() {
let pow = |x: i64, y: i64| Code {
nodes: vec![
Node::Const(Handle::int(x).unwrap()),
Node::Const(Handle::int(y).unwrap()),
Node::Arith(Arith::Pow, 0, 1),
],
..Default::default()
};
let mut m = machine(false, Memo::default());
m.set_fuel(1000);
let nodes = m.heap.arena().peak().0;
let error = m.eval(&pow(3, 100_000), 2).unwrap_err();
assert_eq!(error.kind(), crate::ErrorKind::Unsupported);
assert!(m.fuel_exhausted());
assert_eq!(m.heap.arena().peak().0, nodes, "no digits allocated");
m.set_fuel(1 << 20);
let big = m.eval(&pow(3, 100_000), 2).unwrap();
assert_eq!(
m.heap.big(big).unwrap(),
num_traits::Pow::pow(num_bigint::BigInt::from(3), 100_000_u32)
);
assert!(!m.fuel_exhausted());
m.set_fuel(4);
assert_eq!(m.eval(&pow(2, 10), 2).unwrap(), Handle::int(1024).unwrap());
m.heap.set_int_mode(crate::int::IntMode::Tlc);
m.set_fuel(4);
assert_eq!(m.eval(&pow(2, 10), 2).unwrap(), Handle::int(1024).unwrap());
}
}
#[cfg(test)]
mod same_vars {
#![allow(clippy::unwrap_used, reason = "tests")]
use super::*;
fn code() -> Code {
Code {
nodes: vec![
Node::Var(0),
Node::Var(1),
Node::Var(2),
Node::Tuple(Box::new([1, 2])),
Node::Tuple(Box::new([0, 3])),
Node::Lazy { slot: 0, body: 4 },
Node::Primed(0),
Node::Primed(1),
Node::Eq(5, 13),
Node::Primed(2),
Node::Tuple(Box::new([7, 9])),
Node::Tuple(Box::new([6, 10])),
Node::Lazy { slot: 1, body: 11 },
Node::Lazy { slot: 2, body: 12 },
Node::Const(Handle::TRUE),
Node::SameVars {
eq: 8,
leaves: Box::new([(0, 1), (1, 2), (2, 2)]),
thunks: Box::new([0, 1, 2]),
},
],
..Default::default()
}
}
fn values(m: &mut Machine) -> Vec<Handle> {
let one = Handle::int(1).unwrap();
let two = Handle::int(2).unwrap();
let text = m.heap.string("a").unwrap();
let set = m.heap.set_enum(&[one, two]);
let set = m.heap.intern(set).unwrap();
let other = m.heap.set_enum(&[one]);
let other = m.heap.intern(other).unwrap();
let fcn = m.heap.int_fcn(1, &[set, text]);
let fcn = m.heap.intern_exact(fcn).unwrap();
let interval = m.heap.interval(1, 2);
let interval = m.heap.intern_exact(interval).unwrap();
vec![one, two, text, set, other, fcn, interval, Handle::EMPTY]
}
fn agrees(semantics: crate::store::Semantics) {
let code = code();
let store = Arc::new(Store::with_semantics(true, semantics));
let mut m = Machine::new(store, 3, Opts::default(), Memo::default());
let values = values(&mut m);
let pick = |i: usize| values[i % values.len()];
let mut checked = 0;
for i in 0..values.len().pow(2) {
let (a, b) = (i % values.len(), i / values.len());
for row in [[a, a, b], [a, b, b], [b, a, a], [a, a, a]] {
let before: Vec<_> = row.iter().map(|&k| pick(k)).collect();
for after in [before.clone(), vec![pick(b), before[1], before[2]]] {
m.s0.copy_from_slice(&before);
m.s1.copy_from_slice(&after);
let frame = m.enter(3);
let eq = m.eval(&code, 8).map_err(|e| e.kind());
m.leave(frame);
let frame = m.enter(3);
let same = m.eval(&code, 15).map_err(|e| e.kind());
m.leave(frame);
assert_eq!(same, eq, "{before:?} {after:?}");
let proven: Vec<_> = before
.iter()
.chain(&after)
.copied()
.filter(|&h| m.heap.materialized_within(&[h], 4096, None))
.collect();
let keep = |row: &[Handle]| -> Vec<Handle> {
row.iter()
.map(|&h| {
if proven.contains(&h) {
h
} else {
Handle::EMPTY
}
})
.collect()
};
m.set_proven_materialized(&keep(&before), &keep(&after), []);
let frame = m.enter(3);
let reused = m.eval(&code, 15).map_err(|e| e.kind());
m.leave(frame);
m.set_proven_materialized(&[], &[], []);
assert_eq!(reused, eq, "{before:?} {after:?} with proofs");
checked += 1;
}
}
}
assert!(checked > 100);
assert!(!m.heap.poisoned());
}
#[test]
fn membership_reuses_only_recorded_proofs() {
let store = Arc::new(Store::default());
let mut m = Machine::new(store, 2, Opts::default(), Memo::default());
m.set_fuel(1 << 30);
let one = Handle::int(1).unwrap();
let two = Handle::int(2).unwrap();
let inner = m.heap.set_from(&mut vec![one, two]);
let inner = m.heap.unmarked_copy(inner);
let single = m.heap.set_from(&mut vec![one]);
let single = m.heap.unmarked_copy(single);
let outer = m.heap.set_from(&mut vec![inner, single]);
let outer = m.heap.unmarked_copy(outer);
let other = m.heap.set_from(&mut vec![two]);
let other = m.heap.unmarked_copy(other);
let interval = m.heap.interval(1, 2);
let interval = m.heap.intern_exact(interval).unwrap();
let lazy = m.heap.set_from(&mut vec![interval]);
let lazy = m.heap.unmarked_copy(lazy);
for h in [inner, single, outer, other] {
assert!(!m.heap.proved_concrete(h));
assert!(m.heap.materialized_within(&[h], 64, None));
}
assert!(!m.heap.materialized_within(&[lazy], 64, None));
let cases = [(inner, outer), (other, outer), (one, inner), (two, single)];
for (x, set) in cases {
m.set_proven_materialized(&[], &[], []);
let plain = m.member(x, set).map_err(|e| e.kind());
assert!(plain.is_ok(), "{x:?} {set:?} {plain:?}");
m.set_proven_materialized(&[x], &[set], []);
assert_eq!(m.member(x, set).map_err(|e| e.kind()), plain);
m.set_proven_materialized(&[], &[], [x, set]);
assert_eq!(m.member(x, set).map_err(|e| e.kind()), plain);
}
assert_eq!(m.member(inner, outer).ok(), Some(true));
assert_eq!(m.member(other, outer).ok(), Some(false));
assert_eq!(m.member(two, single).ok(), Some(false));
m.set_proven_materialized(&[], &[], []);
let refused = m.member(lazy, outer).map_err(|e| e.kind());
assert!(refused.is_err());
m.set_proven_materialized(&[outer], &[], []);
assert_eq!(m.member(lazy, outer).map_err(|e| e.kind()), refused);
m.set_proven_materialized(&[], &[], []);
assert!(!m.heap.poisoned());
}
#[test]
fn same_vars_agrees_with_the_tuple_equality_it_wraps() {
agrees(crate::store::Semantics::default());
agrees(crate::store::Semantics::tlc());
}
#[test]
fn a_forced_thunk_is_read_as_the_tuple_equality_reads_it() {
let code = code();
let mut m = Machine::new(
Arc::new(Store::default()),
3,
Opts::default(),
Memo::default(),
);
let one = Handle::int(1).unwrap();
let two = Handle::int(2).unwrap();
m.s0.copy_from_slice(&[one, one, one]);
m.s1.copy_from_slice(&[one, one, one]);
let frame = m.enter(3);
let stale = m.heap.tuple(&[two, two]);
m.set_slot(0, stale);
assert_eq!(m.eval(&code, 15).unwrap(), Handle::FALSE);
for slot in 0..3 {
m.set_slot(slot, Handle::EMPTY);
}
assert_eq!(m.eval(&code, 15).unwrap(), Handle::TRUE);
assert!((0..3).all(|slot| m.slot(slot).is_empty()));
m.s1[2] = two;
assert_eq!(m.eval(&code, 15).unwrap(), Handle::FALSE);
assert!((0..3).all(|slot| m.slot(slot).is_empty()));
m.leave(frame);
}
}