Skip to main content

clm_rust_core/layer2/
workflow_lineage.rs

1//! Merkle Lineage Graph Engine (Sprint 395, Sprint 552 / INV-552).
2//!
3//! Tracks causal ancestry and Merkle provenance across multi-step Action workflows:
4//! (Parent MCards, Action Hash, VCard Receipt) --> Output MCard.
5
6use serde::{Deserialize, Serialize};
7use std::collections::{HashMap, HashSet, VecDeque};
8
9/// A node in the Merkle lineage provenance graph.
10#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
11pub struct LineageNode {
12    pub id: String,
13    #[serde(rename = "type")]
14    pub node_type: String,
15    pub label: String,
16    pub hash: String,
17    #[serde(default)]
18    pub metadata: HashMap<String, serde_json::Value>,
19}
20
21/// A causal directed edge in the lineage provenance graph.
22#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
23pub struct LineageEdge {
24    pub source: String,
25    pub target: String,
26    pub relation: String,
27}
28
29/// Reconstructed directed acyclic graph of MCard provenance.
30#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
31pub struct LineageDAG {
32    pub target_uri: String,
33    pub nodes: HashMap<String, LineageNode>,
34    pub edges: Vec<LineageEdge>,
35}
36
37/// Engine to record and query workflow causal provenance DAGs.
38#[derive(Debug, Default, Clone)]
39pub struct LineageEngine {
40    nodes: HashMap<String, LineageNode>,
41    edges: Vec<LineageEdge>,
42}
43
44impl LineageEngine {
45    pub fn new() -> Self {
46        Self::default()
47    }
48
49    pub fn add_node(&mut self, node: LineageNode) {
50        self.nodes.insert(node.id.clone(), node);
51    }
52
53    pub fn add_edge(&mut self, source: &str, target: &str, relation: &str) {
54        self.edges.push(LineageEdge {
55            source: source.to_string(),
56            target: target.to_string(),
57            relation: relation.to_string(),
58        });
59    }
60
61    pub fn get_mcard_lineage(&self, target_uri: &str) -> LineageDAG {
62        let mut reachable_nodes = HashMap::new();
63        let mut reachable_edges = Vec::new();
64        let mut queue = VecDeque::new();
65        let mut visited = HashSet::new();
66
67        queue.push_back(target_uri.to_string());
68
69        while let Some(curr) = queue.pop_front() {
70            if visited.contains(&curr) {
71                continue;
72            }
73            visited.insert(curr.clone());
74
75            if let Some(node) = self.nodes.get(&curr) {
76                reachable_nodes.insert(curr.clone(), node.clone());
77            }
78
79            for edge in &self.edges {
80                if edge.target == curr {
81                    reachable_edges.push(edge.clone());
82                    if !visited.contains(&edge.source) {
83                        queue.push_back(edge.source.clone());
84                    }
85                }
86            }
87        }
88
89        LineageDAG {
90            target_uri: target_uri.to_string(),
91            nodes: reachable_nodes,
92            edges: reachable_edges,
93        }
94    }
95
96    pub fn to_mermaid(&self, dag: &LineageDAG) -> String {
97        let mut lines = vec!["flowchart TD".to_string()];
98        for (id, node) in &dag.nodes {
99            let short_hash = if node.hash.len() > 8 {
100                &node.hash[..8]
101            } else {
102                &node.hash
103            };
104            lines.push(format!("  {}[\"{}\\n({}) \"]", id, node.label, short_hash));
105        }
106        for edge in &dag.edges {
107            lines.push(format!("  {} -->|{}| {}", edge.source, edge.relation, edge.target));
108        }
109        lines.join("\n")
110    }
111
112    pub fn to_dot(&self, dag: &LineageDAG) -> String {
113        let mut lines = vec!["digraph Lineage {".to_string(), "  rankdir=LR;".to_string()];
114        for (id, node) in &dag.nodes {
115            let short_hash = if node.hash.len() > 8 {
116                &node.hash[..8]
117            } else {
118                &node.hash
119            };
120            lines.push(format!("  \"{}\" [label=\"{}\\n{}\"];", id, node.label, short_hash));
121        }
122        for edge in &dag.edges {
123            lines.push(format!("  \"{}\" -> \"{}\" [label=\"{}\"];", edge.source, edge.target, edge.relation));
124        }
125        lines.push("}".to_string());
126        lines.join("\n")
127    }
128}