clm-kernel 0.0.2

Cubical Logic Model (CLM) sovereign execution engine, CPN-VM, and Cordis spatiotemporal substrate
Documentation
pub fn math_gcd(mut a: i64, mut b: i64) -> i64 {
    a = a.abs();
    b = b.abs();
    while b > 0 {
        let t = b;
        b = a % b;
        a = t;
    }
    a
}

pub fn math_lcm(a: i64, b: i64) -> i64 {
    if a == 0 || b == 0 {
        return 0;
    }
    let gcd = math_gcd(a, b);
    ((a * b) / gcd).abs()
}

pub fn solve_nullspace(
    matrix: &[Vec<i64>],
    rows: usize,
    cols: usize,
    transpose: bool,
) -> Vec<Vec<i64>> {
    let (work_rows, work_cols) = if transpose {
        (cols, rows)
    } else {
        (rows, cols)
    };

    // Initialize working matrix A
    let mut a_mat = vec![vec![0; work_cols]; work_rows];
    for r in 0..work_rows {
        for c in 0..work_cols {
            a_mat[r][c] = if transpose {
                if c < matrix.len() && r < matrix[c].len() {
                    matrix[c][r]
                } else {
                    0
                }
            } else {
                if r < matrix.len() && c < matrix[r].len() {
                    matrix[r][c]
                } else {
                    0
                }
            };
        }
    }

    let mut pivot_row = vec![-1; work_cols];
    let mut is_free = vec![true; work_cols];

    let mut p = 0;
    let mut c = 0;

    while c < work_cols && p < work_rows {
        // Find pivot row
        let mut pr = p;
        let mut found = false;
        while pr < work_rows {
            if a_mat[pr][c] != 0 {
                found = true;
                break;
            }
            pr += 1;
        }

        if !found {
            c += 1;
            continue;
        }

        // Swap row pr and p if needed
        if pr != p {
            a_mat.swap(p, pr);
        }

        let pivot = a_mat[p][c];
        is_free[c] = false;
        pivot_row[c] = p as i32;

        // Eliminate other rows
        for i in 0..work_rows {
            if i != p {
                let val_i = a_mat[i][c];
                if val_i != 0 {
                    let g = math_gcd(pivot, val_i);
                    let factor_p = val_i / g;
                    let factor_i = pivot / g;

                    for j in 0..work_cols {
                        a_mat[i][j] = factor_i * a_mat[i][j] - factor_p * a_mat[p][j];
                    }

                    // Simplify row i
                    let mut r_gcd = 0;
                    for j in 0..work_cols {
                        r_gcd = math_gcd(r_gcd, a_mat[i][j]);
                    }
                    if r_gcd > 1 {
                        for j in 0..work_cols {
                            a_mat[i][j] /= r_gcd;
                        }
                    }
                }
            }
        }

        // Simplify pivot row
        let mut p_gcd = 0;
        for j in 0..work_cols {
            p_gcd = math_gcd(p_gcd, a_mat[p][j]);
        }
        if p_gcd > 1 {
            for j in 0..work_cols {
                a_mat[p][j] /= p_gcd;
            }
        }

        p += 1;
        c += 1;
    }

    // Back-Substitution & Basis Generation
    let mut basis_vectors = Vec::new();

    for f in 0..work_cols {
        if is_free[f] {
            let mut num_vec = vec![0; work_cols];
            let mut den_vec = vec![1; work_cols];

            for j in 0..work_cols {
                if is_free[j] {
                    if j == f {
                        num_vec[j] = 1;
                        den_vec[j] = 1;
                    } else {
                        num_vec[j] = 0;
                        den_vec[j] = 1;
                    }
                } else {
                    let pr = pivot_row[j] as usize;
                    let a_pr_j = a_mat[pr][j];
                    let a_pr_f = a_mat[pr][f];

                    let mut num = -a_pr_f;
                    let mut den = a_pr_j;
                    if den < 0 {
                        num = -num;
                        den = -den;
                    }
                    let g = math_gcd(num, den);
                    num_vec[j] = num / g;
                    den_vec[j] = den / g;
                }
            }

            // Find LCM of denominators
            let mut lcm = 1;
            for j in 0..work_cols {
                lcm = math_lcm(lcm, den_vec[j]);
            }

            // Multiply by LCM to get integer vector
            let mut int_vec = vec![0; work_cols];
            for j in 0..work_cols {
                int_vec[j] = num_vec[j] * (lcm / den_vec[j]);
            }

            // Simplify vector by dividing by overall GCD
            let mut vec_gcd = 0;
            for j in 0..work_cols {
                vec_gcd = math_gcd(vec_gcd, int_vec[j]);
            }
            if vec_gcd > 1 {
                for j in 0..work_cols {
                    int_vec[j] /= vec_gcd;
                }
            }

            // Normalize direction (ensure non-negativity if all components have same sign)
            let mut all_non_positive = true;
            for j in 0..work_cols {
                if int_vec[j] > 0 {
                    all_non_positive = false;
                    break;
                }
            }
            if all_non_positive {
                for j in 0..work_cols {
                    int_vec[j] = -int_vec[j];
                }
            }

            basis_vectors.push(int_vec);
        }
    }

    basis_vectors
}

