clm-kernel 0.0.19

Cubical Logic Model (CLM) sovereign execution engine, CPN-VM, and Cordis spatiotemporal substrate
Documentation
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,
    })
}

/// Evaluate a bialgebraic_bisimulation JSON specification natively in Rust.
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()),
    ))
}