dive-runtime 0.1.0

The run contract shared by dive's checking engines: options, budgets, results and capture evidence
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
//! The result of a check: verdict, statistics, counterexample, and how TLC
//! would classify and report it.

use std::time::Duration;

use dive_eval::EvalError;
use dive_store::StoreMode;
use dive_value::Value;

/// Where an evaluation error was raised: the phase of TLC's search it
/// belongs to. TLC's error class and exit status depend on it.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub enum ErrorSite {
    /// Processing the specification, before the assumptions.
    Startup,
    /// Evaluating an `ASSUME`.
    Assumption,
    /// Generating the initial states.
    Init,
    /// Generating the successors of a state.
    Next,
    /// Evaluating a `CONSTRAINT`.
    Constraint,
    /// Evaluating an `ACTION_CONSTRAINT`.
    ActionConstraint,
    /// Evaluating `VIEW`.
    View,
    /// Fingerprinting or encoding a state.
    Fingerprint,
    /// Evaluating an invariant.
    Invariant,
    /// Evaluating an implied initial predicate.
    ImpliedInit,
    /// Evaluating an implied action.
    ImpliedAction,
    /// Evaluating a `POSTCONDITION`.
    Postcondition,
}

impl ErrorSite {
    /// A short name for output.
    #[must_use]
    pub const fn name(self) -> &'static str {
        match self {
            Self::Startup => "startup",
            Self::Assumption => "assumption",
            Self::Init => "initial-states",
            Self::Next => "next-state",
            Self::Constraint => "constraint",
            Self::ActionConstraint => "action-constraint",
            Self::View => "view",
            Self::Fingerprint => "fingerprint",
            Self::Invariant => "invariant",
            Self::ImpliedInit => "implied-init",
            Self::ImpliedAction => "implied-action",
            Self::Postcondition => "postcondition",
        }
    }
}

/// The verdict of a check.
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum Verdict {
    /// The search finished without finding a violation.
    Success,
    /// An invariant is violated, in an initial state (`initial`) or a later
    /// one.
    InvariantViolated {
        /// The invariant, as TLC names it.
        property: String,
        /// Whether the violating state is an initial state.
        initial: bool,
    },
    /// An implied initial predicate (a state-level part of a `PROPERTY`) is
    /// violated by an initial state.
    PropertyViolatedInitially {
        /// The property.
        property: String,
    },
    /// An implied action (`[][A]_v` in a `PROPERTY`) is violated by a step.
    ActionPropertyViolated {
        /// The property.
        property: String,
    },
    /// A reachable state has no successor at all.
    Deadlock,
    /// An `ASSUME` is false.
    AssumptionFalse {
        /// The failed assumption's source image, as TLC names the property.
        property: String,
        /// TLC's message.
        message: String,
    },
    /// A `POSTCONDITION` is not `TRUE` after a complete search.
    PostconditionFalse {
        /// The postcondition.
        property: String,
        /// TLC's message (`TLC_POSTCONDITION_FALSE`).
        message: String,
    },
    /// TLC's error while processing the model (configuration, constants,
    /// start-up evaluation), as the binding stage reports it.
    ModelError {
        /// TLC's message code.
        code: u32,
        /// Its `EC` name.
        name: String,
        /// TLC's message.
        message: String,
    },
    /// A successor leaves a variable unassigned.
    NotCompletelySpecified {
        /// Whether it is an initial state.
        initial: bool,
        /// The unassigned variables.
        variables: Vec<String>,
        /// TLC's message (`TLC_STATE_NOT_COMPLETELY_SPECIFIED_NEXT`, or
        /// `TLC_INITIAL_STATE` for an initial state).
        message: String,
        /// Actual partial Init candidate, printed inside TLC's error message,
        /// separately from its absent formal counterexample.
        initial_candidate: Option<PartialState>,
    },
    /// Evaluation failed with an error TLC also raises (including a failed
    /// `Assert` and integer overflow), classified as TLC classifies it at
    /// `site` (the error-class table in `class.rs`).
    EvaluationError {
        /// Where.
        site: ErrorSite,
        /// TLC's deciding code: what its run returns, which decides its exit
        /// status (`ModelChecker.modelCheck`). After an error while
        /// exploring, TLC replays the step with its call stack recorded, and
        /// the replay decides it (`TLC_NESTED_EXPRESSION`, or the code of the
        /// `EvalException` it meets again).
        code: u32,
        /// Its `EC` name.
        name: &'static str,
        /// The code of the error message TLC prints first: the site's
        /// wrapper (`TLC_INVARIANT_EVALUATION_FAILED`, `GENERAL`, ...) or the
        /// error's own code.
        reported: u32,
        /// The text of that message, as TLC prints it.
        message: String,
        /// Whether `code` is checked against captured TLC runs for this site
        /// and this kind of error. An unverified class is reported but not
        /// claimed.
        verified: bool,
        /// The evaluation error itself.
        cause: EvalError,
        /// The invariant whose evaluation raised `cause`, retained separately
        /// from TLC's deciding error class and diagnostic replay.
        invariant: Option<String>,
    },
    /// dive refused, naming the feature. Never a verdict about the model.
    Unsupported {
        /// The feature.
        feature: String,
    },
    /// A resource limit (evaluation depth, memory) was hit. Never a verdict
    /// about the model.
    ResourceLimit {
        /// What.
        message: String,
    },
    /// The run's budget (`--time-limit`, `--max-memory`) was exhausted.
    /// Never a verdict about the model; the statistics are those
    /// at the stop.
    Stopped(Box<crate::budget::Stopped>),
    /// A required process-memory observation failed; never a model verdict.
    BudgetMeasurement {
        /// Typed measurement failure, without an invented observed byte count.
        error: crate::budget::MeasurementError,
    },
    /// An internal invariant of dive failed: a bug, never a verdict.
    InternalError {
        /// What.
        message: String,
    },
}

