clm-kernel 0.0.13

Cubical Logic Model (CLM) sovereign execution engine, CPN-VM, and Cordis spatiotemporal substrate
Documentation
//! Union-find cospan pushout, 1-safe boundary marking pullback, and P-invariants.
//!
//! Invariant: INV-CLC-03 (Open Monoidal Net Compositionality).

use std::collections::{BTreeMap, HashMap, HashSet};
use serde::{Deserialize, Serialize};
use thiserror::Error;

use super::open_petri_net::{CospanCompositionResult, OpenPetriNet, OpenPlace, OpenTransition};
pub use super::open_petri_catalyst::*;

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "camelCase")]
pub struct CospanLegs {
    pub left_leg: BTreeMap<String, String>,
    pub right_leg: BTreeMap<String, String>,
}

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[serde(untagged)]
pub enum BoundaryGlueSpec {
    Cospan(CospanLegs),
    Direct(BTreeMap<String, String>),
}

#[derive(Error, Debug, Clone, PartialEq, Eq)]
#[error("BoundaryMarkingPullbackError: {0}")]
pub struct BoundaryMarkingPullbackError(pub String);

fn check_local_p_invariant(net: &OpenPetriNet, weights: &[f64]) -> bool {
    if weights.len() != net.places.len() {
        return false;
    }
    let idx_map: HashMap<&str, usize> = net
        .places
        .iter()
        .enumerate()
        .map(|(idx, p)| (p.id.as_str(), idx))
        .collect();

    for tr in &net.transitions {
        let mut delta = 0.0;
        for inp in &tr.inputs {
            let idx = match idx_map.get(inp.as_str()) {
                Some(&i) => i,
                None => return false,
            };
            delta -= weights[idx];
        }
        for out in &tr.outputs {
            let idx = match idx_map.get(out.as_str()) {
                Some(&i) => i,
                None => return false,
            };
            delta += weights[idx];
        }
        if delta.abs() > 1e-9 {
            return false;
        }
    }
    true
}

