Skip to main content

dive_model/
reach.rs

1//! What a bound model uses that dive does not check yet, each refused as
2//! `unsupported` by name.
3
4use std::collections::BTreeSet;
5
6use dive_eval::{Scope, SlotView};
7use dive_ir::{Arg, DefId, Effects, Expr, ExprId, OpRef, StdOp, StdSupport};
8
9use crate::bind::Binder;
10use crate::model::{Model, Pred, Unsupported, UnsupportedKind};
11use crate::tables::Look;
12
13mod tuple_calls;
14
15/// The features of `model` dive refuses, in a stable order.
16pub(crate) fn unsupported(b: &Binder<'_>, model: &Model) -> Vec<Unsupported> {
17    let mut out: Vec<Unsupported> = b
18        .unsupported
19        .iter()
20        .map(|feature| Unsupported {
21            feature: feature.clone(),
22            kind: UnsupportedKind::Feature,
23        })
24        .collect();
25    let ir = &*model.ir;
26    let (roots, _) = checking_path(b, model);
27    let reach = ir.reachable_defs(&roots);
28    let used = ir.reachable_defs(&startup_roots(b, model, roots.clone()));
29    // A refused start-up evaluation of an impure definition matters only if
30    // the checking path uses the definition (TLC may have given it a value)
31    // or TLC's evaluation of it may have had a lasting effect (output, a
32    // random draw, a register, a write or shared input state). Under TLC's
33    // value or exploration order, the strings that evaluation would have
34    // created (`IOEnv`'s keys and values, `ToString`) change later order, so
35    // every such refusal stands there.
36    let ordered_names = b.opts.eval.ctx.order == dive_value::ValueOrder::Tlc
37        || b.opts.eval.exploration == dive_eval::ExplorationOrder::Tlc;
38    for refusal in &b.startup_refusals {
39        let reached = used.get(refusal.def.index()).copied().unwrap_or(true);
40        if reached || ordered_names || !effect_free(b, refusal.def) {
41            b.ev()
42                .restore_external_input_refusal(refusal.input_refusal.clone());
43            out.push(Unsupported {
44                feature: refusal.what.clone(),
45                kind: UnsupportedKind::Feature,
46            });
47        }
48    }
49    if !model.implied_temporals.is_empty() {
50        let names: Vec<&str> = model
51            .implied_temporals
52            .iter()
53            .map(|n| n.name.as_str())
54            .collect();
55        out.push(Unsupported {
56            kind: UnsupportedKind::TemporalProperty,
57            feature: format!(
58                "temporal properties (liveness checking): {}",
59                names.join(", ")
60            ),
61        });
62    }
63    if let Some(s) = &model.symmetry
64        && !model.unreduced_symmetry_liveness()
65    {
66        out.push(Unsupported {
67            feature: format!("SYMMETRY {s}"),
68            kind: UnsupportedKind::Feature,
69        });
70    }
71    // Java overrides dive does not implement, reachable from what is checked.
72    let mut refused: BTreeSet<String> = BTreeSet::new();
73    for r in ir.refusals() {
74        if reach.get(r.def.index()).copied().unwrap_or(false) {
75            if let dive_ir::Feature::StdOp(op) = &r.feature
76                && matches!(op, StdOp::IoUtilsIOEnv | StdOp::IoUtilsDeserialize)
77                && b.ev().options().host_access.allows(*op)
78            {
79                continue;
80            }
81            refused.insert(r.feature.name());
82        }
83    }
84    // Overridden operators used directly as roles.
85    for d in &roots {
86        if let Some(op) = ir.def(*d).std
87            && op.support() != dive_ir::StdSupport::Core
88        {
89            if matches!(op, StdOp::IoUtilsIOEnv | StdOp::IoUtilsDeserialize)
90                && b.ev().options().host_access.allows(op)
91            {
92                continue;
93            }
94            refused.insert(dive_ir::Feature::StdOp(op).name());
95        }
96    }
97    out.extend(refused.into_iter().map(|feature| Unsupported {
98        feature,
99        kind: UnsupportedKind::Feature,
100    }));
101    out
102}
103
104/// Every definition any role may evaluate: the checking path's `roots`, plus
105/// temporal properties, `ALIAS`, `POSTCONDITION`s and `SYMMETRY`.
106fn startup_roots(b: &Binder<'_>, model: &Model, roots: Vec<DefId>) -> Vec<DefId> {
107    let mut out: BTreeSet<DefId> = roots.into_iter().collect();
108    let mut exprs = Vec::new();
109    let mut preds: Vec<&Pred> = Vec::new();
110    for group in [
111        &model.temporals,
112        &model.implied_temporals,
113        &model.configured_properties,
114    ] {
115        preds.extend(group.iter().map(|n| &n.pred));
116    }
117    if let Some(Ok(alias)) = &model.alias {
118        preds.push(&alias.pred);
119    }
120    if let Ok(post) = &model.postconditions {
121        preds.extend(post.iter().map(|n| &n.pred));
122    }
123    for p in preds {
124        role_defs(b, p.expr, &p.scope, &mut out, &mut exprs, 0);
125    }
126    if let Some(Look::Def(d) | Look::Java(_, d)) = &model.symmetry_definition {
127        out.insert(*d);
128    }
129    out.into_iter().collect()
130}
131
132/// Impure Java overrides whose evaluation only reads: TLC's evaluation of
133/// them leaves nothing behind that a later evaluation can observe.
134fn reads_only(op: StdOp) -> bool {
135    !op.impure()
136        || matches!(
137            op,
138            StdOp::IoUtilsIOEnv | StdOp::TlcJavaTime | StdOp::TlcTLCGet
139        )
140}
141
142/// Whether evaluating `def` (everything it can reach, through constants the
143/// configuration binds) can have no lasting effect: every impure operator it
144/// may apply only reads. Conservative: an instance substitution or an
145/// operator parameter that may be impure counts as an effect.
146fn effect_free(b: &Binder<'_>, def: DefId) -> bool {
147    effect_free_with(b, def, false)
148}
149
150/// Whether evaluating `def` (everything it can reach, through constants the
151/// configuration binds) applies no impure operator at all, not even one that
152/// only reads: its value cannot depend on when it is evaluated.
153pub(crate) fn pure(b: &Binder<'_>, def: DefId) -> bool {
154    effect_free_with(b, def, true)
155}
156
157/// [`effect_free`], or with `strict` [`pure`], which also follows the
158/// configuration's overrides of the definitions it reaches and the
159/// substitutions of instances.
160fn effect_free_with(b: &Binder<'_>, def: DefId, strict: bool) -> bool {
161    let reads_only = |op: StdOp| if strict { !op.impure() } else { reads_only(op) };
162    let ir = &*b.t.ir;
163    let mut seen = vec![false; ir.defs().len()];
164    let mut work = vec![def];
165    // An instance's substitution is read dynamically: its value is a binding
166    // of an enclosing `Subst`, whose expressions and operators the walk
167    // visits there, or else the declaration itself, a constant (whose
168    // configured target's body is evaluated at each use) or a variable.
169    // Only `strict` follows that; otherwise it counts as an effect.
170    let substitutions = strict;
171    let constant = |c: dive_ir::ConstId, work: &mut Vec<DefId>| match b.t.const_look(c) {
172        Some(Look::Def(d)) => {
173            work.push(d);
174            true
175        }
176        Some(Look::Java(op, _)) => reads_only(op),
177        Some(Look::Value(_) | Look::Literal(_)) | None => true,
178    };
179    while let Some(d) = work.pop() {
180        match seen.get_mut(d.index()) {
181            Some(s) if !*s => *s = true,
182            Some(_) => continue,
183            None => return false,
184        }
185        if strict {
186            match b.t.lookup_def(d) {
187                Look::Def(r) if r != d => work.push(r),
188                Look::Java(op, r) => {
189                    if !reads_only(op) {
190                        return false;
191                    }
192                    if r != d {
193                        work.push(r);
194                    }
195                }
196                _ => {}
197            }
198        }
199        let def = ir.def(d);
200        if let Some(op) = def.std {
201            if !reads_only(op) {
202                return false;
203            }
204            continue;
205        }
206        let mut exprs = vec![def.body];
207        while let Some(e) = exprs.pop() {
208            let node = ir.node(e);
209            match &node.expr {
210                Expr::Def(x) => work.push(*x),
211                Expr::Let { defs, .. } => work.extend(defs.iter().copied()),
212                Expr::Const(c) => {
213                    if !constant(*c, &mut work) {
214                        return false;
215                    }
216                }
217                Expr::SubstRef { decl, .. } => {
218                    if !substitutions {
219                        return false;
220                    }
221                    if let Some(c) = ir.decl(*decl).constant
222                        && !constant(c, &mut work)
223                    {
224                        return false;
225                    }
226                }
227                _ => {}
228            }
229            for r in node.expr.op_refs() {
230                let ok = match r {
231                    OpRef::Def(x) => {
232                        work.push(*x);
233                        true
234                    }
235                    OpRef::Std(op) => reads_only(*op),
236                    OpRef::Const(c) => constant(*c, &mut work),
237                    OpRef::Subst(decl) => {
238                        substitutions
239                            && ir
240                                .decl(*decl)
241                                .constant
242                                .is_none_or(|c| constant(c, &mut work))
243                    }
244                    OpRef::Param(_) => !node.effects.intersects(Effects::IMPURE),
245                    OpRef::Builtin(_) | OpRef::Unbound(_) => true,
246                };
247                if !ok {
248                    return false;
249                }
250            }
251            node.expr.for_each_child(|child| exprs.push(child));
252        }
253    }
254    true
255}
256
257/// The definitions a role's expression uses directly, including through the
258/// arguments its scope binds lazily.
259pub(crate) fn role_defs(
260    b: &Binder<'_>,
261    e: ExprId,
262    scope: &Scope,
263    out: &mut BTreeSet<DefId>,
264    exprs: &mut Vec<ExprId>,
265    depth: u32,
266) {
267    if depth > 64 {
268        return;
269    }
270    exprs.push(e);
271    let ir = &*b.t.ir;
272    let mut stack = vec![e];
273    while let Some(x) = stack.pop() {
274        let expr = ir.expr(x);
275        match expr {
276            Expr::Def(d) => {
277                out.insert(*d);
278            }
279            Expr::Local(r) => {
280                if let SlotView::Lazy(y, s) = b.ev().scope_slot(scope, *r) {
281                    role_defs(b, y, &s, out, exprs, depth + 1);
282                }
283            }
284            Expr::SubstRef { decl, .. } => {
285                if let SlotView::Lazy(y, s) = b.ev().scope_subst_slot(scope, *decl) {
286                    role_defs(b, y, &s, out, exprs, depth + 1);
287                }
288            }
289            Expr::Let { defs, .. } => out.extend(defs.iter().copied()),
290            _ => {}
291        }
292        for r in expr.op_refs() {
293            if let OpRef::Def(d) = r {
294                out.insert(*d);
295            }
296        }
297        if let Expr::Apply { args, .. } = expr {
298            for a in args {
299                if let Arg::Op {
300                    op: OpRef::Def(d), ..
301                } = a
302                {
303                    out.insert(*d);
304                }
305            }
306        }
307        stack.extend(expr.children());
308    }
309}
310
311/// The definitions on the checking path (what is evaluated while checking:
312/// the initial predicates, the next-state relation, invariants, implied
313/// initial predicates and actions, constraints, action constraints and
314/// `VIEW`, with the assumptions and the configuration's bindings), and the
315/// role expressions themselves, including the lazy arguments their scopes
316/// bind.
317fn checking_path(b: &Binder<'_>, model: &Model) -> (Vec<DefId>, Vec<ExprId>) {
318    let mut roots: BTreeSet<DefId> = BTreeSet::new();
319    let mut exprs: Vec<ExprId> = Vec::new();
320    for p in role_preds(model) {
321        role_defs(b, p.expr, &p.scope, &mut roots, &mut exprs, 0);
322    }
323    roots.extend(model.assumptions.iter().copied());
324    for l in b.t.consts.iter().flatten() {
325        if let Look::Def(d) | Look::Java(_, d) = l {
326            roots.insert(*d);
327        }
328    }
329    for map in [&b.t.tool_obj, &b.t.body_obj] {
330        for l in map.values() {
331            if let Look::Def(d) | Look::Java(_, d) = l {
332                roots.insert(*d);
333            }
334        }
335    }
336    (roots.into_iter().collect(), exprs)
337}
338
339/// Every role's predicate: initial predicates, the next-state relation,
340/// invariants, implied initial predicates and actions, constraints, action
341/// constraints and `VIEW`.
342fn role_preds(model: &Model) -> Vec<&Pred> {
343    let mut preds: Vec<&Pred> = Vec::new();
344    preds.extend(model.init.iter().map(|i| &i.pred));
345    preds.extend(model.next.iter());
346    for group in [
347        &model.invariants,
348        &model.implied_inits,
349        &model.implied_actions,
350        &model.constraints,
351        &model.action_constraints,
352    ] {
353        preds.extend(group.iter().map(|n| &n.pred));
354    }
355    if let Some(v) = &model.view {
356        preds.push(&v.pred);
357    }
358    preds
359}
360
361pub(crate) struct Sequential {
362    pub reasons: Vec<String>,
363    pub names_only: bool,
364    pub runtime_names: bool,
365    pub stateful_checking: Option<String>,
366}
367
368fn native_op(ir: &dive_ir::Ir, op: &OpRef) -> Option<StdOp> {
369    match op {
370        OpRef::Std(op) => Some(*op),
371        OpRef::Def(id) => ir.def(*id).std,
372        _ => None,
373    }
374}
375
376/// What a use of the Java override `op` (applied to a first argument `key`,
377/// when known) on the checking path forces sequential mode for, if anything.
378fn sequential_op(op: StdOp, key: Option<&Expr>) -> Option<String> {
379    let name = op.qualified_name();
380    if op == StdOp::TlcTLCSet {
381        return Some(format!("{name} (writes TLC's registers)"));
382    }
383    if op == StdOp::TlcTLCGet {
384        return match key {
385            Some(Expr::Str(k)) if !dive_ir::effects::tlcget_string_is_live(k) => None,
386            Some(Expr::Str(k)) => Some(format!(
387                "{name}(\"{k}\") (reads a live counter or a register)"
388            )),
389            Some(Expr::Num(n)) => Some(format!("{name}({n}) (reads a register)")),
390            _ => Some(format!("{name} of a key computed while checking")),
391        };
392    }
393    if matches!(
394        op,
395        StdOp::TlcRandomElement
396            | StdOp::RandomizationRandomSubset
397            | StdOp::RandomizationRandomSetOfSubsets
398            | StdOp::RandomizationRandomSubsetSet
399    ) {
400        return Some(format!(
401            "{name} (draws from the expanded state's random stream)"
402        ));
403    }
404    matches!(op.support(), StdSupport::Io | StdSupport::Introspection)
405        .then(|| format!("{name} ({})", op.support().describe()))
406}
407
408/// TLC's action composition counts its intermediate states as generated; the
409/// parallel engine's per-source counts double as successor ordinals.
410/// Sequential BFS reason for TLC composition intermediate-state accounting.
411/// DFID and simulation ignore those intermediate states, as their TLC functors do.
412pub const TLC_CDOT: &str = "action composition under `--action-composition=tlc` (TLC counts its intermediate states as generated)";
413
414/// Why `model` must be checked in sequential mode,
415/// in a stable order; empty when the parallel engine may run it.
416///
417/// A parallel search evaluates the checking path in an order other than
418/// TLC's single worker's. That is invisible except where evaluation reads
419/// or changes state shared across evaluations:
420/// - `TLCSet` (registers, `TLCSet("exit")`);
421/// - `TLCGet` of a live counter or a register, or of a key computed at run
422///   time;
423/// - an operator that performs I/O or reads the checker's internal state;
424/// - runtime name constructors under TLC value or exploration order;
425/// - randomness, drawn in TLC from one stream per expanded state that the
426///   next-state relation and the checks of its successors share;
427/// - side effects (`Print`, ...) inside a lazily evaluated set filter or
428///   function, or inside a cached lazy value bound when the model was bound:
429///   these are evaluated once, by whichever evaluation forces them first.
430///
431/// `Print` elsewhere does not force sequential mode: the checker buffers its
432/// output and releases it in TLC's order.
433pub(crate) fn sequential(b: &Binder<'_>, model: &Model) -> crate::bind::R<Sequential> {
434    let ir = &*model.ir;
435    let (roots, mut exprs) = checking_path(b, model);
436    let fixed = startup_fixed(b, ir);
437    let reach = reachable_unfixed(b.ev(), ir, &roots, &fixed);
438    let ordered_names = b.opts.eval.ctx.order == dive_value::ValueOrder::Tlc
439        || b.opts.eval.exploration == dive_eval::ExplorationOrder::Tlc;
440    let mut names: BTreeSet<String> = BTreeSet::new();
441    let mut out: BTreeSet<String> = BTreeSet::new();
442    let mut composition = false;
443    for (i, d) in ir.defs().iter().enumerate() {
444        if reach.get(i).copied().unwrap_or(false) {
445            if let Some(op) = d.std {
446                // Configuration-selected native operators may have no call
447                // node in the source IR. The bound checking roots retain the
448                // actual target, and its RNG shares one expansion stream.
449                if native_random(op) {
450                    out.extend(sequential_op(op, None));
451                }
452                if ordered_names && op.creates_runtime_names() {
453                    names.insert(format!(
454                        "{} (runtime names require TLC encounter order)",
455                        op.qualified_name()
456                    ));
457                }
458            } else if !fixed.get(i).copied().unwrap_or(false) {
459                exprs.push(d.body);
460            }
461        }
462    }
463    let tlc_cdot = b.opts.eval.action_composition == dive_eval::ActionComposition::Tlc;
464    // A start-up-fixed definition inside a lazily evaluated filter or
465    // function is a value, never evaluated again.
466    let impure = |e: ExprId| b.ev().impure_after_startup(e);
467    let mut seen = vec![false; ir.nodes().len()];
468    while let Some(e) = exprs.pop() {
469        match seen.get_mut(e.index()) {
470            Some(s) if !*s => *s = true,
471            _ => continue,
472        }
473        let expr = ir.expr(e);
474        match expr {
475            Expr::Apply { callee, args } => {
476                if let Some(op) = native_op(ir, callee) {
477                    let key = args.first().and_then(|a| match a {
478                        Arg::Expr { expr, .. } => Some(ir.expr(*expr)),
479                        Arg::Op { .. } => None,
480                    });
481                    if ordered_names && op.creates_runtime_names() {
482                        names.insert(format!(
483                            "{} (runtime names require TLC encounter order)",
484                            op.qualified_name()
485                        ));
486                    }
487                    out.extend(sequential_op(op, key));
488                }
489                for a in args {
490                    if let Arg::Op { op, .. } = a
491                        && let Some(op) = native_op(ir, op)
492                    {
493                        if ordered_names && op.creates_runtime_names() {
494                            names.insert(format!(
495                                "{} (runtime names require TLC encounter order)",
496                                op.qualified_name()
497                            ));
498                        }
499                        out.extend(sequential_op(op, None));
500                    }
501                }
502            }
503            Expr::Cdot(..) if tlc_cdot => {
504                composition = true;
505            }
506            Expr::SetFilter { pred, .. } if impure(*pred) => {
507                out.insert("side effects inside a set filter TLC evaluates lazily".to_owned());
508            }
509            Expr::FcnCons { body, .. } | Expr::RecFcn { body, .. } if impure(*body) => {
510                out.insert("side effects inside a function TLC evaluates lazily".to_owned());
511            }
512            _ => {}
513        }
514        exprs.extend(expr.children());
515    }
516    let ev = b.ev();
517    let shared = role_preds(model)
518        .iter()
519        .any(|p| ev.scope_shares_side_effects(&p.scope));
520    let shared = shared
521        || model
522            .init_actions
523            .iter()
524            .chain(&model.actions)
525            .any(|a| ev.action_shares_side_effects(a));
526    if shared {
527        out.insert(
528            "side effects inside a lazily evaluated value bound with the model, which TLC caches (a LET or an operator argument)".to_owned(),
529        );
530    }
531    let mut classified = classify_sequential(out, names, composition);
532    // Replay and checkpoint admission retain the conservative source inventory.
533    // Only the actual worker restriction can be discharged by this proof.
534    tuple_calls::remove_proved_concat(b, model, &mut classified.reasons)?;
535    Ok(classified)
536}
537
538/// The definitions whose value the binder fixed at start-up
539/// ([`dive_eval::Evaluator::startup_fixed`]): checking reads the kept value
540/// and never evaluates the body again.
541fn startup_fixed(b: &Binder<'_>, ir: &dive_ir::Ir) -> Vec<bool> {
542    let ev = b.ev();
543    (0..ir.defs().len())
544        .map(|i| u32::try_from(i).is_ok_and(|i| ev.startup_fixed(DefId(i))))
545        .collect()
546}
547
548/// [`dive_ir::Ir::reachable_defs`], except that a start-up-fixed definition
549/// is reached without following its body, and that a configured redirect
550/// (`Op <- D`, `C <- D`) reaches `D`, whose body each use evaluates.
551fn reachable_unfixed(
552    ev: &dive_eval::Evaluator,
553    ir: &dive_ir::Ir,
554    roots: &[DefId],
555    fixed: &[bool],
556) -> Vec<bool> {
557    let constant = |c: &dive_ir::ConstId| match ev.constant_binding(*c) {
558        Some(dive_eval::ConstBinding::Def(d)) => Some(d),
559        _ => None,
560    };
561    let mut seen = vec![false; ir.defs().len()];
562    let mut work: Vec<DefId> = roots.to_vec();
563    while let Some(d) = work.pop() {
564        let Some(s) = seen.get_mut(d.index()) else {
565            continue;
566        };
567        if *s {
568            continue;
569        }
570        *s = true;
571        work.push(ev.redirected(d));
572        let def = ir.def(d);
573        if def.std.is_some() || fixed.get(d.index()).copied().unwrap_or(false) {
574            continue;
575        }
576        let mut exprs = vec![def.body];
577        while let Some(e) = exprs.pop() {
578            let node = ir.node(e);
579            if let Expr::Def(x) = &node.expr {
580                work.push(*x);
581            }
582            if let Expr::Let { defs, .. } = &node.expr {
583                work.extend(defs.iter().copied());
584            }
585            if let Expr::Const(c) = &node.expr {
586                work.extend(constant(c));
587            }
588            for r in node.expr.op_refs() {
589                match r {
590                    OpRef::Def(x) => work.push(*x),
591                    OpRef::Const(c) => work.extend(constant(c)),
592                    _ => {}
593                }
594            }
595            node.expr.for_each_child(|child| exprs.push(child));
596        }
597    }
598    seen
599}
600
601fn classify_sequential(
602    mut out: BTreeSet<String>,
603    names: BTreeSet<String>,
604    composition: bool,
605) -> Sequential {
606    let stateful_checking = out.first().cloned();
607    if composition {
608        out.insert(TLC_CDOT.to_owned());
609    }
610    let runtime_names = !names.is_empty();
611    let names_only = out.is_empty() && runtime_names;
612    out.extend(names);
613    Sequential {
614        reasons: out.into_iter().collect(),
615        names_only,
616        runtime_names,
617        stateful_checking,
618    }
619}
620
621fn native_random(op: StdOp) -> bool {
622    matches!(
623        op,
624        StdOp::TlcRandomElement
625            | StdOp::RandomizationRandomSubset
626            | StdOp::RandomizationRandomSetOfSubsets
627            | StdOp::RandomizationRandomSubsetSet
628    )
629}