clm-kernel 0.0.21

Cubical Logic Model (CLM) sovereign execution engine, CPN-VM, and Cordis spatiotemporal substrate
Documentation
//! Bounded Place Type Lattice Core and Dedekind-MacNeille Completion.

use std::collections::{BTreeMap, BTreeSet, HashMap};
use std::sync::OnceLock;
use serde::{Deserialize, Serialize};

use crate::cpn::mcard_token::{PlaceMCard, TransitionMCard};
use super::place_role_binding::{PlaceRole, VIRTUAL_BOTTOM, VIRTUAL_TOP};
use super::tarjan_scc::tarjan_scc;
use super::{extremal_names, LatticeBitset, LatticeBitsetIndex};

/// Bounded Place Type Lattice `(P, ⊑, ⊔, ⊓, ⊥, τ_mid, τ_exception, ⊤)` condensed via Tarjan SCC.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct PlaceTypeLattice {
    /// Map of place IDs to `PlaceMCard` definitions.
    pub places: BTreeMap<String, PlaceMCard>,
    /// Assigned structural role for each place ID.
    pub roles: BTreeMap<String, PlaceRole>,
    /// Tarjan Strongly Connected Components in topological order.
    pub sccs: Vec<Vec<String>>,
    /// Map of place ID to its SCC index.
    pub node_to_scc: BTreeMap<String, usize>,
    /// Bottom element identifier (`⊥`).
    pub bottom: String,
    /// Top element identifier (`⊤`).
    pub top: String,
    /// Exception trap place identifiers (`τ_exception`).
    pub exception_places: Vec<String>,
    /// Synthesized Dedekind-MacNeille cut identifiers for non-lattice bowties.
    pub dm_cuts: Vec<String>,
    reachability: BTreeMap<String, BTreeSet<String>>,
    #[serde(skip)]
    index: OnceLock<LatticeBitsetIndex>,
}

impl PartialEq for PlaceTypeLattice {
    fn eq(&self, other: &Self) -> bool {
        self.places == other.places
            && self.roles == other.roles
            && self.sccs == other.sccs
            && self.node_to_scc == other.node_to_scc
            && self.bottom == other.bottom
            && self.top == other.top
            && self.exception_places == other.exception_places
            && self.dm_cuts == other.dm_cuts
            && self.reachability == other.reachability
    }
}

impl Eq for PlaceTypeLattice {}

impl PlaceTypeLattice {
    fn idx(&self) -> &LatticeBitsetIndex {
        self.index.get_or_init(|| LatticeBitsetIndex::from_reachability(&self.reachability, &self.bottom, &self.top))
    }

    /// Constructs a `PlaceTypeLattice` from a Petri Net's places and transitions (with Dedekind-MacNeille cut completion).
    pub fn from_net(
        places: &[PlaceMCard],
        transitions: &[TransitionMCard],
        exception_place_ids: Option<&BTreeSet<String>>,
    ) -> Self {
        Self::from_net_with_options(places, transitions, exception_place_ids, true)
    }

