clm-kernel 0.0.4

Cubical Logic Model (CLM) sovereign execution engine, CPN-VM, and Cordis spatiotemporal substrate
Documentation
//! Compressed Sparse Incidence Matrix for High-Performance CPN Transition Evaluation (INV-419).
//!
//! Replaces dense 2D matrix traversals with compressed sparse adjacency lists.
//! Provides zero-allocation in-place transition firing.

use serde::{Deserialize, Serialize};

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct SparseIncidenceMatrix {
    pub place_count: usize,
    pub trans_count: usize,
    /// For each transition, list of (place_idx, tokens_consumed)
    pub consumed: Vec<Vec<(usize, i64)>>,
    /// For each transition, list of (place_idx, tokens_produced)
    pub produced: Vec<Vec<(usize, i64)>>,
    /// Net delta per transition: list of (place_idx, delta)
    pub deltas: Vec<Vec<(usize, i64)>>,
}

impl SparseIncidenceMatrix {
    /// Create a SparseIncidenceMatrix from a dense incidence matrix D (rows=places, cols=transitions).
    pub fn from_dense(d: &[Vec<i64>], place_count: usize, trans_count: usize) -> Self {
        let mut consumed = vec![Vec::new(); trans_count];
        let mut produced = vec![Vec::new(); trans_count];
        let mut deltas = vec![Vec::new(); trans_count];

        for t in 0..trans_count {
            for p in 0..place_count {
                let val = if p < d.len() && t < d[p].len() {
                    d[p][t]
                } else {
                    0
                };
                if val < 0 {
                    consumed[t].push((p, -val));
                    deltas[t].push((p, val));
                } else if val > 0 {
                    produced[t].push((p, val));
                    deltas[t].push((p, val));
                }
            }
        }

        Self {
            place_count,
            trans_count,
            consumed,
            produced,
            deltas,
        }
    }

    /// Check if transition `t` is enabled under the given marking slice.
    #[inline]
    pub fn is_enabled(&self, t: usize, marking: &[i64]) -> bool {
        if t >= self.trans_count {
            return false;
        }
        for &(p, required) in &self.consumed[t] {
            if p >= marking.len() || marking[p] < required {
                return false;
            }
        }
        true
    }

    /// Fire transition `t` in-place on `marking` with zero heap allocations.
    /// Returns Ok(true) on success, or Err if transition was not enabled.
    #[inline]
    pub fn fire(&self, t: usize, marking: &mut [i64]) -> Result<(), &'static str> {
        if !self.is_enabled(t, marking) {
            return Err("Transition not enabled by current marking");
        }

        // Apply deltas directly
        for &(p, delta) in &self.deltas[t] {
            if p < marking.len() {
                marking[p] += delta;
            }
        }
        Ok(())
    }

    /// Compute the net delta vector for transition `t` into `out_delta`.
    #[inline]
    pub fn get_delta(&self, t: usize, out_delta: &mut [i64]) {
        for v in out_delta.iter_mut() {
            *v = 0;
        }
        if t < self.trans_count {
            for &(p, delta) in &self.deltas[t] {
                if p < out_delta.len() {
                    out_delta[p] = delta;
                }
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_sparse_from_dense_and_fire() {
        // D: p0 -> t0 -> p1
        // D = [ [-1], [1] ]
        let d = vec![vec![-1], vec![1]];
        let sparse = SparseIncidenceMatrix::from_dense(&d, 2, 1);

        assert_eq!(sparse.consumed[0], vec![(0, 1)]);
        assert_eq!(sparse.produced[0], vec![(1, 1)]);

        let mut marking = vec![3, 0];
        assert!(sparse.is_enabled(0, &marking));

        sparse.fire(0, &mut marking).expect("Fire should succeed");
        assert_eq!(marking, vec![2, 1]);

        sparse.fire(0, &mut marking).expect("Fire should succeed");
        assert_eq!(marking, vec![1, 2]);

        sparse.fire(0, &mut marking).expect("Fire should succeed");
        assert_eq!(marking, vec![0, 3]);

        assert!(!sparse.is_enabled(0, &marking));
        assert!(sparse.fire(0, &mut marking).is_err());
    }
}