Expand description
The successor generator: ports of TLC’s Tool.getInitStates,
Tool.getNextStates, processUnchanged, enabled and getActions
(tlc2/tool/impl/Tool.java, ported from tlaplus at 94d0c50), rule by
rule.
What it reproduces. For each state and action, the exact sequence of
successors TLC’s enumerator hands to its functor, duplicates included,
since “states generated” counts every one (probe DuplicateSuccessors).
The enumeration works in continuation-passing style over an explicit
continuation list, TLC’s ActionItemList, with one successor buffer that
is bound and unbound as TLC binds and unbinds its TLCStateMut:
| Construct | Rule (Java) |
|---|---|
A /\ B /\ C | A with the continuation B, C consed in order (:1176-1183) |
A \/ B | each disjunct with the same continuation, left to right (:1184-1207) |
\E x \in S, y \in T : A | one enumeration of A per binding, normalized, first variable fastest (ContextEnumerator, :1208-1229; probes ExistsOrder, ExistsSetOrder) |
\A x \in S : A | the first binding’s A, with the other bindings consed onto the continuation, last first (:1230-1246) |
x' = e | binds x' if unassigned, otherwise checks equality (:1353-1378) |
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) |
x' \subseteq S | the same over SUBSET S (:1379-1421) |
UNCHANGED e | a variable, a tuple (items consed), a zero-arity definition or argument (followed), anything else compared (processUnchanged, :1551-1661) |
[A]_e | A, then the UNCHANGED e successor (:1284-1295; probe StutterInNext) |
<A>_e | A with a CHANGED e check consed (:1279-1283) |
IF, CASE, => | guard evaluated, then the chosen branch (:1296-1352, :1469-1482) |
LET, labels, INSTANCE substitutions, Op!1 | transparent; substitutions are bound as uncached lazy values (:960-990) |
| user operator | its body, its arguments bound lazily; an argument naming an action is followed (LazyValue, :1112-1158) |
f[a] | the body of a lazy function, or the function’s boolean value (:1247-1278) |
| anything else | evaluated as a boolean (:1536-1546) |
Once every variable of the successor is assigned, the rest of the
continuation is evaluated as booleans instead (getNextStatesAllAssigned,
:1036-1082), unless warnings are off (crate::Options::warnings).
Initial states follow getInitStates (:427-890), which has the same
rules over unprimed variables, its own error texts and an unconditional
all-assigned path.
What it does not do. It never deduplicates, filters or reorders: the
checker counts, constrains and stores. A successor that leaves a
variable unassigned is still emitted (Successor::complete); TLC reports
it in its functor (TLC_STATE_NOT_COMPLETELY_SPECIFIED_NEXT).
§Driving it
A checker gets the initial predicates and the split actions from
the binding stage (Evaluator::init_predicate, Evaluator::actions,
or Evaluator::scope and its relatives for formulas found inside
definitions and instances), generates the initial states, then expands
each state with Evaluator::successors. Every state handed to the sink
counts as generated. Run it on a thread with
crate::RECOMMENDED_STACK.
use std::sync::Arc;
use dive_eval::next::{Flow, StateVals};
use dive_eval::{Evaluator, Model, Options};
use dive_ir::actions::{ActionName, split};
use dive_sema::{Options as SemaOptions, analyze_source};
let src = "---- MODULE M ----\nEXTENDS Naturals\nVARIABLE x\n\
Init == x \\in {0, 1}\nNext == x' = x + 1 \\/ x' = x + 1\n====\n";
let ir = dive_ir::lower(&analyze_source("M.tla", src, &SemaOptions::default())).expect("lowers");
let ir = Arc::new(ir);
let (init, next) = (ir.root_def("Init").expect("Init"), ir.root_def("Next").expect("Next"));
let ev = Evaluator::new(Model::new(ir.clone()), Options::tlc()).expect("valid context");
let inits = vec![ev.init_predicate(init, 0).expect("no arguments")];
let tree = split(&ir, ir.def(next).body, ActionName::Def(next), next, &Default::default());
let actions = ev.actions(&tree, next, inits.len()).expect("splits");
assert_eq!(actions.len(), 2);
let mut states: Vec<StateVals> = Vec::new();
ev.init_states(&inits, &mut |s| {
states.push(s.state.into());
Flow::Continue
})
.expect("initial states");
assert_eq!(states.len(), 2);
// Both disjuncts generate x = 1 from x = 0: two successors, one state.
let mut generated = 0;
ev.successors(&actions, &states[0], &mut |s| {
assert_eq!(s.ordinal, generated);
generated += 1;
Flow::Continue
})
.expect("successors");
assert_eq!(generated, 2);Structs§
- Action
- One initial predicate or next-state action with its context (TLC’s
Action): an expression, the bindings it is evaluated under, its name and its label. - Next
Error - An error that ended an enumeration, with the number of states already
handed to the sink (they count as generated, probe
EvalErrorMidLevel). - Outcome
- How an enumeration ended without an error.
- Scope
- TLC’s
Contextof a role (see the module documentation). Cheap to clone. - Successor
- A successor or initial state handed to the sink.
Enums§
- Flow
- Whether to go on enumerating after a successor or initial state.
Type Aliases§
- State
Vals - A state’s variable values by
dive_ir::VarId,Nonewhere unassigned.