leptos_sync_core/crdt/advanced/
yjs_tree.rs

1//! Yjs-style tree for hierarchical data
2
3use super::common::{PositionId, AdvancedCrdtError};
4use super::super::{CRDT, Mergeable, ReplicaId};
5use serde::{Deserialize, Serialize};
6use std::collections::HashMap;
7
8/// Yjs-style tree node
9#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
10pub struct YjsNode<T> {
11    /// Unique node identifier
12    pub id: PositionId,
13    /// Node value
14    pub value: T,
15    /// Parent node ID
16    pub parent: Option<PositionId>,
17    /// Child node IDs
18    pub children: Vec<PositionId>,
19    /// Whether the node is visible (not deleted)
20    pub visible: bool,
21}
22
23impl<T> YjsNode<T> {
24    /// Create a new Yjs node
25    pub fn new(id: PositionId, value: T, parent: Option<PositionId>) -> Self {
26        Self {
27            id,
28            value,
29            parent,
30            children: Vec::new(),
31            visible: true,
32        }
33    }
34}
35
36/// Tree node for display purposes
37#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
38pub struct YjsTreeNode<T> {
39    /// Node ID
40    pub id: PositionId,
41    /// Node value
42    pub value: T,
43    /// Child nodes
44    pub children: Vec<YjsTreeNode<T>>,
45}
46
47/// Yjs-style tree for hierarchical data
48#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
49pub struct YjsTree<T> {
50    /// Replica ID
51    replica_id: ReplicaId,
52    /// Nodes indexed by ID
53    nodes: HashMap<PositionId, YjsNode<T>>,
54    /// Root node ID
55    root: Option<PositionId>,
56    /// Logical timestamp counter
57    timestamp_counter: u64,
58    /// Disambiguation counter
59    disambiguation_counter: u64,
60}
61
62impl<T: Clone + PartialEq> YjsTree<T> {
63    /// Create a new Yjs tree
64    pub fn new(replica_id: ReplicaId) -> Self {
65        Self {
66            replica_id,
67            nodes: HashMap::new(),
68            root: None,
69            timestamp_counter: 0,
70            disambiguation_counter: 0,
71        }
72    }
73    
74    /// Add a root node
75    pub fn add_root(&mut self, value: T) -> Result<PositionId, AdvancedCrdtError> {
76        self.timestamp_counter += 1;
77        self.disambiguation_counter += 1;
78        
79        let id = PositionId::new(
80            self.replica_id.clone(),
81            self.timestamp_counter,
82            self.disambiguation_counter,
83        );
84        
85        let node = YjsNode::new(id.clone(), value, None);
86        self.nodes.insert(id.clone(), node);
87        self.root = Some(id.clone());
88        
89        Ok(id)
90    }
91    
92    /// Add a child node
93    pub fn add_child(&mut self, parent_id: &PositionId, value: T) -> Result<PositionId, AdvancedCrdtError> {
94        if !self.nodes.contains_key(parent_id) {
95            return Err(AdvancedCrdtError::ElementNotFound(format!("Parent {:?}", parent_id)));
96        }
97        
98        self.timestamp_counter += 1;
99        self.disambiguation_counter += 1;
100        
101        let id = PositionId::new(
102            self.replica_id.clone(),
103            self.timestamp_counter,
104            self.disambiguation_counter,
105        );
106        
107        let node = YjsNode::new(id.clone(), value, Some(parent_id.clone()));
108        self.nodes.insert(id.clone(), node);
109        
110        // Add to parent's children
111        if let Some(parent) = self.nodes.get_mut(parent_id) {
112            parent.children.push(id.clone());
113        }
114        
115        Ok(id)
116    }
117    
118    /// Delete a node
119    pub fn delete(&mut self, node_id: &PositionId) -> Result<(), AdvancedCrdtError> {
120        if let Some(node) = self.nodes.get_mut(node_id) {
121            node.visible = false;
122            Ok(())
123        } else {
124            Err(AdvancedCrdtError::ElementNotFound(format!("Node {:?}", node_id)))
125        }
126    }
127    
128    /// Get the tree structure as a nested structure
129    pub fn to_tree(&self) -> Option<YjsTreeNode<T>> {
130        if let Some(root_id) = &self.root {
131            self.build_tree_node(root_id)
132        } else {
133            None
134        }
135    }
136    
137    /// Build a tree node recursively
138    fn build_tree_node(&self, node_id: &PositionId) -> Option<YjsTreeNode<T>> {
139        if let Some(node) = self.nodes.get(node_id) {
140            if !node.visible {
141                return None;
142            }
143            
144            let children: Vec<YjsTreeNode<T>> = node.children
145                .iter()
146                .filter_map(|child_id| self.build_tree_node(child_id))
147                .collect();
148            
149            Some(YjsTreeNode {
150                id: node.id.clone(),
151                value: node.value.clone(),
152                children,
153            })
154        } else {
155            None
156        }
157    }
158    
159    /// Get node count
160    pub fn len(&self) -> usize {
161        self.nodes.len()
162    }
163    
164    /// Check if tree is empty
165    pub fn is_empty(&self) -> bool {
166        self.nodes.is_empty()
167    }
168}
169
170impl<T: Clone + PartialEq> CRDT for YjsTree<T> {
171    fn replica_id(&self) -> &ReplicaId {
172        &self.replica_id
173    }
174}
175
176impl<T: Clone + PartialEq + Send + Sync> Mergeable for YjsTree<T> {
177    type Error = AdvancedCrdtError;
178    
179    fn merge(&mut self, other: &Self) -> Result<(), Self::Error> {
180        // Merge all nodes from other tree
181        for (node_id, other_node) in &other.nodes {
182            if let Some(self_node) = self.nodes.get_mut(node_id) {
183                // Node exists in both, keep the one with higher timestamp
184                if other_node.id.timestamp > self_node.id.timestamp {
185                    *self_node = other_node.clone();
186                }
187            } else {
188                // Node only exists in other, add it
189                self.nodes.insert(node_id.clone(), other_node.clone());
190            }
191        }
192        
193        // Update root if other has a root and we don't, or if other's root is newer
194        if let Some(other_root) = &other.root {
195            if self.root.is_none() {
196                self.root = Some(other_root.clone());
197            } else if let Some(self_root) = &self.root {
198                if let (Some(other_root_node), Some(self_root_node)) = (
199                    other.nodes.get(other_root),
200                    self.nodes.get(self_root)
201                ) {
202                    if other_root_node.id.timestamp > self_root_node.id.timestamp {
203                        self.root = Some(other_root.clone());
204                    }
205                }
206            }
207        }
208        
209        Ok(())
210    }
211    
212    fn has_conflict(&self, other: &Self) -> bool {
213        // Check for conflicting nodes (same ID, different values)
214        for (node_id, self_node) in &self.nodes {
215            if let Some(other_node) = other.nodes.get(node_id) {
216                if self_node.value != other_node.value {
217                    return true;
218                }
219            }
220        }
221        false
222    }
223}
224
225#[cfg(test)]
226mod tests {
227    use super::*;
228    use super::super::super::ReplicaId;
229    use uuid::Uuid;
230    
231    fn create_replica(id: u64) -> ReplicaId {
232        ReplicaId::from(Uuid::from_u64_pair(0, id))
233    }
234    
235    #[test]
236    fn test_yjs_tree_creation() {
237        let replica_id = create_replica(1);
238        let tree = YjsTree::<String>::new(replica_id.clone());
239        
240        assert_eq!(tree.replica_id(), &replica_id);
241        assert!(tree.is_empty());
242        assert_eq!(tree.len(), 0);
243    }
244    
245    #[test]
246    fn test_yjs_tree_operations() {
247        let replica_id = create_replica(1);
248        let mut tree = YjsTree::<String>::new(replica_id);
249        
250        // Add root
251        let root_id = tree.add_root("root".to_string()).unwrap();
252        assert_eq!(tree.len(), 1);
253        
254        // Add children
255        let child1_id = tree.add_child(&root_id, "child1".to_string()).unwrap();
256        let child2_id = tree.add_child(&root_id, "child2".to_string()).unwrap();
257        assert_eq!(tree.len(), 3);
258        
259        // Add grandchild
260        let grandchild_id = tree.add_child(&child1_id, "grandchild".to_string()).unwrap();
261        assert_eq!(tree.len(), 4);
262        
263        // Delete node
264        tree.delete(&child2_id).unwrap();
265        assert_eq!(tree.len(), 4); // Node still exists but is invisible
266        
267        // Check tree structure
268        let tree_structure = tree.to_tree().unwrap();
269        assert_eq!(tree_structure.value, "root");
270        assert_eq!(tree_structure.children.len(), 1); // Only child1 is visible
271        assert_eq!(tree_structure.children[0].value, "child1");
272        assert_eq!(tree_structure.children[0].children.len(), 1);
273        assert_eq!(tree_structure.children[0].children[0].value, "grandchild");
274    }
275    
276    #[test]
277    fn test_yjs_tree_merge() {
278        let replica_id1 = create_replica(1);
279        let replica_id2 = create_replica(2);
280        
281        let mut tree1 = YjsTree::<String>::new(replica_id1);
282        let mut tree2 = YjsTree::<String>::new(replica_id2);
283        
284        // Add different roots
285        let root1_id = tree1.add_root("root1".to_string()).unwrap();
286        let root2_id = tree2.add_root("root2".to_string()).unwrap();
287        
288        // Add children
289        tree1.add_child(&root1_id, "child1".to_string()).unwrap();
290        tree2.add_child(&root2_id, "child2".to_string()).unwrap();
291        
292        // Merge
293        tree1.merge(&tree2).unwrap();
294        
295        // Should contain both trees
296        assert_eq!(tree1.len(), 4); // 2 roots + 2 children
297    }
298}
leptos_sync_core/crdt/advanced/yjs_tree.rs

leptos_sync_core/crdt/advanced/
yjs_tree.rs
