Skip to main content

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}