Skip to main content

dive_core/
eval.rs

1//! The interpreter for value nodes: a recursive
2//! `match` over the plan's node array, over one flat frame per activation.
3
4use std::sync::Arc;
5
6use crate::Error;
7use crate::compare;
8use crate::handle::Handle;
9use crate::heap::{Cursor, Heap};
10use crate::int::{IntMode, IntOp};
11use crate::memo::{MAX_KEY, Memo};
12use crate::node::Kind;
13use crate::opts::Opts;
14use crate::plan::{Arith, Bind, Cmp, Code, LibArg, Node, P, Quant, SetOp, StdFn, Update};
15use crate::store::Store;
16
17#[path = "eval_product.rs"]
18mod product;
19#[path = "eval_work.rs"]
20mod work;
21
22/// Conservative call nesting bound, including argument evaluation. Refuse
23/// before unbounded model recursion consumes the host interpreter's stack.
24const MAX_CALL_DEPTH: usize = 64;
25
26/// Charged units between polls of the installed [`WorkControl`]. Every
27/// charge counts at least one unit, so the checkpoint runs at least once per
28/// this many charges and before any charge that would carry the units since
29/// the last poll to this bound. The first charge after
30/// [`Machine::set_work_control`], and every charge after a refused poll,
31/// polls at once.
32pub const WORK_POLL_UNITS: u64 = 32;
33
34/// Evaluation counters.
35#[derive(Clone, Copy, Debug, Default)]
36pub struct EvalStats {
37    /// Thunks forced.
38    pub forced: u64,
39    /// Thunk reads answered from the cache.
40    pub cached: u64,
41    /// Forced thunks whose value is transient (an arena rollback must not
42    /// free it while its slot holds it).
43    pub transient_thunks: u64,
44}
45
46/// An optional cooperative work checkpoint. A false result only interrupts
47/// the machine; the caller must classify its own actual run authority.
48pub trait WorkControl: std::fmt::Debug + Send + Sync {
49    /// Whether evaluation may continue.
50    fn proceed(&self) -> bool;
51}
52
53/// One worker's evaluation state.
54#[derive(Debug)]
55pub struct Machine {
56    /// The value regions.
57    pub heap: Heap,
58    /// The frame stack.
59    pub frame: Vec<Handle>,
60    /// The base of the current frame.
61    pub base: usize,
62    /// The current state (`s0`).
63    pub s0: Vec<Handle>,
64    /// The successor buffer (`s1`); [`Handle::EMPTY`] is unassigned.
65    pub s1: Vec<Handle>,
66    /// Assigned variables in `s1`.
67    pub assigned: usize,
68    /// The strategy switches.
69    pub opts: Opts,
70    /// The memo tables.
71    pub memo: Memo,
72    /// Counters.
73    pub stats: EvalStats,
74    /// Whether the all-assigned shortcut runs for successors (TLC's
75    /// `TLCGlobals.warn`; on in both profiles).
76    pub warn: bool,
77    /// Warnings 2143 raised by the generator (`UNCHANGED` of a variable
78    /// already assigned another value), once per variable and site (an
79    /// `ExprId` index), in the order raised.
80    pub warnings: Vec<(u16, u32)>,
81    /// What `Print` and `PrintT` printed, one line each, in evaluation
82    /// order.
83    pub printed: Vec<String>,
84    output_limits: Option<(usize, usize)>,
85    output_used: (usize, usize),
86    output_failure: Option<&'static str>,
87    pub(crate) checker_access: CheckerAccess,
88    /// The random stream draws come from: the startup stream or the
89    /// expanded state's (`random.rs`); `None` outside a search.
90    pub draw: Option<Box<dyn crate::random::DrawStream>>,
91    /// How many draws were made, which the engine reads to refuse a draw
92    /// in a check.
93    pub draws: u64,
94    /// `TLCGet("level")`: 0 in `Init`, the expanded state's level in the
95    /// next-state relation and action checks, the checked state's level in
96    /// state checks (initial states are level 1). The engine sets it.
97    pub level: i64,
98    pub(crate) conts: Vec<crate::generate::ContNode>,
99    pub(crate) cvals: Vec<Handle>,
100    pub(crate) saved: Vec<Handle>,
101    scratch: Vec<Vec<Handle>>,
102    /// The absolute frame positions of thunk slots forced to a transient,
103    /// in forcing order ([`Machine::thunk_mark`]). A position at or past
104    /// the frame's length names a slot that has left the frame.
105    transient_slots: Vec<usize>,
106    depth: usize,
107    /// Loop iterations left before evaluation gives up. Unbounded at run
108    /// time; the compiler bounds it while folding constants, and an
109    /// isolated optional analysis machine bounds its own speculative work.
110    pub(crate) fuel: u64,
111    /// Whether a site where the dive-eval evaluator prints a warning that
112    /// Core does not record in [`Machine::warnings`] refuses instead
113    /// ([`Machine::set_refuse_unrecorded_warnings`]).
114    refuse_unrecorded_warnings: bool,
115    /// Persistent handles the caller proved materialized
116    /// ([`Machine::set_proven_materialized`]): the rows it loaded into
117    /// `s0` and `s1`, position for position, and others.
118    proven_s0: Vec<Handle>,
119    proven_s1: Vec<Handle>,
120    proven: Vec<Handle>,
121    work_control: Option<Arc<dyn WorkControl>>,
122    /// Charged units left before the next [`WorkControl`] poll, while fuel
123    /// and the transient bound are unbounded ([`Machine::charge`]).
124    work_countdown: u64,
125    /// The same countdown while either is bounded.
126    bounded_countdown: u64,
127    pub(crate) debugger: Option<Arc<dyn crate::debug::Observer>>,
128    /// Results of calls, kept only while the compiler evaluates start-up
129    /// constant definitions (see [`CallCache`]).
130    pub(crate) calls: Option<CallCache>,
131    /// The most transient bytes an evaluation may hold
132    /// ([`crate::compile::STARTUP_TRANSIENT_BYTES`] while the compiler
133    /// evaluates start-up constant definitions); unbounded otherwise.
134    pub(crate) transient_bound: usize,
135}
136
137/// What of a live checker `TLCGet`/`TLCSet` may read.
138#[derive(Debug, Clone, Copy, PartialEq, Eq)]
139pub(crate) enum CheckerAccess {
140    /// Registers and `TLCGet("level")` (model checking).
141    Full,
142    /// `TLCGet("level")` only, set by a finite mode's driver.
143    Level,
144    /// Nothing: a finite mode without a checker context.
145    Denied,
146}
147
148/// The results of the calls made while the compiler evaluates the pure
149/// constant definitions the binder left to the core, keyed by
150/// the function and the exact argument handles.
151///
152/// A start-up constant definition reads no state and applies no impure
153/// operator (`dive_model::bind_deferring_constants` checks it through every
154/// definition it reaches), so a call's result is a function of its
155/// arguments: captures are passed as arguments, and a frame starts empty.
156/// Equal handles are equal values while no transient they name has been
157/// freed, so the table is emptied whenever the arena's reset or rollback
158/// count changes; within one count a kept transient result is still live.
159#[derive(Debug, Default)]
160pub(crate) struct CallCache {
161    revision: (u64, u64),
162    results: std::collections::HashMap<Box<[u64]>, Handle>,
163    key: Vec<u64>,
164    /// Lookups answered from the table.
165    pub(crate) hits: u64,
166}
167
168/// The most results [`CallCache`] holds before it starts again.
169const CALL_CACHE_ENTRIES: usize = 1 << 16;
170
171fn eval_err(what: &str) -> Error {
172    Error::eval(what)
173}
174
175/// An `Assert.fail(EC.GENERAL, ...)` error the core raises exactly where
176/// TLC does. Messages that begin like TLC's keep TLC's beginning, which the
177/// engine's replay rule reads (`dive_runtime::classify`).
178fn general(what: &str) -> Error {
179    Error::eval_class(crate::TlcClass::GENERAL, what)
180}
181
182/// An `EvalException` of TLC class `code`.
183fn eval_exc(code: u32, what: &str) -> Error {
184    Error::eval_class(crate::TlcClass::eval_exception(code), what)
185}
186
187/// `EC.TLC_MODULE_COMPUTING_CARDINALITY`: `Cardinality` of a value that is
188/// not an enumerable set (`FiniteSets.Cardinality`; a function, record or
189/// tuple is not `Enumerable` there either).
190pub(crate) fn cardinality_error() -> Error {
191    eval_exc(2181, "Attempted to compute cardinality of the value")
192}
193
194/// `EC.TLC_MODULE_ONE_ARGUMENT_ERROR`, as `SequencesHelper` raises it.
195fn one_arg(op: &str, what: &str) -> Error {
196    eval_exc(
197        2283,
198        &format!("The argument of {op} should be a {what}, but instead it is not"),
199    )
200}
201
202/// An error raised inside `Node::Spec`: an evaluation error TLC might not
203/// raise, because TLC would not have evaluated the expression yet.
204fn speculative(e: Error) -> Error {
205    if e.kind() == crate::ErrorKind::Eval {
206        Error::unsupported(format!(
207            "an evaluation error in an expression TLC evaluates lazily, where it may not fail: {}",
208            e.message()
209        ))
210    } else {
211        e
212    }
213}
214
215fn int_of(h: Handle) -> Result<i64, Error> {
216    h.as_int().ok_or_else(|| eval_err("expected an integer"))
217}
218
219fn bool_of(h: Handle) -> Result<bool, Error> {
220    h.as_bool().ok_or_else(|| eval_err("expected a boolean"))
221}
222
223fn mk_int(v: i64) -> Result<Handle, Error> {
224    Handle::int(v).ok_or_else(|| Error::unsupported("integer outside the M0 core's 61-bit range"))
225}
226
227impl Machine {
228    /// A machine over `store` for states of `nvars` variables.
229    #[must_use]
230    pub fn new(store: Arc<Store>, nvars: usize, opts: Opts, mut memo: Memo) -> Self {
231        memo.set_cap(opts.memo_cap);
232        memo.reserve_members(opts.memo && store.semantics().tlc_comparisons);
233        memo.reserve_member_index(opts.member_index && !store.semantics().tlc_comparisons);
234        Self {
235            heap: Heap::new(store, !opts.arena, !opts.delta_hash),
236            frame: Vec::new(),
237            base: 0,
238            s0: vec![Handle::EMPTY; nvars],
239            s1: vec![Handle::EMPTY; nvars],
240            assigned: 0,
241            opts,
242            memo,
243            stats: EvalStats::default(),
244            warn: true,
245            warnings: Vec::new(),
246            printed: Vec::new(),
247            output_limits: None,
248            output_used: (0, 0),
249            output_failure: None,
250            checker_access: CheckerAccess::Full,
251            draw: None,
252            draws: 0,
253            level: 0,
254            conts: Vec::new(),
255            cvals: Vec::new(),
256            saved: Vec::new(),
257            scratch: Vec::new(),
258            transient_slots: Vec::new(),
259            depth: 0,
260            fuel: u64::MAX,
261            refuse_unrecorded_warnings: false,
262            proven_s0: Vec::new(),
263            proven_s1: Vec::new(),
264            proven: Vec::new(),
265            work_control: None,
266            work_countdown: 0,
267            bounded_countdown: 0,
268            debugger: None,
269            calls: None,
270            transient_bound: usize::MAX,
271        }
272    }
273
274    /// Bounds optional speculative work. Exhaustion yields unsupported and
275    /// cannot be interpreted as a model verdict or a run-budget stop.
276    ///
277    /// ```
278    /// # fn configure(machine: &mut dive_core::Machine) {
279    /// machine.set_fuel(4096);
280    /// # }
281    /// ```
282    pub fn set_fuel(&mut self, units: u64) {
283        self.disarm_inline_charge();
284        self.fuel = units;
285        self.memo.reserve_member_index(
286            units == u64::MAX
287                && self.opts.member_index
288                && !self.heap.store.semantics().tlc_comparisons,
289        );
290    }
291
292    /// Whether a bounded machine has spent all of its fuel
293    /// ([`Machine::set_fuel`]), as the last charge that failed leaves it.
294    ///
295    /// ```
296    /// # fn inspect(machine: &dive_core::Machine) {
297    /// let _ = machine.fuel_exhausted();
298    /// # }
299    /// ```
300    #[must_use]
301    pub const fn fuel_exhausted(&self) -> bool {
302        self.fuel == 0
303    }
304
305    /// Makes every site where the dive-eval evaluator prints a warning that
306    /// this machine does not record in [`Machine::warnings`] fail as
307    /// unsupported instead: an `EXCEPT` key outside the function's domain
308    /// (TLC warning 2144). An isolated optional machine sets it so that its
309    /// caller can fall back to the dive-eval evaluator, which prints the
310    /// warning. Ordinary machines keep TLC's unchanged-function result.
311    ///
312    /// ```
313    /// # fn configure(machine: &mut dive_core::Machine) {
314    /// machine.set_refuse_unrecorded_warnings(true);
315    /// # }
316    /// ```
317    pub fn set_refuse_unrecorded_warnings(&mut self, enabled: bool) {
318        self.refuse_unrecorded_warnings = enabled;
319    }
320
321    /// Records handles the caller proved materialized in this machine's
322    /// store with [`Heap::proved_concrete`] or [`Heap::materialized_within`]:
323    /// the rows `s0` and `s1` it is about to load, and `others`. It forgets
324    /// the previous ones. Identity tests that require materialized operands
325    /// (a `SameVars` subscript, set membership) then skip re-proving those
326    /// exact handles. Only persistent compound handles are kept: persistent
327    /// nodes never change, so the proof stays true. An isolated analysis
328    /// machine passes the rows and constants it admitted before each
329    /// evaluation.
330    ///
331    /// Precondition, which this method does not check: every recorded handle
332    /// satisfies [`Heap::materialized_within`] in this machine's store.
333    /// Recording any other handle (a lazy or symbolic set, say) makes
334    /// membership binary-search a non-canonical node and can give a wrong
335    /// answer. That walk has no depth limit, unlike the internal check it
336    /// replaces, which declines values nested 64 deep; the skipped check
337    /// would then have refused a value whose identity is nonetheless exact,
338    /// so the recorded proof only answers more of the same questions.
339    ///
340    /// ```
341    /// # fn configure(machine: &mut dive_core::Machine, row: &[dive_core::Handle]) {
342    /// machine.set_proven_materialized(row, &[], []);
343    /// # }
344    /// ```
345    pub fn set_proven_materialized(
346        &mut self,
347        s0: &[Handle],
348        s1: &[Handle],
349        others: impl IntoIterator<Item = Handle>,
350    ) {
351        let keep = |h: &Handle| {
352            if h.is_persistent() && h.is_compound() {
353                *h
354            } else {
355                Handle::EMPTY
356            }
357        };
358        self.proven_s0.clear();
359        self.proven_s0.extend(s0.iter().map(keep));
360        self.proven_s1.clear();
361        self.proven_s1.extend(s1.iter().map(keep));
362        self.proven.clear();
363        self.proven.extend(
364            others
365                .into_iter()
366                .filter(|h| h.is_persistent() && h.is_compound()),
367        );
368    }
369
370    /// Whether `h` is a handle the caller proved materialized
371    /// ([`Machine::set_proven_materialized`]).
372    fn proven(&self, h: Handle) -> bool {
373        h.is_compound()
374            && (self.proven_s0.contains(&h)
375                || self.proven_s1.contains(&h)
376                || self.proven.contains(&h))
377    }
378
379    /// Whether `h`, the value of variable `v` in `s0` (`primed`: `s1`), is
380    /// the proven handle at that position, or otherwise proven.
381    #[inline]
382    fn proven_at(&self, v: usize, primed: bool, h: Handle) -> bool {
383        let row = if primed {
384            &self.proven_s1
385        } else {
386            &self.proven_s0
387        };
388        (h.is_compound() && row.get(v) == Some(&h)) || self.proven(h)
389    }
390
391    /// Installs the optional caller-owned cooperative work checkpoint.
392    /// Ordinary machines have no checkpoint and unbounded fuel.
393    ///
394    /// ```
395    /// # fn example(machine: &mut dive_core::Machine) {
396    /// machine.set_work_control(None);
397    /// # }
398    /// ```
399    pub fn set_work_control(&mut self, control: Option<Arc<dyn WorkControl>>) {
400        self.heap.set_work_control(control.clone());
401        self.work_control = control;
402        self.work_countdown = 0;
403        self.bounded_countdown = 0;
404    }
405
406    /// Installs explicit producer observation. Fresh replay/analysis machines
407    /// remain unobserved unless a caller separately installs this capability.
408    pub fn set_debugger(&mut self, observer: Option<Arc<dyn crate::debug::Observer>>) {
409        self.debugger = observer;
410    }
411
412    /// Keeps generator continuation transients alive during one eager batch.
413    ///
414    /// Internal rollback calls are deferred only inside `work`; normal rollback
415    /// behavior resumes before this method returns. The caller must retain any
416    /// required values after their semantic demands, clear transient receivers,
417    /// then roll back its enclosing batch mark. This does not persist or
418    /// normalize values and must not wrap a whole search or repeated iterations.
419    ///
420    /// ```
421    /// # fn example(machine: &mut dive_core::Machine) {
422    /// let mark = machine.heap.mark();
423    /// machine.with_deferred_reclamation(|_machine| ());
424    /// machine.heap.rollback(mark);
425    /// # }
426    /// ```
427    pub fn with_deferred_reclamation<T>(&mut self, work: impl FnOnce(&mut Self) -> T) -> T {
428        let previous = std::mem::replace(&mut self.heap.defer_reclamation, true);
429        let result = work(self);
430        self.heap.defer_reclamation = previous;
431        result
432    }
433
434    /// Disables TLCGet/TLCSet in finite modes without a live checker context.
435    /// Access refuses when reached; an untaken branch remains unevaluated.
436    pub fn deny_checker_access(&mut self) {
437        self.checker_access = CheckerAccess::Denied;
438    }
439
440    /// Keeps `TLCGet("level")` available in a finite mode whose driver sets
441    /// [`Machine::level`] the way TLC does for that mode. Register reads and
442    /// writes still refuse.
443    pub fn allow_finite_level(&mut self) {
444        if self.checker_access == CheckerAccess::Denied {
445            self.checker_access = CheckerAccess::Level;
446        }
447    }
448
449    fn check_finite_access(&self, op: dive_ir::StdOp) -> Result<(), Error> {
450        let allowed = match self.checker_access {
451            CheckerAccess::Full => true,
452            CheckerAccess::Level => op == dive_ir::StdOp::TlcTLCGet,
453            CheckerAccess::Denied => false,
454        };
455        if !allowed
456            && op.impure()
457            && !matches!(op, dive_ir::StdOp::TlcPrint | dive_ir::StdOp::TlcPrintT)
458        {
459            return Err(Error::unsupported(format!(
460                "{}: native finite mode runtime effect is unsupported",
461                op.qualified_name()
462            )));
463        }
464        Ok(())
465    }
466
467    /// Bounds retained Print events and UTF-8 bytes for a finite mode.
468    /// The ordinary checker leaves this unset. Rendering occurs before admission.
469    pub fn set_output_limits(&mut self, events: usize, bytes: usize) {
470        self.output_limits = Some((events, bytes));
471    }
472
473    /// The first output-admission limit reached by this machine.
474    #[must_use]
475    pub const fn output_failure(&self) -> Option<&'static str> {
476        self.output_failure
477    }
478
479    pub(crate) fn print(&mut self, text: String) -> Result<(), Error> {
480        if let Some((events, bytes)) = self.output_limits {
481            let total = self.output_used.1.checked_add(text.len());
482            let failure = if self.output_used.0 >= events {
483                Some("simulation output event bound")
484            } else if total.is_none_or(|total| total > bytes) {
485                Some("simulation output byte bound")
486            } else {
487                None
488            };
489            if let Some(failure) = failure {
490                self.output_failure.get_or_insert(failure);
491                return Err(Error::unsupported(failure));
492            }
493            self.output_used = (self.output_used.0 + 1, total.unwrap_or(bytes));
494        }
495        self.printed.push(text);
496        Ok(())
497    }
498
499    /// Spends `n` units of fuel: one per element a loop visits.
500    ///
501    /// The inline path only counts down to the next [`WorkControl`] poll
502    /// ([`WORK_POLL_UNITS`]). Its countdown is armed only while fuel and the
503    /// start-up transient bound are unbounded, so a bounded machine checks
504    /// both exactly on every charge ([`Machine::charge_slow`]).
505    #[inline]
506    pub(crate) fn charge(&mut self, n: usize) -> Result<(), Error> {
507        let units = (n as u64).max(1);
508        if units < self.work_countdown {
509            self.work_countdown -= units;
510            return Ok(());
511        }
512        self.charge_slow(units, n)
513    }
514
515    /// The checks [`Machine::charge`] amortizes or skips: the work poll
516    /// once the units since the last one reach [`WORK_POLL_UNITS`], and the
517    /// start-up transient bound and finite fuel, exactly. The units left
518    /// before the next poll live in `work_countdown` while the machine is
519    /// unbounded and in `bounded_countdown` otherwise; at most one is
520    /// nonzero. A refused poll leaves both at zero, so every later charge
521    /// polls again.
522    #[inline(never)]
523    fn charge_slow(&mut self, units: u64, n: usize) -> Result<(), Error> {
524        let left = self.work_countdown.max(self.bounded_countdown);
525        self.work_countdown = 0;
526        self.bounded_countdown = 0;
527        if units < left {
528            self.bounded_countdown = left - units;
529        } else if self
530            .work_control
531            .as_ref()
532            .is_some_and(|control| !control.proceed())
533        {
534            self.heap.mark_work_interrupted();
535            return Err(Error::stop());
536        } else {
537            self.bounded_countdown = WORK_POLL_UNITS;
538        }
539        if self.transient_bound != usize::MAX && self.heap.arena.footprint() > self.transient_bound
540        {
541            return Err(Error::unsupported("the start-up evaluation memory bound"));
542        }
543        if self.fuel == u64::MAX {
544            if self.transient_bound == usize::MAX {
545                self.work_countdown = std::mem::take(&mut self.bounded_countdown);
546            }
547            return Ok(());
548        }
549        let n = n as u64;
550        if self.fuel < n {
551            self.fuel = 0;
552            return Err(Error::unsupported("the constant-folding budget"));
553        }
554        self.fuel -= n;
555        Ok(())
556    }
557
558    /// Moves the poll countdown off the inline path of [`Machine::charge`]
559    /// before fuel or the transient bound changes, keeping the units left.
560    fn disarm_inline_charge(&mut self) {
561        self.bounded_countdown = self
562            .bounded_countdown
563            .max(std::mem::take(&mut self.work_countdown));
564    }
565
566    /// Bounds the transient bytes an evaluation may hold; [`Machine::charge`]
567    /// checks the bound exactly while it is finite.
568    pub(crate) fn set_transient_bound(&mut self, bytes: usize) {
569        self.disarm_inline_charge();
570        self.transient_bound = bytes;
571    }
572
573    fn take_scratch(&mut self) -> Vec<Handle> {
574        let mut v = self.scratch.pop().unwrap_or_default();
575        v.clear();
576        v
577    }
578
579    fn give_scratch(&mut self, v: Vec<Handle>) {
580        self.scratch.push(v);
581    }
582
583    /// Enters a frame of `size` slots for a role, returning the old base.
584    pub fn enter(&mut self, size: u32) -> usize {
585        let old = self.base;
586        self.base = self.frame.len();
587        self.frame.resize(self.base + size as usize, Handle::EMPTY);
588        old
589    }
590
591    /// Leaves the frame entered by [`Machine::enter`].
592    pub fn leave(&mut self, old: usize) {
593        self.frame.truncate(self.base);
594        self.base = old;
595        if self.frame.is_empty() {
596            // Every recorded thunk slot has left the frame.
597            self.transient_slots.clear();
598        }
599    }
600
601    /// The point from which [`Machine::thunks_released`] considers the thunk
602    /// slots forced to a transient. Take it with the [`Heap::mark`] that a
603    /// later rollback frees to.
604    #[must_use]
605    pub fn thunk_mark(&self) -> usize {
606        self.transient_slots.len()
607    }
608
609    /// Whether no thunk slot still in the frame holds a transient forced
610    /// since `since`, so that a rollback
611    /// to the heap mark taken with it frees no value a live slot holds.
612    /// A slot forced in a frame that has since been left is gone: entering
613    /// a frame fills fresh slots with [`Handle::EMPTY`]. Forgets the
614    /// positions of slots that have left the frame; a true result forgets
615    /// every position recorded since `since`.
616    pub fn thunks_released(&mut self, since: usize) -> bool {
617        let len = self.transient_slots.len();
618        if since >= len {
619            return true;
620        }
621        let live = self.frame.len();
622        let mut kept = since;
623        let mut i = since;
624        while i < len {
625            let slot = self.transient_slots[i];
626            if slot < live {
627                self.transient_slots[kept] = slot;
628                kept += 1;
629            }
630            i += 1;
631        }
632        self.transient_slots.truncate(kept);
633        kept == since
634    }
635
636    #[inline]
637    pub(crate) fn slot(&self, s: u32) -> Handle {
638        self.frame
639            .get(self.base + s as usize)
640            .copied()
641            .unwrap_or(Handle::EMPTY)
642    }
643
644    #[inline]
645    pub(crate) fn set_slot(&mut self, s: u32, v: Handle) {
646        if let Some(x) = self.frame.get_mut(self.base + s as usize) {
647            *x = v;
648        }
649    }
650
651    /// Evaluates a node to a boolean.
652    ///
653    /// # Errors
654    /// Evaluation errors, or a non-boolean result.
655    pub fn eval_bool(&mut self, code: &Code, p: P) -> Result<bool, Error> {
656        let v = self.eval(code, p)?;
657        bool_of(v)
658    }
659
660    /// Evaluates a node and normalizes the result.
661    ///
662    /// # Errors
663    /// Evaluation errors.
664    pub fn eval_norm(&mut self, code: &Code, p: P) -> Result<Handle, Error> {
665        let v = self.eval(code, p)?;
666        self.work_norm(v)
667    }
668
669    /// Whether a [`Node::SameVars`] may compare its leaves directly. Its
670    /// `Eq` forces the thunks, whose bodies build both tuples from the
671    /// variables (`eval_component`); `compare::equals` then requires every
672    /// leaf materialized at its depth and, outside TLC comparisons, returns
673    /// the tuples' `Heap::eq`, which is the conjunction of the leaves'
674    /// `Heap::eq` (the same tree, so equal arities). A materialized leaf is
675    /// neither symbolic nor a product, so `eval_component` returns it
676    /// unchanged. Skipping an unforced thunk only leaves it for a later
677    /// demand. TLC comparisons (whose shape guard may refuse), an observed
678    /// debugger, a forced thunk (whose cached value `Eq` would read), an
679    /// unassigned variable or an unmaterialized leaf evaluate the `Eq`.
680    fn same_vars_direct(&self, leaves: &[(u16, u8)], thunks: &[u32]) -> Result<bool, Error> {
681        if self.debugger.is_some()
682            || self.heap.store().semantics().tlc_comparisons
683            || thunks.iter().any(|&slot| !self.slot(slot).is_empty())
684        {
685            return Ok(false);
686        }
687        for &(v, depth) in leaves {
688            let v = usize::from(v);
689            let (Some(&a), Some(&b)) = (self.s0.get(v), self.s1.get(v)) else {
690                return Ok(false);
691            };
692            if !(self.proven_at(v, false, a) || compare::materialized(&self.heap, a, depth)?)
693                || (a != b
694                    && !(self.proven_at(v, true, b)
695                        || compare::materialized(&self.heap, b, depth)?))
696            {
697                return Ok(false);
698            }
699        }
700        Ok(true)
701    }
702
703    pub(crate) fn demand_equals(&mut self, a: Handle, b: Handle) -> Result<bool, Error> {
704        let a = self.work_norm(a)?;
705        let b = self.work_norm(b)?;
706        compare::equals(&self.heap, a, b)
707    }
708
709    pub(crate) fn eval_component(&mut self, code: &Code, p: P) -> Result<Handle, Error> {
710        let value = self.eval(code, p)?;
711        if self.heap.kind(value) == Some(Kind::Product) {
712            // Keep symbolic products lazy until an operator demands their elements.
713            Ok(value)
714        } else {
715            self.work_norm(value)
716        }
717    }
718
719    /// Evaluates a node.
720    ///
721    /// # Errors
722    /// Evaluation errors, refusals and resource limits.
723    pub fn eval(&mut self, code: &Code, p: P) -> Result<Handle, Error> {
724        let Some(observer) = &self.debugger else {
725            return self.eval_inner(code, p);
726        };
727        let instruction = crate::debug::Instruction::Value(p);
728        let guard = crate::debug::Guard::enter(observer, instruction, code, self)?;
729        let result = self.eval_inner(code, p);
730        let returned = match &result {
731            Ok(value) => crate::debug::Returned::Value(*value),
732            Err(error) => crate::debug::Returned::Failed(error),
733        };
734        guard.returned(instruction, code, self, returned)?;
735        result
736    }
737
738    #[allow(
739        clippy::too_many_lines,
740        clippy::many_single_char_names,
741        reason = "one arm per node kind, with operand names as in the semantics"
742    )]
743    fn eval_inner(&mut self, code: &Code, p: P) -> Result<Handle, Error> {
744        if self.fuel != u64::MAX {
745            self.charge(1)?;
746        }
747        let Some(node) = code.nodes.get(p as usize) else {
748            return Err(Error::internal("plan node out of range"));
749        };
750        match node {
751            Node::Const(h) => Ok(*h),
752            Node::Slot(s) => {
753                let v = self.slot(*s);
754                if v.is_empty() {
755                    return Err(Error::internal("read of an unbound slot"));
756                }
757                Ok(v)
758            }
759            Node::Lazy { slot, body } => {
760                let v = self.slot(*slot);
761                if !v.is_empty() {
762                    self.stats.cached += 1;
763                    return Ok(v);
764                }
765                self.stats.forced += 1;
766                let v = self.eval(code, *body)?;
767                if v.is_transient() {
768                    self.stats.transient_thunks += 1;
769                    self.transient_slots.push(self.base + *slot as usize);
770                }
771                self.set_slot(*slot, v);
772                Ok(v)
773            }
774            Node::Var(i) => {
775                let v = self
776                    .s0
777                    .get(usize::from(*i))
778                    .copied()
779                    .unwrap_or(Handle::EMPTY);
780                if v.is_empty() {
781                    return Err(eval_err("read of an unassigned variable"));
782                }
783                Ok(v)
784            }
785            Node::Primed(i) => {
786                let v = self
787                    .s1
788                    .get(usize::from(*i))
789                    .copied()
790                    .unwrap_or(Handle::EMPTY);
791                if v.is_empty() {
792                    return Err(eval_err("read of an unassigned primed variable"));
793                }
794                Ok(v)
795            }
796            Node::Not(a) => Ok(Handle::bool(!self.eval_bool(code, *a)?)),
797            Node::And(items) => {
798                for &i in items {
799                    if !self.eval_bool(code, i)? {
800                        return Ok(Handle::FALSE);
801                    }
802                }
803                Ok(Handle::TRUE)
804            }
805            Node::Or(items) => {
806                for &i in items {
807                    if self.eval_bool(code, i)? {
808                        return Ok(Handle::TRUE);
809                    }
810                }
811                Ok(Handle::FALSE)
812            }
813            Node::Implies(a, b) => {
814                if self.eval_bool(code, *a)? {
815                    Ok(Handle::bool(self.eval_bool(code, *b)?))
816                } else {
817                    Ok(Handle::TRUE)
818                }
819            }
820            Node::Equiv(a, b) => {
821                let x = self.eval_bool(code, *a)?;
822                let y = self.eval_bool(code, *b)?;
823                Ok(Handle::bool(x == y))
824            }
825            Node::If(c, a, b) => {
826                if self.eval_bool(code, *c)? {
827                    self.eval(code, *a)
828                } else {
829                    self.eval(code, *b)
830                }
831            }
832            Node::Case(arms, other) => {
833                for &(g, v) in arms {
834                    if self.eval_bool(code, g)? {
835                        return self.eval(code, v);
836                    }
837                }
838                match other {
839                    Some(o) => self.eval(code, *o),
840                    None => Err(eval_err("TLC encountered a CASE with no conditions true")),
841                }
842            }
843            Node::Eq(a, b) => {
844                let x = self.eval_norm(code, *a)?;
845                let y = self.eval_norm(code, *b)?;
846                Ok(Handle::bool(compare::equals(&self.heap, x, y)?))
847            }
848            Node::SameVars { eq, leaves, thunks } => {
849                if self.same_vars_direct(leaves, thunks)? {
850                    let same = leaves.iter().all(|&(v, _)| {
851                        let v = usize::from(v);
852                        match (self.s0.get(v), self.s1.get(v)) {
853                            (Some(&a), Some(&b)) => self.heap.eq(a, b),
854                            _ => false,
855                        }
856                    });
857                    return Ok(Handle::bool(same));
858                }
859                self.eval(code, *eq)
860            }
861            Node::Neq(a, b) => {
862                let x = self.eval_norm(code, *a)?;
863                let y = self.eval_norm(code, *b)?;
864                Ok(Handle::bool(!compare::equals(&self.heap, x, y)?))
865            }
866            Node::In(a, s) => {
867                let x = self.eval_norm(code, *a)?;
868                let set = self.eval(code, *s)?;
869                Ok(Handle::bool(self.member(x, set)?))
870            }
871            Node::NotIn(a, s) => {
872                let x = self.eval_norm(code, *a)?;
873                let set = self.eval(code, *s)?;
874                Ok(Handle::bool(!self.member(x, set)?))
875            }
876            Node::Subseteq(a, b) => {
877                let x = self.eval(code, *a)?;
878                let x = self.work_norm(x)?;
879                let y = self.eval(code, *b)?;
880                let elems = self.work_elements(x)?;
881                self.charge(elems.len())?;
882                for e in elems {
883                    if !self.member(e, y)? {
884                        return Ok(Handle::FALSE);
885                    }
886                }
887                Ok(Handle::TRUE)
888            }
889            Node::Arith(op, a, b) => {
890                let x = self.eval(code, *a)?;
891                let y = self.eval(code, *b)?;
892                // Inline operands whose result is inline (and, in TLC mode,
893                // a Java `int`) take the fast path; anything else is the
894                // heap's (big integers, TLC overflow, domain errors).
895                if let (Some(i), Some(j)) = (x.as_int(), y.as_int())
896                    && let Some(h) = fast_arith(*op, i, j, self.heap.int_mode())
897                {
898                    return Ok(h);
899                }
900                // A bounded machine pays for a big power's digits before
901                // they are allocated.
902                if *op == Arith::Pow && self.fuel != u64::MAX {
903                    let words = self.heap.pow_result_words(x, y);
904                    self.charge(usize::try_from(words).unwrap_or(usize::MAX))?;
905                }
906                self.heap.int_arith(int_op(*op), x, y)
907            }
908            Node::Cmp(op, a, b) => {
909                let x = self.eval(code, *a)?;
910                let y = self.eval(code, *b)?;
911                let o = match (x.as_int(), y.as_int()) {
912                    (Some(i), Some(j)) => i.cmp(&j),
913                    _ => self
914                        .heap
915                        .int_cmp(x, y)
916                        .ok_or_else(|| eval_err("expected an integer"))?,
917                };
918                Ok(Handle::bool(match op {
919                    Cmp::Lt => o.is_lt(),
920                    Cmp::Le => o.is_le(),
921                    Cmp::Gt => o.is_gt(),
922                    Cmp::Ge => o.is_ge(),
923                }))
924            }
925            Node::Neg(a) => {
926                let x = self.eval(code, *a)?;
927                if self.heap.int_mode() == IntMode::Big
928                    && let Some(h) = x.as_int().and_then(i64::checked_neg).and_then(Handle::int)
929                {
930                    return Ok(h);
931                }
932                self.heap.int_neg(x)
933            }
934            Node::Range(a, b) => {
935                let x = int_of(self.eval(code, *a)?)?;
936                let y = int_of(self.eval(code, *b)?)?;
937                Ok(self.heap.interval(x, y))
938            }
939            Node::SetEnum(items) => {
940                let mut v = self.take_scratch();
941                for &i in items {
942                    match self.eval_component(code, i) {
943                        Ok(e) => v.push(e),
944                        Err(e) => {
945                            self.give_scratch(v);
946                            return Err(e);
947                        }
948                    }
949                }
950                for value in &mut v {
951                    *value = self.work_norm(*value)?;
952                }
953                if let Err(error) = compare::require_materialized(&self.heap, &v) {
954                    self.give_scratch(v);
955                    return Err(error);
956                }
957                let r = self.heap.set_from(&mut v);
958                self.give_scratch(v);
959                self.checked_set(r)
960            }
961            Node::SetBin(op, a, b) => {
962                let x = self.eval(code, *a)?;
963                let y = self.eval(code, *b)?;
964                self.set_bin(*op, x, y)
965            }
966            Node::Powerset(a) => {
967                let x = self.eval(code, *a)?;
968                Ok(self.heap.symbolic(Kind::Subset, 0, &[x]))
969            }
970            Node::BigUnion(a) => {
971                let x = self.eval_norm(code, *a)?;
972                let members = self.work_elements(x)?;
973                // TLC's `UnionValue` stays lazy: membership tests the
974                // members in turn. The core keeps it lazy only when some
975                // member cannot be enumerated.
976                let mut normed = Vec::with_capacity(members.len());
977                for m in members {
978                    normed.push(self.work_norm(m)?);
979                }
980                if normed.iter().any(|&m| !self.heap.is_finite(m)) {
981                    let mut it = normed.into_iter();
982                    let Some(first) = it.next() else {
983                        return Err(Error::internal("an empty UNION with an infinite member"));
984                    };
985                    return Ok(it.fold(first, |acc, m| self.heap.union(acc, m)));
986                }
987                let mut out = Vec::new();
988                for m in normed {
989                    let m = self.work_norm(m)?;
990                    let es = self.work_elements(m)?;
991                    self.charge(es.len())?;
992                    out.extend(es);
993                }
994                let r = self.heap.set_from(&mut out);
995                self.checked_set(r)
996            }
997            Node::Product(items) => {
998                let mut v = Vec::with_capacity(items.len());
999                for &i in items {
1000                    v.push(self.eval(code, i)?);
1001                }
1002                Ok(self.heap.symbolic(Kind::Product, 0, &v))
1003            }
1004            Node::FcnSet(d, r) => {
1005                let x = self.eval_component(code, *d)?;
1006                let y = self.eval(code, *r)?;
1007                Ok(self.heap.symbolic(Kind::FcnSet, 0, &[x, y]))
1008            }
1009            Node::RecSet(fields) => {
1010                let mut v: Vec<Handle> = fields.iter().map(|f| f.0).collect();
1011                for &(_, s) in fields {
1012                    v.push(self.eval(code, s)?);
1013                }
1014                Ok(self.heap.symbolic(Kind::RecSet, 0, &v))
1015            }
1016            Node::Filter { bind, pred, subset } => self.filter(code, bind, *pred, *subset),
1017            Node::Map { binds, body } => {
1018                let mut out = Vec::new();
1019                self.for_each_binding(code, binds, &mut |m: &mut Self| {
1020                    let v = m.eval_component(code, *body)?;
1021                    let v = m.work_norm(v)?;
1022                    m.charge(1)?;
1023                    out.try_reserve(1)
1024                        .map_err(|_| Error::unsupported("MAP construction allocation"))?;
1025                    out.push(v);
1026                    Ok(true)
1027                })?;
1028                compare::require_materialized(&self.heap, &out)?;
1029                let r = self.heap.set_from(&mut out);
1030                self.checked_set(r)
1031            }
1032            Node::FcnCons { binds, body } => self.fcn_cons(code, binds, *body),
1033            Node::Quant { kind, binds, body } => self.quant(code, *kind, binds, *body),
1034            Node::Apply(f, a) => {
1035                let fv = self.eval(code, *f)?;
1036                let av = self.eval_norm(code, *a)?;
1037                self.apply(fv, av)
1038            }
1039            Node::Select(r, field) => {
1040                let rv = self.eval(code, *r)?;
1041                self.select(rv, *field)
1042            }
1043            Node::Domain(f) => {
1044                let fv = self.eval(code, *f)?;
1045                self.domain(fv)
1046            }
1047            Node::Except { base, updates } => {
1048                let mut f = self.eval_norm(code, *base)?;
1049                for u in updates {
1050                    f = self.except(code, f, u, 0)?;
1051                }
1052                Ok(f)
1053            }
1054            Node::Tuple(items) => {
1055                let mut v = self.take_scratch();
1056                for &i in items {
1057                    match self.eval_component(code, i) {
1058                        Ok(e) => v.push(e),
1059                        Err(e) => {
1060                            self.give_scratch(v);
1061                            return Err(e);
1062                        }
1063                    }
1064                }
1065                let r = self.heap.tuple_literal(&v);
1066                self.give_scratch(v);
1067                Ok(r)
1068            }
1069            Node::Record(fields) => {
1070                let mut keys = self.take_scratch();
1071                let mut vals = self.take_scratch();
1072                for &(k, e) in fields {
1073                    keys.push(k);
1074                    match self.eval_component(code, e) {
1075                        Ok(v) => vals.push(v),
1076                        Err(e) => {
1077                            self.give_scratch(keys);
1078                            self.give_scratch(vals);
1079                            return Err(e);
1080                        }
1081                    }
1082                }
1083                let r = self.heap.record(&keys, &vals);
1084                self.give_scratch(keys);
1085                self.give_scratch(vals);
1086                Ok(r)
1087            }
1088            Node::Scope { reset, body } => {
1089                for &s in reset {
1090                    self.set_slot(s, Handle::EMPTY);
1091                }
1092                self.eval(code, *body)
1093            }
1094            Node::Call { fun, args } => self.call(code, *fun, args),
1095            Node::Std(f, args) => self.std(code, *f, args),
1096            Node::Lib {
1097                op,
1098                args,
1099                repeatable_args,
1100            } => {
1101                self.check_finite_access(*op)?;
1102                // A call the core does not reproduce refuses before its
1103                // arguments are evaluated: an argument may itself be such a
1104                // call, or have an effect TLC would order differently.
1105                if crate::stdlib::deferred(*op) {
1106                    return Err(crate::stdlib::deferred_refusal(*op));
1107                }
1108                // A value printed keeps its form: TLC prints an interval as
1109                // `1..3` (`crate::print`), and draws from a lazy `[S -> T]`
1110                // one value per component (`crate::random`).
1111                let prints = matches!(
1112                    op,
1113                    dive_ir::StdOp::TlcPrint
1114                        | dive_ir::StdOp::TlcPrintT
1115                        | dive_ir::StdOp::TlcToString
1116                        | dive_ir::StdOp::TlcRandomElement
1117                );
1118                let mut a = Vec::with_capacity(args.len());
1119                for &x in args {
1120                    a.push(if prints {
1121                        self.eval(code, x)?
1122                    } else if *op == dive_ir::StdOp::TlcMakeFcn {
1123                        self.eval_component(code, x)?
1124                    } else {
1125                        let value = self.eval_component(code, x)?;
1126                        self.work_norm(value)?
1127                    });
1128                }
1129                // The evaluating override returns null for nonstrings and
1130                // TLC then evaluates the TLA+ definition. Its argument
1131                // demands must not be replaced by a single value snapshot.
1132                if !repeatable_args
1133                    && matches!(
1134                        op,
1135                        dive_ir::StdOp::SequencesExtReplaceFirstSubSeq
1136                            | dive_ir::StdOp::SequencesExtReplaceAllSubSeqs
1137                    )
1138                    && a.iter().any(|h| h.as_str_id().is_none())
1139                {
1140                    return Err(Error::unsupported(format!(
1141                        "{} with sequence arguments whose repeated fallback demand is not proven effect-free",
1142                        op.qualified_name()
1143                    )));
1144                }
1145                crate::stdlib::call(self, *op, &a)
1146            }
1147            Node::LibHo(op, args) => {
1148                self.check_finite_access(*op)?;
1149                let mut a = Vec::with_capacity(args.len());
1150                for x in args {
1151                    a.push(match x {
1152                        LibArg::Value(p) => {
1153                            let value = self.eval_component(code, *p)?;
1154                            crate::stdlib::Ho::Value(self.work_norm(value)?)
1155                        }
1156                        LibArg::Op { params, body } => {
1157                            crate::stdlib::Ho::Op(crate::stdlib::OpFn::new(code, params, *body))
1158                        }
1159                    });
1160                }
1161                crate::stdlib::call_ho(self, *op, &a)
1162            }
1163            Node::Enabled { g, .. } => self.enabled(code, *g),
1164            Node::Composition {
1165                first, then, reset, ..
1166            } => self.composition_holds(code, *first, *then, reset),
1167            Node::Memo { site, body } => self.memo_eval(code, *site, *body),
1168            Node::Spec(b) => self.eval(code, *b).map_err(speculative),
1169            Node::Beta { chain, fc, arg } => self.beta(code, *chain, *fc, *arg),
1170            Node::DomCheck { slot, domain, body } => {
1171                let d = self.eval(code, *domain).map_err(speculative)?;
1172                let x = self.slot(*slot);
1173                if !self.member(x, d)? {
1174                    return Err(general(
1175                        "In applying the function\na recursive function, the argument is not in its domain",
1176                    ));
1177                }
1178                self.eval(code, *body)
1179            }
1180            Node::InLazy { elem, set, neg } => {
1181                let x = self.eval_norm(code, *elem)?;
1182                let r = self.member_lazy(code, x, *set)?;
1183                Ok(Handle::bool(r != *neg))
1184            }
1185        }
1186    }
1187
1188    /// `Node::Beta`: TLC's `FcnLambdaValue.apply` on a function constructor
1189    /// whose bound variables have no tuple pattern. The function's domains
1190    /// are evaluated first, in order (TLC builds the lazy function before
1191    /// evaluating the argument), then the argument. With one bound variable
1192    /// the argument must be in the domain; with several it is a tuple of
1193    /// their number whose components, in order, must be in their domains.
1194    /// The body is then evaluated for that argument alone.
1195    fn beta(&mut self, code: &Code, chain: P, fc: P, arg: P) -> Result<Handle, Error> {
1196        match code.nodes.get(chain as usize) {
1197            Some(Node::Lazy { slot, body }) => {
1198                let v = self.slot(*slot);
1199                if v.is_empty() {
1200                    self.beta(code, *body, fc, arg)
1201                } else {
1202                    let a = self.eval_norm(code, arg)?;
1203                    self.apply(v, a)
1204                }
1205            }
1206            Some(Node::Scope { reset, body }) => {
1207                for &s in reset {
1208                    self.set_slot(s, Handle::EMPTY);
1209                }
1210                self.beta(code, *body, fc, arg)
1211            }
1212            Some(Node::Spec(b)) => self.beta(code, *b, fc, arg),
1213            Some(Node::FcnCons { binds, body }) if chain == fc => {
1214                if let [bind] = &binds[..]
1215                    && let [slot] = bind.slots[..]
1216                {
1217                    return self.beta_one(code, bind.domain, slot, arg, *body);
1218                }
1219                self.beta_many(code, chain, binds, arg, *body)
1220            }
1221            _ => Err(Error::internal("a lazy application of a non-function node")),
1222        }
1223    }
1224
1225    fn beta_one(
1226        &mut self,
1227        code: &Code,
1228        domain: P,
1229        slot: u32,
1230        arg: P,
1231        body: P,
1232    ) -> Result<Handle, Error> {
1233        let dom = self.eval(code, domain)?;
1234        let x = self.eval_norm(code, arg)?;
1235        if !self.member(x, dom)? {
1236            return Err(general(
1237                "In applying the function\na function, the argument is not in its domain",
1238            ));
1239        }
1240        let old = self.slot(slot);
1241        self.set_slot(slot, x);
1242        let out = self.eval(code, body);
1243        self.set_slot(slot, old);
1244        out
1245    }
1246
1247    /// [`Machine::beta`] with several bound variables. An argument that is
1248    /// not a tuple of their number takes the constructor's speculative
1249    /// eager build and ordinary application instead, unchanged.
1250    fn beta_many(
1251        &mut self,
1252        code: &Code,
1253        fc: P,
1254        binds: &[Bind],
1255        arg: P,
1256        body: P,
1257    ) -> Result<Handle, Error> {
1258        if binds.iter().any(|b| b.tuple || b.slots.is_empty()) {
1259            return Err(Error::internal(
1260                "a lazy application with a tuple pattern or no bound variable",
1261            ));
1262        }
1263        let mut doms = Vec::with_capacity(binds.len());
1264        for b in binds {
1265            doms.push(self.eval(code, b.domain)?);
1266        }
1267        let x = self.eval_norm(code, arg)?;
1268        let arity: usize = binds.iter().map(|b| b.slots.len()).sum();
1269        let parts = if x.is_compound() {
1270            let v = self.heap.view(x);
1271            (v.kind == Kind::IntFcn && v.lo == 1 && v.data.len() == arity).then(|| v.data.to_vec())
1272        } else {
1273            None
1274        };
1275        let Some(parts) = parts else {
1276            let f = self.eval(code, fc).map_err(speculative)?;
1277            return self.apply(f, x);
1278        };
1279        let mut k = 0;
1280        for (b, &dom) in binds.iter().zip(&doms) {
1281            for _ in &b.slots {
1282                if !self.member(parts[k], dom)? {
1283                    return Err(general(
1284                        "In applying the function\na function, the argument is not in its domain",
1285                    ));
1286                }
1287                k += 1;
1288            }
1289        }
1290        let mark = self.saved.len();
1291        for &s in binds.iter().flat_map(|b| b.slots.iter()) {
1292            let v = self.slot(s);
1293            self.saved.push(v);
1294        }
1295        for (&s, &p) in binds.iter().flat_map(|b| b.slots.iter()).zip(&parts) {
1296            self.set_slot(s, p);
1297        }
1298        let out = self.eval(code, body);
1299        for (k, &s) in binds.iter().flat_map(|b| b.slots.iter()).enumerate() {
1300            let v = self.saved.get(mark + k).copied().unwrap_or(Handle::EMPTY);
1301            self.set_slot(s, v);
1302        }
1303        self.saved.truncate(mark);
1304        out
1305    }
1306
1307    /// Membership in a set node TLC keeps lazy (`Node::InLazy`), without
1308    /// building the set. Any other node is evaluated and tested.
1309    fn member_lazy(&mut self, code: &Code, x: Handle, set: P) -> Result<bool, Error> {
1310        match code.nodes.get(set as usize) {
1311            // TLC's `SetPredValue.member`: the domain first, then the
1312            // predicate on the element.
1313            Some(Node::Filter { bind, pred, .. }) => {
1314                if !self.member_lazy(code, x, bind.domain)? {
1315                    return Ok(false);
1316                }
1317                let mark = self.saved.len();
1318                for &s in &bind.slots {
1319                    let v = self.slot(s);
1320                    self.saved.push(v);
1321                }
1322                let r = self
1323                    .bind_one(bind, x)
1324                    .and_then(|()| self.eval_bool(code, *pred));
1325                for (k, &s) in bind.slots.iter().enumerate() {
1326                    let v = self.saved.get(mark + k).copied().unwrap_or(Handle::EMPTY);
1327                    self.set_slot(s, v);
1328                }
1329                self.saved.truncate(mark);
1330                r
1331            }
1332            // `SetCupValue`, `SetCapValue`, `SetDiffValue`: short-circuit, left
1333            // operand first.
1334            Some(Node::SetBin(op, a, b)) => {
1335                let (op, a, b) = (*op, *a, *b);
1336                let left = self.member_lazy(code, x, a)?;
1337                match op {
1338                    SetOp::Cup if left => Ok(true),
1339                    SetOp::Cap | SetOp::Minus if !left => Ok(false),
1340                    SetOp::Cup | SetOp::Cap => self.member_lazy(code, x, b),
1341                    SetOp::Minus => Ok(!self.member_lazy(code, x, b)?),
1342                }
1343            }
1344            // A thunk not yet forced is not forced: TLC's value behind it is
1345            // the lazy set.
1346            Some(Node::Lazy { slot, body }) => {
1347                let v = self.slot(*slot);
1348                if v.is_empty() {
1349                    self.member_lazy(code, x, *body)
1350                } else {
1351                    self.member(x, v)
1352                }
1353            }
1354            Some(Node::Scope { reset, body }) => {
1355                for &s in reset {
1356                    self.set_slot(s, Handle::EMPTY);
1357                }
1358                self.member_lazy(code, x, *body)
1359            }
1360            // The compiler emits `InLazy` only for sets TLC certainly keeps
1361            // lazy, so deciding membership structurally is exactly TLC's
1362            // evaluation: no speculation.
1363            Some(Node::Spec(b)) => self.member_lazy(code, x, *b),
1364            // A primed definition's site is decided on its body, as the
1365            // inline body is: the test builds nothing to cache
1366            // (`Compiler::lazy_set`).
1367            Some(Node::Memo { site, body })
1368                if code.sites.get(*site as usize).is_some_and(|s| s.candidate) =>
1369            {
1370                self.member_lazy(code, x, *body)
1371            }
1372            _ => {
1373                let s = self.eval(code, set)?;
1374                self.member(x, s)
1375            }
1376        }
1377    }
1378
1379    /// Evaluates a memo site's body through its table.
1380    fn memo_eval(&mut self, code: &Code, site: u32, body: P) -> Result<Handle, Error> {
1381        // Step sites intern primed keys even when opts.memo is false. Candidate
1382        // spill owns transient values instead, so bypass before any promotion.
1383        if self.heap.speculative {
1384            return self.eval(code, body);
1385        }
1386        let Some(s) = code.sites.get(site as usize) else {
1387            return self.eval(code, body);
1388        };
1389        if !(self.opts.memo || s.step) || !self.memo.active(site) {
1390            return self.eval(code, body);
1391        }
1392        // A candidate site's persistent copies are charged to a bounded
1393        // budget; once it is spent the site is off (`Memo::charge_kept`).
1394        if s.candidate && !self.memo.may_keep() {
1395            self.memo.charge_kept(site, 0);
1396            return self.eval(code, body);
1397        }
1398        let added = self.heap.cache.added;
1399        let mut key = [Handle::EMPTY; MAX_KEY];
1400        let mut n = 0;
1401        for &v in &s.vars {
1402            let h = self
1403                .s0
1404                .get(usize::from(v))
1405                .copied()
1406                .unwrap_or(Handle::EMPTY);
1407            if h.is_transient() || h.is_empty() || n >= MAX_KEY {
1408                self.memo.bypass(site);
1409                return self.eval(code, body);
1410            }
1411            key[n] = h;
1412            n += 1;
1413        }
1414        for &v in &s.primed {
1415            let h = self
1416                .s1
1417                .get(usize::from(v))
1418                .copied()
1419                .unwrap_or(Handle::EMPTY);
1420            // The successor's value is keyed by an exact persistent copy
1421            // (`Heap::intern_exact`): equal keys are equal representations.
1422            // The successor itself is left as it is.
1423            let h = match self.heap.intern_exact(h) {
1424                Ok(k) if !h.is_empty() && n < MAX_KEY => k,
1425                _ => {
1426                    if s.candidate {
1427                        self.charge_kept(site, added);
1428                    }
1429                    self.memo.bypass(site);
1430                    return self.eval(code, body);
1431                }
1432            };
1433            key[n] = h;
1434            n += 1;
1435        }
1436        for &sl in &s.slots {
1437            let h = self.slot(sl);
1438            if h.is_transient() || h.is_empty() || n >= MAX_KEY {
1439                self.memo.bypass(site);
1440                return self.eval(code, body);
1441            }
1442            key[n] = h;
1443            n += 1;
1444        }
1445        if s.candidate {
1446            self.charge_kept(site, added);
1447        }
1448        if let Some(r) = self.memo.get(site, &key[..n]) {
1449            return Ok(r);
1450        }
1451        let r = self.eval(code, body)?;
1452        let added = self.heap.cache.added;
1453        // A step site keeps an exact persistent copy of its result; one
1454        // that cannot be kept (lazy) is returned uncached.
1455        let kept = if s.step && r.is_transient() {
1456            self.heap.intern_exact(r).unwrap_or(r)
1457        } else {
1458            r
1459        };
1460        if s.candidate {
1461            self.charge_kept(site, added);
1462        }
1463        if !kept.is_transient() {
1464            self.memo.put(site, &key[..n], kept);
1465        }
1466        Ok(kept)
1467    }
1468
1469    /// Charges a candidate site for the store bytes this heap has added
1470    /// since `since` (`InternCache::added`, `Memo::charge_kept`).
1471    fn charge_kept(&mut self, site: u32, since: u64) {
1472        let bytes = self.heap.cache.added.saturating_sub(since);
1473        self.memo.charge_kept(site, bytes);
1474    }
1475
1476    fn call(&mut self, code: &Code, fun: u32, args: &[P]) -> Result<Handle, Error> {
1477        self.charge(1)?;
1478        if self.depth >= MAX_CALL_DEPTH {
1479            return Err(Error::unsupported(
1480                "Core recursive-call depth limit (64 activations)",
1481            ));
1482        }
1483        // Arguments can recursively call the same function too. Count their
1484        // activations and restore the counter on every success/error path.
1485        self.depth += 1;
1486        let result = self.call_inner(code, fun, args);
1487        self.depth -= 1;
1488        result
1489    }
1490
1491    fn call_inner(&mut self, code: &Code, fun: u32, args: &[P]) -> Result<Handle, Error> {
1492        let Some(f) = code.funs.get(fun as usize) else {
1493            return Err(Error::internal("call of an unknown function"));
1494        };
1495        let mut vals = self.take_scratch();
1496        for &a in args {
1497            match self.eval_norm(code, a) {
1498                Ok(v) => vals.push(v),
1499                Err(e) => {
1500                    self.give_scratch(vals);
1501                    return Err(e);
1502                }
1503            }
1504        }
1505        let cached = match &mut self.calls {
1506            Some(cache) if !self.heap.speculative => {
1507                let revision = self.heap.arena.cache_revision();
1508                if cache.revision != revision {
1509                    cache.results.clear();
1510                    cache.revision = revision;
1511                }
1512                cache.key.clear();
1513                cache.key.push(u64::from(fun));
1514                cache.key.extend(vals.iter().map(|h| h.0));
1515                if let Some(&r) = cache.results.get(cache.key.as_slice()) {
1516                    cache.hits += 1;
1517                    self.give_scratch(vals);
1518                    return Ok(r);
1519                }
1520                Some(cache.key.clone().into_boxed_slice())
1521            }
1522            _ => None,
1523        };
1524        let old = self.enter(f.frame);
1525        for (i, &v) in vals.iter().enumerate() {
1526            #[allow(
1527                clippy::cast_possible_truncation,
1528                reason = "parameter counts are small"
1529            )]
1530            let i = i as u32;
1531            let s = match i.checked_sub(f.params) {
1532                None => i,
1533                Some(c) => f.caps.get(c as usize).copied().unwrap_or(i),
1534            };
1535            self.set_slot(s, v);
1536        }
1537        self.give_scratch(vals);
1538        let r = self.eval(code, f.body);
1539        self.leave(old);
1540        if let (Some(key), Ok(h), Some(cache)) = (cached, &r, &mut self.calls)
1541            && cache.revision == self.heap.arena.cache_revision()
1542        {
1543            if cache.results.len() >= CALL_CACHE_ENTRIES {
1544                cache.results.clear();
1545            }
1546            cache.results.insert(key, *h);
1547        }
1548        r
1549    }
1550
1551    // ------------------------------------------------------------------
1552    // Sets
1553    // ------------------------------------------------------------------
1554
1555    /// Refuses a just-built set whose elements TLC cannot all compare
1556    /// (`compare::check_set`).
1557    fn checked_set(&self, s: Handle) -> Result<Handle, Error> {
1558        compare::require_materialized(&self.heap, &[s])?;
1559        if self.heap.store().semantics().tlc_comparisons && s.is_compound() {
1560            compare::check_set(&self.heap, self.heap.view(s).data)?;
1561        }
1562        Ok(s)
1563    }
1564
1565    /// TLC's error for a membership test of a value that is not a function
1566    /// in a set of functions, records, tuples or sequences.
1567    fn non_fcn_member(&self, x: Handle, what: &str) -> Result<bool, Error> {
1568        if x.is_compound() && self.heap.view(x).kind.is_fcn() {
1569            return Ok(false);
1570        }
1571        if x.as_model_id().is_some() {
1572            return self.mv_member(x);
1573        }
1574        Err(eval_err(&format!(
1575            "Attempted to check if a value that is not a function is in {what}"
1576        )))
1577    }
1578
1579    /// `ModelValue.modelValueMember`: an untyped model value is in no set of
1580    /// another kind; a typed one is TLC's error.
1581    fn mv_member(&self, x: Handle) -> Result<bool, Error> {
1582        if compare::mv_type(&self.heap, x).is_none() {
1583            return Ok(false);
1584        }
1585        Err(general(
1586            "Attempted to check if the typed model value is an element of a set of another kind",
1587        ))
1588    }
1589
1590    /// Whether `x` (normalized) is in `set`.
1591    ///
1592    /// # Errors
1593    /// `set` is not a set, or membership is undefined.
1594    #[allow(clippy::too_many_lines, reason = "one arm per set kind")]
1595    pub fn member(&mut self, x: Handle, set: Handle) -> Result<bool, Error> {
1596        if self.fuel != u64::MAX && set.is_compound() && self.heap.view(set).kind == Kind::SetEnum {
1597            self.domain_work(set, false, 0)?;
1598        }
1599        if !set.is_compound() {
1600            return Err(eval_err("membership in a value that is not a set"));
1601        }
1602        let kind = self.heap.view(set).kind;
1603        if kind != Kind::Set
1604            && kind != Kind::Product
1605            && kind != Kind::Subset
1606            && !self.opts.symbolic_member
1607            && self.heap.is_finite(set)
1608            && !self.heap.is_lazy(set)
1609        {
1610            let m = self.work_materialize_cached(set)?;
1611            return self.member(x, m);
1612        }
1613        let v = self.heap.view(set);
1614        match v.kind {
1615            Kind::Set => {
1616                let indexed = if self.fuel == u64::MAX && !v.is_lazy() {
1617                    self.memo.member_index.search(&self.heap, set, x, v.data)?
1618                } else {
1619                    None
1620                };
1621                if indexed.is_none() {
1622                    for h in [x, set] {
1623                        // A node carrying the cached proof takes the O(1)
1624                        // check; only the others scan the recorded proofs.
1625                        if !h.is_compound()
1626                            || self.heap.view(h).flags & crate::node::flags::CONCRETE != 0
1627                            || !self.proven(h)
1628                        {
1629                            compare::require_materialized(&self.heap, &[h])?;
1630                        }
1631                    }
1632                }
1633                if indexed
1634                    .unwrap_or_else(|| v.data.binary_search_by(|&e| self.heap.cmp(e, x)).is_ok())
1635                {
1636                    return Ok(true);
1637                }
1638                compare::miss_cached(&self.heap, &mut self.memo, x, set, v.data)?;
1639                Ok(false)
1640            }
1641            Kind::Interval => {
1642                let hi = v.data[0].as_int().unwrap_or(v.lo - 1);
1643                let lo = v.lo;
1644                match x.as_int() {
1645                    Some(i) => Ok(lo <= i && i <= hi),
1646                    // TLC answers FALSE for an empty interval, and for an
1647                    // untyped model value.
1648                    None if lo > hi => Ok(false),
1649                    None if x.as_model_id().is_some()
1650                        && compare::mv_type(&self.heap, x).is_none() =>
1651                    {
1652                        Ok(false)
1653                    }
1654                    // Bounds are inline, so a big integer is outside.
1655                    None if self.heap.is_int(x) => Ok(false),
1656                    None => Err(general(
1657                        "Attempted to check if the value:\na value that is not an integer\nis in the integer interval",
1658                    )),
1659                }
1660            }
1661            Kind::Nat | Kind::Int if self.heap.is_int(x) => Ok(match x.as_int() {
1662                Some(i) => v.kind == Kind::Int || i >= 0,
1663                // A big integer: in `Int`, and in `Nat` when positive.
1664                None => {
1665                    v.kind == Kind::Int
1666                        || self
1667                            .heap
1668                            .int_cmp(x, Handle::int(0).unwrap_or(Handle::EMPTY))
1669                            == Some(std::cmp::Ordering::Greater)
1670                }
1671            }),
1672            Kind::Nat | Kind::Int if x.as_model_id().is_some() => self.mv_member(x),
1673            Kind::Nat | Kind::Int => Err(eval_exc(
1674                2158,
1675                "Attempted to check if the value:\na value that is not an integer\nis an element of Nat or Int.",
1676            )),
1677            Kind::Subset => {
1678                let base = v.data[0];
1679                let query_kind = self.heap.kind(x);
1680                if !matches!(query_kind, Some(Kind::Set | Kind::SetEnum | Kind::Interval)) {
1681                    return Err(eval_err(
1682                        "Attempted to check if a non-enumerable value is an element of SUBSET",
1683                    ));
1684                }
1685                // SubsetValue.member demands the query's Enumerable.elements.
1686                // SetEnumValue's enumerator normalizes that actual receiver
1687                // before the first member call; it does not normalize the base.
1688                let mut elements = self.work_cursor(x)?;
1689                while let Some(e) = self.work_next(&mut elements)? {
1690                    if !self.member(e, base)? {
1691                        return Ok(false);
1692                    }
1693                }
1694                Ok(true)
1695            }
1696            Kind::SeqSet => {
1697                let base = v.data[0];
1698                if !x.is_compound() || !self.heap.view(x).kind.is_fcn() {
1699                    return self.non_fcn_member(x, "a set of sequences");
1700                }
1701                let xv = self.heap.view(x);
1702                if xv.kind != Kind::IntFcn || xv.lo != 1 {
1703                    // TLC fails on a function it cannot view as a tuple.
1704                    compare::guard_kind_member(
1705                        &self.heap,
1706                        "a membership test of a function that is not a sequence in Seq(S)",
1707                    )?;
1708                    return Ok(false);
1709                }
1710                let vals = xv.data.to_vec();
1711                for e in vals {
1712                    if !self.member(e, base)? {
1713                        return Ok(false);
1714                    }
1715                }
1716                Ok(true)
1717            }
1718            Kind::FcnSet => {
1719                let (dom, rng) = (v.data[0], v.data[1]);
1720                if !x.is_compound() || !self.heap.view(x).kind.is_fcn() {
1721                    return self.non_fcn_member(x, "a set of functions");
1722                }
1723                let d = self.domain(x)?;
1724                let d = self.work_norm(d)?;
1725                let dom = self.work_norm(dom)?;
1726                if !self.heap.eq(d, dom) {
1727                    // TLC compares the domains with `equals`, which may fail.
1728                    if self.heap.store().semantics().tlc_comparisons {
1729                        compare::equals(&self.heap, d, dom)?;
1730                    }
1731                    return Ok(false);
1732                }
1733                let vals = self.heap.view(x).values().to_vec();
1734                for e in vals {
1735                    if !self.member(e, rng)? {
1736                        return Ok(false);
1737                    }
1738                }
1739                Ok(true)
1740            }
1741            Kind::RecSet => {
1742                let n = v.data.len() / 2;
1743                let (names, sets) = (v.data[..n].to_vec(), v.data[n..].to_vec());
1744                if !x.is_compound() || !self.heap.view(x).kind.is_fcn() {
1745                    return self.non_fcn_member(x, "a set of records");
1746                }
1747                let xv = self.heap.view(x);
1748                if xv.kind != Kind::Fcn || xv.keys().iter().any(|k| k.as_str_id().is_none()) {
1749                    // TLC fails on a function it cannot view as a record.
1750                    compare::guard_kind_member(
1751                        &self.heap,
1752                        "a membership test of a function that is not a record in a set of records",
1753                    )?;
1754                    return Ok(false);
1755                }
1756                if xv.keys() != names.as_slice() {
1757                    return Ok(false);
1758                }
1759                let vals = xv.values().to_vec();
1760                for (e, s) in vals.into_iter().zip(sets) {
1761                    if !self.member(e, s)? {
1762                        return Ok(false);
1763                    }
1764                }
1765                Ok(true)
1766            }
1767            Kind::Product => {
1768                let sets = v.data.to_vec();
1769                if !x.is_compound() || !self.heap.view(x).kind.is_fcn() {
1770                    return self.non_fcn_member(x, "a set of tuples");
1771                }
1772                let xv = self.heap.view(x);
1773                if xv.kind == Kind::Fcn && xv.keys().iter().any(|k| k.as_int().is_none()) {
1774                    // TLC fails on a function over other values than integers.
1775                    compare::guard_kind_member(
1776                        &self.heap,
1777                        "a membership test of a function over non-integers in a set of tuples",
1778                    )?;
1779                }
1780                if xv.kind != Kind::IntFcn || xv.lo != 1 || xv.data.len() != sets.len() {
1781                    return Ok(false);
1782                }
1783                let vals = xv.data.to_vec();
1784                for (e, s) in vals.into_iter().zip(sets) {
1785                    if !self.member(e, s)? {
1786                        return Ok(false);
1787                    }
1788                }
1789                Ok(true)
1790            }
1791            Kind::IntFcn | Kind::Fcn | Kind::Lambda => Err(eval_err("membership in a function")),
1792            Kind::BigInt => Err(eval_err("membership in a value that is not a set")),
1793            // TLC's `SetCupValue.member`: either side, left first.
1794            Kind::Union => {
1795                let (a, b) = (v.data[0], v.data[1]);
1796                Ok(self.member(x, a)? || self.member(x, b)?)
1797            }
1798            Kind::SetPred => Err(Error::unsupported(
1799                "membership in a lazy set predicate (the evaluator side is not built)",
1800            )),
1801            // TLC's unnormalized `SetEnumValue.member` is a linear scan whose
1802            // errors differ from a sorted search; its compat-order
1803            // comparison is not built.
1804            Kind::SetEnum => Err(Error::unsupported(
1805                "membership in a set enumeration TLC has not normalized (--compat=tlc)",
1806            )),
1807        }
1808    }
1809
1810    fn set_bin(&mut self, op: SetOp, x: Handle, y: Handle) -> Result<Handle, Error> {
1811        let (x, y) = (self.work_norm(x)?, self.work_norm(y)?);
1812        let fx = self.heap.is_finite(x);
1813        let fy = self.heap.is_finite(y);
1814        for (s, finite) in [(x, fx), (y, fy)] {
1815            if finite && s.is_compound() {
1816                let n = self.heap.view(s).len();
1817                self.charge(n)?;
1818            }
1819        }
1820        match op {
1821            SetOp::Cup => {
1822                // TLC's `SetCupValue` stays lazy: membership is either
1823                // side's, and enumerating it fails as TLC's does.
1824                if !fx || !fy {
1825                    return Ok(self.heap.union(x, y));
1826                }
1827                if let Some(union) = self.union_concrete(x, y)? {
1828                    return self.checked_set(union);
1829                }
1830                let mut v = self.work_elements(x)?;
1831                v.extend(self.work_elements(y)?);
1832                let r = self.heap.set_from(&mut v);
1833                self.checked_set(r)
1834            }
1835            SetOp::Cap => {
1836                let (a, b) = if fx {
1837                    (x, y)
1838                } else if fy {
1839                    (y, x)
1840                } else {
1841                    return Err(Error::unsupported("intersection of infinite sets"));
1842                };
1843                let mut out = Vec::new();
1844                for e in self.work_elements(a)? {
1845                    if self.member(e, b)? {
1846                        out.push(e);
1847                    }
1848                }
1849                Ok(self.heap.set_sorted(&out))
1850            }
1851            SetOp::Minus => {
1852                if !fx {
1853                    return Err(Error::unsupported("difference of an infinite set"));
1854                }
1855                if let Some(r) = self.minus_small(x, y)? {
1856                    return Ok(r);
1857                }
1858                let mut out = Vec::new();
1859                for e in self.work_elements(x)? {
1860                    if !self.member(e, y)? {
1861                        out.push(e);
1862                    }
1863                }
1864                Ok(self.heap.set_sorted(&out))
1865            }
1866        }
1867    }
1868
1869    /// Merge canonical explicit operands; the caller retains identity/class checks.
1870    fn union_concrete(&mut self, x: Handle, y: Handle) -> Result<Option<Handle>, Error> {
1871        if !x.is_compound() || !y.is_compound() {
1872            return Ok(None);
1873        }
1874        let (left_view, right_view) = (self.heap.view(x), self.heap.view(y));
1875        if left_view.kind != Kind::Set
1876            || right_view.kind != Kind::Set
1877            || left_view.is_lazy()
1878            || right_view.is_lazy()
1879        {
1880            return Ok(None);
1881        }
1882        let capacity = left_view
1883            .data
1884            .len()
1885            .checked_add(right_view.data.len())
1886            .ok_or_else(|| Error::unsupported("set union address space"))?;
1887        let mut out = Vec::new();
1888        out.try_reserve_exact(capacity)
1889            .map_err(|_| Error::unsupported("set union allocation"))?;
1890        let (mut i, mut j) = (0, 0);
1891        while i < left_view.data.len() || j < right_view.data.len() {
1892            self.heap.work_poll()?;
1893            let value = match (left_view.data.get(i), right_view.data.get(j)) {
1894                (Some(&left), Some(&right)) => match self.heap.cmp(left, right) {
1895                    std::cmp::Ordering::Less => {
1896                        i += 1;
1897                        left
1898                    }
1899                    std::cmp::Ordering::Greater => {
1900                        j += 1;
1901                        right
1902                    }
1903                    std::cmp::Ordering::Equal => {
1904                        i += 1;
1905                        j += 1;
1906                        left
1907                    }
1908                },
1909                (Some(&left), None) => {
1910                    i += 1;
1911                    left
1912                }
1913                (None, Some(&right)) => {
1914                    j += 1;
1915                    right
1916                }
1917                (None, None) => return Err(Error::internal("union cursor past both operands")),
1918            };
1919            out.push(value);
1920        }
1921        Ok(Some(self.heap.set_sorted(&out)))
1922    }
1923
1924    /// `x \ y` for enumerated sets with `y` smaller than `x` (`S \ {e}` in
1925    /// a recursive fold): each element of `y` is looked up in `x`, instead
1926    /// of each element of `x` in `y`. The elements of `x` kept are checked
1927    /// against `y` as a failed membership test checks them
1928    /// ([`compare::miss`]), so errors are those of the general path.
1929    fn minus_small(&mut self, x: Handle, y: Handle) -> Result<Option<Handle>, Error> {
1930        if !x.is_compound() || !y.is_compound() {
1931            return Ok(None);
1932        }
1933        let (vx, vy) = (self.heap.view(x), self.heap.view(y));
1934        if vx.kind != Kind::Set || vy.kind != Kind::Set || vy.data.len() >= vx.data.len() {
1935            return Ok(None);
1936        }
1937        let (xs, ys) = (vx.data, vy.data);
1938        let mut drop = Vec::with_capacity(ys.len());
1939        for &z in ys {
1940            if let Ok(i) = xs.binary_search_by(|&e| self.heap.cmp(e, z)) {
1941                drop.push(i);
1942            }
1943        }
1944        drop.sort_unstable();
1945        let mut out = Vec::with_capacity(xs.len() - drop.len());
1946        for (i, &e) in xs.iter().enumerate() {
1947            if drop.binary_search(&i).is_err() {
1948                compare::miss(&self.heap, e, ys)?;
1949                out.push(e);
1950            }
1951        }
1952        Ok(Some(self.heap.set_sorted(&out)))
1953    }
1954
1955    fn filter(
1956        &mut self,
1957        code: &Code,
1958        bind: &Bind,
1959        pred: P,
1960        subset: Option<P>,
1961    ) -> Result<Handle, Error> {
1962        if let Some(mut cur) = self.subset_cursor(code, subset)? {
1963            let mut out = Vec::new();
1964            while let Some(e) = self.work_next(&mut cur)? {
1965                self.charge(1)?;
1966                out.push(e);
1967            }
1968            return Ok(self.heap.set_sorted(&out));
1969        }
1970        // The cursor enumerates a symbolic domain in canonical order without
1971        // materializing it.
1972        let dom = self.eval(code, bind.domain)?;
1973        let mut cur = self.work_cursor(dom)?;
1974        let mut out = Vec::new();
1975        loop {
1976            // Free a rejected candidate, and the predicate's transients, by
1977            // arena rollback. Only when no thunk was forced to a
1978            // transient meanwhile: its slot may hold a value built after the
1979            // mark.
1980            let before = self.heap.mark();
1981            let Some(e) = self.work_next(&mut cur)? else {
1982                break;
1983            };
1984            self.charge(1)?;
1985            let after = self.heap.mark();
1986            let forced = self.thunk_mark();
1987            self.bind_one(bind, e)?;
1988            let keep = self.eval_bool(code, pred)?;
1989            if self.thunks_released(forced) {
1990                if keep {
1991                    self.heap.rollback(after);
1992                } else {
1993                    self.heap.rollback(before);
1994                }
1995            }
1996            if keep {
1997                out.push(e);
1998            }
1999        }
2000        Ok(self.heap.set_sorted(&out))
2001    }
2002
2003    /// The cursor over `SUBSET F` of a proven filter rewrite
2004    /// (`Node::Filter::subset`), whose elements are exactly the filter's,
2005    /// in the same canonical order (the subsets of `F` keep their relative
2006    /// order among those of its superset). An evaluation error while
2007    /// building `F` declines, so that the filter itself raises the error
2008    /// TLC raises, where it raises it; `F`'s predicate is pure, so
2009    /// evaluating it again is unobservable.
2010    pub(crate) fn subset_cursor(
2011        &mut self,
2012        code: &Code,
2013        subset: Option<P>,
2014    ) -> Result<Option<Cursor>, Error> {
2015        let Some(set) = subset else {
2016            return Ok(None);
2017        };
2018        let before = self.heap.mark();
2019        let forced = self.thunk_mark();
2020        match self.eval_norm(code, set) {
2021            Ok(f) => {
2022                let powerset = self.heap.symbolic(Kind::Subset, 0, &[f]);
2023                self.work_cursor(powerset).map(Some)
2024            }
2025            Err(e) if e.kind() == crate::ErrorKind::Eval => {
2026                if self.thunks_released(forced) {
2027                    self.heap.rollback(before);
2028                }
2029                Ok(None)
2030            }
2031            Err(e) => Err(e),
2032        }
2033    }
2034
2035    /// Binds one domain element to a bound group of one variable or a tuple
2036    /// pattern.
2037    pub(crate) fn bind_one(&mut self, bind: &Bind, e: Handle) -> Result<(), Error> {
2038        if bind.tuple {
2039            let v = self.heap.view(e);
2040            if v.kind != Kind::IntFcn || v.lo != 1 || v.data.len() != bind.slots.len() {
2041                return Err(eval_err("a tuple pattern does not match the element"));
2042            }
2043            let parts = v.data.to_vec();
2044            for (&s, p) in bind.slots.iter().zip(parts) {
2045                self.set_slot(s, p);
2046            }
2047        } else if let Some(&s) = bind.slots.first() {
2048            self.set_slot(s, e);
2049        }
2050        Ok(())
2051    }
2052
2053    /// The binding units of bound groups: one per variable of a plain group,
2054    /// one per tuple-pattern group; each with its domain's elements.
2055    pub(crate) fn units(
2056        &mut self,
2057        code: &Code,
2058        binds: &[Bind],
2059    ) -> Result<Vec<(Unit, Vec<Handle>)>, Error> {
2060        let mut out = Vec::new();
2061        for (bi, b) in binds.iter().enumerate() {
2062            let d = match code.nodes.get(b.domain as usize) {
2063                // A plan constant's enumeration is built once (bosco's
2064                // `\E r \in SUBSET (P \X M)`).
2065                Some(Node::Const(h)) if self.fuel == u64::MAX => {
2066                    self.heap.enumerate_constant(*h)?
2067                }
2068                _ => {
2069                    let d = self.eval(code, b.domain)?;
2070                    self.work_norm(d)?
2071                }
2072            };
2073            let elems = self.work_elements(d)?;
2074            if b.tuple {
2075                out.push((
2076                    Unit {
2077                        bind: bi,
2078                        var: None,
2079                    },
2080                    elems,
2081                ));
2082            } else {
2083                for vi in 0..b.slots.len() {
2084                    self.charge(elems.len() + 1)?;
2085                    out.push((
2086                        Unit {
2087                            bind: bi,
2088                            var: Some(vi),
2089                        },
2090                        elems.clone(),
2091                    ));
2092                }
2093            }
2094        }
2095        Ok(out)
2096    }
2097
2098    pub(crate) fn bind_unit(&mut self, binds: &[Bind], u: Unit, e: Handle) -> Result<(), Error> {
2099        let b = &binds[u.bind];
2100        match u.var {
2101            Some(vi) => {
2102                self.set_slot(b.slots[vi], e);
2103                Ok(())
2104            }
2105            None => self.bind_one(b, e),
2106        }
2107    }
2108
2109    /// Visits every binding of the bound groups, the first variable fastest
2110    /// (TLC's `ContextEnumerator`), until `f` returns `false`.
2111    pub(crate) fn for_each_binding(
2112        &mut self,
2113        code: &Code,
2114        binds: &[Bind],
2115        f: &mut dyn FnMut(&mut Self) -> Result<bool, Error>,
2116    ) -> Result<bool, Error> {
2117        if self.fuel != u64::MAX {
2118            return self.binding_stream(code, binds, f);
2119        }
2120        let units = self.units(code, binds)?;
2121        if units.iter().any(|(_, e)| e.is_empty()) {
2122            return Ok(true);
2123        }
2124        let mut idx = vec![0usize; units.len()];
2125        loop {
2126            self.charge(1)?;
2127            for (k, (u, elems)) in units.iter().enumerate() {
2128                self.bind_unit(binds, *u, elems[idx[k]])?;
2129            }
2130            if !f(self)? {
2131                return Ok(false);
2132            }
2133            let mut k = 0;
2134            loop {
2135                if k == units.len() {
2136                    return Ok(true);
2137                }
2138                idx[k] += 1;
2139                if idx[k] < units[k].1.len() {
2140                    break;
2141                }
2142                idx[k] = 0;
2143                k += 1;
2144            }
2145        }
2146    }
2147
2148    fn quant(
2149        &mut self,
2150        code: &Code,
2151        kind: Quant,
2152        binds: &[Bind],
2153        body: P,
2154    ) -> Result<Handle, Error> {
2155        match kind {
2156            Quant::Exists => {
2157                let mut found = false;
2158                self.for_each_binding(code, binds, &mut |m: &mut Self| {
2159                    if m.eval_bool(code, body)? {
2160                        found = true;
2161                        return Ok(false);
2162                    }
2163                    Ok(true)
2164                })?;
2165                Ok(Handle::bool(found))
2166            }
2167            Quant::Forall => {
2168                let all = self
2169                    .for_each_binding(code, binds, &mut |m: &mut Self| m.eval_bool(code, body))?;
2170                Ok(Handle::bool(all))
2171            }
2172            Quant::Choose => {
2173                if binds.len() != 1 || (!binds[0].tuple && binds[0].slots.len() != 1) {
2174                    return Err(Error::unsupported("CHOOSE with several bound variables"));
2175                }
2176                let d = self.eval(code, binds[0].domain)?;
2177                let mut cur = self.work_cursor(d)?;
2178                loop {
2179                    // Free a rejected candidate, and the predicate's
2180                    // transients, by arena rollback, as `filter` does.
2181                    let before = self.heap.mark();
2182                    let Some(e) = self.work_next(&mut cur)? else {
2183                        break;
2184                    };
2185                    self.charge(1)?;
2186                    let forced = self.thunk_mark();
2187                    self.bind_one(&binds[0], e)?;
2188                    if self.eval_bool(code, body)? {
2189                        return Ok(e);
2190                    }
2191                    if self.thunks_released(forced) {
2192                        self.heap.rollback(before);
2193                    }
2194                }
2195                Err(general(
2196                    "Attempted to compute the value of an expression of form\nCHOOSE x \\in S: P, but no element of S satisfied P.",
2197                ))
2198            }
2199        }
2200    }
2201
2202    fn fcn_cons(&mut self, code: &Code, binds: &[Bind], body: P) -> Result<Handle, Error> {
2203        let units = self.units(code, binds)?;
2204        if units.len() == 1 {
2205            let (u, keys) = units
2206                .into_iter()
2207                .next()
2208                .unwrap_or((Unit { bind: 0, var: None }, Vec::new()));
2209            self.charge(keys.len())?;
2210            let mut vals = Vec::with_capacity(keys.len());
2211            for &k in &keys {
2212                self.bind_unit(binds, u, k)?;
2213                vals.push(self.eval_component(code, body)?);
2214            }
2215            return Ok(self.heap.fcn_sorted(&keys, &vals));
2216        }
2217        if units.iter().any(|(u, _)| u.var.is_none()) {
2218            return Err(Error::unsupported(
2219                "a function constructor mixing tuple patterns and several bounds",
2220            ));
2221        }
2222        // Keys are tuples of the units' values, in canonical order (last
2223        // component fastest).
2224        let mut keys = Vec::new();
2225        let mut vals = Vec::new();
2226        if units.iter().any(|(_, e)| e.is_empty()) {
2227            return Ok(self.heap.fcn_sorted(&[], &[]));
2228        }
2229        let mut idx = vec![0usize; units.len()];
2230        'outer: loop {
2231            self.charge(1)?;
2232            let comps: Vec<Handle> = idx.iter().zip(&units).map(|(&i, (_, e))| e[i]).collect();
2233            for (k, (u, _)) in units.iter().enumerate() {
2234                self.bind_unit(binds, *u, comps[k])?;
2235            }
2236            keys.push(self.heap.tuple(&comps));
2237            vals.push(self.eval_component(code, body)?);
2238            let mut k = units.len();
2239            loop {
2240                if k == 0 {
2241                    break 'outer;
2242                }
2243                k -= 1;
2244                idx[k] += 1;
2245                if idx[k] < units[k].1.len() {
2246                    break;
2247                }
2248                idx[k] = 0;
2249            }
2250        }
2251        Ok(self.heap.fcn_sorted(&keys, &vals))
2252    }
2253
2254    // ------------------------------------------------------------------
2255    // Functions and records
2256    // ------------------------------------------------------------------
2257
2258    /// The index of `key` in function `f`, if present.
2259    pub(crate) fn fcn_index(&self, f: Handle, key: Handle) -> Result<Option<usize>, Error> {
2260        if !f.is_compound() {
2261            return Err(eval_err("application of a value that is not a function"));
2262        }
2263        let v = self.heap.view(f);
2264        match v.kind {
2265            Kind::IntFcn => Ok(key.as_int().and_then(|k| {
2266                let i = k.checked_sub(v.lo)?;
2267                usize::try_from(i).ok().filter(|&i| i < v.data.len())
2268            })),
2269            Kind::Fcn => {
2270                let keys = v.keys();
2271                if key.as_str_id().is_some() || keys.len() <= 8 {
2272                    Ok(keys.iter().position(|&k| self.heap.eq(k, key)))
2273                } else if let Some(i) = self.grid_index(keys, key) {
2274                    Ok(Some(i))
2275                } else {
2276                    Ok(keys.binary_search_by(|&k| self.heap.cmp(k, key)).ok())
2277                }
2278            }
2279            _ => Err(eval_err("application of a set as a function")),
2280        }
2281    }
2282
2283    /// The position of the pair `<<a, b>>` of integers in the keys of a
2284    /// function whose domain is a dense rectangle `l1..h1 \X l2..h2` in
2285    /// canonical order (`grid` and `sc` in `GameOfLife`): computed, then
2286    /// checked against the key found there. `None` sends the caller to the
2287    /// binary search, so a domain of another shape is still exact.
2288    fn grid_index(&self, keys: &[Handle], key: Handle) -> Option<usize> {
2289        let (row, col) = self.int_pair(key)?;
2290        let (l1, l2) = self.int_pair(*keys.first()?)?;
2291        let (h1, h2) = self.int_pair(*keys.last()?)?;
2292        let rows = usize::try_from(h1.checked_sub(l1)?.checked_add(1)?).ok()?;
2293        let width = usize::try_from(h2.checked_sub(l2)?.checked_add(1)?).ok()?;
2294        if rows.checked_mul(width)? != keys.len()
2295            || !(l1..=h1).contains(&row)
2296            || !(l2..=h2).contains(&col)
2297        {
2298            return None;
2299        }
2300        let at = usize::try_from(row - l1).ok()? * width + usize::try_from(col - l2).ok()?;
2301        let k = *keys.get(at)?;
2302        self.heap.eq(k, key).then_some(at)
2303    }
2304
2305    /// `<<a, b>>` for a pair of small integers.
2306    fn int_pair(&self, h: Handle) -> Option<(i64, i64)> {
2307        if !h.is_compound() {
2308            return None;
2309        }
2310        let v = self.heap.view(h);
2311        match (v.kind, v.lo, v.data) {
2312            (Kind::IntFcn, 1, &[a, b]) => Some((a.as_int()?, b.as_int()?)),
2313            _ => None,
2314        }
2315    }
2316
2317    /// `f[a]`.
2318    ///
2319    /// # Errors
2320    /// `a` is not in the domain of `f`.
2321    pub fn apply(&mut self, f: Handle, a: Handle) -> Result<Handle, Error> {
2322        if let Some(i) = self.fcn_index(f, a)? {
2323            return Ok(self.heap.view(f).values()[i]);
2324        }
2325        let msg = "Attempted to apply function to an argument not in its domain";
2326        let v = self.heap.view(f);
2327        match v.kind {
2328            // TLC compares the argument with the domain on the way: a value
2329            // of another class fails that comparison first.
2330            Kind::Fcn => {
2331                compare::miss(&self.heap, a, v.keys())?;
2332                Err(general(msg))
2333            }
2334            Kind::IntFcn if a.as_int().is_some() => Err(general(msg)),
2335            _ => Err(eval_err(msg)),
2336        }
2337    }
2338
2339    fn select(&mut self, r: Handle, field: Handle) -> Result<Handle, Error> {
2340        if !r.is_compound() {
2341            return Err(eval_err("field selection on a value that is not a record"));
2342        }
2343        let v = self.heap.view(r);
2344        if v.kind == Kind::Fcn
2345            && let Some(i) = v.keys().iter().position(|&k| k == field)
2346        {
2347            return Ok(v.values()[i]);
2348        }
2349        Err(eval_err(
2350            "Attempted to access a record field that does not exist",
2351        ))
2352    }
2353
2354    fn domain(&mut self, f: Handle) -> Result<Handle, Error> {
2355        if !f.is_compound() {
2356            return Err(eval_err("DOMAIN of a value that is not a function"));
2357        }
2358        let len = self.heap.view(f).len();
2359        self.charge(len.saturating_mul(2))?;
2360        let v = self.heap.view(f);
2361        match v.kind {
2362            #[allow(clippy::cast_possible_wrap, reason = "domains fit in i64")]
2363            Kind::IntFcn => {
2364                let (lo, n) = (v.lo, v.data.len() as i64);
2365                if n == 0 {
2366                    return Ok(self.heap.empty_set());
2367                }
2368                let mut out = Vec::with_capacity(v.data.len());
2369                for k in lo..lo + n {
2370                    out.push(mk_int(k)?);
2371                }
2372                Ok(self.heap.set_sorted(&out))
2373            }
2374            Kind::Fcn => {
2375                let keys = v.keys().to_vec();
2376                Ok(self.heap.set_sorted(&keys))
2377            }
2378            _ => Err(eval_err("DOMAIN of a set")),
2379        }
2380    }
2381
2382    fn except(
2383        &mut self,
2384        code: &Code,
2385        f: Handle,
2386        u: &Update,
2387        depth: usize,
2388    ) -> Result<Handle, Error> {
2389        let Some(&step) = u.path.get(depth) else {
2390            return Err(Error::internal("EXCEPT path out of range"));
2391        };
2392        let key = self.eval_norm(code, step)?;
2393        if !f.is_compound() || !self.heap.view(f).kind.is_fcn() {
2394            return Err(eval_err("EXCEPT on a value that is not a function"));
2395        }
2396        self.charge(self.heap.view(f).len())?;
2397        let Some(i) = self.fcn_index(f, key)? else {
2398            // TLC leaves the function unchanged when the key is outside its
2399            // domain, but fails when it had to compare the key with a domain
2400            // value of another class on the way.
2401            let v = self.heap.view(f);
2402            if v.kind == Kind::IntFcn {
2403                if key.as_int().is_none() && !v.data.is_empty() {
2404                    return Err(eval_err(
2405                        "Attempted to apply EXCEPT to a tuple at a non-integral index",
2406                    ));
2407                }
2408            } else {
2409                compare::miss(&self.heap, key, v.keys())?;
2410            }
2411            if self.refuse_unrecorded_warnings {
2412                return Err(Error::unsupported(
2413                    "an EXCEPT key outside the function's domain, where the reference prints warning 2144",
2414                ));
2415            }
2416            return Ok(f);
2417        };
2418        let old = self.heap.view(f).values()[i];
2419        let new = if depth + 1 == u.path.len() {
2420            self.set_slot(u.at, old);
2421            self.eval_component(code, u.value)?
2422        } else {
2423            self.except(code, old, u, depth + 1)?
2424        };
2425        if new == old {
2426            return Ok(f);
2427        }
2428        self.charge(self.heap.view(f).data.len())?;
2429        Ok(self.heap.fcn_with(f, i, new))
2430    }
2431
2432    // ------------------------------------------------------------------
2433    // Standard operators
2434    // ------------------------------------------------------------------
2435
2436    fn seq_vals(&mut self, s: Handle) -> Result<Vec<Handle>, Error> {
2437        if !s.is_compound() {
2438            return Err(eval_err("expected a sequence"));
2439        }
2440        let v = self.heap.view(s);
2441        if v.kind != Kind::IntFcn || v.lo != 1 {
2442            return Err(eval_err("expected a sequence"));
2443        }
2444        let len = v.data.len();
2445        self.charge(len)?;
2446        Ok(self.heap.view(s).data.to_vec())
2447    }
2448
2449    /// Bags (`tlc2.module.Bags`; as in `dive-eval`'s `community` module).
2450    fn bag(&mut self, op: StdFn, args: &[Handle]) -> Result<Handle, Error> {
2451        let arg = |i: usize| {
2452            args.get(i)
2453                .copied()
2454                .ok_or_else(|| Error::internal("missing argument"))
2455        };
2456        match op {
2457            StdFn::EmptyBag => Ok(self.heap.fcn_sorted(&[], &[])),
2458            StdFn::SetToBag => {
2459                let set = arg(0)?;
2460                if !set.is_compound()
2461                    || matches!(self.heap.view(set).kind, Kind::Fcn | Kind::IntFcn)
2462                {
2463                    return Err(eval_err(
2464                        "The argument of SetToBag should be a finite set, but instead it is not",
2465                    ));
2466                }
2467                let keys = self.work_elements(set)?;
2468                let one = mk_int(1)?;
2469                let ones = vec![one; keys.len()];
2470                Ok(self.heap.fcn_sorted(&keys, &ones))
2471            }
2472            StdFn::BagToSet => {
2473                let bag = arg(0)?;
2474                if !bag.is_compound()
2475                    || !matches!(self.heap.view(bag).kind, Kind::Fcn | Kind::IntFcn)
2476                {
2477                    return Err(eval_err(
2478                        "The argument of BagToSet should be a function with a finite domain",
2479                    ));
2480                }
2481                self.domain(bag)
2482            }
2483            StdFn::BagIn | StdFn::CopiesIn => {
2484                let (elem, bag) = (arg(0)?, arg(1)?);
2485                if !bag.is_compound()
2486                    || !matches!(self.heap.view(bag).kind, Kind::Fcn | Kind::IntFcn)
2487                {
2488                    return Err(eval_err("BagIn or CopiesIn of a value that is not a bag"));
2489                }
2490                // TLC compares the element with the bag's domain in order:
2491                // an element of another class is an error.
2492                let dom = self.domain(bag)?;
2493                if !self.member(elem, dom)? {
2494                    return Ok(if op == StdFn::BagIn {
2495                        Handle::bool(false)
2496                    } else {
2497                        mk_int(0)?
2498                    });
2499                }
2500                let count = self.apply(bag, elem)?;
2501                let n = count
2502                    .as_int()
2503                    .ok_or_else(|| eval_err("The second argument of BagIn should be a bag"))?;
2504                Ok(if op == StdFn::BagIn {
2505                    Handle::bool(n > 0)
2506                } else {
2507                    count
2508                })
2509            }
2510            _ => Err(Error::internal("not a Bags operator")),
2511        }
2512    }
2513
2514    /// `Len(s)`: a sequence's length, or a string's in UTF-16 units, as
2515    /// Java counts.
2516    fn len(&mut self, s: Handle) -> Result<Handle, Error> {
2517        if let Some(id) = s.as_str_id() {
2518            let text = self
2519                .heap
2520                .store()
2521                .strings()
2522                .text(id)
2523                .ok_or_else(|| Error::internal("unknown string"))?;
2524            // UTF-8 byte length is O(1) and bounds UTF-16 traversal work.
2525            // Charge before scanning; the returned length remains Java's.
2526            self.charge(text.len())?;
2527            return mk_int(i64::try_from(text.encode_utf16().count()).unwrap_or(i64::MAX));
2528        }
2529        // Only a compound handle has a node to view.
2530        if !s.is_compound() {
2531            return Err(one_arg("Len", "sequence"));
2532        }
2533        let v = self.heap.view(s);
2534        if v.kind != Kind::IntFcn || v.lo != 1 {
2535            return Err(one_arg("Len", "sequence"));
2536        }
2537        mk_int(i64::try_from(v.data.len()).unwrap_or(i64::MAX))
2538    }
2539
2540    fn std_arg(&mut self, code: &Code, f: StdFn, index: usize, x: P) -> Result<Handle, Error> {
2541        // Finiteness dispatch must inspect the original receiver before an
2542        // eager projection can erase its range methods or their demand.
2543        let value = if matches!(f, StdFn::IsFiniteSet | StdFn::Cardinality | StdFn::Seq) {
2544            self.eval(code, x)?
2545        } else {
2546            self.eval_component(code, x)?
2547        };
2548        let product = self.heap.kind(value) == Some(Kind::Product);
2549        if matches!(f, StdFn::Seq | StdFn::IsFiniteSet)
2550            || (f == StdFn::Append && index == 1)
2551            || (product && matches!(f, StdFn::Cardinality | StdFn::IsFiniteSet | StdFn::Seq))
2552        {
2553            Ok(value)
2554        } else {
2555            self.work_norm(value)
2556        }
2557    }
2558
2559    fn std(&mut self, code: &Code, f: StdFn, args: &[P]) -> Result<Handle, Error> {
2560        let mut a = Vec::with_capacity(args.len());
2561        for (index, &x) in args.iter().enumerate() {
2562            a.push(self.std_arg(code, f, index, x)?);
2563        }
2564        let arg = |i: usize| {
2565            a.get(i)
2566                .copied()
2567                .ok_or_else(|| Error::internal("missing argument"))
2568        };
2569        match f {
2570            StdFn::Len => self.len(arg(0)?),
2571            StdFn::Head => {
2572                let vals = self.seq_vals(arg(0)?)?;
2573                vals.first()
2574                    .copied()
2575                    .ok_or_else(|| eval_exc(2184, "Attempted to apply Head to the empty sequence."))
2576            }
2577            StdFn::Tail => {
2578                let vals = self.seq_vals(arg(0)?)?;
2579                if vals.is_empty() {
2580                    return Err(eval_exc(
2581                        2184,
2582                        "Attempted to apply Tail to the empty sequence.",
2583                    ));
2584                }
2585                Ok(self.heap.tuple(&vals[1..]))
2586            }
2587            StdFn::Append => {
2588                let mut vals = self.seq_vals(arg(0)?)?;
2589                vals.push(arg(1)?);
2590                Ok(self.heap.tuple(&vals))
2591            }
2592            StdFn::Concat => {
2593                let mut vals = self.seq_vals(arg(0)?)?;
2594                vals.extend(self.seq_vals(arg(1)?)?);
2595                Ok(self.heap.tuple(&vals))
2596            }
2597            StdFn::SubSeq => {
2598                let vals = self.seq_vals(arg(0)?)?;
2599                let m = int_of(arg(1)?)?;
2600                let n = int_of(arg(2)?)?;
2601                if m > n {
2602                    return Ok(self.heap.tuple(&[]));
2603                }
2604                let len = i64::try_from(vals.len()).unwrap_or(i64::MAX);
2605                if m < 1 || n > len {
2606                    return Err(eval_err("SubSeq indices out of range"));
2607                }
2608                #[allow(
2609                    clippy::cast_sign_loss,
2610                    clippy::cast_possible_truncation,
2611                    reason = "checked range"
2612                )]
2613                Ok(self.heap.tuple(&vals[(m - 1) as usize..n as usize]))
2614            }
2615            StdFn::Cardinality => {
2616                let s = arg(0)?;
2617                if self.heap.kind(s) == Some(Kind::Set) {
2618                    compare::require_materialized(&self.heap, &[s])?;
2619                }
2620                if self.heap.kind(s) == Some(Kind::Product) {
2621                    return self.product_cardinality(s);
2622                }
2623                let kind = self.heap.kind(s);
2624                match kind {
2625                    // Not enumerable in TLC.
2626                    None | Some(Kind::IntFcn | Kind::Fcn | Kind::Nat | Kind::Int) => {
2627                        return Err(cardinality_error());
2628                    }
2629                    Some(Kind::SeqSet) => {
2630                        return Err(Error::unsupported("Cardinality of Seq(S) (M1 core)"));
2631                    }
2632                    Some(_) if !self.heap.is_finite(s) => return Err(cardinality_error()),
2633                    Some(_) => {}
2634                }
2635                let n = self.work_cardinality(s)?;
2636                mk_int(i64::try_from(n).unwrap_or(i64::MAX))
2637            }
2638            StdFn::Seq => {
2639                let s = arg(0)?;
2640                Ok(self.heap.symbolic(Kind::SeqSet, 0, &[s]))
2641            }
2642            StdFn::IsFiniteSet => self.symbolic_finiteness(arg(0)?).map(Handle::bool),
2643            StdFn::EmptyBag
2644            | StdFn::SetToBag
2645            | StdFn::BagToSet
2646            | StdFn::BagIn
2647            | StdFn::CopiesIn => self.bag(f, &a),
2648        }
2649    }
2650}
2651
2652/// A binding unit (see [`Machine::units`]).
2653#[derive(Clone, Copy, Debug)]
2654pub(crate) struct Unit {
2655    pub(crate) bind: usize,
2656    pub(crate) var: Option<usize>,
2657}
2658
2659/// The plan's operator as the heap's.
2660const fn int_op(op: Arith) -> IntOp {
2661    match op {
2662        Arith::Add => IntOp::Add,
2663        Arith::Sub => IntOp::Sub,
2664        Arith::Mul => IntOp::Mul,
2665        Arith::Div => IntOp::Div,
2666        Arith::DivNaturals => IntOp::DivNaturals,
2667        Arith::Mod => IntOp::Mod,
2668        Arith::Pow => IntOp::Pow,
2669    }
2670}
2671
2672/// Integer arithmetic on inline operands when its result is certain to be
2673/// inline and error-free in `mode`; `None` sends it to
2674/// [`crate::Heap::int_arith`], which handles every other case exactly.
2675fn fast_arith(op: Arith, x: i64, y: i64, mode: IntMode) -> Option<Handle> {
2676    let r = match op {
2677        Arith::Add => x.checked_add(y)?,
2678        Arith::Sub => x.checked_sub(y)?,
2679        Arith::Mul => x.checked_mul(y)?,
2680        // Floored division; in TLC mode only where `Naturals` and
2681        // `Integers` agree.
2682        Arith::Div | Arith::DivNaturals if y > 0 && (mode == IntMode::Big || x >= 0) => {
2683            x.div_euclid(y)
2684        }
2685        Arith::Mod if y > 0 => x.rem_euclid(y),
2686        _ => return None,
2687    };
2688    if mode == IntMode::Tlc && i32::try_from(r).is_err() {
2689        return None;
2690    }
2691    Handle::int(r)
2692}
2693
2694#[cfg(test)]
2695#[path = "eval_union_tests.rs"]
2696mod union_tests;
2697
2698#[cfg(test)]
2699mod tests {
2700    #![allow(clippy::unwrap_used, reason = "tests")]
2701    use super::*;
2702    use crate::TlcClass;
2703
2704    /// A primed definition's site (`MemoSite::candidate`) sees a new
2705    /// primed key value for every enumeration candidate. Its persistent
2706    /// copies are bounded by the memo cap (#869 review), never one per
2707    /// candidate, and its results are those of the body throughout.
2708    #[test]
2709    fn candidate_site_copies_stay_within_the_memo_cap() {
2710        use crate::plan::{Code, MemoSite};
2711        let cap = 64 << 10;
2712        let store = Arc::new(Store::new(true));
2713        let opts = Opts {
2714            memo_cap: cap,
2715            ..Opts::default()
2716        };
2717        let mut m = Machine::new(Arc::clone(&store), 1, opts, Memo::new(&[1]));
2718        let code = Code {
2719            nodes: vec![
2720                Node::Primed(0),
2721                Node::Tuple(vec![0, 0].into()),
2722                Node::Memo { site: 0, body: 1 },
2723            ],
2724            sites: vec![MemoSite {
2725                name: "F (Primed, action)".into(),
2726                vars: vec![].into(),
2727                slots: vec![].into(),
2728                primed: vec![0].into(),
2729                step: true,
2730                candidate: true,
2731            }],
2732            ..Code::default()
2733        };
2734        let before = store.stats().nodes;
2735        let candidates: i64 = 20_000;
2736        for i in 0..candidates {
2737            let items: Vec<Handle> = (0..6).map(|k| Handle::int(i * 8 + k).unwrap()).collect();
2738            let x = m.heap.tuple(&items);
2739            m.s1[0] = x;
2740            let expected = m.heap.tuple(&[x, x]);
2741            for _ in 0..4 {
2742                let r = m.eval(&code, 2).unwrap();
2743                assert!(
2744                    compare::equals(&m.heap, r, expected).unwrap(),
2745                    "candidate {i}"
2746                );
2747            }
2748            m.s1[0] = Handle::EMPTY;
2749            m.heap.reset();
2750        }
2751        let added = store.stats().nodes - before;
2752        // Each candidate's key and result are two nodes of 6 and 2 handles:
2753        // copying every one would add `2 * candidates` nodes.
2754        assert!(
2755            added < 2 * candidates.unsigned_abs() / 4,
2756            "{added} persistent nodes"
2757        );
2758        assert!(!m.memo.may_keep());
2759        assert!(m.memo.stats()[0].off);
2760        assert!(m.memo.stats()[0].hits > 0);
2761    }
2762
2763    #[test]
2764    fn a_transient_bound_stops_an_evaluation_by_name() {
2765        let mut m = Machine::new(
2766            Arc::new(Store::with_semantics(true, crate::Semantics::default())),
2767            0,
2768            Opts::default(),
2769            Memo::new(&[]),
2770        );
2771        let one = Handle::int(1).unwrap();
2772        assert_eq!(m.charge(1), Ok(()));
2773        m.set_transient_bound(4096);
2774        while m.heap.arena.footprint() <= 4096 {
2775            m.heap.tuple(&[one, one, one, one]);
2776        }
2777        let error = m.charge(1).unwrap_err();
2778        assert_eq!(error.kind(), crate::ErrorKind::Unsupported);
2779        assert!(error.message().contains("start-up evaluation memory bound"));
2780        m.set_transient_bound(usize::MAX);
2781        assert_eq!(m.charge(1), Ok(()));
2782        m.heap.reset();
2783        m.heap.arena.release();
2784        assert_eq!(m.heap.arena.footprint(), 0);
2785    }
2786
2787    #[test]
2788    fn sequences_keep_the_original_product_range_and_its_member_demand() {
2789        for tlc in [false, true] {
2790            let semantics = if tlc {
2791                crate::Semantics::tlc()
2792            } else {
2793                crate::Semantics::default()
2794            };
2795            let mut m = Machine::new(
2796                Arc::new(Store::with_semantics(true, semantics)),
2797                1,
2798                Opts::default(),
2799                Memo::new(&[]),
2800            );
2801            let zero = Handle::int(0).unwrap();
2802            let empty = m.heap.interval(0, -1);
2803            let product = m.heap.symbolic(Kind::Product, 0, &[empty, zero]);
2804            let code = Code {
2805                nodes: vec![Node::Const(product), Node::Std(StdFn::Seq, vec![0].into())],
2806                ..Code::default()
2807            };
2808            let sequences = m.eval(&code, 1).unwrap();
2809            assert_eq!(m.heap.view(sequences).kind, Kind::SeqSet);
2810            assert_eq!(m.heap.view(sequences).data, &[product]);
2811            assert_eq!(m.heap.view(product).data, &[empty, zero]);
2812            let empty_sequence = m.heap.tuple(&[]);
2813            assert_eq!(m.member(empty_sequence, sequences), Ok(true));
2814            let scalar_sequence = m.heap.tuple(&[zero]);
2815            let error = m.member(scalar_sequence, sequences).unwrap_err();
2816            assert_eq!(error.kind(), crate::ErrorKind::Eval);
2817            assert!(error.message().contains("not a function"));
2818            assert_eq!(m.heap.view(sequences).data, &[product]);
2819
2820            let mut values = vec![zero];
2821            let nonempty = m.heap.set_from(&mut values);
2822            let malformed = m.heap.symbolic(Kind::Product, 0, &[nonempty, zero]);
2823            let code = Code {
2824                nodes: vec![
2825                    Node::Const(malformed),
2826                    Node::Std(StdFn::Seq, vec![0].into()),
2827                ],
2828                ..Code::default()
2829            };
2830            let sequences = m.eval(&code, 1).unwrap();
2831            assert_eq!(m.member(empty_sequence, sequences), Ok(true));
2832            let element = m.heap.tuple(&[zero, zero]);
2833            let nonempty_sequence = m.heap.tuple(&[element]);
2834            let error = m.member(nonempty_sequence, sequences).unwrap_err();
2835            assert_eq!(error.kind(), crate::ErrorKind::Eval);
2836            assert!(error.message().contains("not a set"));
2837            assert_eq!(m.heap.view(sequences).data, &[malformed]);
2838        }
2839    }
2840
2841    #[test]
2842    fn public_cap_shrink_and_memo_move_cannot_add_over_budget_certificates() {
2843        let one = Handle::int(1).unwrap();
2844        let two = Handle::int(2).unwrap();
2845        for warm_first in [false, true] {
2846            let store = Arc::new(Store::with_semantics(true, crate::Semantics::tlc()));
2847            let mut m = Machine::new(
2848                store.clone(),
2849                0,
2850                Opts {
2851                    memo_cap: 2048,
2852                    ..Opts::default()
2853                },
2854                Memo::new(&[]),
2855            );
2856            let vertex = m.heap.tuple(&[one]);
2857            let set = m.heap.set_from(&mut vec![vertex]);
2858            let set = m.heap.intern_exact(set).unwrap();
2859            let query = m.heap.tuple(&[two]);
2860            if warm_first {
2861                assert_eq!(m.member(query, set), Ok(false));
2862                assert_eq!(m.memo.bytes(), 128);
2863                assert_eq!(Arc::weak_count(&store), 1);
2864            }
2865            m.memo.set_cap(64);
2866            assert_eq!(m.memo.bytes(), 0);
2867            assert_eq!(Arc::weak_count(&store), 0, "release the certificate owner");
2868            let expected = compare::miss(&m.heap, query, m.heap.view(set).data).map(|()| false);
2869            assert_eq!(m.member(query, set), expected);
2870            assert!(m.memo.bytes() <= 64);
2871            assert!(!m.memo.members_active());
2872
2873            let memo = std::mem::take(&mut m.memo);
2874            let mut moved = Machine::new(
2875                store,
2876                0,
2877                Opts {
2878                    memo_cap: 64,
2879                    ..Opts::default()
2880                },
2881                memo,
2882            );
2883            let query = moved.heap.tuple(&[two]);
2884            assert_eq!(moved.member(query, set), expected);
2885            assert!(moved.memo.bytes() <= 64);
2886            assert!(!moved.heap.poisoned());
2887        }
2888    }
2889
2890    #[test]
2891    fn prepopulated_public_memo_keeps_membership_allocation_within_its_cap() {
2892        let one = Handle::int(1).unwrap();
2893        let two = Handle::int(2).unwrap();
2894        for cap in [2048, 2079, 2112, 4096, 1 << 20, crate::memo::DEFAULT_CAP] {
2895            for (semantics, memo_enabled) in [
2896                (crate::Semantics::tlc(), true),
2897                (crate::Semantics::default(), true),
2898                (crate::Semantics::tlc(), false),
2899            ] {
2900                let mut memo = Memo::new(&[1]);
2901                memo.set_cap(cap);
2902                memo.put(0, &[one], two);
2903                assert_eq!(memo.bytes(), 2048);
2904                let body_bytes = memo.bytes();
2905                let store = Arc::new(Store::with_semantics(true, semantics));
2906                let opts = Opts {
2907                    memo_cap: cap,
2908                    memo: memo_enabled,
2909                    ..Opts::default()
2910                };
2911                let mut m = Machine::new(store, 0, opts, memo);
2912                let vertex = m.heap.tuple(&[one]);
2913                let set = m.heap.set_from(&mut vec![vertex]);
2914                let set = m.heap.intern_exact(set).unwrap();
2915                let query = m.heap.tuple(&[two]);
2916                assert_eq!(m.member(query, set), Ok(false));
2917                assert!(m.memo.bytes() <= cap);
2918                assert_eq!(m.memo.get(0, &[one]), Some(two), "keep the body result");
2919                if cap == 2048 || cap == 2079 || !memo_enabled || !semantics.tlc_comparisons {
2920                    assert!(!m.memo.members_active());
2921                    assert_eq!(m.memo.bytes(), body_bytes);
2922                } else {
2923                    assert!(m.memo.members_active());
2924                    assert!(m.memo.bytes() > body_bytes);
2925                    if cap == 2112 {
2926                        assert_eq!(m.memo.bytes(), 2112, "only 64 bytes remain");
2927                    }
2928                }
2929                if cap == 2048 {
2930                    m.memo.set_cap(64);
2931                    assert_eq!(m.memo.bytes(), body_bytes, "retain existing body storage");
2932                    assert_eq!(m.memo.get(0, &[one]), Some(two));
2933                    assert_eq!(m.member(query, set), Ok(false));
2934                    assert_eq!(m.memo.bytes(), body_bytes, "add no certificate bytes");
2935                }
2936                // Subsequent ordinary table growth must respect the reduced
2937                // allowance as well as the pre-existing table allocation.
2938                for i in 1..1000 {
2939                    m.memo.put(0, &[Handle::int(i).unwrap()], two);
2940                    assert!(m.memo.bytes() <= cap);
2941                }
2942                assert!(!m.heap.poisoned());
2943            }
2944        }
2945    }
2946
2947    #[test]
2948    fn public_heap_replacement_cannot_reuse_another_stores_membership_proof() {
2949        fn values(heap: &mut Heap, name: &str) -> (Handle, Handle) {
2950            let one = Handle::int(1).unwrap();
2951            let model = Handle::model(heap.store().strings().intern(name).unwrap());
2952            let witness = heap.tuple(&[one]);
2953            let witness = heap.intern_exact(witness).unwrap();
2954            let other = heap.tuple(&[model]);
2955            let other = heap.intern_exact(other).unwrap();
2956            let set = heap.set_from(&mut vec![witness, other]);
2957            let set = heap.intern_exact(set).unwrap();
2958            (set, witness)
2959        }
2960
2961        for hashcons in [true, false] {
2962            let store = Arc::new(Store::with_semantics(hashcons, crate::Semantics::tlc()));
2963            let old_owner = Arc::downgrade(&store);
2964            let mut m = Machine::new(store, 0, Opts::default(), Memo::new(&[]));
2965            let (old_set, old_witness) = values(&mut m.heap, "u");
2966            let two = Handle::int(2).unwrap();
2967            let query = m.heap.tuple(&[two]);
2968            assert_eq!(m.member(query, old_set), Ok(false));
2969            assert!(m.memo.bytes() > 0);
2970
2971            let store = Arc::new(Store::with_semantics(hashcons, crate::Semantics::tlc()));
2972            let mut replacement = Heap::new(store, false, false);
2973            let (set, witness) = values(&mut replacement, "T_x");
2974            assert_eq!(old_set, set, "complete set handles collide across stores");
2975            assert_eq!(old_witness, witness, "witness handles also collide");
2976            m.heap = replacement;
2977            assert!(
2978                old_owner.upgrade().is_none(),
2979                "a certificate does not retain Store"
2980            );
2981            let query = m.heap.tuple(&[two]);
2982            let expected = compare::miss(&m.heap, query, m.heap.view(set).data).map(|()| false);
2983            assert!(expected.is_err(), "typed versus integer constraints refuse");
2984            assert_eq!(m.member(query, set), expected, "warm equals the full miss");
2985            assert_eq!(m.memo.bytes(), 0, "rebind drops the old entries");
2986            m.memo.clear();
2987            assert_eq!(m.member(query, set), expected, "cold equals the full miss");
2988            assert!(!m.heap.poisoned());
2989        }
2990    }
2991
2992    #[test]
2993    fn membership_certificates_respect_profiles_epochs_and_machine_stores() {
2994        let one = Handle::int(1).unwrap();
2995        let two = Handle::int(2).unwrap();
2996        for hashcons in [false, true] {
2997            let store = Arc::new(Store::with_semantics(hashcons, crate::Semantics::tlc()));
2998            let opts = Opts {
2999                memo_cap: 512,
3000                ..Opts::default()
3001            };
3002            let mut m = Machine::new(store.clone(), 0, opts, Memo::new(&[]));
3003            let u = Handle::model(store.strings().intern("u").unwrap());
3004            let genesis = m.heap.tuple(&[]);
3005            let vertex = m.heap.tuple(&[u, one]);
3006            let set = m.heap.set_from(&mut vec![genesis, vertex]);
3007            let set = m.heap.intern_exact(set).unwrap();
3008            let query = m.heap.tuple(&[u, two]);
3009            assert_eq!(m.member(query, set), Ok(false));
3010            let vertex = m.memo.member_witness(m.heap.store(), set).unwrap();
3011            assert_eq!(m.memo.bytes(), 32);
3012            m.heap.reset();
3013            let mark = m.heap.mark();
3014            let query = m.heap.tuple(&[u, two]);
3015            assert_eq!(m.member(query, set), Ok(false));
3016            m.heap.rollback(mark);
3017            let query = m.heap.tuple(&[u, two]);
3018            assert_eq!(m.member(query, set), Ok(false));
3019            let ephemeral = m.heap.set_from(&mut vec![query]);
3020            assert_eq!(m.member(vertex, ephemeral), Ok(false));
3021            assert_eq!(m.memo.member_witness(m.heap.store(), ephemeral), None);
3022            assert!(!m.heap.poisoned());
3023
3024            let mut worker = Machine::new(store, 0, opts, Memo::new(&[]));
3025            assert_eq!(worker.memo.member_witness(worker.heap.store(), set), None);
3026            let query = worker.heap.tuple(&[u, two]);
3027            assert_eq!(worker.member(query, set), Ok(false));
3028            assert!(
3029                worker
3030                    .memo
3031                    .member_witness(worker.heap.store(), set)
3032                    .is_some()
3033            );
3034            let reused = std::mem::take(&mut worker.memo);
3035            let other = Arc::new(Store::with_semantics(hashcons, crate::Semantics::tlc()));
3036            let mut worker = Machine::new(other, 0, opts, reused);
3037            assert_eq!(worker.memo.member_witness(worker.heap.store(), set), None);
3038            assert_eq!(worker.memo.bytes(), 0);
3039        }
3040        for (semantics, memo_enabled) in [
3041            (crate::Semantics::default(), true),
3042            (crate::Semantics::tlc(), false),
3043        ] {
3044            let store = Arc::new(Store::with_semantics(true, semantics));
3045            let mut m = Machine::new(
3046                store,
3047                0,
3048                Opts {
3049                    memo: memo_enabled,
3050                    ..Opts::default()
3051                },
3052                Memo::new(&[]),
3053            );
3054            assert!(!m.memo.members_active());
3055            let vertex = m.heap.tuple(&[one]);
3056            let set = m.heap.set_from(&mut vec![vertex]);
3057            let set = m.heap.intern_exact(set).unwrap();
3058            let query = m.heap.tuple(&[two]);
3059            assert_eq!(m.member(query, set), Ok(false));
3060            assert_eq!(m.memo.bytes(), 0);
3061        }
3062    }
3063
3064    #[test]
3065    fn arithmetic_errors_carry_tlc_classes() {
3066        let exc = |c| Some(TlcClass::eval_exception(c));
3067        for mode in [crate::int::IntMode::Big, crate::int::IntMode::Tlc] {
3068            let mut h =
3069                crate::Heap::new(std::sync::Arc::new(crate::Store::default()), false, false);
3070            h.set_int_mode(mode);
3071            let n = |v| Handle::int(v).unwrap();
3072            let mut class = |op, x, y| h.int_arith(op, n(x), n(y)).unwrap_err().tlc();
3073            assert_eq!(class(IntOp::Div, 1, 0), exc(2179));
3074            assert_eq!(class(IntOp::Mod, 1, 0), exc(2169));
3075            assert_eq!(class(IntOp::Pow, 2, -1), exc(2169));
3076            assert_eq!(class(IntOp::Pow, 0, 0), exc(2180));
3077        }
3078        let mut h = crate::Heap::new(std::sync::Arc::new(crate::Store::default()), false, false);
3079        h.set_int_mode(crate::int::IntMode::Tlc);
3080        let big = h
3081            .int_arith(
3082                IntOp::Mul,
3083                Handle::int(1 << 20).unwrap(),
3084                Handle::int(1 << 20).unwrap(),
3085            )
3086            .unwrap_err();
3087        assert_eq!(big.tlc(), exc(2178));
3088    }
3089}
3090
3091#[cfg(test)]
3092mod recursive_call_bounds {
3093    use super::*;
3094    use std::sync::atomic::{AtomicUsize, Ordering};
3095
3096    #[derive(Debug)]
3097    struct StopAfterOne(AtomicUsize);
3098    impl WorkControl for StopAfterOne {
3099        fn proceed(&self) -> bool {
3100            self.0.fetch_add(1, Ordering::Relaxed) == 0
3101        }
3102    }
3103
3104    #[test]
3105    fn recursive_calls_poll_work_and_restore_depth_and_frames_after_stops()
3106    -> Result<(), Box<dyn std::error::Error>> {
3107        let code = Code {
3108            nodes: vec![Node::Call {
3109                fun: 0,
3110                args: Box::new([]),
3111            }],
3112            funs: vec![crate::plan::Fun {
3113                name: "loop".into(),
3114                params: 0,
3115                frame: 0,
3116                body: 0,
3117                caps: Box::new([]),
3118            }],
3119            ..Default::default()
3120        };
3121        let mut m = Machine::new(
3122            Arc::new(Store::default()),
3123            0,
3124            Opts::default(),
3125            Memo::default(),
3126        );
3127        let control = Arc::new(StopAfterOne(AtomicUsize::new(0)));
3128        m.set_work_control(Some(control.clone()));
3129        let stopped = m.eval(&code, 0).err().ok_or("expected cooperative stop")?;
3130        assert_eq!(stopped.kind(), crate::ErrorKind::Stop);
3131        assert_eq!(control.0.load(Ordering::Relaxed), 2);
3132        assert_eq!(m.depth, 0);
3133        assert_eq!(m.frame, Vec::<Handle>::new());
3134        m.set_work_control(None);
3135        let bounded = m.eval(&code, 0).err().ok_or("expected depth refusal")?;
3136        assert_eq!(bounded.kind(), crate::ErrorKind::Unsupported);
3137        assert!(bounded.message().contains("recursive-call depth limit"));
3138        assert_eq!(m.depth, 0);
3139        assert_eq!(m.frame, Vec::<Handle>::new());
3140        Ok(())
3141    }
3142}
3143
3144#[cfg(test)]
3145mod thunk_rollback {
3146    #![allow(clippy::unwrap_used, reason = "tests")]
3147    use super::*;
3148
3149    /// Slot 0's thunk is a tuple of `x`: a transient.
3150    fn code() -> Code {
3151        Code {
3152            nodes: vec![
3153                Node::Var(0),
3154                Node::Tuple(Box::new([0, 0])),
3155                Node::Lazy { slot: 0, body: 1 },
3156            ],
3157            ..Default::default()
3158        }
3159    }
3160
3161    fn machine() -> Machine {
3162        let mut m = Machine::new(
3163            Arc::new(Store::default()),
3164            1,
3165            Opts::default(),
3166            Memo::default(),
3167        );
3168        m.s0[0] = Handle::int(1).unwrap();
3169        m
3170    }
3171
3172    #[test]
3173    fn a_thunk_forced_in_a_left_frame_releases_the_rollback() {
3174        let code = code();
3175        let mut m = machine();
3176        let outer = m.enter(1);
3177        let before = m.heap.mark();
3178        let since = m.thunk_mark();
3179        let inner = m.enter(1);
3180        let v = m.eval(&code, 2).unwrap();
3181        assert!(v.is_transient());
3182        // While the check's frame is live, its slot holds the value.
3183        assert!(!m.thunks_released(since));
3184        m.leave(inner);
3185        assert!(m.thunks_released(since));
3186        m.heap.rollback(before);
3187        assert!(!m.heap.poisoned());
3188        // The outer frame's own thunk is unforced and evaluates afresh.
3189        let w = m.eval(&code, 2).unwrap();
3190        assert!(compare::equals(&m.heap, w, w).unwrap());
3191        assert!(!m.heap.poisoned());
3192        m.leave(outer);
3193    }
3194
3195    #[test]
3196    fn a_thunk_forced_in_a_live_frame_keeps_the_values_it_holds() {
3197        let code = code();
3198        let mut m = machine();
3199        let outer = m.enter(1);
3200        let since = m.thunk_mark();
3201        let v = m.eval(&code, 2).unwrap();
3202        let inner = m.enter(1);
3203        m.leave(inner);
3204        // The live slot holds a value built after the mark: no rollback.
3205        assert!(!m.thunks_released(since));
3206        // An enclosing scope still sees it, and a later scope does not.
3207        assert!(!m.thunks_released(0));
3208        let later = m.thunk_mark();
3209        assert!(m.thunks_released(later));
3210        assert_eq!(m.eval(&code, 2).unwrap(), v);
3211        assert!(!m.heap.poisoned());
3212        m.leave(outer);
3213        // Leaving the last frame drops every slot.
3214        assert!(m.thunks_released(0));
3215    }
3216
3217    #[test]
3218    fn a_released_inner_scope_keeps_the_enclosing_scopes_live_slots() {
3219        let code = code();
3220        let mut m = machine();
3221        let outer = m.enter(1);
3222        let since = m.thunk_mark();
3223        m.eval(&code, 2).unwrap();
3224        let inner_since = m.thunk_mark();
3225        let inner = m.enter(1);
3226        m.eval(&code, 2).unwrap();
3227        m.leave(inner);
3228        assert!(m.thunks_released(inner_since));
3229        assert!(!m.thunks_released(since));
3230        m.leave(outer);
3231    }
3232}
3233
3234#[cfg(test)]
3235mod work_poll_bound {
3236    use super::*;
3237    use std::sync::atomic::{AtomicUsize, Ordering};
3238
3239    /// Proceeds for the first `allow` polls, then refuses.
3240    #[derive(Debug)]
3241    struct Allow {
3242        allow: usize,
3243        polls: AtomicUsize,
3244    }
3245    impl WorkControl for Allow {
3246        fn proceed(&self) -> bool {
3247            self.polls.fetch_add(1, Ordering::Relaxed) < self.allow
3248        }
3249    }
3250
3251    fn machine(allow: usize) -> (Machine, Arc<Allow>) {
3252        let mut m = Machine::new(
3253            Arc::new(Store::default()),
3254            0,
3255            Opts::default(),
3256            Memo::default(),
3257        );
3258        let control = Arc::new(Allow {
3259            allow,
3260            polls: AtomicUsize::new(0),
3261        });
3262        m.set_work_control(Some(control.clone()));
3263        (m, control)
3264    }
3265
3266    fn polls(control: &Allow) -> usize {
3267        control.polls.load(Ordering::Relaxed)
3268    }
3269
3270    #[test]
3271    fn the_first_charge_after_installation_polls() {
3272        let (mut m, control) = machine(0);
3273        let error = m.charge(1).err();
3274        assert!(error.is_some_and(|e| e.kind() == crate::ErrorKind::Stop));
3275        assert_eq!(polls(&control), 1);
3276        assert!(m.heap.work_interrupted());
3277    }
3278
3279    #[test]
3280    fn a_stop_is_seen_within_the_documented_unit_bound() {
3281        let units = usize::try_from(WORK_POLL_UNITS).unwrap_or(usize::MAX);
3282        for n in [0, 1, 3] {
3283            let (mut m, control) = machine(1);
3284            let mut charged = 0usize;
3285            let mut calls = 0usize;
3286            let stopped = loop {
3287                let result = m.charge(n);
3288                calls += 1;
3289                if let Err(error) = result {
3290                    break error;
3291                }
3292                charged += n.max(1);
3293                assert!(calls <= units + 1, "no stop within the bound (n={n})");
3294            };
3295            assert_eq!(stopped.kind(), crate::ErrorKind::Stop);
3296            assert_eq!(polls(&control), 2);
3297            // The first charge polled; the refused poll came on the charge
3298            // that would carry the units since it to the bound.
3299            assert!(charged < units + n.max(1), "n={n} charged={charged}");
3300            assert!(calls <= units + 1, "n={n} calls={calls}");
3301            // Once refused, every later charge polls again.
3302            for _ in 0..3 {
3303                assert!(m.charge(1).is_err());
3304            }
3305            assert_eq!(polls(&control), 5);
3306        }
3307    }
3308
3309    #[test]
3310    fn a_large_charge_polls_before_its_work() {
3311        let (mut m, control) = machine(1);
3312        assert_eq!(m.charge(1), Ok(()));
3313        let big = usize::try_from(WORK_POLL_UNITS).unwrap_or(usize::MAX);
3314        let error = m.charge(big).err();
3315        assert!(error.is_some_and(|e| e.kind() == crate::ErrorKind::Stop));
3316        assert_eq!(polls(&control), 2);
3317    }
3318
3319    #[test]
3320    fn bounded_fuel_and_transients_are_checked_on_every_charge_and_polled_on_the_bound() {
3321        let units = usize::try_from(WORK_POLL_UNITS).unwrap_or(usize::MAX);
3322        let (mut m, control) = machine(usize::MAX);
3323        assert_eq!(m.charge(1), Ok(()));
3324        m.set_fuel(10);
3325        for spent in 1..=10 {
3326            assert_eq!(m.charge(1), Ok(()));
3327            assert_eq!(m.fuel, 10 - spent);
3328        }
3329        let error = m.charge(1).err();
3330        assert!(error.is_some_and(|e| e.kind() == crate::ErrorKind::Unsupported));
3331        assert_eq!(polls(&control), 1);
3332        m.set_fuel(u64::MAX);
3333        m.heap.tuple(&[Handle::TRUE]);
3334        m.set_transient_bound(0);
3335        let error = m.charge(1).err();
3336        assert!(error.is_some_and(|e| e.kind() == crate::ErrorKind::Unsupported));
3337        m.set_transient_bound(usize::MAX);
3338        // Twelve charges since the one that polled: the bound counts the
3339        // bounded and unbounded charges alike, so charge 33 polls.
3340        for _ in 13..units {
3341            assert_eq!(m.charge(1), Ok(()));
3342        }
3343        assert_eq!(polls(&control), 1);
3344        assert_eq!(m.charge(1), Ok(()));
3345        assert_eq!(polls(&control), 2);
3346        // A bounded machine still polls within the bound.
3347        m.set_fuel(u64::MAX - 1);
3348        for _ in 1..units {
3349            assert_eq!(m.charge(1), Ok(()));
3350        }
3351        assert_eq!(polls(&control), 2);
3352        assert_eq!(m.charge(1), Ok(()));
3353        assert_eq!(polls(&control), 3);
3354    }
3355
3356    #[test]
3357    fn reinstalling_a_control_polls_at_once() {
3358        let (mut m, control) = machine(usize::MAX);
3359        assert_eq!(m.charge(1), Ok(()));
3360        assert_eq!(polls(&control), 1);
3361        let deny = Arc::new(Allow {
3362            allow: 0,
3363            polls: AtomicUsize::new(0),
3364        });
3365        m.set_work_control(Some(deny.clone()));
3366        assert!(m.charge(1).is_err());
3367        assert_eq!(polls(&deny), 1);
3368    }
3369}
3370
3371#[cfg(test)]
3372mod bounded_analysis_machine {
3373    #![allow(clippy::unwrap_used, reason = "tests")]
3374    use super::*;
3375    use crate::plan::MemoSite;
3376
3377    fn memo_code(step: bool) -> Code {
3378        Code {
3379            nodes: vec![
3380                Node::Const(Handle::int(7).unwrap()),
3381                Node::Memo { site: 0, body: 0 },
3382            ],
3383            sites: vec![MemoSite {
3384                name: "site".into(),
3385                vars: Box::new([0]),
3386                slots: Box::new([]),
3387                primed: Box::new([]),
3388                step,
3389                candidate: false,
3390            }],
3391            ..Default::default()
3392        }
3393    }
3394
3395    fn machine(memo_on: bool, memo: Memo) -> Machine {
3396        let opts = Opts {
3397            memo: memo_on,
3398            step_memo: memo_on,
3399            ..Opts::default()
3400        };
3401        let mut m = Machine::new(Arc::new(Store::default()), 1, opts, memo);
3402        m.s0[0] = Handle::int(1).unwrap();
3403        m
3404    }
3405
3406    #[test]
3407    fn memo_off_machines_evaluate_memo_bodies_without_reading_or_filling_a_site() {
3408        // Control: with memoization on, the site is looked up and filled.
3409        let mut on = machine(true, Memo::new(&[1]));
3410        assert_eq!(
3411            on.eval(&memo_code(false), 1).unwrap(),
3412            Handle::int(7).unwrap()
3413        );
3414        assert_eq!(on.memo.stats()[0].lookups, 1);
3415        assert!(on.memo.bytes() > 0);
3416        // memo = step_memo = false: even a site with a table is never used.
3417        let mut off = machine(false, Memo::new(&[1]));
3418        for _ in 0..2 {
3419            assert_eq!(
3420                off.eval(&memo_code(false), 1).unwrap(),
3421                Handle::int(7).unwrap()
3422            );
3423        }
3424        assert_eq!(off.memo.stats()[0].lookups, 0);
3425        assert_eq!(off.memo.bytes(), 0);
3426        // An analysis machine owns a table-less Memo, so not even a step
3427        // site (which ignores Opts::memo) can read or fill one.
3428        let mut analysis = machine(false, Memo::default());
3429        for step in [false, true] {
3430            assert_eq!(
3431                analysis.eval(&memo_code(step), 1).unwrap(),
3432                Handle::int(7).unwrap()
3433            );
3434        }
3435        assert_eq!(analysis.memo.stats(), Vec::new());
3436        assert_eq!(analysis.memo.bytes(), 0);
3437    }
3438
3439    #[test]
3440    fn bounded_machines_precharge_big_powers_before_allocating() {
3441        let pow = |x: i64, y: i64| Code {
3442            nodes: vec![
3443                Node::Const(Handle::int(x).unwrap()),
3444                Node::Const(Handle::int(y).unwrap()),
3445                Node::Arith(Arith::Pow, 0, 1),
3446            ],
3447            ..Default::default()
3448        };
3449        let mut m = machine(false, Memo::default());
3450        // 3^100000 has about 158,497 bits (2,476 words): more than the fuel.
3451        m.set_fuel(1000);
3452        let nodes = m.heap.arena().peak().0;
3453        let error = m.eval(&pow(3, 100_000), 2).unwrap_err();
3454        assert_eq!(error.kind(), crate::ErrorKind::Unsupported);
3455        assert!(m.fuel_exhausted());
3456        assert_eq!(m.heap.arena().peak().0, nodes, "no digits allocated");
3457        // Within the fuel the exact big result is built.
3458        m.set_fuel(1 << 20);
3459        let big = m.eval(&pow(3, 100_000), 2).unwrap();
3460        assert_eq!(
3461            m.heap.big(big).unwrap(),
3462            num_traits::Pow::pow(num_bigint::BigInt::from(3), 100_000_u32)
3463        );
3464        assert!(!m.fuel_exhausted());
3465        // Small and TLC-mode powers cost no digit fuel.
3466        m.set_fuel(4);
3467        assert_eq!(m.eval(&pow(2, 10), 2).unwrap(), Handle::int(1024).unwrap());
3468        m.heap.set_int_mode(crate::int::IntMode::Tlc);
3469        m.set_fuel(4);
3470        assert_eq!(m.eval(&pow(2, 10), 2).unwrap(), Handle::int(1024).unwrap());
3471    }
3472}
3473
3474#[cfg(test)]
3475mod same_vars {
3476    #![allow(clippy::unwrap_used, reason = "tests")]
3477    use super::*;
3478
3479    /// `<<x, <<y, z>>>> = <<x', <<y', z'>>>>` behind a thunk (node 8), and
3480    /// its `SameVars` (node 15).
3481    fn code() -> Code {
3482        Code {
3483            nodes: vec![
3484                Node::Var(0),
3485                Node::Var(1),
3486                Node::Var(2),
3487                Node::Tuple(Box::new([1, 2])),
3488                Node::Tuple(Box::new([0, 3])),
3489                Node::Lazy { slot: 0, body: 4 },
3490                Node::Primed(0),
3491                Node::Primed(1),
3492                Node::Eq(5, 13),
3493                Node::Primed(2),
3494                Node::Tuple(Box::new([7, 9])),
3495                Node::Tuple(Box::new([6, 10])),
3496                Node::Lazy { slot: 1, body: 11 },
3497                Node::Lazy { slot: 2, body: 12 },
3498                Node::Const(Handle::TRUE),
3499                Node::SameVars {
3500                    eq: 8,
3501                    leaves: Box::new([(0, 1), (1, 2), (2, 2)]),
3502                    thunks: Box::new([0, 1, 2]),
3503                },
3504            ],
3505            ..Default::default()
3506        }
3507    }
3508
3509    fn values(m: &mut Machine) -> Vec<Handle> {
3510        let one = Handle::int(1).unwrap();
3511        let two = Handle::int(2).unwrap();
3512        let text = m.heap.string("a").unwrap();
3513        let set = m.heap.set_enum(&[one, two]);
3514        let set = m.heap.intern(set).unwrap();
3515        let other = m.heap.set_enum(&[one]);
3516        let other = m.heap.intern(other).unwrap();
3517        let fcn = m.heap.int_fcn(1, &[set, text]);
3518        let fcn = m.heap.intern_exact(fcn).unwrap();
3519        // A symbolic interval is not materialized: `Eq` normalizes it.
3520        let interval = m.heap.interval(1, 2);
3521        let interval = m.heap.intern_exact(interval).unwrap();
3522        vec![one, two, text, set, other, fcn, interval, Handle::EMPTY]
3523    }
3524
3525    /// The `SameVars` result equals the `Eq` it wraps on every pair of
3526    /// rows drawn from `values`, error for error.
3527    fn agrees(semantics: crate::store::Semantics) {
3528        let code = code();
3529        let store = Arc::new(Store::with_semantics(true, semantics));
3530        let mut m = Machine::new(store, 3, Opts::default(), Memo::default());
3531        let values = values(&mut m);
3532        let pick = |i: usize| values[i % values.len()];
3533        let mut checked = 0;
3534        for i in 0..values.len().pow(2) {
3535            let (a, b) = (i % values.len(), i / values.len());
3536            for row in [[a, a, b], [a, b, b], [b, a, a], [a, a, a]] {
3537                let before: Vec<_> = row.iter().map(|&k| pick(k)).collect();
3538                for after in [before.clone(), vec![pick(b), before[1], before[2]]] {
3539                    m.s0.copy_from_slice(&before);
3540                    m.s1.copy_from_slice(&after);
3541                    let frame = m.enter(3);
3542                    let eq = m.eval(&code, 8).map_err(|e| e.kind());
3543                    m.leave(frame);
3544                    let frame = m.enter(3);
3545                    let same = m.eval(&code, 15).map_err(|e| e.kind());
3546                    m.leave(frame);
3547                    assert_eq!(same, eq, "{before:?} {after:?}");
3548                    // With the handles a row proof admits recorded as
3549                    // proven, the result is the same.
3550                    let proven: Vec<_> = before
3551                        .iter()
3552                        .chain(&after)
3553                        .copied()
3554                        .filter(|&h| m.heap.materialized_within(&[h], 4096, None))
3555                        .collect();
3556                    let keep = |row: &[Handle]| -> Vec<Handle> {
3557                        row.iter()
3558                            .map(|&h| {
3559                                if proven.contains(&h) {
3560                                    h
3561                                } else {
3562                                    Handle::EMPTY
3563                                }
3564                            })
3565                            .collect()
3566                    };
3567                    m.set_proven_materialized(&keep(&before), &keep(&after), []);
3568                    let frame = m.enter(3);
3569                    let reused = m.eval(&code, 15).map_err(|e| e.kind());
3570                    m.leave(frame);
3571                    m.set_proven_materialized(&[], &[], []);
3572                    assert_eq!(reused, eq, "{before:?} {after:?} with proofs");
3573                    checked += 1;
3574                }
3575            }
3576        }
3577        assert!(checked > 100);
3578        assert!(!m.heap.poisoned());
3579    }
3580
3581    /// Set membership with recorded proofs agrees with membership without
3582    /// them, and an operand nobody recorded still refuses when it is not
3583    /// materialized.
3584    #[test]
3585    fn membership_reuses_only_recorded_proofs() {
3586        let store = Arc::new(Store::default());
3587        let mut m = Machine::new(store, 2, Opts::default(), Memo::default());
3588        // Bounded fuel: membership takes the checked path, not the index.
3589        m.set_fuel(1 << 30);
3590        let one = Handle::int(1).unwrap();
3591        let two = Handle::int(2).unwrap();
3592        // Persistent copies without the cached proof, as snapshot restore
3593        // and owned exchange produce them.
3594        let inner = m.heap.set_from(&mut vec![one, two]);
3595        let inner = m.heap.unmarked_copy(inner);
3596        let single = m.heap.set_from(&mut vec![one]);
3597        let single = m.heap.unmarked_copy(single);
3598        let outer = m.heap.set_from(&mut vec![inner, single]);
3599        let outer = m.heap.unmarked_copy(outer);
3600        let other = m.heap.set_from(&mut vec![two]);
3601        let other = m.heap.unmarked_copy(other);
3602        let interval = m.heap.interval(1, 2);
3603        let interval = m.heap.intern_exact(interval).unwrap();
3604        let lazy = m.heap.set_from(&mut vec![interval]);
3605        let lazy = m.heap.unmarked_copy(lazy);
3606        for h in [inner, single, outer, other] {
3607            assert!(!m.heap.proved_concrete(h));
3608            assert!(m.heap.materialized_within(&[h], 64, None));
3609        }
3610        assert!(!m.heap.materialized_within(&[lazy], 64, None));
3611        let cases = [(inner, outer), (other, outer), (one, inner), (two, single)];
3612        for (x, set) in cases {
3613            m.set_proven_materialized(&[], &[], []);
3614            let plain = m.member(x, set).map_err(|e| e.kind());
3615            assert!(plain.is_ok(), "{x:?} {set:?} {plain:?}");
3616            m.set_proven_materialized(&[x], &[set], []);
3617            assert_eq!(m.member(x, set).map_err(|e| e.kind()), plain);
3618            m.set_proven_materialized(&[], &[], [x, set]);
3619            assert_eq!(m.member(x, set).map_err(|e| e.kind()), plain);
3620        }
3621        assert_eq!(m.member(inner, outer).ok(), Some(true));
3622        assert_eq!(m.member(other, outer).ok(), Some(false));
3623        assert_eq!(m.member(two, single).ok(), Some(false));
3624        // An unmaterialized operand that is not recorded still refuses,
3625        // with or without proofs recorded for the other operand.
3626        m.set_proven_materialized(&[], &[], []);
3627        let refused = m.member(lazy, outer).map_err(|e| e.kind());
3628        assert!(refused.is_err());
3629        m.set_proven_materialized(&[outer], &[], []);
3630        assert_eq!(m.member(lazy, outer).map_err(|e| e.kind()), refused);
3631        m.set_proven_materialized(&[], &[], []);
3632        assert!(!m.heap.poisoned());
3633    }
3634
3635    #[test]
3636    fn same_vars_agrees_with_the_tuple_equality_it_wraps() {
3637        agrees(crate::store::Semantics::default());
3638        agrees(crate::store::Semantics::tlc());
3639    }
3640
3641    #[test]
3642    fn a_forced_thunk_is_read_as_the_tuple_equality_reads_it() {
3643        let code = code();
3644        let mut m = Machine::new(
3645            Arc::new(Store::default()),
3646            3,
3647            Opts::default(),
3648            Memo::default(),
3649        );
3650        let one = Handle::int(1).unwrap();
3651        let two = Handle::int(2).unwrap();
3652        m.s0.copy_from_slice(&[one, one, one]);
3653        m.s1.copy_from_slice(&[one, one, one]);
3654        let frame = m.enter(3);
3655        // A cached value the variables no longer give is what `Eq` reads.
3656        let stale = m.heap.tuple(&[two, two]);
3657        m.set_slot(0, stale);
3658        assert_eq!(m.eval(&code, 15).unwrap(), Handle::FALSE);
3659        for slot in 0..3 {
3660            m.set_slot(slot, Handle::EMPTY);
3661        }
3662        assert_eq!(m.eval(&code, 15).unwrap(), Handle::TRUE);
3663        // The direct comparison forces no thunk.
3664        assert!((0..3).all(|slot| m.slot(slot).is_empty()));
3665        m.s1[2] = two;
3666        assert_eq!(m.eval(&code, 15).unwrap(), Handle::FALSE);
3667        assert!((0..3).all(|slot| m.slot(slot).is_empty()));
3668        m.leave(frame);
3669    }
3670}