/// How TLC classifies a result: its observable primary code, `EC` name,
/// and physical process exit status. A source-qualified Init replay may
/// retain GENERAL as primary while its diagnostic context supplies exit 75.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TlcClass {
    /// The observable deciding message code, distinct from a replay exit code.
    pub code: u32,
    /// Its `EC` name.
    pub name: String,
    /// TLC's physical exit status, including qualified diagnostic replay paths.
    pub exit: u8,
    /// The code of the error message TLC prints first, where it differs
    /// from `code` (an evaluation error wrapped by its site); otherwise
    /// `code`.
    pub reported: u32,
    /// Whether dive reproduces TLC's class here, checked against a captured
    /// TLC run. An unverified class is reported but not claimed.
    pub verified: bool,
}

impl Verdict {
    /// The verdict's kebab-case name in dive's output.
    #[must_use]
    pub const fn kind(&self) -> &'static str {
        match self {
            Self::Success => "success",
            Self::InvariantViolated { .. } => "invariant-violation",
            Self::PropertyViolatedInitially { .. } => "property-violation",
            Self::ActionPropertyViolated { .. } => "action-property-violation",
            Self::Deadlock => "deadlock",
            Self::AssumptionFalse { .. } => "assumption-failure",
            Self::PostconditionFalse { .. } => "postcondition-failure",
            Self::ModelError { .. } => "model-error",
            Self::NotCompletelySpecified { .. } => "incomplete-state",
            Self::EvaluationError { code: 2132, .. } => "assertion-failure",
            Self::EvaluationError {
                code: 2178 | 2265, ..
            } => "overflow",
            Self::EvaluationError { .. } => "evaluation-error",
            Self::Unsupported { .. } => "unsupported",
            Self::ResourceLimit { .. } => "resource-limit",
            Self::Stopped(_) => "stopped",
            Self::InternalError { .. } | Self::BudgetMeasurement { .. } => "internal-error",
        }
    }

    /// The violated property, where there is one.
    #[must_use]
    pub fn property(&self) -> Option<&str> {
        match self {
            Self::InvariantViolated { property, .. }
            | Self::PropertyViolatedInitially { property }
            | Self::ActionPropertyViolated { property }
            | Self::PostconditionFalse { property, .. }
            | Self::AssumptionFalse { property, .. } => Some(property),
            _ => None,
        }
    }

    /// Whether this is a verdict about the model (as opposed to a refusal,
    /// a resource limit or a bug).
    #[must_use]
    pub const fn is_verdict(&self) -> bool {
        !matches!(
            self,
            Self::Unsupported { .. }
                | Self::ResourceLimit { .. }
                | Self::Stopped(_)
                | Self::BudgetMeasurement { .. }
                | Self::InternalError { .. }
        )
    }

    /// TLC's classification of this verdict, where TLC has one.
    #[must_use]
    pub fn tlc(&self) -> Option<TlcClass> {
        let class = |code: u32, name: &str, verified: bool| TlcClass {
            code,
            name: name.to_owned(),
            exit: tlc_exit_status(code),
            reported: code,
            verified,
        };
        Some(match self {
            Self::Success => class(2193, "TLC_SUCCESS", true),
            Self::InvariantViolated { initial: true, .. } => {
                class(2107, "TLC_INVARIANT_VIOLATED_INITIAL", true)
            }
            Self::InvariantViolated { initial: false, .. } => {
                class(2110, "TLC_INVARIANT_VIOLATED_BEHAVIOR", true)
            }
            Self::PropertyViolatedInitially { .. } => {
                class(2108, "TLC_PROPERTY_VIOLATED_INITIAL", true)
            }
            Self::ActionPropertyViolated { .. } => {
                class(2112, "TLC_ACTION_PROPERTY_VIOLATED_BEHAVIOR", true)
            }
            Self::Deadlock => class(2114, "TLC_DEADLOCK_REACHED", true),
            Self::AssumptionFalse { .. } => class(2104, "TLC_ASSUMPTION_FALSE", true),
            // Fixture `ErPostFalse`.
            Self::PostconditionFalse { .. } => class(2404, "TLC_POSTCONDITION_FALSE", true),
            // The binding stage's errors are checked against TLC;
            // `TLC_STATES_AND_NO_NEXT_ACTION` (2115) is read from TLC's source
            // only (`ModelChecker.java:233-245`).
            Self::ModelError { code, name, .. } => class(*code, name, *code != 2115),
            // Fixtures `ErInitIncomplete` and `ErNextIncomplete`.
            Self::NotCompletelySpecified { initial: true, .. } => {
                class(2102, "TLC_INITIAL_STATE", true)
            }
            Self::NotCompletelySpecified { initial: false, .. } => {
                class(2109, "TLC_STATE_NOT_COMPLETELY_SPECIFIED_NEXT", true)
            }
            // The error-class table (`class.rs`) decides the code and
            // whether it is verified.
            Self::EvaluationError {
                site,
                code,
                name,
                reported,
                verified,
                cause,
                ..
            } => {
                if crate::class::init_primary_general(*site, *code, *reported, *verified, cause) {
                    TlcClass {
                        code: 1000,
                        name: "GENERAL".to_owned(),
                        exit: 75,
                        reported: 1000,
                        verified: true,
                    }
                } else {
                    TlcClass {
                        reported: *reported,
                        ..class(*code, name, *verified)
                    }
                }
            }
            Self::Unsupported { .. }
            | Self::ResourceLimit { .. }
            | Self::Stopped(_)
            | Self::BudgetMeasurement { .. }
            | Self::InternalError { .. } => {
                return None;
            }
        })
    }
}

