use std::collections::BTreeSet;
pub use crate::layer1::bisimulation_ast::CanonNum;
use crate::layer1::bisimulation_ast::{
Step, Store, canon_ast, encode_num_val, mk_obj, preserve_json_numeric_tokens, step_ast,
};
fn state_key_rs(ast: &serde_json::Value, store: &Store) -> String {
let entries: Vec<serde_json::Value> = store
.iter()
.map(|(k, v)| serde_json::json!([k, v]))
.collect();
serde_json::to_string(&mk_obj(vec![
("ast", ast.clone()),
("store", entries.into()),
]))
.unwrap()
}
fn obs_head(
mut ast: serde_json::Value,
mut store: Store,
budget: usize,
) -> (&'static str, String, serde_json::Value, Store, usize) {
let mut used = 0;
loop {
match step_ast(&ast, &store) {
Step::Ret(val) => return ("Ret", val, ast, store, used),
_ if used >= budget => return ("OpenFrontier", String::new(), ast, store, used),
Step::Vis(ev, next_ast, next_store) => {
return ("Vis", ev, next_ast, next_store, used + 1);
}
Step::Tau(next_ast, next_store) => {
used += 1;
ast = next_ast;
store = next_store;
}
}
}
}
fn unfold_trace_rs(
mut ast: serde_json::Value,
mut store: Store,
mut remaining: usize,
) -> Vec<String> {
let mut trace = Vec::new();
loop {
let (kind, val, next_ast, next_store, used) = obs_head(ast, store, remaining);
if kind != "Vis" {
let terminal = if kind == "Ret" {
format!("RET:{}", val)
} else {
"OPEN_FRONTIER".into()
};
trace.push(terminal);
return trace;
}
trace.push(format!("VIS:{}", val));
ast = next_ast;
store = next_store;
remaining -= used;
}
}
fn verify_cert_rs(
left_ast: &serde_json::Value,
right_ast: &serde_json::Value,
init_store: &Store,
cert: &[(String, String)],
max_steps: usize,
) -> bool {
let set: BTreeSet<(String, String)> = cert.iter().cloned().collect();
let root_pair = (
state_key_rs(left_ast, init_store),
state_key_rs(right_ast, init_store),
);
if set.is_empty() || !set.contains(&root_pair) {
return false;
}
let parse_key = |key: &str| -> Option<(serde_json::Value, Store)> {
let val: serde_json::Value = serde_json::from_str(key).ok()?;
let mut store = Store::new();
for item in val.get("store")?.as_array()? {
store.insert(
item.get(0)?.as_str()?.into(),
item.get(1)?.as_str()?.into(),
);
}
Some((canon_ast(val.get("ast")?).ok()?, store))
};
set.iter().all(|(kl, kr)| match (parse_key(kl), parse_key(kr)) {
(Some((al, stl)), Some((ar, str_))) => {
let hl = obs_head(al, stl, max_steps);
let hr = obs_head(ar, str_, max_steps);
hl.0 != "OpenFrontier"
&& hr.0 != "OpenFrontier"
&& hl.0 == hr.0
&& hl.1 == hr.1
&& (hl.0 != "Vis"
|| set.contains(&(state_key_rs(&hl.2, &hl.3), state_key_rs(&hr.2, &hr.3))))
}
_ => false,
})
}
pub fn evaluate_bisimulation_spec_rs(raw_text: &str) -> Result<(i32, String), String> {
let preserved = preserve_json_numeric_tokens(raw_text);
let spec: serde_json::Value = serde_json::from_str(&preserved).map_err(|e| e.to_string())?;
let def_max = spec.get("max_steps").and_then(|v| v.as_u64()).unwrap_or(64) as usize;
let def_bound = spec
.get("bound_name")
.and_then(|v| v.as_str())
.unwrap_or("maxSteps");
let single = vec![spec.clone()];
let cases = spec
.get("cases")
.and_then(|v| v.as_array())
.unwrap_or(&single);
let mut results = Vec::new();
let mut all_ok = true;
for case in cases {
let la = canon_ast(case.get("left").ok_or("Missing left")?)?;
let ra = canon_ast(case.get("right").ok_or("Missing right")?)?;
let max_steps = case
.get("max_steps")
.and_then(|v| v.as_u64())
.map(|v| v as usize)
.unwrap_or(def_max);
let bound_name = case
.get("bound_name")
.and_then(|v| v.as_str())
.unwrap_or(def_bound);
let mut init_store = Store::new();
if let Some(obj) = case.get("initial_store").and_then(|v| v.as_object()) {
for (k, v) in obj {
init_store.insert(k.clone(), encode_num_val(v)?.token());
}
}
let lt = unfold_trace_rs(la.clone(), init_store.clone(), max_steps);
let rt = unfold_trace_rs(ra.clone(), init_store.clone(), max_steps);
let (mut sl, mut stl) = (la.clone(), init_store.clone());
let (mut sr, mut str_) = (ra.clone(), init_store.clone());
let (mut bl, mut br) = (max_steps, max_steps);
let mut events = Vec::<String>::new();
let mut rel = Vec::<(String, String)>::new();
let mut seen = BTreeSet::new();
let (verdict, cert, cert_ok, cex, frontier) = loop {
let hl = obs_head(sl.clone(), stl.clone(), bl);
let hr = obs_head(sr.clone(), str_.clone(), br);
if hl.0 == "OpenFrontier" || hr.0 == "OpenFrontier" {
let open = serde_json::json!([state_key_rs(&sl, &stl), state_key_rs(&sr, &str_)]);
break ("UNDECIDED_WITHIN_BOUND", vec![], false, vec![], vec![open]);
}
if hl.0 != hr.0 {
events.push(format!(
"STEP_KIND_MISMATCH:left={}:{}|right={}:{}",
hl.0, hl.1, hr.0, hr.1
));
break ("DIVERGENT", vec![], false, events, vec![]);
}
if hl.0 == "Ret" {
if hl.1 != hr.1 {
events.push(format!("RET_MISMATCH:left={}|right={}", hl.1, hr.1));
break ("DIVERGENT", vec![], false, events, vec![]);
}
let pair = (state_key_rs(&sl, &stl), state_key_rs(&sr, &str_));
if seen.insert(pair.clone()) {
rel.push(pair);
}
let ok = verify_cert_rs(&la, &ra, &init_store, &rel, max_steps);
let cert_json: Vec<serde_json::Value> = if ok {
rel.iter().map(|(a, b)| serde_json::json!([a, b])).collect()
} else {
vec![]
};
let cex_out = if ok {
vec![]
} else {
vec!["CERTIFICATE_CLOSURE_FAILED".into()]
};
break (
if ok { "EQUIVALENT" } else { "DIVERGENT" },
cert_json,
ok,
cex_out,
vec![],
);
}
if hl.1 != hr.1 {
events.push(format!("VIS_MISMATCH:left={}|right={}", hl.1, hr.1));
break ("DIVERGENT", vec![], false, events, vec![]);
}
let pair = (state_key_rs(&sl, &stl), state_key_rs(&sr, &str_));
if seen.insert(pair.clone()) {
rel.push(pair);
}
events.push(format!("VIS:{}", hl.1));
bl -= hl.4;
br -= hr.4;
sl = hl.2;
stl = hl.3;
sr = hr.2;
str_ = hr.3;
};
let report_only = spec
.get("report_only")
.and_then(|v| v.as_bool())
.unwrap_or(false);
let expected = case
.get("expected_verdict")
.and_then(|v| v.as_str())
.unwrap_or("EQUIVALENT");
all_ok = all_ok && (report_only || verdict == expected);
let id = case.get("id").and_then(|v| v.as_str()).unwrap_or("default");
results.push(mk_obj(vec![
("boundName", bound_name.into()),
("certificate", cert.into()),
("certificateVerified", cert_ok.into()),
("counterexampleTrace", cex.into()),
("id", id.into()),
("leftObservableTrace", lt.into()),
("maxSteps", (max_steps as u64).into()),
("openFrontier", frontier.into()),
("rightObservableTrace", rt.into()),
("verdict", verdict.into()),
]));
}
let payload = mk_obj(vec![
("results", results.into()),
("schema", "clm.bialgebraic.bisimulation.v1".into()),
]);
Ok((
if all_ok { 0 } else { 1 },
format!("{}\n", serde_json::to_string(&payload).unwrap()),
))
}