Skip to main content

dive_model/
model.rs

1//! The bound model: what the checker, simulator and trace validator consume.
2
3use std::sync::Arc;
4
5use dive_eval::{AssumptionOutcome, Evaluator, Scope, St};
6use dive_ir::{DefId, ExprId, Ir};
7use dive_value::{Interner, Value};
8
9use crate::error::{BindError, Message};
10
11/// A predicate or expression TLC evaluates for a role, with the context it
12/// is evaluated in: TLC's `tlc2.tool.Action` (`pred`, `con`).
13#[derive(Clone, Debug)]
14pub struct Pred {
15    /// The expression.
16    pub expr: ExprId,
17    /// Where it is evaluated (operator parameters, split `\E` variables,
18    /// instance substitutions).
19    pub scope: Scope,
20    /// The node TLC reports the role's location from: the expression, or the
21    /// outermost instance substitution TLC wrapped around it
22    /// (`Specs.addSubsts`).
23    pub location: ExprId,
24}
25
26impl Pred {
27    /// A predicate evaluated in its own definition's frame.
28    #[must_use]
29    pub fn new(expr: ExprId, scope: Scope) -> Self {
30        Self {
31            expr,
32            scope,
33            location: expr,
34        }
35    }
36}
37
38/// A role with the name TLC reports it under.
39#[derive(Clone, Debug)]
40pub struct Named {
41    /// The name: the configuration's name for `INVARIANT` and the
42    /// constraints, TLC's derived name for parts of a `PROPERTY`.
43    pub name: String,
44    /// The predicate.
45    pub pred: Pred,
46}
47
48/// An initial predicate (`getInitStateSpec`).
49#[derive(Clone, Debug)]
50pub struct Init {
51    /// The predicate.
52    pub pred: Pred,
53    /// The definition it came from, if any (`INIT Init`, or a conjunct of a
54    /// `SPECIFICATION` that is a use of a definition).
55    pub def: Option<DefId>,
56}
57
58/// The `-deadlock` and `CHECK_DEADLOCK` outcome and other run settings.
59#[derive(Clone, Debug)]
60pub struct Settings {
61    /// Whether deadlock is checked: `CHECK_DEADLOCK` and TLC's `-deadlock`
62    /// flag together.
63    pub check_deadlock: bool,
64}
65
66/// Why the model cannot yet receive a complete checking verdict.
67#[derive(Clone, Copy, Debug, PartialEq, Eq)]
68pub enum UnsupportedKind {
69    /// A temporal property requires the liveness backend.
70    TemporalProperty,
71    /// Another unimplemented feature, which graph capture cannot defer.
72    Feature,
73}
74
75/// A feature of the model that dive does not check yet. The checker refuses
76/// the model as `unsupported`, naming it.
77#[derive(Clone, Debug, PartialEq, Eq)]
78pub struct Unsupported {
79    /// The structured reason, never inferred from diagnostic text.
80    pub kind: UnsupportedKind,
81    /// The feature, by name.
82    pub feature: String,
83}
84
85/// A specification bound to its configuration.
86#[derive(Clone, Debug)]
87pub struct Model {
88    /// The lowered specification.
89    pub ir: Arc<Ir>,
90    /// The evaluator, with the constants bound and the start-up values
91    /// computed. Clones share them.
92    pub evaluator: Evaluator,
93    /// The run's names, in TLC's encounter order.
94    pub names: Arc<Interner>,
95    /// What TLC prints while it processes the model, before it checks the
96    /// assumptions: `Print` output of constant definitions and warnings.
97    pub output: Vec<Message>,
98    /// Initial predicates, in TLC's order.
99    pub init: Vec<Init>,
100    /// The next-state relation as TLC holds it before splitting
101    /// (`getNextStateSpec`), if any.
102    pub next: Option<Pred>,
103    /// The initial predicates as the successor generator's actions
104    /// (`Evaluator::init_states`), numbered from 0.
105    pub init_actions: Vec<dive_eval::next::Action>,
106    /// The next-state relation split into TLC's actions, with TLC's labels,
107    /// numbered after the initial predicates (`Evaluator::successors`).
108    pub actions: Vec<dive_eval::next::Action>,
109    /// Invariants: `INVARIANT`s, then the state predicates `[]P` of
110    /// `PROPERTY`s.
111    pub invariants: Vec<Named>,
112    /// Implied initial predicates: state-level parts of `PROPERTY`s.
113    pub implied_inits: Vec<Named>,
114    /// Implied actions: the `[A]_v` of `[][A]_v` in `PROPERTY`s.
115    pub implied_actions: Vec<Named>,
116    /// Temporal formulas of the behavior specification (fairness), named as
117    /// TLC names them. Inert for safety checking.
118    pub temporals: Vec<Named>,
119    /// Temporal properties to check (liveness).
120    pub implied_temporals: Vec<Named>,
121    /// Binder-recorded original names of TLC implied-temporal Actions.
122    pub(crate) implied_temporal_action_names: Vec<String>,
123    /// Original configured PROPERTY formulas, before TLC's role splitting.
124    /// These retain configuration names for complete counterexample claims;
125    /// the role vectors above keep TLC's evaluation/checking order unchanged.
126    pub configured_properties: Vec<Named>,
127    /// `CONSTRAINT`s.
128    pub constraints: Vec<Named>,
129    /// `ACTION_CONSTRAINT`s.
130    pub action_constraints: Vec<Named>,
131    /// `VIEW`.
132    pub view: Option<Named>,
133    /// `ALIAS`. TLC looks it up only when it prints a trace
134    /// (`Spec.getAliasSpec`), so a lookup error is reported then, not at
135    /// start-up.
136    pub alias: Option<Result<Named, BindError>>,
137    /// `POSTCONDITION`s. TLC looks them up after checking
138    /// (`Spec.getPostConditionSpecs`), stopping at the first error, which it
139    /// reports then.
140    pub postconditions: Result<Vec<Named>, BindError>,
141    /// `SYMMETRY`, by name.
142    pub symmetry: Option<String>,
143    pub(crate) symmetry_liveness: crate::SymmetryLivenessResolution,
144    /// Prepared safety reduction. Concrete states remain unmodified.
145    pub symmetry_reduction: Option<Arc<crate::symmetry::Reduction>>,
146    /// Pre-constant-evaluation lookup, retained only for the configured declaration.
147    pub(crate) symmetry_definition: Option<crate::tables::Look>,
148    /// Run settings.
149    pub settings: Settings,
150    /// The root module's assumptions TLC checks (not `AXIOM`s), in order.
151    pub assumptions: Vec<DefId>,
152    /// Features this model uses that dive does not check yet.
153    pub unsupported: Vec<Unsupported>,
154    /// Why the model must be checked in sequential mode, with one logical
155    /// worker evaluating in TLC's order; empty when a parallel
156    /// search gives the same results. Each entry names the feature.
157    pub sequential: Vec<String>,
158    /// The only sequential restriction is preserving runtime name encounter
159    /// order. This is not an I/O, random-stream or live-checker-state effect.
160    /// This conservative source inventory remains available to checkpoint
161    /// admission after a proof discharges the corresponding worker restriction.
162    pub sequential_names_only: bool,
163    /// Checking may create runtime names whose encounter order is observable
164    /// under the selected value or exploration order. Remains true when other
165    /// sequential effects are also reachable.
166    /// This is a conservative source feature flag; a worker-selection proof
167    /// can remove a scheduling reason without changing replay's inventory.
168    pub runtime_name_order: bool,
169    pub(crate) stateful_checking: Option<String>,
170    /// Pure constant-level definitions whose start-up evaluation was left to
171    /// Core ([`crate::bind_deferring_constants`]); empty
172    /// otherwise. The evaluator evaluates them lazily.
173    pub deferred_constants: std::collections::BTreeSet<dive_ir::DefId>,
174    /// The root module's pure `ASSUME`s, in order, that Core
175    /// evaluates when it compiles its plan
176    /// ([`crate::bind_deferring_constants`]); empty otherwise. Their value
177    /// is a function of the start-up values alone, so one the core finds
178    /// `TRUE` need not be checked again
179    /// ([`Model::check_assumptions_except`]).
180    pub deferred_assumptions: Vec<DefId>,
181}
182
183impl Model {
184    /// A reachable stateful checking restriction, if any, from model binding.
185    ///
186    /// Runtime-name encounter order and TLC composition accounting are separate
187    /// sequential requirements. Their presence alone does not return a reason
188    /// here. This classification does not establish support: each backend must
189    /// still apply its remaining checks and evaluate the actual model.
190    ///
191    /// ```
192    /// # fn explain(model: &dive_model::Model) {
193    /// if let Some(reason) = model.stateful_checking() {
194    ///     eprintln!("stateful checking: {reason}");
195    /// }
196    /// # }
197    /// ```
198    #[must_use]
199    pub fn stateful_checking(&self) -> Option<&str> {
200        self.stateful_checking.as_deref()
201    }
202
203    /// Records every name interned so far as a start-up name
204    /// ([`dive_eval::Evaluator::seal_startup_names`]). Call it only after
205    /// interning names TLC interns before it evaluates any `ASSUME` or state.
206    pub fn seal_startup_names(&self) {
207        self.evaluator.seal_startup_names();
208    }
209
210    /// Whether a name was interned after start-up
211    /// ([`dive_eval::Evaluator::startup_names`])
212    /// and string order follows encounter order (TLC's value or exploration
213    /// order), so that the name's position relative to the others depends
214    /// on evaluations outside a given trace.
215    #[must_use]
216    pub fn has_runtime_names(&self) -> bool {
217        let opts = self.evaluator.options();
218        (opts.ctx.order == dive_value::ValueOrder::Tlc
219            || opts.exploration == dive_eval::ExplorationOrder::Tlc)
220            && self.names.len() > self.evaluator.startup_names()
221    }
222
223    /// The immutable original declaration and policy after actual role binding.
224    /// This is not exploration or witness evidence.
225    ///
226    /// ```
227    /// # fn example(model: &dive_model::Model) {
228    /// let requested = model.symmetry_liveness().requested();
229    /// assert!(["unreduced", "refuse", "tlc"].contains(&requested.as_str()));
230    /// # }
231    /// ```
232    #[must_use]
233    pub const fn symmetry_liveness(&self) -> &crate::SymmetryLivenessResolution {
234        &self.symmetry_liveness
235    }
236
237    /// Whether this model uses full concrete identities for temporal checking.
238    /// Public role/declaration changes or an installed reduction invalidate it.
239    ///
240    /// ```
241    /// # fn example(model: &dive_model::Model) {
242    /// if model.unreduced_symmetry_liveness() {
243    ///     assert!(model.symmetry_reduction.is_none());
244    ///     assert!(!model.implied_temporals.is_empty());
245    /// }
246    /// # }
247    /// ```
248    #[must_use]
249    pub fn unreduced_symmetry_liveness(&self) -> bool {
250        self.symmetry_liveness.unreduced()
251            && self.symmetry.as_deref() == self.symmetry_liveness.declared()
252            && !self.implied_temporals.is_empty()
253            && self.symmetry_reduction.is_none()
254    }
255
256    /// Admits public bound-model metadata before backend startup or host effects.
257    /// Checks evaluator ownership and every predicate/action scope without
258    /// evaluating expressions or forcing captured values.
259    ///
260    /// # Errors
261    /// A named malformed/foreign context or bounded admission refusal.
262    pub fn validate_context(&self) -> dive_eval::Result<()> {
263        self.evaluator
264            .validate_model_context(&self.ir, &self.names)?;
265        let check = |pred: &Pred| {
266            if self.ir.nodes().get(pred.location.index()).is_none() {
267                return Err(dive_eval::EvalError::unsupported(
268                    "invalid model predicate location (DIVE-EVAL-C001)",
269                ));
270            }
271            self.evaluator.validate_predicate(&pred.scope, pred.expr)
272        };
273        for init in &self.init {
274            if init
275                .def
276                .is_some_and(|d| self.ir.defs().get(d.index()).is_none())
277            {
278                return Err(dive_eval::EvalError::unsupported(
279                    "invalid initial definition (DIVE-EVAL-C001)",
280                ));
281            }
282            check(&init.pred)?;
283        }
284        if let Some(next) = &self.next {
285            check(next)?;
286        }
287        for named in self
288            .invariants
289            .iter()
290            .chain(&self.implied_inits)
291            .chain(&self.implied_actions)
292            .chain(&self.temporals)
293            .chain(&self.implied_temporals)
294            .chain(&self.configured_properties)
295            .chain(&self.constraints)
296            .chain(&self.action_constraints)
297            .chain(self.view.iter())
298            .chain(self.alias.as_ref().and_then(|a| a.as_ref().ok()))
299            .chain(self.postconditions.as_ref().into_iter().flatten())
300        {
301            check(&named.pred)?;
302        }
303        if self
304            .assumptions
305            .iter()
306            .any(|d| self.ir.defs().get(d.index()).is_none())
307        {
308            return Err(dive_eval::EvalError::unsupported(
309                "invalid assumption definition (DIVE-EVAL-C001)",
310            ));
311        }
312        for action in self.init_actions.iter().chain(&self.actions) {
313            self.evaluator
314                .validate_predicate(&action.scope(), action.expr())?;
315        }
316        if self.implied_temporal_action_names.len() != self.implied_temporals.len() {
317            return Err(dive_eval::EvalError::unsupported(
318                "invalid temporal property-origin metadata (DIVE-EVAL-C001)",
319            ));
320        }
321        Ok(())
322    }
323
324    /// Original configuration names on TLC's expanded implied-temporal Actions,
325    /// recorded in role order by the binder. A conjunctive `P` can yield
326    /// `P;P`; these are distinct from configured claims and derived labels.
327    /// Rebind caller-edited role vectors before using this binding snapshot.
328    #[must_use]
329    pub fn implied_temporal_action_names(&self) -> &[String] {
330        &self.implied_temporal_action_names
331    }
332
333    /// Original configured property claims, or the temporal roles for a model
334    /// without retained originals. A quantified conjunction must be attributed
335    /// as one configured property, not as ambiguous identically named roles.
336    #[must_use]
337    pub fn property_claims(&self) -> &[Named] {
338        if self.configured_properties.is_empty() {
339            &self.implied_temporals
340        } else {
341            &self.configured_properties
342        }
343    }
344
345    /// Evaluates a role's predicate.
346    ///
347    /// # Errors
348    /// Any evaluation error, refusal or resource limit.
349    pub fn eval(&self, pred: &Pred, st: &St) -> dive_eval::Result<Value> {
350        self.evaluator
351            .validate_model_context(&self.ir, &self.names)?;
352        self.evaluator.eval_scoped(&pred.scope, pred.expr, st)
353    }
354
355    /// Evaluates a configured Boolean role with TLC's `Tool.isValid` boundary.
356    /// A returned non-Boolean value raises the tool's source-qualified 2215;
357    /// an error inside the expression retains its original constructor/source.
358    ///
359    /// ```no_run
360    /// # fn check(model: &dive_model::Model, pred: &dive_model::Pred, state: &dive_eval::St) -> dive_eval::Result<()> {
361    /// let holds = model.eval_boolean(pred, state)?;
362    /// # let _ = holds; Ok(()) }
363    /// ```
364    ///
365    /// # Errors
366    /// The original evaluation failure, or the actual non-Boolean role failure.
367    pub fn eval_boolean(&self, pred: &Pred, st: &St) -> dive_eval::Result<bool> {
368        match self.eval(pred, st)? {
369            Value::Bool(value) => Ok(value),
370            _ => Err(dive_eval::EvalError::coded(
371                dive_eval::Ec::ExpectedValue,
372                format!(
373                    "TLC expected a boolean value, but did not find one. {}",
374                    self.evaluator.location(pred.location)
375                ),
376            )
377            .at(pred.location)),
378        }
379    }
380
381    /// TLC's `Tool.checkAssumptions`: the assumptions in order, `AXIOM`s
382    /// skipped, stopping at the first that is not `TRUE`.
383    #[must_use]
384    pub fn check_assumptions(&self) -> AssumptionOutcome {
385        self.check_assumptions_except(&[])
386    }
387
388    /// [`Self::check_assumptions`], skipping `proved`: pure assumptions
389    /// (among [`Self::deferred_assumptions`]) another evaluator found
390    /// `TRUE`. Skipping one is unobservable: TLC's evaluation of it has no
391    /// effect and does not stop the check.
392    #[must_use]
393    pub fn check_assumptions_except(&self, proved: &[DefId]) -> AssumptionOutcome {
394        if let Err(error) = self.evaluator.validate_model_context(&self.ir, &self.names) {
395            return AssumptionOutcome::Error {
396                def: DefId(u32::MAX),
397                message: error.to_string(),
398                error: error.into(),
399            };
400        }
401        let axioms: Vec<DefId> = {
402            let root = self.ir.module(self.ir.root());
403            root.assumptions
404                .iter()
405                .zip(&root.axioms)
406                .filter(|(_, ax)| **ax)
407                .map(|(d, _)| *d)
408                .collect()
409        };
410        self.evaluator
411            .check_assumptions(|d| axioms.contains(&d) || proved.contains(&d))
412    }
413
414    /// The `Print` output collected since the last call (the evaluator's
415    /// default sink).
416    #[must_use]
417    pub fn take_output(&self) -> Vec<String> {
418        self.evaluator.take_output()
419    }
420
421    /// The location TLC prints for a role's predicate (`getLocation()`).
422    #[must_use]
423    pub fn location(&self, pred: &Pred) -> String {
424        self.ir.location(&self.ir.node(pred.location).origin)
425    }
426}