clm-kernel 0.0.15

Cubical Logic Model (CLM) sovereign execution engine, CPN-VM, and Cordis spatiotemporal substrate
Documentation
//! Merkle Lineage Graph Engine (Sprint 395, Sprint 552 / INV-552).
//!
//! Tracks causal ancestry and Merkle provenance across multi-step Action workflows:
//! (Parent MCards, Action Hash, VCard Receipt) --> Output MCard.

use serde::{Deserialize, Serialize};
use std::collections::{HashMap, HashSet, VecDeque};

/// A node in the Merkle lineage provenance graph.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct LineageNode {
    pub id: String,
    #[serde(rename = "type")]
    pub node_type: String,
    pub label: String,
    pub hash: String,
    #[serde(default)]
    pub metadata: HashMap<String, serde_json::Value>,
}

/// A causal directed edge in the lineage provenance graph.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct LineageEdge {
    pub source: String,
    pub target: String,
    pub relation: String,
}

/// Reconstructed directed acyclic graph of MCard provenance.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct LineageDAG {
    pub target_uri: String,
    pub nodes: HashMap<String, LineageNode>,
    pub edges: Vec<LineageEdge>,
}

/// Engine to record and query workflow causal provenance DAGs.
#[derive(Debug, Default, Clone)]
pub struct LineageEngine {
    nodes: HashMap<String, LineageNode>,
    edges: Vec<LineageEdge>,
}

impl LineageEngine {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn add_node(&mut self, node: LineageNode) {
        self.nodes.insert(node.id.clone(), node);
    }

    pub fn add_edge(&mut self, source: &str, target: &str, relation: &str) {
        self.edges.push(LineageEdge {
            source: source.to_string(),
            target: target.to_string(),
            relation: relation.to_string(),
        });
    }

    pub fn get_mcard_lineage(&self, target_uri: &str) -> LineageDAG {
        let mut reachable_nodes = HashMap::new();
        let mut reachable_edges = Vec::new();
        let mut queue = VecDeque::new();
        let mut visited = HashSet::new();

        queue.push_back(target_uri.to_string());

        while let Some(curr) = queue.pop_front() {
            if visited.contains(&curr) {
                continue;
            }
            visited.insert(curr.clone());

            if let Some(node) = self.nodes.get(&curr) {
                reachable_nodes.insert(curr.clone(), node.clone());
            }

            for edge in &self.edges {
                if edge.target == curr {
                    reachable_edges.push(edge.clone());
                    if !visited.contains(&edge.source) {
                        queue.push_back(edge.source.clone());
                    }
                }
            }
        }

        LineageDAG {
            target_uri: target_uri.to_string(),
            nodes: reachable_nodes,
            edges: reachable_edges,
        }
    }

    pub fn to_mermaid(&self, dag: &LineageDAG) -> String {
        let mut lines = vec!["flowchart TD".to_string()];
        for (id, node) in &dag.nodes {
            let short_hash = if node.hash.len() > 8 {
                &node.hash[..8]
            } else {
                &node.hash
            };
            lines.push(format!("  {}[\"{}\\n({}) \"]", id, node.label, short_hash));
        }
        for edge in &dag.edges {
            lines.push(format!("  {} -->|{}| {}", edge.source, edge.relation, edge.target));
        }
        lines.join("\n")
    }

    pub fn to_dot(&self, dag: &LineageDAG) -> String {
        let mut lines = vec!["digraph Lineage {".to_string(), "  rankdir=LR;".to_string()];
        for (id, node) in &dag.nodes {
            let short_hash = if node.hash.len() > 8 {
                &node.hash[..8]
            } else {
                &node.hash
            };
            lines.push(format!("  \"{}\" [label=\"{}\\n{}\"];", id, node.label, short_hash));
        }
        for edge in &dag.edges {
            lines.push(format!("  \"{}\" -> \"{}\" [label=\"{}\"];", edge.source, edge.target, edge.relation));
        }
        lines.push("}".to_string());
        lines.join("\n")
    }
}