/// Pre-computed nullspace basis for Noetherian P-invariants (INV-419).
/// Replaces dynamic Gaussian elimination during transitions with O(1) dot-product checks.
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct PrecomputedInvariants {
    /// Basis vectors v_k where D^T · v_k = 0 (or x^T · D = 0).
    pub basis_vectors: Vec<Vec<i64>>,
    /// Expected invariant constants w · M_0 for initial marking M_0.
    pub initial_constants: Vec<i64>,
}

impl PrecomputedInvariants {
    /// Compile nullspace invariants from an incidence matrix D and initial marking.
    pub fn compile(matrix: &[Vec<i64>], rows: usize, cols: usize, initial_marking: &[i64]) -> Self {
        let basis_vectors = solve_nullspace(matrix, rows, cols, true);
        let mut initial_constants = Vec::with_capacity(basis_vectors.len());
        for b in &basis_vectors {
            let mut sum = 0i64;
            for (p_idx, &w) in b.iter().enumerate() {
                if p_idx < initial_marking.len() {
                    sum += w * initial_marking[p_idx];
                }
            }
            initial_constants.push(sum);
        }
        Self {
            basis_vectors,
            initial_constants,
        }
    }

    /// Fast-path check: returns true if current marking satisfies all basis conservation laws.
    /// Runs in O(k * P) where k is number of basis invariants and P is place count.
    #[inline]
    pub fn verify_marking(&self, marking: &[i64]) -> bool {
        for (i, b) in self.basis_vectors.iter().enumerate() {
            let mut sum = 0i64;
            for (p_idx, &w) in b.iter().enumerate() {
                if p_idx < marking.len() {
                    sum += w * marking[p_idx];
                }
            }
            if i < self.initial_constants.len() && sum != self.initial_constants[i] {
                return false;
            }
        }
        true
    }

    /// Fast-path check on marking delta ΔM: returns true if ΔM · v_k == 0 for all basis vectors.
    #[inline]
    pub fn verify_delta(&self, delta: &[i64]) -> bool {
        for b in &self.basis_vectors {
            let mut sum = 0i64;
            for (p_idx, &w) in b.iter().enumerate() {
                if p_idx < delta.len() {
                    sum += w * delta[p_idx];
                }
            }
            if sum != 0 {
                return false;
            }
        }
        true
    }
}

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

    #[test]
    fn test_gcd() {
        assert_eq!(math_gcd(12, 18), 6);
        assert_eq!(math_gcd(18, 12), 6);
        assert_eq!(math_gcd(-8, 12), 4);
        assert_eq!(math_gcd(12, -8), 4);
        assert_eq!(math_gcd(0, 5), 5);
        assert_eq!(math_gcd(5, 0), 5);
        assert_eq!(math_gcd(0, 0), 0);
    }

    #[test]
    fn test_lcm() {
        assert_eq!(math_lcm(4, 6), 12);
        assert_eq!(math_lcm(7, 13), 91);
        assert_eq!(math_lcm(0, 5), 0);
    }

    #[test]
    fn test_solve_nullspace_1() {
        // D = [ -1 ]
        //     [  1 ]
        // Transpose = true => A = [ -1 1 ]
        let matrix = vec![vec![-1], vec![1]];
        let basis = solve_nullspace(&matrix, 2, 1, true);
        assert_eq!(basis.len(), 1);
        assert_eq!(basis[0], vec![1, 1]);
    }

    #[test]
    fn test_precomputed_invariants() {
        let matrix = vec![vec![-1], vec![1]];
        let initial_marking = vec![5, 0];
        let precomputed = PrecomputedInvariants::compile(&matrix, 2, 1, &initial_marking);

        assert_eq!(precomputed.initial_constants, vec![5]);
        // Valid marking [3, 2] -> sum = 5
        assert!(precomputed.verify_marking(&[3, 2]));
        // Invalid marking [3, 3] -> sum = 6 != 5
        assert!(!precomputed.verify_marking(&[3, 3]));

        // Delta for valid transition: [-1, 1] -> dot product = 0
        assert!(precomputed.verify_delta(&[-1, 1]));
        // Delta for invalid transition: [-1, 2] -> dot product = 1 != 0
        assert!(!precomputed.verify_delta(&[-1, 2]));
    }
}