    /// Constructs a `PlaceTypeLattice` with optional Dedekind-MacNeille normal cut completion (`complete_cuts`).
    pub fn from_net_with_options(
        places: &[PlaceMCard],
        transitions: &[TransitionMCard],
        exception_place_ids: Option<&BTreeSet<String>>,
        complete_cuts: bool,
    ) -> Self {
        let mut place_map = BTreeMap::new();
        let mut explicit_exc = exception_place_ids.cloned().unwrap_or_default();
        for p in places {
            place_map.insert(p.place_id.clone(), p.clone());
            let low = p.place_id.to_lowercase();
            if p.role == "Exception" || low.contains("exception") || low.contains("trap") {
                explicit_exc.insert(p.place_id.clone());
            }
        }
        let mut adj: BTreeMap<String, BTreeSet<String>> =
            place_map.keys().map(|k| (k.clone(), BTreeSet::new())).collect();
        for tr in transitions {
            for u in &tr.input_places {
                if !adj.contains_key(u) { continue; }
                for v in &tr.output_places {
                    if adj.contains_key(v) { adj.get_mut(u).unwrap().insert(v.clone()); }
                }
            }
        }
        let all_nodes: Vec<String> = place_map.keys().cloned().collect();
        let sccs = tarjan_scc(&all_nodes, &adj);
        let mut node_to_scc = BTreeMap::new();
        for (idx, comp) in sccs.iter().enumerate() {
            for pid in comp { node_to_scc.insert(pid.clone(), idx); }
        }
        let (mut scc_in, mut scc_out_normal) = (vec![BTreeSet::new(); sccs.len()], vec![BTreeSet::new(); sccs.len()]);
        for (u, nbrs) in &adj {
            let su = node_to_scc[u];
            for v in nbrs {
                let sv = node_to_scc[v];
                if su != sv {
                    scc_in[sv].insert(su);
                    if !explicit_exc.contains(v) { scc_out_normal[su].insert(sv); }
                }
            }
        }
        let mut roles = BTreeMap::new();
        let (mut init_cands, mut term_cands) = (Vec::new(), Vec::new());
        for (pid, p) in &place_map {
            let s_idx = node_to_scc[pid];
            if explicit_exc.contains(pid) {
                roles.insert(pid.clone(), PlaceRole::Exception);
            } else if p.role == "InitialBottom" || scc_in[s_idx].is_empty() {
                roles.insert(pid.clone(), PlaceRole::InitialBottom);
                init_cands.push(pid.clone());
            } else if p.role == "TerminalTop" || scc_out_normal[s_idx].is_empty() {
                roles.insert(pid.clone(), PlaceRole::TerminalTop);
                term_cands.push(pid.clone());
            } else {
                roles.insert(pid.clone(), PlaceRole::Intermediate);
            }
        }
        let bottom_id = if init_cands.len() == 1 { init_cands[0].clone() } else { VIRTUAL_BOTTOM.to_string() };
        let top_id = if term_cands.len() == 1 { term_cands[0].clone() } else { VIRTUAL_TOP.to_string() };
        let mut aug_set: BTreeSet<String> = all_nodes.into_iter().collect();
        aug_set.insert(bottom_id.clone());
        aug_set.insert(top_id.clone());
        let sorted_aug: Vec<String> = aug_set.into_iter().collect();
        let n0 = sorted_aug.len();
        let aug_idx: HashMap<&str, usize> = sorted_aug.iter().enumerate().map(|(i, n)| (n.as_str(), i)).collect();
        let (bot_i, top_i) = (aug_idx[bottom_id.as_str()], aug_idx[top_id.as_str()]);
        let mut aug_adj = vec![LatticeBitset::zero(n0); n0];
        for (i, name) in sorted_aug.iter().enumerate() {
            if i == bot_i {
                aug_adj[i] = LatticeBitset::full(n0);
            } else {
                aug_adj[i].set(i);
                aug_adj[i].set(top_i);
                if let Some(nbrs) = adj.get(name) {
                    for v in nbrs { aug_adj[i].set(aug_idx[v.as_str()]); }
                }
            }
        }
        let mut reach0 = vec![LatticeBitset::zero(n0); n0];
        for start in (0..n0).rev() {
            let mut vis = LatticeBitset::zero(n0);
            vis.set(start);
            let mut todo = aug_adj[start].andnot(&vis);
            while let Some(nxt) = todo.first_set() {
                todo.clear(nxt);
                if !reach0[nxt].is_empty() {
                    vis.bitor_assign(&reach0[nxt]);
                    todo.andnot_assign(&reach0[nxt]);
                } else {
                    vis.set(nxt);
                    todo.bitor_assign(&aug_adj[nxt].andnot(&vis));
                }
            }
            reach0[start] = vis;
        }
        let mut down0 = vec![LatticeBitset::zero(n0); n0];
        for (x, rx) in reach0.iter().enumerate() {
            for y in rx.iter_ones() { down0[y].set(x); }
        }
        let mut dm_cuts_list = Vec::new();
        let (mut final_nodes, mut final_up, mut final_down) = (sorted_aug.clone(), reach0.clone(), down0.clone());
        if complete_cuts {
            let existing: BTreeSet<LatticeBitset> = down0.iter().cloned().collect();
            let mut all_cuts = existing.clone();
            let mut queue: Vec<LatticeBitset> = existing.iter().cloned().collect();
            while let Some(c1) = queue.pop() {
                let snap: Vec<LatticeBitset> = all_cuts.iter().cloned().collect();
                for c2 in snap {
                    let inter = c1.bitand(&c2);
                    if !inter.is_empty() && all_cuts.insert(inter.clone()) { queue.push(inter); }
                }
            }
            if all_cuts.len() > existing.len() {
                let mut cut_by_name: BTreeMap<String, LatticeBitset> =
                    sorted_aug.iter().enumerate().map(|(i, n)| (n.clone(), down0[i].clone())).collect();
                for c_mask in &all_cuts {
                    if existing.contains(c_mask) { continue; }
                    let c_ind = c_mask.iter_ones();
                    let u_ind: Vec<usize> = (0..n0).filter(|&y| c_mask.is_subset(&down0[y])).collect();
                    let max_c = extremal_names(&c_ind, &reach0, &sorted_aug, true);
                    let min_u = extremal_names(&u_ind, &reach0, &sorted_aug, false);
                    let cut_id = format!("__dm_cut__{}__to__{}__", max_c.join("_"), min_u.join("_"));
                    dm_cuts_list.push(cut_id.clone());
                    cut_by_name.insert(cut_id.clone(), c_mask.clone());
                    roles.insert(cut_id, PlaceRole::Intermediate);
                }
                dm_cuts_list.sort();
                final_nodes = cut_by_name.keys().cloned().collect();
                let k = final_nodes.len();
                let cut_masks: Vec<LatticeBitset> = final_nodes.iter().map(|n| cut_by_name[n].clone()).collect();
                final_up = vec![LatticeBitset::zero(k); k];
                final_down = vec![LatticeBitset::zero(k); k];
                for i in 0..k {
                    for j in 0..k {
                        if cut_masks[i].is_subset(&cut_masks[j]) {
                            final_up[i].set(j);
                            final_down[j].set(i);
                        }
                    }
                }
            }
        }
        let reach: BTreeMap<String, BTreeSet<String>> = final_nodes.iter().enumerate().map(|(i, n)| {
            (n.clone(), final_up[i].iter_ones().into_iter().map(|j| final_nodes[j].clone()).collect())
        }).collect();
        let idx = LatticeBitsetIndex::build(final_nodes, final_up, final_down, &bottom_id, &top_id);
        let lock = OnceLock::new();
        let _ = lock.set(idx);
        Self {
            places: place_map, roles, sccs, node_to_scc, bottom: bottom_id, top: top_id,
            exception_places: explicit_exc.into_iter().collect(), dm_cuts: dm_cuts_list, reachability: reach, index: lock,
        }
    }