/// TLC's exit status for a deciding message code
/// (`EC.ExitStatus.errorConstantToExitStatus`, tlaplus `94d0c50`).
#[must_use]
pub const fn tlc_exit_status(code: u32) -> u8 {
    match code {
        2193 => 0,
        2253 => 77,
        2103 | 2109 | 2115 | 2147 => 75,
        2111 | 2146 => 76,
        2107 | 2110 => 12,
        2108 | 2112 | 2113 | 2116 => 13,
        2114 => 11,
        2104 | 2105 | 2404 | 2405 | 2780 => 10,
        2132 => 14,
        2171 | 3002 => 150,
        2222..=2245 | 2272..=2274 | 2280 | 2281 | 5001..=5007 => 151,
        _ => 255,
    }
}

/// State-space statistics.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct Stats {
    /// States generated, duplicates and states outside the model included.
    pub generated: u64,
    /// Distinct states found.
    pub distinct: u64,
    /// States left on the queue.
    pub left_on_queue: u64,
    /// The depth of the search, as TLC reports it.
    pub depth: u64,
    /// Initial states generated.
    pub initial_generated: u64,
}

/// One state of a counterexample.
#[derive(Clone, Debug)]
pub struct TraceState {
    /// TLC's label: `<Initial predicate>` or the action's location label.
    pub label: String,
    /// The action's name, when the state was produced by a named action.
    pub action: Option<String>,
    /// The state's values, by `VarId`. Empty for a state that leaves
    /// variables unassigned; `partial` retains its structured bindings.
    pub values: Vec<Value>,
    /// TLC's text of a state that leaves variables unassigned (`null` for
    /// them), the last state of a `TLC_STATE_NOT_COMPLETELY_SPECIFIED_NEXT`
    /// counterexample; `None` otherwise.
    pub text: Option<String>,
    /// Structured terminal bindings, kept separate from complete state values.
    /// `None` entries are unassigned, never ordinary TLA values.
    pub partial: Option<PartialState>,
}

/// The observed incomplete candidate and the action that actually emitted it.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct PartialState {
    /// Bindings by variable id; absent assignments remain absent.
    pub values: Vec<Option<Value>>,
    /// Original generating expression, in the result's source IR.
    pub expression: dive_ir::ExprId,
}

