use serde_json::{Map, Value as J, json};
pub const FORMAT: &str = "dive-trace";
pub const VERSION: u64 = 1;
pub const INVARIANT_ERROR_VERSION: u64 = 2;
pub const PARTIAL_STATE_VERSION: u64 = 3;
pub const CANDIDATE_ERROR_VERSION: u64 = 4;
pub const TEMPORAL_SOURCE_ERROR_VERSION: u64 = 5;
pub const VIEW_SOURCE_ERROR_VERSION: u64 = 6;
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum Ending {
Invariant(String),
Property(String),
Deadlock,
Behavior,
Lasso {
back_to: usize,
},
Stuttering,
Assertion,
Error {
ec: Option<String>,
},
InvariantError {
name: String,
ec: String,
},
TemporalStateError {
ec: String,
endpoint: crate::TemporalStateEndpoint,
},
TemporalSourceError {
ec: String,
endpoint: crate::TemporalSourceEndpoint,
},
NextStateError {
ec: String,
endpoint: crate::NextStateEndpoint,
},
CandidateStateError {
ec: String,
endpoint: crate::CandidateStateEndpoint,
},
ViewSourceError {
ec: String,
endpoint: crate::ViewSourceEndpoint,
},
PartialNext {
endpoint: crate::PartialNextEndpoint,
},
PartialInit {
endpoint: crate::PartialStateEndpoint,
},
}
impl Ending {
#[must_use]
pub fn to_json(&self) -> J {
match self {
Self::Invariant(n) => json!({"kind": "invariant", "name": n}),
Self::Property(n) => json!({"kind": "property", "name": n}),
Self::Deadlock => json!({"kind": "deadlock"}),
Self::Behavior => json!({"kind": "behavior"}),
Self::Lasso { back_to } => json!({"kind": "lasso", "back_to": back_to}),
Self::Stuttering => json!({"kind": "stuttering"}),
Self::Assertion => json!({"kind": "assertion"}),
Self::Error { ec } => json!({"kind": "error", "ec": ec}),
Self::InvariantError { name, ec } => {
json!({"kind": "invariant-error", "name": name, "ec": ec})
}
Self::TemporalStateError { ec, endpoint } => {
json!({"kind":"error", "ec":ec, "endpoint":endpoint.to_json()})
}
Self::TemporalSourceError { ec, endpoint } => {
json!({"kind":"error", "ec":ec, "endpoint":endpoint.to_json()})
}
Self::ViewSourceError { ec, endpoint } => {
json!({"kind":"error", "ec":ec, "endpoint":endpoint.to_json()})
}
Self::CandidateStateError { ec, endpoint } => {
json!({"kind":"error", "ec":ec, "endpoint":endpoint.to_json()})
}
Self::NextStateError { ec, endpoint } => {
json!({"kind":"error", "ec":ec, "endpoint":endpoint.to_json()})
}
Self::PartialNext { endpoint } => {
json!({"kind":"partial-state", "ec":"TLC_STATE_NOT_COMPLETELY_SPECIFIED_NEXT", "endpoint":endpoint.to_json()})
}
Self::PartialInit { endpoint } => {
json!({"kind":"partial-state","ec":"TLC_INITIAL_STATE","endpoint":endpoint.to_json()})
}
}
}
#[allow(
clippy::too_many_lines,
reason = "closed endpoint variants are decoded together without fallback"
)]
pub fn from_json(j: &J) -> Result<Self, String> {
let kind = j
.get("kind")
.and_then(J::as_str)
.ok_or("an ending needs a `kind`")?;
if j.get("endpoint").is_some() {
let object = j.as_object().ok_or("ending must be an object")?;
if kind == "partial-state" {
if object.len() != 3 {
return Err("partial Next ending needs its exact incomplete-state class".into());
}
let endpoint = crate::PartialStateEndpoint::from_json(&j["endpoint"])?;
return match (endpoint.initial(), j["ec"].as_str()) {
(false, Some("TLC_STATE_NOT_COMPLETELY_SPECIFIED_NEXT")) => {
Ok(Self::PartialNext { endpoint })
}
(true, Some("TLC_INITIAL_STATE")) => Ok(Self::PartialInit { endpoint }),
_ => Err("partial terminal phase and error class disagree".into()),
};
}
if kind != "error" || object.len() != 3 || !object.contains_key("ec") {
return Err("endpoint requires an exact error ending".into());
}
if j["endpoint"]["stage"] == "temporal-source-row" {
return Ok(Self::TemporalSourceError {
ec: j["ec"]
.as_str()
.filter(|ec| !ec.is_empty())
.ok_or("temporal source endpoint needs an underlying error class")?
.to_owned(),
endpoint: crate::TemporalSourceEndpoint::from_json(&j["endpoint"])?,
});
}
if j["endpoint"]["stage"] == "view-source-terminal" {
return Ok(Self::ViewSourceError {
ec: j["ec"]
.as_str()
.filter(|ec| !ec.is_empty())
.ok_or("VIEW endpoint needs an underlying error class")?
.to_owned(),
endpoint: crate::ViewSourceEndpoint::from_json(&j["endpoint"])?,
});
}
if j["endpoint"]["stage"] == "candidate-ordered-terminal" {
return Ok(Self::CandidateStateError {
ec: j["ec"]
.as_str()
.filter(|ec| !ec.is_empty())
.ok_or("candidate endpoint needs an underlying error class")?
.to_owned(),
endpoint: crate::CandidateStateEndpoint::from_json(&j["endpoint"])?,
});
}
if matches!(
j["endpoint"]["stage"].as_str(),
Some("next-before-successor" | "next-ordered-terminal")
) {
return Ok(Self::NextStateError {
ec: j["ec"]
.as_str()
.filter(|ec| !ec.is_empty())
.ok_or("a Next endpoint needs an underlying error class")?
.to_owned(),
endpoint: crate::NextStateEndpoint::from_json(&j["endpoint"])?,
});
}
let ec = j["ec"]
.as_str()
.filter(|ec| matches!(*ec, "TLC_MODULE_DIVISION_BY_ZERO" | "TLC_MODULE_EVALUATING"))
.ok_or("unsupported temporal endpoint error class")?
.to_owned();
return Ok(Self::TemporalStateError {
ec,
endpoint: crate::TemporalStateEndpoint::from_json(&j["endpoint"])?,
});
}
let name = || {
j.get("name")
.and_then(J::as_str)
.map(str::to_owned)
.ok_or_else(|| format!("a `{kind}` ending needs a `name`"))
};
Ok(match kind {
"invariant" => Self::Invariant(name()?),
"property" => Self::Property(name()?),
"deadlock" => Self::Deadlock,
"behavior" => Self::Behavior,
"lasso" => Self::Lasso {
back_to: j
.get("back_to")
.and_then(J::as_u64)
.and_then(|n| usize::try_from(n).ok())
.ok_or("a `lasso` ending needs `back_to`")?,
},
"stuttering" => Self::Stuttering,
"assertion" => Self::Assertion,
"error" => Self::Error {
ec: j.get("ec").and_then(J::as_str).map(str::to_owned),
},
"invariant-error" => Self::InvariantError {
name: name()?,
ec: j
.get("ec")
.and_then(J::as_str)
.filter(|ec| !ec.is_empty())
.ok_or("an invariant-error ending needs an underlying `ec`")?
.to_owned(),
},
other => return Err(format!("unknown ending kind `{other}`")),
})
}
#[must_use]
pub fn from_tlc(class: &str, property: Option<&str>, back_to: Option<usize>) -> Option<Self> {
let named = || property.map(str::to_owned);
Some(match class {
"TLC_INVARIANT_VIOLATED_INITIAL" | "TLC_INVARIANT_VIOLATED_BEHAVIOR" => {
Self::Invariant(named()?)
}
"TLC_PROPERTY_VIOLATED_INITIAL" | "TLC_ACTION_PROPERTY_VIOLATED_BEHAVIOR" => {
Self::Property(named()?)
}
"TLC_DEADLOCK_REACHED" => Self::Deadlock,
"TLC_TEMPORAL_PROPERTY_VIOLATED" => match back_to {
Some(back_to) => Self::Lasso { back_to },
None => Self::Stuttering,
},
"TLC_VALUE_ASSERT_FAILED" => Self::Assertion,
other => Self::Error {
ec: Some(other.to_owned()),
},
})
}
pub fn parse(text: &str) -> Result<Self, String> {
let (kind, arg) = match text.split_once(':') {
Some((k, a)) => (k, Some(a)),
None => (text, None),
};
let mut j = json!({ "kind": kind });
if let Some(a) = arg {
match kind {
"lasso" => {
j["back_to"] = J::from(
a.parse::<u64>()
.map_err(|_| format!("`{a}` is not a state index"))?,
);
}
"error" => j["ec"] = J::from(a),
_ => j["name"] = J::from(a),
}
}
Self::from_json(&j)
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Label {
pub name: String,
pub location: Option<String>,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum Source {
Dive,
Tlc,
}
#[derive(Clone, Debug, PartialEq)]
pub struct TraceDoc {
pub variables: Vec<String>,
pub states: Vec<Map<String, J>>,
pub labels: Vec<Option<Label>>,
pub ending: Option<Ending>,
pub length: Option<usize>,
pub source: Source,
pub properties: Vec<String>,
}
impl TraceDoc {
#[must_use]
pub fn logical_length(&self) -> usize {
self.states.len().saturating_add(usize::from(matches!(
self.ending,
Some(Ending::PartialNext { .. } | Ending::PartialInit { .. })
)))
}
pub fn behavior(states: Vec<J>) -> Result<Self, String> {
let mut out = Vec::with_capacity(states.len());
for (k, s) in states.into_iter().enumerate() {
match s {
J::Object(m) => out.push(m),
_ => return Err(format!("state {k} is not a JSON object")),
}
}
let variables = out
.first()
.map(|m| m.keys().cloned().collect())
.unwrap_or_default();
let n = out.len();
Ok(Self {
variables,
states: out,
labels: vec![None; n],
ending: Some(Ending::Behavior),
length: None,
source: Source::Dive,
properties: Vec::new(),
})
}
#[must_use]
pub fn with_ending(mut self, ending: Ending) -> Self {
self.ending = Some(ending);
self
}
#[must_use]
pub fn with_properties(mut self, properties: Vec<String>) -> Self {
self.properties = properties;
self
}
pub fn from_json(j: &J) -> Result<Self, String> {
if j.get("format").and_then(J::as_str) == Some(FORMAT) {
return Self::from_dive(j);
}
if let Some(witness) = j.get("error_witness")
&& witness.get("format").and_then(J::as_str) == Some(FORMAT)
{
if j.get("counterexample")
.is_some_and(|value| !value.is_null())
{
return Err(
"a report cannot carry both a formal counterexample and an Init error witness"
.into(),
);
}
let doc = Self::from_dive(witness)?;
if !matches!(doc.ending, Some(Ending::PartialInit { .. })) {
return Err("error_witness requires an Init partial terminal".into());
}
return Ok(doc);
}
for t in [
j.get("trace"),
j.get("counterexample").and_then(|c| c.get("trace")),
]
.into_iter()
.flatten()
{
if t.get("format").and_then(J::as_str) == Some(FORMAT) {
let mut doc = Self::from_dive(t)?;
let outer = j.get("counterexample").unwrap_or(j);
if let Some(names) = outer.get("properties") {
let names =
strings(Some(names)).ok_or("`properties` must be a list of names")?;
let outer_set: std::collections::BTreeSet<_> = names.iter().collect();
if outer_set.len() != names.len() {
return Err("enclosing report repeats a temporal property name".into());
}
if doc.properties.is_empty() {
doc.properties = names;
} else if doc.properties != names {
return Err("enclosing report and trace disagree on `properties`".into());
}
}
return Ok(doc);
}
}
if let Some(c) = j.get("counterexample") {
if c.get("format").and_then(J::as_str) == Some(FORMAT) {
return Self::from_dive(c);
}
if j.get("vars").is_some() {
return Self::from_tlc(j);
}
}
Err(format!(
"not a trace: expected a `{FORMAT}` document or TLC's -dumpTrace json document"
))
}
pub fn parse(text: &str) -> Result<Self, String> {
let j: J = serde_json::from_str(text).map_err(|e| format!("invalid JSON: {e}"))?;
Self::from_json(&j)
}
fn from_dive(j: &J) -> Result<Self, String> {
let version = j.get("version").and_then(J::as_u64);
if !matches!(
version,
Some(
VERSION
| INVARIANT_ERROR_VERSION
| PARTIAL_STATE_VERSION
| CANDIDATE_ERROR_VERSION
| TEMPORAL_SOURCE_ERROR_VERSION
| VIEW_SOURCE_ERROR_VERSION
)
) {
return Err(format!(
"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}"
));
}
let variables = strings(j.get("variables")).ok_or("`variables` must be a list of names")?;
let states_j = j
.get("states")
.and_then(J::as_array)
.ok_or("`states` must be a list")?;
let mut states = Vec::with_capacity(states_j.len());
let mut labels = Vec::with_capacity(states_j.len());
for (k, s) in states_j.iter().enumerate() {
let values = s
.get("values")
.and_then(J::as_object)
.ok_or_else(|| format!("state {k} has no `values` object"))?;
states.push(values.clone());
labels.push(match s.get("action") {
None | Some(J::Null) => None,
Some(a) => Some(Label {
name: a
.get("name")
.and_then(J::as_str)
.ok_or_else(|| format!("state {k}: an action needs a `name`"))?
.to_owned(),
location: a.get("location").and_then(J::as_str).map(str::to_owned),
}),
});
}
let ending = match j.get("ending") {
None | Some(J::Null) => None,
Some(e) => Some(Ending::from_json(e)?),
};
if version == Some(VERSION) && matches!(ending, Some(Ending::InvariantError { .. })) {
return Err("`invariant-error` requires dive-trace version 2".to_owned());
}
if matches!(
ending,
Some(Ending::PartialNext { .. } | Ending::PartialInit { .. })
) && version != Some(PARTIAL_STATE_VERSION)
{
return Err("a partial terminal candidate requires dive-trace version 3".into());
}
if version == Some(PARTIAL_STATE_VERSION)
&& !matches!(
ending,
Some(Ending::PartialNext { .. } | Ending::PartialInit { .. })
)
{
return Err("dive-trace version 3 requires a partial terminal candidate".into());
}
if matches!(ending, Some(Ending::CandidateStateError { .. }))
!= (version == Some(CANDIDATE_ERROR_VERSION))
{
return Err("an ordered candidate error requires exactly dive-trace version 4".into());
}
if matches!(ending, Some(Ending::ViewSourceError { .. }))
!= (version == Some(VIEW_SOURCE_ERROR_VERSION))
{
return Err("a VIEW source error requires exactly dive-trace version 6".into());
}
if matches!(ending, Some(Ending::TemporalSourceError { .. }))
!= (version == Some(TEMPORAL_SOURCE_ERROR_VERSION))
{
return Err("a temporal source-row error requires exactly dive-trace version 5".into());
}
let length = match j.get("length") {
None | Some(J::Null) => None,
Some(l) => Some(
l.as_u64()
.and_then(|n| usize::try_from(n).ok())
.ok_or("`length` must be a count")?,
),
};
Ok(Self {
variables,
states,
labels,
ending,
length,
source: Source::Dive,
properties: match j.get("properties") {
None => Vec::new(),
Some(names) => {
strings(Some(names)).ok_or("`properties` must be a list of names")?
}
},
})
}
fn from_tlc(j: &J) -> Result<Self, String> {
let variables = strings(j.get("vars")).ok_or("`vars` must be a list of names")?;
let cex = &j["counterexample"];
let state_j = cex
.get("state")
.and_then(J::as_array)
.ok_or("`counterexample.state` must be a list")?;
let mut states = Vec::with_capacity(state_j.len());
for (k, s) in state_j.iter().enumerate() {
match s.as_array().map(Vec::as_slice) {
Some([J::Number(n), J::Object(m)]) if n.as_u64() == Some(k as u64 + 1) => {
states.push(m.clone());
}
_ => {
return Err(format!(
"`counterexample.state[{k}]` is not [{}, {{...}}]",
k + 1
));
}
}
}
let mut labels = vec![None; states.len()];
let actions = cex
.get("action")
.and_then(J::as_array)
.map(Vec::as_slice)
.unwrap_or_default();
let count = states.len();
let state_at = |end: &J, at: usize| {
matches!(end.as_array().map(Vec::as_slice),
Some([J::Number(i), J::Object(m)])
if i.as_u64() == Some(at as u64 + 1) && states.get(at) == Some(m))
};
for (k, a) in actions.iter().enumerate() {
let Some([from, label, to]) = a.as_array().map(Vec::as_slice) else {
return Err(format!(
"`counterexample.action[{k}]` is not [from, label, to]"
));
};
if k + 1 == count {
let back = to
.get(0)
.and_then(J::as_u64)
.and_then(|i| usize::try_from(i).ok())
.filter(|&i| i >= 1 && i <= count);
if !state_at(from, k) || !back.is_some_and(|i| state_at(to, i - 1)) {
return Err(format!(
"`counterexample.action[{k}]` is not a loop from the last state to a listed one"
));
}
continue;
}
for (end, at) in [(from, k), (to, k + 1)] {
if !state_at(end, at) {
return Err(format!(
"`counterexample.action[{k}]` does not connect states {} and {}",
k + 1,
k + 2
));
}
}
labels[k + 1] = Some(Label {
name: label
.get("name")
.and_then(J::as_str)
.ok_or_else(|| format!("`counterexample.action[{k}]` has no name"))?
.to_owned(),
location: label.get("location").map(|l| match l {
J::Object(m) => format!(
"line {}, col {} to line {}, col {} of module {}",
m.get("beginLine").unwrap_or(&J::Null),
m.get("beginColumn").unwrap_or(&J::Null),
m.get("endLine").unwrap_or(&J::Null),
m.get("endColumn").unwrap_or(&J::Null),
m.get("module").and_then(J::as_str).unwrap_or("?"),
),
other => other.to_string(),
}),
});
}
if !actions.is_empty() && actions.len() + 1 != count && actions.len() != count {
return Err(format!(
"{} states but {} steps",
states.len(),
actions.len()
));
}
Ok(Self {
variables,
states,
labels,
ending: None,
length: None,
source: Source::Tlc,
properties: Vec::new(),
})
}
#[must_use]
pub fn to_json(&self) -> J {
let states: Vec<J> = self
.states
.iter()
.zip(&self.labels)
.map(|(s, l)| {
json!({
"action": l.as_ref().map(|l| json!({"name": l.name, "location": l.location})),
"values": s,
})
})
.collect();
let version = if matches!(
self.ending,
Some(Ending::PartialNext { .. } | Ending::PartialInit { .. })
) {
PARTIAL_STATE_VERSION
} else if matches!(self.ending, Some(Ending::CandidateStateError { .. })) {
CANDIDATE_ERROR_VERSION
} else if matches!(self.ending, Some(Ending::ViewSourceError { .. })) {
VIEW_SOURCE_ERROR_VERSION
} else if matches!(self.ending, Some(Ending::TemporalSourceError { .. })) {
TEMPORAL_SOURCE_ERROR_VERSION
} else if matches!(self.ending, Some(Ending::InvariantError { .. })) {
INVARIANT_ERROR_VERSION
} else {
VERSION
};
let mut j = json!({
"format": FORMAT,
"version": version,
"variables": self.variables,
"states": states,
"ending": self.ending.as_ref().map(Ending::to_json),
});
if let Some(n) = self.length {
j["length"] = J::from(n);
}
if !self.properties.is_empty() {
j["properties"] = J::from(self.properties.clone());
}
j
}
}
fn strings(j: Option<&J>) -> Option<Vec<String>> {
j?.as_array()?
.iter()
.map(|v| v.as_str().map(str::to_owned))
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn reads_tlc_dump_trace_json() -> Result<(), String> {
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"]}"#;
let d = TraceDoc::parse(text)?;
assert_eq!(d.source, Source::Tlc);
assert_eq!(d.states.len(), 2);
assert_eq!(d.labels[0], None);
let l = d.labels[1].clone().ok_or("label")?;
assert_eq!(l.name, "Next");
assert_eq!(
l.location.as_deref(),
Some("line 9, col 9 to line 9, col 18 of module M")
);
Ok(())
}
#[test]
fn rejects_a_tlc_document_whose_steps_do_not_connect() {
let text = r#"{"counterexample":{"action":[[[1,{"x":0}],{"name":"Next"},[2,{"x":5}]]],"state":[[1,{"x":0}],[2,{"x":1}]]},"vars":["x"]}"#;
assert!(TraceDoc::parse(text).is_err());
}
#[test]
fn dive_format_round_trips() -> Result<(), String> {
let text = r#"{"format":"dive-trace","version":1,"variables":["x"],
"states":[{"action":null,"values":{"x":0}},{"action":{"name":"A","location":null},"values":{"x":1}}],
"ending":{"kind":"invariant","name":"Inv"},"length":2}"#;
let d = TraceDoc::parse(text)?;
assert_eq!(d.ending, Some(Ending::Invariant("Inv".to_owned())));
assert_eq!(TraceDoc::from_json(&d.to_json())?, d);
let wrapped = json!({"schema_version": 1, "counterexample": d.to_json()});
assert_eq!(TraceDoc::from_json(&wrapped)?, d);
Ok(())
}
#[test]
fn parses_command_line_endings() -> Result<(), String> {
assert_eq!(
Ending::parse("invariant:Inv")?,
Ending::Invariant("Inv".into())
);
assert_eq!(Ending::parse("deadlock")?, Ending::Deadlock);
assert_eq!(Ending::parse("lasso:2")?, Ending::Lasso { back_to: 2 });
assert!(Ending::parse("invariant").is_err());
assert!(Ending::parse("nonsense").is_err());
Ok(())
}
}