    /// Partial order `p1 ⊑ p2` (true if `p2` is reachable from `p1`).
    pub fn leq(&self, p1: &str, p2: &str) -> bool {
        if p1 == p2 || p1 == self.bottom || p2 == self.top { return true; }
        let idx = self.idx();
        match (idx.node_to_idx.get(p1), idx.node_to_idx.get(p2)) {
            (Some(&i), Some(&j)) => idx.up[i].test(j),
            _ => false,
        }
    }

    /// Alias for `leq(p1, p2)` in the Place Type Lattice.
    pub fn is_subtype(&self, p1: &str, p2: &str) -> bool { self.leq(p1, p2) }

    /// Returns true if `p1` and `p2` belong to the same Strongly Connected Component.
    pub fn same_scc(&self, p1: &str, p2: &str) -> bool {
        if p1 == p2 { return true; }
        let idx = self.idx();
        match (idx.node_to_idx.get(p1), idx.node_to_idx.get(p2)) {
            (Some(&i), Some(&j)) => idx.scc_rep[i] == idx.scc_rep[j],
            _ => false,
        }
    }

    /// Computes least upper bound `p1 ⊔ p2` in the condensed lattice.
    pub fn join(&self, p1: &str, p2: &str) -> String {
        if self.leq(p1, p2) { return p2.to_string(); }
        if self.leq(p2, p1) { return p1.to_string(); }
        let idx = self.idx();
        match (idx.node_to_idx.get(p1), idx.node_to_idx.get(p2)) {
            (Some(&i), Some(&j)) => idx.nodes[idx.join_idx(i, j)].clone(),
            _ => self.top.clone(),
        }
    }

    /// Computes greatest lower bound `p1 ⊓ p2` in the condensed lattice.
    pub fn meet(&self, p1: &str, p2: &str) -> String {
        if self.leq(p1, p2) { return p1.to_string(); }
        if self.leq(p2, p1) { return p2.to_string(); }
        let idx = self.idx();
        match (idx.node_to_idx.get(p1), idx.node_to_idx.get(p2)) {
            (Some(&i), Some(&j)) => idx.nodes[idx.meet_idx(i, j)].clone(),
            _ => self.bottom.clone(),
        }
    }

    /// Materializes the transitive type graph `(nodes, edges, bottom, top)`.
    pub fn to_type_graph(&self) -> (Vec<String>, Vec<(String, String)>, String, String) {
        let idx = self.idx();
        let mut edges = Vec::new();
        for (i, u) in idx.nodes.iter().enumerate() {
            for j in idx.up[i].iter_ones() {
                edges.push((u.clone(), idx.nodes[j].clone()));
            }
        }
        (idx.nodes.clone(), edges, self.bottom.clone(), self.top.clone())
    }

