Skip to main content

dive_eval/
startup_fixed.rs

1//! Side effects that remain after start-up.
2//!
3//! The binder evaluates each zero-arity constant-level definition once at
4//! start-up and keeps its value, as TLC's `SpecProcessor.processConstantDefns`
5//! does; a configured `Op = v` likewise replaces a definition by a value.
6//! Checking then reads the kept value and never evaluates the body again, so
7//! a `RandomElement` in such a body draws once, from the run's start-up
8//! stream (reported with its seed), and never while checking. The IR's
9//! syntactic [`Effects::IMPURE`] flag cannot see this: it propagates through
10//! every reference. [`Evaluator::impure_after_startup`] answers the same
11//! question with the fixed definitions as values, and is conservative in
12//! every case it does not resolve.
13
14use std::sync::OnceLock;
15
16use dive_ir::{Arg, DefId, Effects, Expr, ExprId, OpRef, StdOp};
17use dive_value::Value;
18
19use crate::{ConstBinding, Evaluator};
20
21impl Evaluator {
22    /// Whether start-up fixed the value of `def` for the whole run: it was
23    /// precomputed to an eager value, or the configuration assigns it a
24    /// value, it is not redirected to another definition, and no configured
25    /// redirect ([`Self::redirect_target`]) evaluates its body.
26    ///
27    /// A precomputed value that holds a deferred set anywhere inside it
28    /// (`{x \in S : P}` or `{e : x \in S}` kept lazy) is not fixed: each
29    /// membership test or enumeration evaluates its predicate or map again
30    /// while checking, so its body still runs after start-up.
31    ///
32    /// ```
33    /// # fn example(ev: &dive_eval::Evaluator, d: dive_ir::DefId) {
34    /// if ev.startup_fixed(d) {
35    ///     assert!(ev.precomputed(d).is_some() || ev.is_value_override(d));
36    ///     assert!(!ev.redirect_target(d));
37    /// }
38    /// # }
39    /// ```
40    #[must_use]
41    pub fn startup_fixed(&self, def: DefId) -> bool {
42        self.redirected(def) == def
43            && (self.precomputed_eager(def) || self.is_value_override(def))
44            && !self.redirect_target(def)
45    }
46
47    /// Whether `def` has a precomputed value with no deferred set anywhere
48    /// inside it. The answer is kept once the value is set, which start-up
49    /// does at most once.
50    fn precomputed_eager(&self, def: DefId) -> bool {
51        let core = &self.core;
52        let (Some(value), Some(eager)) = (
53            core.startup.get(def.index()).and_then(OnceLock::get),
54            core.startup_eager.get(def.index()),
55        ) else {
56            return false;
57        };
58        *eager.get_or_init(|| no_deferred_set(value))
59    }
60
61    /// Whether a configured redirect evaluates `def`'s body at each use,
62    /// whatever value start-up gave `def` itself: it is the target of an
63    /// `Op <- def` override (of a definition or of a Java-implemented
64    /// operator), or of a constant bound by `C <- def`
65    /// (`SpecProcessor.java:276-316`).
66    ///
67    /// ```
68    /// # fn example(ev: &dive_eval::Evaluator, d: dive_ir::DefId) {
69    /// if ev.redirect_target(d) {
70    ///     assert!(!ev.startup_fixed(d));
71    /// }
72    /// # }
73    /// ```
74    #[must_use]
75    pub fn redirect_target(&self, def: DefId) -> bool {
76        let core = &self.core;
77        core.redirects
78            .iter()
79            .any(|(&s, &t)| s != t && core.redirect(t) == def)
80            || core.consts.iter().flatten().any(|b| match b {
81                ConstBinding::Def(t) => core.redirect(*t) == def,
82                ConstBinding::Value(_) => false,
83            })
84    }
85
86    /// The definition a constant bound by `C <- D` evaluates at each use.
87    fn bound_def(&self, c: dive_ir::ConstId) -> Option<DefId> {
88        match self.core.consts.get(c.index()) {
89            Some(Some(ConstBinding::Def(d))) => Some(*d),
90            _ => None,
91        }
92    }
93
94    /// Whether some configured redirect evaluates a body whose IR effects
95    /// are impure. The IR's flags propagate through syntactic references
96    /// only, so a node that reaches such a redirect can look pure.
97    fn impure_redirect(&self) -> bool {
98        let ir = self.ir();
99        let core = &self.core;
100        let impure = |t: DefId| {
101            ir.defs().get(core.redirect(t).index()).is_none_or(|d| {
102                d.effects.intersects(Effects::IMPURE) || d.std.is_some_and(StdOp::impure)
103            })
104        };
105        core.redirects.iter().any(|(&s, &t)| s != t && impure(t))
106            || core.consts.iter().flatten().any(|b| match b {
107                ConstBinding::Def(t) => impure(*t),
108                ConstBinding::Value(_) => false,
109            })
110    }
111
112    /// Whether evaluating `expr` while checking can have a side effect
113    /// (output, registers, randomness, time, I/O or checker state): its
114    /// IR [`Effects::IMPURE`] flag, except that a definition
115    /// [`Self::startup_fixed`] is a value, and that a configured redirect
116    /// (`Op <- D`, `C <- D`) reaches `D`'s body. When some redirect reaches
117    /// an impure body, the IR's flags, which follow syntactic references
118    /// only, are not trusted and the walk visits every reachable node. Every
119    /// source the walk does not resolve (operator parameters, instance
120    /// substitutions, `LET` and parameter reads, an unknown node) counts as
121    /// impure.
122    ///
123    /// ```
124    /// # fn example(ev: &dive_eval::Evaluator, e: dive_ir::ExprId) {
125    /// if !ev.impure_after_startup(e) {
126    ///     // Evaluating `e` while checking has no side effect.
127    /// }
128    /// # }
129    /// ```
130    #[must_use]
131    pub fn impure_after_startup(&self, expr: ExprId) -> bool {
132        let ir = self.ir();
133        let core = &self.core;
134        let trust = !self.impure_redirect();
135        let impure = |e: ExprId| {
136            !trust
137                || ir
138                    .nodes()
139                    .get(e.index())
140                    .is_none_or(|n| n.effects.intersects(Effects::IMPURE))
141        };
142        if !impure(expr) {
143            return false;
144        }
145        let mut seen_defs = vec![false; ir.defs().len()];
146        let mut seen = vec![false; ir.nodes().len()];
147        let mut work = vec![expr];
148        // A definition the walk reaches: its body, and its redirect target.
149        let mut reach = |d: DefId, work: &mut Vec<ExprId>| -> bool {
150            for d in [d, self.redirected(d)] {
151                if self.startup_fixed(d) {
152                    continue;
153                }
154                let Some(slot) = seen_defs.get_mut(d.index()) else {
155                    return true;
156                };
157                if *slot {
158                    continue;
159                }
160                *slot = true;
161                let Some(def) = ir.defs().get(d.index()) else {
162                    return true;
163                };
164                if trust && !def.effects.intersects(Effects::IMPURE) {
165                    continue;
166                }
167                if let Some(op) = def.std {
168                    if trust || op.impure() {
169                        return true;
170                    }
171                    continue;
172                }
173                work.push(def.body);
174            }
175            false
176        };
177        while let Some(e) = work.pop() {
178            match seen.get_mut(e.index()) {
179                Some(s) if !*s => *s = true,
180                Some(_) => continue,
181                None => return true,
182            }
183            if !impure(e) {
184                continue;
185            }
186            let node = ir.node(e);
187            match &node.expr {
188                Expr::Def(d) if reach(*d, &mut work) => return true,
189                Expr::Const(c) if self.bound_def(*c).is_some_and(|d| reach(d, &mut work)) => {
190                    return true;
191                }
192                Expr::Local(_) | Expr::SubstRef { .. } | Expr::Subst { .. } => return true,
193                Expr::Apply { callee, args } => {
194                    let key = args.first().and_then(|a| match a {
195                        Arg::Expr { expr, .. } => Some(ir.expr(*expr)),
196                        Arg::Op { .. } => None,
197                    });
198                    let mut src = |op: &OpRef, key, work: &mut Vec<ExprId>| match op {
199                        OpRef::Const(c) => self.bound_def(*c).is_some_and(|d| reach(d, work)),
200                        // `Java <- D` replaces the Java method by `D`.
201                        OpRef::Std(op) if core.std_redirects.contains_key(op) => {
202                            core.std_redirects.get(op).is_none_or(|&d| reach(d, work))
203                        }
204                        op => opref_impure(op, key, work, &mut reach),
205                    };
206                    if src(callee, key, &mut work) {
207                        return true;
208                    }
209                    for a in args {
210                        if let Arg::Op { op, .. } = a
211                            && src(op, None, &mut work)
212                        {
213                            return true;
214                        }
215                    }
216                }
217                Expr::Let { defs, .. } => {
218                    for d in defs {
219                        if reach(*d, &mut work) {
220                            return true;
221                        }
222                    }
223                }
224                _ => {}
225            }
226            node.expr.for_each_child(|c| work.push(c));
227        }
228        false
229    }
230}
231
232/// Whether an operator reference is itself an impure source; a definition
233/// is walked instead.
234fn opref_impure(
235    op: &OpRef,
236    key: Option<&Expr>,
237    work: &mut Vec<ExprId>,
238    reach: &mut impl FnMut(DefId, &mut Vec<ExprId>) -> bool,
239) -> bool {
240    match op {
241        OpRef::Def(d) => reach(*d, work),
242        OpRef::Std(StdOp::TlcTLCGet) => match key {
243            Some(Expr::Str(k)) => dive_ir::effects::tlcget_string_is_live(k),
244            _ => true,
245        },
246        OpRef::Std(op) => op.impure(),
247        // Operator parameters and substitutions carry the effects of any
248        // operator passed as an argument anywhere.
249        OpRef::Param(_) | OpRef::Subst(_) => true,
250        OpRef::Builtin(_) | OpRef::Const(_) | OpRef::Unbound(_) => false,
251    }
252}
253
254/// Whether `value` holds no deferred set anywhere: in set elements, in the
255/// components of a lazy set (`SUBSET S`, `[S -> T]`, `S \X T`, records,
256/// `Seq(S)`), or in function keys and values. The walk reads stored
257/// structure only and never invokes a deferred provider.
258fn no_deferred_set(value: &Value) -> bool {
259    let mut work = vec![value.clone()];
260    while let Some(value) = work.pop() {
261        match value {
262            Value::Set(set) => {
263                if set.as_deferred().is_some() {
264                    return false;
265                }
266                if let Some(elements) = set.stored_elements() {
267                    work.extend(elements.iter().cloned());
268                }
269                work.extend(set.components().into_iter().map(|(_, c)| c));
270            }
271            Value::Fcn(f) => {
272                for i in 0..f.len() {
273                    if let Some((key, val)) = f.entry_cow(i) {
274                        work.push(key.into_owned());
275                        work.push(val.clone());
276                    }
277                }
278            }
279            Value::Bool(_) | Value::Int(_) | Value::BigInt(_) | Value::Str(_) | Value::Model(_) => {
280            }
281        }
282    }
283    true
284}