/// A counterexample: a finite behavior prefix.
#[derive(Clone, Debug, Default)]
pub struct Counterexample {
    /// The states, from an initial state.
    pub states: Vec<TraceState>,
}

/// The original initial-state diagnostic context, not a formal counterexample.
/// Its values and named underlying error still require independent replay;
/// neither this typed transport nor a reported wrapper supplies proof.
#[derive(Clone, Debug)]
pub struct DiagnosticWitness {
    #[doc(hidden)]
    pub states: Vec<TraceState>,
}

impl DiagnosticWitness {
    /// The actual recorded diagnostic states, in generation order.
    #[must_use]
    pub fn states(&self) -> &[TraceState] {
        &self.states
    }
}

/// The fingerprint-collision figures TLC prints on success, as their text.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Collision {
    /// "calculated (optimistic)".
    pub optimistic: String,
    /// "based on the actual fingerprints", when TLC computes it.
    pub actual: Option<String>,
}

/// Evidence for the separately budgeted transient predecessor log.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct PredecessorUsage {
    /// Retained capacity/confirmed complete disk writes before cleanup.
    pub storage: dive_store::predecessor::Usage,
    /// Explicit storage/reconstruction/cleanup failures.
    pub failures: Vec<String>,
    /// Search event reached before storage prevented certification.
    pub deciding_event_before_failure: Option<String>,
    /// Explicit cleanup completed. False for an unstarted or failed close.
    pub cleanup_completed: bool,
}

/// The result of a check.
#[derive(Clone, Debug)]
pub struct CheckResult {
    /// Original declared symmetry and effective temporal policy after binding.
    /// `None` means no model was successfully bound.
    pub symmetry_liveness: Option<dive_model::SymmetryLivenessResolution>,
    /// Opt-in transient disk seen-state operation and explicit cleanup facts.
    pub seen: Option<crate::SeenUsage>,
    /// Frontier-only encoded/disk retention and cleanup evidence.
    pub frontier: crate::FrontierUsage,
    /// Predecessor storage evidence; not a bound on total search memory.
    pub predecessor: PredecessorUsage,
    /// The verdict.
    pub verdict: Verdict,
    /// Whether a model error originated during binding or symmetry preparation,
    /// before the engine started. Engine model errors leave this false.
    pub binding_model_error: bool,
    /// Statistics at the stop, when the search started.
    pub stats: Option<Stats>,
    /// Whether TLC prints statistics for this result. TLC prints none for a
    /// stop while generating initial states (`ModelChecker.java:152-160`,
    /// probe `InitViolation`) or before the search.
    pub tlc_prints_stats: bool,
    /// The counterexample, for violations, deadlock and errors in a state.
    pub counterexample: Option<Counterexample>,
    /// Separate complete initial diagnostic context; never a behavior word.
    pub diagnostic_witness: Option<DiagnosticWitness>,
    /// Collision figures (fingerprint mode, on success).
    pub collision: Option<Collision>,
    /// The store used.
    pub store: StoreMode,
    /// The fingerprint polynomial index (fingerprint mode).
    pub fp_index: Option<usize>,
    /// Whether the fingerprints are TLC's own (`--compat=tlc`) or dive's.
    pub tlc_fingerprints: bool,
    /// The variable names, by `VarId`.
    pub var_names: Vec<String>,
    /// TLC's variable order, as `VarId` indices: states print in it.
    pub tlc_var_order: Vec<usize>,
    /// `Print`/`PrintT` output, in order (start-up, assumptions, search).
    pub output: Vec<String>,
    /// TLC's warnings while processing the model: code and text.
    pub warnings: Vec<(u32, String)>,
    /// Notes for the user: anything that qualifies the result.
    pub notes: Vec<String>,
    /// The worker threads requested and used. Thread fields: the only part
    /// of a result, with [`CheckResult::elapsed`], that may differ between
    /// worker counts.
    pub workers: Workers,
    /// Wall-clock time of the check (binding and search).
    pub elapsed: Duration,
}

/// Worker threads requested and used.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Workers {
    /// Requested (`--workers`).
    pub requested: usize,
    /// Used for the search: at most the requested count, 1 in sequential
    /// mode, fewer if the system would not start more threads, 0 when the
    /// run ended before the search.
    pub used: usize,
    /// Whether the search ran in sequential mode: every level inline, with
    /// one logical worker evaluating in TLC's order.
    pub sequential: bool,
    /// Why fewer workers were used than requested.
    pub reason: Option<String>,
}

impl Workers {
    /// One worker, as requested.
    #[must_use]
    pub const fn one() -> Self {
        Self {
            requested: 1,
            used: 1,
            sequential: false,
            reason: None,
        }
    }
}