Skip to main content

dive_eval/
next.rs

1//! The successor generator: ports of TLC's `Tool.getInitStates`,
2//! `Tool.getNextStates`, `processUnchanged`, `enabled` and `getActions`
3//! (`tlc2/tool/impl/Tool.java`, ported from tlaplus at `94d0c50`), rule by
4//! rule.
5//!
6//! **What it reproduces.** For each state and action, the exact sequence of
7//! successors TLC's enumerator hands to its functor, duplicates included,
8//! since "states generated" counts every one (probe `DuplicateSuccessors`).
9//! The enumeration works in continuation-passing style over an explicit
10//! continuation list, TLC's `ActionItemList`, with one successor buffer that
11//! is bound and unbound as TLC binds and unbinds its `TLCStateMut`:
12//!
13//! | Construct | Rule (Java) |
14//! |---|---|
15//! | `A /\ B /\ C` | `A` with the continuation `B, C` consed in order (`:1176-1183`) |
16//! | `A \/ B` | each disjunct with the same continuation, left to right (`:1184-1207`) |
17//! | `\E x \in S, y \in T : A` | one enumeration of `A` per binding, normalized, **first** variable fastest (`ContextEnumerator`, `:1208-1229`; probes `ExistsOrder`, `ExistsSetOrder`) |
18//! | `\A x \in S : A` | the first binding's `A`, with the other bindings consed onto the continuation, last first (`:1230-1246`) |
19//! | `x' = e` | binds `x'` if unassigned, otherwise checks equality (`:1353-1378`) |
20//! | `x' \in S` | binds each element of `S` in TLC's `elements()` order if unassigned, otherwise checks membership (`:1422-1468`; probes `InSetOrder`, `FilterSetOrder`, `MapSetOrder`); for lazily represented sets TLC's unnormalized `elements()` order, refused where it depends on history (`tlc_enum.rs`) |
21//! | `x' \subseteq S` | the same over `SUBSET S` (`:1379-1421`) |
22//! | `UNCHANGED e` | a variable, a tuple (items consed), a zero-arity definition or argument (followed), anything else compared (`processUnchanged`, `:1551-1661`) |
23//! | `[A]_e` | `A`, then the `UNCHANGED e` successor (`:1284-1295`; probe `StutterInNext`) |
24//! | `<A>_e` | `A` with a `CHANGED e` check consed (`:1279-1283`) |
25//! | `IF`, `CASE`, `=>` | guard evaluated, then the chosen branch (`:1296-1352`, `:1469-1482`) |
26//! | `LET`, labels, `INSTANCE` substitutions, `Op!1` | transparent; substitutions are bound as uncached lazy values (`:960-990`) |
27//! | user operator | its body, its arguments bound lazily; an argument naming an action is followed (`LazyValue`, `:1112-1158`) |
28//! | `f[a]` | the body of a lazy function, or the function's boolean value (`:1247-1278`) |
29//! | anything else | evaluated as a boolean (`:1536-1546`) |
30//!
31//! Once every variable of the successor is assigned, the rest of the
32//! continuation is evaluated as booleans instead (`getNextStatesAllAssigned`,
33//! `:1036-1082`), unless warnings are off ([`crate::Options::warnings`]).
34//! Initial states follow `getInitStates` (`:427-890`), which has the same
35//! rules over unprimed variables, its own error texts and an unconditional
36//! all-assigned path.
37//!
38//! **What it does not do.** It never deduplicates, filters or reorders: the
39//! checker counts, constrains and stores. A successor that leaves a
40//! variable unassigned is still emitted ([`Successor::complete`]); TLC reports
41//! it in its functor (`TLC_STATE_NOT_COMPLETELY_SPECIFIED_NEXT`).
42//!
43//! # Driving it
44//!
45//! A checker gets the initial predicates and the split actions from
46//! the binding stage ([`Evaluator::init_predicate`], [`Evaluator::actions`],
47//! or [`Evaluator::scope`] and its relatives for formulas found inside
48//! definitions and instances), generates the initial states, then expands
49//! each state with [`Evaluator::successors`]. Every state handed to the sink
50//! counts as generated. Run it on a thread with
51//! [`crate::RECOMMENDED_STACK`].
52//!
53//! ```
54//! use std::sync::Arc;
55//! use dive_eval::next::{Flow, StateVals};
56//! use dive_eval::{Evaluator, Model, Options};
57//! use dive_ir::actions::{ActionName, split};
58//! use dive_sema::{Options as SemaOptions, analyze_source};
59//!
60//! let src = "---- MODULE M ----\nEXTENDS Naturals\nVARIABLE x\n\
61//!            Init == x \\in {0, 1}\nNext == x' = x + 1 \\/ x' = x + 1\n====\n";
62//! let ir = dive_ir::lower(&analyze_source("M.tla", src, &SemaOptions::default())).expect("lowers");
63//! let ir = Arc::new(ir);
64//! let (init, next) = (ir.root_def("Init").expect("Init"), ir.root_def("Next").expect("Next"));
65//! let ev = Evaluator::new(Model::new(ir.clone()), Options::tlc()).expect("valid context");
66//! let inits = vec![ev.init_predicate(init, 0).expect("no arguments")];
67//! let tree = split(&ir, ir.def(next).body, ActionName::Def(next), next, &Default::default());
68//! let actions = ev.actions(&tree, next, inits.len()).expect("splits");
69//! assert_eq!(actions.len(), 2);
70//!
71//! let mut states: Vec<StateVals> = Vec::new();
72//! ev.init_states(&inits, &mut |s| {
73//!     states.push(s.state.into());
74//!     Flow::Continue
75//! })
76//! .expect("initial states");
77//! assert_eq!(states.len(), 2);
78//!
79//! // Both disjuncts generate x = 1 from x = 0: two successors, one state.
80//! let mut generated = 0;
81//! ev.successors(&actions, &states[0], &mut |s| {
82//!     assert_eq!(s.ordinal, generated);
83//!     generated += 1;
84//!     Flow::Continue
85//! })
86//! .expect("successors");
87//! assert_eq!(generated, 2);
88//! ```
89
90#![allow(
91    clippy::too_many_arguments,
92    clippy::too_many_lines,
93    clippy::many_single_char_names,
94    reason = "each rule ports one TLC method and is kept together for comparison, with the short names of the TLC code"
95)]
96
97use std::sync::Arc;
98
99use dive_ir::actions::{ActionName, ActionTree, Split, label};
100use dive_ir::{Arg, BuiltinOp, DefId, DefScope, Expr, ExprId, JunctionKind, OpRef, QuantKind};
101use dive_value::Value;
102
103use crate::core::{Core, is_enumerable};
104use crate::env::{Env, Ev, OpVal, St, StateRef, Sv, Thunk, control};
105use crate::error::{Ec, ErrorClass, EvalError, Result};
106pub use crate::scope::Scope;
107use crate::{ConstBinding, Evaluator};
108
109mod cdot;
110
111/// A state's variable values by [`dive_ir::VarId`], `None` where unassigned.
112pub type StateVals = Arc<[Option<Value>]>;
113
114/// Whether to go on enumerating after a successor or initial state.
115#[derive(Clone, Copy, Debug, PartialEq, Eq)]
116pub enum Flow {
117    /// Go on.
118    Continue,
119    /// Stop now: no further successor is generated or evaluated (TLC's
120    /// functor throwing, for example at an invariant violation).
121    Stop,
122}
123
124/// One initial predicate or next-state action with its context (TLC's
125/// `Action`): an expression, the bindings it is evaluated under, its name
126/// and its label.
127#[derive(Clone, Debug)]
128pub struct Action {
129    pub(crate) expr: ExprId,
130    pub(crate) env: Env,
131    owner: Arc<dive_ir::Ir>,
132    names: Arc<dive_value::Interner>,
133    context: std::sync::Weak<crate::core::Core>,
134    name: ActionName,
135    params: Vec<(String, Value)>,
136    label: String,
137    id: usize,
138}
139
140impl Action {
141    /// The predicate.
142    #[must_use]
143    pub fn expr(&self) -> ExprId {
144        self.expr
145    }
146
147    /// The captured evaluation context, for conservative backend preflight.
148    /// Reading the context does not evaluate or force any captured value.
149    #[must_use]
150    pub fn scope(&self) -> Scope {
151        Scope {
152            env: self.env.clone(),
153            owner: self.owner.clone(),
154            names: self.names.clone(),
155            context: self.context.clone(),
156            wrapper: None,
157        }
158    }
159
160    /// What the action is named after.
161    #[must_use]
162    pub fn name(&self) -> ActionName {
163        self.name
164    }
165
166    /// The values of the named definition's parameters bound by splitting,
167    /// in parameter order (TLC's `Action.getParameters`).
168    #[must_use]
169    pub fn params(&self) -> &[(String, Value)] {
170        &self.params
171    }
172
173    /// TLC's label, `<Name(v1,v2) line L, col C to line L2, col C2 of
174    /// module M>` (`Action.getLocation`), as printed in counterexamples.
175    #[must_use]
176    pub fn label(&self) -> &str {
177        &self.label
178    }
179
180    /// The action's id: initial predicates first, then the next-state
181    /// actions, as TLC numbers them (`Tool.java:225-241`).
182    #[must_use]
183    pub fn id(&self) -> usize {
184        self.id
185    }
186}
187
188/// A successor or initial state handed to the sink.
189#[derive(Debug)]
190pub struct Successor<'a> {
191    /// The state, by [`dive_ir::VarId`]; `None` where the action left a
192    /// variable unassigned.
193    pub state: &'a [Option<Value>],
194    /// The action (or initial predicate) that produced it.
195    pub action: &'a Action,
196    /// Its position among the states generated from the same expanded state
197    /// (or among the initial states), from 0.
198    pub ordinal: u64,
199}
200
201impl Successor<'_> {
202    /// Whether every variable is assigned (`TLCState.allAssigned`). TLC's
203    /// functor reports an incomplete state as
204    /// `TLC_STATE_NOT_COMPLETELY_SPECIFIED_NEXT` (or `_INITIAL`).
205    #[must_use]
206    pub fn complete(&self) -> bool {
207        self.state.iter().all(Option::is_some)
208    }
209
210    /// The variables left unassigned, by [`dive_ir::VarId`] index.
211    #[must_use]
212    pub fn unassigned(&self) -> Vec<usize> {
213        self.state
214            .iter()
215            .enumerate()
216            .filter_map(|(i, v)| v.is_none().then_some(i))
217            .collect()
218    }
219}
220
221/// How an enumeration ended without an error.
222#[derive(Clone, Copy, Debug, PartialEq, Eq)]
223pub struct Outcome {
224    /// States handed to the sink.
225    pub emitted: u64,
226    /// Intermediate states of action compositions that count as generated
227    /// without being handed to the sink (TLC's
228    /// `nss.incrementStatesGenerated`; [`crate::ActionComposition::Tlc`]
229    /// only, 0 otherwise). A checker adds them to its generated count, and
230    /// they keep the expanded state from being a deadlock, as in TLC.
231    pub intermediate: u64,
232    /// Whether the sink stopped the enumeration.
233    pub stopped: bool,
234}
235
236/// An error that ended an enumeration, with the number of states already
237/// handed to the sink (they count as generated, probe `EvalErrorMidLevel`).
238#[derive(Clone, Debug)]
239pub struct NextError {
240    /// The error.
241    pub error: EvalError,
242    /// States handed to the sink before it.
243    pub emitted: u64,
244    /// Intermediate states counted as generated before it (see
245    /// [`Outcome::intermediate`]).
246    pub intermediate: u64,
247    /// The action being enumerated (`None` for initial states).
248    pub action: Option<usize>,
249}
250
251impl std::fmt::Display for NextError {
252    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
253        write!(f, "{} (after {} states)", self.error, self.emitted)
254    }
255}
256
257impl std::error::Error for NextError {}
258
259// -----------------------------------------------------------------------------
260// The public entry points
261// -----------------------------------------------------------------------------
262
263impl Evaluator {
264    /// An initial predicate named by `INIT` (or a level-1 conjunct of a
265    /// `SPECIFICATION` that is a use of `def`): `def`'s body in its own frame
266    /// (`SpecProcessor.processConfigInitAndNext`).
267    ///
268    /// # Errors
269    /// A bug if `def` has parameters.
270    pub fn init_predicate(&self, def: DefId, id: usize) -> Result<Action> {
271        let d = self.admit_def(def)?;
272        if !d.params.is_empty() {
273            return Err(EvalError::bug(format!("{} takes arguments", d.name)));
274        }
275        self.predicate(def, d.body, ActionName::Def(def), id)
276    }
277
278    /// An initial predicate or action that is the expression `expr` of the
279    /// top-level definition `frame`, evaluated in a fresh frame of it (for
280    /// example the `Init` conjunct of a `SPECIFICATION`, named `Unnamed`).
281    ///
282    /// # Errors
283    /// An unknown ID, a foreign context or an incompatible lexical frame.
284    pub fn predicate(
285        &self,
286        frame: DefId,
287        expr: ExprId,
288        name: ActionName,
289        id: usize,
290    ) -> Result<Action> {
291        self.predicate_in(&self.scope(frame)?, expr, name, id)
292    }
293
294    /// An initial predicate or action `expr` evaluated in `scope`.
295    ///
296    /// # Errors
297    /// An unknown ID, a foreign context or an incompatible lexical frame.
298    pub fn predicate_in(
299        &self,
300        scope: &Scope,
301        expr: ExprId,
302        name: ActionName,
303        id: usize,
304    ) -> Result<Action> {
305        self.validate_scope(scope)?;
306        self.admit_scoped_expr(scope, expr)?;
307        if let ActionName::Def(d) = name {
308            self.admit_def(d)?;
309        }
310        Ok(Action {
311            owner: self.core.ir.clone(),
312            names: self.core.names.clone(),
313            context: Arc::downgrade(&self.core),
314            expr,
315            env: scope.env.clone(),
316            name,
317            params: Vec::new(),
318            label: label(&self.core.ir, name, &[], scope.wrapper.unwrap_or(expr)),
319            id,
320        })
321    }
322
323    /// Splits a next-state relation into TLC's action list (`Tool.getActions`,
324    /// `Tool.java:250-419`), expanding the tree `dive_ir::actions::split`
325    /// built: each split `\E` is enumerated in the empty state and each
326    /// inlined operator's constant arguments are evaluated. `frame` is the
327    /// top-level definition the relation is evaluated in; the actions are
328    /// numbered from `first_id`.
329    ///
330    /// # Errors
331    /// A refusal or bug while expanding, or TLC's failure to split (an
332    /// operator TLC cannot cast at the top of the relation), which is refused.
333    pub fn actions(&self, split: &Split, frame: DefId, first_id: usize) -> Result<Vec<Action>> {
334        self.actions_in(&self.scope(frame)?, split, first_id)
335    }
336
337    /// [`Evaluator::actions`] for a relation found in `scope` (inside a
338    /// parameterized definition's body, for example). A relation under a
339    /// substitution is not split by TLC: build its one action with
340    /// [`Evaluator::predicate_in`] instead.
341    ///
342    /// # Errors
343    /// As [`Evaluator::actions`].
344    pub fn actions_in(&self, scope: &Scope, split: &Split, first_id: usize) -> Result<Vec<Action>> {
345        self.validate_scope(scope)?;
346        self.admit_split(split)?;
347        let env = scope.env.clone();
348        let mut x = Expander {
349            core: &self.core,
350            split,
351            out: Vec::new(),
352            stack: Vec::new(),
353            first_id,
354        };
355        // Leaves, `\E`s and constants carry their own names.
356        let r = on_stack(move || x.expand(&split.root, &env).map(|()| x.out));
357        match r {
358            Ok(Ok(v)) => Ok(v),
359            Ok(Err(Split1::Throw(e))) => Err(EvalError::unsupported(format!(
360                "a next-state relation TLC cannot split ({})",
361                e.message().lines().next().unwrap_or("")
362            ))),
363            Ok(Err(Split1::Fatal(e))) | Err(e) => Err(e),
364        }
365    }
366
367    fn admit_split(&self, split: &Split) -> Result<()> {
368        let mut work = vec![&split.root];
369        for (&def, tree) in &split.defs {
370            self.admit_def(def)?;
371            work.push(tree);
372        }
373        let mut remaining = 65_536_usize;
374        while let Some(tree) = work.pop() {
375            remaining = remaining
376                .checked_sub(1)
377                .ok_or_else(|| EvalError::resource_limit("action split admission"))?;
378            let (expr, name) = match tree {
379                ActionTree::Disj { expr, children } => {
380                    work.extend(children);
381                    (*expr, None)
382                }
383                ActionTree::Exists { expr, name, body } => {
384                    work.push(body);
385                    (*expr, Some(*name))
386                }
387                ActionTree::Scope { expr, body } => {
388                    work.push(body);
389                    (*expr, None)
390                }
391                ActionTree::Inline { expr, def, .. } => {
392                    self.admit_def(*def)?;
393                    (*expr, None)
394                }
395                ActionTree::Leaf { expr, name } | ActionTree::Configured { expr, name } => {
396                    (*expr, Some(*name))
397                }
398                ActionTree::Throws { expr } => (*expr, None),
399            };
400            self.admit_expr(expr)?;
401            if let Some(ActionName::Def(def)) = name {
402                self.admit_def(def)?;
403            }
404            if work.len() > remaining {
405                return Err(EvalError::resource_limit("action split admission"));
406            }
407        }
408        Ok(())
409    }
410
411    /// Evaluates an action's predicate as an expression (TLC's
412    /// `Tool.eval(pred, con, s0, s1, EvalControl.Clear)`), for a checker's
413    /// invariants, constraints and implied actions found by a binding stage.
414    ///
415    /// # Errors
416    /// Any evaluation error, refusal or resource limit.
417    pub fn eval_action(&self, action: &Action, st: &St) -> Result<Value> {
418        self.validate_scope(&action.scope())?;
419        self.validate_state_context(st)?;
420        let ev = self.core.eval(&mut action.env.clone(), st, action.expr)?;
421        self.core.force_fcn(ev)
422    }
423
424    /// [`Evaluator::scope_shares_side_effects`] for an initial predicate or
425    /// action.
426    #[must_use]
427    pub fn action_shares_side_effects(&self, action: &Action) -> bool {
428        self.scope_shares_side_effects(&action.scope())
429    }
430
431    /// Generates the initial states (`Tool.getInitStates`): every initial
432    /// predicate in order, the first one enumerated and the others consed as
433    /// its continuation. Each state, duplicates included, goes to `sink`
434    /// (TLC's `DoInitFunctor.addElement` counts every one).
435    ///
436    /// # Errors
437    /// The evaluation error, refusal or resource limit that ended the
438    /// enumeration, with the number of states emitted before it.
439    pub fn init_states(
440        &self,
441        inits: &[Action],
442        sink: &mut dyn FnMut(&Successor<'_>) -> Flow,
443    ) -> std::result::Result<Outcome, NextError> {
444        self.init_states_mode(inits, sink, false)
445    }
446
447    /// Runs the same initial generator with the diagnostic tool's source hook.
448    /// Cached/stored values are not relabelled; only actual fresh constructors
449    /// acquire diagnostic sources. The current host owner remains installed.
450    ///
451    /// # Errors
452    /// The actual generation error, refusal or owned interruption.
453    pub fn init_states_diagnostic(
454        &self,
455        inits: &[Action],
456        sink: &mut dyn FnMut(&Successor<'_>) -> Flow,
457    ) -> std::result::Result<Outcome, NextError> {
458        self.init_states_mode(inits, sink, true)
459    }
460
461    fn init_states_mode(
462        &self,
463        inits: &[Action],
464        sink: &mut dyn FnMut(&Successor<'_>) -> Flow,
465        diagnostic: bool,
466    ) -> std::result::Result<Outcome, NextError> {
467        for action in inits {
468            self.validate_scope(&action.scope())
469                .map_err(|error| NextError {
470                    error,
471                    emitted: 0,
472                    intermediate: 0,
473                    action: None,
474                })?;
475        }
476        let Some(first) = inits.first() else {
477            return Ok(Outcome {
478                emitted: 0,
479                intermediate: 0,
480                stopped: false,
481            });
482        };
483        let nvars = self.core.ir.vars().len();
484        let mut acts: Acts = None;
485        for a in inits[1..].iter().rev() {
486            acts = cons(&acts, Kind::Pred, a.expr, &a.env);
487        }
488        let mut g = Gen {
489            core: &self.core,
490            init: true,
491            diagnostic,
492            s0: StateRef::Empty,
493            s1: vec![None; nvars].into(),
494            action: first,
495            ordinal: 0,
496            emitted: 0,
497            intermediate: 0,
498            sink,
499            choices: None,
500        };
501        let r = g.step(first.expr, &acts, &first.env);
502        g.finish(r, None)
503    }
504
505    /// Generates the successors of `s0` under one action
506    /// (`Tool.getNextStates(functor, state, action)`), in TLC's order,
507    /// duplicates included. `ordinal` is the number of successors of `s0`
508    /// already generated by earlier actions.
509    ///
510    /// # Errors
511    /// The evaluation error, refusal or resource limit that ended the
512    /// enumeration, with the number of successors emitted before it.
513    pub fn next_states(
514        &self,
515        action: &Action,
516        s0: &StateVals,
517        ordinal: u64,
518        sink: &mut dyn FnMut(&Successor<'_>) -> Flow,
519    ) -> std::result::Result<Outcome, NextError> {
520        self.next_states_mode(action, s0, ordinal, sink, false, None)
521    }
522
523    /// Traverses Next's disjunctions and bounded existentials in a seeded
524    /// constructive order. The sink stops after its first admitted complete
525    /// state; returning [`Flow::Continue`] searches the remaining alternatives.
526    /// Init and predicate evaluation, including `ENABLED`, retain their ordinary
527    /// semantics. `choose(n)` must return an index below the positive `n`.
528    ///
529    /// # Errors
530    /// The ordinary generation errors, an unsupported indexed domain, or an
531    /// out-of-range index returned by the caller.
532    pub fn next_states_generation(
533        &self,
534        action: &Action,
535        s0: &StateVals,
536        ordinal: u64,
537        choose: &mut dyn FnMut(u64) -> u64,
538        sink: &mut dyn FnMut(&Successor<'_>) -> Flow,
539    ) -> std::result::Result<Outcome, NextError> {
540        self.next_states_mode(action, s0, ordinal, sink, false, Some(choose))
541    }
542
543    /// Generates Next with the diagnostic tool's source hook. Only receivers
544    /// actually constructed during this execution acquire diagnostic sources;
545    /// cached or stored values retain their original lifetime and provenance.
546    /// The current host owner remains installed.
547    ///
548    /// ```no_run
549    /// # fn replay(ev: &dive_eval::Evaluator, action: &dive_eval::next::Action, source: &dive_eval::next::StateVals) {
550    /// let result = ev.next_states_diagnostic(action, source, 0, &mut |_| {
551    ///     dive_eval::next::Flow::Continue
552    /// });
553    /// // Inspect the actual error's typed receiver source, never its text.
554    /// # let _ = result;
555    /// # }
556    /// ```
557    ///
558    /// # Errors
559    /// The actual generation error, refusal or owned interruption.
560    pub fn next_states_diagnostic(
561        &self,
562        action: &Action,
563        s0: &StateVals,
564        ordinal: u64,
565        sink: &mut dyn FnMut(&Successor<'_>) -> Flow,
566    ) -> std::result::Result<Outcome, NextError> {
567        self.next_states_mode(action, s0, ordinal, sink, true, None)
568    }
569
570    fn next_states_mode(
571        &self,
572        action: &Action,
573        s0: &StateVals,
574        ordinal: u64,
575        sink: &mut dyn FnMut(&Successor<'_>) -> Flow,
576        diagnostic: bool,
577        choices: Option<&mut dyn FnMut(u64) -> u64>,
578    ) -> std::result::Result<Outcome, NextError> {
579        self.validate_scope(&action.scope())
580            .map_err(|error| NextError {
581                error,
582                emitted: 0,
583                intermediate: 0,
584                action: Some(action.id),
585            })?;
586        let mut g = Gen {
587            core: &self.core,
588            init: false,
589            diagnostic,
590            s0: StateRef::Vals(s0.clone()),
591            s1: vec![None; s0.len()].into(),
592            action,
593            ordinal,
594            emitted: 0,
595            intermediate: 0,
596            sink,
597            choices,
598        };
599        let r = g.step(action.expr, &None, &action.env);
600        g.finish(r, Some(action.id))
601    }
602
603    /// Generates the successors of `s0` under every action in order
604    /// (`Tool.getNextStates(functor, state)`).
605    ///
606    /// # Errors
607    /// As [`Evaluator::next_states`]; `emitted` counts all actions' states.
608    pub fn successors(
609        &self,
610        actions: &[Action],
611        s0: &StateVals,
612        sink: &mut dyn FnMut(&Successor<'_>) -> Flow,
613    ) -> std::result::Result<Outcome, NextError> {
614        let mut total = 0u64;
615        let mut intermediate = 0u64;
616        for a in actions {
617            match self.next_states(a, s0, total, sink) {
618                Ok(o) => {
619                    total += o.emitted;
620                    intermediate += o.intermediate;
621                    if o.stopped {
622                        return Ok(Outcome {
623                            emitted: total,
624                            intermediate,
625                            stopped: true,
626                        });
627                    }
628                }
629                Err(mut e) => {
630                    e.emitted += total;
631                    e.intermediate += intermediate;
632                    return Err(e);
633                }
634            }
635        }
636        Ok(Outcome {
637            emitted: total,
638            intermediate,
639            stopped: false,
640        })
641    }
642}
643
644/// Runs `f` on a thread with [`crate::RECOMMENDED_STACK`] (splitting can
645/// evaluate deeply recursive operators).
646fn on_stack<T: Send>(f: impl FnOnce() -> T + Send) -> Result<T> {
647    std::thread::scope(|s| {
648        std::thread::Builder::new()
649            .stack_size(crate::RECOMMENDED_STACK)
650            .spawn_scoped(s, f)
651            .map_err(|e| EvalError::resource_limit(format!("cannot start a thread: {e}")))?
652            .join()
653            .map_err(|_| EvalError::bug("action expansion panicked"))
654    })
655}
656
657// -----------------------------------------------------------------------------
658// The continuation list
659// -----------------------------------------------------------------------------
660
661#[derive(Clone, Copy, Debug, PartialEq, Eq)]
662enum Kind {
663    /// `IActionItemList.PRED` and conjuncts.
664    Pred,
665    /// `IActionItemList.UNCHANGED`.
666    Unchanged,
667    /// `IActionItemList.CHANGED`.
668    Changed,
669}
670
671#[derive(Debug)]
672struct Item {
673    kind: Kind,
674    expr: ExprId,
675    env: Env,
676    next: Acts,
677}
678
679/// TLC's `ActionItemList`: a persistent list.
680type Acts = Option<Arc<Item>>;
681
682#[allow(
683    clippy::unnecessary_wraps,
684    reason = "a cons cell is a non-empty list, used where lists are expected"
685)]
686fn cons(acts: &Acts, kind: Kind, expr: ExprId, env: &Env) -> Acts {
687    Some(Arc::new(Item {
688        kind,
689        expr,
690        env: env.clone(),
691        next: acts.clone(),
692    }))
693}
694
695// -----------------------------------------------------------------------------
696// The generator
697// -----------------------------------------------------------------------------
698
699/// `getInitStates` (with `init`) or `getNextStates` over one action.
700struct Gen<'a, 's, 'c> {
701    core: &'a Arc<Core>,
702    init: bool,
703    diagnostic: bool,
704    /// The current state (`Empty` for initial states).
705    s0: StateRef,
706    /// The successor being built (`ps`, the initial state, with `init`).
707    s1: StateVals,
708    action: &'a Action,
709    ordinal: u64,
710    emitted: u64,
711    /// Intermediate states of `\cdot` counted as generated (`cdot.rs`).
712    intermediate: u64,
713    sink: &'s mut dyn FnMut(&Successor<'_>) -> Flow,
714    /// Only this actual Next generator may draw; ordinary evaluator calls
715    /// and separately constructed ENABLED generators never inherit it.
716    choices: Option<&'c mut dyn FnMut(u64) -> u64>,
717}
718
719impl Gen<'_, '_, '_> {
720    fn finish(
721        &self,
722        r: Result<Flow>,
723        action: Option<usize>,
724    ) -> std::result::Result<Outcome, NextError> {
725        match r {
726            Ok(flow) => Ok(Outcome {
727                emitted: self.emitted,
728                intermediate: self.intermediate,
729                stopped: flow == Flow::Stop,
730            }),
731            Err(error) => Err(NextError {
732                error,
733                emitted: self.emitted,
734                intermediate: self.intermediate,
735                action,
736            }),
737        }
738    }
739
740    /// The states and control TLC evaluates expressions under.
741    fn st(&self) -> St {
742        if self.init {
743            // `eval(e, c, ps, TLCState.Empty, EvalControl.Init)`
744            St {
745                s0: StateRef::Vals(self.s1.clone()),
746                s1: StateRef::Empty,
747                control: control::INIT
748                    | if self.diagnostic {
749                        control::DIAGNOSTIC
750                    } else {
751                        0
752                    },
753            }
754        } else {
755            St {
756                s0: self.s0.clone(),
757                s1: StateRef::Vals(self.s1.clone()),
758                control: if self.diagnostic {
759                    control::DIAGNOSTIC
760                } else {
761                    control::CLEAR
762                },
763            }
764        }
765    }
766
767    /// The states a `LazyValue`'s cache is consulted under
768    /// (`getCachedValue(this, ps, null, Clear)` for initial states).
769    fn st_cache(&self) -> St {
770        if self.init {
771            St {
772                s0: StateRef::Vals(self.s1.clone()),
773                s1: StateRef::Null,
774                control: control::CLEAR,
775            }
776        } else {
777            self.st()
778        }
779    }
780
781    fn what(&self) -> &'static str {
782        if self.init {
783            "initial states"
784        } else {
785            "next states"
786        }
787    }
788
789    fn bind(&mut self, var: usize, v: Value) {
790        if let Some(slot) = Arc::make_mut(&mut self.s1).get_mut(var) {
791            *slot = Some(v);
792        }
793    }
794
795    fn unbind(&mut self, var: usize) {
796        if let Some(slot) = Arc::make_mut(&mut self.s1).get_mut(var) {
797            *slot = None;
798        }
799    }
800
801    fn all_assigned(&self) -> bool {
802        self.s1.iter().all(Option::is_some)
803    }
804
805    fn emit(&mut self) -> Flow {
806        let succ = Successor {
807            state: &self.s1,
808            action: self.action,
809            ordinal: self.ordinal,
810        };
811        let flow = (self.sink)(&succ);
812        self.ordinal += 1;
813        self.emitted += 1;
814        flow
815    }
816
817    fn eval(&self, env: &Env, e: ExprId) -> Result<Ev> {
818        self.core.eval(&mut env.clone(), &self.st(), e)
819    }
820
821    fn eval_v(&self, env: &Env, e: ExprId) -> Result<Value> {
822        self.core.eval_v(&mut env.clone(), &self.st(), e)
823    }
824
825    /// `getNextStates(action, acts, s0, s1, ...)` / `getInitStates(acts, ps,
826    /// ...)`: the continuation.
827    fn cont(&mut self, acts: &Acts) -> Result<Flow> {
828        let Some(item) = acts else {
829            return Ok(self.emit());
830        };
831        if self.init {
832            if self.all_assigned() {
833                return self.init_all_assigned(acts);
834            }
835            return self.step(item.expr, &item.next, &item.env);
836        }
837        if self.core.opts.warnings && self.all_assigned() {
838            return self.next_all_assigned(acts);
839        }
840        match item.kind {
841            Kind::Pred => self.step(item.expr, &item.next, &item.env),
842            Kind::Unchanged => self.unchanged(item.expr, &item.next, &item.env),
843            Kind::Changed => {
844                if self.changed(item)? {
845                    self.cont(&item.next)
846                } else {
847                    Ok(Flow::Continue)
848                }
849            }
850        }
851    }
852
853    /// The `CHANGED e` item of `<A>_e`: `e` differs between the states.
854    fn changed(&self, item: &Item) -> Result<bool> {
855        let s0 = St {
856            s0: self.s0.clone(),
857            s1: StateRef::Empty,
858            control: control::CLEAR,
859        };
860        let s1 = St {
861            s0: StateRef::Vals(self.s1.clone()),
862            s1: StateRef::Empty,
863            control: control::CLEAR,
864        };
865        let v1 = self.core.eval_v(&mut item.env.clone(), &s0, item.expr)?;
866        let v2 = self.core.eval_v(&mut item.env.clone(), &s1, item.expr)?;
867        Ok(!self.core.equals(&v1, &v2)?)
868    }
869
870    /// `getInitStates(acts, ps, ...)` once every variable is assigned
871    /// (`Tool.java:540-572`).
872    fn init_all_assigned(&mut self, acts: &Acts) -> Result<Flow> {
873        let mut cur = acts.clone();
874        while let Some(item) = cur.take() {
875            let v = self.eval(&item.env, item.expr)?;
876            match v {
877                Ev::V(Value::Bool(true)) => {}
878                Ev::V(Value::Bool(false)) => {
879                    return Ok(Flow::Continue);
880                }
881                other => return Err(self.expected_bool(&other, item.expr)),
882            }
883            cur.clone_from(&item.next);
884        }
885        Ok(self.emit())
886    }
887
888    /// `getNextStatesAllAssigned` (`Tool.java:1047-1082`).
889    fn next_all_assigned(&mut self, acts: &Acts) -> Result<Flow> {
890        let mut cur = acts.clone();
891        while let Some(item) = cur.take() {
892            match item.kind {
893                Kind::Pred => {
894                    let v = self.eval(&item.env, item.expr)?;
895                    match v {
896                        Ev::V(Value::Bool(true)) => {}
897                        Ev::V(Value::Bool(false)) => return Ok(Flow::Continue),
898                        other => return Err(self.expected_bool(&other, item.expr)),
899                    }
900                }
901                Kind::Unchanged => return self.unchanged(item.expr, &item.next, &item.env),
902                Kind::Changed => {
903                    if !self.changed(&item)? {
904                        return Ok(Flow::Continue);
905                    }
906                }
907            }
908            cur.clone_from(&item.next);
909        }
910        Ok(self.emit())
911    }
912
913    /// `TLC_EXPECTED_EXPRESSION_IN_COMPUTING` for a non-boolean.
914    fn expected_bool(&self, v: &Ev, at: ExprId) -> EvalError {
915        EvalError::coded(
916            Ec::ExpectedExpressionInComputing,
917            format!(
918                "In computing {}, TLC expected a boolean expression,\nbut instead found {}.\n{}",
919                self.what(),
920                self.core.ev_string(v),
921                self.core.loc(at)
922            ),
923        )
924    }
925
926    /// Continues after a predicate that evaluated to `v`.
927    fn after_bool(&mut self, v: &Ev, acts: &Acts, at: ExprId) -> Result<Flow> {
928        match v {
929            Ev::V(Value::Bool(true)) => self.cont(acts),
930            Ev::V(Value::Bool(false)) => Ok(Flow::Continue),
931            other => Err(self.expected_bool(other, at)),
932        }
933    }
934
935    /// The default rule: evaluate `e` as a boolean.
936    fn default_rule(&mut self, e: ExprId, acts: &Acts, env: &Env) -> Result<Flow> {
937        let v = self.eval(env, e)?;
938        match v {
939            Ev::V(Value::Bool(true)) => self.cont(acts),
940            Ev::V(Value::Bool(false)) => Ok(Flow::Continue),
941            other if self.init => Err(EvalError::general(format!(
942                "In computing initial states, TLC expected a boolean expression,\nbut instead found {}.\n{}",
943                self.core.ev_string(&other),
944                self.core.loc(e)
945            ))),
946            _ if matches!(self.core.ir.expr(e), Expr::Num(_) | Expr::Str(_)) => {
947                Err(EvalError::general(format!(
948                    "The next state relation is not a boolean expression.\n{}",
949                    self.core.loc(e)
950                )))
951            }
952            other => Err(self.expected_bool(&other, e)),
953        }
954    }
955
956    /// `getNextStates(action, pred, acts, c, ...)` / `getInitStates(init,
957    /// acts, c, ...)`.
958    fn step(&mut self, e: ExprId, acts: &Acts, env: &Env) -> Result<Flow> {
959        self.step_inner(e, acts, env).map_err(|error| error.at(e))
960    }
961
962    fn step_inner(&mut self, e: ExprId, acts: &Acts, env: &Env) -> Result<Flow> {
963        let core = self.core;
964        let _g = core.enter(e)?;
965        let node = core.ir.node(e);
966        match &node.expr {
967            Expr::Junction { kind, items, .. } => match kind {
968                JunctionKind::And => {
969                    // OPCODE_cl / OPCODE_land
970                    let mut acts1 = acts.clone();
971                    for &i in items.iter().skip(1).rev() {
972                        acts1 = cons(&acts1, Kind::Pred, i, env);
973                    }
974                    match items.first() {
975                        Some(&first) => self.step(first, &acts1, env),
976                        None => self.cont(acts),
977                    }
978                }
979                JunctionKind::Or => {
980                    // OPCODE_dl / OPCODE_lor
981                    if let Some(choose) = self.choices.as_deref_mut() {
982                        let len = u64::try_from(items.len()).map_err(|_| {
983                            EvalError::resource_limit("generation disjunction size")
984                        })?;
985                        let mut order = crate::generation::IndexOrder::new(len, choose)?;
986                        while let Some(index) = order.current() {
987                            let index = usize::try_from(index).map_err(|_| {
988                                EvalError::resource_limit("generation branch index")
989                            })?;
990                            if self.step(items[index], acts, env)? == Flow::Stop {
991                                return Ok(Flow::Stop);
992                            }
993                            if !order.advance() {
994                                break;
995                            }
996                        }
997                        return Ok(Flow::Continue);
998                    }
999                    for &i in items {
1000                        if self.step(i, acts, env)? == Flow::Stop {
1001                            return Ok(Flow::Stop);
1002                        }
1003                    }
1004                    Ok(Flow::Continue)
1005                }
1006            },
1007            Expr::Quant {
1008                kind: QuantKind::Exists,
1009                bounds,
1010                body,
1011            } if bounds.iter().all(|b| b.domain.is_some()) => {
1012                // OPCODE_be
1013                let st = self.st();
1014                if let Some(choose) = self.choices.as_deref_mut() {
1015                    let mut inner = env.clone();
1016                    let mut contexts =
1017                        core.generation_contexts(&mut inner, &st, bounds, e, choose)?;
1018                    while contexts.bind(core, &mut inner)? {
1019                        if self.step(*body, acts, &inner)? == Flow::Stop {
1020                            return Ok(Flow::Stop);
1021                        }
1022                        contexts.advance();
1023                    }
1024                    return Ok(Flow::Continue);
1025                }
1026                let mut flow = Flow::Continue;
1027                let mut err: Option<EvalError> = None;
1028                let body = *body;
1029                core.for_each_context(&mut env.clone(), &st, bounds, e, &mut |_, env1| match self
1030                    .step(body, acts, env1)
1031                {
1032                    Ok(Flow::Continue) => Ok(true),
1033                    Ok(Flow::Stop) => {
1034                        flow = Flow::Stop;
1035                        Ok(false)
1036                    }
1037                    Err(x) => {
1038                        err = Some(x);
1039                        Ok(false)
1040                    }
1041                })?;
1042                match err {
1043                    Some(x) => Err(x),
1044                    None => Ok(flow),
1045                }
1046            }
1047            Expr::Quant {
1048                kind: QuantKind::Forall,
1049                bounds,
1050                body,
1051            } if bounds.iter().all(|b| b.domain.is_some()) => {
1052                // OPCODE_bf
1053                let st = self.st();
1054                let mut envs: Vec<Env> = Vec::new();
1055                core.for_each_context(&mut env.clone(), &st, bounds, e, &mut |_, env1| {
1056                    envs.push(env1.clone());
1057                    Ok(true)
1058                })?;
1059                let Some((first, rest)) = envs.split_first() else {
1060                    return self.cont(acts);
1061                };
1062                let mut acts1 = acts.clone();
1063                for c2 in rest {
1064                    acts1 = cons(&acts1, Kind::Pred, *body, c2);
1065                }
1066                self.step(*body, &acts1, first)
1067            }
1068            Expr::If { cond, then, other } => {
1069                // OPCODE_ite
1070                let g = self.eval(env, *cond)?;
1071                let b = match g {
1072                    Ev::V(Value::Bool(b)) => b,
1073                    other => {
1074                        let kind = core.kind_of(&other);
1075                        return Err(EvalError::general(if self.init {
1076                            format!(
1077                                "In computing initial states, a non-boolean expression ({kind}) was used as the condition of an IF.\n{}",
1078                                core.loc(e)
1079                            )
1080                        } else {
1081                            format!(
1082                                "In computing next states, a non-boolean expression ({kind}) was used as the condition of an IF.{}",
1083                                core.loc(e)
1084                            )
1085                        }));
1086                    }
1087                };
1088                self.step(if b { *then } else { *other }, acts, env)
1089            }
1090            Expr::Case { arms, other } => {
1091                if self.choices.is_some() {
1092                    return Err(EvalError::unsupported(
1093                        "constructive generation of CASE actions",
1094                    ));
1095                }
1096                // OPCODE_case
1097                for arm in arms {
1098                    match self.eval(env, arm.guard)? {
1099                        Ev::V(Value::Bool(true)) => return self.step(arm.value, acts, env),
1100                        Ev::V(Value::Bool(false)) => {}
1101                        other => {
1102                            return Err(EvalError::general(format!(
1103                                "In computing {}, a non-boolean expression ({}) was used as a guard condition of a CASE.\n{}",
1104                                self.what(),
1105                                core.kind_of(&other),
1106                                core.loc(arm.value)
1107                            )));
1108                        }
1109                    }
1110                }
1111                match other {
1112                    Some(o) => self.step(*o, acts, env),
1113                    None => Err(EvalError::general(format!(
1114                        "In computing {}, TLC encountered a CASE with no conditions true.\n{}",
1115                        self.what(),
1116                        core.loc(e)
1117                    ))),
1118                }
1119            }
1120            Expr::Implies(a, b) => {
1121                // OPCODE_implies
1122                match self.eval(env, *a)? {
1123                    Ev::V(Value::Bool(true)) => self.step(*b, acts, env),
1124                    Ev::V(Value::Bool(false)) => self.cont(acts),
1125                    other => {
1126                        let kind = core.kind_of(&other);
1127                        Err(EvalError::general(if self.init {
1128                            format!(
1129                                "In computing initial states of a predicate of form P => Q, P was {kind}\n.{}",
1130                                core.loc(e)
1131                            )
1132                        } else {
1133                            format!(
1134                                "In computing next states of a predicate of the form P => Q, P was\n{kind}.\n{}",
1135                                core.loc(e)
1136                            )
1137                        }))
1138                    }
1139                }
1140            }
1141            Expr::Builtin {
1142                op: op @ (BuiltinOp::Eq | BuiltinOp::In | BuiltinOp::Subseteq),
1143                args,
1144            } if args.len() == 2 => self.assign(*op, args[0], args[1], e, acts, env),
1145            Expr::Unchanged(a) if !self.init => self.unchanged(*a, acts, env),
1146            Expr::Cdot(a, b) if !self.init => self.cdot(*a, *b, acts, env, e),
1147            Expr::StepBox { action, sub } if !self.init => {
1148                // OPCODE_sa
1149                if self.step(*action, acts, env)? == Flow::Stop {
1150                    return Ok(Flow::Stop);
1151                }
1152                self.unchanged(*sub, acts, env)
1153            }
1154            Expr::StepAngle { action, sub } if !self.init => {
1155                // OPCODE_aa
1156                let acts1 = cons(acts, Kind::Changed, *sub, env);
1157                self.step(*action, &acts1, env)
1158            }
1159            Expr::Let { defs, body } => {
1160                // LetInKind: the definitions are not bound; a use finds the
1161                // definition and evaluates its body afresh each time.
1162                let env1 = core.bind_let_uncached(env, defs);
1163                self.step(*body, acts, &env1)
1164            }
1165            Expr::Subst { bindings, body } => {
1166                // SubstInKind: uncached lazy values over the outer context.
1167                let env1 = core.bind_subst(env, &self.st(), bindings, false)?;
1168                self.step(*body, acts, &env1)
1169            }
1170            Expr::Label { body, .. } | Expr::Selected(body) => self.step(*body, acts, env),
1171            Expr::FcnApply { fcn, arg } => self.fcn_apply(*fcn, *arg, e, acts, env),
1172            Expr::Def(_)
1173            | Expr::Apply { .. }
1174            | Expr::Local(_)
1175            | Expr::Const(_)
1176            | Expr::SubstRef { primed: false, .. } => self.user_op(e, acts, env),
1177            _ => self.default_rule(e, acts, env),
1178        }
1179    }
1180
1181    /// `x' = e`, `x' \in S`, `x' \subseteq S` (`x = e`, ... in an initial
1182    /// predicate).
1183    fn assign(
1184        &mut self,
1185        op: BuiltinOp,
1186        lhs: ExprId,
1187        rhs: ExprId,
1188        e: ExprId,
1189        acts: &Acts,
1190        env: &Env,
1191    ) -> Result<Flow> {
1192        let core = self.core;
1193        let var = if self.init {
1194            core.var_of(env, lhs, false)?
1195        } else {
1196            core.primed_var(env, lhs, false)?
1197        };
1198        let Some(var) = var else {
1199            let v = self.eval(env, e)?;
1200            return match v {
1201                Ev::V(Value::Bool(true)) => self.cont(acts),
1202                Ev::V(Value::Bool(false)) => Ok(Flow::Continue),
1203                _ => Err(EvalError::bug("=, \\in or \\subseteq not boolean")),
1204            };
1205        };
1206        let lval = self.s1.get(var).cloned().flatten();
1207        match op {
1208            BuiltinOp::Eq => {
1209                let rval = core.embed(self.eval(env, rhs)?)?;
1210                match lval {
1211                    None => {
1212                        self.bind(var, rval);
1213                        let flow = self.cont(acts);
1214                        self.unbind(var);
1215                        flow
1216                    }
1217                    Some(l) => {
1218                        if core.equals(&l, &rval)? {
1219                            self.cont(acts)
1220                        } else {
1221                            Ok(Flow::Continue)
1222                        }
1223                    }
1224                }
1225            }
1226            BuiltinOp::In => {
1227                let rval = self.eval_v(env, rhs)?;
1228                match lval {
1229                    None => {
1230                        let Value::Set(s) = &rval else {
1231                            return Err(self.not_enumerable_in(e));
1232                        };
1233                        if !is_enumerable(&rval) {
1234                            return Err(self.not_enumerable_in(e));
1235                        }
1236                        if let Some((lo, hi)) = s.as_interval() {
1237                            // IntervalValue.elements() walks ascending integers;
1238                            // no normalized copy or history-sensitive lazy-set
1239                            // decision is needed. Reach the sink before building
1240                            // an entire domain so its stop can interrupt Init
1241                            // and successor enumeration.
1242                            return self.bind_interval(var, lo, hi, acts);
1243                        }
1244                        if let Some(elements) = core.in_element_stream(s)? {
1245                            for value in elements.with_owner(rval) {
1246                                let value = value?;
1247                                if self.bind_value(var, value, acts)? == Flow::Stop {
1248                                    return Ok(Flow::Stop);
1249                                }
1250                            }
1251                            return Ok(Flow::Continue);
1252                        }
1253                        let elems = core.in_elements(s)?;
1254                        self.bind_each(var, &elems, acts)
1255                    }
1256                    Some(l) => {
1257                        if core.member(&l, &rval)? {
1258                            self.cont(acts)
1259                        } else {
1260                            Ok(Flow::Continue)
1261                        }
1262                    }
1263                }
1264            }
1265            _ => {
1266                let rset = self.eval_v(env, rhs)?;
1267                if !matches!(rset, Value::Set(_)) {
1268                    return Err(EvalError::unsupported(format!(
1269                        "x' \\subseteq S where S is not a set ({})",
1270                        core.loc(e)
1271                    )));
1272                }
1273                let rval = Value::subset(rset, core.ctx);
1274                match lval {
1275                    None => {
1276                        let Value::Set(s) = &rval else {
1277                            return Err(EvalError::bug("SUBSET is not a set"));
1278                        };
1279                        let elems = core.explore(s)?;
1280                        self.bind_each(var, &elems, acts)
1281                    }
1282                    Some(l) => {
1283                        if core.member(&l, &rval)? {
1284                            self.cont(acts)
1285                        } else {
1286                            Ok(Flow::Continue)
1287                        }
1288                    }
1289                }
1290            }
1291        }
1292    }
1293
1294    fn not_enumerable_in(&self, e: ExprId) -> EvalError {
1295        EvalError::general(format!(
1296            "In computing {}, the right side of \\IN is not enumerable.\n{}",
1297            self.what(),
1298            self.core.loc(e)
1299        ))
1300    }
1301
1302    fn bind_each(&mut self, var: usize, elems: &[Value], acts: &Acts) -> Result<Flow> {
1303        for x in elems {
1304            if self.bind_value(var, x.clone(), acts)? == Flow::Stop {
1305                return Ok(Flow::Stop);
1306            }
1307        }
1308        Ok(Flow::Continue)
1309    }
1310
1311    fn bind_value(&mut self, var: usize, value: Value, acts: &Acts) -> Result<Flow> {
1312        // A candidate is real work even when its continuation rejects it and
1313        // no successor reaches the sink, including private composition sinks.
1314        self.core.loop_work()?;
1315        self.bind(var, value);
1316        let flow = self.cont(acts);
1317        self.unbind(var);
1318        flow
1319    }
1320
1321    fn bind_interval(
1322        &mut self,
1323        var: usize,
1324        lo: &dive_value::Int,
1325        hi: &dive_value::Int,
1326        acts: &Acts,
1327    ) -> Result<Flow> {
1328        if let (Some(lo), Some(hi)) = (lo.to_i64(), hi.to_i64()) {
1329            for value in lo..=hi {
1330                if self.bind_value(var, Value::Int(value), acts)? == Flow::Stop {
1331                    return Ok(Flow::Stop);
1332                }
1333            }
1334        } else {
1335            let mut value = lo.clone();
1336            while value <= *hi {
1337                if self.bind_value(var, Value::int(value.clone()), acts)? == Flow::Stop {
1338                    return Ok(Flow::Stop);
1339                }
1340                if value == *hi {
1341                    break;
1342                }
1343                value = value.add(&dive_value::Int::ONE, dive_value::IntMode::Big)?;
1344            }
1345        }
1346        Ok(Flow::Continue)
1347    }
1348
1349    /// `processUnchanged` (`Tool.java:1557-1661`).
1350    fn unchanged(&mut self, e: ExprId, acts: &Acts, env: &Env) -> Result<Flow> {
1351        let core = self.core;
1352        let _g = core.enter(e)?;
1353        if let Some(var) = core.var_of(env, e, false)? {
1354            let name = &core.ir.decl(core.ir.vars()[var]).name;
1355            let Some(val0) = core.state_variable(&self.s0, name, Some(var))?.cloned() else {
1356                return Err(EvalError::bug(
1357                    "UNCHANGED of a variable the current state lacks",
1358                ));
1359            };
1360            return match self.s1.get(var).cloned().flatten() {
1361                None => {
1362                    self.bind(var, val0);
1363                    let flow = self.cont(acts);
1364                    self.unbind(var);
1365                    flow
1366                }
1367                Some(val1) => {
1368                    if core.equals(&val0, &val1)? {
1369                        self.cont(acts)
1370                    } else {
1371                        core.unchanged_warning(var, e);
1372                        Ok(Flow::Continue)
1373                    }
1374                }
1375            };
1376        }
1377        match &core.ir.node(e).expr {
1378            Expr::Tuple(items) => {
1379                let Some((&first, rest)) = items.split_first() else {
1380                    return self.cont(acts);
1381                };
1382                let mut acts1 = acts.clone();
1383                for &i in rest.iter().rev() {
1384                    acts1 = cons(&acts1, Kind::Unchanged, i, env);
1385                }
1386                self.unchanged(first, &acts1, env)
1387            }
1388            _ => match core.zero_arity_target(env, e)? {
1389                Target::Body(env1, body) => self.unchanged(body, acts, &env1),
1390                Target::Value => self.verify_unchanged(e, acts, env),
1391            },
1392        }
1393    }
1394
1395    /// `verifyUnchanged`: `e` has the same value in both states.
1396    fn verify_unchanged(&mut self, e: ExprId, acts: &Acts, env: &Env) -> Result<Flow> {
1397        let st0 = St {
1398            s0: self.s0.clone(),
1399            s1: StateRef::Empty,
1400            control: control::CLEAR,
1401        };
1402        let st1 = St {
1403            s0: StateRef::Vals(self.s1.clone()),
1404            s1: StateRef::Null,
1405            control: control::CLEAR,
1406        };
1407        let v0 = self.core.eval_v(&mut env.clone(), &st0, e)?;
1408        let v1 = self.core.eval_v(&mut env.clone(), &st1, e)?;
1409        if self.core.equals(&v0, &v1)? {
1410            self.cont(acts)
1411        } else {
1412            Ok(Flow::Continue)
1413        }
1414    }
1415
1416    /// `OPCODE_fa` in an action.
1417    fn fcn_apply(
1418        &mut self,
1419        fcn: ExprId,
1420        arg: ExprId,
1421        e: ExprId,
1422        acts: &Acts,
1423        env: &Env,
1424    ) -> Result<Flow> {
1425        let core = self.core;
1426        let st = if self.init {
1427            self.st()
1428        } else {
1429            self.st().keep_lazy()
1430        };
1431        let f = core.eval(&mut env.clone(), &st, fcn)?;
1432        let fv = match f {
1433            Ev::F(lf) => {
1434                if let Some(v) = lf.materialized.get(core.host.cache_domain()) {
1435                    v
1436                } else {
1437                    // `getFcnContext`: the lambda's body, its parameters bound.
1438                    let a = self.eval_v(env, arg)?;
1439                    let env1 = core.fcn_context(&lf, &a, e)?;
1440                    return self.step(lf.body, acts, &env1);
1441                }
1442            }
1443            Ev::V(v) => v,
1444        };
1445        let Value::Fcn(fv) = fv else {
1446            return Err(EvalError::general(format!(
1447                "In computing {}, a non-function ({}) was applied as a function.\n{}",
1448                self.what(),
1449                crate::core::kind_string(&fv),
1450                core.loc(e)
1451            )));
1452        };
1453        let a = self.eval_v(env, arg)?;
1454        match core.apply_fcn(&fv, &a)? {
1455            Value::Bool(true) => self.cont(acts),
1456            Value::Bool(false) => Ok(Flow::Continue),
1457            _ => Err(EvalError::coded(
1458                Ec::ExpectedExpressionInComputing2,
1459                format!(
1460                    "In computing {}, TLC expected a boolean expression,\nbut didn't find one.\n{}",
1461                    self.what(),
1462                    core.loc(e)
1463                ),
1464            )),
1465        }
1466    }
1467
1468    /// `opcode == 0`: a user-defined operator, an argument or `LET` value, a
1469    /// constant or a Java override, looked up and followed or evaluated
1470    /// (`Tool.java:1112-1158` and `getNextStatesApplUsrDefOp`).
1471    fn user_op(&mut self, e: ExprId, acts: &Acts, env: &Env) -> Result<Flow> {
1472        let core = self.core;
1473        let st = self.st();
1474        match core.op_target(env, &st, e)? {
1475            OpTarget::Body(env1, body) => self.step(body, acts, &env1),
1476            OpTarget::Thunk(t) => {
1477                if let Some(v) = t.cached(&self.st_cache(), core.host.cache_domain()) {
1478                    return self.user_bool(&v, acts, e);
1479                }
1480                self.step(t.expr, acts, &t.env)
1481            }
1482            OpTarget::Value(v) => self.user_bool(&v, acts, e),
1483        }
1484    }
1485
1486    fn user_bool(&mut self, v: &Ev, acts: &Acts, e: ExprId) -> Result<Flow> {
1487        self.after_bool(v, acts, e)
1488    }
1489}
1490
1491// -----------------------------------------------------------------------------
1492// Lookups shared by the generator and ENABLED
1493// -----------------------------------------------------------------------------
1494
1495/// What a zero-arity name in `UNCHANGED` leads to.
1496pub(crate) enum Target {
1497    /// Follow the expression in this environment.
1498    Body(Env, ExprId),
1499    /// Compare its value.
1500    Value,
1501}
1502
1503/// What an operator application in an action leads to.
1504pub(crate) enum OpTarget {
1505    /// A definition's body, with its parameters bound.
1506    Body(Env, ExprId),
1507    /// A `LazyValue` (an argument, `LET` value or substitution).
1508    Thunk(Arc<Thunk>),
1509    /// A value: a constant, a Java override's result, a bound variable.
1510    Value(Ev),
1511}
1512
1513impl Core {
1514    /// `Tool.lookup` for an operator in an action, and the step TLC takes
1515    /// with the result: a definition is followed, a `LazyValue` is consulted,
1516    /// anything else is evaluated (`OpValue.eval`, with the control the
1517    /// generator uses).
1518    pub(crate) fn op_target(self: &Arc<Self>, env: &Env, st: &St, e: ExprId) -> Result<OpTarget> {
1519        let node = self.ir.node(e);
1520        let mut env = env.clone();
1521        match &node.expr {
1522            Expr::Def(d) => self.def_target(&mut env, st, *d, &[], e),
1523            Expr::Apply { callee, args } => match callee {
1524                OpRef::Def(d) => self.def_target(&mut env, st, *d, args, e),
1525                OpRef::Std(op) => Ok(OpTarget::Value(self.eval_std(&mut env, st, *op, args, e)?)),
1526                _ => {
1527                    let op = self.op_value(&env, callee)?;
1528                    self.opval_target(&mut env, st, &op, args, e)
1529                }
1530            },
1531            Expr::Local(lr) => match self.slot(&env, *lr)?.clone() {
1532                Sv::Thunk(t) => Ok(OpTarget::Thunk(t)),
1533                Sv::Op(op) => self.opval_target(&mut env, st, &op, &[], e),
1534                Sv::Unset => Err(EvalError::bug("read of an unbound slot")),
1535                sv => Ok(OpTarget::Value(self.force(&mut env, &sv, st, e)?)),
1536            },
1537            Expr::Const(c) => match self.consts.get(c.index()).and_then(Option::as_ref) {
1538                Some(ConstBinding::Def(d)) => self.def_target(&mut env, st, *d, &[], e),
1539                _ => Ok(OpTarget::Value(self.eval(&mut env, st, e)?)),
1540            },
1541            Expr::SubstRef {
1542                decl,
1543                primed: false,
1544            } => match env.dynamic.lookup(*decl).cloned() {
1545                Some(Sv::Thunk(t)) => Ok(OpTarget::Thunk(t)),
1546                Some(Sv::Op(op)) => self.opval_target(&mut env, st, &op, &[], e),
1547                Some(_) => Ok(OpTarget::Value(self.eval(&mut env, st, e)?)),
1548                None => {
1549                    let bound = self
1550                        .ir
1551                        .decl(*decl)
1552                        .constant
1553                        .and_then(|c| self.consts.get(c.index()).and_then(Option::as_ref));
1554                    match bound {
1555                        Some(ConstBinding::Def(d)) => self.def_target(&mut env, st, *d, &[], e),
1556                        _ => Ok(OpTarget::Value(self.eval(&mut env, st, e)?)),
1557                    }
1558                }
1559            },
1560            _ => Err(EvalError::bug("op_target on a non-operator")),
1561        }
1562    }
1563
1564    fn def_target(
1565        self: &Arc<Self>,
1566        env: &mut Env,
1567        st: &St,
1568        d: DefId,
1569        args: &[Arg],
1570        e: ExprId,
1571    ) -> Result<OpTarget> {
1572        let d = self.redirect(d);
1573        if let Some(v) = self.def_values.get(&d) {
1574            return Ok(OpTarget::Value(Ev::V(v.clone())));
1575        }
1576        let def = self.ir.def(d);
1577        if let Some(op) = def.std {
1578            return Ok(OpTarget::Value(self.eval_std(env, st, op, args, e)?));
1579        }
1580        if args.is_empty() && self.cacheable(d) {
1581            // TLC precomputed it at start-up (`processConstantDefns`) and
1582            // looks the value up; a failure there left the definition lazy.
1583            if let Some(v) = self.def_cache[d.index()].get() {
1584                return Ok(OpTarget::Value(Ev::V(v.clone())));
1585            }
1586            let mut fresh = Env::new(
1587                d,
1588                def.depth,
1589                def.frame.len(),
1590                None,
1591                crate::env::Dyn::default(),
1592            );
1593            match self.eval(&mut fresh, &St::constant(), def.body) {
1594                Ok(Ev::V(v)) => {
1595                    let _ = self.def_cache[d.index()].set(v.clone());
1596                    return Ok(OpTarget::Value(Ev::V(v)));
1597                }
1598                Ok(ev) => return Ok(OpTarget::Value(ev)),
1599                Err(err) if err.class() == ErrorClass::Eval => {}
1600                Err(err) => return Err(err),
1601            }
1602        }
1603        let env1 = self.callee_env(env, st, d, None, args)?;
1604        Ok(OpTarget::Body(env1, def.body))
1605    }
1606
1607    fn opval_target(
1608        self: &Arc<Self>,
1609        env: &mut Env,
1610        st: &St,
1611        op: &OpVal,
1612        args: &[Arg],
1613        e: ExprId,
1614    ) -> Result<OpTarget> {
1615        match op {
1616            OpVal::Def {
1617                def,
1618                parent,
1619                dynamic,
1620            } => {
1621                if self.ir.def(*def).std.is_some() {
1622                    return Ok(OpTarget::Value(self.apply_op(op, env, st, args, e)?));
1623                }
1624                // As `apply_op`: an operator passed with its context is
1625                // applied in that context.
1626                let mut caller = env.clone();
1627                if let Some(d) = dynamic {
1628                    caller.dynamic = d.clone();
1629                }
1630                let env1 = self.callee_env(&mut caller, st, *def, parent.clone(), args)?;
1631                Ok(OpTarget::Body(env1, self.ir.def(*def).body))
1632            }
1633            OpVal::Const(c) => match self.consts.get(c.index()).and_then(Option::as_ref) {
1634                Some(ConstBinding::Def(d)) => self.def_target(env, st, *d, args, e),
1635                _ => Ok(OpTarget::Value(self.apply_op(op, env, st, args, e)?)),
1636            },
1637            OpVal::Builtin(b) => match b {
1638                BuiltinOp::Eq
1639                | BuiltinOp::In
1640                | BuiltinOp::Subseteq
1641                | BuiltinOp::And
1642                | BuiltinOp::Or
1643                | BuiltinOp::Implies
1644                | BuiltinOp::Unchanged
1645                | BuiltinOp::Prime
1646                | BuiltinOp::Enabled
1647                | BuiltinOp::Cdot => Err(EvalError::unsupported(format!(
1648                    "the built-in operator {b:?} passed as an operator argument and applied in an action ({})",
1649                    self.loc(e)
1650                ))),
1651                _ => Ok(OpTarget::Value(self.apply_op(op, env, st, args, e)?)),
1652            },
1653            OpVal::Std(_) | OpVal::Unbound(_) => {
1654                Ok(OpTarget::Value(self.apply_op(op, env, st, args, e)?))
1655            }
1656        }
1657    }
1658
1659    /// For `UNCHANGED` and `ENABLED`'s `UNCHANGED`: a zero-arity operator is
1660    /// followed when its lookup is a definition or a `LazyValue`
1661    /// (`processUnchangedImpl0Arity`).
1662    pub(crate) fn zero_arity_target(self: &Arc<Self>, env: &Env, e: ExprId) -> Result<Target> {
1663        match &self.ir.node(e).expr {
1664            Expr::Def(d) => Ok(self
1665                .def_follow(env, *d)
1666                .map_or(Target::Value, |(env1, body)| Target::Body(env1, body))),
1667            Expr::Local(lr) => match self.slot(env, *lr)? {
1668                Sv::Thunk(t) => Ok(Target::Body(t.env.clone(), t.expr)),
1669                _ => Ok(Target::Value),
1670            },
1671            Expr::Const(c) => match self.consts.get(c.index()).and_then(Option::as_ref) {
1672                Some(ConstBinding::Def(d)) => Ok(self
1673                    .def_follow(env, *d)
1674                    .map_or(Target::Value, |(env1, body)| Target::Body(env1, body))),
1675                _ => Ok(Target::Value),
1676            },
1677            Expr::SubstRef {
1678                decl,
1679                primed: false,
1680            } => match env.dynamic.lookup(*decl) {
1681                Some(Sv::Thunk(t)) => Ok(Target::Body(t.env.clone(), t.expr)),
1682                _ => Ok(Target::Value),
1683            },
1684            _ => Ok(Target::Value),
1685        }
1686    }
1687
1688    /// A zero-arity definition TLC's lookup finds as an `OpDefNode`: its body
1689    /// in a fresh frame (`None` when the lookup gives a value instead).
1690    fn def_follow(&self, env: &Env, d: DefId) -> Option<(Env, ExprId)> {
1691        let d = self.redirect(d);
1692        let def = self.ir.def(d);
1693        if self.def_values.contains_key(&d)
1694            || def.std.is_some()
1695            || (self.cacheable(d) && self.def_cache[d.index()].get().is_some())
1696            || !def.params.is_empty()
1697        {
1698            return None;
1699        }
1700        let parent = match def.scope {
1701            DefScope::Local { .. } | DefScope::Inline { .. } => {
1702                Some(env.frame_at_depth(def.depth.saturating_sub(1))?.clone())
1703            }
1704            _ => None,
1705        };
1706        Some((
1707            Env::new(d, def.depth, def.frame.len(), parent, env.dynamic.clone()),
1708            def.body,
1709        ))
1710    }
1711
1712    /// `getVar`: the root variable `e` denotes, if it is one, seeing through
1713    /// substitutions, `LET`s, labels, zero-arity definitions and lazy
1714    /// arguments (`SymbolNodeValueLookupProvider.getVar`).
1715    pub(crate) fn var_of(
1716        self: &Arc<Self>,
1717        env: &Env,
1718        e: ExprId,
1719        cutoff: bool,
1720    ) -> Result<Option<usize>> {
1721        Ok(self
1722            .var_lookup(env, e, VariableLookup::Root(cutoff), false, 0)?
1723            .and_then(|decl| self.ir.decl(decl).var)
1724            .map(dive_ir::VarId::index))
1725    }
1726
1727    /// `getPrimedVar`: the root variable `e` is the primed form of.
1728    pub(crate) fn primed_var(
1729        self: &Arc<Self>,
1730        env: &Env,
1731        e: ExprId,
1732        cutoff: bool,
1733    ) -> Result<Option<usize>> {
1734        Ok(self
1735            .var_lookup(env, e, VariableLookup::Root(cutoff), true, 0)?
1736            .and_then(|decl| self.ir.decl(decl).var)
1737            .map(dive_ir::VarId::index))
1738    }
1739
1740    fn var_lookup(
1741        self: &Arc<Self>,
1742        env: &Env,
1743        e: ExprId,
1744        mode: VariableLookup,
1745        primed: bool,
1746        depth: u32,
1747    ) -> Result<Option<dive_ir::DeclId>> {
1748        if depth > 256 {
1749            return Err(EvalError::resource_limit(format!(
1750                "following definitions to a variable more than 256 levels deep ({})",
1751                self.loc(e)
1752            )));
1753        }
1754        let next = |core: &Arc<Self>, env: &Env, e: ExprId| {
1755            core.var_lookup(env, e, mode, primed, depth + 1)
1756        };
1757        match &self.ir.node(e).expr {
1758            Expr::Subst { bindings, body } => {
1759                let env1 = self.bind_subst(env, &St::default(), bindings, false)?;
1760                next(self, &env1, *body)
1761            }
1762            Expr::Let { defs, body } => {
1763                let env1 = self.bind_let_uncached(env, defs);
1764                next(self, &env1, *body)
1765            }
1766            Expr::Label { body, .. } => next(self, env, *body),
1767            Expr::Var { var, primed: p } => {
1768                Ok((*p == primed).then_some(self.ir.vars()[var.index()]))
1769            }
1770            Expr::Prime(a) if primed => self.var_lookup(env, *a, mode, false, depth + 1),
1771            Expr::SubstRef { decl, primed: p } => {
1772                if *p && !primed {
1773                    return Ok(None);
1774                }
1775                // `x'` with `x` substituted is `getVar(x)`.
1776                let as_primed = primed && !*p;
1777                let d = self.ir.decl(*decl);
1778                let cut = mode.cutoff() && d.variable;
1779                match env.dynamic.lookup_cut(*decl, cut) {
1780                    Some(Sv::Thunk(t)) => {
1781                        self.var_lookup(&t.env, t.expr, mode, as_primed, depth + 1)
1782                    }
1783                    Some(_) => Ok(None),
1784                    None if d.variable && !as_primed => {
1785                        if d.var.is_some() || matches!(mode, VariableLookup::Enabled) {
1786                            return Ok(Some(*decl));
1787                        }
1788                        match self.root_var_named(&d.name) {
1789                            Some(v) => Ok(Some(self.ir.vars()[v])),
1790                            None => Err(EvalError::unsupported(format!(
1791                                "a variable of an instantiated module, hidden by ENABLED, with no root variable of its name ({})",
1792                                self.loc(e)
1793                            ))),
1794                        }
1795                    }
1796                    None => match d.constant {
1797                        Some(c) => match self.consts.get(c.index()).and_then(Option::as_ref) {
1798                            Some(ConstBinding::Def(t)) => match self.def_follow(env, *t) {
1799                                Some((env1, body)) => {
1800                                    self.var_lookup(&env1, body, mode, as_primed, depth + 1)
1801                                }
1802                                None => Ok(None),
1803                            },
1804                            _ => Ok(None),
1805                        },
1806                        None => Ok(None),
1807                    },
1808                }
1809            }
1810            Expr::Def(d) => match self.def_follow(env, *d) {
1811                Some((env1, body)) => next(self, &env1, body),
1812                None => Ok(None),
1813            },
1814            Expr::Local(lr) => match self.slot(env, *lr)? {
1815                Sv::Thunk(t) => self.var_lookup(&t.env, t.expr, mode, primed, depth + 1),
1816                _ => Ok(None),
1817            },
1818            Expr::Const(c) => match self.consts.get(c.index()).and_then(Option::as_ref) {
1819                Some(ConstBinding::Def(t)) => match self.def_follow(env, *t) {
1820                    Some((env1, body)) => next(self, &env1, body),
1821                    None => Ok(None),
1822                },
1823                _ => Ok(None),
1824            },
1825            _ => Ok(None),
1826        }
1827    }
1828
1829    /// Binds a `LET`'s zero-arity definitions as uncached lazy values: the
1830    /// enumerator does not bind them, and each use evaluates the definition
1831    /// afresh (`getNextStates`, `LetInKind`).
1832    pub(crate) fn bind_let_uncached(self: &Arc<Self>, env: &Env, defs: &[DefId]) -> Env {
1833        self.bind_let(env, defs, false)
1834    }
1835
1836    fn bind_let(self: &Arc<Self>, env: &Env, defs: &[DefId], cachable: bool) -> Env {
1837        let mut env1 = env.clone();
1838        for &d in defs {
1839            let def = self.ir.def(d);
1840            if let DefScope::LetValue { slot, .. } = def.scope {
1841                let t = Thunk::new(def.body, env1.clone(), cachable);
1842                env1.bind(slot.index(), Sv::Thunk(t));
1843            }
1844        }
1845        env1
1846    }
1847
1848    /// Conses a `Subst`'s bindings onto the dynamic context, as lazy values
1849    /// over the outer context (cached or not, as the caller's TLC code does).
1850    /// `Tool.getFcnContext`: the lambda's context with its parameters bound
1851    /// to `arg`, for applying a lazy function as an action. TLC ignores the
1852    /// lambda's pending `EXCEPT`s here, so one with any is refused, as is an
1853    /// argument TLC would reject (its messages are not reproduced).
1854    pub(crate) fn fcn_context(
1855        self: &Arc<Self>,
1856        f: &Arc<crate::lazy::LazyFcn>,
1857        arg: &Value,
1858        e: ExprId,
1859    ) -> Result<Env> {
1860        let refuse = |what: &str| {
1861            Err(EvalError::unsupported(format!(
1862                "applying a lazily evaluated function (TLC's FcnLambdaValue) as an action, {what} ({})",
1863                self.loc(e)
1864            )))
1865        };
1866        if !f.excepts.is_empty() {
1867            return refuse("with EXCEPTs pending");
1868        }
1869        let mut env = f.body_env();
1870        if f.bounds.len() == 1 {
1871            let b = &f.bounds[0];
1872            if !self.member(arg, &b.domain)? {
1873                return refuse("to an argument outside its domain");
1874            }
1875            if b.tuple {
1876                match arg {
1877                    Value::Fcn(t) if t.as_tuple().is_some_and(|t| t.len() == b.slots.len()) => {
1878                        self.bind_one(&mut env, &b.slots, true, arg, e)?;
1879                    }
1880                    _ => return refuse("to an argument that does not match its tuple parameter"),
1881                }
1882            } else if let Some(&s) = b.slots.first() {
1883                env.bind(s, Sv::Val(arg.clone()));
1884            }
1885            return Ok(env);
1886        }
1887        let Some(elems) = (match arg {
1888            Value::Fcn(t) => t.as_tuple(),
1889            _ => None,
1890        }) else {
1891            return refuse("to an argument that is not a tuple");
1892        };
1893        let mut k = 0;
1894        for b in &f.bounds {
1895            let n = if b.tuple { 1 } else { b.slots.len() };
1896            for j in 0..n {
1897                let Some(x) = elems.get(k) else {
1898                    return refuse("to too few arguments");
1899                };
1900                if !self.member(x, &b.domain)? {
1901                    return refuse("to an argument outside its domain");
1902                }
1903                if b.tuple {
1904                    match x {
1905                        Value::Fcn(t) if t.as_tuple().is_some_and(|t| t.len() == b.slots.len()) => {
1906                            self.bind_one(&mut env, &b.slots, true, x, e)?;
1907                        }
1908                        _ => {
1909                            return refuse(
1910                                "to an argument that does not match its tuple parameter",
1911                            );
1912                        }
1913                    }
1914                } else {
1915                    env.bind(b.slots[j], Sv::Val(x.clone()));
1916                }
1917                k += 1;
1918            }
1919        }
1920        Ok(env)
1921    }
1922
1923    /// TLC's `toString` of a value in a message.
1924    pub(crate) fn ev_string(self: &Arc<Self>, v: &Ev) -> String {
1925        match v {
1926            Ev::V(v) => dive_value::print::to_tlc_string_lenient(v, self.ctx),
1927            Ev::F(f) => match self.materialize(f) {
1928                Ok(v) => dive_value::print::to_tlc_string_lenient(&v, self.ctx),
1929                Err(_) => "a function".to_owned(),
1930            },
1931        }
1932    }
1933
1934    /// `TLC_UNCHANGED_VARIABLE_CHANGED` (2143), a warning.
1935    pub(crate) fn unchanged_warning(&self, var: usize, e: ExprId) {
1936        let name = self
1937            .ir
1938            .vars()
1939            .get(var)
1940            .map_or("?", |&d| self.ir.decl(d).name.as_str());
1941        self.unchanged_named_warning(name, e);
1942    }
1943
1944    fn unchanged_named_warning(&self, name: &str, e: ExprId) {
1945        self.warn(
1946            2143,
1947            &format!(
1948                "The variable {name} was changed while it is specified as UNCHANGED at\n{}",
1949                self.loc(e)
1950            ),
1951        );
1952    }
1953}
1954
1955// -----------------------------------------------------------------------------
1956// Splitting the next-state relation (`Tool.getActions`)
1957// -----------------------------------------------------------------------------
1958
1959/// Why a subtree could not be split.
1960enum Split1 {
1961    /// TLC throws here (`ClassCastException`, a failed evaluation): the
1962    /// nearest enclosing inlining or `\E` catches it.
1963    Throw(EvalError),
1964    /// dive cannot tell what TLC does (a refusal, a resource limit, a bug).
1965    Fatal(EvalError),
1966}
1967
1968impl From<EvalError> for Split1 {
1969    fn from(e: EvalError) -> Self {
1970        if e.class() == ErrorClass::Eval {
1971            Self::Throw(e)
1972        } else {
1973            Self::Fatal(e)
1974        }
1975    }
1976}
1977
1978struct Expander<'a> {
1979    core: &'a Arc<Core>,
1980    split: &'a Split,
1981    out: Vec<Action>,
1982    /// The definitions inlined around the current node, with their
1983    /// parameters' values.
1984    stack: Vec<(DefId, Vec<(String, Value)>)>,
1985    first_id: usize,
1986}
1987
1988impl Expander<'_> {
1989    fn push(&mut self, expr: ExprId, env: &Env, name: ActionName) {
1990        let params = match name {
1991            ActionName::Def(d) => self
1992                .stack
1993                .iter()
1994                .rev()
1995                .find(|(s, _)| *s == d)
1996                .map(|(_, p)| p.clone())
1997                .unwrap_or_default(),
1998            _ => Vec::new(),
1999        };
2000        let values: Vec<String> = params
2001            .iter()
2002            .map(|(_, v)| dive_value::print::to_tlc_string_lenient(v, self.core.ctx))
2003            .collect();
2004        let id = self.first_id + self.out.len();
2005        self.out.push(Action {
2006            owner: self.core.ir.clone(),
2007            names: self.core.names.clone(),
2008            context: Arc::downgrade(self.core),
2009            expr,
2010            env: env.clone(),
2011            name,
2012            label: label(&self.core.ir, name, &values, expr),
2013            params,
2014            id,
2015        });
2016    }
2017
2018    fn expand(&mut self, t: &ActionTree, env: &Env) -> std::result::Result<(), Split1> {
2019        let core = self.core;
2020        let st = St {
2021            s0: StateRef::Empty,
2022            s1: StateRef::Empty,
2023            control: control::CLEAR,
2024        };
2025        match t {
2026            ActionTree::Leaf { expr, name } => {
2027                self.push(*expr, env, *name);
2028                Ok(())
2029            }
2030            ActionTree::Throws { expr } => Err(Split1::Throw(EvalError::general(format!(
2031                "TLC cannot split the next-state relation at {}",
2032                core.loc(*expr)
2033            )))),
2034            ActionTree::Disj { children, .. } => {
2035                for c in children {
2036                    self.expand(c, env)?;
2037                }
2038                Ok(())
2039            }
2040            ActionTree::Scope { expr, body } => {
2041                let env1 = match &core.ir.node(*expr).expr {
2042                    Expr::Let { defs, .. } => core.bind_let_uncached(env, defs),
2043                    _ => env.clone(),
2044                };
2045                self.expand(body, &env1)
2046            }
2047            ActionTree::Exists {
2048                expr,
2049                name: n,
2050                body,
2051            } => {
2052                let cnt = self.out.len();
2053                let Expr::Quant { bounds, .. } = &core.ir.node(*expr).expr else {
2054                    return Err(Split1::Fatal(EvalError::bug(
2055                        "Exists node is not a quantifier",
2056                    )));
2057                };
2058                let mut calls = 0usize;
2059                let mut failed: Option<Split1> = None;
2060                let r =
2061                    core.for_each_context(&mut env.clone(), &st, bounds, *expr, &mut |_, env1| {
2062                        calls += 1;
2063                        match self.expand(body, env1) {
2064                            Ok(()) => Ok(true),
2065                            Err(x) => {
2066                                failed = Some(x);
2067                                Ok(false)
2068                            }
2069                        }
2070                    });
2071                let outcome = match (r, failed) {
2072                    (Err(e), _) => Split1::from(e),
2073                    (Ok(()), Some(x)) => x,
2074                    (Ok(()), None) => {
2075                        if calls == 0 {
2076                            // `Enum.isDone()`: an empty enumeration is one action.
2077                            self.push(*expr, env, *n);
2078                        }
2079                        return Ok(());
2080                    }
2081                };
2082                match outcome {
2083                    Split1::Throw(_) => {
2084                        self.out.truncate(cnt);
2085                        self.push(*expr, env, *n);
2086                        Ok(())
2087                    }
2088                    fatal @ Split1::Fatal(_) => Err(fatal),
2089                }
2090            }
2091            ActionTree::Inline {
2092                expr,
2093                def,
2094                constant_args,
2095            } => self.inline(*expr, *def, *constant_args, env),
2096            ActionTree::Configured { expr, name: n } => {
2097                let node = &core.ir.node(*expr).expr;
2098                let (c, args): (Option<dive_ir::ConstId>, &[Arg]) = match node {
2099                    Expr::Const(c) => (Some(*c), &[]),
2100                    Expr::Apply {
2101                        callee: OpRef::Const(c),
2102                        args,
2103                    } => (Some(*c), args),
2104                    _ => (None, &[]),
2105                };
2106                let Some(c) = c else {
2107                    return Err(Split1::Fatal(EvalError::unsupported(format!(
2108                        "an instance substitution used as an action of the next-state relation ({})",
2109                        core.loc(*expr)
2110                    ))));
2111                };
2112                match core.consts.get(c.index()).and_then(Option::as_ref) {
2113                    Some(ConstBinding::Def(d)) => {
2114                        let constant = args.iter().all(|a| match a {
2115                            Arg::Expr { expr, .. } => {
2116                                core.ir.node(*expr).level == dive_ir::Level::Constant
2117                            }
2118                            Arg::Op { level, .. } => *level == dive_ir::Level::Constant,
2119                        });
2120                        let _ = n;
2121                        self.inline(*expr, *d, constant, env)
2122                    }
2123                    _ => Err(Split1::Throw(EvalError::general(format!(
2124                        "TLC cannot split the next-state relation at {}",
2125                        core.loc(*expr)
2126                    )))),
2127                }
2128            }
2129        }
2130    }
2131
2132    /// `getActionsAppl` for a user definition: inlined with its constant
2133    /// arguments evaluated, or one action named after it.
2134    fn inline(
2135        &mut self,
2136        expr: ExprId,
2137        def: DefId,
2138        constant_args: bool,
2139        env: &Env,
2140    ) -> std::result::Result<(), Split1> {
2141        let core = self.core;
2142        let name = ActionName::Def(def);
2143        if !constant_args {
2144            self.push(expr, env, name);
2145            return Ok(());
2146        }
2147        let Some(body) = self.split.defs.get(&def) else {
2148            return Err(Split1::Fatal(EvalError::bug(
2149                "inlined definition without a tree",
2150            )));
2151        };
2152        let args: Vec<Arg> = match &core.ir.node(expr).expr {
2153            Expr::Apply { args, .. } => args.to_vec(),
2154            _ => Vec::new(),
2155        };
2156        let st = St {
2157            s0: StateRef::Empty,
2158            s1: StateRef::Empty,
2159            control: control::CLEAR,
2160        };
2161        let attempt = (|| -> std::result::Result<(), Split1> {
2162            let d = core.ir.def(def);
2163            // `eval(args[i], con, TLCState.Empty)`: values, not lazy values.
2164            let mut vals = Vec::with_capacity(args.len());
2165            for a in &args {
2166                vals.push(match a {
2167                    Arg::Expr { expr, .. } => Sv::from(core.eval(&mut env.clone(), &st, *expr)?),
2168                    Arg::Op { op, .. } => Sv::op(core.op_value(env, op)?),
2169                });
2170            }
2171            let parent = match d.scope {
2172                DefScope::Local { .. } | DefScope::Inline { .. } => Some(
2173                    env.frame_at_depth(d.depth.saturating_sub(1))
2174                        .cloned()
2175                        .ok_or_else(|| Split1::Fatal(EvalError::bug("no enclosing frame")))?,
2176                ),
2177                DefScope::LetValue { .. } | DefScope::TopLevel => None,
2178            };
2179            let mut env1 = match d.scope {
2180                // A zero-arity `LET` value is evaluated in its parent's frame.
2181                DefScope::LetValue { .. } => env.clone(),
2182                _ => Env::new(def, d.depth, d.frame.len(), parent, env.dynamic.clone()),
2183            };
2184            let mut params = Vec::new();
2185            for (i, sv) in vals.into_iter().enumerate() {
2186                if let (Sv::Val(v), Some(p)) = (&sv, d.params.get(i)) {
2187                    params.push((p.name.clone(), v.clone()));
2188                }
2189                env1.bind(i, sv);
2190            }
2191            self.stack.push((def, params));
2192            let r = self.expand(body, &env1);
2193            self.stack.pop();
2194            r
2195        })();
2196        match attempt {
2197            Ok(()) => Ok(()),
2198            Err(Split1::Throw(_)) => {
2199                // `catch (Throwable e) { /*SKIP*/ }`: the actions the body
2200                // added stay, and the application is one more action.
2201                self.push(expr, env, name);
2202                Ok(())
2203            }
2204            Err(fatal) => Err(fatal),
2205        }
2206    }
2207}
2208
2209// -----------------------------------------------------------------------------
2210// ENABLED (`Tool.enabled`, `Tool.java:2953-3570`)
2211// -----------------------------------------------------------------------------
2212
2213impl Evaluator {
2214    /// Decides whether a scoped action has a successor, using TLC's existing
2215    /// ENABLED search. A subscript requests a non-stuttering successor,
2216    /// equivalent to `ENABLED <<action>>_sub`. The checker, the liveness
2217    /// checker and the trace validator all decide `ENABLED` here.
2218    ///
2219    /// ```
2220    /// use std::sync::Arc;
2221    /// use dive_eval::{Evaluator, Model, Options};
2222    /// use dive_value::Value;
2223    /// let src = "---- MODULE M ----\nVARIABLE x\nNext == x' = ~x\n====\n";
2224    /// let analysis = dive_sema::analyze_source("M.tla", src, &dive_sema::Options::default());
2225    /// let ir = Arc::new(dive_ir::lower(&analysis).expect("IR"));
2226    /// let d = ir.root_def("Next").expect("Next");
2227    /// let ev = Evaluator::new(Model::new(ir.clone()), Options::tlc()).expect("valid context");
2228    /// assert!(ev.enabled_scoped(&ev.scope(d).expect("valid scope"), ir.def(d).body, None,
2229    ///     Arc::from([Some(Value::Bool(false))])).expect("enabled"));
2230    /// ```
2231    ///
2232    /// # Errors
2233    /// Malformed current state or the existing TLC ENABLED evaluation errors.
2234    pub fn enabled_scoped(
2235        &self,
2236        scope: &Scope,
2237        action: ExprId,
2238        sub: Option<ExprId>,
2239        state: StateVals,
2240    ) -> Result<bool> {
2241        self.validate_scope(scope)?;
2242        self.admit_scoped_expr(scope, action)?;
2243        if let Some(sub) = sub {
2244            self.admit_scoped_expr(scope, sub)?;
2245        }
2246        if state.len() != self.core.ir.vars().len() || state.iter().any(Option::is_none) {
2247            return Err(EvalError::general(
2248                "ENABLED requires a complete current state",
2249            ));
2250        }
2251        let mut env = scope.env.clone();
2252        env.dynamic.branch();
2253        let acts = sub.and_then(|sub| cons(&None, Kind::Changed, sub, &env));
2254        let en = Enab {
2255            core: self.core.clone(),
2256            s0: StateRef::Vals(state),
2257        };
2258        let successor = crate::NamedState::empty(&self.core);
2259        Ok(en.enabled(action, &acts, &env, successor)?.is_some())
2260    }
2261}
2262
2263impl Core {
2264    /// `OPCODE_enabled`: whether the action has a successor from the current
2265    /// state, searched as TLC's `enabled` searches, in a branched context.
2266    pub(crate) fn eval_enabled_native(
2267        self: &Arc<Self>,
2268        env: &mut Env,
2269        st: &St,
2270        a: ExprId,
2271        _e: ExprId,
2272    ) -> Result<Ev> {
2273        let mut env1 = env.clone();
2274        env1.dynamic.branch();
2275        let s1 = crate::NamedState::empty(self);
2276        let en = Enab {
2277            core: self.clone(),
2278            s0: st.s0.clone(),
2279        };
2280        let found = en.enabled(a, &None, &env1, s1)?;
2281        Ok(Ev::V(Value::Bool(found.is_some())))
2282    }
2283}
2284
2285#[derive(Clone, Copy)]
2286enum VariableLookup {
2287    Root(bool),
2288    Enabled,
2289}
2290
2291impl VariableLookup {
2292    fn cutoff(self) -> bool {
2293        match self {
2294            Self::Root(cutoff) => cutoff,
2295            Self::Enabled => true,
2296        }
2297    }
2298}
2299
2300type EnabledState = Arc<crate::NamedState>;
2301
2302struct Enab {
2303    core: Arc<Core>,
2304    s0: StateRef,
2305}
2306
2307impl Enab {
2308    fn st(&self, s1: &EnabledState) -> St {
2309        St {
2310            s0: self.s0.clone(),
2311            s1: StateRef::Named(s1.clone()),
2312            control: control::ENABLED,
2313        }
2314    }
2315
2316    fn eval(&self, env: &Env, s1: &EnabledState, e: ExprId) -> Result<Ev> {
2317        self.core.eval(&mut env.clone(), &self.st(s1), e)
2318    }
2319
2320    fn with(&self, s1: &EnabledState, var: dive_ir::DeclId, v: Value) -> EnabledState {
2321        s1.with(&self.core.ir.decl(var).name, v)
2322    }
2323
2324    fn loc(&self, e: ExprId) -> String {
2325        self.core.loc(e)
2326    }
2327
2328    /// `enabled(acts, s0, s1)`.
2329    fn cont(&self, acts: &Acts, s1: EnabledState) -> Result<Option<EnabledState>> {
2330        let Some(item) = acts else {
2331            return Ok(Some(s1));
2332        };
2333        match item.kind {
2334            Kind::Pred => self.enabled(item.expr, &item.next, &item.env, s1),
2335            Kind::Unchanged => self.unchanged(item.expr, &item.next, &item.env, s1),
2336            Kind::Changed => {
2337                let st0 = St {
2338                    s0: self.s0.clone(),
2339                    s1: StateRef::Empty,
2340                    control: control::ENABLED,
2341                };
2342                let st1 = St {
2343                    s0: StateRef::Named(s1.clone()),
2344                    s1: StateRef::Null,
2345                    control: control::PRIMED,
2346                };
2347                let v1 = self.core.eval_v(&mut item.env.clone(), &st0, item.expr)?;
2348                let v2 = self.core.eval_v(&mut item.env.clone(), &st1, item.expr)?;
2349                if self.core.equals(&v1, &v2)? {
2350                    return Ok(None);
2351                }
2352                self.cont(&item.next, s1)
2353            }
2354        }
2355    }
2356
2357    fn after_bool(
2358        &self,
2359        v: &Ev,
2360        acts: &Acts,
2361        s1: EnabledState,
2362        e: ExprId,
2363    ) -> Result<Option<EnabledState>> {
2364        match v {
2365            Ev::V(Value::Bool(true)) => self.cont(acts, s1),
2366            Ev::V(Value::Bool(false)) => Ok(None),
2367            other => Err(EvalError::coded(
2368                Ec::ExpectedExpressionInComputing,
2369                format!(
2370                    "In computing ENABLED, TLC expected a boolean expression,\nbut instead found {}.\n{}",
2371                    self.core.ev_string(other),
2372                    self.loc(e)
2373                ),
2374            )),
2375        }
2376    }
2377
2378    fn wrong(&self, what: &str, e: ExprId) -> EvalError {
2379        EvalError::coded(
2380            Ec::EnabledWrongFormula,
2381            format!(
2382                "In computing ENABLED, TLC encountered a temporal formula ({what}).\n{}",
2383                self.loc(e)
2384            ),
2385        )
2386    }
2387
2388    /// `enabled(pred, acts, c, s0, s1)`.
2389    fn enabled(
2390        &self,
2391        e: ExprId,
2392        acts: &Acts,
2393        env: &Env,
2394        s1: EnabledState,
2395    ) -> Result<Option<EnabledState>> {
2396        let core = &self.core;
2397        let _g = core.enter(e)?;
2398        match &core.ir.node(e).expr {
2399            Expr::Let { defs, body } => {
2400                let env1 = core.bind_let(env, defs, true);
2401                self.enabled(*body, acts, &env1, s1)
2402            }
2403            Expr::Subst { bindings, body } => {
2404                let env1 = core.bind_subst(env, &self.st(&s1), bindings, false)?;
2405                self.enabled(*body, acts, &env1, s1)
2406            }
2407            Expr::Label { body, .. } | Expr::Selected(body) => self.enabled(*body, acts, env, s1),
2408            Expr::Def(_)
2409            | Expr::Apply { .. }
2410            | Expr::Local(_)
2411            | Expr::Const(_)
2412            | Expr::SubstRef { primed: false, .. } => {
2413                match core.op_target(env, &self.st(&s1), e)? {
2414                    OpTarget::Body(env1, body) => self.enabled(body, acts, &env1, s1),
2415                    OpTarget::Thunk(t) => self.enabled(t.expr, acts, &t.env, s1),
2416                    OpTarget::Value(v) => self.after_bool(&v, acts, s1, e),
2417                }
2418            }
2419            Expr::StepAngle { action, sub } => {
2420                let acts1 = cons(acts, Kind::Changed, *sub, env);
2421                self.enabled(*action, &acts1, env, s1)
2422            }
2423            Expr::Quant {
2424                kind: QuantKind::Exists,
2425                bounds,
2426                body,
2427            } if bounds.iter().all(|b| b.domain.is_some()) => {
2428                let st = self.st(&s1);
2429                let mut found = None;
2430                let mut err = None;
2431                core.for_each_context(&mut env.clone(), &st, bounds, e, &mut |_, env1| match self
2432                    .enabled(*body, acts, env1, s1.clone())
2433                {
2434                    Ok(Some(s)) => {
2435                        found = Some(s);
2436                        Ok(false)
2437                    }
2438                    Ok(None) => Ok(true),
2439                    Err(x) => {
2440                        err = Some(x);
2441                        Ok(false)
2442                    }
2443                })?;
2444                match err {
2445                    Some(x) => Err(x),
2446                    None => Ok(found),
2447                }
2448            }
2449            Expr::Quant {
2450                kind: QuantKind::Forall,
2451                bounds,
2452                body,
2453            } if bounds.iter().all(|b| b.domain.is_some()) => {
2454                let st = self.st(&s1);
2455                let mut envs: Vec<Env> = Vec::new();
2456                core.for_each_context(&mut env.clone(), &st, bounds, e, &mut |_, env1| {
2457                    envs.push(env1.clone());
2458                    Ok(true)
2459                })?;
2460                let Some((first, rest)) = envs.split_first() else {
2461                    return self.cont(acts, s1);
2462                };
2463                let mut acts1 = acts.clone();
2464                for c2 in rest {
2465                    acts1 = cons(&acts1, Kind::Pred, *body, c2);
2466                }
2467                self.enabled(*body, &acts1, first, s1)
2468            }
2469            Expr::Quant { kind, .. } => Err(EvalError::general(match kind {
2470                QuantKind::Choose => format!(
2471                    "In computing ENABLED, TLC encountered unbounded CHOOSE. Make sure that the expression is of form CHOOSE x \\in S: P(x).\n{}",
2472                    self.loc(e)
2473                ),
2474                QuantKind::Exists => format!(
2475                    "In computing ENABLED, TLC encountered unbounded quantifier. Make sure that the expression is of form \\E x \\in S: P(x).\n{}",
2476                    self.loc(e)
2477                ),
2478                QuantKind::Forall => format!(
2479                    "In computing ENABLED, TLC encountered unbounded quantifier. Make sure that the expression is of form \\A x \\in S: P(x).\n{}",
2480                    self.loc(e)
2481                ),
2482            })),
2483            Expr::Case { arms, other } => {
2484                for arm in arms {
2485                    match self.eval(env, &s1, arm.guard)? {
2486                        Ev::V(Value::Bool(true)) => return self.enabled(arm.value, acts, env, s1),
2487                        Ev::V(Value::Bool(false)) => {}
2488                        other => {
2489                            return Err(EvalError::general(format!(
2490                                "In computing ENABLED, a non-boolean expression({}) was used as a guard condition of a CASE.\n{}",
2491                                core.kind_of(&other),
2492                                self.loc(arm.value)
2493                            )));
2494                        }
2495                    }
2496                }
2497                match other {
2498                    Some(o) => self.enabled(*o, acts, env, s1),
2499                    None => Err(EvalError::general(format!(
2500                        "In computing ENABLED, TLC encountered a CASE with no conditions true.\n{}",
2501                        self.loc(e)
2502                    ))),
2503                }
2504            }
2505            Expr::Junction { kind, items, .. } => match kind {
2506                JunctionKind::And => {
2507                    let mut acts1 = acts.clone();
2508                    for &i in items.iter().skip(1).rev() {
2509                        acts1 = cons(&acts1, Kind::Pred, i, env);
2510                    }
2511                    match items.first() {
2512                        Some(&f) => self.enabled(f, &acts1, env, s1),
2513                        None => self.cont(acts, s1),
2514                    }
2515                }
2516                JunctionKind::Or => {
2517                    for &i in items {
2518                        if let Some(s) = self.enabled(i, acts, env, s1.clone())? {
2519                            return Ok(Some(s));
2520                        }
2521                    }
2522                    Ok(None)
2523                }
2524            },
2525            Expr::FcnApply { fcn, arg } => {
2526                let st = St {
2527                    control: control::ENABLED | control::KEEP_LAZY,
2528                    ..self.st(&s1)
2529                };
2530                let f = core.eval(&mut env.clone(), &st, *fcn)?;
2531                let fv = match f {
2532                    Ev::F(lf) => {
2533                        if let Some(v) = lf.materialized.get(core.host.cache_domain()) {
2534                            v
2535                        } else {
2536                            let a = core.force_fcn(self.eval(env, &s1, *arg)?)?;
2537                            let env1 = core.fcn_context(&lf, &a, e)?;
2538                            return self.enabled(lf.body, acts, &env1, s1);
2539                        }
2540                    }
2541                    Ev::V(v) => v,
2542                };
2543                let Value::Fcn(fv) = fv else {
2544                    return Err(EvalError::general(format!(
2545                        "In computing ENABLED, a non-function ({}) was applied as a function.\n{}",
2546                        crate::core::kind_string(&fv),
2547                        self.loc(e)
2548                    )));
2549                };
2550                let a = core.force_fcn(self.eval(env, &s1, *arg)?)?;
2551                match core.apply_fcn(&fv, &a)? {
2552                    Value::Bool(true) => self.cont(acts, s1),
2553                    Value::Bool(false) => Ok(None),
2554                    _ => Err(EvalError::coded(
2555                        Ec::ExpectedExpressionInComputing2,
2556                        format!(
2557                            "In computing ENABLED, TLC expected a boolean expression,\nbut didn't find one.\n{}",
2558                            self.loc(e)
2559                        ),
2560                    )),
2561                }
2562            }
2563            Expr::If { cond, then, other } => match self.eval(env, &s1, *cond)? {
2564                Ev::V(Value::Bool(b)) => {
2565                    self.enabled(if b { *then } else { *other }, acts, env, s1)
2566                }
2567                other => Err(EvalError::general(format!(
2568                    "In computing ENABLED, a non-boolean expression({}) was used as the guard condition of an IF.\n{}",
2569                    core.kind_of(&other),
2570                    self.loc(e)
2571                ))),
2572            },
2573            Expr::StepBox { action, sub } => {
2574                if let Some(s) = self.enabled(*action, acts, env, s1.clone())? {
2575                    return Ok(Some(s));
2576                }
2577                self.unchanged(*sub, acts, env, s1)
2578            }
2579            Expr::TemporalQuant { .. } => Err(EvalError::general(format!(
2580                "In computing ENABLED, TLC encountered temporal quantifier.\n{}",
2581                self.loc(e)
2582            ))),
2583            Expr::Sf { .. } => Err(self.wrong("SF", e)),
2584            Expr::Wf { .. } => Err(self.wrong("WF", e)),
2585            Expr::Always(_) => Err(self.wrong("[]", e)),
2586            Expr::Eventually(_) => Err(self.wrong("<>", e)),
2587            Expr::LeadsTo(..) => Err(EvalError::general(format!(
2588                "In computing ENABLED, TLC encountered a temporal formula (a ~> b).\n{}",
2589                self.loc(e)
2590            ))),
2591            Expr::WhilePlus(..) => Err(EvalError::general(format!(
2592                "In computing ENABLED, TLC encountered a temporal formula (a -+-> formula).\n{}",
2593                self.loc(e)
2594            ))),
2595            Expr::Unchanged(a) => self.unchanged(*a, acts, env, s1),
2596            Expr::Implies(a, b) => match self.eval(env, &s1, *a)? {
2597                Ev::V(Value::Bool(true)) => self.enabled(*b, acts, env, s1),
2598                Ev::V(Value::Bool(false)) => self.cont(acts, s1),
2599                other => Err(EvalError::general(format!(
2600                    "While computing ENABLED of an expression of the form P => Q, P was {}.\n{}",
2601                    core.kind_of(&other),
2602                    self.loc(e)
2603                ))),
2604            },
2605            Expr::Cdot(a, b) => self.cdot(*a, *b, acts, env, &s1, e),
2606            Expr::Builtin {
2607                op: op @ (BuiltinOp::Eq | BuiltinOp::In | BuiltinOp::Subseteq),
2608                args,
2609            } if args.len() == 2 => self.assign(*op, args[0], args[1], e, acts, env, s1),
2610            _ => {
2611                let v = self.eval(env, &s1, e)?;
2612                self.after_bool(&v, acts, s1, e)
2613            }
2614        }
2615    }
2616
2617    fn bind_value(
2618        &self,
2619        var: dive_ir::DeclId,
2620        value: Value,
2621        acts: &Acts,
2622        s1: &EnabledState,
2623    ) -> Result<Option<EnabledState>> {
2624        // Rejected query candidates are work even when no witness is found.
2625        self.core.loop_work()?;
2626        self.cont(acts, self.with(s1, var, value))
2627    }
2628
2629    fn bind_interval(
2630        &self,
2631        var: dive_ir::DeclId,
2632        lo: &dive_value::Int,
2633        hi: &dive_value::Int,
2634        acts: &Acts,
2635        s1: &EnabledState,
2636    ) -> Result<Option<EnabledState>> {
2637        // IntervalValue.elements() is incremental and ascending, as in the
2638        // ordinary assignment path. ENABLED stops at its first witness.
2639        if let (Some(lo), Some(hi)) = (lo.to_i64(), hi.to_i64()) {
2640            for value in lo..=hi {
2641                if let Some(found) = self.bind_value(var, Value::Int(value), acts, s1)? {
2642                    return Ok(Some(found));
2643                }
2644            }
2645        } else {
2646            let mut value = lo.clone();
2647            while value <= *hi {
2648                if let Some(found) = self.bind_value(var, Value::int(value.clone()), acts, s1)? {
2649                    return Ok(Some(found));
2650                }
2651                if value == *hi {
2652                    break;
2653                }
2654                value = value.add(&dive_value::Int::ONE, dive_value::IntMode::Big)?;
2655            }
2656        }
2657        Ok(None)
2658    }
2659
2660    fn assign(
2661        &self,
2662        op: BuiltinOp,
2663        lhs: ExprId,
2664        rhs: ExprId,
2665        e: ExprId,
2666        acts: &Acts,
2667        env: &Env,
2668        s1: EnabledState,
2669    ) -> Result<Option<EnabledState>> {
2670        let core = &self.core;
2671        let Some(var) = core.var_lookup(env, lhs, VariableLookup::Enabled, true, 0)? else {
2672            return match self.eval(env, &s1, e)? {
2673                Ev::V(Value::Bool(true)) => self.cont(acts, s1),
2674                Ev::V(Value::Bool(false)) => Ok(None),
2675                _ => Err(EvalError::bug("=, \\in or \\subseteq not boolean")),
2676            };
2677        };
2678        let lval = s1.get(&core.ir.decl(var).name).cloned();
2679        match op {
2680            BuiltinOp::Eq => {
2681                let rval = core.embed(self.eval(env, &s1, rhs)?)?;
2682                match lval {
2683                    None => {
2684                        let s2 = s1.with_owned(&core.ir.decl(var).name, rval);
2685                        self.cont(acts, s2)
2686                    }
2687                    Some(l) => {
2688                        if core.equals(&l, &rval)? {
2689                            self.cont(acts, s1)
2690                        } else {
2691                            Ok(None)
2692                        }
2693                    }
2694                }
2695            }
2696            BuiltinOp::In => {
2697                let rval = core.force_fcn(self.eval(env, &s1, rhs)?)?;
2698                match lval {
2699                    None => {
2700                        let elems = match &rval {
2701                            Value::Set(set) if is_enumerable(&rval) => {
2702                                if let Some((lo, hi)) = set.as_interval() {
2703                                    return self.bind_interval(var, lo, hi, acts, &s1);
2704                                }
2705                                if let Some(elements) = core.in_element_stream(set)? {
2706                                    for value in elements.with_owner(rval) {
2707                                        let value = value?;
2708                                        if let Some(found) =
2709                                            self.bind_value(var, value, acts, &s1)?
2710                                        {
2711                                            return Ok(Some(found));
2712                                        }
2713                                    }
2714                                    return Ok(None);
2715                                }
2716                                core.in_elements(set)?
2717                            }
2718                            _ => {
2719                                return Err(EvalError::general(format!(
2720                                    "The right side of \\IN is not enumerable.\n{}",
2721                                    self.loc(e)
2722                                )));
2723                            }
2724                        };
2725                        for x in elems.iter() {
2726                            if let Some(s) = self.bind_value(var, x.clone(), acts, &s1)? {
2727                                return Ok(Some(s));
2728                            }
2729                        }
2730                        Ok(None)
2731                    }
2732                    Some(l) => {
2733                        if core.member(&l, &rval)? {
2734                            self.cont(acts, s1)
2735                        } else {
2736                            Ok(None)
2737                        }
2738                    }
2739                }
2740            }
2741            _ => {
2742                let rset = core.force_fcn(self.eval(env, &s1, rhs)?)?;
2743                if !matches!(rset, Value::Set(_)) {
2744                    return Err(EvalError::unsupported(format!(
2745                        "x' \\subseteq S where S is not a set ({})",
2746                        self.loc(e)
2747                    )));
2748                }
2749                let rval = Value::subset(rset, core.ctx);
2750                match lval {
2751                    None => {
2752                        let Value::Set(s) = &rval else {
2753                            return Err(EvalError::bug("SUBSET is not a set"));
2754                        };
2755                        for x in core.explore(s)?.iter() {
2756                            let s2 = self.with(&s1, var, x.clone());
2757                            if let Some(s) = self.cont(acts, s2)? {
2758                                return Ok(Some(s));
2759                            }
2760                        }
2761                        Ok(None)
2762                    }
2763                    Some(l) => {
2764                        if core.member(&l, &rval)? {
2765                            self.cont(acts, s1)
2766                        } else {
2767                            Ok(None)
2768                        }
2769                    }
2770                }
2771            }
2772        }
2773    }
2774
2775    /// `enabledUnchanged` (`Tool.java:3506-3570`).
2776    fn unchanged(
2777        &self,
2778        e: ExprId,
2779        acts: &Acts,
2780        env: &Env,
2781        s1: EnabledState,
2782    ) -> Result<Option<EnabledState>> {
2783        let core = &self.core;
2784        let _g = core.enter(e)?;
2785        if let Some(var) = core.var_lookup(env, e, VariableLookup::Enabled, false, 0)? {
2786            let v0 = core.force_fcn(self.eval(env, &s1, e)?)?;
2787            return match s1.get(&core.ir.decl(var).name).cloned() {
2788                None => {
2789                    let s2 = s1.with_owned(&core.ir.decl(var).name, v0);
2790                    self.cont(acts, s2)
2791                }
2792                Some(v1) => {
2793                    if core.equals(&v1, &v0)? {
2794                        self.cont(acts, s1)
2795                    } else {
2796                        core.unchanged_named_warning(&core.ir.decl(var).name, e);
2797                        Ok(None)
2798                    }
2799                }
2800            };
2801        }
2802        match &core.ir.node(e).expr {
2803            Expr::Tuple(items) => {
2804                let Some((&first, rest)) = items.split_first() else {
2805                    return self.cont(acts, s1);
2806                };
2807                // `for (int i = 1; i < alen; i++) acts1 = acts1.cons(args[i])`:
2808                // the last item is checked right after the first.
2809                let mut acts1 = acts.clone();
2810                for &i in rest {
2811                    acts1 = cons(&acts1, Kind::Unchanged, i, env);
2812                }
2813                self.unchanged(first, &acts1, env, s1)
2814            }
2815            Expr::Def(_)
2816            | Expr::Local(_)
2817            | Expr::Const(_)
2818            | Expr::SubstRef { primed: false, .. } => {
2819                match core.zero_arity_target(env, e)? {
2820                    Target::Body(env1, body) => self.unchanged(body, acts, &env1, s1),
2821                    // Any other value of a zero-arity name is unchanged.
2822                    Target::Value => self.cont(acts, s1),
2823                }
2824            }
2825            _ => {
2826                let st0 = St {
2827                    s0: self.s0.clone(),
2828                    s1: StateRef::Empty,
2829                    control: control::ENABLED,
2830                };
2831                let st1 = St {
2832                    s0: StateRef::Named(s1.clone()),
2833                    s1: StateRef::Empty,
2834                    control: control::PRIMED,
2835                };
2836                let v0 = core.eval_v(&mut env.clone(), &st0, e)?;
2837                let v1 = core.eval_v(&mut env.clone(), &st1, e)?;
2838                if core.equals(&v0, &v1)? {
2839                    self.cont(acts, s1)
2840                } else {
2841                    Ok(None)
2842                }
2843            }
2844        }
2845    }
2846}