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