    /// Verifies bounded poset laws AND least-upper-bound (`join`) / greatest-lower-bound (`meet`) lattice laws.
    pub fn verify_lattice_laws(&self) -> bool {
        let idx = self.idx();
        let k = idx.nodes.len();
        if k == 0 { return true; }
        let (Some(bot_u), Some(top_u)) = (idx.bot_idx, idx.top_idx) else { return false; };
        let (bot_i, top_i) = (bot_u as usize, top_u as usize);
        for a in 0..k {
            let up_a = &idx.up[a];
            if !up_a.test(a) || !idx.up[bot_i].test(a) || !up_a.test(top_i) { return false; }
            let (down_a, rep_a) = (&idx.down[a], idx.scc_rep[a]);
            for b in (a + 1)..k {
                let (up_b, down_b) = (&idx.up[b], &idx.down[b]);
                let (ab, ba, rep_b) = (up_a.test(b), up_b.test(a), idx.scc_rep[b]);
                if ab && !ba {
                    if !up_b.is_subset(up_a) || !down_a.is_subset(down_b) { return false; }
                    continue;
                }
                if ba && !ab {
                    if !up_a.is_subset(up_b) || !down_b.is_subset(down_a) { return false; }
                    continue;
                }
                if ab && ba && (rep_a != rep_b || up_a != up_b || down_a != down_b) { return false; }
                let (jab, jba, mab, mba) = (idx.join_idx(a, b), idx.join_idx(b, a), idx.meet_idx(a, b), idx.meet_idx(b, a));
                let cu = up_a.bitand(up_b);
                if !cu.test(jab) || !cu.test(jba) || !cu.is_subset(&idx.up[jab]) || !cu.is_subset(&idx.up[jba]) { return false; }
                let cd = down_a.bitand(down_b);
                if !cd.test(mab) || !cd.test(mba) || !cd.is_subset(&idx.down[mab]) || !cd.is_subset(&idx.down[mba]) { return false; }
                if idx.scc_rep[jab] != idx.scc_rep[jba] || idx.scc_rep[mab] != idx.scc_rep[mba] { return false; }
                if idx.scc_rep[idx.join_idx(a, mab)] != rep_a || idx.scc_rep[idx.meet_idx(a, jab)] != rep_a { return false; }
                if idx.scc_rep[idx.join_idx(b, mba)] != rep_b || idx.scc_rep[idx.meet_idx(b, jba)] != rep_b { return false; }
            }
        }
        true
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use super::super::MAX_FAST_LATTICE_K;
    use crate::cpn::mcard_token::DEFAULT_TIMESTAMP;

    #[test]
    fn test_place_type_lattice_laws_and_multiword_fallback() {
        let mk_p = |id: &str| PlaceMCard::create(id, "any", None, "Intermediate", Some("blake3"), Some(DEFAULT_TIMESTAMP)).unwrap();
        let mk_t = |id: &str, u: &str, v: &str| {
            TransitionMCard::create(id, vec![u.into()], vec![v.into()], "any", "any", None, "id", Some("blake3"), Some(DEFAULT_TIMESTAMP)).unwrap()
        };
        let places = vec![mk_p("a"), mk_p("b"), mk_p("u"), mk_p("v")];
        let transitions = vec![mk_t("t_au", "a", "u"), mk_t("t_av", "a", "v"), mk_t("t_bu", "b", "u"), mk_t("t_bv", "b", "v")];
        assert!(!PlaceTypeLattice::from_net_with_options(&places, &transitions, None, false).verify_lattice_laws());
        let completed = PlaceTypeLattice::from_net(&places, &transitions, None);
        assert!(completed.verify_lattice_laws());
        assert_eq!(completed.join("a", "b"), "__dm_cut__a_b__to__u_v__");
        assert_eq!(completed.meet("u", "v"), "__dm_cut__a_b__to__u_v__");

        let mut big_p: Vec<PlaceMCard> = (0..260).map(|i| mk_p(&format!("c{i:03}"))).collect();
        big_p.extend(["bw_a", "bw_b", "bw_u", "bw_v"].into_iter().map(mk_p));
        let mut big_t: Vec<TransitionMCard> = (0..259).map(|i| mk_t(&format!("tc{i:03}"), &format!("c{i:03}"), &format!("c{:03}", i + 1))).collect();
        big_t.extend([
            mk_t("tb_ia", "c010", "bw_a"), mk_t("tb_ib", "c010", "bw_b"),
            mk_t("tb_au", "bw_a", "bw_u"), mk_t("tb_av", "bw_a", "bw_v"),
            mk_t("tb_bu", "bw_b", "bw_u"), mk_t("tb_bv", "bw_b", "bw_v"),
            mk_t("tb_ou", "bw_u", "c250"), mk_t("tb_ov", "bw_v", "c250"),
        ]);
        let big = PlaceTypeLattice::from_net(&big_p, &big_t, None);
        assert!(big.reachability.len() > MAX_FAST_LATTICE_K);
        assert!(big.verify_lattice_laws());
        assert_eq!(big.join("bw_a", "bw_b"), "__dm_cut__bw_a_bw_b__to__bw_u_bw_v__");
    }
}