Skip to main content

Module next

Module next 

Source
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:

ConstructRule (Java)
A /\ B /\ CA with the continuation B, C consed in order (:1176-1183)
A \/ Beach disjunct with the same continuation, left to right (:1184-1207)
\E x \in S, y \in T : Aone enumeration of A per binding, normalized, first variable fastest (ContextEnumerator, :1208-1229; probes ExistsOrder, ExistsSetOrder)
\A x \in S : Athe first binding’s A, with the other bindings consed onto the continuation, last first (:1230-1246)
x' = ebinds x' if unassigned, otherwise checks equality (:1353-1378)
x' \in Sbinds 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 Sthe same over SUBSET S (:1379-1421)
UNCHANGED ea variable, a tuple (items consed), a zero-arity definition or argument (followed), anything else compared (processUnchanged, :1551-1661)
[A]_eA, then the UNCHANGED e successor (:1284-1295; probe StutterInNext)
<A>_eA 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!1transparent; substitutions are bound as uncached lazy values (:960-990)
user operatorits 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 elseevaluated 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.
NextError
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 Context of 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§

StateVals
A state’s variable values by dive_ir::VarId, None where unassigned.