Skip to main content

dive_model/
level.rs

1//! TLC's level bound (`SymbolNodeValueLookupProvider.getLevelBound` and
2//! `getLevelBoundAppl`, tlaplus `94d0c50`).
3//!
4//! TLC does not use SANY's levels when it binds a model: it computes an upper
5//! bound of an expression's level itself, after the configuration has been
6//! applied, and decides with it which constant definitions to evaluate at
7//! start-up, which conjuncts of a `SPECIFICATION` are initial predicates and
8//! how a `PROPERTY` splits. The bound differs from SANY's level:
9//!
10//! - a constant the configuration assigns a value has level 0, one it binds to
11//!   a definition (`C <- D`) has `D`'s level;
12//! - a definition TLC has already replaced by a value (start-up evaluation,
13//!   `Op = v`) has level 0, a Java override its annotation's `minLevel`;
14//! - any operator, parameter or bound variable whose *name* is the name of a
15//!   root state variable has level 1 (`opName.getVarLoc() >= 0`);
16//! - primes, `UNCHANGED`, `[A]_v`, `<<A>>_v` and `\cdot` are 2, temporal
17//!   operators 3 and `ENABLED` 1, without looking inside;
18//! - an operator's parameters are not bound when TLC looks into its body,
19//!   so a parameter there has level 0 unless the context binds it.
20
21use std::collections::HashSet;
22
23use dive_eval::{Scope, SlotView};
24use dive_ir::{
25    Arg, BuiltinOp, DeclId, DefId, DefScope, Expr, ExprId, LocalRef, OpRef, SlotKind, StdOp,
26};
27
28use crate::tables::{Look, Tables};
29
30/// A substitution in the level context: `decl` is bound to `expr`,
31/// evaluated in `scope` with the substitutions `outer`.
32#[derive(Clone)]
33struct SubstLevel {
34    decl: DeclId,
35    expr: Option<(ExprId, Scope)>,
36    outer: Vec<SubstLevel>,
37}
38
39/// The state of one level computation.
40pub(crate) struct LevelCx<'a> {
41    pub(crate) t: &'a Tables,
42    /// Definitions bound to `ValOne` in TLC's context (recursion guard,
43    /// `LET` definitions).
44    marks: HashSet<DefId>,
45    substs: Vec<SubstLevel>,
46    depth: u32,
47    error: Option<dive_eval::EvalError>,
48}
49
50impl<'a> LevelCx<'a> {
51    pub(crate) fn new(t: &'a Tables) -> Self {
52        Self {
53            t,
54            marks: HashSet::new(),
55            substs: Vec::new(),
56            depth: 0,
57            error: None,
58        }
59    }
60
61    pub(crate) fn try_level(&mut self, e: ExprId, scope: &Scope) -> crate::bind::R<u8> {
62        self.t.ev().validate_scope(scope).map_err(|e| {
63            self.t
64                .eval_error(e, |e| crate::BindError::unsupported(e.to_string()))
65        })?;
66        let level = self.level(e, scope);
67        if let Some(e) = self.error.take() {
68            Err(self
69                .t
70                .eval_error(e, |e| crate::BindError::unsupported(e.to_string())))
71        } else {
72            Ok(level)
73        }
74    }
75
76    /// `getLevelBound(expr, c)` where `c` is what `scope` binds.
77    fn level(&mut self, e: ExprId, scope: &Scope) -> u8 {
78        if self
79            .error
80            .as_ref()
81            .is_some_and(|error| self.t.is_exception(error))
82        {
83            return 0;
84        }
85        // Deep recursion only through pathological definitions; TLC would
86        // overflow its stack. Treat the rest as level 0, conservatively the
87        // bound TLC computes for what it cannot look into.
88        if self.depth > 2_000 {
89            return 0;
90        }
91        self.depth += 1;
92        let l = self.level_inner(e, scope);
93        self.depth -= 1;
94        l
95    }
96
97    #[allow(clippy::too_many_lines, reason = "one arm per node kind")]
98    fn level_inner(&mut self, e: ExprId, scope: &Scope) -> u8 {
99        let ir = &*self.t.ir;
100        match ir.expr(e) {
101            Expr::Bool(_)
102            | Expr::Num(_)
103            | Expr::Decimal { .. }
104            | Expr::Str(_)
105            | Expr::ExceptAt
106            | Expr::Unbound(_)
107            | Expr::Unevaluable(_) => 0,
108            Expr::Var { primed, .. } => {
109                if *primed {
110                    2
111                } else {
112                    1
113                }
114            }
115            Expr::Const(c) => {
116                let decl = ir.consts()[c.index()];
117                self.decl_level(decl, scope)
118            }
119            Expr::SubstRef { decl, primed } => {
120                if *primed {
121                    return 2;
122                }
123                self.decl_level(*decl, scope)
124            }
125            Expr::Local(r) => self.local_level(*r, scope),
126            Expr::Def(d) => self.def_level(*d, scope),
127            Expr::Apply { callee, args } => {
128                let mut l = 0;
129                for a in args {
130                    if let Arg::Expr { expr, .. } = a {
131                        l = l.max(self.level(*expr, scope));
132                    }
133                }
134                l.max(self.callee_level(callee, scope))
135            }
136            Expr::Builtin { op, args } => match op {
137                BuiltinOp::Prime | BuiltinOp::Unchanged | BuiltinOp::Cdot => 2,
138                BuiltinOp::Always
139                | BuiltinOp::Eventually
140                | BuiltinOp::LeadsTo
141                | BuiltinOp::WhilePlus => 3,
142                BuiltinOp::Enabled => 1,
143                _ => self.max_of(args, scope),
144            },
145            Expr::Prime(_)
146            | Expr::Unchanged(_)
147            | Expr::StepBox { .. }
148            | Expr::StepAngle { .. }
149            | Expr::Cdot(..) => 2,
150            Expr::Enabled(_) => 1,
151            Expr::Always(_)
152            | Expr::Eventually(_)
153            | Expr::LeadsTo(..)
154            | Expr::WhilePlus(..)
155            | Expr::Wf { .. }
156            | Expr::Sf { .. }
157            | Expr::TemporalQuant { .. } => 3,
158            Expr::Let { defs, body } => {
159                // `LetInKind`: each definition's body, then the body, with the
160                // definitions marked (`c1.cons(opDef, ValOne)`).
161                let mut l = 0;
162                let mut marked = Vec::new();
163                for &d in defs {
164                    let s = match self.t.ev().scope_unbound(scope, d) {
165                        Ok(s) => s,
166                        Err(e) => {
167                            if !self
168                                .error
169                                .as_ref()
170                                .is_some_and(|prior| self.t.is_exception(prior))
171                            {
172                                self.error = Some(e);
173                            }
174                            return 0;
175                        }
176                    };
177                    l = l.max(self.level(ir.def(d).body, &s));
178                    if self.marks.insert(d) {
179                        marked.push(d);
180                    }
181                }
182                l = l.max(self.level(*body, scope));
183                for d in marked {
184                    self.marks.remove(&d);
185                }
186                l
187            }
188            Expr::Subst { bindings, body } => {
189                let outer = self.substs.clone();
190                for b in bindings {
191                    let expr = match &b.value {
192                        Arg::Expr { expr, .. } => Some((*expr, scope.clone())),
193                        Arg::Op { .. } => None,
194                    };
195                    self.substs.push(SubstLevel {
196                        decl: b.decl,
197                        expr,
198                        outer: outer.clone(),
199                    });
200                }
201                let l = self.level(*body, scope);
202                self.substs = outer;
203                l
204            }
205            Expr::Label { body, .. } | Expr::Selected(body) => self.level(*body, scope),
206            other => {
207                let mut l = 0;
208                for c in other.children() {
209                    l = l.max(self.level(c, scope));
210                }
211                l
212            }
213        }
214    }
215
216    fn max_of(&mut self, es: &[ExprId], scope: &Scope) -> u8 {
217        let mut l = 0;
218        for &e in es {
219            l = l.max(self.level(e, scope));
220        }
221        l
222    }
223
224    /// The level of a constant or substituted declaration (`OpApplKind` with
225    /// a declaration as the operator).
226    fn decl_level(&mut self, decl: DeclId, scope: &Scope) -> u8 {
227        let ir = &*self.t.ir;
228        let d = ir.decl(decl);
229        if self.t.is_root_var_name(&d.name) {
230            return 1;
231        }
232        // A substitution bound by an enclosing `SubstIn` of this level
233        // computation (`c1.cons(sub.getOp(), LazyValue)`).
234        if let Some(pos) = self.substs.iter().rposition(|s| s.decl == decl) {
235            let s = self.substs[pos].clone();
236            return match s.expr {
237                Some((expr, sc)) => {
238                    let saved = std::mem::replace(&mut self.substs, s.outer);
239                    let l = self.level(expr, &sc);
240                    self.substs = saved;
241                    l
242                }
243                None => 0,
244            };
245        }
246        if d.variable {
247            return 0;
248        }
249        match d.constant.and_then(|c| self.t.const_look(c)) {
250            Some(Look::Def(def)) => self.def_body_level(def, scope),
251            Some(Look::Java(op, _)) => min_level(op),
252            _ => 0,
253        }
254    }
255
256    fn local_level(&mut self, r: LocalRef, scope: &Scope) -> u8 {
257        let info = self.t.slot_info(scope.def(), r);
258        if let Some((name, _)) = &info
259            && self.t.is_root_var_name(name)
260        {
261            return 1;
262        }
263        // A `LET` definition: TLC finds its node, marked inside the `LET`
264        // and otherwise looked into like any definition.
265        if let Some((_, SlotKind::LetValue(d))) = info {
266            if self.marks.contains(&d) {
267                return 0;
268            }
269            return self.def_body_level(d, scope);
270        }
271        match self.t.ev().scope_slot(scope, r) {
272            SlotView::Lazy(expr, sc) => self.level(expr, &sc),
273            SlotView::AnalysisBound => 1, // Pure unknowns are conservatively state level.
274            SlotView::Unset
275            | SlotView::Value(_)
276            | SlotView::AnalysisConstant
277            | SlotView::Other
278            | SlotView::Function(_) => 0,
279        }
280    }
281
282    /// A use of a definition with no arguments.
283    fn def_level(&mut self, d: DefId, scope: &Scope) -> u8 {
284        if self.t.is_root_var_name(&self.t.ir.def(d).name) {
285            return 1;
286        }
287        match self.t.lookup_def(d) {
288            Look::Def(r) => self.def_body_level(r, scope),
289            Look::Java(op, _) => min_level(op),
290            Look::Value(_) | Look::Literal(_) => 0,
291        }
292    }
293
294    /// `c.cons(opNode, ValOne)` and the level of the body.
295    fn def_body_level(&mut self, d: DefId, scope: &Scope) -> u8 {
296        if !self.marks.insert(d) {
297            return 0;
298        }
299        let s = match self.t.ev().scope_unbound(scope, d) {
300            Ok(s) => s,
301            Err(e) => {
302                if !self
303                    .error
304                    .as_ref()
305                    .is_some_and(|prior| self.t.is_exception(prior))
306                {
307                    self.error = Some(e);
308                }
309                return 0;
310            }
311        };
312        let l = self.level(self.t.ir.def(d).body, &s);
313        self.marks.remove(&d);
314        l
315    }
316
317    fn callee_level(&mut self, callee: &OpRef, scope: &Scope) -> u8 {
318        let ir = &*self.t.ir;
319        match callee {
320            OpRef::Def(d) => {
321                if self.t.is_root_var_name(&ir.def(*d).name) {
322                    return 1;
323                }
324                match self.t.lookup_def(*d) {
325                    Look::Def(r) => self.def_body_level(r, scope),
326                    Look::Java(op, _) => min_level(op),
327                    Look::Value(_) | Look::Literal(_) => 0,
328                }
329            }
330            OpRef::Std(op) => min_level(*op),
331            OpRef::Builtin(op) => match op {
332                BuiltinOp::Prime | BuiltinOp::Unchanged | BuiltinOp::Cdot => 2,
333                BuiltinOp::Always
334                | BuiltinOp::Eventually
335                | BuiltinOp::LeadsTo
336                | BuiltinOp::WhilePlus => 3,
337                BuiltinOp::Enabled => 1,
338                _ => 0,
339            },
340            OpRef::Const(c) => {
341                let decl = ir.consts()[c.index()];
342                self.decl_level(decl, scope)
343            }
344            OpRef::Subst(decl) => self.decl_level(*decl, scope),
345            OpRef::Param(r) => {
346                if let Some((name, _)) = self.t.slot_info(scope.def(), *r)
347                    && self.t.is_root_var_name(&name)
348                {
349                    return 1;
350                }
351                0
352            }
353            OpRef::Unbound(_) => 0,
354        }
355    }
356}
357
358/// The `minLevel` of a Java override's annotation (0 for unannotated module
359/// methods): `TLCGet`, `TLCExt!CounterExample` and `Trace`, the trace
360/// modules' `_TLCState`, and the `IOUtils` operators that run processes.
361fn min_level(op: StdOp) -> u8 {
362    match (op.module(), op.name()) {
363        ("TLC", "TLCGet")
364        | ("TLCExt", "CounterExample" | "Trace")
365        | ("_JsonTrace" | "_TLCTrace", "_TLCState")
366        | ("IOUtils", "IOExec" | "IOEnvExec" | "IOExecTemplate" | "IOEnvExecTemplate") => 1,
367        _ => 0,
368    }
369}
370
371/// Whether a definition sits in another definition's frame (for slot names).
372pub(crate) fn parent_of(scope: DefScope) -> Option<DefId> {
373    match scope {
374        DefScope::Local { parent }
375        | DefScope::Inline { parent }
376        | DefScope::LetValue { parent, .. } => Some(parent),
377        DefScope::TopLevel => None,
378    }
379}