Skip to main content

dive_trace/
format.rs

1//! Counterexample transports: dive's format (versions 1 through 6) and TLC's JSON.
2//!
3//! # dive's format
4//!
5//! ```json
6//! {
7//!   "format": "dive-trace",
8//!   "version": 1,
9//!   "variables": ["big", "small"],
10//!   "states": [
11//!     {"action": null, "values": {"big": 0, "small": 0}},
12//!     {"action": {"name": "FillBigJug", "location": "line 68, col 18 to line 69, col 34 of module DieHard"},
13//!      "values": {"big": 5, "small": 0}}
14//!   ],
15//!   "ending": {"kind": "invariant", "name": "NotSolved"}
16//! }
17//! ```
18//!
19//! - `variables` lists the specification's variables. Every state assigns
20//!   exactly these, in dive's value JSON ([`crate::value_json`]).
21//! - `states[k].action` labels the step into state `k`: `null` for the
22//!   initial state, and optional elsewhere. `name` is the action's name as
23//!   TLC prints it, without parameters; `location` is informative.
24//! - `ending` says what the trace claims ([`Ending`]):
25//!
26//!   | `kind` | Fields | Claim |
27//!   |---|---|---|
28//!   | `invariant` | `name` | the invariant is false in the last state |
29//!   | `property` | `name` | the action property is false on the last step (or, for a one-state trace, the implied initial predicate is false in it) |
30//!   | `deadlock` | | the last state has no successor |
31//!   | `behavior` | | nothing beyond being a behavior of the specification (implementation traces) |
32//!   | `lasso` | `back_to` | the last state's successor is state `back_to` (0-based); a liveness counterexample |
33//!   | `stuttering` | | the behavior stutters forever after the last state |
34//!   | `assertion`, `error` | `ec` (`error`, optional) | expanding the last state fails |
35//!   | `invariant-error` | `name`, `ec` | evaluating the named invariant on the last state raises the given underlying error |
36//!
37//! The format version is the lowest one that can express the document:
38//!
39//! | Version | Adds |
40//! |---|---|
41//! | 1 | every ending kind above except `invariant-error` |
42//! | 2 | the `invariant-error` ending |
43//! | 3 | a terminal partial candidate, separate from the complete state rows |
44//! | 4 | ordered errors on the candidate side of a step |
45//! | 5 | errors in temporal-source rows after `Next` |
46//! | 6 | errors in a source-final `VIEW` evaluation |
47//!
48//! Readers accept all six versions and reject a version-1 document that uses
49//! the `invariant-error` ending. Unknown versions and ending kinds are
50//! rejected, never guessed.
51//!
52//! `invariant-error.ec` is the underlying evaluation cause. The enclosing
53//! check report retains TLC's deciding class, normally
54//! `TLC_INVARIANT_EVALUATION_FAILED` (2111), or a separately qualified
55//! diagnostic replay's class; replacing the cause with a wrapper is invalid. Validation
56//! requires the named invariant to raise exactly that cause, with all
57//! earlier states and earlier configured invariants passing.
58//!
59//! - `length` (optional) is the claimed number of states; it must match.
60//! - `properties` lists all temporal properties violated by a lasso or
61//!   stuttering word. Older documents without names remain unsupported for
62//!   liveness validation. An enclosing report's names must agree with these.
63//!
64//! `dive check --output json` embeds this object as `counterexample.trace`;
65//! [`TraceDoc::from_json`] accepts the object itself, a document that
66//! carries it as `counterexample`, or `dive check`'s report or its
67//! `counterexample` object.
68//!
69//! # TLC's format
70//!
71//! TLC's `-dumpTrace json` document (`{"vars": [...], "counterexample":
72//! {"state": [[1, {...}], ...], "action": [[[1, {...}], {"name": ...}, [2,
73//! {...}]], ...]}}`) is read too. It carries no ending, so one must be
74//! given ([`TraceDoc::with_ending`]), and its values are in TLC's lossy form,
75//! which [`crate::tlc`] interprets against the model.
76
77use serde_json::{Map, Value as J, json};
78
79/// The format name in [`TraceDoc::to_json`].
80pub const FORMAT: &str = "dive-trace";
81
82/// The base format version, still written for every ending kind that needs
83/// nothing newer.
84pub const VERSION: u64 = 1;
85
86/// The format version required by named invariant-error endings.
87pub const INVARIANT_ERROR_VERSION: u64 = 2;
88
89/// Version for a terminal partial candidate separate from complete prefix rows.
90pub const PARTIAL_STATE_VERSION: u64 = 3;
91
92/// Version for an ordered candidate-side error with independent wrapper replay.
93pub const CANDIDATE_ERROR_VERSION: u64 = 4;
94
95/// Version for an independently replayed post-Next temporal-source-row error.
96pub const TEMPORAL_SOURCE_ERROR_VERSION: u64 = 5;
97
98/// Version for a source-final VIEW demand with independently reconstructed keys.
99pub const VIEW_SOURCE_ERROR_VERSION: u64 = 6;
100
101/// What a trace claims about its end.
102#[derive(Clone, Debug, PartialEq, Eq)]
103#[non_exhaustive]
104pub enum Ending {
105    /// The named invariant is false in the last state.
106    Invariant(String),
107    /// The named action property is false on the last step; for a
108    /// one-state trace, the named implied initial predicate is false in it.
109    Property(String),
110    /// The last state has no successor.
111    Deadlock,
112    /// No violation: the trace is a behavior of the specification.
113    Behavior,
114    /// A liveness counterexample that loops back to state `back_to`
115    /// (0-based).
116    Lasso {
117        /// The state the last state's successor equals.
118        back_to: usize,
119    },
120    /// A liveness counterexample that stutters after the last state.
121    Stuttering,
122    /// An assertion fails while the last state is expanded.
123    Assertion,
124    /// An evaluation error while the last state is expanded.
125    Error {
126        /// TLC's error class, if known (`EC` name).
127        ec: Option<String>,
128    },
129    /// The named invariant fails to evaluate in the last state. Earlier
130    /// invariants and earlier states must pass. `ec` names the underlying
131    /// error, not TLC's `TLC_INVARIANT_EVALUATION_FAILED` wrapper.
132    InvariantError {
133        /// The configured invariant name.
134        name: String,
135        /// The underlying evaluation error's `EC` name.
136        ec: String,
137    },
138    /// A source-state demand error, checked only by a fresh source-bound session.
139    /// Its descriptor requests independent replay, never grants authority.
140    TemporalStateError {
141        /// The expected TLC evaluation error class.
142        ec: String,
143        /// Untrusted stage and original inner source context.
144        endpoint: crate::TemporalStateEndpoint,
145    },
146    /// A post-Next row error with independently reconstructed primary lifecycle.
147    TemporalSourceError {
148        /// Untrusted underlying row-error class, distinct from outer wrappers.
149        ec: String,
150        /// Original row-error source only; fresh replay supplies all authority.
151        endpoint: crate::TemporalSourceEndpoint,
152    },
153    /// Next raises this underlying error before emitting any successor.
154    /// Only fresh source-bound replay can establish the original context.
155    NextStateError {
156        /// The underlying evaluation error class, never a replay wrapper.
157        ec: String,
158        /// Untrusted original source context.
159        endpoint: crate::NextStateEndpoint,
160    },
161    /// A generated final candidate raises an independently replayed error.
162    CandidateStateError {
163        /// Underlying primary error, distinct from the deciding wrapper.
164        ec: String,
165        /// Untrusted actual site, original source and both wrapper identities.
166        endpoint: crate::CandidateStateEndpoint,
167    },
168    /// A VIEW demand fails on an independently generated candidate; the last
169    /// complete row is its source, never the absent failing candidate.
170    ViewSourceError {
171        /// Underlying primary error, distinct from the diagnostic wrapper.
172        ec: String,
173        /// Untrusted original source and both exception identities.
174        endpoint: crate::ViewSourceEndpoint,
175    },
176    /// An actual incomplete Next candidate, separately replayed from its prefix.
177    PartialNext {
178        /// Untrusted source context and assigned/unassigned bindings.
179        endpoint: crate::PartialNextEndpoint,
180    },
181    /// An actual partial Init candidate, with no complete prefix state.
182    PartialInit {
183        /// Untrusted observed bindings/source, requiring fresh Init generation.
184        endpoint: crate::PartialStateEndpoint,
185    },
186}
187
188impl Ending {
189    /// The JSON form.
190    #[must_use]
191    pub fn to_json(&self) -> J {
192        match self {
193            Self::Invariant(n) => json!({"kind": "invariant", "name": n}),
194            Self::Property(n) => json!({"kind": "property", "name": n}),
195            Self::Deadlock => json!({"kind": "deadlock"}),
196            Self::Behavior => json!({"kind": "behavior"}),
197            Self::Lasso { back_to } => json!({"kind": "lasso", "back_to": back_to}),
198            Self::Stuttering => json!({"kind": "stuttering"}),
199            Self::Assertion => json!({"kind": "assertion"}),
200            Self::Error { ec } => json!({"kind": "error", "ec": ec}),
201            Self::InvariantError { name, ec } => {
202                json!({"kind": "invariant-error", "name": name, "ec": ec})
203            }
204            Self::TemporalStateError { ec, endpoint } => {
205                json!({"kind":"error", "ec":ec, "endpoint":endpoint.to_json()})
206            }
207            Self::TemporalSourceError { ec, endpoint } => {
208                json!({"kind":"error", "ec":ec, "endpoint":endpoint.to_json()})
209            }
210            Self::ViewSourceError { ec, endpoint } => {
211                json!({"kind":"error", "ec":ec, "endpoint":endpoint.to_json()})
212            }
213            Self::CandidateStateError { ec, endpoint } => {
214                json!({"kind":"error", "ec":ec, "endpoint":endpoint.to_json()})
215            }
216            Self::NextStateError { ec, endpoint } => {
217                json!({"kind":"error", "ec":ec, "endpoint":endpoint.to_json()})
218            }
219            Self::PartialNext { endpoint } => {
220                json!({"kind":"partial-state", "ec":"TLC_STATE_NOT_COMPLETELY_SPECIFIED_NEXT", "endpoint":endpoint.to_json()})
221            }
222            Self::PartialInit { endpoint } => {
223                json!({"kind":"partial-state","ec":"TLC_INITIAL_STATE","endpoint":endpoint.to_json()})
224            }
225        }
226    }
227
228    /// Reads the JSON form.
229    ///
230    /// # Errors
231    /// For an unknown kind or a missing field.
232    #[allow(
233        clippy::too_many_lines,
234        reason = "closed endpoint variants are decoded together without fallback"
235    )]
236    pub fn from_json(j: &J) -> Result<Self, String> {
237        let kind = j
238            .get("kind")
239            .and_then(J::as_str)
240            .ok_or("an ending needs a `kind`")?;
241        if j.get("endpoint").is_some() {
242            let object = j.as_object().ok_or("ending must be an object")?;
243            if kind == "partial-state" {
244                if object.len() != 3 {
245                    return Err("partial Next ending needs its exact incomplete-state class".into());
246                }
247                let endpoint = crate::PartialStateEndpoint::from_json(&j["endpoint"])?;
248                return match (endpoint.initial(), j["ec"].as_str()) {
249                    (false, Some("TLC_STATE_NOT_COMPLETELY_SPECIFIED_NEXT")) => {
250                        Ok(Self::PartialNext { endpoint })
251                    }
252                    (true, Some("TLC_INITIAL_STATE")) => Ok(Self::PartialInit { endpoint }),
253                    _ => Err("partial terminal phase and error class disagree".into()),
254                };
255            }
256            if kind != "error" || object.len() != 3 || !object.contains_key("ec") {
257                return Err("endpoint requires an exact error ending".into());
258            }
259            if j["endpoint"]["stage"] == "temporal-source-row" {
260                return Ok(Self::TemporalSourceError {
261                    ec: j["ec"]
262                        .as_str()
263                        .filter(|ec| !ec.is_empty())
264                        .ok_or("temporal source endpoint needs an underlying error class")?
265                        .to_owned(),
266                    endpoint: crate::TemporalSourceEndpoint::from_json(&j["endpoint"])?,
267                });
268            }
269            if j["endpoint"]["stage"] == "view-source-terminal" {
270                return Ok(Self::ViewSourceError {
271                    ec: j["ec"]
272                        .as_str()
273                        .filter(|ec| !ec.is_empty())
274                        .ok_or("VIEW endpoint needs an underlying error class")?
275                        .to_owned(),
276                    endpoint: crate::ViewSourceEndpoint::from_json(&j["endpoint"])?,
277                });
278            }
279            if j["endpoint"]["stage"] == "candidate-ordered-terminal" {
280                return Ok(Self::CandidateStateError {
281                    ec: j["ec"]
282                        .as_str()
283                        .filter(|ec| !ec.is_empty())
284                        .ok_or("candidate endpoint needs an underlying error class")?
285                        .to_owned(),
286                    endpoint: crate::CandidateStateEndpoint::from_json(&j["endpoint"])?,
287                });
288            }
289            if matches!(
290                j["endpoint"]["stage"].as_str(),
291                Some("next-before-successor" | "next-ordered-terminal")
292            ) {
293                return Ok(Self::NextStateError {
294                    ec: j["ec"]
295                        .as_str()
296                        .filter(|ec| !ec.is_empty())
297                        .ok_or("a Next endpoint needs an underlying error class")?
298                        .to_owned(),
299                    endpoint: crate::NextStateEndpoint::from_json(&j["endpoint"])?,
300                });
301            }
302            let ec = j["ec"]
303                .as_str()
304                .filter(|ec| matches!(*ec, "TLC_MODULE_DIVISION_BY_ZERO" | "TLC_MODULE_EVALUATING"))
305                .ok_or("unsupported temporal endpoint error class")?
306                .to_owned();
307            return Ok(Self::TemporalStateError {
308                ec,
309                endpoint: crate::TemporalStateEndpoint::from_json(&j["endpoint"])?,
310            });
311        }
312        let name = || {
313            j.get("name")
314                .and_then(J::as_str)
315                .map(str::to_owned)
316                .ok_or_else(|| format!("a `{kind}` ending needs a `name`"))
317        };
318        Ok(match kind {
319            "invariant" => Self::Invariant(name()?),
320            "property" => Self::Property(name()?),
321            "deadlock" => Self::Deadlock,
322            "behavior" => Self::Behavior,
323            "lasso" => Self::Lasso {
324                back_to: j
325                    .get("back_to")
326                    .and_then(J::as_u64)
327                    .and_then(|n| usize::try_from(n).ok())
328                    .ok_or("a `lasso` ending needs `back_to`")?,
329            },
330            "stuttering" => Self::Stuttering,
331            "assertion" => Self::Assertion,
332            "error" => Self::Error {
333                ec: j.get("ec").and_then(J::as_str).map(str::to_owned),
334            },
335            "invariant-error" => Self::InvariantError {
336                name: name()?,
337                ec: j
338                    .get("ec")
339                    .and_then(J::as_str)
340                    .filter(|ec| !ec.is_empty())
341                    .ok_or("an invariant-error ending needs an underlying `ec`")?
342                    .to_owned(),
343            },
344            other => return Err(format!("unknown ending kind `{other}`")),
345        })
346    }
347
348    /// The ending of a TLC counterexample reported with error class `class`
349    /// (TLC's `EC` name) and violated property `property`. A temporal
350    /// property violation needs the trace's loop, which TLC reports
351    /// separately: `back_to` is the state its lasso returns to (0-based), or
352    /// `None` for stuttering.
353    #[must_use]
354    pub fn from_tlc(class: &str, property: Option<&str>, back_to: Option<usize>) -> Option<Self> {
355        let named = || property.map(str::to_owned);
356        Some(match class {
357            "TLC_INVARIANT_VIOLATED_INITIAL" | "TLC_INVARIANT_VIOLATED_BEHAVIOR" => {
358                Self::Invariant(named()?)
359            }
360            "TLC_PROPERTY_VIOLATED_INITIAL" | "TLC_ACTION_PROPERTY_VIOLATED_BEHAVIOR" => {
361                Self::Property(named()?)
362            }
363            "TLC_DEADLOCK_REACHED" => Self::Deadlock,
364            "TLC_TEMPORAL_PROPERTY_VIOLATED" => match back_to {
365                Some(back_to) => Self::Lasso { back_to },
366                None => Self::Stuttering,
367            },
368            "TLC_VALUE_ASSERT_FAILED" => Self::Assertion,
369            other => Self::Error {
370                ec: Some(other.to_owned()),
371            },
372        })
373    }
374
375    /// Parses the command-line form: `invariant:NAME`, `property:NAME`,
376    /// `deadlock`, `behavior`, `lasso:K`, `stuttering`, `assertion`,
377    /// `error[:EC]`.
378    ///
379    /// # Errors
380    /// For anything else.
381    pub fn parse(text: &str) -> Result<Self, String> {
382        let (kind, arg) = match text.split_once(':') {
383            Some((k, a)) => (k, Some(a)),
384            None => (text, None),
385        };
386        let mut j = json!({ "kind": kind });
387        if let Some(a) = arg {
388            match kind {
389                "lasso" => {
390                    j["back_to"] = J::from(
391                        a.parse::<u64>()
392                            .map_err(|_| format!("`{a}` is not a state index"))?,
393                    );
394                }
395                "error" => j["ec"] = J::from(a),
396                _ => j["name"] = J::from(a),
397            }
398        }
399        Self::from_json(&j)
400    }
401}
402
403/// The label of a step.
404#[derive(Clone, Debug, PartialEq, Eq)]
405pub struct Label {
406    /// The action's name, without parameters.
407    pub name: String,
408    /// Its location, as given.
409    pub location: Option<String>,
410}
411
412/// Which format a document was read from.
413#[derive(Clone, Copy, Debug, PartialEq, Eq)]
414#[non_exhaustive]
415pub enum Source {
416    /// dive's format.
417    Dive,
418    /// TLC's `-dumpTrace json`: values are in TLC's lossy form.
419    Tlc,
420}
421
422/// A counterexample as data, before its values are read against a model.
423#[derive(Clone, Debug, PartialEq)]
424pub struct TraceDoc {
425    /// The variables, as listed by the document.
426    pub variables: Vec<String>,
427    /// Each state's values by variable name, in the document's JSON form.
428    pub states: Vec<Map<String, J>>,
429    /// The label of the step into each state (`labels[0]` is `None`).
430    pub labels: Vec<Option<Label>>,
431    /// What the trace claims, if the document says.
432    pub ending: Option<Ending>,
433    /// The claimed number of states, if the document says.
434    pub length: Option<usize>,
435    /// The format.
436    pub source: Source,
437    /// All temporal properties claimed to be false on this periodic word.
438    /// Empty for other endings, or for an older unnamed liveness document.
439    pub properties: Vec<String>,
440}
441
442impl TraceDoc {
443    /// Logical word length, including a separate terminal partial candidate.
444    #[must_use]
445    pub fn logical_length(&self) -> usize {
446        self.states.len().saturating_add(usize::from(matches!(
447            self.ending,
448            Some(Ending::PartialNext { .. } | Ending::PartialInit { .. })
449        )))
450    }
451    /// A behavior in dive's format, from states given as JSON objects
452    /// (variable name to value, in dive's JSON form), with no labels. The
453    /// ending is [`Ending::Behavior`]: use it to check an implementation's
454    /// trace.
455    ///
456    /// # Errors
457    /// If a state is not a JSON object.
458    pub fn behavior(states: Vec<J>) -> Result<Self, String> {
459        let mut out = Vec::with_capacity(states.len());
460        for (k, s) in states.into_iter().enumerate() {
461            match s {
462                J::Object(m) => out.push(m),
463                _ => return Err(format!("state {k} is not a JSON object")),
464            }
465        }
466        let variables = out
467            .first()
468            .map(|m| m.keys().cloned().collect())
469            .unwrap_or_default();
470        let n = out.len();
471        Ok(Self {
472            variables,
473            states: out,
474            labels: vec![None; n],
475            ending: Some(Ending::Behavior),
476            length: None,
477            source: Source::Dive,
478            properties: Vec::new(),
479        })
480    }
481
482    /// This document with its ending replaced.
483    #[must_use]
484    pub fn with_ending(mut self, ending: Ending) -> Self {
485        self.ending = Some(ending);
486        self
487    }
488
489    /// Names every temporal property this periodic word claims to violate.
490    /// Validation checks the names, their truth values and completeness.
491    #[must_use]
492    pub fn with_properties(mut self, properties: Vec<String>) -> Self {
493        self.properties = properties;
494        self
495    }
496
497    /// Reads a document in dive's format (or one that carries it as
498    /// `counterexample`), or in TLC's `-dumpTrace json` format.
499    ///
500    /// # Errors
501    /// A message naming what is malformed.
502    pub fn from_json(j: &J) -> Result<Self, String> {
503        if j.get("format").and_then(J::as_str) == Some(FORMAT) {
504            return Self::from_dive(j);
505        }
506        if let Some(witness) = j.get("error_witness")
507            && witness.get("format").and_then(J::as_str) == Some(FORMAT)
508        {
509            if j.get("counterexample")
510                .is_some_and(|value| !value.is_null())
511            {
512                return Err(
513                    "a report cannot carry both a formal counterexample and an Init error witness"
514                        .into(),
515                );
516            }
517            let doc = Self::from_dive(witness)?;
518            if !matches!(doc.ending, Some(Ending::PartialInit { .. })) {
519                return Err("error_witness requires an Init partial terminal".into());
520            }
521            return Ok(doc);
522        }
523        // `dive check --output json`'s counterexample object carries the
524        // document as `trace`; accept the object or the whole report.
525        for t in [
526            j.get("trace"),
527            j.get("counterexample").and_then(|c| c.get("trace")),
528        ]
529        .into_iter()
530        .flatten()
531        {
532            if t.get("format").and_then(J::as_str) == Some(FORMAT) {
533                let mut doc = Self::from_dive(t)?;
534                let outer = j.get("counterexample").unwrap_or(j);
535                if let Some(names) = outer.get("properties") {
536                    let names =
537                        strings(Some(names)).ok_or("`properties` must be a list of names")?;
538                    let outer_set: std::collections::BTreeSet<_> = names.iter().collect();
539                    if outer_set.len() != names.len() {
540                        return Err("enclosing report repeats a temporal property name".into());
541                    }
542                    if doc.properties.is_empty() {
543                        doc.properties = names;
544                    } else if doc.properties != names {
545                        return Err("enclosing report and trace disagree on `properties`".into());
546                    }
547                }
548                return Ok(doc);
549            }
550        }
551        if let Some(c) = j.get("counterexample") {
552            if c.get("format").and_then(J::as_str) == Some(FORMAT) {
553                return Self::from_dive(c);
554            }
555            if j.get("vars").is_some() {
556                return Self::from_tlc(j);
557            }
558        }
559        Err(format!(
560            "not a trace: expected a `{FORMAT}` document or TLC's -dumpTrace json document"
561        ))
562    }
563
564    /// Reads [`TraceDoc::from_json`] from text.
565    ///
566    /// # Errors
567    /// For invalid JSON or a malformed document.
568    pub fn parse(text: &str) -> Result<Self, String> {
569        let j: J = serde_json::from_str(text).map_err(|e| format!("invalid JSON: {e}"))?;
570        Self::from_json(&j)
571    }
572
573    fn from_dive(j: &J) -> Result<Self, String> {
574        let version = j.get("version").and_then(J::as_u64);
575        if !matches!(
576            version,
577            Some(
578                VERSION
579                    | INVARIANT_ERROR_VERSION
580                    | PARTIAL_STATE_VERSION
581                    | CANDIDATE_ERROR_VERSION
582                    | TEMPORAL_SOURCE_ERROR_VERSION
583                    | VIEW_SOURCE_ERROR_VERSION
584            )
585        ) {
586            return Err(format!(
587                "unsupported {FORMAT} version {version:?}; this build reads versions {VERSION}, {INVARIANT_ERROR_VERSION}, {PARTIAL_STATE_VERSION}, {CANDIDATE_ERROR_VERSION}, {TEMPORAL_SOURCE_ERROR_VERSION} and {VIEW_SOURCE_ERROR_VERSION}"
588            ));
589        }
590        let variables = strings(j.get("variables")).ok_or("`variables` must be a list of names")?;
591        let states_j = j
592            .get("states")
593            .and_then(J::as_array)
594            .ok_or("`states` must be a list")?;
595        let mut states = Vec::with_capacity(states_j.len());
596        let mut labels = Vec::with_capacity(states_j.len());
597        for (k, s) in states_j.iter().enumerate() {
598            let values = s
599                .get("values")
600                .and_then(J::as_object)
601                .ok_or_else(|| format!("state {k} has no `values` object"))?;
602            states.push(values.clone());
603            labels.push(match s.get("action") {
604                None | Some(J::Null) => None,
605                Some(a) => Some(Label {
606                    name: a
607                        .get("name")
608                        .and_then(J::as_str)
609                        .ok_or_else(|| format!("state {k}: an action needs a `name`"))?
610                        .to_owned(),
611                    location: a.get("location").and_then(J::as_str).map(str::to_owned),
612                }),
613            });
614        }
615        let ending = match j.get("ending") {
616            None | Some(J::Null) => None,
617            Some(e) => Some(Ending::from_json(e)?),
618        };
619        if version == Some(VERSION) && matches!(ending, Some(Ending::InvariantError { .. })) {
620            return Err("`invariant-error` requires dive-trace version 2".to_owned());
621        }
622        if matches!(
623            ending,
624            Some(Ending::PartialNext { .. } | Ending::PartialInit { .. })
625        ) && version != Some(PARTIAL_STATE_VERSION)
626        {
627            return Err("a partial terminal candidate requires dive-trace version 3".into());
628        }
629        if version == Some(PARTIAL_STATE_VERSION)
630            && !matches!(
631                ending,
632                Some(Ending::PartialNext { .. } | Ending::PartialInit { .. })
633            )
634        {
635            return Err("dive-trace version 3 requires a partial terminal candidate".into());
636        }
637        if matches!(ending, Some(Ending::CandidateStateError { .. }))
638            != (version == Some(CANDIDATE_ERROR_VERSION))
639        {
640            return Err("an ordered candidate error requires exactly dive-trace version 4".into());
641        }
642        if matches!(ending, Some(Ending::ViewSourceError { .. }))
643            != (version == Some(VIEW_SOURCE_ERROR_VERSION))
644        {
645            return Err("a VIEW source error requires exactly dive-trace version 6".into());
646        }
647        if matches!(ending, Some(Ending::TemporalSourceError { .. }))
648            != (version == Some(TEMPORAL_SOURCE_ERROR_VERSION))
649        {
650            return Err("a temporal source-row error requires exactly dive-trace version 5".into());
651        }
652        let length = match j.get("length") {
653            None | Some(J::Null) => None,
654            Some(l) => Some(
655                l.as_u64()
656                    .and_then(|n| usize::try_from(n).ok())
657                    .ok_or("`length` must be a count")?,
658            ),
659        };
660        Ok(Self {
661            variables,
662            states,
663            labels,
664            ending,
665            length,
666            source: Source::Dive,
667            properties: match j.get("properties") {
668                None => Vec::new(),
669                Some(names) => {
670                    strings(Some(names)).ok_or("`properties` must be a list of names")?
671                }
672            },
673        })
674    }
675
676    fn from_tlc(j: &J) -> Result<Self, String> {
677        let variables = strings(j.get("vars")).ok_or("`vars` must be a list of names")?;
678        let cex = &j["counterexample"];
679        let state_j = cex
680            .get("state")
681            .and_then(J::as_array)
682            .ok_or("`counterexample.state` must be a list")?;
683        let mut states = Vec::with_capacity(state_j.len());
684        for (k, s) in state_j.iter().enumerate() {
685            match s.as_array().map(Vec::as_slice) {
686                Some([J::Number(n), J::Object(m)]) if n.as_u64() == Some(k as u64 + 1) => {
687                    states.push(m.clone());
688                }
689                _ => {
690                    return Err(format!(
691                        "`counterexample.state[{k}]` is not [{}, {{...}}]",
692                        k + 1
693                    ));
694                }
695            }
696        }
697        let mut labels = vec![None; states.len()];
698        let actions = cex
699            .get("action")
700            .and_then(J::as_array)
701            .map(Vec::as_slice)
702            .unwrap_or_default();
703        let count = states.len();
704        let state_at = |end: &J, at: usize| {
705            matches!(end.as_array().map(Vec::as_slice),
706                Some([J::Number(i), J::Object(m)])
707                    if i.as_u64() == Some(at as u64 + 1) && states.get(at) == Some(m))
708        };
709        for (k, a) in actions.iter().enumerate() {
710            let Some([from, label, to]) = a.as_array().map(Vec::as_slice) else {
711                return Err(format!(
712                    "`counterexample.action[{k}]` is not [from, label, to]"
713                ));
714            };
715            if k + 1 == count {
716                // A liveness counterexample's loop: from the last state back
717                // to a listed one (itself, for stuttering). The ending
718                // carries it; it must still connect listed states.
719                let back = to
720                    .get(0)
721                    .and_then(J::as_u64)
722                    .and_then(|i| usize::try_from(i).ok())
723                    .filter(|&i| i >= 1 && i <= count);
724                if !state_at(from, k) || !back.is_some_and(|i| state_at(to, i - 1)) {
725                    return Err(format!(
726                        "`counterexample.action[{k}]` is not a loop from the last state to a listed one"
727                    ));
728                }
729                continue;
730            }
731            // TLC repeats the states around each step; they must be the
732            // listed ones, or the document contradicts itself.
733            for (end, at) in [(from, k), (to, k + 1)] {
734                if !state_at(end, at) {
735                    return Err(format!(
736                        "`counterexample.action[{k}]` does not connect states {} and {}",
737                        k + 1,
738                        k + 2
739                    ));
740                }
741            }
742            labels[k + 1] = Some(Label {
743                name: label
744                    .get("name")
745                    .and_then(J::as_str)
746                    .ok_or_else(|| format!("`counterexample.action[{k}]` has no name"))?
747                    .to_owned(),
748                location: label.get("location").map(|l| match l {
749                    J::Object(m) => format!(
750                        "line {}, col {} to line {}, col {} of module {}",
751                        m.get("beginLine").unwrap_or(&J::Null),
752                        m.get("beginColumn").unwrap_or(&J::Null),
753                        m.get("endLine").unwrap_or(&J::Null),
754                        m.get("endColumn").unwrap_or(&J::Null),
755                        m.get("module").and_then(J::as_str).unwrap_or("?"),
756                    ),
757                    other => other.to_string(),
758                }),
759            });
760        }
761        if !actions.is_empty() && actions.len() + 1 != count && actions.len() != count {
762            return Err(format!(
763                "{} states but {} steps",
764                states.len(),
765                actions.len()
766            ));
767        }
768        Ok(Self {
769            variables,
770            states,
771            labels,
772            ending: None,
773            length: None,
774            source: Source::Tlc,
775            properties: Vec::new(),
776        })
777    }
778
779    /// Writes the document in dive's format. A document read from TLC's
780    /// format keeps TLC's lossy values.
781    #[must_use]
782    pub fn to_json(&self) -> J {
783        let states: Vec<J> = self
784            .states
785            .iter()
786            .zip(&self.labels)
787            .map(|(s, l)| {
788                json!({
789                    "action": l.as_ref().map(|l| json!({"name": l.name, "location": l.location})),
790                    "values": s,
791                })
792            })
793            .collect();
794        let version = if matches!(
795            self.ending,
796            Some(Ending::PartialNext { .. } | Ending::PartialInit { .. })
797        ) {
798            PARTIAL_STATE_VERSION
799        } else if matches!(self.ending, Some(Ending::CandidateStateError { .. })) {
800            CANDIDATE_ERROR_VERSION
801        } else if matches!(self.ending, Some(Ending::ViewSourceError { .. })) {
802            VIEW_SOURCE_ERROR_VERSION
803        } else if matches!(self.ending, Some(Ending::TemporalSourceError { .. })) {
804            TEMPORAL_SOURCE_ERROR_VERSION
805        } else if matches!(self.ending, Some(Ending::InvariantError { .. })) {
806            INVARIANT_ERROR_VERSION
807        } else {
808            VERSION
809        };
810        let mut j = json!({
811            "format": FORMAT,
812            "version": version,
813            "variables": self.variables,
814            "states": states,
815            "ending": self.ending.as_ref().map(Ending::to_json),
816        });
817        if let Some(n) = self.length {
818            j["length"] = J::from(n);
819        }
820        if !self.properties.is_empty() {
821            j["properties"] = J::from(self.properties.clone());
822        }
823        j
824    }
825}
826
827fn strings(j: Option<&J>) -> Option<Vec<String>> {
828    j?.as_array()?
829        .iter()
830        .map(|v| v.as_str().map(str::to_owned))
831        .collect()
832}
833
834#[cfg(test)]
835mod tests {
836    use super::*;
837
838    #[test]
839    fn reads_tlc_dump_trace_json() -> Result<(), String> {
840        let text = r#"{"counterexample":{"action":[[[1,{"x":0}],{"name":"Next","location":{"beginLine":9,"beginColumn":9,"endLine":9,"endColumn":18,"module":"M"}},[2,{"x":1}]]],"state":[[1,{"x":0}],[2,{"x":1}]]},"vars":["x"]}"#;
841        let d = TraceDoc::parse(text)?;
842        assert_eq!(d.source, Source::Tlc);
843        assert_eq!(d.states.len(), 2);
844        assert_eq!(d.labels[0], None);
845        let l = d.labels[1].clone().ok_or("label")?;
846        assert_eq!(l.name, "Next");
847        assert_eq!(
848            l.location.as_deref(),
849            Some("line 9, col 9 to line 9, col 18 of module M")
850        );
851        Ok(())
852    }
853
854    #[test]
855    fn rejects_a_tlc_document_whose_steps_do_not_connect() {
856        let text = r#"{"counterexample":{"action":[[[1,{"x":0}],{"name":"Next"},[2,{"x":5}]]],"state":[[1,{"x":0}],[2,{"x":1}]]},"vars":["x"]}"#;
857        assert!(TraceDoc::parse(text).is_err());
858    }
859
860    #[test]
861    fn dive_format_round_trips() -> Result<(), String> {
862        let text = r#"{"format":"dive-trace","version":1,"variables":["x"],
863            "states":[{"action":null,"values":{"x":0}},{"action":{"name":"A","location":null},"values":{"x":1}}],
864            "ending":{"kind":"invariant","name":"Inv"},"length":2}"#;
865        let d = TraceDoc::parse(text)?;
866        assert_eq!(d.ending, Some(Ending::Invariant("Inv".to_owned())));
867        assert_eq!(TraceDoc::from_json(&d.to_json())?, d);
868        // Embedded in a `dive check --output json` document.
869        let wrapped = json!({"schema_version": 1, "counterexample": d.to_json()});
870        assert_eq!(TraceDoc::from_json(&wrapped)?, d);
871        Ok(())
872    }
873
874    #[test]
875    fn parses_command_line_endings() -> Result<(), String> {
876        assert_eq!(
877            Ending::parse("invariant:Inv")?,
878            Ending::Invariant("Inv".into())
879        );
880        assert_eq!(Ending::parse("deadlock")?, Ending::Deadlock);
881        assert_eq!(Ending::parse("lasso:2")?, Ending::Lasso { back_to: 2 });
882        assert!(Ending::parse("invariant").is_err());
883        assert!(Ending::parse("nonsense").is_err());
884        Ok(())
885    }
886}