dive_trace/lib.rs
1//! `dive-trace`: the counterexample format and the independent trace
2//! validator.
3//!
4//! The validator checks a counterexample *as data* against a bound
5//! [`dive_model::Model`]: that its first state satisfies the initial
6//! predicate, that every step satisfies the next-state relation, evaluated as
7//! a predicate over the two given states, that the states the search must
8//! have explored are inside the model and violate nothing earlier, and that
9//! the trace ends as it claims. It shares only the dive-eval evaluator, the
10//! value library and the binding stage with the checker, never the search,
11//! store or liveness graph. This is deliberate: code such as the scoped
12//! temporal walk in [`mod@temporal`] duplicates what `dive-liveness` does
13//! rather than sharing it, so that a checker bug cannot also hide itself from
14//! validation. Whether a state has a successor (`ENABLED`, deadlock and
15//! fairness) is the dive-eval evaluator's `ENABLED`; the states and
16//! steps of the counterexample are still replayed and checked here.
17//!
18//! Named pure periodic words (`TraceDoc::with_properties`) also check all
19//! behavior temporal conjuncts and the complete violated-property set.
20//! Fairness is decided with the dive-eval evaluator's `ENABLED`. VIEW/symmetry
21//! closing evidence and unnamed periodic claims from older documents remain explicit
22//! refusals.
23//!
24//! - [`mod@format`]: the versioned trace format (also TLC's `-dumpTrace json`).
25//! - [`value_json`]: dive's tagged JSON values, with documented representation
26//! and mixed-set round-trip limitations.
27//! - [`validate()`]: the checks, giving [`Validation::Valid`],
28//! [`Validation::Invalid`] (the first failing state and check) or
29//! [`Validation::Unsupported`] (naming what cannot be checked). A random
30//! draw is refused by name ([`RANDOM_UNSUPPORTED`]), and so is a string
31//! created at run time when strings follow encounter order
32//! ([`RUNTIME_NAMES_UNSUPPORTED`]).
33//! TLC register reads and writes are refused ([`REGISTERS_UNSUPPORTED`])
34//! because their contents can depend on evaluations outside the trace.
35//! [`Session`] reconstructs immutable source/config inputs privately and
36//! supports startup registers through a single-candidate Init operation;
37//! every later register access retains that refusal.
38//! - [`tlc`]: reading TLC's lossy JSON by interpretation.
39//! - [`mutate`]: by-construction invalid mutants, the negative controls.
40//!
41//! Evaluation recurses on the caller's stack: run validation on a thread
42//! with [`dive_eval::RECOMMENDED_STACK`], as `dive-api` does.
43//!
44//! # Example
45//!
46//! ```
47//! use std::sync::Arc;
48//! use dive_trace::{TraceDoc, Validation, validate_doc};
49//!
50//! let src = "---- MODULE M ----\nEXTENDS Naturals\nVARIABLE x\n\
51//! Init == x = 0\nNext == x' = x + 1\nInv == x < 2\n====\n";
52//! let analysis = dive_sema::analyze_source("M.tla", src, &dive_sema::Options::default());
53//! let ir = Arc::new(dive_ir::lower(&analysis).unwrap());
54//! let cfg = dive_config::parse("INIT Init\nNEXT Next\nINVARIANT Inv\n").into_config().unwrap();
55//! let model = dive_model::bind(ir, &cfg, &dive_model::BindOptions::tlc()).unwrap();
56//!
57//! let doc = TraceDoc::parse(r#"{"format": "dive-trace", "version": 1, "variables": ["x"],
58//! "states": [{"action": null, "values": {"x": 0}},
59//! {"action": {"name": "Next"}, "values": {"x": 1}},
60//! {"action": {"name": "Next"}, "values": {"x": 2}}],
61//! "ending": {"kind": "invariant", "name": "Inv"}}"#).unwrap();
62//! let (report, _) = validate_doc(&model, &doc, &cfg.model_values);
63//! assert_eq!(report.validation, Validation::Valid);
64//!
65//! // Skipping a state is not a step of the specification.
66//! let doc = TraceDoc::behavior(vec![
67//! serde_json::json!({"x": 0}),
68//! serde_json::json!({"x": 2}),
69//! ]).unwrap();
70//! let (report, _) = validate_doc(&model, &doc, &cfg.model_values);
71//! let Validation::Invalid(failure) = report.validation else { panic!() };
72//! assert_eq!((failure.state, failure.check), (1, dive_trace::Check::Next));
73//! ```
74#![forbid(unsafe_code)]
75
76mod candidate_error;
77mod choices;
78pub mod enabled;
79mod endpoint;
80pub mod format;
81mod initial;
82mod invariant_error;
83pub mod mutate;
84mod next_error;
85mod next_temporal;
86mod ordered;
87mod ordered_prefix;
88mod partial;
89mod row_demand;
90mod session;
91mod source_row;
92pub mod temporal;
93pub mod tlc;
94mod trace;
95mod validate;
96pub mod value_json;
97
98use dive_model::Model;
99
100pub use endpoint::{
101 CandidateErrorSite, CandidateStateEndpoint, NextStateEndpoint, PartialNextEndpoint,
102 PartialStateEndpoint, TemporalSourceEndpoint, TemporalStateEndpoint, ViewSourceEndpoint,
103};
104pub use format::{Ending, Label, Source, TraceDoc};
105pub use invariant_error::{InitialErrorStage, InitialInvariantClass};
106pub use ordered_prefix::InvariantErrorClass;
107pub use session::Session;
108pub use trace::{ShapeError, State, Trace, variables};
109pub use validate::{
110 COMPOSITION_UNSUPPORTED, Check, DEADLOCK_UNSUPPORTED, Failure, RANDOM_UNSUPPORTED,
111 REGISTERS_UNSUPPORTED, RUNTIME_NAMES_UNSUPPORTED, Report, Validation, ValidationProgress,
112 ValidationRunError, validate, validate_controlled,
113};
114
115/// Reads a document in either format against `model` and validates it.
116/// `model_values` are the configuration's model value names
117/// (`dive_config::ModelConfig::model_values`), which reading TLC's format
118/// needs. Returns the report and the trace as read (for a TLC document, the
119/// interpretation the verdict is about; see [`tlc`]). Random draws are refused
120/// by name ([`RANDOM_UNSUPPORTED`]).
121#[must_use]
122pub fn validate_doc(
123 model: &Model,
124 doc: &TraceDoc,
125 model_values: &[String],
126) -> (Report, Option<Trace>) {
127 // Decoding uses public variable metadata too, so validate structural
128 // ownership before reading either document format, not only at replay.
129 if let Err(error) = model.validate_context() {
130 return (
131 Report {
132 validation: Validation::Unsupported(error.to_string()),
133 notes: Vec::new(),
134 length: doc.states.len(),
135 },
136 None,
137 );
138 }
139 match doc.source {
140 Source::Tlc => {
141 let r = tlc::validate_tlc(model, doc, model_values);
142 (r.report, r.trace)
143 }
144 Source::Dive => match Trace::decode(model, doc) {
145 Ok(t) => (validate(model, &t), Some(t)),
146 Err(e) => (
147 validate::guard_runtime_names(
148 model,
149 Report {
150 validation: Validation::Invalid(Failure {
151 state: e.state.unwrap_or(0),
152 check: Check::Shape,
153 detail: e.detail,
154 }),
155 notes: Vec::new(),
156 length: doc.states.len(),
157 },
158 ),
159 None,
160 ),
161 },
162 }
163}