Skip to main content

dive_runtime/
result.rs

1//! The result of a check: verdict, statistics, counterexample, and how TLC
2//! would classify and report it.
3
4use std::time::Duration;
5
6use dive_eval::EvalError;
7use dive_store::StoreMode;
8use dive_value::Value;
9
10/// Where an evaluation error was raised: the phase of TLC's search it
11/// belongs to. TLC's error class and exit status depend on it.
12#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
13#[non_exhaustive]
14pub enum ErrorSite {
15    /// Processing the specification, before the assumptions.
16    Startup,
17    /// Evaluating an `ASSUME`.
18    Assumption,
19    /// Generating the initial states.
20    Init,
21    /// Generating the successors of a state.
22    Next,
23    /// Evaluating a `CONSTRAINT`.
24    Constraint,
25    /// Evaluating an `ACTION_CONSTRAINT`.
26    ActionConstraint,
27    /// Evaluating `VIEW`.
28    View,
29    /// Fingerprinting or encoding a state.
30    Fingerprint,
31    /// Evaluating an invariant.
32    Invariant,
33    /// Evaluating an implied initial predicate.
34    ImpliedInit,
35    /// Evaluating an implied action.
36    ImpliedAction,
37    /// Evaluating a `POSTCONDITION`.
38    Postcondition,
39}
40
41impl ErrorSite {
42    /// A short name for output.
43    #[must_use]
44    pub const fn name(self) -> &'static str {
45        match self {
46            Self::Startup => "startup",
47            Self::Assumption => "assumption",
48            Self::Init => "initial-states",
49            Self::Next => "next-state",
50            Self::Constraint => "constraint",
51            Self::ActionConstraint => "action-constraint",
52            Self::View => "view",
53            Self::Fingerprint => "fingerprint",
54            Self::Invariant => "invariant",
55            Self::ImpliedInit => "implied-init",
56            Self::ImpliedAction => "implied-action",
57            Self::Postcondition => "postcondition",
58        }
59    }
60}
61
62/// The verdict of a check.
63#[derive(Clone, Debug, PartialEq, Eq)]
64#[non_exhaustive]
65pub enum Verdict {
66    /// The search finished without finding a violation.
67    Success,
68    /// An invariant is violated, in an initial state (`initial`) or a later
69    /// one.
70    InvariantViolated {
71        /// The invariant, as TLC names it.
72        property: String,
73        /// Whether the violating state is an initial state.
74        initial: bool,
75    },
76    /// An implied initial predicate (a state-level part of a `PROPERTY`) is
77    /// violated by an initial state.
78    PropertyViolatedInitially {
79        /// The property.
80        property: String,
81    },
82    /// An implied action (`[][A]_v` in a `PROPERTY`) is violated by a step.
83    ActionPropertyViolated {
84        /// The property.
85        property: String,
86    },
87    /// A reachable state has no successor at all.
88    Deadlock,
89    /// An `ASSUME` is false.
90    AssumptionFalse {
91        /// The failed assumption's source image, as TLC names the property.
92        property: String,
93        /// TLC's message.
94        message: String,
95    },
96    /// A `POSTCONDITION` is not `TRUE` after a complete search.
97    PostconditionFalse {
98        /// The postcondition.
99        property: String,
100        /// TLC's message (`TLC_POSTCONDITION_FALSE`).
101        message: String,
102    },
103    /// TLC's error while processing the model (configuration, constants,
104    /// start-up evaluation), as the binding stage reports it.
105    ModelError {
106        /// TLC's message code.
107        code: u32,
108        /// Its `EC` name.
109        name: String,
110        /// TLC's message.
111        message: String,
112    },
113    /// A successor leaves a variable unassigned.
114    NotCompletelySpecified {
115        /// Whether it is an initial state.
116        initial: bool,
117        /// The unassigned variables.
118        variables: Vec<String>,
119        /// TLC's message (`TLC_STATE_NOT_COMPLETELY_SPECIFIED_NEXT`, or
120        /// `TLC_INITIAL_STATE` for an initial state).
121        message: String,
122        /// Actual partial Init candidate, printed inside TLC's error message,
123        /// separately from its absent formal counterexample.
124        initial_candidate: Option<PartialState>,
125    },
126    /// Evaluation failed with an error TLC also raises (including a failed
127    /// `Assert` and integer overflow), classified as TLC classifies it at
128    /// `site` (the error-class table in `class.rs`).
129    EvaluationError {
130        /// Where.
131        site: ErrorSite,
132        /// TLC's deciding code: what its run returns, which decides its exit
133        /// status (`ModelChecker.modelCheck`). After an error while
134        /// exploring, TLC replays the step with its call stack recorded, and
135        /// the replay decides it (`TLC_NESTED_EXPRESSION`, or the code of the
136        /// `EvalException` it meets again).
137        code: u32,
138        /// Its `EC` name.
139        name: &'static str,
140        /// The code of the error message TLC prints first: the site's
141        /// wrapper (`TLC_INVARIANT_EVALUATION_FAILED`, `GENERAL`, ...) or the
142        /// error's own code.
143        reported: u32,
144        /// The text of that message, as TLC prints it.
145        message: String,
146        /// Whether `code` is checked against captured TLC runs for this site
147        /// and this kind of error. An unverified class is reported but not
148        /// claimed.
149        verified: bool,
150        /// The evaluation error itself.
151        cause: EvalError,
152        /// The invariant whose evaluation raised `cause`, retained separately
153        /// from TLC's deciding error class and diagnostic replay.
154        invariant: Option<String>,
155    },
156    /// dive refused, naming the feature. Never a verdict about the model.
157    Unsupported {
158        /// The feature.
159        feature: String,
160    },
161    /// A resource limit (evaluation depth, memory) was hit. Never a verdict
162    /// about the model.
163    ResourceLimit {
164        /// What.
165        message: String,
166    },
167    /// The run's budget (`--time-limit`, `--max-memory`) was exhausted.
168    /// Never a verdict about the model; the statistics are those
169    /// at the stop.
170    Stopped(Box<crate::budget::Stopped>),
171    /// A required process-memory observation failed; never a model verdict.
172    BudgetMeasurement {
173        /// Typed measurement failure, without an invented observed byte count.
174        error: crate::budget::MeasurementError,
175    },
176    /// An internal invariant of dive failed: a bug, never a verdict.
177    InternalError {
178        /// What.
179        message: String,
180    },
181}
182
183/// How TLC classifies a result: its observable primary code, `EC` name,
184/// and physical process exit status. A source-qualified Init replay may
185/// retain GENERAL as primary while its diagnostic context supplies exit 75.
186#[derive(Clone, Debug, PartialEq, Eq)]
187pub struct TlcClass {
188    /// The observable deciding message code, distinct from a replay exit code.
189    pub code: u32,
190    /// Its `EC` name.
191    pub name: String,
192    /// TLC's physical exit status, including qualified diagnostic replay paths.
193    pub exit: u8,
194    /// The code of the error message TLC prints first, where it differs
195    /// from `code` (an evaluation error wrapped by its site); otherwise
196    /// `code`.
197    pub reported: u32,
198    /// Whether dive reproduces TLC's class here, checked against a captured
199    /// TLC run. An unverified class is reported but not claimed.
200    pub verified: bool,
201}
202
203impl Verdict {
204    /// The verdict's kebab-case name in dive's output.
205    #[must_use]
206    pub const fn kind(&self) -> &'static str {
207        match self {
208            Self::Success => "success",
209            Self::InvariantViolated { .. } => "invariant-violation",
210            Self::PropertyViolatedInitially { .. } => "property-violation",
211            Self::ActionPropertyViolated { .. } => "action-property-violation",
212            Self::Deadlock => "deadlock",
213            Self::AssumptionFalse { .. } => "assumption-failure",
214            Self::PostconditionFalse { .. } => "postcondition-failure",
215            Self::ModelError { .. } => "model-error",
216            Self::NotCompletelySpecified { .. } => "incomplete-state",
217            Self::EvaluationError { code: 2132, .. } => "assertion-failure",
218            Self::EvaluationError {
219                code: 2178 | 2265, ..
220            } => "overflow",
221            Self::EvaluationError { .. } => "evaluation-error",
222            Self::Unsupported { .. } => "unsupported",
223            Self::ResourceLimit { .. } => "resource-limit",
224            Self::Stopped(_) => "stopped",
225            Self::InternalError { .. } | Self::BudgetMeasurement { .. } => "internal-error",
226        }
227    }
228
229    /// The violated property, where there is one.
230    #[must_use]
231    pub fn property(&self) -> Option<&str> {
232        match self {
233            Self::InvariantViolated { property, .. }
234            | Self::PropertyViolatedInitially { property }
235            | Self::ActionPropertyViolated { property }
236            | Self::PostconditionFalse { property, .. }
237            | Self::AssumptionFalse { property, .. } => Some(property),
238            _ => None,
239        }
240    }
241
242    /// Whether this is a verdict about the model (as opposed to a refusal,
243    /// a resource limit or a bug).
244    #[must_use]
245    pub const fn is_verdict(&self) -> bool {
246        !matches!(
247            self,
248            Self::Unsupported { .. }
249                | Self::ResourceLimit { .. }
250                | Self::Stopped(_)
251                | Self::BudgetMeasurement { .. }
252                | Self::InternalError { .. }
253        )
254    }
255
256    /// TLC's classification of this verdict, where TLC has one.
257    #[must_use]
258    pub fn tlc(&self) -> Option<TlcClass> {
259        let class = |code: u32, name: &str, verified: bool| TlcClass {
260            code,
261            name: name.to_owned(),
262            exit: tlc_exit_status(code),
263            reported: code,
264            verified,
265        };
266        Some(match self {
267            Self::Success => class(2193, "TLC_SUCCESS", true),
268            Self::InvariantViolated { initial: true, .. } => {
269                class(2107, "TLC_INVARIANT_VIOLATED_INITIAL", true)
270            }
271            Self::InvariantViolated { initial: false, .. } => {
272                class(2110, "TLC_INVARIANT_VIOLATED_BEHAVIOR", true)
273            }
274            Self::PropertyViolatedInitially { .. } => {
275                class(2108, "TLC_PROPERTY_VIOLATED_INITIAL", true)
276            }
277            Self::ActionPropertyViolated { .. } => {
278                class(2112, "TLC_ACTION_PROPERTY_VIOLATED_BEHAVIOR", true)
279            }
280            Self::Deadlock => class(2114, "TLC_DEADLOCK_REACHED", true),
281            Self::AssumptionFalse { .. } => class(2104, "TLC_ASSUMPTION_FALSE", true),
282            // Fixture `ErPostFalse`.
283            Self::PostconditionFalse { .. } => class(2404, "TLC_POSTCONDITION_FALSE", true),
284            // The binding stage's errors are checked against TLC;
285            // `TLC_STATES_AND_NO_NEXT_ACTION` (2115) is read from TLC's source
286            // only (`ModelChecker.java:233-245`).
287            Self::ModelError { code, name, .. } => class(*code, name, *code != 2115),
288            // Fixtures `ErInitIncomplete` and `ErNextIncomplete`.
289            Self::NotCompletelySpecified { initial: true, .. } => {
290                class(2102, "TLC_INITIAL_STATE", true)
291            }
292            Self::NotCompletelySpecified { initial: false, .. } => {
293                class(2109, "TLC_STATE_NOT_COMPLETELY_SPECIFIED_NEXT", true)
294            }
295            // The error-class table (`class.rs`) decides the code and
296            // whether it is verified.
297            Self::EvaluationError {
298                site,
299                code,
300                name,
301                reported,
302                verified,
303                cause,
304                ..
305            } => {
306                if crate::class::init_primary_general(*site, *code, *reported, *verified, cause) {
307                    TlcClass {
308                        code: 1000,
309                        name: "GENERAL".to_owned(),
310                        exit: 75,
311                        reported: 1000,
312                        verified: true,
313                    }
314                } else {
315                    TlcClass {
316                        reported: *reported,
317                        ..class(*code, name, *verified)
318                    }
319                }
320            }
321            Self::Unsupported { .. }
322            | Self::ResourceLimit { .. }
323            | Self::Stopped(_)
324            | Self::BudgetMeasurement { .. }
325            | Self::InternalError { .. } => {
326                return None;
327            }
328        })
329    }
330}
331
332/// TLC's exit status for a deciding message code
333/// (`EC.ExitStatus.errorConstantToExitStatus`, tlaplus `94d0c50`).
334#[must_use]
335pub const fn tlc_exit_status(code: u32) -> u8 {
336    match code {
337        2193 => 0,
338        2253 => 77,
339        2103 | 2109 | 2115 | 2147 => 75,
340        2111 | 2146 => 76,
341        2107 | 2110 => 12,
342        2108 | 2112 | 2113 | 2116 => 13,
343        2114 => 11,
344        2104 | 2105 | 2404 | 2405 | 2780 => 10,
345        2132 => 14,
346        2171 | 3002 => 150,
347        2222..=2245 | 2272..=2274 | 2280 | 2281 | 5001..=5007 => 151,
348        _ => 255,
349    }
350}
351
352/// State-space statistics.
353#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
354pub struct Stats {
355    /// States generated, duplicates and states outside the model included.
356    pub generated: u64,
357    /// Distinct states found.
358    pub distinct: u64,
359    /// States left on the queue.
360    pub left_on_queue: u64,
361    /// The depth of the search, as TLC reports it.
362    pub depth: u64,
363    /// Initial states generated.
364    pub initial_generated: u64,
365}
366
367/// One state of a counterexample.
368#[derive(Clone, Debug)]
369pub struct TraceState {
370    /// TLC's label: `<Initial predicate>` or the action's location label.
371    pub label: String,
372    /// The action's name, when the state was produced by a named action.
373    pub action: Option<String>,
374    /// The state's values, by `VarId`. Empty for a state that leaves
375    /// variables unassigned; `partial` retains its structured bindings.
376    pub values: Vec<Value>,
377    /// TLC's text of a state that leaves variables unassigned (`null` for
378    /// them), the last state of a `TLC_STATE_NOT_COMPLETELY_SPECIFIED_NEXT`
379    /// counterexample; `None` otherwise.
380    pub text: Option<String>,
381    /// Structured terminal bindings, kept separate from complete state values.
382    /// `None` entries are unassigned, never ordinary TLA values.
383    pub partial: Option<PartialState>,
384}
385
386/// The observed incomplete candidate and the action that actually emitted it.
387#[derive(Clone, Debug, PartialEq, Eq)]
388pub struct PartialState {
389    /// Bindings by variable id; absent assignments remain absent.
390    pub values: Vec<Option<Value>>,
391    /// Original generating expression, in the result's source IR.
392    pub expression: dive_ir::ExprId,
393}
394
395/// A counterexample: a finite behavior prefix.
396#[derive(Clone, Debug, Default)]
397pub struct Counterexample {
398    /// The states, from an initial state.
399    pub states: Vec<TraceState>,
400}
401
402/// The original initial-state diagnostic context, not a formal counterexample.
403/// Its values and named underlying error still require independent replay;
404/// neither this typed transport nor a reported wrapper supplies proof.
405#[derive(Clone, Debug)]
406pub struct DiagnosticWitness {
407    #[doc(hidden)]
408    pub states: Vec<TraceState>,
409}
410
411impl DiagnosticWitness {
412    /// The actual recorded diagnostic states, in generation order.
413    #[must_use]
414    pub fn states(&self) -> &[TraceState] {
415        &self.states
416    }
417}
418
419/// The fingerprint-collision figures TLC prints on success, as their text.
420#[derive(Clone, Debug, PartialEq, Eq)]
421pub struct Collision {
422    /// "calculated (optimistic)".
423    pub optimistic: String,
424    /// "based on the actual fingerprints", when TLC computes it.
425    pub actual: Option<String>,
426}
427
428/// Evidence for the separately budgeted transient predecessor log.
429#[derive(Clone, Debug, Default, PartialEq, Eq)]
430pub struct PredecessorUsage {
431    /// Retained capacity/confirmed complete disk writes before cleanup.
432    pub storage: dive_store::predecessor::Usage,
433    /// Explicit storage/reconstruction/cleanup failures.
434    pub failures: Vec<String>,
435    /// Search event reached before storage prevented certification.
436    pub deciding_event_before_failure: Option<String>,
437    /// Explicit cleanup completed. False for an unstarted or failed close.
438    pub cleanup_completed: bool,
439}
440
441/// The result of a check.
442#[derive(Clone, Debug)]
443pub struct CheckResult {
444    /// Original declared symmetry and effective temporal policy after binding.
445    /// `None` means no model was successfully bound.
446    pub symmetry_liveness: Option<dive_model::SymmetryLivenessResolution>,
447    /// Opt-in transient disk seen-state operation and explicit cleanup facts.
448    pub seen: Option<crate::SeenUsage>,
449    /// Frontier-only encoded/disk retention and cleanup evidence.
450    pub frontier: crate::FrontierUsage,
451    /// Predecessor storage evidence; not a bound on total search memory.
452    pub predecessor: PredecessorUsage,
453    /// The verdict.
454    pub verdict: Verdict,
455    /// Whether a model error originated during binding or symmetry preparation,
456    /// before the engine started. Engine model errors leave this false.
457    pub binding_model_error: bool,
458    /// Statistics at the stop, when the search started.
459    pub stats: Option<Stats>,
460    /// Whether TLC prints statistics for this result. TLC prints none for a
461    /// stop while generating initial states (`ModelChecker.java:152-160`,
462    /// probe `InitViolation`) or before the search.
463    pub tlc_prints_stats: bool,
464    /// The counterexample, for violations, deadlock and errors in a state.
465    pub counterexample: Option<Counterexample>,
466    /// Separate complete initial diagnostic context; never a behavior word.
467    pub diagnostic_witness: Option<DiagnosticWitness>,
468    /// Collision figures (fingerprint mode, on success).
469    pub collision: Option<Collision>,
470    /// The store used.
471    pub store: StoreMode,
472    /// The fingerprint polynomial index (fingerprint mode).
473    pub fp_index: Option<usize>,
474    /// Whether the fingerprints are TLC's own (`--compat=tlc`) or dive's.
475    pub tlc_fingerprints: bool,
476    /// The variable names, by `VarId`.
477    pub var_names: Vec<String>,
478    /// TLC's variable order, as `VarId` indices: states print in it.
479    pub tlc_var_order: Vec<usize>,
480    /// `Print`/`PrintT` output, in order (start-up, assumptions, search).
481    pub output: Vec<String>,
482    /// TLC's warnings while processing the model: code and text.
483    pub warnings: Vec<(u32, String)>,
484    /// Notes for the user: anything that qualifies the result.
485    pub notes: Vec<String>,
486    /// The worker threads requested and used. Thread fields: the only part
487    /// of a result, with [`CheckResult::elapsed`], that may differ between
488    /// worker counts.
489    pub workers: Workers,
490    /// Wall-clock time of the check (binding and search).
491    pub elapsed: Duration,
492}
493
494/// Worker threads requested and used.
495#[derive(Clone, Debug, PartialEq, Eq)]
496pub struct Workers {
497    /// Requested (`--workers`).
498    pub requested: usize,
499    /// Used for the search: at most the requested count, 1 in sequential
500    /// mode, fewer if the system would not start more threads, 0 when the
501    /// run ended before the search.
502    pub used: usize,
503    /// Whether the search ran in sequential mode: every level inline, with
504    /// one logical worker evaluating in TLC's order.
505    pub sequential: bool,
506    /// Why fewer workers were used than requested.
507    pub reason: Option<String>,
508}
509
510impl Workers {
511    /// One worker, as requested.
512    #[must_use]
513    pub const fn one() -> Self {
514        Self {
515            requested: 1,
516            used: 1,
517            sequential: false,
518            reason: None,
519        }
520    }
521}