Skip to main content

dive_core/
compile.rs

1//! The plan compiler: `dive_ir` plus the binder
2//! handoff to a [`Plan`].
3//!
4//! Passes, in one walk:
5//!
6//! 1. **Static resolution.** Configuration redirects (`Op <- D`), startup
7//!    values of constant definitions and constants become pool constants.
8//! 2. **Operator inlining.** Every non-recursive user operator is inlined.
9//!    Each argument is substituted directly when it is a literal, a constant,
10//!    a bound variable or a state read (pure and unable to fail); otherwise it
11//!    becomes a thunk slot, forced at most once per activation; an argument
12//!    that reads primed variables is re-evaluated by name, as TLC's cache
13//!    check would see a different successor buffer. Zero-arity `LET`
14//!    definitions are thunks, re-enumerated by name in action position
15//!    (TLC binds no `LET` in the generator). Recursive operators are
16//!    compiled once into their own frame.
17//! 3. **Slot resolution.** Locals become offsets in one flat frame per role.
18//! 4. **Specialization.** Arithmetic, comparisons, `x' = e`, `x' \in S`,
19//!    `UNCHANGED` of variable tuples, record fields by constant name, and
20//!    membership in symbolic sets get their own node kinds.
21//! 5. **Constant folding.** A closed subexpression (no state read, no free
22//!    slot) is evaluated once at compile time; if it fails it is left alone,
23//!    so the error surfaces where TLC raises it.
24//! 6. **Read sets and memo sites.** Every node records the variables and
25//!    free slots it reads; invariant and constraint conjuncts and action
26//!    guards become memo sites keyed on them.
27//!
28//! Anything else is refused, naming the construct.
29
30use std::collections::HashMap;
31use std::sync::Arc;
32
33use dive_ir::{
34    Arg, Bound, BuiltinOp, DefId, DefScope, Expr, ExprId, Ir, JunctionKind, Level, LocalRef, OpRef,
35    QuantKind, Slot, StdOp,
36};
37use dive_value::Value;
38
39use crate::Error;
40use crate::eval::Machine;
41use crate::handle::Handle;
42use crate::memo::{MAX_KEY, Memo};
43use crate::node::Kind;
44use crate::opts::Opts;
45use crate::plan::{
46    Action, Arith, Bind, Check, Cmp, Code, CompileStats, Conjunct, Fun, G, GNode, LibArg, MemoSite,
47    Node, P, Plan, Quant, SetOp, StdFn, Update,
48};
49use crate::store::Store;
50
51#[path = "compile_gen.rs"]
52mod generator;
53
54#[path = "compile_composition.rs"]
55mod composition;
56
57/// The largest plan the compiler builds (inlining blow-up guard).
58const MAX_NODES: usize = 4_000_000;
59
60/// The most loop iterations one constant fold may spend. A larger
61/// closed expression, such as `CoffeeCan`'s initial filter over 1,002,001
62/// records (over 10,201 already at 100 beans), is left to run time, where
63/// the generator streams it instead of building it in the compile arena.
64/// Type sets of a few hundred records, such as `MCNano`'s
65/// `SignedBlock \cup {NoBlock}` (593 records, about 5,000 iterations), fit
66/// and are folded once instead of being rebuilt in every state.
67pub const FOLD_FUEL: u64 = 1 << 16;
68
69/// The most loop iterations all constant folds of one compile may spend
70/// together: the compile-time budget. Once it is spent, nothing more
71/// is folded.
72pub const FOLD_BUDGET: u64 = 1 << 22;
73
74/// The most loop iterations the start-up evaluation of one closed
75/// zero-arity definition whose fold ran out of [`FOLD_FUEL`] may spend
76/// (`Compiler::settle`). `LeastCircularSubstring`'s
77/// `Corpus == ZSeq(CharacterSet)` (9,841 sequences in the Medium model,
78/// about 217,000 iterations) fits, and is built once instead of in every
79/// state that tests membership in it.
80pub const SETTLE_FUEL: u64 = 1 << 22;
81
82/// The most loop iterations all such start-up evaluations of one compile
83/// may spend together.
84pub const SETTLE_BUDGET: u64 = 1 << 24;
85
86/// A role as `dive-model`'s binder split it: an expression evaluated in a
87/// definition's frame, with some of that frame's slots bound to values.
88#[derive(Clone, Debug)]
89pub struct Role {
90    /// The name TLC reports.
91    pub name: String,
92    /// The expression.
93    pub expr: ExprId,
94    /// The definition whose frame it is evaluated in.
95    pub def: DefId,
96    /// Slots of that frame bound by splitting (`\E` variables and inlined
97    /// parameters), with their values.
98    pub slots: Vec<(Slot, Value)>,
99    /// The `INSTANCE` substitutions active where splitting found the role
100    /// (it found it inside an instantiated definition).
101    pub substs: Vec<RoleSubst>,
102}
103
104/// An `INSTANCE` substitution active at a split role.
105#[derive(Clone, Debug)]
106pub enum RoleSubst {
107    /// An operator bound to an uncaptured top-level definition.
108    Operator {
109        /// The substituted declaration.
110        decl: dive_ir::DeclId,
111        /// The actual definition, with no retained lexical/dynamic closure.
112        def: DefId,
113    },
114    /// `decl <- expr`, with `expr` evaluated in the frame of `def` with
115    /// `slots` bound, outside any substitution.
116    Expr {
117        /// The substituted declaration.
118        decl: dive_ir::DeclId,
119        /// The expression.
120        expr: ExprId,
121        /// The definition whose frame it is evaluated in.
122        def: DefId,
123        /// That frame's bound slots.
124        slots: Vec<(Slot, Value)>,
125    },
126    /// `decl` bound to a value.
127    Value {
128        /// The substituted declaration.
129        decl: dive_ir::DeclId,
130        /// The value.
131        value: Value,
132    },
133}
134
135/// A configured constant.
136#[derive(Clone, Debug)]
137pub enum ConstBinding {
138    /// `C = v`.
139    Value(Value),
140    /// `C <- D`.
141    Def(DefId),
142}
143
144/// The binder's start-up evaluation of a constant definition it left to
145/// the core ([`Handoff::deferred`]).
146///
147/// ```
148/// #[derive(Debug)]
149/// struct Never;
150/// impl dive_core::compile::StartupEvaluator for Never {
151///     fn evaluate(&self, _def: dive_ir::DefId) -> Option<dive_value::Value> {
152///         None
153///     }
154/// }
155/// ```
156pub trait StartupEvaluator: std::fmt::Debug {
157    /// The definition's start-up value, or `None` when its evaluation fails
158    /// or leaves no value: the core then evaluates its body where it is
159    /// used.
160    fn evaluate(&self, def: DefId) -> Option<Value>;
161}
162
163/// The most transient memory, in bytes, the core's evaluation of one
164/// deferred start-up definition may hold; past it, the definition goes to
165/// the binder's evaluation ([`Handoff::startup_evaluator`]).
166pub const STARTUP_TRANSIENT_BYTES: usize = 256 << 20;
167
168/// What `dive-model`'s binder hands to the core.
169#[derive(Clone, Debug)]
170pub struct Handoff<'a> {
171    /// The lowered specification.
172    pub ir: &'a Ir,
173    /// The value semantics the startup values were built under.
174    pub ctx: dive_value::Ctx,
175    /// Whether the existing TLA+ action-composition mode is enabled.
176    pub action_composition: bool,
177    /// Constants, by `ConstId`.
178    pub constants: Vec<Option<ConstBinding>>,
179    /// `Op <- D` redirects, resolved to their final target.
180    pub redirects: HashMap<DefId, DefId>,
181    /// Redirects of Java-overridden operators (`Nat <- NatOverride`).
182    pub std_redirects: HashMap<StdOp, DefId>,
183    /// Startup values of constant definitions.
184    pub precomputed: HashMap<DefId, Value>,
185    /// The definitions among `precomputed` whose value is a configuration
186    /// override (`Op <- value`): their body is not their value.
187    pub overrides: std::collections::HashSet<DefId>,
188    /// Pure constant-level definitions the binder did not evaluate at
189    /// startup (`dive_model::bind_deferring_constants`): the compiler
190    /// evaluates each once, before the roles, and uses its value as a
191    /// startup value. One the core cannot evaluate within its startup
192    /// bounds goes to [`Self::startup_evaluator`], the binder's evaluation;
193    /// one that fails there too keeps its body, which is then evaluated
194    /// where it is used, as TLC does after a failed startup evaluation.
195    pub deferred: std::collections::BTreeSet<DefId>,
196    /// The binder's evaluation of a deferred definition, for the ones the
197    /// core does not evaluate itself. Without one, such a definition keeps
198    /// its body.
199    pub startup_evaluator: Option<Arc<dyn StartupEvaluator>>,
200    /// Pure `ASSUME`s of the root module (`dive_model::Model::deferred_assumptions`):
201    /// the compiler evaluates them in order, after the deferred definitions,
202    /// as it evaluates those, stopping at the first that is not `TRUE`, and
203    /// lists the ones it finds `TRUE` in [`Plan::startup_assumptions`]. The caller checks the others with the
204    /// dive-eval evaluator, which reports a false or failing one as TLC does.
205    pub assumptions: Vec<DefId>,
206    /// Initial predicates.
207    pub init: Vec<Role>,
208    /// Next-state actions, split, in TLC's order.
209    pub next: Vec<Role>,
210    /// `INVARIANT`s.
211    pub invariants: Vec<Role>,
212    /// `CONSTRAINT`s.
213    pub constraints: Vec<Role>,
214    /// `ACTION_CONSTRAINT`s, evaluated on a step: unprimed variables read
215    /// the parent, primed ones the successor.
216    pub action_constraints: Vec<Role>,
217    /// Implied initial predicates: the state-level parts of `PROPERTY`s,
218    /// checked on the initial states.
219    pub implied_inits: Vec<Role>,
220    /// Implied actions: the `[A]_v` of `[][A]_v` in `PROPERTY`s, evaluated
221    /// on every step as `ACTION_CONSTRAINT`s are.
222    pub implied_actions: Vec<Role>,
223    /// Whether deadlock is checked.
224    pub check_deadlock: bool,
225    /// `SYMMETRY`: the closure's nonidentity maps, each as its moved
226    /// model values `(from, to)` by name; empty without one.
227    pub symmetry: Vec<Vec<(String, String)>>,
228    /// `VIEW`: states are keyed by its value.
229    pub view: Option<Role>,
230}
231
232#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
233enum Mode {
234    Plain,
235    Primed,
236}
237
238/// Recursive compilation identity: definition, mode, Init, owner and substitutions.
239type RecKey = (DefId, Mode, bool, Option<usize>, Option<u32>);
240
241/// What a thunk of `Compiler::def_cache` stands for: a zero-arity
242/// definition, or a substitution used by name, in a mode.
243#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
244enum Cached {
245    // The last substitution's unique id identifies the whole active prefix:
246    // entries are immutable, appended fresh, and only truncated/restored.
247    // A shared source definition can compile differently in two instances.
248    Def(DefId, Mode, Option<u32>),
249    Subst(u32, Mode),
250}
251
252#[derive(Clone, Copy, Debug)]
253enum ArgHow {
254    Alias(P),
255    Thunk(u32, P),
256    ByName,
257}
258
259#[derive(Clone, Debug)]
260enum Sb {
261    Unset,
262    Flat(u32),
263    Arg {
264        expr: ExprId,
265        env: usize,
266        how: ArgHow,
267    },
268    LetVal {
269        def: DefId,
270        env: usize,
271        thunk: Option<(u32, P)>,
272        owner: usize,
273    },
274    /// The function name inside a recursive function definition.
275    RecSelf(DefId, u32, Mode),
276    /// A slot of the owning frame viewed by a LET-bound recursive function.
277    /// The value is captured lazily; caller flat slot numbers never enter the
278    /// function's runtime frame.
279    Enclosing {
280        env: usize,
281        slot: usize,
282    },
283    /// An operator parameter bound to an operator argument: the operator,
284    /// resolved in the caller's environment `env`.
285    OpArg {
286        op: OpRef,
287        env: usize,
288    },
289}
290
291/// A function being compiled from a definition nested in others (a
292/// recursive `LET` operator or function): its references to enclosing
293/// locals become captures, passed by every call (lambda lifting).
294#[derive(Debug)]
295struct Lift {
296    /// The first environment of the function: lower ones enclose it.
297    floor: usize,
298    /// The definition's lexical parent environment.
299    parent: Option<usize>,
300    /// The function.
301    fun: u32,
302    /// Captures: frames out from `parent`, slot there, capture slot.
303    caps: Vec<(u32, usize, u32)>,
304    /// Recursive calls inside the body, completed with the captures.
305    self_calls: Vec<P>,
306    /// The mode the body is compiled in. A next-state variant reads every
307    /// capture primed, and its callers compute the captures primed.
308    mode: Mode,
309}
310
311/// One active `INSTANCE` substitution `decl <- value` (`Expr::Subst`), in
312/// the dynamic context TLC binds it in (`Expr::SubstRef`).
313#[derive(Clone, Debug)]
314struct SubstEntry {
315    /// Unique among the compiler's substitution entries (`Cached::Subst`).
316    id: u32,
317    decl: dive_ir::DeclId,
318    /// The value: an argument, or a constant (`RoleSubst::Value`).
319    value: Result<Arg, P>,
320    /// The environment outside the substitution.
321    env: usize,
322    /// How an expression value is passed (as an operator argument is).
323    how: ArgHow,
324    /// The dynamic context outside the substitution: the stack below its
325    /// group.
326    depth: usize,
327}
328
329/// Saved slot bindings: environment, slot, old binding.
330type Saved = Vec<(usize, usize, Sb)>;
331
332#[derive(Clone, Debug)]
333struct EnvFrame {
334    def: DefId,
335    slots: Vec<Sb>,
336    parent: Option<usize>,
337}
338
339/// Pushes every value operand of `n` (not the bodies of called functions
340/// or the generators of `ENABLED` and composition queries).
341fn push_operands(n: &Node, out: &mut Vec<P>) {
342    match n {
343        Node::Const(_)
344        | Node::Slot(_)
345        | Node::Var(_)
346        | Node::Primed(_)
347        | Node::Enabled { .. }
348        | Node::Composition { .. } => {}
349        Node::Lazy { body, .. }
350        | Node::Scope { body, .. }
351        | Node::Memo { body, .. }
352        | Node::SameVars { eq: body, .. }
353        | Node::Spec(body)
354        | Node::Not(body)
355        | Node::Neg(body)
356        | Node::Powerset(body)
357        | Node::BigUnion(body)
358        | Node::Domain(body)
359        | Node::Select(body, _) => out.push(*body),
360        Node::And(xs)
361        | Node::Or(xs)
362        | Node::SetEnum(xs)
363        | Node::Product(xs)
364        | Node::Tuple(xs)
365        | Node::Std(_, xs)
366        | Node::Lib { args: xs, .. }
367        | Node::Call { args: xs, .. } => out.extend(xs.iter().copied()),
368        Node::Implies(a, b)
369        | Node::Equiv(a, b)
370        | Node::Eq(a, b)
371        | Node::Neq(a, b)
372        | Node::In(a, b)
373        | Node::NotIn(a, b)
374        | Node::Subseteq(a, b)
375        | Node::Arith(_, a, b)
376        | Node::Cmp(_, a, b)
377        | Node::Range(a, b)
378        | Node::SetBin(_, a, b)
379        | Node::FcnSet(a, b)
380        | Node::Apply(a, b)
381        | Node::InLazy {
382            elem: a, set: b, ..
383        }
384        | Node::DomCheck {
385            domain: a, body: b, ..
386        } => out.extend([*a, *b]),
387        Node::If(a, b, c)
388        | Node::Beta {
389            chain: a,
390            fc: b,
391            arg: c,
392        } => out.extend([*a, *b, *c]),
393        Node::Case(arms, other) => {
394            for &(g, v) in arms {
395                out.extend([g, v]);
396            }
397            out.extend(*other);
398        }
399        Node::RecSet(fs) | Node::Record(fs) => out.extend(fs.iter().map(|&(_, x)| x)),
400        Node::Filter { bind, pred, subset } => {
401            out.extend([bind.domain, *pred]);
402            out.extend(*subset);
403        }
404        Node::Map { binds, body }
405        | Node::FcnCons { binds, body }
406        | Node::Quant { binds, body, .. } => {
407            out.extend(binds.iter().map(|b| b.domain));
408            out.push(*body);
409        }
410        Node::Except { base, updates } => {
411            out.push(*base);
412            for u in updates {
413                out.extend(u.path.iter().copied());
414                out.push(u.value);
415            }
416        }
417        Node::LibHo(_, args) => out.extend(args.iter().map(|a| match a {
418            LibArg::Value(p) => *p,
419            LibArg::Op { body, .. } => *body,
420        })),
421    }
422}
423
424#[derive(Clone, Debug, Default)]
425#[allow(
426    clippy::struct_excessive_bools,
427    reason = "independent read, effect and budget eligibility facts"
428)]
429struct Info {
430    vars: u64,
431    primed: u64,
432    free: Vec<u32>,
433    calls: bool,
434    /// Reaches a nested `ENABLED` or composition query: an instance query's
435    /// identity-substitution proof does not cover its own cutoff.
436    nested_query: bool,
437    /// Contains a fold that ran out of fuel: enclosing folds would too.
438    heavy: bool,
439    /// Reaches an operator with an effect (`Print`, `PrintT`): TLC performs
440    /// it on every evaluation, so the node is never folded, memoized,
441    /// cached or skipped.
442    effect: bool,
443    /// Whether TLC's value of a set expression is `Reducible`,
444    /// so that TLC builds a filter, function
445    /// or set operation over it eagerly.
446    red: Red,
447}
448
449/// Whether TLC's value of a set expression is `Reducible`: a set
450/// enumeration or an interval (as `dive-eval`'s `is_reducible` decides). TLC builds `{x \in S : P}`, `[x \in S |-> e]` and
451/// `S \cup T` eagerly over reducible operands and keeps them lazy
452/// otherwise.
453#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
454enum Red {
455    /// Always reducible.
456    Yes,
457    /// Never reducible.
458    No,
459    /// Not known statically.
460    #[default]
461    Maybe,
462}
463
464/// The most nodes of a constant [`Compiler::holds_lazy_set`] looks at.
465const LAZY_SCAN: usize = 4096;
466
467/// Whether Core applies the built-in `op` when it is passed as an
468/// operator argument and applied to values: the set, equality,
469/// membership, Boolean and `DOMAIN`/`SUBSET`/`UNION` operators. TLC
470/// applies these exactly as the operator written in place, including the
471/// short-circuit evaluation of `/\`, `\/` and `=>`. The state, temporal
472/// and action operators (`'`, `UNCHANGED`, `ENABLED`, `\cdot`, `[]`, ...)
473/// stay refused, and `\X` cannot be passed (`DIVE-S0032`).
474const fn builtin_value_arg(op: BuiltinOp) -> bool {
475    use BuiltinOp as B;
476    matches!(
477        op,
478        B::Eq
479            | B::Neq
480            | B::In
481            | B::NotIn
482            | B::Subseteq
483            | B::Cup
484            | B::Cap
485            | B::SetMinus
486            | B::PowerSet
487            | B::BigUnion
488            | B::Domain
489            | B::Not
490            | B::And
491            | B::Or
492            | B::Implies
493            | B::Equiv
494    )
495}
496
497/// The arity of a built-in [`builtin_value_arg`] admits.
498const fn builtin_arity(op: BuiltinOp) -> Option<usize> {
499    use BuiltinOp as B;
500    match op {
501        B::PowerSet | B::BigUnion | B::Domain | B::Not => Some(1),
502        B::Eq
503        | B::Neq
504        | B::In
505        | B::NotIn
506        | B::Subseteq
507        | B::Cup
508        | B::Cap
509        | B::SetMinus
510        | B::And
511        | B::Or
512        | B::Implies
513        | B::Equiv => Some(2),
514        _ => None,
515    }
516}
517
518fn union(a: &mut Vec<u32>, b: &[u32]) {
519    if b.is_empty() {
520        return;
521    }
522    a.extend_from_slice(b);
523    a.sort_unstable();
524    a.dedup();
525}
526
527fn minus(a: &mut Vec<u32>, b: &[u32]) {
528    a.retain(|x| !b.contains(x));
529}
530
531/// The plan's `SYMMETRY`: the maps over the store's string ids, and under
532/// TLC's order TLC's canonicalization.
533fn symmetry(h: &Handoff<'_>, m: &Machine) -> Result<Option<crate::symmetry::Symmetry>, Error> {
534    if h.symmetry.is_empty() {
535        return Ok(None);
536    }
537    let strings = m.heap.store().strings();
538    let mut maps = Vec::with_capacity(h.symmetry.len());
539    for perm in &h.symmetry {
540        let mut pairs = Vec::with_capacity(perm.len());
541        for (a, b) in perm {
542            pairs.push((strings.intern(a)?, strings.intern(b)?));
543        }
544        maps.push(pairs);
545    }
546    let sym = crate::symmetry::Symmetry::new(maps);
547    // TLC's order (`--compat=tlc`): TLC's comparison, in TLC's variable
548    // order, as `TLCStateMut` canonicalizes.
549    Ok(Some(if h.ctx.order == dive_value::ValueOrder::Tlc {
550        sym.tlc(h.ir.tlc_var_order().iter().map(|v| v.index()).collect())
551    } else {
552        sym
553    }))
554}
555
556/// A source-bound optional atom wrapper. The role and subscript share one scope.
557#[derive(Clone, Copy, Debug)]
558pub enum BoundTest {
559    /// Ordinary predicate evaluation.
560    Predicate,
561    /// Successor existence, optionally requiring a subscript change.
562    Enabled(Option<ExprId>),
563    /// Check subscript change before evaluating the action.
564    Nonstuttering(ExprId),
565}
566
567/// Compiles one optional source-bound atom using existing evaluation/generation.
568///
569/// The plan uses the same value nodes as safety checking. Callers separately
570/// check its effects, compiled constants and actual input handles, and run it
571/// on a machine with [`crate::Machine::set_refuse_unrecorded_warnings`], so a
572/// reference warning that Core does not record declines instead.
573///
574/// ```no_run
575/// # fn example(h: &dive_core::Handoff<'_>, store: std::sync::Arc<dive_core::Store>) -> Result<(), dive_core::Error> {
576/// let plan = dive_core::compile::compile_bound_test(
577///     h, store, dive_core::Opts::default(), dive_core::compile::BoundTest::Enabled(None))?;
578/// # let _ = plan;
579/// # Ok(()) }
580/// ```
581///
582/// # Errors
583/// The existing compiler refusal or an unproved wrapper/update shape.
584pub fn compile_bound_test(
585    h: &Handoff<'_>,
586    store: Arc<Store>,
587    opts: Opts,
588    test: BoundTest,
589) -> Result<Plan, Error> {
590    if h.implied_actions.len() != 1
591        || !h.init.is_empty()
592        || !h.next.is_empty()
593        || !h.invariants.is_empty()
594        || !h.constraints.is_empty()
595        || !h.action_constraints.is_empty()
596        || !h.implied_inits.is_empty()
597        || h.view.is_some()
598    {
599        return Err(Error::unsupported("one bound optional atom is required"));
600    }
601    let opts = Opts {
602        memo: false,
603        step_memo: false,
604        primed_memo: false,
605        fold: false,
606        ..opts
607    };
608    compile_inner(h, store, opts, Some(test), false)
609}
610
611/// Compiles the handoff into a plan.
612///
613/// # Errors
614/// [`crate::ErrorKind::Unsupported`] naming the first construct Core does
615/// not implement.
616pub fn compile(h: &Handoff<'_>, store: Arc<Store>, opts: Opts) -> Result<Plan, Error> {
617    compile_inner(h, store, opts, None, false)
618}
619
620/// Compiles actual value/generator instruction maps for an explicitly observed run.
621/// Ordinary compilation retains its allocation-free disabled mapping route.
622///
623/// # Errors
624/// The existing compiler refusal or a bounded source-map capacity refusal.
625pub fn compile_debug(h: &Handoff<'_>, store: Arc<Store>, opts: Opts) -> Result<Plan, Error> {
626    if h.ir
627        .files()
628        .iter()
629        .map(|file| file.source.len())
630        .sum::<usize>()
631        > 16 << 20
632    {
633        return Err(Error::unsupported("compiled debugger source capacity"));
634    }
635    compile_inner(h, store, opts, None, true)
636}
637
638#[allow(
639    clippy::too_many_lines,
640    reason = "ordered role compilation and optional source map finalization"
641)]
642fn compile_inner(
643    h: &Handoff<'_>,
644    store: Arc<Store>,
645    opts: Opts,
646    test: Option<BoundTest>,
647    mapped: bool,
648) -> Result<Plan, Error> {
649    let nvars = h.ir.vars().len();
650    if nvars > 64 {
651        return Err(Error::unsupported("more than 64 state variables (M0 core)"));
652    }
653    let mut c = Compiler {
654        h,
655        effects: crate::plan::Effects::default(),
656        ir: h.ir,
657        code: Code {
658            source_map: mapped.then(|| crate::debug::SourceMap {
659                files: h.ir.files().to_vec(),
660                variables: h
661                    .ir
662                    .vars()
663                    .iter()
664                    .map(|id| h.ir.decl(*id).name.clone())
665                    .collect(),
666                ..crate::debug::SourceMap::default()
667            }),
668            ..Code::default()
669        },
670        debug_current: None,
671        debug_bytes: 0,
672        info: Vec::new(),
673        envs: Vec::new(),
674        m: Machine::new(store, nvars, opts, Memo::default()),
675        consts: HashMap::new(),
676        pre: HashMap::new(),
677        settled: HashMap::new(),
678        settle_fuel: 0,
679        fallback: HashMap::new(),
680        startup_assumptions: Vec::new(),
681        startup_assumption_false: None,
682        next_slot: 0,
683        reset_stack: Vec::new(),
684        at_stack: Vec::new(),
685        init_mode: false,
686        funs: HashMap::new(),
687        recfuns: HashMap::new(),
688        primed_funs: std::collections::HashSet::new(),
689        next_funs: std::collections::HashSet::new(),
690        open_funs: std::collections::HashSet::new(),
691        reentered_funs: std::collections::HashSet::new(),
692        fun_reads: HashMap::new(),
693        recursive_action_predicate: false,
694        instance_query_calls: false,
695        composition: composition::State::Absent,
696        frame: 0,
697        frames: 0,
698        lazies: Vec::new(),
699        compositions: Vec::new(),
700        def_slots: std::collections::HashSet::new(),
701        lifts: Vec::new(),
702        substs: Vec::new(),
703        fun_caps: HashMap::new(),
704        def_cache: HashMap::new(),
705        step: false,
706        subst_ids: 0,
707        effect_thunks: HashMap::new(),
708        leaf: 0,
709        opts,
710        stats: CompileStats::default(),
711        site_names: Vec::new(),
712        role_name: String::new(),
713        bound_preset: test.map(|_| Vec::new()),
714    };
715    c.startup_values();
716    // The initial predicates are conjoined, as TLC's (and the reference
717    // engine's `init_states`): one action.
718    let init = if h.init.is_empty() {
719        Vec::new()
720    } else {
721        vec![c.init_action(&h.init)?]
722    };
723    let mut next = Vec::new();
724    for r in &h.next {
725        next.push(c.action(r, false)?);
726    }
727    let mut invariants = Vec::new();
728    for r in &h.invariants {
729        invariants.push(c.check(r)?);
730    }
731    let view = h.view.as_ref().map(|r| c.view(r)).transpose()?;
732    let mut constraints = Vec::new();
733    for r in &h.constraints {
734        constraints.push(c.check(r)?);
735    }
736    let mut action_constraints = Vec::new();
737    for r in &h.action_constraints {
738        action_constraints.push(c.step_check(r)?);
739    }
740    let mut implied_inits = Vec::new();
741    for r in &h.implied_inits {
742        implied_inits.push(c.check(r)?);
743    }
744    let mut implied_actions = Vec::new();
745    for r in &h.implied_actions {
746        implied_actions.push(if let Some(test) = test {
747            c.bound_test(r, test)?
748        } else {
749            c.step_check(r)?
750        });
751    }
752    // Check the complete compiled plan: Info::effect deliberately does not
753    // follow Node::Call bodies, whereas every compiled effect sets effects.any.
754    // Conservatively refuse mixed-effect plans and unknown call targets rather
755    // than changing witness-dependent effects or inventing a purity analysis.
756    if c.recursive_action_predicate
757        && (c.effects.any
758            || c.code.nodes.iter().any(|node| {
759                matches!(node, Node::Call { fun, .. } if c.code.funs.get(*fun as usize).is_none())
760            }))
761    {
762        return Err(Error::unsupported(
763            "recursive Boolean action predicates in a compiled plan with effects or unproved calls",
764        ));
765    }
766    // An instance ENABLED query may read compiled calls only when no call
767    // body can reach an effect or a nested query, proved conservatively over
768    // the whole plan once every function body is compiled.
769    if c.instance_query_calls
770        && (c.effects.any
771            || c.code.nodes.iter().any(|node| {
772                matches!(node, Node::Call { fun, .. } if c.code.funs.get(*fun as usize).is_none())
773            })
774            || c.code.funs.iter().any(|fun| {
775                c.info
776                    .get(fun.body as usize)
777                    .is_none_or(|info| info.effect || info.nested_query)
778            }))
779    {
780        return Err(Error::unsupported(
781            "ENABLED in an INSTANCE with effects or recursive/nested calls (M1 core)",
782        ));
783    }
784    c.reset_composition_thunks();
785    c.stats.nodes = c.code.nodes.len();
786    c.stats.gnodes = c.code.gnodes.len();
787    let vars =
788        h.ir.vars()
789            .iter()
790            .map(|&d| h.ir.decl(d).name.clone())
791            .collect();
792    if c.m.heap.poisoned() {
793        return Err(Error::internal("a stale handle was read while compiling"));
794    }
795    let symmetry = symmetry(h, &c.m)?;
796    if let Some(map) = &mut c.code.source_map {
797        for check in invariants
798            .iter()
799            .chain(&implied_inits)
800            .chain(&implied_actions)
801        {
802            map.obligations.extend(
803                check
804                    .conjuncts
805                    .iter()
806                    .map(|part| (part.p, check.name.clone())),
807            );
808        }
809    }
810    let mut plan = Plan {
811        code: c.code,
812        vars,
813        init,
814        next,
815        invariants,
816        constraints,
817        action_constraints,
818        implied_inits,
819        implied_actions,
820        check_deadlock: h.check_deadlock,
821        symmetry,
822        effects: c.effects,
823        view,
824        stats: c.stats,
825        bound_preset: c.bound_preset.unwrap_or_default(),
826        startup_assumptions: c.startup_assumptions,
827        startup_assumption_false: c.startup_assumption_false,
828    };
829    if mapped {
830        let executable = crate::debug::reachable(&plan);
831        if let Some(map) = &mut plan.code.source_map {
832            map.executable = executable;
833        }
834    }
835    Ok(plan)
836}
837
838#[allow(
839    clippy::struct_excessive_bools,
840    reason = "independent compile modes and whole-plan proof obligations"
841)]
842struct Compiler<'a> {
843    h: &'a Handoff<'a>,
844    /// The effects compiled nodes reach (`Info::effect`).
845    effects: crate::plan::Effects,
846    ir: &'a Ir,
847    code: Code,
848    debug_current: Option<usize>,
849    debug_bytes: usize,
850    info: Vec<Info>,
851    envs: Vec<EnvFrame>,
852    m: Machine,
853    consts: HashMap<usize, Handle>,
854    pre: HashMap<DefId, Handle>,
855    /// Closed zero-arity definitions whose fold ran out of fuel, evaluated
856    /// once at their first use (`Self::settle`): the value, or `None` when
857    /// the evaluation failed and the body is evaluated where it is used.
858    settled: HashMap<DefId, Option<Handle>>,
859    /// Loop iterations spent by [`Self::settle`], against [`SETTLE_BUDGET`].
860    settle_fuel: u64,
861    /// Start-up values of deferred definitions the binder's evaluation
862    /// supplied ([`Handoff::startup_evaluator`]), used as `h.precomputed`.
863    fallback: HashMap<DefId, Value>,
864    /// The pure `ASSUME`s the compiler found `TRUE` ([`Handoff::assumptions`]).
865    startup_assumptions: Vec<DefId>,
866    /// The first pure `ASSUME` the compiler found `FALSE`, if it stopped there.
867    startup_assumption_false: Option<DefId>,
868    next_slot: u32,
869    reset_stack: Vec<Vec<u32>>,
870    at_stack: Vec<u32>,
871    init_mode: bool,
872    /// Recursive operators use the same context identity as function definitions.
873    funs: HashMap<RecKey, u32>,
874    /// Recursive function definitions `f[x \in S] == e` compiled as
875    /// functions of their argument.
876    recfuns: HashMap<RecKey, u32>,
877    /// The functions compiled as a next-state variant (`Mode::Primed`): the
878    /// whole body, and every capture, is read in the next state, so a call
879    /// of one reads primed variables.
880    primed_funs: std::collections::HashSet<u32>,
881    /// The functions a call of which reads primed variables: the next-state
882    /// variants, the plain variants of action-level definitions (SANY's
883    /// level, the maximum over a recursive section, known before the body
884    /// is compiled), and plain variants whose compiled body reads primed
885    /// variables. A call of one is never passed as a thunk.
886    next_funs: std::collections::HashSet<u32>,
887    /// The functions whose body is being compiled.
888    open_funs: std::collections::HashSet<u32>,
889    /// The open functions called from inside their own compilation, before
890    /// their body's reads were known.
891    reentered_funs: std::collections::HashSet<u32>,
892    /// The unprimed variables a call of a completed function reads through
893    /// its body ([`Self::fun_summary`]), beyond those its arguments read.
894    /// A function without an entry is assumed to read every variable.
895    fun_reads: HashMap<u32, u64>,
896    /// Whether an applied recursive function became a Boolean action guard.
897    recursive_action_predicate: bool,
898    /// Whether an `ENABLED` query in an instance reads a compiled call
899    /// (`Node::Call`), whose body facts `Info` does not follow.
900    instance_query_calls: bool,
901    /// Whether source-changing composition is present or being compiled.
902    composition: composition::State,
903    /// The runtime frame being compiled: a role's frame, a compiled
904    /// function body or a start-up evaluation. Slots index this frame only.
905    frame: u32,
906    /// Frames numbered so far.
907    frames: u32,
908    /// Every pushed thunk, with its frame (`Node::Lazy`).
909    lazies: Vec<(u32, P)>,
910    /// Every compiled composition site, with its frame.
911    compositions: Vec<(u32, composition::Site)>,
912    /// The thunk slots of `def_cache`.
913    def_slots: std::collections::HashSet<u32>,
914    /// The nested functions being compiled, innermost last.
915    lifts: Vec<Lift>,
916    /// The active `INSTANCE` substitutions, innermost last.
917    substs: Vec<SubstEntry>,
918    /// Each lifted function's captures: frames out from the definition's
919    /// lexical parent, and slot there.
920    fun_caps: HashMap<u32, Vec<(u32, usize)>>,
921    /// Zero-arity top-level definitions of state level, and in a step
922    /// predicate any zero-arity definition or substitution used by name,
923    /// cached once per frame activation: their thunk slot and body.
924    def_cache: HashMap<Cached, (u32, P)>,
925    /// Whether the role being compiled is a step predicate (an implied
926    /// action or an action constraint), evaluated on a complete pair: its
927    /// primed variables, like its unprimed ones, are fixed while it is
928    /// evaluated.
929    step: bool,
930    /// The next `SubstEntry::id`.
931    subst_ids: u32,
932    /// The generator expression of the first use of each thunk whose body
933    /// has an effect (`Compiler::effect_thunk_use`).
934    effect_thunks: HashMap<u32, u32>,
935    /// The generator expression being compiled (`Compiler::g`).
936    leaf: u32,
937    opts: Opts,
938    stats: CompileStats,
939    site_names: Vec<String>,
940    role_name: String,
941    /// `Some` while compiling one bound optional atom: the frame slots its
942    /// role binds, with their values, which the caller installs.
943    bound_preset: Option<Vec<(u32, Handle)>>,
944}
945
946impl Compiler<'_> {
947    fn debug_context(&mut self, expression: ExprId, env: usize) -> Result<Option<usize>, Error> {
948        let Some(map) = &self.code.source_map else {
949            return Ok(None);
950        };
951        if map.locations.len() >= 65_536 {
952            return Err(Error::unsupported(
953                "compiled debugger instruction context capacity",
954            ));
955        }
956        let frame = self
957            .envs
958            .get(env)
959            .ok_or_else(|| Error::internal("debugger compile environment"))?;
960        let definition = self.ir.def(frame.def);
961        let context_bytes = self
962            .substs
963            .iter()
964            .try_fold(definition.name.len() + 128, |bytes, entry| {
965                bytes.checked_add(self.ir.decl(entry.decl).name.len() + 96)
966            })
967            .ok_or_else(|| Error::unsupported("compiled debugger substitution capacity"))?;
968        let bytes = definition
969            .frame
970            .iter()
971            .try_fold(context_bytes, |bytes, slot| {
972                bytes.checked_add(slot.name.len() + 64)
973            })
974            .and_then(|bytes| self.debug_bytes.checked_add(bytes))
975            .filter(|bytes| *bytes <= 8 << 20)
976            .ok_or_else(|| Error::unsupported("compiled debugger source/local byte capacity"))?;
977        self.debug_bytes = bytes;
978        let locals = definition
979            .frame
980            .iter()
981            .zip(&frame.slots)
982            .map(|(name, slot)| {
983                let binding = match slot {
984                    Sb::Flat(slot)
985                    | Sb::Arg {
986                        how: ArgHow::Thunk(slot, _),
987                        ..
988                    }
989                    | Sb::LetVal {
990                        thunk: Some((slot, _)),
991                        ..
992                    } => crate::debug::Binding::Slot(*slot),
993                    Sb::Arg {
994                        how: ArgHow::Alias(node),
995                        ..
996                    } => crate::debug::Binding::Alias(*node),
997                    _ => crate::debug::Binding::Unavailable,
998                };
999                crate::debug::Local {
1000                    name: name.name.clone(),
1001                    binding,
1002                }
1003            })
1004            .collect();
1005        let location = crate::debug::Location {
1006            origin: self.ir.node(expression).origin,
1007            definition: definition.name.clone(),
1008            definition_id: frame.def.index(),
1009            environment_id: env,
1010            locals,
1011            caller: self.debug_current,
1012            substitutions: self
1013                .substs
1014                .iter()
1015                .map(|entry| crate::debug::Substitution {
1016                    declaration: self.ir.decl(entry.decl).name.clone(),
1017                    actual: match &entry.value {
1018                        Ok(Arg::Expr { expr, .. }) => Some(self.ir.node(*expr).origin),
1019                        _ => None,
1020                    },
1021                    identity: entry.id,
1022                })
1023                .collect(),
1024        };
1025        let Some(map) = &mut self.code.source_map else {
1026            return Ok(None);
1027        };
1028        let index = map.locations.len();
1029        map.locations.push(location);
1030        Ok(Some(index))
1031    }
1032
1033    /// Starts a new runtime frame, returning the enclosing one.
1034    fn new_frame(&mut self) -> u32 {
1035        self.frames += 1;
1036        std::mem::replace(&mut self.frame, self.frames)
1037    }
1038
1039    fn alloc(&mut self) -> u32 {
1040        let s = self.next_slot;
1041        self.next_slot += 1;
1042        s
1043    }
1044
1045    fn redirect(&self, d: DefId) -> DefId {
1046        let mut d = d;
1047        for _ in 0..64 {
1048            match self.h.redirects.get(&d) {
1049                Some(&t) if t != d => d = t,
1050                _ => break,
1051            }
1052        }
1053        d
1054    }
1055
1056    fn convert(&mut self, v: &Value) -> Result<Handle, Error> {
1057        crate::convert::from_value(&mut self.m.heap, v, self.h.ctx)
1058    }
1059
1060    /// Whether `d` has a startup value: the binder's, or one the compiler
1061    /// evaluated ([`Self::startup_values`]).
1062    fn has_startup_value(&self, d: DefId) -> bool {
1063        self.h.precomputed.contains_key(&d)
1064            || self.pre.contains_key(&d)
1065            || self.fallback.contains_key(&d)
1066    }
1067
1068    fn precomputed(&mut self, d: DefId) -> Result<Option<Handle>, Error> {
1069        if let Some(&h) = self.pre.get(&d) {
1070            return Ok(Some(h));
1071        }
1072        let v = match self.h.precomputed.get(&d) {
1073            Some(v) => v.clone(),
1074            None => match self.fallback.get(&d) {
1075                Some(v) => v.clone(),
1076                None => return Ok(None),
1077            },
1078        };
1079        // TLC's startup value of a constant definition may be lazy (a
1080        // filter or function over `Nat`, a recursive function): the core
1081        // then compiles the definition's body, which has the same value.
1082        let h = match self.convert(&v) {
1083            Ok(h) => h,
1084            Err(e)
1085                if e.kind() == crate::ErrorKind::Unsupported && !self.h.overrides.contains(&d) =>
1086            {
1087                return Ok(None);
1088            }
1089            Err(e) => return Err(e),
1090        };
1091        self.pre.insert(d, h);
1092        Ok(Some(h))
1093    }
1094
1095    fn new_env(&mut self, def: DefId, parent: Option<usize>) -> usize {
1096        let n = self.ir.def(def).frame.len();
1097        self.envs.push(EnvFrame {
1098            def,
1099            slots: vec![Sb::Unset; n],
1100            parent,
1101        });
1102        self.envs.len() - 1
1103    }
1104
1105    /// The environment of the enclosing activation of `def`, from `env`
1106    /// outwards.
1107    fn find_env(&self, env: usize, def: DefId) -> Option<usize> {
1108        let mut e = Some(env);
1109        while let Some(i) = e {
1110            if self.envs[i].def == def {
1111                return Some(i);
1112            }
1113            e = self.envs[i].parent;
1114        }
1115        None
1116    }
1117
1118    fn lexical_parent(&self, d: DefId, env: usize) -> Result<Option<usize>, Error> {
1119        match self.ir.def(d).scope {
1120            DefScope::TopLevel => Ok(None),
1121            DefScope::Local { parent } | DefScope::Inline { parent } => self
1122                .find_env(env, parent)
1123                .map(Some)
1124                .ok_or_else(|| Error::unsupported("a LET operator used outside its LET (M0 core)")),
1125            DefScope::LetValue { .. } => Err(Error::internal("a LET value used as an operator")),
1126        }
1127    }
1128
1129    // ------------------------------------------------------------------
1130    // Nodes, read sets and folding
1131    // ------------------------------------------------------------------
1132
1133    #[allow(
1134        clippy::too_many_lines,
1135        clippy::many_single_char_names,
1136        reason = "one arm per node kind"
1137    )]
1138    fn info_of(&self, n: &Node) -> Info {
1139        let mut i = Info::default();
1140        let mut add = |p: P, i: &mut Info| {
1141            if let Some(c) = self.info.get(p as usize) {
1142                i.vars |= c.vars;
1143                i.primed |= c.primed;
1144                i.calls |= c.calls;
1145                i.nested_query |= c.nested_query;
1146                i.heavy |= c.heavy;
1147                i.effect |= c.effect;
1148                union(&mut i.free, &c.free);
1149            }
1150        };
1151        let binders =
1152            |binds: &[Bind], body: &[P], i: &mut Info, add: &mut dyn FnMut(P, &mut Info)| {
1153                let mut inner = Info::default();
1154                for &b in body {
1155                    add(b, &mut inner);
1156                }
1157                let bound: Vec<u32> = binds.iter().flat_map(|b| b.slots.iter().copied()).collect();
1158                minus(&mut inner.free, &bound);
1159                i.vars |= inner.vars;
1160                i.primed |= inner.primed;
1161                i.calls |= inner.calls;
1162                i.nested_query |= inner.nested_query;
1163                i.heavy |= inner.heavy;
1164                i.effect |= inner.effect;
1165                union(&mut i.free, &inner.free);
1166                for b in binds {
1167                    add(b.domain, i);
1168                }
1169            };
1170        match n {
1171            Node::Const(_) => {}
1172            Node::Slot(s) => i.free.push(*s),
1173            Node::Lazy { body, .. }
1174            | Node::Scope { body, .. }
1175            | Node::Memo { body, .. }
1176            | Node::SameVars { eq: body, .. }
1177            | Node::Spec(body) => {
1178                add(*body, &mut i);
1179            }
1180            Node::InLazy { elem, set, .. } => {
1181                add(*elem, &mut i);
1182                add(*set, &mut i);
1183            }
1184            Node::Beta { chain, arg, .. } => {
1185                add(*chain, &mut i);
1186                add(*arg, &mut i);
1187            }
1188            Node::DomCheck { slot, domain, body } => {
1189                add(*domain, &mut i);
1190                add(*body, &mut i);
1191                minus(&mut i.free, &[*slot]);
1192            }
1193            Node::Var(v) => i.vars |= 1u64 << v,
1194            Node::Primed(v) => i.primed |= 1u64 << v,
1195            Node::Not(a)
1196            | Node::Neg(a)
1197            | Node::Powerset(a)
1198            | Node::BigUnion(a)
1199            | Node::Domain(a)
1200            | Node::Select(a, _) => {
1201                add(*a, &mut i);
1202            }
1203            Node::And(xs)
1204            | Node::Or(xs)
1205            | Node::SetEnum(xs)
1206            | Node::Product(xs)
1207            | Node::Tuple(xs)
1208            | Node::Std(_, xs) => {
1209                for &x in xs {
1210                    add(x, &mut i);
1211                }
1212            }
1213            Node::Lib { op, args: xs, .. } => {
1214                for &x in xs {
1215                    add(x, &mut i);
1216                }
1217                i.effect |= crate::stdlib::effectful(*op);
1218            }
1219            Node::Implies(a, b)
1220            | Node::Equiv(a, b)
1221            | Node::Eq(a, b)
1222            | Node::Neq(a, b)
1223            | Node::In(a, b)
1224            | Node::NotIn(a, b)
1225            | Node::Subseteq(a, b)
1226            | Node::Arith(_, a, b)
1227            | Node::Cmp(_, a, b)
1228            | Node::Range(a, b)
1229            | Node::SetBin(_, a, b)
1230            | Node::FcnSet(a, b)
1231            | Node::Apply(a, b) => {
1232                add(*a, &mut i);
1233                add(*b, &mut i);
1234            }
1235            Node::If(a, b, c) => {
1236                add(*a, &mut i);
1237                add(*b, &mut i);
1238                add(*c, &mut i);
1239            }
1240            Node::Case(arms, other) => {
1241                for &(g, v) in arms {
1242                    add(g, &mut i);
1243                    add(v, &mut i);
1244                }
1245                if let Some(o) = other {
1246                    add(*o, &mut i);
1247                }
1248            }
1249            Node::RecSet(fs) | Node::Record(fs) => {
1250                for &(_, x) in fs {
1251                    add(x, &mut i);
1252                }
1253            }
1254            Node::Filter { bind, pred, .. } => {
1255                binders(std::slice::from_ref(bind), &[*pred], &mut i, &mut add);
1256            }
1257            Node::Map { binds, body }
1258            | Node::FcnCons { binds, body }
1259            | Node::Quant { binds, body, .. } => {
1260                binders(binds, &[*body], &mut i, &mut add);
1261            }
1262            Node::Except { base, updates } => {
1263                add(*base, &mut i);
1264                for u in updates {
1265                    for &p in &u.path {
1266                        add(p, &mut i);
1267                    }
1268                    let mut inner = Info::default();
1269                    add(u.value, &mut inner);
1270                    minus(&mut inner.free, &[u.at]);
1271                    i.vars |= inner.vars;
1272                    i.primed |= inner.primed;
1273                    i.calls |= inner.calls;
1274                    i.nested_query |= inner.nested_query;
1275                    i.heavy |= inner.heavy;
1276                    i.effect |= inner.effect;
1277                    union(&mut i.free, &inner.free);
1278                }
1279            }
1280            Node::LibHo(_, args) => {
1281                for a in args {
1282                    match a {
1283                        LibArg::Value(p) => add(*p, &mut i),
1284                        LibArg::Op { params, body } => {
1285                            let mut inner = Info::default();
1286                            add(*body, &mut inner);
1287                            minus(&mut inner.free, params);
1288                            i.vars |= inner.vars;
1289                            i.primed |= inner.primed;
1290                            i.calls |= inner.calls;
1291                            i.nested_query |= inner.nested_query;
1292                            i.heavy |= inner.heavy;
1293                            i.effect |= inner.effect;
1294                            union(&mut i.free, &inner.free);
1295                        }
1296                    }
1297                }
1298            }
1299            Node::Call { fun, args } => {
1300                for &a in args {
1301                    add(a, &mut i);
1302                }
1303                i.calls = true;
1304                // A completed function's body reads only its own frame (the
1305                // arguments and captures passed here) and the variables of
1306                // its summary. An open one's reads are not known yet.
1307                match self.fun_reads.get(fun) {
1308                    Some(&vars) if !self.open_funs.contains(fun) => i.vars |= vars,
1309                    _ => i.vars = u64::MAX,
1310                }
1311                if self.next_funs.contains(fun) {
1312                    i.primed = u64::MAX;
1313                }
1314            }
1315            // The action's reads are not tracked variable by variable: it
1316            // reads every variable, so it is never folded or skipped.
1317            Node::Enabled { free, .. } => {
1318                union(&mut i.free, free);
1319                i.calls = true;
1320                i.nested_query = true;
1321                i.vars = u64::MAX;
1322            }
1323            Node::Composition { free, .. } => {
1324                union(&mut i.free, free);
1325                i.calls = true;
1326                i.nested_query = true;
1327                i.vars = u64::MAX;
1328                i.primed = u64::MAX;
1329            }
1330        }
1331        i.red = self.red_of(n);
1332        i
1333    }
1334
1335    fn red(&self, p: P) -> Red {
1336        self.info.get(p as usize).map_or(Red::Maybe, |i| i.red)
1337    }
1338
1339    /// TLC's reducibility of a node's value (`Info::red`).
1340    fn red_of(&self, n: &Node) -> Red {
1341        match n {
1342            Node::Const(h) => {
1343                if !h.is_compound() {
1344                    return Red::Yes;
1345                }
1346                match self.m.heap.view(*h).kind {
1347                    Kind::Product
1348                    | Kind::FcnSet
1349                    | Kind::RecSet
1350                    | Kind::Subset
1351                    | Kind::Nat
1352                    | Kind::Int
1353                    | Kind::SeqSet => Red::No,
1354                    _ => Red::Yes,
1355                }
1356            }
1357            Node::SetEnum(..) | Node::Range(..) | Node::Map { .. } => Red::Yes,
1358            Node::Product(_)
1359            | Node::FcnSet(..)
1360            | Node::RecSet(_)
1361            | Node::Powerset(_)
1362            | Node::Std(StdFn::Seq, _) => Red::No,
1363            Node::Filter { bind, .. } => match self.red(bind.domain) {
1364                Red::Yes => Red::Yes,
1365                Red::No => Red::No,
1366                Red::Maybe => Red::Maybe,
1367            },
1368            // `S \ T` is reducible as `S` is; `S \cup T` and `S \cap T` are
1369            // reducible when both are, and lazy when neither is.
1370            Node::SetBin(SetOp::Minus, a, _) => self.red(*a),
1371            Node::SetBin(_, a, b) => match (self.red(*a), self.red(*b)) {
1372                (Red::Yes, Red::Yes) => Red::Yes,
1373                (Red::No, Red::No) => Red::No,
1374                _ => Red::Maybe,
1375            },
1376            Node::Spec(b)
1377            | Node::Lazy { body: b, .. }
1378            | Node::Scope { body: b, .. }
1379            | Node::Memo { body: b, .. } => self.red(*b),
1380            _ => Red::Maybe,
1381        }
1382    }
1383
1384    /// The rewrite of `{E \in SUBSET T : \A e \in E : Q}` as `SUBSET F`,
1385    /// `F = {e \in T : Q}`, when its side conditions hold: one plain
1386    /// bound `E` over `SUBSET T` (or its folded constant), a predicate that
1387    /// is exactly a single-variable `\A` over `E` itself, and a body `Q`
1388    /// that does not read `E`, reads no primed variable, makes no call
1389    /// (recursive operator, `ENABLED`, composition) and has no effect.
1390    /// Then `Q` is a function of `e` alone during the filter, so
1391    /// `\A e \in E : Q` holds exactly when `E \subseteq F`. Returns the
1392    /// node of `F`, which enumeration uses in place of the filter
1393    /// (`Node::Filter::subset`).
1394    fn subset_rewrite(&mut self, bind: &Bind, pred: P) -> Result<Option<P>, Error> {
1395        let [outer] = *bind.slots else {
1396            return Ok(None);
1397        };
1398        if bind.tuple {
1399            return Ok(None);
1400        }
1401        let base = match self.code.nodes.get(bind.domain as usize) {
1402            Some(Node::Powerset(t)) => *t,
1403            Some(Node::Const(h)) if h.is_compound() => {
1404                let v = self.m.heap.view(*h);
1405                match (v.kind, v.data) {
1406                    (Kind::Subset, &[t]) => self.push(Node::Const(t))?,
1407                    _ => return Ok(None),
1408                }
1409            }
1410            _ => return Ok(None),
1411        };
1412        let Some(Node::Quant {
1413            kind: Quant::Forall,
1414            binds,
1415            body,
1416        }) = self.code.nodes.get(pred as usize)
1417        else {
1418            return Ok(None);
1419        };
1420        let [inner] = binds.as_ref() else {
1421            return Ok(None);
1422        };
1423        if inner.tuple
1424            || inner.slots.len() != 1
1425            || !matches!(
1426                self.code.nodes.get(inner.domain as usize),
1427                Some(Node::Slot(s)) if *s == outer
1428            )
1429        {
1430            return Ok(None);
1431        }
1432        let (inner, body) = (inner.clone(), *body);
1433        let Some(info) = self.info.get(body as usize) else {
1434            return Ok(None);
1435        };
1436        if info.free.contains(&outer) || info.primed != 0 || info.calls || info.effect {
1437            return Ok(None);
1438        }
1439        let set = self.push(Node::Filter {
1440            bind: Bind {
1441                slots: inner.slots,
1442                tuple: false,
1443                domain: base,
1444            },
1445            pred: body,
1446            subset: None,
1447        })?;
1448        Ok(Some(set))
1449    }
1450
1451    /// Pushes a filter, function constructor or set operation, wrapped in
1452    /// `Node::Spec` when TLC would build it lazily: the core builds it
1453    /// eagerly, so an evaluation error inside it may be one TLC never
1454    /// raises.
1455    fn push_lazy(&mut self, n: Node) -> Result<P, Error> {
1456        let eager = match &n {
1457            Node::Filter { bind, .. } => self.red(bind.domain) == Red::Yes,
1458            Node::FcnCons { binds, .. } => binds.iter().all(|b| self.red(b.domain) == Red::Yes),
1459            Node::SetBin(SetOp::Minus, a, _) => self.red(*a) == Red::Yes,
1460            Node::SetBin(_, a, b) => self.red(*a) == Red::Yes && self.red(*b) == Red::Yes,
1461            _ => true,
1462        };
1463        let p = self.push(n)?;
1464        if eager {
1465            Ok(p)
1466        } else {
1467            self.stats.speculative += 1;
1468            self.push(Node::Spec(p))
1469        }
1470    }
1471
1472    /// Whether a set node is one TLC certainly keeps lazy, a filter or a
1473    /// set operation over non-reducible sets: membership in it is decided
1474    /// structurally (`Node::InLazy`), as TLC decides it.
1475    fn lazy_set(&self, p: P) -> bool {
1476        let p = self.unspec(p);
1477        match self.code.nodes.get(p as usize) {
1478            Some(Node::Filter { .. } | Node::SetBin(..)) => self.red(p) == Red::No,
1479            Some(Node::Lazy { body, .. } | Node::Scope { body, .. }) => self.lazy_set(*body),
1480            // A primed definition's site is transparent to membership: the
1481            // test is decided on the body, never on a materialized value
1482            // (`Machine::member_lazy`).
1483            Some(Node::Memo { site, body })
1484                if self
1485                    .code
1486                    .sites
1487                    .get(*site as usize)
1488                    .is_some_and(|s| s.candidate) =>
1489            {
1490                self.lazy_set(*body)
1491            }
1492            _ => false,
1493        }
1494    }
1495
1496    /// The function constructor a function expression leads to through
1497    /// thunks, scopes and speculation wrappers, if any.
1498    fn lambda(&self, mut p: P) -> Option<P> {
1499        loop {
1500            match self.code.nodes.get(p as usize)? {
1501                Node::Spec(b) | Node::Lazy { body: b, .. } | Node::Scope { body: b, .. } => p = *b,
1502                Node::FcnCons { .. } => return Some(p),
1503                _ => return None,
1504            }
1505        }
1506    }
1507
1508    /// `f[a]`. TLC evaluates `f` with `KEEP_LAZY`, so a function
1509    /// constructor reached directly, or through a definition, stays lazy,
1510    /// and so does one over a non-reducible domain. One reached through a
1511    /// `LET` value or an operator argument (a `LazyValue`) over reducible
1512    /// domains is built eagerly (fixture `LzApplyDef`). A lazy one whose
1513    /// bound variables have no tuple pattern is applied without being built
1514    /// (`Node::Beta`); a lazy one with a tuple pattern is built
1515    /// speculatively.
1516    fn apply_value(&mut self, f: P, a: P) -> Result<P, Error> {
1517        let Some(fc) = self.lambda(f) else {
1518            return self.push(Node::Apply(f, a));
1519        };
1520        let Some(Node::FcnCons { binds, .. }) = self.code.nodes.get(fc as usize) else {
1521            return self.push(Node::Apply(f, a));
1522        };
1523        // Bound variables without tuple patterns: TLC's `FcnLambdaValue.apply`
1524        // binds each from its argument (several from a tuple) and evaluates
1525        // the body for that argument alone.
1526        let plain = binds.iter().all(|b| !b.tuple && !b.slots.is_empty());
1527        let non_reducible = binds.iter().any(|b| self.red(b.domain) == Red::No);
1528        let mut thunk = false;
1529        let mut p = f;
1530        while let Some(
1531            n @ (Node::Spec(b) | Node::Lazy { body: b, .. } | Node::Scope { body: b, .. }),
1532        ) = self.code.nodes.get(p as usize)
1533        {
1534            if let Node::Lazy { slot, .. } = n {
1535                thunk |= !self.def_slots.contains(slot);
1536            }
1537            p = *b;
1538        }
1539        if !non_reducible && thunk {
1540            // Built eagerly, as TLC builds it (speculatively already when
1541            // its domains may not be reducible: `push_lazy`).
1542            return self.push(Node::Apply(f, a));
1543        }
1544        if plain {
1545            self.stats.beta += 1;
1546            return self.push(Node::Beta {
1547                chain: f,
1548                fc,
1549                arg: a,
1550            });
1551        }
1552        let f = if matches!(self.code.nodes.get(f as usize), Some(Node::Spec(_))) {
1553            f
1554        } else {
1555            self.stats.speculative += 1;
1556            self.push(Node::Spec(f))?
1557        };
1558        self.push(Node::Apply(f, a))
1559    }
1560
1561    /// `DOMAIN f` of a function constructor TLC certainly keeps lazy (over
1562    /// a non-reducible domain): its domain, without building it
1563    /// (`FcnLambdaValue.getDomain`). `None` otherwise.
1564    fn lambda_domain(&mut self, f: P) -> Result<Option<P>, Error> {
1565        let Some(fc) = self.lambda(f) else {
1566            return Ok(None);
1567        };
1568        let Some(Node::FcnCons { binds, .. }) = self.code.nodes.get(fc as usize) else {
1569            return Ok(None);
1570        };
1571        if !binds.iter().any(|b| self.red(b.domain) == Red::No) {
1572            return Ok(None);
1573        }
1574        if binds.len() == 1 && (binds[0].tuple || binds[0].slots.len() == 1) {
1575            return Ok(Some(binds[0].domain));
1576        }
1577        let mut ds = Vec::new();
1578        for b in binds {
1579            if b.tuple {
1580                ds.push(b.domain);
1581            } else {
1582                ds.extend(std::iter::repeat_n(b.domain, b.slots.len()));
1583            }
1584        }
1585        Ok(Some(self.push(Node::Product(ds.into()))?))
1586    }
1587
1588    /// The recursive function a function expression names, if it is the
1589    /// name of `f[x \in S] == e` (outside or inside its body), compiled as
1590    /// a function of its argument.
1591    fn rec_target(
1592        &mut self,
1593        fcn: ExprId,
1594        env: usize,
1595        mode: Mode,
1596    ) -> Result<Option<(DefId, u32)>, Error> {
1597        let (d, call_env) = match &self.ir.node(fcn).expr {
1598            Expr::Local(r) => {
1599                let fe = self.frame_env(env, r.up)?;
1600                match self.envs[fe].slots.get(r.slot.index()).cloned() {
1601                    Some(Sb::RecSelf(d, f, defined_mode)) => {
1602                        if self.lifts.last().is_some_and(|l| fe < l.floor) {
1603                            return Err(Error::unsupported(
1604                                "a recursive function used inside a nested recursive definition (M1 core)",
1605                            ));
1606                        }
1607                        if mode != defined_mode {
1608                            return Err(Error::unsupported(
1609                                "a recursive function with mixed plain and primed self applications (M1 core)",
1610                            ));
1611                        }
1612                        return Ok(Some((d, f)));
1613                    }
1614                    Some(Sb::LetVal { def, env, .. }) => (def, env),
1615                    _ => return Ok(None),
1616                }
1617            }
1618            Expr::Def(d) => (*d, env),
1619            Expr::Apply {
1620                callee: OpRef::Def(d),
1621                args,
1622            } if args.is_empty() => (*d, env),
1623            _ => return Ok(None),
1624        };
1625        let d = self.redirect(d);
1626        if self.precomputed(d)?.is_some() {
1627            return Ok(None);
1628        }
1629        let def = self.ir.def(d);
1630        if !def.params.is_empty() || def.std.is_some() {
1631            return Ok(None);
1632        }
1633        let Expr::RecFcn { .. } = &self.ir.node(def.body).expr else {
1634            return Ok(None);
1635        };
1636        self.recfun(d, call_env, mode).map(|f| Some((d, f)))
1637    }
1638
1639    /// Compiles `f[x \in S] == e` as a function of its argument, in slot 0:
1640    /// `DomCheck { 0, S, e }`, with `f[...]` inside `e` a recursive call.
1641    fn recfun(&mut self, d: DefId, call_env: usize, mode: Mode) -> Result<u32, Error> {
1642        let owner = match self.ir.def(d).scope {
1643            DefScope::LetValue { parent, .. } => {
1644                Some(self.find_env(call_env, parent).ok_or_else(|| {
1645                    Error::unsupported(
1646                        "a recursive LET function outside its lexical activation (M1 core)",
1647                    )
1648                })?)
1649            }
1650            _ => self.lexical_parent(d, call_env)?,
1651        };
1652        let key = (
1653            d,
1654            mode,
1655            self.init_mode,
1656            owner,
1657            self.substs.last().map(|s| s.id),
1658        );
1659        if let Some(&f) = self.recfuns.get(&key) {
1660            return Ok(self.reenter(f));
1661        }
1662        let def = self.ir.def(d);
1663        let Expr::RecFcn { name, bounds, body } = &self.ir.node(def.body).expr else {
1664            return Err(Error::internal("not a recursive function definition"));
1665        };
1666        let (name, body) = (*name, *body);
1667        let [b] = &bounds[..] else {
1668            return Err(Error::unsupported(
1669                "a recursive function of several bound groups (M1 core)",
1670            ));
1671        };
1672        let ([x], false, Some(domain)) = (&b.vars[..], b.tuple, b.domain) else {
1673            return Err(Error::unsupported(
1674                "a recursive function of several arguments or a tuple pattern (M1 core)",
1675            ));
1676        };
1677        let x = *x;
1678        #[allow(clippy::cast_possible_truncation, reason = "bounded")]
1679        let id = self.code.funs.len() as u32;
1680        self.code.funs.push(Fun {
1681            name: def.name.clone(),
1682            params: 1,
1683            frame: 1,
1684            body: 0,
1685            caps: Box::new([]),
1686        });
1687        self.recfuns.insert(key, id);
1688        self.open_fun(id, mode, def.level);
1689        let saved_slot = self.next_slot;
1690        let saved_resets = std::mem::take(&mut self.reset_stack);
1691        let saved_cache = std::mem::take(&mut self.def_cache);
1692        let saved_at = std::mem::take(&mut self.at_stack);
1693        self.next_slot = 1;
1694        let saved_frame = self.new_frame();
1695        let (env, lifted) = match self.begin_recfun(d, id, call_env, owner, mode) {
1696            Ok(x) => x,
1697            Err(e) => {
1698                self.frame = saved_frame;
1699                self.next_slot = saved_slot;
1700                self.reset_stack = saved_resets;
1701                self.def_cache = saved_cache;
1702                self.at_stack = saved_at;
1703                return Err(e);
1704            }
1705        };
1706        if let Some(s) = self.envs[env].slots.get_mut(name.index()) {
1707            *s = Sb::RecSelf(d, id, mode);
1708        }
1709        if let Some(s) = self.envs[env].slots.get_mut(x.index()) {
1710            *s = Sb::Flat(0);
1711        }
1712        let r = self
1713            .p(domain, env, mode)
1714            .and_then(|dom| Ok((dom, self.p(body, env, mode)?)));
1715        let ended = self.end_fun(id, lifted);
1716        self.frame = saved_frame;
1717        let frame = self.next_slot;
1718        self.next_slot = saved_slot;
1719        self.reset_stack = saved_resets;
1720        self.def_cache = saved_cache;
1721        self.at_stack = saved_at;
1722        self.open_funs.remove(&id);
1723        let (dom, b) = r?;
1724        ended?;
1725        self.note_next_reads(id, &[dom, b])?;
1726        if mode == Mode::Primed && (self.info[dom as usize].effect || self.info[b as usize].effect)
1727        {
1728            return Err(Error::unsupported(
1729                "an effectful recursive function under a prime (M1 core)",
1730            ));
1731        }
1732        let checked = self.push(Node::DomCheck {
1733            slot: 0,
1734            domain: dom,
1735            body: b,
1736        })?;
1737        self.complete_fun(id, checked, frame);
1738        Ok(id)
1739    }
1740
1741    /// The node under any `Node::Spec` wrappers.
1742    fn unspec(&self, mut p: P) -> P {
1743        while let Some(Node::Spec(b)) = self.code.nodes.get(p as usize) {
1744            p = *b;
1745        }
1746        p
1747    }
1748
1749    /// Refuses an effect inside an expression whose evaluation order or
1750    /// count is TLC's representation choice rather than the expression's:
1751    /// a function constructor, filter or set map (TLC may build it eagerly,
1752    /// lazily or once per application), a speculative evaluation, and an
1753    /// operator argument of a library operator (applied in TLC's internal
1754    /// order).
1755    fn effect_allowed(&self, n: &Node) -> Result<(), Error> {
1756        let inside = |p: P| self.info.get(p as usize).is_some_and(|i| i.effect);
1757        let lazy = match n {
1758            Node::FcnCons { body, .. } | Node::Map { body, .. } => inside(*body),
1759            Node::Filter { pred, .. } => inside(*pred),
1760            Node::Spec(b) => inside(*b),
1761            Node::LibHo(_, args) => args
1762                .iter()
1763                .any(|a| matches!(a, LibArg::Op { body, .. } if inside(*body))),
1764            _ => false,
1765        };
1766        if lazy {
1767            return Err(Error::unsupported(
1768                "Print, PrintT, RandomElement, TLCSet or TLCGet inside a function constructor, set filter, set map or operator argument, which TLC may evaluate lazily or in its own order (M1 core)",
1769            ));
1770        }
1771        Ok(())
1772    }
1773
1774    /// Records a use of the thunk `slot`. A `LET`-bound definition or an
1775    /// operator argument whose body has an effect is TLC's `LazyValue`.
1776    /// Within one expression TLC forces it once, as the core does; across
1777    /// the conjuncts of `Init` or an action it evaluates the body again
1778    /// (fixture `RndLetRedraw`), where the core's thunk is forced once. So
1779    /// a use in a second generator expression is refused.
1780    fn effect_thunk_use(&mut self, slot: u32, body: P) -> Result<(), Error> {
1781        if !self.info.get(body as usize).is_some_and(|i| i.effect) {
1782            return Ok(());
1783        }
1784        let leaf = self.leaf;
1785        if *self.effect_thunks.entry(slot).or_insert(leaf) != leaf {
1786            return Err(Error::unsupported(
1787                "a LET-bound definition or operator argument with an effect (Print, PrintT, RandomElement) used in more than one conjunct, which TLC evaluates again in each (M1 core)",
1788            ));
1789        }
1790        Ok(())
1791    }
1792
1793    /// Whether a node may build a value TLC keeps as an interval or a lazy
1794    /// set, which printing must know (`Store::note_lazy_sets`).
1795    fn builds_lazy_set(&self, n: &Node) -> bool {
1796        match n {
1797            Node::Range(..)
1798            | Node::Domain(_)
1799            | Node::Powerset(_)
1800            | Node::FcnSet(..)
1801            | Node::RecSet(_)
1802            | Node::Product(_) => true,
1803            Node::Const(h) => self.holds_lazy_set(*h, &mut 0),
1804            _ => false,
1805        }
1806    }
1807
1808    /// Whether a constant holds an interval or a lazy set, looking at most
1809    /// at [`LAZY_SCAN`] nodes (beyond, it is assumed to).
1810    fn holds_lazy_set(&self, h: Handle, seen: &mut usize) -> bool {
1811        if !h.is_compound() {
1812            return false;
1813        }
1814        *seen += 1;
1815        if *seen > LAZY_SCAN {
1816            return true;
1817        }
1818        let v = self.m.heap.view(h);
1819        if matches!(
1820            v.kind,
1821            Kind::Interval | Kind::Subset | Kind::FcnSet | Kind::RecSet | Kind::Product
1822        ) {
1823            return true;
1824        }
1825        let data = v.data.to_vec();
1826        data.into_iter().any(|d| self.holds_lazy_set(d, seen))
1827    }
1828
1829    fn push(&mut self, n: Node) -> Result<P, Error> {
1830        if self.code.nodes.len() >= MAX_NODES {
1831            return Err(Error::unsupported(
1832                "a plan larger than the M0 core's inlining limit",
1833            ));
1834        }
1835        let info = self.info_of(&n);
1836        if !self.m.heap.store().lazy_sets() && self.builds_lazy_set(&n) {
1837            self.m.heap.store().note_lazy_sets();
1838        }
1839        if info.effect {
1840            self.effect_allowed(&n)?;
1841            self.effects.any = true;
1842        }
1843        if let Node::Lib { op, .. } = &n {
1844            match op {
1845                StdOp::TlcPrint | StdOp::TlcPrintT => self.effects.prints = true,
1846                StdOp::TlcRandomElement => self.effects.draws = true,
1847                StdOp::TlcTLCSet => self.effects.registers = true,
1848                _ => {}
1849            }
1850        }
1851        let foldable = !matches!(
1852            n,
1853            Node::Const(_) | Node::Slot(_) | Node::Var(_) | Node::Primed(_) | Node::Memo { .. }
1854        );
1855        #[allow(clippy::cast_possible_truncation, reason = "bounded by MAX_NODES")]
1856        let id = self.code.nodes.len() as P;
1857        if let Some(map) = &mut self.code.source_map {
1858            let source = self.debug_current.or_else(|| match &n {
1859                Node::Memo { body, .. } | Node::Scope { body, .. } => {
1860                    map.values.get(*body as usize).copied().flatten()
1861                }
1862                _ => None,
1863            });
1864            map.values.push(source);
1865        }
1866        if matches!(n, Node::Lazy { .. }) {
1867            self.lazies.push((self.frame, id));
1868        }
1869        self.code.nodes.push(n);
1870        let closed = info.vars == 0
1871            && info.primed == 0
1872            && info.free.is_empty()
1873            && !info.calls
1874            && !info.heavy
1875            && !info.effect;
1876        self.info.push(info);
1877        if self.opts.fold && foldable && closed {
1878            self.fold(id);
1879        }
1880        Ok(id)
1881    }
1882
1883    /// Folds a closed node to a constant, within [`FOLD_FUEL`] and what is
1884    /// left of [`FOLD_BUDGET`]. A fold that fails or runs out of fuel leaves
1885    /// the node alone: its error, if any, surfaces where TLC raises it.
1886    fn fold(&mut self, id: P) {
1887        let left = FOLD_BUDGET.saturating_sub(self.stats.fold_fuel);
1888        if left == 0 {
1889            self.stats.fold_skipped += 1;
1890            return;
1891        }
1892        let fuel = FOLD_FUEL.min(left);
1893        let started = std::time::Instant::now();
1894        self.m.set_fuel(fuel);
1895        let old = self.m.enter(self.next_slot + 1);
1896        let r = self.m.eval(&self.code, id);
1897        self.m.leave(old);
1898        let spent = fuel - self.m.fuel;
1899        let exhausted = self.m.fuel == 0;
1900        self.m.set_fuel(u64::MAX);
1901        let r = r.and_then(|h| self.m.heap.intern_const(h));
1902        self.m.heap.reset();
1903        self.stats.fold_fuel += spent;
1904        self.stats.fold_nanos += u64::try_from(started.elapsed().as_nanos()).unwrap_or(u64::MAX);
1905        match r {
1906            Ok(h) if !exhausted && !h.is_empty() => {
1907                self.code.nodes[id as usize] = Node::Const(h);
1908                // The folded node keeps TLC's reducibility of the expression.
1909                let red = self.info[id as usize].red;
1910                self.info[id as usize] = Info {
1911                    red,
1912                    ..Info::default()
1913                };
1914                self.stats.folded += 1;
1915            }
1916            _ if exhausted => {
1917                self.info[id as usize].heavy = true;
1918                self.stats.fold_abandoned += 1;
1919            }
1920            _ => {}
1921        }
1922    }
1923
1924    /// Evaluates the constant definitions the binder left to the core
1925    /// ([`Handoff::deferred`]), in definition order, before any role is
1926    /// compiled. Each body is compiled in a fresh top-level frame and
1927    /// evaluated without a fuel bound, as TLC evaluates it at startup, with
1928    /// the results of calls kept for the evaluation ([`crate::eval`]'s
1929    /// `CallCache`), and within [`STARTUP_TRANSIENT_BYTES`] of transient
1930    /// memory. A definition the core does not evaluate to a value (its body
1931    /// does not compile, is not closed, fails, or needs more memory) goes to
1932    /// the binder's evaluation ([`Handoff::startup_evaluator`]). One that fails
1933    /// there too is left alone: its uses compile it in place, and an error
1934    /// surfaces where it is used, as TLC reports it after swallowing the
1935    /// startup failure.
1936    fn startup_values(&mut self) {
1937        if self.h.deferred.is_empty() && self.h.assumptions.is_empty() {
1938            return;
1939        }
1940        let deferred: Vec<DefId> = self.h.deferred.iter().copied().collect();
1941        for d in deferred {
1942            if self.redirect(d) != d || self.h.precomputed.contains_key(&d) {
1943                continue;
1944            }
1945            let def = self.ir.def(d);
1946            let started = std::time::Instant::now();
1947            let skip = !def.params.is_empty()
1948                || def.std.is_some()
1949                || def.recursive
1950                || def.scope != DefScope::TopLevel
1951                || matches!(self.ir.node(def.body).expr, Expr::RecFcn { .. });
1952            let value = if skip { None } else { self.startup_value(d) };
1953            if let Some(h) = value {
1954                self.pre.insert(d, h);
1955                self.stats.startup_values += 1;
1956            } else if let Some(v) = self
1957                .h
1958                .startup_evaluator
1959                .as_ref()
1960                .and_then(|e| e.evaluate(d))
1961            {
1962                self.fallback.insert(d, v);
1963                self.stats.startup_fallbacks += 1;
1964            }
1965            self.stats.startup_nanos +=
1966                u64::try_from(started.elapsed().as_nanos()).unwrap_or(u64::MAX);
1967        }
1968        // The pure `ASSUME`s, in order, under the same bounds, stopping at
1969        // the first that is not `TRUE`, as TLC's `Tool.checkAssumptions`
1970        // does: an earlier `ASSUME` may guard a later one. `FALSE` is
1971        // reported ([`Plan::startup_assumption_false`]); anything else (an
1972        // error, a refusal or the memory bound) is left to the reference
1973        // evaluator, whose report TLC's matches.
1974        for a in self.h.assumptions.clone() {
1975            let def = self.ir.def(a);
1976            if !def.params.is_empty() || def.std.is_some() || def.scope != DefScope::TopLevel {
1977                break;
1978            }
1979            let started = std::time::Instant::now();
1980            let value = self.startup_value(a);
1981            self.stats.startup_nanos +=
1982                u64::try_from(started.elapsed().as_nanos()).unwrap_or(u64::MAX);
1983            if value == Some(Handle::TRUE) {
1984                self.startup_assumptions.push(a);
1985            } else {
1986                if value == Some(Handle::FALSE) {
1987                    self.startup_assumption_false = Some(a);
1988                }
1989                break;
1990            }
1991        }
1992        // A bounded evaluation may still have grown the arena: give that
1993        // memory back before the search.
1994        self.m.heap.reset();
1995        self.m.heap.arena.release();
1996    }
1997
1998    fn startup_value(&mut self, d: DefId) -> Option<Handle> {
1999        let body = self.ir.def(d).body;
2000        let saved_slot = self.next_slot;
2001        let saved_resets = std::mem::take(&mut self.reset_stack);
2002        let saved_cache = std::mem::take(&mut self.def_cache);
2003        let saved_at = std::mem::take(&mut self.at_stack);
2004        let saved_lifts = self.lifts.len();
2005        let saved_substs = self.substs.len();
2006        let init = std::mem::replace(&mut self.init_mode, false);
2007        let step = std::mem::replace(&mut self.step, false);
2008        // What compiling the body records about frame slots and compiled
2009        // functions belongs to this evaluation only: the roles compile
2010        // their own, in their own contexts.
2011        let saved_def_slots = std::mem::take(&mut self.def_slots);
2012        let saved_thunks = std::mem::take(&mut self.effect_thunks);
2013        let saved_funs = std::mem::take(&mut self.funs);
2014        let saved_recfuns = std::mem::take(&mut self.recfuns);
2015        self.next_slot = 0;
2016        let saved_frame = self.new_frame();
2017        let env = self.new_env(d, None);
2018        let compiled = self.p(body, env, Mode::Plain);
2019        self.frame = saved_frame;
2020        let frame = self.next_slot;
2021        self.def_slots = saved_def_slots;
2022        self.effect_thunks = saved_thunks;
2023        self.funs = saved_funs;
2024        self.recfuns = saved_recfuns;
2025        self.next_slot = saved_slot;
2026        self.reset_stack = saved_resets;
2027        self.def_cache = saved_cache;
2028        self.at_stack = saved_at;
2029        self.lifts.truncate(saved_lifts);
2030        self.substs.truncate(saved_substs);
2031        self.init_mode = init;
2032        self.step = step;
2033        let p = compiled.ok()?;
2034        let info = self.info.get(p as usize)?;
2035        // A call is assumed to read every variable; the compiler's machine
2036        // has no state, so a read raises an error, and the body is left
2037        // alone.
2038        if (info.vars != 0 && !info.calls)
2039            || info.primed != 0
2040            || !info.free.is_empty()
2041            || info.effect
2042        {
2043            return None;
2044        }
2045        self.m.set_fuel(u64::MAX);
2046        self.m.calls = Some(crate::eval::CallCache::default());
2047        self.m.set_transient_bound(STARTUP_TRANSIENT_BYTES);
2048        let old = self.m.enter(frame + 1);
2049        let r = self.m.eval(&self.code, p);
2050        self.m.leave(old);
2051        self.m.set_transient_bound(usize::MAX);
2052        if let Some(calls) = self.m.calls.take() {
2053            self.stats.startup_call_hits += calls.hits;
2054        }
2055        let r = r.and_then(|h| self.m.heap.intern_const(h));
2056        self.m.heap.reset();
2057        r.ok().filter(|h| !h.is_empty())
2058    }
2059
2060    /// `ENABLED A`: `A` compiled as an action
2061    /// in the current frame, searched for one successor at run time.
2062    ///
2063    /// An instance environment is supported when its variable substitutions
2064    /// resolve to the same root variables by name. TLC's branch cutoff then
2065    /// leaves every primed lookup unchanged, and no hidden candidate state
2066    /// requires the B2/B4 lazy-cache machinery. Other variable substitutions
2067    /// remain refused.
2068    fn enabled(
2069        &mut self,
2070        a: Option<ExprId>,
2071        sub: Option<ExprId>,
2072        env: usize,
2073        mode: Mode,
2074    ) -> Result<P, Error> {
2075        let a = a.ok_or_else(|| Error::internal("ENABLED without operand"))?;
2076        if mode == Mode::Primed {
2077            return Err(Error::unsupported("a primed ENABLED (M1 core)"));
2078        }
2079        if self.init_mode && !self.substs.is_empty() {
2080            return Err(Error::unsupported(
2081                "ENABLED in an INSTANCE inside an initial predicate (M1 core)",
2082            ));
2083        }
2084        let instance = !self.substs.is_empty();
2085        let first_slot = self.next_slot;
2086        // ENABLED evaluates its action on successors of its own, so its body
2087        // must not reuse a step predicate's primed thunks or memo sites.
2088        let init = std::mem::replace(&mut self.init_mode, false);
2089        let step = std::mem::replace(&mut self.step, false);
2090        let cache = std::mem::take(&mut self.def_cache);
2091        let g = (|| {
2092            self.enabled_substs()?;
2093            let action = self.g(a, env)?;
2094            if let Some(sub) = sub {
2095                let same = self.changed_test(sub, env)?;
2096                Ok(self.gpush(GNode::StepAngle { action, same }))
2097            } else {
2098                Ok(action)
2099            }
2100        })();
2101        self.init_mode = init;
2102        self.step = step;
2103        self.def_cache = cache;
2104        let g = g?;
2105        let mut free = Vec::new();
2106        self.instance_query_calls |= self.g_free(g, &mut free, 0, instance)?;
2107        free.retain(|&s| s < first_slot);
2108        self.push(Node::Enabled {
2109            g,
2110            free: free.into(),
2111        })
2112    }
2113
2114    /// Proves that hiding outer variable substitutions at an ENABLED branch
2115    /// changes no variable lookup. Constants are not hidden by TLC's cutoff.
2116    fn enabled_substs(&mut self) -> Result<(), Error> {
2117        if self.substs.is_empty() {
2118            return Ok(());
2119        }
2120        // Configuration operator overrides bypass SANY's level constraint
2121        // on source INSTANCE constant/operator parameters. Their captured
2122        // state and cutoff behavior needs a separate proof before admission.
2123        let stateful_config = self.h.constants.iter().flatten().any(|binding| {
2124            matches!(binding, ConstBinding::Def(d) if self.ir.def(self.redirect(*d)).level != Level::Constant)
2125        }) || self.h.redirects.values().any(|&d| self.ir.def(d).level != Level::Constant);
2126        if stateful_config {
2127            return Err(Error::unsupported(
2128                "ENABLED in an INSTANCE with a state-dependent configured operator (M1 core)",
2129            ));
2130        }
2131        for subst in self.substs.clone() {
2132            let decl = self.ir.decl(subst.decl);
2133            if !decl.variable {
2134                // Source constant/operator actuals are level zero, including
2135                // formal forwarding. Configuration bypasses were refused above.
2136                // Query effects and unknown calls are checked after generation.
2137                continue;
2138            }
2139            let root = self
2140                .ir
2141                .vars()
2142                .iter()
2143                .position(|&root| self.ir.decl(root).name == decl.name);
2144            let Some(root) = root else {
2145                return Err(Error::unsupported(
2146                    "ENABLED with a hidden INSTANCE variable (B2, B3, B4; M1 core)",
2147                ));
2148            };
2149            let target = match subst.value {
2150                Ok(Arg::Expr { expr, .. }) => {
2151                    self.outside(subst.depth, |c| c.target(expr, subst.env, true))?
2152                }
2153                Ok(Arg::Op { .. }) | Err(_) => None,
2154            };
2155            if target.map(usize::from) != Some(root) {
2156                return Err(Error::unsupported(
2157                    "ENABLED with a nonidentity INSTANCE variable substitution (B3; M1 core)",
2158                ));
2159            }
2160        }
2161        Ok(())
2162    }
2163
2164    /// The free slots of the value nodes a generator node reads, its own
2165    /// binders included (the caller drops the slots the action allocated).
2166    /// In an instance query, refuses value nodes with effects or nested
2167    /// queries and returns whether any reads a compiled call, whose body the
2168    /// caller checks once the whole plan is compiled.
2169    #[allow(clippy::too_many_lines, reason = "one arm per generator rule")]
2170    fn g_free(&self, g: G, out: &mut Vec<u32>, depth: u32, instance: bool) -> Result<bool, Error> {
2171        if depth > 10_000 {
2172            return Err(Error::unsupported("an action nested too deeply (M1 core)"));
2173        }
2174        let mut unproved = false;
2175        let mut calls = false;
2176        let mut inner = false;
2177        let mut p = |p: P, out: &mut Vec<u32>| {
2178            if let Some(i) = self.info.get(p as usize) {
2179                union(out, &i.free);
2180                unproved |= instance && (i.effect || i.nested_query);
2181                calls |= instance && i.calls;
2182            }
2183        };
2184        let unch = |items: &[crate::plan::Unch],
2185                    out: &mut Vec<u32>,
2186                    p: &mut dyn FnMut(P, &mut Vec<u32>)| {
2187            for u in items {
2188                if let crate::plan::Unch::Verify(x) = u {
2189                    p(*x, out);
2190                }
2191            }
2192        };
2193        let Some(node) = self.code.gnodes.get(g as usize) else {
2194            return Err(Error::internal("generator node out of range"));
2195        };
2196        match node {
2197            GNode::Composition { first, then, .. } => {
2198                inner |= self.g_free(*first, out, depth + 1, instance)?;
2199                inner |= self.g_free(*then, out, depth + 1, instance)?;
2200            }
2201            GNode::Conj(items) => {
2202                for &(g, x) in items {
2203                    p(x, out);
2204                    inner |= self.g_free(g, out, depth + 1, instance)?;
2205                }
2206            }
2207            GNode::Disj(gs) => {
2208                for &g in gs {
2209                    inner |= self.g_free(g, out, depth + 1, instance)?;
2210                }
2211            }
2212            GNode::Exists {
2213                binds,
2214                body,
2215                body_p,
2216            }
2217            | GNode::Forall {
2218                binds,
2219                body,
2220                body_p,
2221            } => {
2222                for b in binds {
2223                    p(b.domain, out);
2224                }
2225                p(*body_p, out);
2226                inner |= self.g_free(*body, out, depth + 1, instance)?;
2227            }
2228            GNode::If { cond, then, other } => {
2229                p(*cond, out);
2230                inner |= self.g_free(*then, out, depth + 1, instance)?;
2231                inner |= self.g_free(*other, out, depth + 1, instance)?;
2232            }
2233            GNode::Case { arms, other } => {
2234                for &(c, g) in arms {
2235                    p(c, out);
2236                    inner |= self.g_free(g, out, depth + 1, instance)?;
2237                }
2238                if let Some(o) = other {
2239                    inner |= self.g_free(*o, out, depth + 1, instance)?;
2240                }
2241            }
2242            GNode::Implies { lhs, rhs } => {
2243                p(*lhs, out);
2244                inner |= self.g_free(*rhs, out, depth + 1, instance)?;
2245            }
2246            GNode::Assign { rhs, .. } => p(*rhs, out),
2247            GNode::AssignIn { set, .. } | GNode::AssignInRaw { set, .. } => p(*set, out),
2248            GNode::Unchanged(items) => unch(items, out, &mut p),
2249            GNode::StepBox { action, vars } => {
2250                unch(vars, out, &mut p);
2251                inner |= self.g_free(*action, out, depth + 1, instance)?;
2252            }
2253            GNode::StepAngle { action, same } => {
2254                p(*same, out);
2255                inner |= self.g_free(*action, out, depth + 1, instance)?;
2256            }
2257            GNode::FcnAction { binds, arg, body } => {
2258                for b in binds {
2259                    p(b.domain, out);
2260                }
2261                p(*arg, out);
2262                inner |= self.g_free(*body, out, depth + 1, instance)?;
2263            }
2264            GNode::Scope { reset, body } => {
2265                union(out, reset);
2266                inner |= self.g_free(*body, out, depth + 1, instance)?;
2267            }
2268            GNode::Guard(x) => p(*x, out),
2269        }
2270        if unproved {
2271            return Err(Error::unsupported(
2272                "ENABLED in an INSTANCE with effects or recursive/nested calls (M1 core)",
2273            ));
2274        }
2275        Ok(calls || inner)
2276    }
2277
2278    fn konst(&mut self, h: Handle) -> Result<P, Error> {
2279        self.push(Node::Const(h))
2280    }
2281
2282    fn gpush(&mut self, g: GNode) -> G {
2283        #[allow(clippy::cast_possible_truncation, reason = "bounded by MAX_NODES")]
2284        let id = self.code.gnodes.len() as G;
2285        if let Some(map) = &mut self.code.source_map {
2286            map.generators.push(self.debug_current);
2287        }
2288        self.code.gnodes.push(g);
2289        id
2290    }
2291
2292    fn string(&mut self, s: &str) -> Result<Handle, Error> {
2293        self.m.heap.string(s)
2294    }
2295
2296    fn is_trivial(&self, p: P) -> bool {
2297        matches!(
2298            self.code.nodes.get(p as usize),
2299            Some(Node::Const(_) | Node::Slot(_) | Node::Var(_) | Node::Primed(_))
2300        )
2301    }
2302
2303    /// A memo site for a body, if it is eligible.
2304    fn site(&mut self, name: String, p: P) -> Result<Option<P>, Error> {
2305        if !self.opts.memo || self.init_mode {
2306            return Ok(None);
2307        }
2308        let Some(info) = self.info.get(p as usize) else {
2309            return Ok(None);
2310        };
2311        if info.primed != 0
2312            || info.effect
2313            || matches!(self.code.nodes.get(p as usize), Some(Node::Const(_)))
2314        {
2315            return Ok(None);
2316        }
2317        #[allow(clippy::cast_possible_truncation, reason = "at most 64 variables")]
2318        let vars: Vec<u16> = (0..64u16)
2319            .filter(|&v| info.vars & (1u64 << v) != 0)
2320            .take(MAX_KEY + 1)
2321            .collect();
2322        let slots = info.free.clone();
2323        if vars.len() + slots.len() > MAX_KEY || (vars.is_empty() && slots.is_empty()) {
2324            return Ok(None);
2325        }
2326        #[allow(clippy::cast_possible_truncation, reason = "bounded")]
2327        let site = self.code.sites.len() as u32;
2328        self.code.sites.push(MemoSite {
2329            name: name.clone(),
2330            vars: vars.into(),
2331            slots: slots.into(),
2332            primed: Box::new([]),
2333            step: false,
2334            candidate: false,
2335        });
2336        self.site_names.push(name);
2337        Ok(Some(self.push(Node::Memo { site, body: p })?))
2338    }
2339
2340    // ------------------------------------------------------------------
2341    // Roles
2342    // ------------------------------------------------------------------
2343
2344    /// Binds the `LET` values of a role's frame that splitting left unbound
2345    /// (the role sits inside their `LET`): lazy values, as TLC's
2346    /// `getActions` binds them, forced at most once per evaluation of the
2347    /// action (its frame starts empty).
2348    fn bind_role_lets(&mut self, env: usize, def: DefId) {
2349        let owner = self.reset_stack.len().saturating_sub(1);
2350        for (i, info) in self.ir.def(def).frame.iter().enumerate() {
2351            let dive_ir::SlotKind::LetValue(d) = info.kind else {
2352                continue;
2353            };
2354            if let Some(s @ Sb::Unset) = self.envs[env].slots.get_mut(i) {
2355                *s = Sb::LetVal {
2356                    def: d,
2357                    env,
2358                    thunk: None,
2359                    owner,
2360                };
2361            }
2362        }
2363    }
2364
2365    fn role_env(&mut self, r: &Role) -> Result<(usize, Vec<(u32, Handle)>), Error> {
2366        self.next_slot = 0;
2367        self.new_frame();
2368        self.role_env_after(r)
2369    }
2370
2371    /// [`Self::role_env`] for a role compiled into the same frame as the
2372    /// previous one: its slots follow the previous role's.
2373    fn role_env_after(&mut self, r: &Role) -> Result<(usize, Vec<(u32, Handle)>), Error> {
2374        self.reset_stack.clear();
2375        self.def_cache.clear();
2376        self.at_stack.clear();
2377        self.role_name.clone_from(&r.name);
2378        let def = self.ir.def(r.def);
2379        if def.depth != 0 {
2380            return Err(Error::unsupported(
2381                "a role inside a LET or LAMBDA (M0 core)",
2382            ));
2383        }
2384        let env = self.new_env(r.def, None);
2385        let mut preset = Vec::new();
2386        for (slot, v) in &r.slots {
2387            let flat = self.alloc();
2388            let h = self.convert(v)?;
2389            if let Some(s) = self.envs[env].slots.get_mut(slot.index()) {
2390                *s = Sb::Flat(flat);
2391            }
2392            preset.push((flat, h));
2393        }
2394        self.reset_stack.push(Vec::new());
2395        self.bind_role_lets(env, r.def);
2396        // Substitutions around the role: values are evaluated by name in
2397        // their own frame, outside any substitution (TLC's generator binds
2398        // them uncached: B5).
2399        self.substs.clear();
2400        for rs in &r.substs {
2401            let entry = match rs {
2402                RoleSubst::Operator { decl, def } => SubstEntry {
2403                    id: self.subst_id(),
2404                    decl: *decl,
2405                    value: Ok(Arg::Op {
2406                        op: OpRef::Def(*def),
2407                        level: self.ir.def(*def).level,
2408                    }),
2409                    env,
2410                    how: ArgHow::ByName,
2411                    depth: 0,
2412                },
2413                RoleSubst::Value { decl, value } => {
2414                    let h = self.convert(value)?;
2415                    let p = self.konst(h)?;
2416                    SubstEntry {
2417                        id: self.subst_id(),
2418                        decl: *decl,
2419                        value: Err(p),
2420                        env,
2421                        how: ArgHow::Alias(p),
2422                        depth: 0,
2423                    }
2424                }
2425                RoleSubst::Expr {
2426                    decl,
2427                    expr,
2428                    def,
2429                    slots,
2430                } => {
2431                    if self.ir.def(*def).depth != 0 {
2432                        return Err(Error::unsupported(
2433                            "an INSTANCE substitution inside a LET or LAMBDA (M1 core)",
2434                        ));
2435                    }
2436                    let senv = self.new_env(*def, None);
2437                    for (slot, v) in slots {
2438                        let flat = self.alloc();
2439                        let h = self.convert(v)?;
2440                        if let Some(s) = self.envs[senv].slots.get_mut(slot.index()) {
2441                            *s = Sb::Flat(flat);
2442                        }
2443                        preset.push((flat, h));
2444                    }
2445                    self.bind_role_lets(senv, *def);
2446                    SubstEntry {
2447                        id: self.subst_id(),
2448                        decl: *decl,
2449                        value: Ok(Arg::Expr {
2450                            expr: *expr,
2451                            pass: dive_ir::Pass::Lazy,
2452                        }),
2453                        env: senv,
2454                        how: ArgHow::ByName,
2455                        depth: 0,
2456                    }
2457                }
2458            };
2459            self.substs.push(entry);
2460        }
2461        Ok((env, preset))
2462    }
2463
2464    fn action(&mut self, r: &Role, init: bool) -> Result<Action, Error> {
2465        self.init_mode = init;
2466        let (env, preset) = self.role_env(r)?;
2467        let g = self.g(r.expr, env)?;
2468        Ok(Action {
2469            name: r.name.clone(),
2470            g,
2471            frame: self.next_slot,
2472            preset,
2473        })
2474    }
2475
2476    /// The initial predicates, conjoined left to right into one action
2477    /// named after the first.
2478    fn init_action(&mut self, roles: &[Role]) -> Result<Action, Error> {
2479        let [first, rest @ ..] = roles else {
2480            return Err(Error::internal("no initial predicate"));
2481        };
2482        if rest.is_empty() {
2483            return self.action(first, true);
2484        }
2485        self.init_mode = true;
2486        let mut items = Vec::with_capacity(roles.len());
2487        let mut presets = Vec::new();
2488        for (i, r) in roles.iter().enumerate() {
2489            let (env, preset) = if i == 0 {
2490                self.role_env(r)?
2491            } else {
2492                self.role_env_after(r)?
2493            };
2494            presets.extend(preset);
2495            let g = self.g(r.expr, env)?;
2496            let p = self.p(r.expr, env, Mode::Plain)?;
2497            items.push((g, p));
2498        }
2499        let g = self.gpush(GNode::Conj(items.into()));
2500        Ok(Action {
2501            name: first.name.clone(),
2502            g,
2503            frame: self.next_slot,
2504            preset: presets,
2505        })
2506    }
2507
2508    fn check(&mut self, r: &Role) -> Result<Check, Error> {
2509        self.init_mode = false;
2510        let (env, preset) = self.role_env(r)?;
2511        if let Some(bound) = &mut self.bound_preset {
2512            bound.extend(preset);
2513        } else if !preset.is_empty() {
2514            return Err(Error::unsupported(
2515                "an invariant with bound parameters (M0 core)",
2516            ));
2517        }
2518        let mut parts = Vec::new();
2519        self.conjuncts(r.expr, env, &mut parts)?;
2520        let mut conjuncts = Vec::new();
2521        for (k, (e, env)) in parts.into_iter().enumerate() {
2522            let p = self.p(e, env, Mode::Plain)?;
2523            let info = self.info[p as usize].clone();
2524            let skippable = info.free.is_empty() && info.primed == 0 && !info.effect;
2525            let reads = info.vars;
2526            let (p, site) = match self.site(format!("{}#{k}", r.name), p)? {
2527                Some(m) => {
2528                    let site = match self.code.nodes.get(m as usize) {
2529                        Some(Node::Memo { site, .. }) => Some(*site),
2530                        _ => None,
2531                    };
2532                    (m, site)
2533                }
2534                None => (p, None),
2535            };
2536            conjuncts.push(Conjunct {
2537                p,
2538                reads,
2539                skippable,
2540                site,
2541            });
2542        }
2543        Ok(Check {
2544            name: r.name.clone(),
2545            conjuncts,
2546            frame: self.next_slot,
2547        })
2548    }
2549
2550    fn bound_test(&mut self, r: &Role, test: BoundTest) -> Result<Check, Error> {
2551        if matches!(test, BoundTest::Predicate) {
2552            return self.step_check(r);
2553        }
2554        self.init_mode = false;
2555        let (env, preset) = self.role_env(r)?;
2556        if let Some(bound) = &mut self.bound_preset {
2557            bound.extend(preset);
2558        } else if !preset.is_empty() {
2559            return Err(Error::internal(
2560                "a bound atom outside bound-test compilation",
2561            ));
2562        }
2563        let p = match test {
2564            BoundTest::Enabled(sub) => self.enabled(Some(r.expr), sub, env, Mode::Plain)?,
2565            BoundTest::Nonstuttering(sub) => {
2566                // Unlike ENABLED, the reference Nonstuttering wrapper evaluates
2567                // two ordinary scoped state values and then the action. It
2568                // creates no branch cutoff; retain actual substitutions in
2569                // both modes rather than applying ENABLED's identity proof.
2570                self.step = true;
2571                let same = self.changed_test(sub, env)?;
2572                let changed = self.push(Node::Not(same))?;
2573                let action = self.p(r.expr, env, Mode::Plain)?;
2574                self.step = false;
2575                self.push(Node::And([changed, action].into()))?
2576            }
2577            BoundTest::Predicate => return Err(Error::internal("ordinary bound test dispatch")),
2578        };
2579        Ok(Check {
2580            name: r.name.clone(),
2581            conjuncts: vec![Conjunct {
2582                p,
2583                reads: u64::MAX,
2584                skippable: false,
2585                site: None,
2586            }],
2587            frame: self.next_slot,
2588        })
2589    }
2590
2591    /// A step predicate: a check whose conjuncts are never skipped, since
2592    /// the parent-delta skip compares a state with its parent and a step
2593    /// predicate has no such parent.
2594    fn step_check(&mut self, r: &Role) -> Result<Check, Error> {
2595        self.step = true;
2596        let k = self.check(r);
2597        self.step = false;
2598        let mut k = k?;
2599        k.conjuncts.iter_mut().for_each(|j| j.skippable = false);
2600        Ok(k)
2601    }
2602
2603    /// `VIEW`: one value-valued conjunct, the whole expression.
2604    fn view(&mut self, r: &Role) -> Result<Check, Error> {
2605        self.init_mode = false;
2606        let (env, preset) = self.role_env(r)?;
2607        if !preset.is_empty() {
2608            return Err(Error::unsupported("a VIEW with bound parameters (core)"));
2609        }
2610        let p = self.p(r.expr, env, Mode::Plain)?;
2611        let reads = self.info[p as usize].vars;
2612        Ok(Check {
2613            name: r.name.clone(),
2614            conjuncts: vec![Conjunct {
2615                p,
2616                reads,
2617                skippable: false,
2618                site: None,
2619            }],
2620            frame: self.next_slot,
2621        })
2622    }
2623
2624    /// Flattens a conjunction, through zero-arity definitions, into its
2625    /// conjuncts in order.
2626    fn conjuncts(
2627        &mut self,
2628        e: ExprId,
2629        env: usize,
2630        out: &mut Vec<(ExprId, usize)>,
2631    ) -> Result<(), Error> {
2632        match &self.ir.node(e).expr {
2633            Expr::Junction {
2634                kind: JunctionKind::And,
2635                items,
2636                ..
2637            } => {
2638                for &i in items {
2639                    self.conjuncts(i, env, out)?;
2640                }
2641                Ok(())
2642            }
2643            Expr::Label { body, .. } | Expr::Selected(body) => self.conjuncts(*body, env, out),
2644            Expr::Def(d) => {
2645                let d = self.redirect(*d);
2646                let def = self.ir.def(d);
2647                if self.has_startup_value(d)
2648                    || def.std.is_some()
2649                    || def.recursive
2650                    || !def.params.is_empty()
2651                    || matches!(def.scope, DefScope::LetValue { .. })
2652                {
2653                    out.push((e, env));
2654                    return Ok(());
2655                }
2656                let parent = self.lexical_parent(d, env)?;
2657                let inner = self.new_env(d, parent);
2658                self.conjuncts(def.body, inner, out)
2659            }
2660            _ => {
2661                out.push((e, env));
2662                Ok(())
2663            }
2664        }
2665    }
2666
2667    // ------------------------------------------------------------------
2668    // Value compilation
2669    // ------------------------------------------------------------------
2670
2671    fn p(&mut self, e: ExprId, env: usize, mode: Mode) -> Result<P, Error> {
2672        if self.code.source_map.is_none() {
2673            return self.p_inner(e, env, mode);
2674        }
2675        let previous = self.debug_current;
2676        self.debug_current = self.debug_context(e, env)?;
2677        let result = self.p_inner(e, env, mode);
2678        self.debug_current = previous;
2679        result
2680    }
2681
2682    #[allow(clippy::too_many_lines, reason = "one arm per expression kind")]
2683    fn p_inner(&mut self, e: ExprId, env: usize, mode: Mode) -> Result<P, Error> {
2684        let expr = &self.ir.node(e).expr;
2685        match expr {
2686            Expr::Bool(b) => self.konst(Handle::bool(*b)),
2687            Expr::Num(s) => {
2688                if self.m.heap.int_mode() == crate::int::IntMode::Tlc && s.parse::<i32>().is_err() {
2689                    // TLC rejects the numeral before checking starts.
2690                    return Err(Error::unsupported(format!(
2691                        "the numeral {s}, outside TLC's 32-bit integers (--compat=tlc)"
2692                    )));
2693                }
2694                let v = if let Some(h) = s.parse::<i64>().ok().and_then(Handle::int) {
2695                    h
2696                } else {
2697                    // Outside the inline range: a big integer constant.
2698                    let b = s
2699                        .parse::<num_bigint::BigInt>()
2700                        .map_err(|_| Error::unsupported(format!("the numeral {s}")))?;
2701                    let h = self.m.heap.int_from_big(&b);
2702                    let h = self.m.heap.intern_const(h);
2703                    self.m.heap.reset();
2704                    h?
2705                };
2706                self.konst(v)
2707            }
2708            Expr::Decimal { .. } => Err(Error::unsupported("decimal numbers")),
2709            Expr::Str(s) => {
2710                let h = self.string(s)?;
2711                self.konst(h)
2712            }
2713            Expr::Var { var, primed } => {
2714                #[allow(clippy::cast_possible_truncation, reason = "at most 64 variables")]
2715                let i = var.index() as u16;
2716                if self.init_mode {
2717                    if *primed || mode == Mode::Primed {
2718                        return Err(Error::unsupported(
2719                            "a primed variable in an initial predicate",
2720                        ));
2721                    }
2722                    return self.push(Node::Primed(i));
2723                }
2724                match (*primed, mode) {
2725                    (false, Mode::Plain) => self.push(Node::Var(i)),
2726                    (true, Mode::Plain) | (false, Mode::Primed) => self.push(Node::Primed(i)),
2727                    (true, Mode::Primed) => Err(Error::unsupported("a doubly primed variable")),
2728                }
2729            }
2730            Expr::Const(c) => self.const_expr(*c, env, mode),
2731            Expr::Local(r) => self.local(*r, env, mode),
2732            Expr::Def(d) => self.def_use(*d, env, mode),
2733            Expr::Apply { callee, args } => self.apply(callee, args, env, mode),
2734            Expr::Builtin { op, args } => self.builtin(*op, args, env, mode),
2735            Expr::Junction { kind, items, .. } => {
2736                let mut ps = Vec::with_capacity(items.len());
2737                for &i in items {
2738                    ps.push(self.p(i, env, mode)?);
2739                }
2740                match kind {
2741                    JunctionKind::And => self.push(Node::And(ps.clone().into())),
2742                    JunctionKind::Or => self.push(Node::Or(ps.clone().into())),
2743                }
2744            }
2745            Expr::Not(a) => {
2746                let a = self.p(*a, env, mode)?;
2747                self.push(Node::Not(a))
2748            }
2749            Expr::Implies(a, b) => {
2750                let a = self.p(*a, env, mode)?;
2751                let b = self.p(*b, env, mode)?;
2752                self.push(Node::Implies(a, b))
2753            }
2754            Expr::Equiv(a, b) => {
2755                let a = self.p(*a, env, mode)?;
2756                let b = self.p(*b, env, mode)?;
2757                self.push(Node::Equiv(a, b))
2758            }
2759            Expr::If { cond, then, other } => {
2760                let c = self.p(*cond, env, mode)?;
2761                let t = self.p(*then, env, mode)?;
2762                let o = self.p(*other, env, mode)?;
2763                self.push(Node::If(c, t, o))
2764            }
2765            Expr::Case { arms, other } => {
2766                let mut out = Vec::with_capacity(arms.len());
2767                for a in arms {
2768                    let g = self.p(a.guard, env, mode)?;
2769                    let v = self.p(a.value, env, mode)?;
2770                    out.push((g, v));
2771                }
2772                let o = match other {
2773                    Some(o) => Some(self.p(*o, env, mode)?),
2774                    None => None,
2775                };
2776                self.push(Node::Case(out.into(), o))
2777            }
2778            Expr::Quant { kind, bounds, body } => {
2779                let (binds, saved) = self.binds(bounds, env, mode)?;
2780                let b = self.p(*body, env, mode);
2781                self.unbind(saved);
2782                let b = b?;
2783                let kind = match kind {
2784                    QuantKind::Exists => Quant::Exists,
2785                    QuantKind::Forall => Quant::Forall,
2786                    QuantKind::Choose => Quant::Choose,
2787                };
2788                self.push(Node::Quant {
2789                    kind,
2790                    binds: binds.into(),
2791                    body: b,
2792                })
2793            }
2794            Expr::SetFilter { bound, pred } => {
2795                let (mut binds, saved) = self.binds(std::slice::from_ref(bound), env, mode)?;
2796                let b = self.p(*pred, env, mode);
2797                self.unbind(saved);
2798                let b = b?;
2799                let bind = binds
2800                    .pop()
2801                    .ok_or_else(|| Error::internal("filter without a bound"))?;
2802                let subset = self.subset_rewrite(&bind, b)?;
2803                self.push_lazy(Node::Filter {
2804                    bind,
2805                    pred: b,
2806                    subset,
2807                })
2808            }
2809            Expr::SetMap { expr, bounds } => {
2810                let (binds, saved) = self.binds(bounds, env, mode)?;
2811                let b = self.p(*expr, env, mode);
2812                self.unbind(saved);
2813                let b = b?;
2814                self.push(Node::Map {
2815                    binds: binds.into(),
2816                    body: b,
2817                })
2818            }
2819            Expr::FcnCons { bounds, body } => {
2820                let (binds, saved) = self.binds(bounds, env, mode)?;
2821                let b = self.p(*body, env, mode);
2822                self.unbind(saved);
2823                let b = b?;
2824                self.push_lazy(Node::FcnCons {
2825                    binds: binds.into(),
2826                    body: b,
2827                })
2828            }
2829            Expr::RecFcn { .. } => Err(Error::unsupported(
2830                "a recursive function used other than applied (M1 core)",
2831            )),
2832            Expr::SetEnum(items) => {
2833                let ps = self.ps(items, env, mode)?;
2834                self.push(Node::SetEnum(ps.into()))
2835            }
2836            Expr::Tuple(items) => {
2837                let ps = self.ps(items, env, mode)?;
2838                self.push(Node::Tuple(ps.into()))
2839            }
2840            Expr::Cartesian(items) => {
2841                let ps = self.ps(items, env, mode)?;
2842                self.push(Node::Product(ps.clone().into()))
2843            }
2844            Expr::Record(fields) | Expr::RecordSet(fields) => {
2845                let is_set = matches!(expr, Expr::RecordSet(_));
2846                let mut out = Vec::with_capacity(fields.len());
2847                for f in fields {
2848                    let name = self.string(&f.name)?;
2849                    let v = self.p(f.value, env, mode)?;
2850                    out.push((name, v));
2851                }
2852                out.sort_by(|a, b| self.m.heap.cmp(a.0, b.0));
2853                if out.windows(2).any(|w| w[0].0 == w[1].0) {
2854                    return Err(Error::unsupported("a record with a repeated field"));
2855                }
2856                if is_set {
2857                    self.push(Node::RecSet(out.into()))
2858                } else {
2859                    self.push(Node::Record(out.into()))
2860                }
2861            }
2862            Expr::FcnSet { domain, range } => {
2863                let d = self.p(*domain, env, mode)?;
2864                let r = self.p(*range, env, mode)?;
2865                self.push(Node::FcnSet(d, r))
2866            }
2867            Expr::FcnApply { fcn, arg } => {
2868                let (fcn, arg) = (*fcn, *arg);
2869                if let Some((d, fun)) = self.rec_target(fcn, env, mode)? {
2870                    let a = self.p(arg, env, mode)?;
2871                    return self.fun_call(d, fun, vec![a], env);
2872                }
2873                let f = self.p(fcn, env, mode)?;
2874                let a = self.p(arg, env, mode)?;
2875                self.apply_value(f, a)
2876            }
2877            Expr::RecordSelect { record, field } => {
2878                let r = self.p(*record, env, mode)?;
2879                let f = self.string(field)?;
2880                self.push(Node::Select(r, f))
2881            }
2882            Expr::Except { base, updates } => {
2883                let b = self.p(*base, env, mode)?;
2884                let mut out = Vec::with_capacity(updates.len());
2885                for u in updates {
2886                    let path = self.ps(&u.path, env, mode)?;
2887                    let at = self.alloc();
2888                    self.at_stack.push(at);
2889                    let v = self.p(u.value, env, mode);
2890                    self.at_stack.pop();
2891                    out.push(Update {
2892                        path: path.into(),
2893                        at,
2894                        value: v?,
2895                    });
2896                }
2897                self.push(Node::Except {
2898                    base: b,
2899                    updates: out.into(),
2900                })
2901            }
2902            Expr::ExceptAt => match self.at_stack.last() {
2903                Some(&at) => self.push(Node::Slot(at)),
2904                None => Err(Error::unsupported("@ outside EXCEPT")),
2905            },
2906            Expr::Let { defs, body } => {
2907                let body = *body;
2908                let defs = defs.clone();
2909                let (b, reset) = self.let_scope(&defs, env, |c| c.p(body, env, mode))?;
2910                if reset.is_empty() {
2911                    Ok(b)
2912                } else {
2913                    self.push(Node::Scope {
2914                        reset: reset.into(),
2915                        body: b,
2916                    })
2917                }
2918            }
2919            Expr::Selected(a) | Expr::Label { body: a, .. } => self.p(*a, env, mode),
2920            Expr::Prime(a) => {
2921                if mode == Mode::Primed {
2922                    return Err(Error::unsupported("a doubly primed expression"));
2923                }
2924                if self.init_mode {
2925                    return Err(Error::unsupported(
2926                        "a primed expression in an initial predicate",
2927                    ));
2928                }
2929                self.p(*a, env, Mode::Primed)
2930            }
2931            Expr::Unchanged(a) => self.unchanged_value(*a, env, mode),
2932            Expr::Subst { bindings, body } => {
2933                let (bindings, body) = (bindings.clone(), *body);
2934                let (b, reset) =
2935                    self.subst_scope(&bindings, env, mode, |c| c.p(body, env, mode))?;
2936                if reset.is_empty() {
2937                    Ok(b)
2938                } else {
2939                    self.push(Node::Scope {
2940                        reset: reset.into(),
2941                        body: b,
2942                    })
2943                }
2944            }
2945            Expr::SubstRef { decl, primed } => {
2946                let (decl, primed) = (*decl, *primed);
2947                if primed && mode == Mode::Primed {
2948                    return Err(Error::unsupported("a doubly primed expression"));
2949                }
2950                let mode = if primed { Mode::Primed } else { mode };
2951                self.subst_ref(decl, env, mode)
2952            }
2953            // `[A]_v` is `A \/ UNCHANGED v`; `<<A>>_v` is `A /\ v' # v`
2954            // (TLC's `OPCODE_sa`, `OPCODE_aa` in `eval`).
2955            Expr::StepBox { action, sub } | Expr::StepAngle { action, sub } => {
2956                if mode == Mode::Primed || self.init_mode {
2957                    return Err(Error::unsupported(
2958                        "[A]_v under a prime or in an initial predicate (M1 core)",
2959                    ));
2960                }
2961                let boxed = matches!(expr, Expr::StepBox { .. });
2962                let (action, sub) = (*action, *sub);
2963                let a = self.p(action, env, mode)?;
2964                let x = self.p(sub, env, Mode::Plain)?;
2965                let y = self.p(sub, env, Mode::Primed)?;
2966                let same = self.push(Node::Eq(x, y))?;
2967                if boxed {
2968                    self.push(Node::Or([a, same].into()))
2969                } else {
2970                    let changed = self.push(Node::Not(same))?;
2971                    self.push(Node::And([a, changed].into()))
2972                }
2973            }
2974            Expr::Enabled(a) => self.enabled(Some(*a), None, env, mode),
2975            Expr::Cdot(a, b) => self.composition_value(*a, *b, env, mode),
2976            Expr::Always(_)
2977            | Expr::Eventually(_)
2978            | Expr::LeadsTo(..)
2979            | Expr::WhilePlus(..)
2980            | Expr::Wf { .. }
2981            | Expr::Sf { .. }
2982            | Expr::TemporalQuant { .. } => Err(Error::unsupported(
2983                "a temporal formula in a state or action role",
2984            )),
2985            Expr::Unbound(n) => Err(Error::unsupported(format!("the unbound name {n}"))),
2986            Expr::Unevaluable(_) => Err(Error::unsupported("an unevaluable expression")),
2987        }
2988    }
2989
2990    /// A configured constant, including an imported declaration in an INSTANCE.
2991    fn const_expr(&mut self, c: dive_ir::ConstId, env: usize, mode: Mode) -> Result<P, Error> {
2992        match self.h.constants.get(c.index()).cloned().flatten() {
2993            Some(ConstBinding::Value(v)) => {
2994                let h = if let Some(&h) = self.consts.get(&c.index()) {
2995                    h
2996                } else {
2997                    let h = self.convert(&v)?;
2998                    self.consts.insert(c.index(), h);
2999                    h
3000                };
3001                self.konst(h)
3002            }
3003            Some(ConstBinding::Def(d)) => {
3004                let d = self.redirect(d);
3005                let body = if self.h.overrides.contains(&d) {
3006                    self.def_use(d, env, mode)?
3007                } else {
3008                    // A configured constant names the target's body, not the
3009                    // startup value of that target. Ordinary helpers retain
3010                    // their own legitimate startup values.
3011                    self.def_body(d, env, mode)?
3012                };
3013                self.configured_result(body)
3014            }
3015            None => Err(Error::unsupported("an unbound constant")),
3016        }
3017    }
3018
3019    /// Unknown calls cannot establish a configured target's runtime effects.
3020    fn configured_result(&self, body: P) -> Result<P, Error> {
3021        if self.info[body as usize].calls {
3022            return Err(Error::unsupported(
3023                "a configured constant target with unresolved recursive or ENABLED calls (core)",
3024            ));
3025        }
3026        Ok(body)
3027    }
3028
3029    fn ps(&mut self, items: &[ExprId], env: usize, mode: Mode) -> Result<Vec<P>, Error> {
3030        let mut out = Vec::with_capacity(items.len());
3031        for &i in items {
3032            out.push(self.p(i, env, mode)?);
3033        }
3034        Ok(out)
3035    }
3036
3037    fn unchanged_value(&mut self, a: ExprId, env: usize, mode: Mode) -> Result<P, Error> {
3038        if mode == Mode::Primed || self.init_mode {
3039            return Err(Error::unsupported(
3040                "UNCHANGED under a prime or in an initial predicate",
3041            ));
3042        }
3043        let x = self.p(a, env, Mode::Plain)?;
3044        let y = self.p(a, env, Mode::Primed)?;
3045        self.push(Node::Eq(x, y))
3046    }
3047
3048    /// Compiles bound groups: the domains first, then each variable gets a
3049    /// fresh slot. Returns the saved bindings to restore.
3050    fn binds(
3051        &mut self,
3052        bounds: &[Bound],
3053        env: usize,
3054        mode: Mode,
3055    ) -> Result<(Vec<Bind>, Saved), Error> {
3056        let mut domains = Vec::with_capacity(bounds.len());
3057        for b in bounds {
3058            let Some(d) = b.domain else {
3059                return Err(Error::unsupported("an unbounded quantifier or CHOOSE"));
3060            };
3061            domains.push(self.p(d, env, mode)?);
3062        }
3063        let mut saved = Vec::new();
3064        let mut binds = Vec::with_capacity(bounds.len());
3065        for (b, domain) in bounds.iter().zip(domains) {
3066            let mut slots = Vec::with_capacity(b.vars.len());
3067            for v in &b.vars {
3068                let flat = self.alloc();
3069                let old = self.envs[env]
3070                    .slots
3071                    .get(v.index())
3072                    .cloned()
3073                    .unwrap_or(Sb::Unset);
3074                saved.push((env, v.index(), old));
3075                if let Some(s) = self.envs[env].slots.get_mut(v.index()) {
3076                    *s = Sb::Flat(flat);
3077                }
3078                slots.push(flat);
3079            }
3080            binds.push(Bind {
3081                slots: slots.into(),
3082                tuple: b.tuple,
3083                domain,
3084            });
3085        }
3086        Ok((binds, saved))
3087    }
3088
3089    fn unbind(&mut self, saved: Saved) {
3090        for (env, slot, old) in saved.into_iter().rev() {
3091            if let Some(s) = self.envs[env].slots.get_mut(slot) {
3092                *s = old;
3093            }
3094        }
3095    }
3096
3097    /// Binds a `LET`'s zero-arity definitions as lazy values in `env`, runs
3098    /// `f`, and returns its result with the thunk slots to reset on entry.
3099    fn let_scope<T>(
3100        &mut self,
3101        defs: &[DefId],
3102        env: usize,
3103        f: impl FnOnce(&mut Self) -> Result<T, Error>,
3104    ) -> Result<(T, Vec<u32>), Error> {
3105        let owner = self.reset_stack.len();
3106        self.reset_stack.push(Vec::new());
3107        let mut saved = Vec::new();
3108        for &d in defs {
3109            if let DefScope::LetValue { parent, slot, .. } = self.ir.def(d).scope {
3110                let target = self.find_env(env, parent).unwrap_or(env);
3111                let old = self.envs[target]
3112                    .slots
3113                    .get(slot.index())
3114                    .cloned()
3115                    .unwrap_or(Sb::Unset);
3116                saved.push((target, slot.index(), old));
3117                if let Some(s) = self.envs[target].slots.get_mut(slot.index()) {
3118                    *s = Sb::LetVal {
3119                        def: d,
3120                        env: target,
3121                        thunk: None,
3122                        owner,
3123                    };
3124                }
3125            }
3126        }
3127        let r = f(self);
3128        self.unbind(saved);
3129        let reset = self.reset_stack.pop().unwrap_or_default();
3130        Ok((r?, reset))
3131    }
3132
3133    fn frame_env(&self, env: usize, up: u32) -> Result<usize, Error> {
3134        let mut e = env;
3135        for _ in 0..up {
3136            e = self.envs[e]
3137                .parent
3138                .ok_or_else(|| Error::internal("a local reference beyond the outermost frame"))?;
3139        }
3140        Ok(e)
3141    }
3142
3143    fn local(&mut self, r: LocalRef, env: usize, mode: Mode) -> Result<P, Error> {
3144        let fe = self.frame_env(env, r.up)?;
3145        if self.lifts.last().is_some_and(|l| fe < l.floor) {
3146            return self.capture(fe, r.slot.index(), mode);
3147        }
3148        let sb = self.envs[fe]
3149            .slots
3150            .get(r.slot.index())
3151            .cloned()
3152            .unwrap_or(Sb::Unset);
3153        match sb {
3154            Sb::Flat(f) => self.push(Node::Slot(f)),
3155            Sb::Arg {
3156                expr,
3157                env: aenv,
3158                how,
3159            } => match (how, mode) {
3160                (ArgHow::Alias(p), Mode::Plain) => Ok(p),
3161                (ArgHow::Alias(p), Mode::Primed) => match self.code.nodes.get(p as usize) {
3162                    Some(Node::Var(i)) => {
3163                        let i = *i;
3164                        self.push(Node::Primed(i))
3165                    }
3166                    Some(Node::Const(_) | Node::Slot(_)) => Ok(p),
3167                    _ => {
3168                        self.stats.by_name += 1;
3169                        self.p(expr, aenv, Mode::Primed)
3170                    }
3171                },
3172                (ArgHow::Thunk(slot, body), Mode::Plain) => {
3173                    self.effect_thunk_use(slot, body)?;
3174                    self.push(Node::Lazy { slot, body })
3175                }
3176                (ArgHow::Thunk(..), Mode::Primed) | (ArgHow::ByName, _) => {
3177                    self.stats.by_name += 1;
3178                    self.p(expr, aenv, mode)
3179                }
3180            },
3181            Sb::LetVal {
3182                def,
3183                env: lenv,
3184                thunk,
3185                owner,
3186            } => {
3187                let d = self.ir.def(def);
3188                if mode == Mode::Primed || d.level >= Level::Action {
3189                    return self.p(d.body, lenv, mode);
3190                }
3191                let (slot, body) = if let Some(t) = thunk {
3192                    t
3193                } else {
3194                    let body = self.p(d.body, lenv, Mode::Plain)?;
3195                    let slot = self.alloc();
3196                    if let Some(Sb::LetVal { thunk, .. }) =
3197                        self.envs[fe].slots.get_mut(r.slot.index())
3198                    {
3199                        *thunk = Some((slot, body));
3200                    }
3201                    if let Some(list) = self.reset_stack.get_mut(owner) {
3202                        list.push(slot);
3203                    }
3204                    (slot, body)
3205                };
3206                if self.is_trivial(body) {
3207                    return Ok(body);
3208                }
3209                self.effect_thunk_use(slot, body)?;
3210                self.push(Node::Lazy { slot, body })
3211            }
3212            Sb::RecSelf(..) => Err(Error::unsupported(
3213                "a recursive function used other than applied (M1 core)",
3214            )),
3215            Sb::Enclosing { env, slot } => self.capture(env, slot, mode),
3216            Sb::OpArg { .. } => Err(Error::internal("an operator parameter used as a value")),
3217            Sb::Unset => Err(Error::internal(format!(
3218                "unbound local {} in {}",
3219                self.ir
3220                    .def(self.envs[fe].def)
3221                    .frame
3222                    .get(r.slot.index())
3223                    .map_or("?", |s| s.name.as_str()),
3224                self.ir.def(self.envs[fe].def).name
3225            ))),
3226        }
3227    }
3228
3229    /// A reference, inside a lifted function, to a local of an enclosing
3230    /// definition: a capture slot of the function.
3231    fn capture(&mut self, fe: usize, slot: usize, mode: Mode) -> Result<P, Error> {
3232        // A function's captures are computed once per call, in its mode: a
3233        // read in the other mode would need a second value of the capture.
3234        match (self.lifts.last().map(|l| l.mode), mode) {
3235            (None | Some(Mode::Plain), Mode::Primed) => {
3236                return Err(Error::unsupported(
3237                    "a recursive LET definition reading an enclosing local under a prime (M1 core)",
3238                ));
3239            }
3240            (Some(Mode::Primed), Mode::Plain) => {
3241                return Err(Error::unsupported(
3242                    "a recursive LET definition under a prime reading an enclosing local unprimed (M1 core)",
3243                ));
3244            }
3245            _ => {}
3246        }
3247        if matches!(self.envs[fe].slots.get(slot), Some(Sb::RecSelf(..))) {
3248            return Err(Error::unsupported(
3249                "a recursive function used inside a nested recursive definition (M1 core)",
3250            ));
3251        }
3252        let Some(l) = self.lifts.last() else {
3253            return Err(Error::internal("a capture outside a lifted function"));
3254        };
3255        let mut k = 0u32;
3256        let mut e = l.parent;
3257        loop {
3258            match e {
3259                Some(x) if x == fe => break,
3260                Some(x) => {
3261                    e = self.envs[x].parent;
3262                    k += 1;
3263                }
3264                None => {
3265                    return Err(Error::unsupported(
3266                        "a recursive function with a dynamic INSTANCE capture outside its lexical activation (M1 core)",
3267                    ));
3268                }
3269            }
3270        }
3271        if let Some(&(_, _, c)) = l.caps.iter().find(|c| c.0 == k && c.1 == slot) {
3272            return self.push(Node::Slot(c));
3273        }
3274        let c = self.alloc();
3275        if let Some(l) = self.lifts.last_mut() {
3276            l.caps.push((k, slot, c));
3277        }
3278        self.push(Node::Slot(c))
3279    }
3280
3281    /// A call of a compiled function: the arguments, then the captures
3282    /// (compiled at the call site), or, inside the function itself, its own
3283    /// capture slots (filled in when its body is complete).
3284    fn fun_call(&mut self, d: DefId, fun: u32, mut ps: Vec<P>, env: usize) -> Result<P, Error> {
3285        if let Some(i) = self.lifts.iter().position(|l| l.fun == fun) {
3286            // Top-level functions still need the substitution frame boundary,
3287            // but have no lexical captures to pass along a mutual back-edge.
3288            if i + 1 != self.lifts.len() && self.lifts[i].parent.is_some() {
3289                return Err(Error::unsupported(
3290                    "mutually recursive nested definitions (M1 core)",
3291                ));
3292            }
3293            let call = self.push(Node::Call {
3294                fun,
3295                args: ps.into(),
3296            })?;
3297            if let Some(l) = self.lifts.get_mut(i) {
3298                l.self_calls.push(call);
3299            }
3300            return Ok(call);
3301        }
3302        let caps = self.fun_caps.get(&fun).cloned().unwrap_or_default();
3303        if !caps.is_empty() {
3304            let mode = if self.primed_funs.contains(&fun) {
3305                Mode::Primed
3306            } else {
3307                Mode::Plain
3308            };
3309            let parent = match self.ir.def(d).scope {
3310                DefScope::LetValue { parent, .. } => self.find_env(env, parent),
3311                _ => self.lexical_parent(d, env)?,
3312            };
3313            let Some(parent) = parent else {
3314                return Err(Error::internal("captures of a top-level definition"));
3315            };
3316            for (k, slot) in caps {
3317                #[allow(clippy::cast_possible_truncation, reason = "frame slots are u32")]
3318                let r = LocalRef {
3319                    up: k,
3320                    slot: dive_ir::Slot(slot as u32),
3321                };
3322                let v = self.local(r, parent, mode)?;
3323                if self.info[v as usize].calls {
3324                    return Err(Error::unsupported(
3325                        "a recursive definition capturing a value with unproved recursive calls (M1 core)",
3326                    ));
3327                }
3328                let v = if self.is_trivial(v) {
3329                    v
3330                } else {
3331                    self.stats.speculative += 1;
3332                    self.push(Node::Spec(v))?
3333                };
3334                ps.push(v);
3335            }
3336        }
3337        self.push(Node::Call {
3338            fun,
3339            args: ps.into(),
3340        })
3341    }
3342
3343    /// Starts a fresh runtime frame for `d`, including top-level definitions.
3344    /// Its boundary prevents caller substitutions from reusing frame slots;
3345    /// a nested definition's lexical parent supplies its captures.
3346    fn begin_fun(
3347        &mut self,
3348        d: DefId,
3349        fun: u32,
3350        env: usize,
3351        mode: Mode,
3352    ) -> Result<(usize, bool), Error> {
3353        let parent = self.lexical_parent(d, env)?;
3354        let inner = self.new_env(d, parent);
3355        self.lifts.push(Lift {
3356            floor: inner,
3357            parent,
3358            fun,
3359            caps: Vec::new(),
3360            self_calls: Vec::new(),
3361            mode,
3362        });
3363        Ok((inner, true))
3364    }
3365
3366    /// LET values use their owner's frame layout, rather than owning a frame.
3367    fn begin_recfun(
3368        &mut self,
3369        d: DefId,
3370        fun: u32,
3371        env: usize,
3372        owner: Option<usize>,
3373        mode: Mode,
3374    ) -> Result<(usize, bool), Error> {
3375        if !matches!(self.ir.def(d).scope, DefScope::LetValue { .. }) {
3376            return self.begin_fun(d, fun, env, mode);
3377        }
3378        let owner = owner.ok_or_else(|| Error::internal("recursive LET function owner"))?;
3379        let inner = self.new_env(self.envs[owner].def, self.envs[owner].parent);
3380        for (slot, binding) in self.envs[inner].slots.iter_mut().enumerate() {
3381            *binding = Sb::Enclosing { env: owner, slot };
3382        }
3383        self.lifts.push(Lift {
3384            floor: inner,
3385            parent: Some(owner),
3386            fun,
3387            caps: Vec::new(),
3388            self_calls: Vec::new(),
3389            mode,
3390        });
3391        Ok((inner, true))
3392    }
3393
3394    /// Ends `begin_fun`: records the captures and completes the recursive
3395    /// calls with them.
3396    fn end_fun(&mut self, fun: u32, lifted: bool) -> Result<(), Error> {
3397        if !lifted {
3398            return Ok(());
3399        }
3400        let Some(l) = self.lifts.pop() else {
3401            return Err(Error::internal("unbalanced lifted function"));
3402        };
3403        let slots: Vec<u32> = l.caps.iter().map(|c| c.2).collect();
3404        for &call in &l.self_calls {
3405            let mut extra = Vec::with_capacity(slots.len());
3406            for &c in &slots {
3407                extra.push(self.push(Node::Slot(c))?);
3408            }
3409            if let Some(Node::Call { args, .. }) = self.code.nodes.get_mut(call as usize) {
3410                let mut v = args.to_vec();
3411                v.extend(extra);
3412                *args = v.into();
3413            }
3414        }
3415        if let Some(f) = self.code.funs.get_mut(fun as usize) {
3416            f.caps = slots.clone().into();
3417        }
3418        self.fun_caps
3419            .insert(fun, l.caps.iter().map(|c| (c.0, c.1)).collect());
3420        Ok(())
3421    }
3422
3423    /// Binds an instance's substitutions for `f`, as operator arguments are
3424    /// bound (`inline`): each expression value is compiled outside the
3425    /// substitution, then aliased, made a thunk, or passed by name. Returns
3426    /// `f`'s result with the thunk slots to reset on entry.
3427    fn subst_scope<T>(
3428        &mut self,
3429        bindings: &[dive_ir::SubstBinding],
3430        env: usize,
3431        mode: Mode,
3432        f: impl FnOnce(&mut Self) -> Result<T, Error>,
3433    ) -> Result<(T, Vec<u32>), Error> {
3434        let depth = self.substs.len();
3435        let mut reset = Vec::new();
3436        let mut entries = Vec::with_capacity(bindings.len());
3437        for b in bindings {
3438            let how = match &b.value {
3439                Arg::Expr { expr, .. } => {
3440                    let cp = self.p(*expr, env, mode)?;
3441                    if self.opts.eager && self.is_trivial(cp) {
3442                        self.stats.aliased += 1;
3443                        ArgHow::Alias(cp)
3444                    } else if self.info[cp as usize].primed == 0 {
3445                        self.stats.thunks += 1;
3446                        let slot = self.alloc();
3447                        reset.push(slot);
3448                        ArgHow::Thunk(slot, cp)
3449                    } else {
3450                        ArgHow::ByName
3451                    }
3452                }
3453                Arg::Op { .. } => ArgHow::ByName,
3454            };
3455            let id = self.subst_id();
3456            entries.push(SubstEntry {
3457                id,
3458                decl: b.decl,
3459                value: Ok(b.value.clone()),
3460                env,
3461                how,
3462                depth,
3463            });
3464        }
3465        self.stats.substituted += entries.len();
3466        self.substs.extend(entries);
3467        let r = f(self);
3468        self.substs.truncate(depth);
3469        Ok((r?, reset))
3470    }
3471
3472    /// Runs `f` in the dynamic context of depth `depth` (outside the
3473    /// substitutions above it).
3474    fn outside<T>(&mut self, depth: usize, f: impl FnOnce(&mut Self) -> T) -> T {
3475        let inner = self.substs.split_off(depth.min(self.substs.len()));
3476        let r = f(self);
3477        self.substs.extend(inner);
3478        r
3479    }
3480
3481    /// The operator an operator declaration stands for: the innermost
3482    /// active substitution, followed through substitutions by declarations
3483    /// of enclosing instances (`INSTANCE M WITH F <- F`, nested), each
3484    /// looked up in the context outside its own substitution.
3485    fn subst_op(&self, decl: dive_ir::DeclId) -> Result<OpRef, Error> {
3486        let mut decl = decl;
3487        let mut limit = self.substs.len();
3488        loop {
3489            let Some(i) = self.substs[..limit].iter().rposition(|s| s.decl == decl) else {
3490                return match self.ir.decl(decl).constant {
3491                    Some(c) => Ok(OpRef::Const(c)),
3492                    None => Err(Error::unsupported(
3493                        "an unsubstituted operator declaration (M1 core)",
3494                    )),
3495                };
3496            };
3497            let s = &self.substs[i];
3498            match &s.value {
3499                Ok(Arg::Op {
3500                    op: OpRef::Subst(d2),
3501                    ..
3502                }) => {
3503                    decl = *d2;
3504                    limit = s.depth.min(i);
3505                }
3506                Ok(Arg::Op {
3507                    op: op @ (OpRef::Def(_) | OpRef::Std(_) | OpRef::Const(_)),
3508                    ..
3509                }) if !matches!(op, OpRef::Def(d) if self.ir.def(self.redirect(*d)).scope != DefScope::TopLevel) =>
3510                {
3511                    return Ok(op.clone());
3512                }
3513                _ => {
3514                    return Err(Error::unsupported(
3515                        "an INSTANCE substitution of an operator by a non-top-level operator (M1 core)",
3516                    ));
3517                }
3518            }
3519        }
3520    }
3521
3522    /// A reference to a substituted declaration: the innermost active
3523    /// substitution, or else the declaration itself (a root variable or a
3524    /// constant).
3525    fn subst_ref(&mut self, decl: dive_ir::DeclId, env: usize, mode: Mode) -> Result<P, Error> {
3526        let Some(i) = self.substs.iter().rposition(|s| s.decl == decl) else {
3527            let d = self.ir.decl(decl);
3528            #[allow(clippy::cast_possible_truncation, reason = "at most 64 variables")]
3529            return match (d.var, d.constant) {
3530                (Some(v), _) if self.init_mode => {
3531                    if mode == Mode::Primed {
3532                        return Err(Error::unsupported(
3533                            "a primed variable in an initial predicate",
3534                        ));
3535                    }
3536                    self.push(Node::Primed(v.index() as u16))
3537                }
3538                (Some(v), _) => match mode {
3539                    Mode::Plain => self.push(Node::Var(v.index() as u16)),
3540                    Mode::Primed => self.push(Node::Primed(v.index() as u16)),
3541                },
3542                (None, Some(c)) => self.const_expr(c, env, mode),
3543                (None, None) => Err(Error::unsupported(format!(
3544                    "the unsubstituted variable {} of an instantiated module (M1 core)",
3545                    d.name
3546                ))),
3547            };
3548        };
3549        let SubstEntry {
3550            id,
3551            value,
3552            env,
3553            how,
3554            depth,
3555            ..
3556        } = self.substs[i].clone();
3557        let expr = match value {
3558            Ok(Arg::Expr { expr, .. }) => expr,
3559            Err(p) => return Ok(p),
3560            Ok(Arg::Op { .. }) => {
3561                return Err(Error::unsupported(
3562                    "an operator substitution used as a value (M1 core)",
3563                ));
3564            }
3565        };
3566        if self.lifts.last().is_some_and(|lift| env < lift.floor) {
3567            // Caller aliases and thunk slots belong to another runtime frame.
3568            // Constants are frame-independent; otherwise compile fresh nodes
3569            // here. Existing capture resolution refuses non-lexical locals.
3570            if let ArgHow::Alias(mut p) | ArgHow::Thunk(_, mut p) = how {
3571                // Disabling eager aliases can wrap the same constant in
3572                // caller thunks. Reuse only the constant, never their slots.
3573                while let Some(Node::Lazy { body, .. }) = self.code.nodes.get(p as usize) {
3574                    p = *body;
3575                }
3576                if matches!(self.code.nodes.get(p as usize), Some(Node::Const(_))) {
3577                    return Ok(p);
3578                }
3579            }
3580            let body = self.outside(depth, |c| c.p(expr, env, mode))?;
3581            if self.info[body as usize].effect || self.info[body as usize].calls {
3582                return Err(Error::unsupported(
3583                    "an effectful or recursive INSTANCE substitution inside a recursive function (M1 core)",
3584                ));
3585            }
3586            return Ok(body);
3587        }
3588        match (how, mode) {
3589            (ArgHow::Alias(p), Mode::Plain) => Ok(p),
3590            (ArgHow::Alias(p), Mode::Primed) => match self.code.nodes.get(p as usize) {
3591                Some(Node::Var(v)) => {
3592                    let v = *v;
3593                    self.push(Node::Primed(v))
3594                }
3595                Some(Node::Const(_) | Node::Slot(_)) => Ok(p),
3596                _ => {
3597                    self.stats.by_name += 1;
3598                    self.outside(depth, |c| c.p(expr, env, Mode::Primed))
3599                }
3600            },
3601            (ArgHow::Thunk(slot, body), Mode::Plain) => {
3602                self.effect_thunk_use(slot, body)?;
3603                self.push(Node::Lazy { slot, body })
3604            }
3605            (ArgHow::Thunk(..), Mode::Primed) | (ArgHow::ByName, _) => {
3606                self.stats.by_name += 1;
3607                if self.step {
3608                    return self.step_cached(Cached::Subst(id, mode), |c| {
3609                        c.outside(depth, |c| c.p(expr, env, mode))
3610                    });
3611                }
3612                self.outside(depth, |c| c.p(expr, env, mode))
3613            }
3614        }
3615    }
3616
3617    /// A fresh `SubstEntry::id`.
3618    fn subst_id(&mut self) -> u32 {
3619        self.subst_ids += 1;
3620        self.subst_ids
3621    }
3622
3623    /// In a step predicate, a body evaluated at most once per frame
3624    /// activation: the pair does not change within one, so a pure body
3625    /// with no bound variable has one value. TLC evaluates it by name at
3626    /// each use; the result, or the first error, is the same. The thunk
3627    /// counts as by-name for the function-application rule
3628    /// (`def_slots`).
3629    fn step_cached(
3630        &mut self,
3631        key: Cached,
3632        compile: impl FnOnce(&mut Self) -> Result<P, Error>,
3633    ) -> Result<P, Error> {
3634        if let Some(&(slot, body)) = self.def_cache.get(&key) {
3635            return self.push(Node::Lazy { slot, body });
3636        }
3637        let body = compile(self)?;
3638        let info = &self.info[body as usize];
3639        if !info.free.is_empty() || info.effect || info.calls || self.is_trivial(body) {
3640            return Ok(body);
3641        }
3642        let body = self.step_site(key, body)?;
3643        let slot = self.alloc();
3644        self.def_cache.insert(key, (slot, body));
3645        self.def_slots.insert(slot);
3646        self.stats.cached_defs += 1;
3647        self.push(Node::Lazy { slot, body })
3648    }
3649
3650    /// Whether a body is already cached (a thunk or a memo site), or only
3651    /// assembles a tuple, record or set from leaves and thunks (such as a
3652    /// `vars` tuple): rebuilding it is cheaper than keeping an interned
3653    /// copy of each.
3654    fn assembles(&self, mut body: P) -> bool {
3655        while let Some(Node::Scope { body: b, .. } | Node::Spec(b)) =
3656            self.code.nodes.get(body as usize)
3657        {
3658            body = *b;
3659        }
3660        let leaf = |p: &P| {
3661            matches!(
3662                self.code.nodes.get(*p as usize),
3663                Some(
3664                    Node::Const(_)
3665                        | Node::Slot(_)
3666                        | Node::Var(_)
3667                        | Node::Primed(_)
3668                        | Node::Lazy { .. }
3669                        | Node::Memo { .. }
3670                )
3671            )
3672        };
3673        match self.code.nodes.get(body as usize) {
3674            Some(Node::Lazy { .. } | Node::Memo { .. }) => true,
3675            Some(Node::Tuple(items) | Node::SetEnum(items)) => items.iter().all(leaf),
3676            Some(Node::Record(fields)) => fields.iter().all(|(_, p)| leaf(p)),
3677            _ => false,
3678        }
3679    }
3680
3681    /// A step predicate's cached body as a memo site keyed on the
3682    /// variables it reads, primed and unprimed (`Opts::step_memo`): its
3683    /// value is a function of them, the same for every pair that agrees
3684    /// on them, such as the successors of one state.
3685    fn step_site(&mut self, key: Cached, body: P) -> Result<P, Error> {
3686        if !self.opts.step_memo || self.assembles(body) {
3687            return Ok(body);
3688        }
3689        let info = &self.info[body as usize];
3690        let bits = |m: u64| -> Vec<u16> {
3691            #[allow(clippy::cast_possible_truncation, reason = "at most 64 variables")]
3692            (0..64u16).filter(|&v| m & (1u64 << v) != 0).collect()
3693        };
3694        let (vars, primed) = (bits(info.vars), bits(info.primed));
3695        if vars.len() + primed.len() > MAX_KEY || (vars.is_empty() && primed.is_empty()) {
3696            return Ok(body);
3697        }
3698        let name = match key {
3699            Cached::Def(d, mode, _) => format!("{} ({mode:?}, step)", self.ir.def(d).name),
3700            Cached::Subst(id, mode) => format!("substitution {id} ({mode:?}, step)"),
3701        };
3702        #[allow(clippy::cast_possible_truncation, reason = "bounded")]
3703        let site = self.code.sites.len() as u32;
3704        self.code.sites.push(MemoSite {
3705            name: name.clone(),
3706            vars: vars.into(),
3707            slots: Box::new([]),
3708            primed: primed.into(),
3709            step: true,
3710            candidate: false,
3711        });
3712        self.site_names.push(name);
3713        self.push(Node::Memo { site, body })
3714    }
3715
3716    /// Whether the innermost substitution of a declaration is a value
3717    /// (`RoleSubst::Value`).
3718    fn subst_is_value(&self, decl: dive_ir::DeclId) -> bool {
3719        self.substs
3720            .iter()
3721            .rev()
3722            .find(|s| s.decl == decl)
3723            .is_some_and(|s| s.value.is_err())
3724    }
3725
3726    /// The substitution for a declaration, if one is active: its expression,
3727    /// environment and dynamic depth.
3728    fn subst_expr(&self, decl: dive_ir::DeclId) -> Option<Result<(ExprId, usize, usize), Error>> {
3729        let i = self.substs.iter().rposition(|s| s.decl == decl)?;
3730        let s = &self.substs[i];
3731        Some(match &s.value {
3732            Ok(Arg::Expr { expr, .. }) => Ok((*expr, s.env, s.depth)),
3733            Ok(Arg::Op { .. }) => Err(Error::unsupported(
3734                "an operator substitution used as a value (M1 core)",
3735            )),
3736            Err(_) => Err(Error::unsupported(
3737                "a substitution by a value used as an action or a variable (M1 core)",
3738            )),
3739        })
3740    }
3741
3742    /// A use of a zero-arity definition.
3743    fn def_use(&mut self, d: DefId, env: usize, mode: Mode) -> Result<P, Error> {
3744        let r = self.redirect(d);
3745        if r != d
3746            && !self.h.overrides.contains(&r)
3747            && self.ir.def(r).effects.intersects(dive_ir::Effects::IMPURE)
3748        {
3749            // `Op <- D`: `Op`'s tool object is `D`'s node, whose body TLC
3750            // evaluates at every use, not `D`'s own startup value. A pure
3751            // body's startup value is the same, so only an impure one
3752            // (`RandomElement`, ...) is compiled again.
3753            return self.def_body(r, env, mode);
3754        }
3755        let d = r;
3756        if let Some(h) = self.precomputed(d)? {
3757            return self.konst(h);
3758        }
3759        if self.substs.is_empty()
3760            && let Some(&Some(h)) = self.settled.get(&d)
3761        {
3762            return self.konst(h);
3763        }
3764        self.def_body(d, env, mode)
3765    }
3766
3767    /// Evaluates the compiled body of a closed zero-arity top-level
3768    /// definition once, when its constant fold ran out of [`FOLD_FUEL`]
3769    /// (`Info::heavy`): within [`SETTLE_FUEL`], what is left of
3770    /// [`SETTLE_BUDGET`] and [`STARTUP_TRANSIENT_BYTES`], into the permanent
3771    /// store, as TLC evaluates a constant definition at start-up
3772    /// (`SpecProcessor.processConstantDefns`). Its uses then read the value
3773    /// instead of rebuilding it in every state. The body is the same
3774    /// node a fold would replace, with the same reducibility, so its uses
3775    /// behave as they do for a folded one.
3776    ///
3777    /// An evaluation that fails, refuses, or runs out of fuel or memory
3778    /// changes nothing: the body is evaluated where it is used, as before,
3779    /// so an error surfaces only where TLC raises it. Only a definition
3780    /// outside any `INSTANCE` substitution is evaluated, so that its value
3781    /// depends on the definition alone and is kept for all its uses.
3782    fn settle(&mut self, d: DefId, body: P) -> P {
3783        // A deferred definition was evaluated without a fuel bound already
3784        // (`Self::startup_values`): one that is still compiled failed there.
3785        if !self.opts.fold
3786            || !self.substs.is_empty()
3787            || self.h.deferred.contains(&d)
3788            || self.settled.contains_key(&d)
3789        {
3790            return body;
3791        }
3792        let Some(info) = self.info.get(body as usize) else {
3793            return body;
3794        };
3795        let closed = info.vars == 0
3796            && info.primed == 0
3797            && info.free.is_empty()
3798            && !info.calls
3799            && !info.effect;
3800        if !closed || !info.heavy || self.is_trivial(body) {
3801            return body;
3802        }
3803        let fuel = SETTLE_FUEL.min(SETTLE_BUDGET.saturating_sub(self.settle_fuel));
3804        if fuel == 0 {
3805            return body;
3806        }
3807        let started = std::time::Instant::now();
3808        self.m.set_fuel(fuel);
3809        let bound = std::mem::replace(&mut self.m.transient_bound, STARTUP_TRANSIENT_BYTES);
3810        let old = self.m.enter(self.next_slot + 1);
3811        let r = self.m.eval(&self.code, body);
3812        self.m.leave(old);
3813        self.m.transient_bound = bound;
3814        let spent = fuel - self.m.fuel;
3815        let exhausted = self.m.fuel == 0;
3816        self.m.set_fuel(u64::MAX);
3817        let r = r.and_then(|h| self.m.heap.intern_const(h));
3818        self.m.heap.reset();
3819        self.settle_fuel += spent;
3820        self.stats.startup_nanos += u64::try_from(started.elapsed().as_nanos()).unwrap_or(u64::MAX);
3821        match r {
3822            Ok(h) if !exhausted && !h.is_empty() => {
3823                self.code.nodes[body as usize] = Node::Const(h);
3824                let red = self.info[body as usize].red;
3825                self.info[body as usize] = Info {
3826                    red,
3827                    ..Info::default()
3828                };
3829                self.settled.insert(d, Some(h));
3830                self.stats.startup_values += 1;
3831            }
3832            _ => {
3833                self.settled.insert(d, None);
3834            }
3835        }
3836        body
3837    }
3838
3839    /// Compiles a definition's body without replacing it by its startup value.
3840    fn def_body(&mut self, d: DefId, env: usize, mode: Mode) -> Result<P, Error> {
3841        let def = self.ir.def(d);
3842        if let Some(op) = def.std {
3843            return self.std_apply(op, &[], env, mode);
3844        }
3845        if !def.params.is_empty() {
3846            return Err(Error::unsupported(format!(
3847                "the operator {} used as a value",
3848                def.name
3849            )));
3850        }
3851        if def.recursive {
3852            return self.call(d, &[], env, mode);
3853        }
3854        let key = Cached::Def(d, mode, self.substs.last().map(|s| s.id));
3855        if self.step && !self.init_mode && def.scope == DefScope::TopLevel {
3856            let parent = self.lexical_parent(d, env)?;
3857            return self.step_cached(key, |c| {
3858                let inner = c.new_env(d, parent);
3859                let body = c.p(def.body, inner, mode)?;
3860                Ok(c.settle(d, body))
3861            });
3862        }
3863        let cacheable = mode == Mode::Plain && !self.init_mode && def.scope == DefScope::TopLevel;
3864        if cacheable && let Some(&(slot, body)) = self.def_cache.get(&key) {
3865            return self.push(Node::Lazy { slot, body });
3866        }
3867        let parent = self.lexical_parent(d, env)?;
3868        let inner = self.new_env(d, parent);
3869        let body = self.p(def.body, inner, mode)?;
3870        let body = self.settle(d, body);
3871        // A state-level definition is a pure function of the current state:
3872        // evaluate it at most once per frame activation (the state does not
3873        // change within one). TLC re-evaluates it; the result is the same.
3874        let info = &self.info[body as usize];
3875        if cacheable
3876            && info.free.is_empty()
3877            && info.primed == 0
3878            && !info.effect
3879            && !info.calls
3880            && !self.is_trivial(body)
3881        {
3882            let slot = self.alloc();
3883            self.def_cache.insert(key, (slot, body));
3884            self.def_slots.insert(slot);
3885            self.stats.cached_defs += 1;
3886            return self.push(Node::Lazy { slot, body });
3887        }
3888        if def.scope == DefScope::TopLevel && !self.init_mode {
3889            return self.primed_site(d, mode, body);
3890        }
3891        Ok(body)
3892    }
3893
3894    /// A zero-arity top-level definition that a next-state action reads
3895    /// primed, such as `totalOpOrder'` in `InnerSerial`, as a memo site
3896    /// keyed on the variables it reads, primed and unprimed
3897    /// (`Opts::primed_memo`).
3898    ///
3899    /// The body is pure (no effect), makes no call and reads no bound
3900    /// variable, so its value is a function of the key alone. At run time
3901    /// the site is used only once every primed variable of its key is
3902    /// assigned (`Machine::memo_eval` bypasses an unassigned one, and the
3903    /// body then raises the error it raises), so a body that does not read
3904    /// the variable an enumeration `x' \in S` assigns is evaluated once
3905    /// per distinct key, not once per candidate. Errors are never cached.
3906    fn primed_site(&mut self, d: DefId, mode: Mode, body: P) -> Result<P, Error> {
3907        if !self.opts.primed_memo
3908            || self.assembles(body)
3909            || self.is_trivial(body)
3910            || self.structural(body)
3911        {
3912            return Ok(body);
3913        }
3914        let info = &self.info[body as usize];
3915        if info.primed == 0 || !info.free.is_empty() || info.effect || info.calls {
3916            return Ok(body);
3917        }
3918        let bits = |m: u64| -> Vec<u16> {
3919            #[allow(clippy::cast_possible_truncation, reason = "at most 64 variables")]
3920            (0..64u16).filter(|&v| m & (1u64 << v) != 0).collect()
3921        };
3922        let (vars, primed) = (bits(info.vars), bits(info.primed));
3923        if vars.len() + primed.len() > MAX_KEY {
3924            return Ok(body);
3925        }
3926        let name = format!("{} ({mode:?}, action)", self.ir.def(d).name);
3927        #[allow(clippy::cast_possible_truncation, reason = "bounded")]
3928        let site = self.code.sites.len() as u32;
3929        self.code.sites.push(MemoSite {
3930            name: name.clone(),
3931            vars: vars.into(),
3932            slots: Box::new([]),
3933            primed: primed.into(),
3934            step: true,
3935            candidate: true,
3936        });
3937        self.site_names.push(name);
3938        self.push(Node::Memo { site, body })
3939    }
3940
3941    /// Whether a primed definition's body is a value its consumers may
3942    /// use without building it, so that a memo site, which builds it,
3943    /// would change what is evaluated: a function constructor (applied
3944    /// through `Node::Beta`, or its `DOMAIN` taken, without being built)
3945    /// or a symbolic set constructor (`SUBSET`, `\X`, `[S -> T]`, a
3946    /// record set, `Seq`), whose value is a description and which a
3947    /// filter over it may rewrite (`Compiler::subset_rewrite`). A filter
3948    /// or set operation stays eligible: membership in it is decided on the
3949    /// body through the site (`Compiler::lazy_set`), and an enumeration
3950    /// streams a filter's body (`Machine::assign_in`); every other
3951    /// consumer builds it.
3952    fn structural(&self, body: P) -> bool {
3953        if self.lambda(body).is_some() {
3954            return true;
3955        }
3956        let mut p = body;
3957        while let Some(Node::Scope { body: b, .. } | Node::Spec(b)) =
3958            self.code.nodes.get(p as usize)
3959        {
3960            p = *b;
3961        }
3962        matches!(
3963            self.code.nodes.get(p as usize),
3964            Some(
3965                Node::Powerset(_)
3966                    | Node::Product(_)
3967                    | Node::FcnSet(..)
3968                    | Node::RecSet(_)
3969                    | Node::Std(StdFn::Seq, _)
3970            )
3971        )
3972    }
3973
3974    fn apply(&mut self, callee: &OpRef, args: &[Arg], env: usize, mode: Mode) -> Result<P, Error> {
3975        match callee {
3976            OpRef::Def(d) => {
3977                let d = self.redirect(*d);
3978                let def = self.ir.def(d);
3979                if let Some(op) = def.std {
3980                    return self.std_apply(op, args, env, mode);
3981                }
3982                if args.is_empty() {
3983                    return self.def_use(d, env, mode);
3984                }
3985                if def.recursive {
3986                    return self.call(d, args, env, mode);
3987                }
3988                self.inline_apply(d, args, env, env, mode)
3989            }
3990            OpRef::Std(op) => {
3991                if let Some(&t) = self.h.std_redirects.get(op) {
3992                    return self.apply(&OpRef::Def(t), args, env, mode);
3993                }
3994                self.std_apply(*op, args, env, mode)
3995            }
3996            OpRef::Param(r) => self.apply_param(*r, args, env, env, mode),
3997            OpRef::Builtin(op) => self.builtin_apply(*op, args, env, mode),
3998            // `CONSTANT F(_)` with `F <- D` in the configuration.
3999            OpRef::Const(c) => match self.h.constants.get(c.index()).cloned().flatten() {
4000                Some(ConstBinding::Def(_)) if args.is_empty() => self.const_expr(*c, env, mode),
4001                Some(ConstBinding::Def(d)) => {
4002                    let body = self.apply(&OpRef::Def(d), args, env, mode)?;
4003                    self.configured_result(body)
4004                }
4005                _ => Err(Error::unsupported(
4006                    "a constant operator the configuration does not bind to a definition (M1 core)",
4007                )),
4008            },
4009            // The operator is resolved outside the substitution; the
4010            // arguments are compiled here, and TLC applies the operator in
4011            // the current (dynamic) context.
4012            OpRef::Subst(decl) => {
4013                let op = self.subst_op(*decl)?;
4014                self.apply(&op, args, env, mode)
4015            }
4016            OpRef::Unbound(n) => Err(Error::unsupported(format!("the unbound operator {n}"))),
4017        }
4018    }
4019
4020    /// Applies a built-in operator passed as an operator argument (for
4021    /// example `ReduceSet(\intersect, S, b)` applying `op(x, y)`) to
4022    /// expression arguments compiled in `env`, as the built-in written
4023    /// in place would be. Only the value operators of
4024    /// [`builtin_value_arg`] are applied; the others stay refused.
4025    fn builtin_apply(
4026        &mut self,
4027        op: BuiltinOp,
4028        args: &[Arg],
4029        env: usize,
4030        mode: Mode,
4031    ) -> Result<P, Error> {
4032        if !builtin_value_arg(op) {
4033            return Err(Error::unsupported(format!(
4034                "the built-in {} as an operator argument (M0 core)",
4035                op.sany_name()
4036            )));
4037        }
4038        let mut exprs = Vec::with_capacity(args.len());
4039        for a in args {
4040            let Arg::Expr { expr, .. } = a else {
4041                return Err(Error::unsupported(format!(
4042                    "the built-in {} applied to an operator argument",
4043                    op.sany_name()
4044                )));
4045            };
4046            exprs.push(*expr);
4047        }
4048        if builtin_arity(op) != Some(exprs.len()) {
4049            return Err(Error::internal(format!(
4050                "the built-in {} applied to {} arguments",
4051                op.sany_name(),
4052                exprs.len()
4053            )));
4054        }
4055        self.builtin(op, &exprs, env, mode)
4056    }
4057
4058    /// Inlines a non-recursive operator applied to `args`, which are
4059    /// compiled in `env`; the operator's lexical parent is found from
4060    /// `def_env` (the caller's, or where an operator argument was passed).
4061    fn inline_apply(
4062        &mut self,
4063        d: DefId,
4064        args: &[Arg],
4065        env: usize,
4066        def_env: usize,
4067        mode: Mode,
4068    ) -> Result<P, Error> {
4069        let body = self.ir.def(d).body;
4070        let (inner, reset) = self.inline(d, args, env, def_env, mode)?;
4071        let b = self.p(body, inner, mode)?;
4072        if reset.is_empty() {
4073            Ok(b)
4074        } else {
4075            self.push(Node::Scope {
4076                reset: reset.into(),
4077                body: b,
4078            })
4079        }
4080    }
4081
4082    /// Inlines a non-recursive operator applied as an action (see
4083    /// [`Self::inline_apply`]).
4084    fn g_inline(&mut self, d: DefId, args: &[Arg], env: usize, def_env: usize) -> Result<G, Error> {
4085        let body = self.ir.def(d).body;
4086        let (inner, reset) = self.inline(d, args, env, def_env, Mode::Plain)?;
4087        let g = self.g(body, inner)?;
4088        if reset.is_empty() {
4089            Ok(g)
4090        } else {
4091            Ok(self.gpush(GNode::Scope {
4092                reset: reset.into(),
4093                body: g,
4094            }))
4095        }
4096    }
4097
4098    /// Applies, as an action, an operator resolved from a constant, a
4099    /// substitution or a parameter; `aenv` is where it was resolved.
4100    fn g_apply_op(
4101        &mut self,
4102        op: &OpRef,
4103        args: &[Arg],
4104        e: ExprId,
4105        env: usize,
4106        aenv: usize,
4107    ) -> Result<G, Error> {
4108        let d = match *op {
4109            OpRef::Def(d) => d,
4110            OpRef::Const(c) => match self.h.constants.get(c.index()).cloned().flatten() {
4111                Some(ConstBinding::Def(d)) => d,
4112                _ => return self.guard_expr(e, env),
4113            },
4114            // TLC's action splitting of a passed built-in (`Op(\/)`,
4115            // `Op(=)` with a primed operand) is not reproduced.
4116            OpRef::Builtin(b) => {
4117                return Err(Error::unsupported(format!(
4118                    "the built-in {} passed as an operator argument and applied as an action (M1 core)",
4119                    b.sany_name()
4120                )));
4121            }
4122            _ => return self.guard_expr(e, env),
4123        };
4124        let d = self.redirect(d);
4125        let def = self.ir.def(d);
4126        if def.std.is_some() || def.recursive || args.is_empty() {
4127            return self.guard_expr(e, env);
4128        }
4129        let def_env = if def.scope == DefScope::TopLevel {
4130            env
4131        } else {
4132            aenv
4133        };
4134        self.g_inline(d, args, env, def_env)
4135    }
4136
4137    /// An operator argument as a function of `arity` fresh frame slots, for
4138    /// the standard modules' higher-order operators (`SelectSeq`, the
4139    /// Folds, ...): the slots, and its body compiled with its parameters
4140    /// bound to them. The caller sets the slots and evaluates the body for
4141    /// each element. The body's free slots include the parameter slots,
4142    /// which the caller's node must treat as bound, as a binder's are.
4143    ///
4144    /// The operator is resolved as an application of it would be:
4145    /// - through operator parameters passed on;
4146    /// - through constant operators bound in the configuration
4147    ///   (`F <- D`);
4148    /// - through `INSTANCE` substitutions.
4149    ///
4150    /// A `LAMBDA` or `LET` operator's body is compiled in the environment
4151    /// where it was written, so it reads the caller's locals.
4152    ///
4153    /// # Errors
4154    /// Unsupported for a std or built-in operator passed as the argument
4155    /// (`FoldSet(+, 0, S)`), a recursive operator, or an expression
4156    /// argument; internal for an arity mismatch.
4157    pub(crate) fn op_fn(
4158        &mut self,
4159        a: &Arg,
4160        env: usize,
4161        arity: usize,
4162    ) -> Result<(Box<[u32]>, P), Error> {
4163        let Arg::Op { op, .. } = a else {
4164            return Err(Error::unsupported(
4165                "an expression where an operator argument is expected (M1 core)",
4166            ));
4167        };
4168        let (op, aenv, enclosing) = match op {
4169            OpRef::Param(r) => self.resolve_param(*r, env)?,
4170            OpRef::Subst(decl) => (self.subst_op(*decl)?, env, false),
4171            op => (op.clone(), env, false),
4172        };
4173        let d = match op {
4174            OpRef::Def(d) => d,
4175            OpRef::Std(s) => match self.h.std_redirects.get(&s) {
4176                Some(&t) => t,
4177                None => return self.std_op_fn(s, arity),
4178            },
4179            OpRef::Const(c) => match self.h.constants.get(c.index()).cloned().flatten() {
4180                Some(ConstBinding::Def(d)) => d,
4181                _ => {
4182                    return Err(Error::unsupported(
4183                        "a constant operator the configuration does not bind to a definition (M1 core)",
4184                    ));
4185                }
4186            },
4187            _ => {
4188                return Err(Error::unsupported(
4189                    "a built-in operator passed to a higher-order operator (M1 core)",
4190                ));
4191            }
4192        };
4193        let mut d = self.redirect(d);
4194        if let Some(s) = self.ir.def(d).std {
4195            match self.h.std_redirects.get(&s) {
4196                Some(&t) if t != d => d = self.redirect(t),
4197                _ => {
4198                    if self.ir.def(d).params.len() != arity {
4199                        return Err(Error::internal(format!(
4200                            "{} passed where an operator of {arity} arguments is expected",
4201                            self.ir.def(d).name
4202                        )));
4203                    }
4204                    return self.std_op_fn(s, arity);
4205                }
4206            }
4207        }
4208        let def = self.ir.def(d);
4209        if def.std.is_some() || def.recursive {
4210            return Err(Error::unsupported(
4211                "a std or recursive operator passed to a higher-order operator (M1 core)",
4212            ));
4213        }
4214        if def.params.len() != arity {
4215            return Err(Error::internal(format!(
4216                "{} passed where an operator of {arity} arguments is expected",
4217                def.name
4218            )));
4219        }
4220        let body = def.body;
4221        let def_env = if def.scope == DefScope::TopLevel {
4222            env
4223        } else {
4224            aenv
4225        };
4226        let parent = self.lexical_parent(d, def_env)?;
4227        let inner = self.new_env(d, parent);
4228        let mut slots = Vec::with_capacity(arity);
4229        for i in 0..arity {
4230            let slot = self.alloc();
4231            if let Some(s) = self.envs[inner].slots.get_mut(i) {
4232                *s = Sb::Flat(slot);
4233            }
4234            slots.push(slot);
4235        }
4236        let b = self.p(body, inner, Mode::Plain)?;
4237        self.enclosing_op_body(b, enclosing)?;
4238        Ok((slots.into(), b))
4239    }
4240
4241    /// A value-only standard operator (`+`, `\\o`, ...) passed as an
4242    /// operator argument, as the `LAMBDA` of its arity that applies it: TLC
4243    /// passes its `MethodValue`, which the override applies to values.
4244    /// TLC wraps an error the operator raises there in the override's
4245    /// `TLC_MODULE_VALUE_JAVA_METHOD_OVERRIDE` report, which the core does
4246    /// not reproduce: the body is a `Node::Spec`, so any such error is
4247    /// reported as `unsupported`.
4248    ///
4249    /// # Errors
4250    /// Unsupported for an operator with operator arguments, an effectful
4251    /// or nullary one, one of another arity, or one the core does not
4252    /// apply to values.
4253    fn std_op_fn(&mut self, op: StdOp, arity: usize) -> Result<(Box<[u32]>, P), Error> {
4254        if crate::stdlib::higher_order(op) || op.impure() || arity == 0 {
4255            return Err(Error::unsupported(format!(
4256                "{} passed to a higher-order operator (M1 core)",
4257                op.qualified_name()
4258            )));
4259        }
4260        if usize::try_from(op.java_arity()).ok() != Some(arity) {
4261            return Err(Error::unsupported(format!(
4262                "{} passed where an operator of {arity} arguments is expected",
4263                op.qualified_name()
4264            )));
4265        }
4266        let mut slots = Vec::with_capacity(arity);
4267        let mut ps = Vec::with_capacity(arity);
4268        for _ in 0..arity {
4269            let slot = self.alloc();
4270            slots.push(slot);
4271            ps.push(self.push(Node::Slot(slot))?);
4272        }
4273        let body = self.std_node(op, ps, None)?;
4274        let body = self.push(Node::Spec(body))?;
4275        Ok((slots.into(), body))
4276    }
4277
4278    /// The operator argument an operator parameter is bound to, following
4279    /// parameters passed on and recursive LET-function views. The original
4280    /// argument environment is retained; the boolean records a function view.
4281    fn resolve_param(&self, r: LocalRef, look_env: usize) -> Result<(OpRef, usize, bool), Error> {
4282        let mut r = r;
4283        let mut look = look_env;
4284        let mut enclosing = false;
4285        loop {
4286            let fe = self.frame_env(look, r.up)?;
4287            if !enclosing && self.lifts.last().is_some_and(|l| fe < l.floor) {
4288                return Err(Error::unsupported(
4289                    "an enclosing operator parameter inside a recursive LET definition (M1 core)",
4290                ));
4291            }
4292            let mut binding = self.envs[fe].slots.get(r.slot.index());
4293            while let Some(Sb::Enclosing { env, slot }) = binding {
4294                // This is compile-time operator metadata, not a captured
4295                // runtime value. The inlined body still resolves every value
4296                // through `local`/`capture` in its original environment.
4297                enclosing = true;
4298                binding = self.envs[*env].slots.get(*slot);
4299            }
4300            let Some(Sb::OpArg { op, env }) = binding.cloned() else {
4301                return Err(Error::unsupported(
4302                    "an operator parameter of a recursive operator (M1 core)",
4303                ));
4304            };
4305            match op {
4306                OpRef::Param(r2) => {
4307                    r = r2;
4308                    look = env;
4309                }
4310                op => return Ok((op, env, enclosing)),
4311            }
4312        }
4313    }
4314
4315    /// A newly admitted enclosing callback cannot hide effects or unknown
4316    /// calls behind a recursive function's call node.
4317    fn enclosing_op_body(&self, body: P, enclosing: bool) -> Result<(), Error> {
4318        if enclosing && (self.info[body as usize].effect || self.info[body as usize].calls) {
4319            return Err(Error::unsupported(
4320                "an enclosing operator argument with effects or recursive calls inside a recursive function (M1 core)",
4321            ));
4322        }
4323        Ok(())
4324    }
4325
4326    /// Applies an operator parameter: the operator argument bound to it.
4327    /// The arguments are compiled in `env`; the parameter is looked up from
4328    /// `look_env`. TLC applies the argument as a closure over the caller's
4329    /// context, which inlining it there reproduces.
4330    fn apply_param(
4331        &mut self,
4332        r: LocalRef,
4333        args: &[Arg],
4334        env: usize,
4335        look_env: usize,
4336        mode: Mode,
4337    ) -> Result<P, Error> {
4338        let (op, aenv, enclosing) = self.resolve_param(r, look_env)?;
4339        let body = match op {
4340            OpRef::Param(_) => Err(Error::internal("an unresolved operator parameter")),
4341            OpRef::Def(d) => {
4342                let d = self.redirect(d);
4343                let def = self.ir.def(d);
4344                if def.std.is_some() || def.scope == DefScope::TopLevel {
4345                    self.apply(&OpRef::Def(d), args, env, mode)
4346                } else if def.recursive {
4347                    Err(Error::unsupported(
4348                        "a recursive LET operator passed as an operator argument (M1 core)",
4349                    ))
4350                } else {
4351                    self.inline_apply(d, args, env, aenv, mode)
4352                }
4353            }
4354            OpRef::Subst(_) => Err(Error::unsupported(
4355                "an INSTANCE-substituted operator passed as an operator argument (M1 core)",
4356            )),
4357            // A built-in has no body of its own: its application is the
4358            // built-in written in place, over arguments compiled in `env`,
4359            // so any recursive call or effect in it is the caller's own and
4360            // nothing is hidden behind an enclosing callback.
4361            OpRef::Builtin(b) => return self.builtin_apply(b, args, env, mode),
4362            op @ (OpRef::Std(_) | OpRef::Const(_) | OpRef::Unbound(_)) => {
4363                self.apply(&op, args, env, mode)
4364            }
4365        }?;
4366        self.enclosing_op_body(body, enclosing)?;
4367        Ok(body)
4368    }
4369
4370    /// Binds an inlined operator's parameters: returns its environment and
4371    /// the thunk slots to reset on entry.
4372    fn inline(
4373        &mut self,
4374        d: DefId,
4375        args: &[Arg],
4376        env: usize,
4377        def_env: usize,
4378        mode: Mode,
4379    ) -> Result<(usize, Vec<u32>), Error> {
4380        let def = self.ir.def(d);
4381        if def.params.len() != args.len() {
4382            return Err(Error::internal(format!(
4383                "{} applied to {} arguments",
4384                def.name,
4385                args.len()
4386            )));
4387        }
4388        let parent = self.lexical_parent(d, def_env)?;
4389        let inner = self.new_env(d, parent);
4390        let mut reset = Vec::new();
4391        self.stats.inlined += 1;
4392        for (i, a) in args.iter().enumerate() {
4393            let expr = match a {
4394                Arg::Expr { expr, .. } => expr,
4395                Arg::Op { op, .. } => {
4396                    if let Some(s) = self.envs[inner].slots.get_mut(i) {
4397                        *s = Sb::OpArg {
4398                            op: op.clone(),
4399                            env,
4400                        };
4401                    }
4402                    continue;
4403                }
4404            };
4405            let cp = self.p(*expr, env, mode)?;
4406            let how = if self.opts.eager && self.is_trivial(cp) {
4407                self.stats.aliased += 1;
4408                ArgHow::Alias(cp)
4409            } else if self.info[cp as usize].primed == 0 {
4410                self.stats.thunks += 1;
4411                let slot = self.alloc();
4412                reset.push(slot);
4413                ArgHow::Thunk(slot, cp)
4414            } else {
4415                ArgHow::ByName
4416            };
4417            if let Some(s) = self.envs[inner].slots.get_mut(i) {
4418                *s = Sb::Arg {
4419                    expr: *expr,
4420                    env,
4421                    how,
4422                };
4423            }
4424        }
4425        Ok((inner, reset))
4426    }
4427
4428    /// A recursive operator call. Under a prime, `op(a)'` is `op` applied to
4429    /// `a'` and evaluated in the next state: the call is of `op`'s
4430    /// next-state variant, whose body is compiled primed. A prime or
4431    /// `ENABLED` inside that body stays refused (a doubly primed expression,
4432    /// a primed `ENABLED`).
4433    fn call(&mut self, d: DefId, args: &[Arg], env: usize, mode: Mode) -> Result<P, Error> {
4434        let fun = self.fun(d, env, mode)?;
4435        let mut ps = Vec::with_capacity(args.len());
4436        for a in args {
4437            let Arg::Expr { expr, .. } = a else {
4438                return Err(Error::unsupported("operator arguments (M0 core)"));
4439            };
4440            // TLC passes a recursive operator's arguments lazily; the core
4441            // evaluates them at the call, speculatively.
4442            let a = self.p(*expr, env, mode)?;
4443            let a = if self.is_trivial(a) {
4444                a
4445            } else {
4446                self.stats.speculative += 1;
4447                self.push(Node::Spec(a))?
4448            };
4449            ps.push(a);
4450        }
4451        self.fun_call(d, fun, ps, env)
4452    }
4453
4454    fn fun(&mut self, d: DefId, call_env: usize, mode: Mode) -> Result<u32, Error> {
4455        let key = (
4456            d,
4457            mode,
4458            self.init_mode,
4459            self.lexical_parent(d, call_env)?,
4460            self.substs.last().map(|s| s.id),
4461        );
4462        if let Some(&f) = self.funs.get(&key) {
4463            return Ok(self.reenter(f));
4464        }
4465        let def = self.ir.def(d);
4466        #[allow(clippy::cast_possible_truncation, reason = "bounded")]
4467        let id = self.code.funs.len() as u32;
4468        #[allow(
4469            clippy::cast_possible_truncation,
4470            reason = "parameter counts are small"
4471        )]
4472        let params = def.params.len() as u32;
4473        self.code.funs.push(Fun {
4474            name: def.name.clone(),
4475            params,
4476            frame: params,
4477            body: 0,
4478            caps: Box::new([]),
4479        });
4480        self.funs.insert(key, id);
4481        self.open_fun(id, mode, def.level);
4482        let saved_slot = self.next_slot;
4483        let saved_resets = std::mem::take(&mut self.reset_stack);
4484        let saved_cache = std::mem::take(&mut self.def_cache);
4485        let saved_at = std::mem::take(&mut self.at_stack);
4486        self.next_slot = params;
4487        let saved_frame = self.new_frame();
4488        let (env, lifted) = match self.begin_fun(d, id, call_env, mode) {
4489            Ok(x) => x,
4490            Err(e) => {
4491                self.frame = saved_frame;
4492                self.next_slot = saved_slot;
4493                self.reset_stack = saved_resets;
4494                self.def_cache = saved_cache;
4495                self.at_stack = saved_at;
4496                return Err(e);
4497            }
4498        };
4499        for i in 0..def.params.len() {
4500            #[allow(
4501                clippy::cast_possible_truncation,
4502                reason = "parameter counts are small"
4503            )]
4504            let s = Sb::Flat(i as u32);
4505            if let Some(x) = self.envs[env].slots.get_mut(i) {
4506                *x = s;
4507            }
4508        }
4509        let body = self.p(def.body, env, mode);
4510        let ended = self.end_fun(id, lifted);
4511        self.frame = saved_frame;
4512        let frame = self.next_slot;
4513        self.next_slot = saved_slot;
4514        self.reset_stack = saved_resets;
4515        self.def_cache = saved_cache;
4516        self.at_stack = saved_at;
4517        self.open_funs.remove(&id);
4518        let body = body?;
4519        ended?;
4520        self.note_next_reads(id, &[body])?;
4521        if mode == Mode::Primed && self.info[body as usize].effect {
4522            return Err(Error::unsupported(
4523                "an effectful recursive operator under a prime (M1 core)",
4524            ));
4525        }
4526        self.complete_fun(id, body, frame);
4527        Ok(id)
4528    }
4529
4530    /// Records the completed body and frame size of `fun`, and its
4531    /// [`Self::fun_summary`].
4532    fn complete_fun(&mut self, fun: u32, body: P, frame: u32) {
4533        if let Some(f) = self.code.funs.get_mut(fun as usize) {
4534            f.body = body;
4535            f.frame = frame;
4536        }
4537        if let Some(vars) = self.fun_summary(fun, body) {
4538            self.fun_reads.insert(fun, vars);
4539        }
4540    }
4541
4542    /// The unprimed variables that evaluating `body`, the completed body of
4543    /// `fun`, can read, when that is provably a function of the call's
4544    /// frame and those variables alone; `None` otherwise.
4545    ///
4546    /// A node without calls contributes its own read set. A recursive call
4547    /// of `fun` itself contributes only its arguments: the reads of `fun`
4548    /// are the least set closed under its body, and a self-call adds
4549    /// nothing beyond that set. A call of another completed function
4550    /// contributes that function's summary. Anything else (an effect, a
4551    /// nested `ENABLED` or composition query, a call of an open or
4552    /// unsummarized function) gives `None`, and calls of `fun` keep reading
4553    /// every variable.
4554    fn fun_summary(&self, fun: u32, body: P) -> Option<u64> {
4555        let mut vars = 0u64;
4556        let mut seen = std::collections::HashSet::new();
4557        let mut stack = vec![body];
4558        while let Some(p) = stack.pop() {
4559            if !seen.insert(p) {
4560                continue;
4561            }
4562            let info = self.info.get(p as usize)?;
4563            if info.effect || info.nested_query {
4564                return None;
4565            }
4566            if !info.calls {
4567                vars |= info.vars;
4568                continue;
4569            }
4570            let node = self.code.nodes.get(p as usize)?;
4571            match node {
4572                Node::Call { fun: g, .. } if *g != fun => {
4573                    if self.open_funs.contains(g) {
4574                        return None;
4575                    }
4576                    vars |= *self.fun_reads.get(g)?;
4577                }
4578                Node::Enabled { .. } | Node::Composition { .. } => return None,
4579                _ => {}
4580            }
4581            push_operands(node, &mut stack);
4582        }
4583        Some(vars)
4584    }
4585
4586    /// A call of `fun` found compiled: notes a call from inside its own
4587    /// compilation.
4588    fn reenter(&mut self, fun: u32) -> u32 {
4589        if self.open_funs.contains(&fun) {
4590            self.reentered_funs.insert(fun);
4591        }
4592        fun
4593    }
4594
4595    /// Starts compiling `fun`, a `mode` variant of a definition at `level`.
4596    fn open_fun(&mut self, fun: u32, mode: Mode, level: Level) {
4597        if mode == Mode::Primed {
4598            self.primed_funs.insert(fun);
4599        }
4600        if mode == Mode::Primed || self.reads_next(level) {
4601            self.next_funs.insert(fun);
4602        }
4603        self.open_funs.insert(fun);
4604    }
4605
4606    /// Whether a plain-mode function of a definition at `level`, in the
4607    /// active substitutions, may read primed variables: an action-level
4608    /// definition, or a state-level one while compiling an initial
4609    /// predicate (which reads the state being built as primed), or any
4610    /// definition under a substitution whose value is at that level.
4611    fn reads_next(&self, level: Level) -> bool {
4612        let at = if self.init_mode {
4613            Level::State
4614        } else {
4615            Level::Action
4616        };
4617        level >= at
4618            || self.substs.iter().any(|s| match &s.value {
4619                Ok(Arg::Expr { expr, .. }) => self.ir.node(*expr).level >= at,
4620                Ok(Arg::Op { level, .. }) => *level >= at,
4621                Err(p) => self.info.get(*p as usize).is_none_or(|i| i.primed != 0),
4622            })
4623    }
4624
4625    /// Records that a call of `fun` reads primed variables when its compiled
4626    /// `parts` do, although [`Self::reads_next`] did not predict it. Calls
4627    /// compiled while `fun` was open assumed it did not, so then the
4628    /// function is refused.
4629    fn note_next_reads(&mut self, fun: u32, parts: &[P]) -> Result<(), Error> {
4630        let reentered = self.reentered_funs.remove(&fun);
4631        if self.next_funs.contains(&fun) || parts.iter().all(|&p| self.info[p as usize].primed == 0)
4632        {
4633            return Ok(());
4634        }
4635        if reentered {
4636            return Err(Error::unsupported(
4637                "a recursive definition below action level whose body reads the next state (M1 core)",
4638            ));
4639        }
4640        self.next_funs.insert(fun);
4641        Ok(())
4642    }
4643
4644    /// A [`crate::stdlib`] operator with operator arguments
4645    /// (`Node::LibHo`): each operator argument is compiled with
4646    /// [`Self::op_fn`] at the arity the library expects.
4647    fn lib_ho(&mut self, op: StdOp, args: &[Arg], env: usize, mode: Mode) -> Result<P, Error> {
4648        if mode == Mode::Primed && op != StdOp::SequencesSelectSeq {
4649            return Err(Error::unsupported(format!(
4650                "{} under a prime (M1 core)",
4651                op.qualified_name()
4652            )));
4653        }
4654        let mut out = Vec::with_capacity(args.len());
4655        for (i, a) in args.iter().enumerate() {
4656            match (crate::stdlib::op_arity(op, i), a) {
4657                (Some(arity), _) => {
4658                    let (params, body) = self.op_fn(a, env, arity)?;
4659                    if mode == Mode::Primed {
4660                        // `op_fn` compiles the callback in Plain mode. That is
4661                        // unchanged by the surrounding prime only when its
4662                        // sole inputs are its element parameters. In
4663                        // particular, neither a state read hidden behind an
4664                        // INSTANCE/configured operator nor a lexical capture
4665                        // may retain the source-state context here.
4666                        let info = &self.info[body as usize];
4667                        if info.vars != 0
4668                            || info.primed != 0
4669                            || info.effect
4670                            || info.calls
4671                            || info.free.iter().any(|s| !params.contains(s))
4672                        {
4673                            return Err(Error::unsupported(
4674                                "Sequences!SelectSeq under a prime with a state-dependent, captured or effectful predicate (M1 core)",
4675                            ));
4676                        }
4677                    }
4678                    if crate::stdlib::takes_op_value(op)
4679                        && matches!(self.code.nodes.get(body as usize), Some(Node::Const(_)))
4680                    {
4681                        return Err(Error::unsupported(format!(
4682                            "{} with an operator whose body is constant: TLC may fail to apply it",
4683                            op.qualified_name()
4684                        )));
4685                    }
4686                    out.push(LibArg::Op { params, body });
4687                }
4688                (None, Arg::Expr { expr, .. }) => {
4689                    out.push(LibArg::Value(self.p(*expr, env, mode)?));
4690                }
4691                (None, Arg::Op { .. }) => {
4692                    return Err(Error::unsupported(format!(
4693                        "{} with an operator where a value is expected",
4694                        op.qualified_name()
4695                    )));
4696                }
4697            }
4698        }
4699        self.push(Node::LibHo(op, out.into()))
4700    }
4701
4702    /// Records whether a value-only library call can replace a repeated-demand
4703    /// TLA+ definition without changing argument effects.
4704    fn lib_node(&self, op: StdOp, args: Vec<P>) -> Node {
4705        let repeatable_args = args.iter().all(|&p| {
4706            let info = &self.info[p as usize];
4707            // Calls and free slots can hide effects in a callee or capture.
4708            !info.effect && !info.calls && info.free.is_empty()
4709        });
4710        Node::Lib {
4711            op,
4712            args: args.into(),
4713            repeatable_args,
4714        }
4715    }
4716
4717    fn std_apply(&mut self, op: StdOp, args: &[Arg], env: usize, mode: Mode) -> Result<P, Error> {
4718        if let Some(&t) = self.h.std_redirects.get(&op) {
4719            return if args.is_empty() {
4720                self.def_use(t, env, mode)
4721            } else {
4722                self.apply(&OpRef::Def(t), args, env, mode)
4723            };
4724        }
4725        if crate::stdlib::higher_order(op) {
4726            return self.lib_ho(op, args, env, mode);
4727        }
4728        // TLC evaluates a primed expression in the successor state, so a
4729        // primed `TLCGet("level")` is the successor's level, which the core
4730        // does not track: `Machine::level` is the source's in a step.
4731        if mode == Mode::Primed
4732            && op == StdOp::TlcTLCGet
4733            && !matches!(args, [Arg::Expr { expr, .. }]
4734                if matches!(&self.ir.node(*expr).expr, Expr::Num(_))
4735                    || matches!(&self.ir.node(*expr).expr, Expr::Str(k) if k.as_ref() != "level"))
4736        {
4737            return Err(Error::unsupported(
4738                "TLCGet(\"level\") under a prime, which TLC evaluates at the successor's level (M1 core)",
4739            ));
4740        }
4741        let mut ps = Vec::with_capacity(args.len());
4742        for a in args {
4743            let Arg::Expr { expr, .. } = a else {
4744                return Err(Error::unsupported(format!(
4745                    "{} with an operator argument",
4746                    op.qualified_name()
4747                )));
4748            };
4749            ps.push(self.p(*expr, env, mode)?);
4750        }
4751        self.std_node(op, ps, Some(args))
4752    }
4753
4754    /// The node of the value-only standard operator `op` applied to the
4755    /// compiled arguments `ps`; `args` are their source arguments, absent
4756    /// when the operator is applied by a higher-order operator to values.
4757    fn std_node(&mut self, op: StdOp, ps: Vec<P>, args: Option<&[Arg]>) -> Result<P, Error> {
4758        use StdOp as S;
4759        let arg = |i: usize| {
4760            ps.get(i)
4761                .copied()
4762                .ok_or_else(|| Error::internal("missing argument"))
4763        };
4764        let arith = |o: Arith| -> Result<Node, Error> { Ok(Node::Arith(o, arg(0)?, arg(1)?)) };
4765        let cmp = |o: Cmp| -> Result<Node, Error> { Ok(Node::Cmp(o, arg(0)?, arg(1)?)) };
4766        let n = match op {
4767            S::NaturalsPlus | S::IntegersPlus => arith(Arith::Add)?,
4768            S::NaturalsMinus | S::IntegersMinus => arith(Arith::Sub)?,
4769            S::NaturalsTimes | S::IntegersTimes => arith(Arith::Mul)?,
4770            S::IntegersDiv => arith(Arith::Div)?,
4771            S::NaturalsDiv => arith(Arith::DivNaturals)?,
4772            S::NaturalsMod | S::IntegersMod => arith(Arith::Mod)?,
4773            S::NaturalsExpt | S::IntegersExpt => arith(Arith::Pow)?,
4774            S::NaturalsLt | S::IntegersLt => cmp(Cmp::Lt)?,
4775            S::NaturalsLeq | S::IntegersLeq => cmp(Cmp::Le)?,
4776            S::NaturalsGt | S::IntegersGt => cmp(Cmp::Gt)?,
4777            S::NaturalsGeq | S::IntegersGeq => cmp(Cmp::Ge)?,
4778            S::NaturalsDotDot | S::IntegersDotDot => Node::Range(arg(0)?, arg(1)?),
4779            S::IntegersNeg => Node::Neg(arg(0)?),
4780            S::NaturalsNat | S::IntegersNat => {
4781                let h = self.m.heap.symbolic(Kind::Nat, 0, &[]);
4782                let h = self.m.heap.intern_const(h)?;
4783                Node::Const(h)
4784            }
4785            S::IntegersInt => {
4786                let h = self.m.heap.symbolic(Kind::Int, 0, &[]);
4787                let h = self.m.heap.intern_const(h)?;
4788                Node::Const(h)
4789            }
4790            S::SequencesLen => Node::Std(StdFn::Len, ps.into()),
4791            S::SequencesHead => Node::Std(StdFn::Head, ps.into()),
4792            S::SequencesTail => Node::Std(StdFn::Tail, ps.into()),
4793            S::SequencesAppend => Node::Std(StdFn::Append, ps.into()),
4794            S::SequencesConcat => Node::Std(StdFn::Concat, ps.into()),
4795            S::SequencesSubSeq => Node::Std(StdFn::SubSeq, ps.into()),
4796            S::SequencesSeq => Node::Std(StdFn::Seq, ps.into()),
4797            S::FiniteSetsCardinality => Node::Std(StdFn::Cardinality, ps.into()),
4798            S::FiniteSetsIsFiniteSet => Node::Std(StdFn::IsFiniteSet, ps.into()),
4799            S::BagsEmptyBag => Node::Std(StdFn::EmptyBag, ps.into()),
4800            S::BagsSetToBag => Node::Std(StdFn::SetToBag, ps.into()),
4801            S::BagsBagToSet => Node::Std(StdFn::BagToSet, ps.into()),
4802            S::BagsBagIn => Node::Std(StdFn::BagIn, ps.into()),
4803            S::BagsCopiesIn => Node::Std(StdFn::CopiesIn, ps.into()),
4804            S::TlcTLCGet => {
4805                // TLC wraps an error raised while evaluating the argument as
4806                // TLCGet's own (`TLCGetEval`), so the argument is a literal;
4807                // `"level"` is the engine's, any other key a register.
4808                let lit = match args {
4809                    Some([Arg::Expr { expr, .. }]) => match &self.ir.node(*expr).expr {
4810                        Expr::Str(k) => Some(k.as_ref() != "level"),
4811                        Expr::Num(_) => Some(true),
4812                        _ => None,
4813                    },
4814                    _ => None,
4815                };
4816                let Some(register) = lit else {
4817                    return Err(Error::unsupported(
4818                        "TLCGet of an expression other than a literal, whose errors TLC reports inside TLCGet (M1 core)",
4819                    ));
4820                };
4821                self.effects.registers |= register;
4822                self.effects.level |= !register;
4823                self.lib_node(op, ps)
4824            }
4825            other if crate::stdlib::implements(other) => self.lib_node(other, ps),
4826            other => {
4827                return Err(Error::unsupported(format!(
4828                    "the standard operator {} (M0 core)",
4829                    other.qualified_name()
4830                )));
4831            }
4832        };
4833        self.push(n)
4834    }
4835
4836    /// `S` in `UNION {S}` when `S` is a set constructor (`[D -> R]`,
4837    /// `[a : R]`, `SUBSET R`, `A \X B`). `UNION {S}` is then `S`: TLC's
4838    /// `UnionValue` tests membership in each member, so `S` stays lazy
4839    /// instead of being enumerated as the element of a set in every state.
4840    /// Other operands keep TLC's check that the member is a set.
4841    fn union_of_one_constructor(&self, args: &[ExprId]) -> Option<ExprId> {
4842        let a = *args.first()?;
4843        let Expr::SetEnum(items) = &self.ir.node(a).expr else {
4844            return None;
4845        };
4846        let [item] = items.as_ref() else {
4847            return None;
4848        };
4849        matches!(
4850            &self.ir.node(*item).expr,
4851            Expr::FcnSet { .. }
4852                | Expr::RecordSet(_)
4853                | Expr::Cartesian(_)
4854                | Expr::Builtin {
4855                    op: BuiltinOp::PowerSet | BuiltinOp::Times,
4856                    ..
4857                }
4858        )
4859        .then_some(*item)
4860    }
4861
4862    #[allow(clippy::too_many_lines, reason = "one arm per built-in operator")]
4863    fn builtin(
4864        &mut self,
4865        op: BuiltinOp,
4866        args: &[ExprId],
4867        env: usize,
4868        mode: Mode,
4869    ) -> Result<P, Error> {
4870        use BuiltinOp as B;
4871        match op {
4872            B::Prime => {
4873                let a = *args
4874                    .first()
4875                    .ok_or_else(|| Error::internal("prime without operand"))?;
4876                if mode == Mode::Primed || self.init_mode {
4877                    return Err(Error::unsupported(
4878                        "a doubly primed expression or a prime in Init",
4879                    ));
4880                }
4881                return self.p(a, env, Mode::Primed);
4882            }
4883            B::Unchanged => {
4884                let a = *args
4885                    .first()
4886                    .ok_or_else(|| Error::internal("UNCHANGED without operand"))?;
4887                return self.unchanged_value(a, env, mode);
4888            }
4889            B::Boolean => {
4890                let mut v = vec![Handle::FALSE, Handle::TRUE];
4891                let h = self.m.heap.set_from(&mut v);
4892                let h = self.m.heap.intern_const(h)?;
4893                return self.konst(h);
4894            }
4895            B::BigUnion => {
4896                if let Some(item) = self.union_of_one_constructor(args) {
4897                    return self.p(item, env, mode);
4898                }
4899            }
4900            B::String => return Err(Error::unsupported("STRING (M0 core)")),
4901            B::Enabled => return self.enabled(args.first().copied(), None, env, mode),
4902            B::Cdot => {
4903                let [a, b] = args else {
4904                    return Err(Error::internal("action composition without two operands"));
4905                };
4906                return self.composition_value(*a, *b, env, mode);
4907            }
4908            B::Always | B::Eventually | B::LeadsTo | B::WhilePlus => {
4909                return Err(Error::unsupported(
4910                    "a temporal operator in a state or action role",
4911                ));
4912            }
4913            _ => {}
4914        }
4915        let ps = self.ps(args, env, mode)?;
4916        let a = |i: usize| {
4917            ps.get(i)
4918                .copied()
4919                .ok_or_else(|| Error::internal("missing operand"))
4920        };
4921        let n = match op {
4922            B::Cup | B::Cap | B::SetMinus => {
4923                let o = match op {
4924                    B::Cup => SetOp::Cup,
4925                    B::Cap => SetOp::Cap,
4926                    _ => SetOp::Minus,
4927                };
4928                return self.push_lazy(Node::SetBin(o, a(0)?, a(1)?));
4929            }
4930            B::In | B::NotIn => {
4931                let (x, set) = (a(0)?, a(1)?);
4932                if self.lazy_set(set) {
4933                    return self.push(Node::InLazy {
4934                        elem: x,
4935                        set,
4936                        neg: op == B::NotIn,
4937                    });
4938                }
4939                if op == B::In {
4940                    Node::In(x, set)
4941                } else {
4942                    Node::NotIn(x, set)
4943                }
4944            }
4945            B::Eq => Node::Eq(a(0)?, a(1)?),
4946            B::Neq => Node::Neq(a(0)?, a(1)?),
4947            B::Subseteq => Node::Subseteq(a(0)?, a(1)?),
4948            B::PowerSet => Node::Powerset(a(0)?),
4949            B::BigUnion => Node::BigUnion(a(0)?),
4950            B::Domain => {
4951                let f = a(0)?;
4952                if let Some(d) = self.lambda_domain(f)? {
4953                    return Ok(d);
4954                }
4955                Node::Domain(f)
4956            }
4957            B::Times => Node::Product(ps.clone().into()),
4958            B::Not => Node::Not(a(0)?),
4959            B::And => Node::And(ps.clone().into()),
4960            B::Or => Node::Or(ps.clone().into()),
4961            B::Implies => Node::Implies(a(0)?, a(1)?),
4962            B::Equiv => Node::Equiv(a(0)?, a(1)?),
4963            _ => {
4964                return Err(Error::unsupported(format!(
4965                    "the built-in {} (M0 core)",
4966                    op.sany_name()
4967                )));
4968            }
4969        };
4970        self.push(n)
4971    }
4972
4973    // ------------------------------------------------------------------
4974    // Generator compilation
4975    // ------------------------------------------------------------------
4976
4977    fn guard(&mut self, p: P) -> Result<G, Error> {
4978        let name = format!("{} guard", self.role_name);
4979        let p = self.site(name, p)?.unwrap_or(p);
4980        Ok(self.gpush(GNode::Guard(p)))
4981    }
4982
4983    fn guard_expr(&mut self, e: ExprId, env: usize) -> Result<G, Error> {
4984        let p = self.p(e, env, Mode::Plain)?;
4985        self.guard(p)
4986    }
4987
4988    fn g(&mut self, e: ExprId, env: usize) -> Result<G, Error> {
4989        if self.code.source_map.is_none() {
4990            return self.g_inner(e, env);
4991        }
4992        let previous = self.debug_current;
4993        self.debug_current = self.debug_context(e, env)?;
4994        let result = self.g_inner(e, env);
4995        self.debug_current = previous;
4996        result
4997    }
4998
4999    #[allow(
5000        clippy::too_many_lines,
5001        clippy::many_single_char_names,
5002        reason = "one arm per generator rule"
5003    )]
5004    fn g_inner(&mut self, e: ExprId, env: usize) -> Result<G, Error> {
5005        // Each generator expression is evaluated by its own TLC call
5006        // (`Compiler::effect_thunk_use`).
5007        self.leaf += 1;
5008        let expr = &self.ir.node(e).expr;
5009        match expr {
5010            Expr::Cdot(a, b) => {
5011                let (first, then, _) = self.composition_parts(*a, *b, env)?;
5012                Ok(self.composition_gen(first, then))
5013            }
5014            Expr::Builtin {
5015                op: BuiltinOp::Cdot,
5016                args,
5017            } if args.len() == 2 => {
5018                let (first, then, _) = self.composition_parts(args[0], args[1], env)?;
5019                Ok(self.composition_gen(first, then))
5020            }
5021            Expr::Junction { kind, items, .. } => match kind {
5022                JunctionKind::And => {
5023                    let mut out = Vec::with_capacity(items.len());
5024                    for &i in items {
5025                        let g = self.g(i, env)?;
5026                        let p = self.p(i, env, Mode::Plain)?;
5027                        out.push((g, p));
5028                    }
5029                    Ok(self.gpush(GNode::Conj(out.into())))
5030                }
5031                JunctionKind::Or => {
5032                    let mut out = Vec::with_capacity(items.len());
5033                    for &i in items {
5034                        out.push(self.g(i, env)?);
5035                    }
5036                    Ok(self.gpush(GNode::Disj(out.into())))
5037                }
5038            },
5039            Expr::Quant {
5040                kind: kind @ (QuantKind::Exists | QuantKind::Forall),
5041                bounds,
5042                body,
5043            } if bounds.iter().all(|b| b.domain.is_some()) => {
5044                let exists = *kind == QuantKind::Exists;
5045                let body = *body;
5046                let (binds, saved) = self.binds(bounds, env, Mode::Plain)?;
5047                let r = (|| {
5048                    let bg = self.g(body, env)?;
5049                    let bp = self.p(body, env, Mode::Plain)?;
5050                    Ok((bg, bp))
5051                })();
5052                self.unbind(saved);
5053                let (bg, bp) = r?;
5054                let binds: Box<[Bind]> = binds.into();
5055                Ok(self.gpush(if exists {
5056                    GNode::Exists {
5057                        binds,
5058                        body: bg,
5059                        body_p: bp,
5060                    }
5061                } else {
5062                    GNode::Forall {
5063                        binds,
5064                        body: bg,
5065                        body_p: bp,
5066                    }
5067                }))
5068            }
5069            Expr::If { cond, then, other } => {
5070                let c = self.p(*cond, env, Mode::Plain)?;
5071                let t = self.g(*then, env)?;
5072                let o = self.g(*other, env)?;
5073                Ok(self.gpush(GNode::If {
5074                    cond: c,
5075                    then: t,
5076                    other: o,
5077                }))
5078            }
5079            Expr::Case { arms, other } => {
5080                let mut out = Vec::with_capacity(arms.len());
5081                for a in arms {
5082                    let p = self.p(a.guard, env, Mode::Plain)?;
5083                    let g = self.g(a.value, env)?;
5084                    out.push((p, g));
5085                }
5086                let o = match other {
5087                    Some(o) => Some(self.g(*o, env)?),
5088                    None => None,
5089                };
5090                Ok(self.gpush(GNode::Case {
5091                    arms: out.into(),
5092                    other: o,
5093                }))
5094            }
5095            Expr::Implies(a, b) => {
5096                let l = self.p(*a, env, Mode::Plain)?;
5097                let r = self.g(*b, env)?;
5098                Ok(self.gpush(GNode::Implies { lhs: l, rhs: r }))
5099            }
5100            Expr::Builtin {
5101                op: BuiltinOp::Eq,
5102                args,
5103            } if args.len() == 2 => {
5104                if let Some(var) = self.target(args[0], env, false)? {
5105                    let rhs = self.p(args[1], env, Mode::Plain)?;
5106                    return Ok(self.gpush(GNode::Assign { var, rhs }));
5107                }
5108                self.guard_expr(e, env)
5109            }
5110            Expr::Builtin {
5111                op: BuiltinOp::In,
5112                args,
5113            } if args.len() == 2 => {
5114                if let Some(var) = self.target(args[0], env, false)? {
5115                    // TLC enumerates a lazy set in full, as the core does:
5116                    // no speculation.
5117                    let set = self.p(args[1], env, Mode::Plain)?;
5118                    let set = self.unspec(set);
5119                    // TLC enumerates a lazy union without normalizing it,
5120                    // so its elements can repeat (ยง6).
5121                    if let Some(raw) = self.raw_plan(args[1], env)? {
5122                        return Ok(self.gpush(GNode::AssignInRaw { var, set, raw }));
5123                    }
5124                    return Ok(self.gpush(GNode::AssignIn { var, set }));
5125                }
5126                self.guard_expr(e, env)
5127            }
5128            Expr::Builtin {
5129                op: BuiltinOp::Subseteq,
5130                args,
5131            } if args.len() == 2 => {
5132                // `x' \subseteq S` enumerates `SUBSET S`, normalized
5133                // (`Tool.java:1379-1421`).
5134                if let Some(var) = self.target(args[0], env, false)? {
5135                    let base = self.p(args[1], env, Mode::Plain)?;
5136                    let set = self.push(Node::Powerset(base))?;
5137                    return Ok(self.gpush(GNode::AssignIn { var, set }));
5138                }
5139                self.guard_expr(e, env)
5140            }
5141            Expr::Builtin {
5142                op: BuiltinOp::Unchanged,
5143                args,
5144            } if args.len() == 1 => {
5145                if self.init_mode {
5146                    return self.guard_expr(e, env);
5147                }
5148                let mut items = Vec::new();
5149                self.unchanged_items(args[0], env, &mut items)?;
5150                Ok(self.gpush(GNode::Unchanged(items.into())))
5151            }
5152            Expr::Unchanged(a) => {
5153                if self.init_mode {
5154                    return self.guard_expr(e, env);
5155                }
5156                let mut items = Vec::new();
5157                self.unchanged_items(*a, env, &mut items)?;
5158                Ok(self.gpush(GNode::Unchanged(items.into())))
5159            }
5160            Expr::StepBox { action, sub } => {
5161                if self.init_mode {
5162                    return self.guard_expr(e, env);
5163                }
5164                let a = self.g(*action, env)?;
5165                let mut items = Vec::new();
5166                self.unchanged_items(*sub, env, &mut items)?;
5167                Ok(self.gpush(GNode::StepBox {
5168                    action: a,
5169                    vars: items.into(),
5170                }))
5171            }
5172            Expr::StepAngle { action, sub } => {
5173                if self.init_mode {
5174                    return self.guard_expr(e, env);
5175                }
5176                let (action, sub) = (*action, *sub);
5177                let a = self.g(action, env)?;
5178                let same = self.changed_test(sub, env)?;
5179                Ok(self.gpush(GNode::StepAngle { action: a, same }))
5180            }
5181            Expr::FcnApply { fcn, arg } => {
5182                let (fcn, arg) = (*fcn, *arg);
5183                let Some((lambda, lenv)) = self.fcn_lambda(fcn, env, 0)? else {
5184                    // Applied recursive predicates are Boolean guards: Core
5185                    // counts the successors they emit rather than TLC's
5186                    // duplicate witnesses.
5187                    // Their whole-plan effect safety is checked after all
5188                    // function bodies and roles have been compiled.
5189                    if self.rec_target(fcn, env, Mode::Plain)?.is_some() {
5190                        self.recursive_action_predicate = true;
5191                    }
5192                    return self.guard_expr(e, env);
5193                };
5194                let Expr::FcnCons { bounds, body } = self.ir.node(lambda).expr.clone() else {
5195                    return self.guard_expr(e, env);
5196                };
5197                if bounds.iter().any(|b| b.domain.is_none()) {
5198                    return self.guard_expr(e, env);
5199                }
5200                let (binds, saved) = self.binds(&bounds, lenv, Mode::Plain)?;
5201                let r = (|| {
5202                    let a = self.p(arg, env, Mode::Plain)?;
5203                    let b = self.g(body, lenv)?;
5204                    Ok((a, b))
5205                })();
5206                self.unbind(saved);
5207                let (a, b) = r?;
5208                Ok(self.gpush(GNode::FcnAction {
5209                    binds: binds.into(),
5210                    arg: a,
5211                    body: b,
5212                }))
5213            }
5214            Expr::Let { defs, body } => {
5215                let body = *body;
5216                let defs = defs.clone();
5217                let (g, reset) = self.let_scope(&defs, env, |c| c.g(body, env))?;
5218                if reset.is_empty() {
5219                    Ok(g)
5220                } else {
5221                    Ok(self.gpush(GNode::Scope {
5222                        reset: reset.into(),
5223                        body: g,
5224                    }))
5225                }
5226            }
5227            Expr::Selected(a) | Expr::Label { body: a, .. } => self.g(*a, env),
5228            Expr::Subst { bindings, body } => {
5229                let (bindings, body) = (bindings.clone(), *body);
5230                let (g, reset) =
5231                    self.subst_scope(&bindings, env, Mode::Plain, |c| c.g(body, env))?;
5232                if reset.is_empty() {
5233                    Ok(g)
5234                } else {
5235                    Ok(self.gpush(GNode::Scope {
5236                        reset: reset.into(),
5237                        body: g,
5238                    }))
5239                }
5240            }
5241            // A substituted name used as an action is enumerated by name
5242            // (TLC binds substitutions uncached in the generator: B5).
5243            Expr::SubstRef {
5244                decl,
5245                primed: false,
5246            } if !self.subst_is_value(*decl) => match self.subst_expr(*decl) {
5247                Some(r) => {
5248                    let (expr, aenv, depth) = r?;
5249                    self.stats.by_name += 1;
5250                    self.outside(depth, |c| c.g(expr, aenv))
5251                }
5252                None => self.guard_expr(e, env),
5253            },
5254            Expr::Def(d) => {
5255                let d = self.redirect(*d);
5256                let def = self.ir.def(d);
5257                if self.has_startup_value(d)
5258                    || def.std.is_some()
5259                    || def.recursive
5260                    || !def.params.is_empty()
5261                    || matches!(def.scope, DefScope::LetValue { .. })
5262                {
5263                    return self.guard_expr(e, env);
5264                }
5265                let parent = self.lexical_parent(d, env)?;
5266                let inner = self.new_env(d, parent);
5267                self.g(def.body, inner)
5268            }
5269            Expr::Apply {
5270                callee: OpRef::Def(d),
5271                args,
5272            } => {
5273                let d = self.redirect(*d);
5274                let def = self.ir.def(d);
5275                if def.std.is_some() || def.recursive || args.is_empty() {
5276                    if args.is_empty()
5277                        && def.std.is_none()
5278                        && !def.recursive
5279                        && !self.has_startup_value(d)
5280                    {
5281                        let parent = self.lexical_parent(d, env)?;
5282                        let inner = self.new_env(d, parent);
5283                        return self.g(def.body, inner);
5284                    }
5285                    return self.guard_expr(e, env);
5286                }
5287                self.g_inline(d, args, env, env)
5288            }
5289            // An operator that stands for a definition, applied as an
5290            // action: a constant operator bound to a definition (`F <- D`),
5291            // an operator declaration an instance substitutes, or an
5292            // operator parameter (the argument, inlined where it was
5293            // passed).
5294            Expr::Apply {
5295                callee: OpRef::Const(c),
5296                args,
5297            } => self.g_apply_op(&OpRef::Const(*c), args, e, env, env),
5298            Expr::Apply {
5299                callee: OpRef::Subst(decl),
5300                args,
5301            } => {
5302                let op = self.subst_op(*decl)?;
5303                self.g_apply_op(&op, args, e, env, env)
5304            }
5305            Expr::Apply {
5306                callee: OpRef::Param(r),
5307                args,
5308            } => {
5309                let (op, aenv, enclosing) = self.resolve_param(*r, env)?;
5310                if enclosing {
5311                    return Err(Error::unsupported(
5312                        "an enclosing operator parameter used as an action inside a recursive function (M1 core)",
5313                    ));
5314                }
5315                self.g_apply_op(&op, args, e, env, aenv)
5316            }
5317            Expr::Local(r) => {
5318                let fe = self.frame_env(env, r.up)?;
5319                match self.envs[fe].slots.get(r.slot.index()).cloned() {
5320                    Some(Sb::Arg {
5321                        expr, env: aenv, ..
5322                    }) => {
5323                        self.stats.by_name += 1;
5324                        self.g(expr, aenv)
5325                    }
5326                    Some(Sb::LetVal { def, env: lenv, .. }) => {
5327                        let body = self.ir.def(def).body;
5328                        self.g(body, lenv)
5329                    }
5330                    _ => self.guard_expr(e, env),
5331                }
5332            }
5333            _ => self.guard_expr(e, env),
5334        }
5335    }
5336
5337    /// The variable an assignment's left side names (TLC's `getPrimedVar`,
5338    /// or `getVar` in an initial predicate).
5339    fn target(&mut self, e: ExprId, env: usize, under_prime: bool) -> Result<Option<u16>, Error> {
5340        #[allow(clippy::cast_possible_truncation, reason = "at most 64 variables")]
5341        match &self.ir.node(e).expr {
5342            Expr::Var { var, primed } => {
5343                let ok = if self.init_mode {
5344                    !*primed && !under_prime
5345                } else {
5346                    *primed != under_prime
5347                };
5348                Ok(ok.then_some(var.index() as u16))
5349            }
5350            Expr::Prime(a) if !self.init_mode && !under_prime => self.target(*a, env, true),
5351            Expr::Builtin {
5352                op: BuiltinOp::Prime,
5353                args,
5354            } if !self.init_mode && !under_prime && args.len() == 1 => {
5355                self.target(args[0], env, true)
5356            }
5357            Expr::Label { body: a, .. } | Expr::Selected(a) => self.target(*a, env, under_prime),
5358            // `x'` with `x` substituted is the substitution's variable
5359            // (`getPrimedVar`); unsubstituted, the root variable.
5360            Expr::SubstRef { decl, primed } => {
5361                let (decl, primed) = (*decl, *primed);
5362                if primed && under_prime {
5363                    return Ok(None);
5364                }
5365                let under = under_prime || primed;
5366                if self.subst_is_value(decl) {
5367                    return Ok(None);
5368                }
5369                if let Some(r) = self.subst_expr(decl) {
5370                    let (expr, aenv, depth) = r?;
5371                    return self.outside(depth, |c| c.target(expr, aenv, under));
5372                }
5373                let Some(v) = self.ir.decl(decl).var else {
5374                    return Ok(None);
5375                };
5376                let ok = if self.init_mode { !under } else { under };
5377                Ok(ok.then_some(v.index() as u16))
5378            }
5379            Expr::Local(r) => {
5380                let fe = self.frame_env(env, r.up)?;
5381                match self.envs[fe].slots.get(r.slot.index()).cloned() {
5382                    Some(Sb::Arg {
5383                        expr, env: aenv, ..
5384                    }) => self.target(expr, aenv, under_prime),
5385                    Some(Sb::LetVal { def, env: lenv, .. }) => {
5386                        let body = self.ir.def(def).body;
5387                        self.target(body, lenv, under_prime)
5388                    }
5389                    _ => Ok(None),
5390                }
5391            }
5392            Expr::Def(d) => {
5393                let d = self.redirect(*d);
5394                let def = self.ir.def(d);
5395                if self.has_startup_value(d)
5396                    || def.std.is_some()
5397                    || !def.params.is_empty()
5398                    || def.recursive
5399                {
5400                    return Ok(None);
5401                }
5402                let parent = self.lexical_parent(d, env)?;
5403                let inner = self.new_env(d, parent);
5404                self.target(def.body, inner, under_prime)
5405            }
5406            _ => Ok(None),
5407        }
5408    }
5409}