clawft_kernel/
mesh_tree.rs

1//! Resource tree synchronization for mesh networking (K6.4).
2//!
3//! Defines types for comparing and synchronizing resource tree state
4//! between mesh nodes using Merkle root hash comparison and incremental
5//! diff transfer.
6
7use std::collections::HashMap;
8
9use serde::{Deserialize, Serialize};
10
11/// Request to sync tree state from a peer.
12#[derive(Debug, Clone, Serialize, Deserialize)]
13pub struct TreeSyncRequest {
14    /// Local Merkle root hash.
15    pub local_root_hash: String,
16    /// Number of nodes in local tree.
17    pub local_node_count: usize,
18    /// Whether to request a full snapshot (vs. incremental diff).
19    pub full_snapshot: bool,
20}
21
22/// Response with tree state for sync.
23#[derive(Debug, Clone, Serialize, Deserialize)]
24pub struct TreeSyncResponse {
25    /// Remote Merkle root hash.
26    pub remote_root_hash: String,
27    /// Whether trees are already in sync.
28    pub in_sync: bool,
29    /// Changed/new nodes (if not in_sync).
30    pub diff_nodes: Vec<TreeNodeDiff>,
31    /// Deleted node paths (if any).
32    pub deleted_paths: Vec<String>,
33}
34
35/// A diff entry for a single tree node.
36#[derive(Debug, Clone, Serialize, Deserialize)]
37pub struct TreeNodeDiff {
38    /// Resource path.
39    pub path: String,
40    /// Resource kind (e.g., "namespace", "service", "agent").
41    pub kind: String,
42    /// Node hash after the change.
43    pub hash: String,
44    /// Metadata key-value pairs.
45    pub metadata: HashMap<String, String>,
46    /// Chain sequence that caused this change.
47    pub chain_seq: Option<u64>,
48    /// Type of diff.
49    pub diff_type: TreeDiffType,
50}
51
52/// Type of tree diff entry.
53#[non_exhaustive]
54#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
55pub enum TreeDiffType {
56    /// Node was added.
57    Added,
58    /// Node metadata was modified.
59    Modified,
60    /// Node was removed.
61    Removed,
62}
63
64/// Merkle proof for a specific tree node.
65#[derive(Debug, Clone, Serialize, Deserialize)]
66pub struct MerkleProof {
67    /// Path of the node being proven.
68    pub path: String,
69    /// Hash of the node.
70    pub node_hash: String,
71    /// Sibling hashes along the path from node to root.
72    pub sibling_hashes: Vec<String>,
73    /// Expected root hash.
74    pub root_hash: String,
75}
76
77impl MerkleProof {
78    /// Structural validation (non-empty fields). For full cryptographic
79    /// verification use `from_inclusion` +
80    /// `exo_resource_tree::MerkleInclusionProof::verify` (WEFT-106).
81    pub fn verify(&self) -> bool {
82        !self.path.is_empty() && !self.node_hash.is_empty() && !self.root_hash.is_empty()
83    }
84
85    /// Build a wire-format proof from a cryptographic inclusion proof.
86    #[cfg(feature = "exochain")]
87    pub fn from_inclusion(proof: &exo_resource_tree::MerkleInclusionProof) -> Self {
88        let sibling_hashes: Vec<String> = proof
89            .levels
90            .iter()
91            .flat_map(|level| {
92                level
93                    .child_hashes_sorted
94                    .iter()
95                    .map(|h| h.iter().map(|b| format!("{b:02x}")).collect::<String>())
96            })
97            .collect();
98        Self {
99            path: proof.path.to_string(),
100            node_hash: proof
101                .node_hash
102                .iter()
103                .map(|b| format!("{b:02x}"))
104                .collect(),
105            sibling_hashes,
106            root_hash: proof
107                .root_hash
108                .iter()
109                .map(|b| format!("{b:02x}"))
110                .collect(),
111        }
112    }
113}
114
115/// Compare two tree roots to determine sync action.
116pub fn compare_tree_roots(local_hash: &str, remote_hash: &str) -> TreeSyncAction {
117    if local_hash == remote_hash {
118        TreeSyncAction::InSync
119    } else if local_hash.is_empty() {
120        TreeSyncAction::FullPull
121    } else if remote_hash.is_empty() {
122        TreeSyncAction::FullPush
123    } else {
124        TreeSyncAction::IncrementalSync
125    }
126}
127
128/// Sync action based on tree root comparison.
129#[non_exhaustive]
130#[derive(Debug, Clone, Copy, PartialEq, Eq)]
131pub enum TreeSyncAction {
132    /// Trees are identical.
133    InSync,
134    /// Local tree is empty -- pull full snapshot from remote.
135    FullPull,
136    /// Remote tree is empty -- push full snapshot to remote.
137    FullPush,
138    /// Both have content but differ -- do incremental Merkle diff.
139    IncrementalSync,
140}
141
142// ── Tests ────────────────────────────────────────────────────────
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147
148    #[test]
149    fn tree_sync_request_serde_roundtrip() {
150        let req = TreeSyncRequest {
151            local_root_hash: "abc123".into(),
152            local_node_count: 42,
153            full_snapshot: false,
154        };
155        let json = serde_json::to_string(&req).unwrap();
156        let decoded: TreeSyncRequest = serde_json::from_str(&json).unwrap();
157        assert_eq!(decoded.local_root_hash, "abc123");
158        assert_eq!(decoded.local_node_count, 42);
159        assert!(!decoded.full_snapshot);
160    }
161
162    #[test]
163    fn tree_sync_response_serde_roundtrip() {
164        let resp = TreeSyncResponse {
165            remote_root_hash: "root_hash".into(),
166            in_sync: false,
167            diff_nodes: vec![TreeNodeDiff {
168                path: "/ns/svc".into(),
169                kind: "service".into(),
170                hash: "node_hash".into(),
171                metadata: HashMap::from([("version".into(), "1".into())]),
172                chain_seq: Some(5),
173                diff_type: TreeDiffType::Added,
174            }],
175            deleted_paths: vec!["/ns/old".into()],
176        };
177        let json = serde_json::to_string(&resp).unwrap();
178        let decoded: TreeSyncResponse = serde_json::from_str(&json).unwrap();
179        assert_eq!(decoded.remote_root_hash, "root_hash");
180        assert!(!decoded.in_sync);
181        assert_eq!(decoded.diff_nodes.len(), 1);
182        assert_eq!(decoded.diff_nodes[0].path, "/ns/svc");
183        assert_eq!(decoded.diff_nodes[0].diff_type, TreeDiffType::Added);
184        assert_eq!(decoded.deleted_paths, vec!["/ns/old"]);
185    }
186
187    #[test]
188    fn tree_node_diff_serde_roundtrip() {
189        let diff = TreeNodeDiff {
190            path: "/agents/bot-1".into(),
191            kind: "agent".into(),
192            hash: "diff_hash".into(),
193            metadata: HashMap::new(),
194            chain_seq: None,
195            diff_type: TreeDiffType::Modified,
196        };
197        let json = serde_json::to_string(&diff).unwrap();
198        let decoded: TreeNodeDiff = serde_json::from_str(&json).unwrap();
199        assert_eq!(decoded.path, "/agents/bot-1");
200        assert_eq!(decoded.kind, "agent");
201        assert_eq!(decoded.diff_type, TreeDiffType::Modified);
202        assert!(decoded.chain_seq.is_none());
203    }
204
205    #[test]
206    fn merkle_proof_verify_valid() {
207        let proof = MerkleProof {
208            path: "/ns/svc".into(),
209            node_hash: "node_abc".into(),
210            sibling_hashes: vec!["sib1".into(), "sib2".into()],
211            root_hash: "root_xyz".into(),
212        };
213        assert!(proof.verify());
214    }
215
216    #[test]
217    fn merkle_proof_verify_empty_fields() {
218        let empty_path = MerkleProof {
219            path: "".into(),
220            node_hash: "abc".into(),
221            sibling_hashes: vec![],
222            root_hash: "root".into(),
223        };
224        assert!(!empty_path.verify());
225
226        let empty_node = MerkleProof {
227            path: "/x".into(),
228            node_hash: "".into(),
229            sibling_hashes: vec![],
230            root_hash: "root".into(),
231        };
232        assert!(!empty_node.verify());
233
234        let empty_root = MerkleProof {
235            path: "/x".into(),
236            node_hash: "abc".into(),
237            sibling_hashes: vec![],
238            root_hash: "".into(),
239        };
240        assert!(!empty_root.verify());
241    }
242
243    #[test]
244    fn compare_tree_roots_in_sync() {
245        assert_eq!(
246            compare_tree_roots("hash_a", "hash_a"),
247            TreeSyncAction::InSync
248        );
249    }
250
251    #[test]
252    fn compare_tree_roots_full_pull() {
253        assert_eq!(
254            compare_tree_roots("", "hash_remote"),
255            TreeSyncAction::FullPull
256        );
257    }
258
259    #[test]
260    fn compare_tree_roots_full_push() {
261        assert_eq!(
262            compare_tree_roots("hash_local", ""),
263            TreeSyncAction::FullPush
264        );
265    }
266
267    #[test]
268    fn compare_tree_roots_incremental() {
269        assert_eq!(
270            compare_tree_roots("hash_a", "hash_b"),
271            TreeSyncAction::IncrementalSync
272        );
273    }
274
275    #[test]
276    fn tree_diff_type_variants() {
277        // Ensure all variants serialize/deserialize correctly.
278        for variant in [
279            TreeDiffType::Added,
280            TreeDiffType::Modified,
281            TreeDiffType::Removed,
282        ] {
283            let json = serde_json::to_string(&variant).unwrap();
284            let decoded: TreeDiffType = serde_json::from_str(&json).unwrap();
285            assert_eq!(decoded, variant);
286        }
287    }
288}
clawft_kernel/mesh_tree.rs

clawft_kernel/
mesh_tree.rs
