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}