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}