dive_eval/recursive_leaf.rs
1//! State-level recursive operators, which temporal planning and validation
2//! treat as evaluation leaves, as TLC does.
3//!
4//! Temporal planning and the trace validator inline every non-recursive
5//! operator they meet, so that the temporal structure and each binder of a
6//! temporal atom is seen before evaluation. A `RECURSIVE` operator cannot be
7//! inlined: its unfolding depends on the actual arguments. TLC does not expand
8//! a call of a `RECURSIVE` operator whose level is at most `ActionLevel`; it
9//! leaves the call to `Tool.eval`, which handles the recursion
10//! (`Liveness.astToLive`, `Liveness.java:196-245` at the pinned oracle).
11//!
12//! dive admits the state-level part of that rule: a top-level `RECURSIVE`
13//! operator whose body, together with every definition it reaches, is at most
14//! state level and contains no operator argument, `ENABLED`, dynamic
15//! substitution or effect.
16//! State-level binders, `LET` and recursive functions are ordinary values of
17//! that body. Admission uses semantic levels and effects, not expression shape.
18//! Its arguments are still analysed in the caller's context; the
19//! call itself is a leaf that the core evaluator computes. Action-level
20//! recursive operators keep the named refusal.
21
22use std::collections::BTreeSet;
23
24use dive_ir::{Arg, DefId, DefScope, Effects, Expr, ExprId, Level, OpRef};
25
26use crate::{ConstBinding, Evaluator};
27
28impl Evaluator {
29 /// Whether a call of `def`, a top-level `RECURSIVE` operator, is a pure
30 /// state-level evaluation leaf: its body and every definition it reaches
31 /// are at most state level, with no operator argument, `ENABLED`,
32 /// dynamic substitution or effect. Value-bound constants are supported;
33 /// configured operator bindings and overrides retain their refusal. `false`
34 /// for anything else, including a non-recursive or
35 /// overridden definition.
36 ///
37 /// ```
38 /// use std::sync::Arc;
39 /// use dive_eval::{Evaluator, Model, Options};
40 /// let source = "---- MODULE M ----\nEXTENDS Naturals, Sequences\nVARIABLE v\n\
41 /// RECURSIVE Sum(_)\nSum(q) == IF q = <<>> THEN 0 ELSE Head(q) + Sum(Tail(q))\n\
42 /// RECURSIVE Any(_)\nAny(q) == IF q = <<>> THEN FALSE ELSE \\E x \\in {Head(q)} : x > 0 \\/ Any(Tail(q))\n\
43 /// RECURSIVE Next(_)\nNext(q) == IF q = <<>> THEN v' = v ELSE Next(Tail(q))\n====\n";
44 /// let analysis = dive_sema::analyze_source("M.tla", source, &dive_sema::Options::default());
45 /// let ir = dive_ir::lower(&analysis).expect("IR");
46 /// let (sum, any, next) = (
47 /// ir.root_def("Sum").expect("Sum"),
48 /// ir.root_def("Any").expect("Any"),
49 /// ir.root_def("Next").expect("Next"),
50 /// );
51 /// let evaluator = Evaluator::new(Model::new(Arc::new(ir)), Options::tlc()).expect("context");
52 /// assert!(evaluator.recursive_leaf(sum));
53 /// assert!(evaluator.recursive_leaf(any));
54 /// assert!(!evaluator.recursive_leaf(next));
55 /// ```
56 #[must_use]
57 pub fn recursive_leaf(&self, def: DefId) -> bool {
58 // Both definition and expression edges use a work list: cyclic
59 // recursion and long acyclic helper chains cannot consume Rust stack.
60 enum Work {
61 Definition(DefId),
62 Expression(ExprId),
63 }
64 let ir = self.ir();
65 let Some(info) = ir.defs().get(def.index()) else {
66 return false;
67 };
68 if !info.recursive || info.scope != DefScope::TopLevel || info.std.is_some() {
69 return false;
70 }
71 let mut seen_defs = BTreeSet::new();
72 let mut seen_exprs = BTreeSet::new();
73 let mut todo = vec![Work::Definition(def)];
74 while let Some(work) = todo.pop() {
75 let expr = match work {
76 Work::Definition(def) => {
77 if !seen_defs.insert(def) {
78 continue;
79 }
80 let Some(info) = ir.defs().get(def.index()) else {
81 return false;
82 };
83 if self.is_value_override(def) || self.redirected(def) != def {
84 return false;
85 }
86 // Native definitions use their evaluator implementation,
87 // not the TLA+ body retained for documentation.
88 if let Some(op) = info.std {
89 if !pure_native(op) {
90 return false;
91 }
92 continue;
93 }
94 if info.level > Level::State
95 || info.params.iter().any(|p| p.arity != 0)
96 || info
97 .effects
98 .intersects(Effects::IMPURE | Effects::TEMPORAL | Effects::USES_ENABLED)
99 {
100 return false;
101 }
102 info.body
103 }
104 Work::Expression(expr) => expr,
105 };
106 if !seen_exprs.insert(expr) {
107 continue;
108 }
109 let Some(node) = ir.nodes().get(expr.index()) else {
110 return false;
111 };
112 if node.level > Level::State
113 || node
114 .effects
115 .intersects(Effects::IMPURE | Effects::TEMPORAL | Effects::USES_ENABLED)
116 {
117 return false;
118 }
119 match &node.expr {
120 Expr::Const(constant) => {
121 if !matches!(
122 self.constant_binding(*constant),
123 Some(ConstBinding::Value(_))
124 ) {
125 return false;
126 }
127 }
128 Expr::Def(def) => todo.push(Work::Definition(*def)),
129 Expr::Apply { callee, args } => {
130 if args.iter().any(|arg| matches!(arg, Arg::Op { .. })) {
131 return false;
132 }
133 match callee {
134 OpRef::Def(def) => todo.push(Work::Definition(*def)),
135 OpRef::Std(op) if pure_native(*op) => {}
136 _ => return false,
137 }
138 }
139 Expr::Let { defs, .. } => {
140 // Inspect even unused local definitions. Their lexical
141 // scope is part of this closed body's proof.
142 todo.extend(defs.iter().copied().map(Work::Definition));
143 }
144 // A substituted declaration can obtain a different level or
145 // effect from its dynamic context. Static metadata cannot
146 // establish the leaf proof for that context.
147 Expr::Subst { .. } | Expr::SubstRef { .. } => return false,
148 // Other expressions use the core evaluator unchanged. Their
149 // semantic level/effects and all children are checked above
150 // and below, including binders and lazy function bodies.
151 _ => {}
152 }
153 node.expr
154 .for_each_child(|child| todo.push(Work::Expression(child)));
155 }
156 true
157 }
158}
159
160/// A standard-module operator that computes a value only: no effect, I/O or
161/// checker introspection.
162fn pure_native(op: dive_ir::StdOp) -> bool {
163 !op.impure()
164 && !matches!(
165 op.support(),
166 dive_ir::StdSupport::Io | dive_ir::StdSupport::Introspection
167 )
168}