pub fn compose_marked_open_petri_nets(
    net1: &OpenPetriNet,
    net2: &OpenPetriNet,
    glue_spec: Option<&BoundaryGlueSpec>,
    allow_multiset_boundary: bool,
) -> Result<CospanCompositionResult, BoundaryMarkingPullbackError> {
    let net1_by_id: HashMap<&str, &OpenPlace> = net1.places.iter().map(|p| (p.id.as_str(), p)).collect();
    let net2_by_id: HashMap<&str, &OpenPlace> = net2.places.iter().map(|p| (p.id.as_str(), p)).collect();

    let mut ordered_keys: Vec<String> = Vec::new();
    for p in &net1.places {
        ordered_keys.push(format!("net1:{}", p.id));
    }
    for p in &net2.places {
        ordered_keys.push(format!("net2:{}", p.id));
    }

    let mut parent: HashMap<String, String> = ordered_keys.iter().map(|k| (k.clone(), k.clone())).collect();
    let rank: HashMap<String, usize> = ordered_keys.iter().enumerate().map(|(idx, k)| (k.clone(), idx)).collect();

    fn find(parent: &mut HashMap<String, String>, x: &str) -> String {
        let mut cur = x.to_string();
        while parent.get(&cur).unwrap() != &cur {
            let nxt = parent.get(&cur).unwrap().clone();
            let nxt_parent = parent.get(&nxt).unwrap().clone();
            parent.insert(cur.clone(), nxt_parent);
            cur = nxt;
        }
        cur
    }

    fn union(parent: &mut HashMap<String, String>, rank: &HashMap<String, usize>, a: &str, b: &str) {
        let ra = find(parent, a);
        let rb = find(parent, b);
        if ra != rb {
            if rank.get(&ra).unwrap() <= rank.get(&rb).unwrap() {
                parent.insert(rb, ra);
            } else {
                parent.insert(ra, rb);
            }
        }
    }

    let mut glue_pairs: Vec<(String, String)> = Vec::new();
    match glue_spec {
        None => {
            for out in &net1.outputs {
                if net2.inputs.contains(out) {
                    glue_pairs.push((out.clone(), out.clone()));
                }
            }
        }
        Some(BoundaryGlueSpec::Cospan(legs)) => {
            let mut apexes: HashSet<&str> = HashSet::new();
            for k in legs.left_leg.keys() {
                apexes.insert(k.as_str());
            }
            for k in legs.right_leg.keys() {
                apexes.insert(k.as_str());
            }
            for apex in apexes {
                let p1 = legs.left_leg.get(apex).ok_or_else(|| {
                    BoundaryMarkingPullbackError(format!("Incomplete cospan leg for apex '{}'", apex))
                })?;
                let p2 = legs.right_leg.get(apex).ok_or_else(|| {
                    BoundaryMarkingPullbackError(format!("Incomplete cospan leg for apex '{}'", apex))
                })?;
                glue_pairs.push((p1.clone(), p2.clone()));
            }
        }
        Some(BoundaryGlueSpec::Direct(direct)) => {
            for (p1, p2) in direct {
                glue_pairs.push((p1.clone(), p2.clone()));
            }
        }
    }

    for (p1, p2) in &glue_pairs {
        if !net1_by_id.contains_key(p1.as_str()) {
            return Err(BoundaryMarkingPullbackError(format!("Unknown net1 boundary place '{}'", p1)));
        }
        if !net2_by_id.contains_key(p2.as_str()) {
            return Err(BoundaryMarkingPullbackError(format!("Unknown net2 boundary place '{}'", p2)));
        }
        union(&mut parent, &rank, &format!("net1:{}", p1), &format!("net2:{}", p2));
    }

    let mut classes: BTreeMap<String, Vec<String>> = BTreeMap::new();
    for key in &ordered_keys {
        let root = find(&mut parent, key);
        classes.entry(root).or_default().push(key.clone());
    }

    let mut glued_place_map = BTreeMap::new();
    let mut composite_places = Vec::new();
    let mut used_ids: HashSet<String> = HashSet::new();

    for members in classes.values() {
        let place_objs: Vec<&OpenPlace> = members
            .iter()
            .map(|m| {
                if m.starts_with("net1:") {
                    net1_by_id.get(&m[5..]).copied().unwrap()
                } else {
                    net2_by_id.get(&m[5..]).copied().unwrap()
                }
            })
            .collect();

        let expected_tokens = place_objs[0].initial_tokens;
        if members.len() > 1 {
            if expected_tokens < 0 || (!allow_multiset_boundary && expected_tokens > 1) {
                return Err(BoundaryMarkingPullbackError(format!(
                    "Glued boundary place violates 1-safe marking ({})",
                    expected_tokens
                )));
            }
            if place_objs.iter().any(|pl| pl.initial_tokens != expected_tokens) {
                return Err(BoundaryMarkingPullbackError(
                    "Boundary marking pullback mismatch across glued places".to_string(),
                ));
            }
        }

        let first_net1 = members.iter().find(|m| m.starts_with("net1:"));
        let mut canonical_id = match first_net1 {
            Some(m) => m[5..].to_string(),
            None => members[0][5..].to_string(),
        };
        if used_ids.contains(&canonical_id) {
            canonical_id = format!("{}_{}", if first_net1.is_some() { &net1.name } else { &net2.name }, canonical_id);
        }
        used_ids.insert(canonical_id.clone());

        for m in members {
            glued_place_map.insert(m.clone(), canonical_id.clone());
        }

        let label = place_objs.iter().find_map(|pl| pl.label.clone());
        composite_places.push(OpenPlace {
            id: canonical_id,
            initial_tokens: expected_tokens,
            label,
        });
    }

    let map_ids = |prefix: &str, ids: &[String]| -> Vec<String> {
        ids.iter()
            .map(|id| glued_place_map.get(&format!("{}:{}", prefix, id)).cloned().unwrap_or_else(|| id.clone()))
            .collect()
    };

    let map_tr = |prefix: &str, net_name: &str, t: &OpenTransition| -> OpenTransition {
        OpenTransition {
            id: format!("{}_{}", net_name, t.id),
            inputs: map_ids(prefix, &t.inputs),
            outputs: map_ids(prefix, &t.outputs),
            read_arcs: t.read_arcs.as_ref().map(|ras| map_ids(prefix, ras)),
        }
    };

    let mut composite_transitions = Vec::new();
    for t in &net1.transitions {
        composite_transitions.push(map_tr("net1", &net1.name, t));
    }
    for t in &net2.transitions {
        composite_transitions.push(map_tr("net2", &net2.name, t));
    }

    let composite = OpenPetriNet {
        name: format!("{}_x_{}", net1.name, net2.name),
        places: composite_places,
        transitions: composite_transitions,
        inputs: map_ids("net1", &net1.inputs),
        outputs: map_ids("net2", &net2.outputs),
    };

    Ok(CospanCompositionResult { composite, glued_place_map })
}

pub fn synthesize_pullback_p_invariant(
    net1: &OpenPetriNet,
    weights1: &[f64],
    net2: &OpenPetriNet,
    weights2: &[f64],
    glue_spec: Option<&BoundaryGlueSpec>,
) -> Result<Vec<f64>, BoundaryMarkingPullbackError> {
    if !check_local_p_invariant(net1, weights1) || !check_local_p_invariant(net2, weights2) {
        return Err(BoundaryMarkingPullbackError(
            "Constituent weight vector is not a valid local P-invariant".to_string(),
        ));
    }

    let res = compose_marked_open_petri_nets(net1, net2, glue_spec, false)?;
    let mut weight_by_cid: HashMap<String, f64> = HashMap::new();

    let mut assign = |prefix: &str, places: &[OpenPlace], weights: &[f64]| -> Result<(), BoundaryMarkingPullbackError> {
        for (idx, p) in places.iter().enumerate() {
            let cid = res.glued_place_map.get(&format!("{}:{}", prefix, p.id)).unwrap();
            let w = weights[idx];
            if let Some(&prev) = weight_by_cid.get(cid) {
                if (prev - w).abs() > 1e-9 {
                    return Err(BoundaryMarkingPullbackError(format!(
                        "Pullback P-invariant disagreement on '{}'",
                        cid
                    )));
                }
            }
            weight_by_cid.insert(cid.clone(), w);
        }
        Ok(())
    };

    assign("net1", &net1.places, weights1)?;
    assign("net2", &net2.places, weights2)?;

    Ok(res.composite.places.iter().map(|cp| *weight_by_cid.get(&cp.id).unwrap()).collect())
}