leptos_sync_core/crdt/
tree.rs

1use super::{CRDT, Mergeable, ReplicaId};
2use serde::{Deserialize, Serialize};
3use std::collections::HashMap;
4use std::error::Error;
5use uuid::Uuid;
6
7/// Custom error type for tree operations
8#[derive(Debug, Clone, PartialEq, Eq)]
9pub struct TreeError {
10    message: String,
11}
12
13impl TreeError {
14    pub fn new(message: String) -> Self {
15        Self { message }
16    }
17}
18
19impl std::fmt::Display for TreeError {
20    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
21        write!(f, "TreeError: {}", self.message)
22    }
23}
24
25impl Error for TreeError {}
26
27/// Unique identifier for a tree node
28#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
29pub struct NodeId {
30    /// Unique identifier for the node
31    pub id: Uuid,
32    /// Replica that created the node
33    pub replica: ReplicaId,
34}
35
36impl NodeId {
37    /// Create a new node ID
38    pub fn new(replica: ReplicaId) -> Self {
39        Self {
40            id: Uuid::new_v4(),
41            replica,
42        }
43    }
44
45    /// Create a node ID from existing UUID and replica
46    pub fn from_parts(id: Uuid, replica: ReplicaId) -> Self {
47        Self { id, replica }
48    }
49}
50
51/// Metadata for a tree node
52#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
53pub struct NodeMetadata {
54    /// When the node was created
55    pub created_at: u64,
56    /// When the node was last modified
57    pub modified_at: u64,
58    /// Whether the node is marked as deleted
59    pub deleted: bool,
60    /// Replica that last modified the node
61    pub last_modified_by: ReplicaId,
62}
63
64impl NodeMetadata {
65    /// Create new metadata
66    pub fn new(replica: ReplicaId, timestamp: u64) -> Self {
67        Self {
68            created_at: timestamp,
69            modified_at: timestamp,
70            deleted: false,
71            last_modified_by: replica,
72        }
73    }
74
75    /// Mark as modified
76    pub fn mark_modified(&mut self, replica: ReplicaId, timestamp: u64) {
77        self.modified_at = timestamp;
78        self.last_modified_by = replica;
79    }
80
81    /// Mark as deleted
82    pub fn mark_deleted(&mut self, replica: ReplicaId, timestamp: u64) {
83        self.deleted = true;
84        self.mark_modified(replica, timestamp);
85    }
86}
87
88/// A tree node with its metadata and relationships
89#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
90pub struct TreeNode<T> {
91    /// Unique identifier
92    pub id: NodeId,
93    /// The actual value
94    pub value: T,
95    /// Metadata
96    pub metadata: NodeMetadata,
97    /// Parent node ID (None for root)
98    pub parent: Option<NodeId>,
99    /// Child node IDs
100    pub children: Vec<NodeId>,
101}
102
103impl<T> TreeNode<T> {
104    /// Create a new tree node
105    pub fn new(value: T, replica: ReplicaId, timestamp: u64) -> Self {
106        Self {
107            id: NodeId::new(replica),
108            value,
109            metadata: NodeMetadata::new(replica, timestamp),
110            parent: None,
111            children: Vec::new(),
112        }
113    }
114
115    /// Create a child node
116    pub fn new_child(value: T, replica: ReplicaId, timestamp: u64, parent: NodeId) -> Self {
117        Self {
118            id: NodeId::new(replica),
119            value,
120            metadata: NodeMetadata::new(replica, timestamp),
121            parent: Some(parent),
122            children: Vec::new(),
123        }
124    }
125
126    /// Mark as modified
127    pub fn mark_modified(&mut self, replica: ReplicaId, timestamp: u64) {
128        self.metadata.mark_modified(replica, timestamp);
129    }
130
131    /// Mark as deleted
132    pub fn mark_deleted(&mut self, replica: ReplicaId, timestamp: u64) {
133        self.metadata.mark_deleted(replica, timestamp);
134    }
135
136    /// Add a child
137    pub fn add_child(&mut self, child_id: NodeId) {
138        self.children.push(child_id);
139    }
140
141    /// Remove a child
142    pub fn remove_child(&mut self, child_id: &NodeId) -> bool {
143        if let Some(pos) = self.children.iter().position(|id| id == child_id) {
144            self.children.remove(pos);
145            true
146        } else {
147            false
148        }
149    }
150}
151
152/// Strategy for handling tree conflicts
153#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
154pub enum TreeStrategy {
155    /// Add-Wins: Nodes are never removed, only marked as deleted
156    AddWins,
157    /// Remove-Wins: Deleted nodes are completely removed
158    RemoveWins,
159}
160
161/// Configuration for tree CRDTs
162#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
163pub struct TreeConfig {
164    /// Conflict resolution strategy
165    pub strategy: TreeStrategy,
166    /// Whether to preserve deleted nodes in metadata
167    pub preserve_deleted: bool,
168    /// Maximum depth of the tree
169    pub max_depth: Option<usize>,
170    /// Maximum number of children per node
171    pub max_children: Option<usize>,
172}
173
174impl Default for TreeConfig {
175    fn default() -> Self {
176        Self {
177            strategy: TreeStrategy::AddWins,
178            preserve_deleted: true,
179            max_depth: None,
180            max_children: None,
181        }
182    }
183}
184
185/// Add-Wins Tree CRDT implementation
186/// 
187/// This implementation ensures that nodes are never completely lost.
188/// Deleted nodes are marked as deleted but preserved for potential recovery.
189#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
190pub struct AddWinsTree<T> {
191    /// Configuration
192    config: TreeConfig,
193    /// Nodes in the tree
194    nodes: HashMap<NodeId, TreeNode<T>>,
195    /// Replica ID for this instance
196    replica: ReplicaId,
197}
198
199impl<T: Clone + PartialEq + Eq + Send + Sync> AddWinsTree<T> {
200    /// Create a new Add-Wins tree
201    pub fn new(replica: ReplicaId) -> Self {
202        Self {
203            config: TreeConfig::default(),
204            nodes: HashMap::new(),
205            replica,
206        }
207    }
208
209    /// Create with custom configuration
210    pub fn with_config(replica: ReplicaId, config: TreeConfig) -> Self {
211        Self {
212            config,
213            nodes: HashMap::new(),
214            replica,
215        }
216    }
217
218    /// Add a root node to the tree
219    pub fn add_root(&mut self, value: T, timestamp: u64) -> NodeId {
220        let node = TreeNode::new(value, self.replica, timestamp);
221        let id = node.id.clone();
222        self.nodes.insert(id.clone(), node);
223        id
224    }
225
226    /// Add a child node
227    pub fn add_child(&mut self, parent_id: &NodeId, value: T, timestamp: u64) -> Result<NodeId, TreeError> {
228        if !self.nodes.contains_key(parent_id) {
229            return Err(TreeError::new("Parent node not found".to_string()));
230        }
231
232        let node = TreeNode::new_child(value, self.replica, timestamp, parent_id.clone());
233        let id = node.id.clone();
234        
235        // Add the child node
236        self.nodes.insert(id.clone(), node);
237        
238        // Update parent's children list
239        if let Some(parent) = self.nodes.get_mut(parent_id) {
240            parent.add_child(id.clone());
241        }
242        
243        Ok(id)
244    }
245
246    /// Update an existing node
247    pub fn update(&mut self, id: &NodeId, value: T, timestamp: u64) -> Result<(), TreeError> {
248        if let Some(node) = self.nodes.get_mut(id) {
249            node.value = value;
250            node.mark_modified(self.replica, timestamp);
251            Ok(())
252        } else {
253            Err(TreeError::new("Node not found".to_string()))
254        }
255    }
256
257    /// Mark a node as deleted
258    pub fn remove(&mut self, id: &NodeId, timestamp: u64) -> Result<(), TreeError> {
259        if let Some(node) = self.nodes.get_mut(id) {
260            node.mark_deleted(self.replica, timestamp);
261            Ok(())
262        } else {
263            Err(TreeError::new("Node not found".to_string()))
264        }
265    }
266
267    /// Move a node to a new parent
268    pub fn move_node(&mut self, id: &NodeId, new_parent_id: &NodeId) -> Result<(), TreeError> {
269        if !self.nodes.contains_key(id) || !self.nodes.contains_key(new_parent_id) {
270            return Err(TreeError::new("Node not found".to_string()));
271        }
272
273        // Get the old parent ID first
274        let old_parent_id = self.nodes.get(id).and_then(|node| node.parent.clone());
275        
276        // Remove from old parent
277        if let Some(old_parent_id) = old_parent_id {
278            if let Some(old_parent) = self.nodes.get_mut(&old_parent_id) {
279                old_parent.remove_child(id);
280            }
281        }
282        
283        // Update the node's parent reference
284        if let Some(node) = self.nodes.get_mut(id) {
285            node.parent = Some(new_parent_id.clone());
286        }
287        
288        // Add to new parent
289        if let Some(new_parent) = self.nodes.get_mut(new_parent_id) {
290            new_parent.add_child(id.clone());
291        }
292        
293        Ok(())
294    }
295
296    /// Get a node by ID
297    pub fn get(&self, id: &NodeId) -> Option<&TreeNode<T>> {
298        self.nodes.get(id)
299    }
300
301    /// Get all visible nodes (not deleted)
302    pub fn visible_nodes(&self) -> Vec<&TreeNode<T>> {
303        self.nodes
304            .values()
305            .filter(|n| !n.metadata.deleted)
306            .collect()
307    }
308
309    /// Get all nodes including deleted ones
310    pub fn all_nodes(&self) -> Vec<&TreeNode<T>> {
311        self.nodes.values().collect()
312    }
313
314    /// Get root nodes
315    pub fn roots(&self) -> Vec<&TreeNode<T>> {
316        self.nodes
317            .values()
318            .filter(|n| n.parent.is_none() && !n.metadata.deleted)
319            .collect()
320    }
321
322    /// Get children of a node
323    pub fn children(&self, id: &NodeId) -> Vec<&TreeNode<T>> {
324        if let Some(node) = self.nodes.get(id) {
325            node.children
326                .iter()
327                .filter_map(|child_id| self.nodes.get(child_id))
328                .filter(|n| !n.metadata.deleted)
329                .collect()
330        } else {
331            Vec::new()
332        }
333    }
334
335    /// Get descendants of a node (recursive)
336    pub fn descendants(&self, id: &NodeId) -> Vec<&TreeNode<T>> {
337        let mut descendants = Vec::new();
338        self.collect_descendants(id, &mut descendants);
339        descendants
340    }
341    
342    fn collect_descendants<'a>(&'a self, id: &NodeId, descendants: &mut Vec<&'a TreeNode<T>>) {
343        if let Some(node) = self.nodes.get(id) {
344            if !node.metadata.deleted {
345                for child_id in &node.children {
346                    if let Some(child_node) = self.nodes.get(child_id) {
347                        if !child_node.metadata.deleted {
348                            descendants.push(child_node);
349                            self.collect_descendants(child_id, descendants);
350                        }
351                    }
352                }
353            }
354        }
355    }
356
357    /// Check if the tree contains a node
358    pub fn contains(&self, id: &NodeId) -> bool {
359        self.nodes.contains_key(id)
360    }
361
362    /// Get the number of visible nodes
363    pub fn len(&self) -> usize {
364        self.visible_nodes().len()
365    }
366
367    /// Check if the tree is empty
368    pub fn is_empty(&self) -> bool {
369        self.len() == 0
370    }
371
372    /// Clear all nodes
373    pub fn clear(&mut self) {
374        self.nodes.clear();
375    }
376}
377
378impl<T: Clone + PartialEq + Eq + Send + Sync> CRDT for AddWinsTree<T> {
379    fn replica_id(&self) -> &ReplicaId {
380        &self.replica
381    }
382}
383
384impl<T: Clone + PartialEq + Eq + Send + Sync> Mergeable for AddWinsTree<T> {
385    type Error = TreeError;
386
387    fn merge(&mut self, other: &Self) -> Result<(), Self::Error> {
388        for (id, node) in &other.nodes {
389            match self.nodes.get(id) {
390                Some(existing) => {
391                    // Conflict resolution: later timestamp wins
392                    if node.metadata.modified_at > existing.metadata.modified_at {
393                        self.nodes.insert(id.clone(), node.clone());
394                    }
395                }
396                None => {
397                    // New node, add it
398                    self.nodes.insert(id.clone(), node.clone());
399                }
400            }
401        }
402        Ok(())
403    }
404
405    fn has_conflict(&self, other: &Self) -> bool {
406        for (id, node) in &other.nodes {
407            if let Some(existing) = self.nodes.get(id) {
408                // Check for conflicts: same timestamp but different replica
409                if node.metadata.modified_at == existing.metadata.modified_at
410                    && node.metadata.last_modified_by != existing.metadata.last_modified_by
411                {
412                    return true;
413                }
414            }
415        }
416        false
417    }
418}
419
420/// Remove-Wins Tree CRDT implementation
421/// 
422/// This implementation completely removes deleted nodes.
423/// It's more memory-efficient but nodes cannot be recovered.
424#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
425pub struct RemoveWinsTree<T> {
426    /// Configuration
427    config: TreeConfig,
428    /// Nodes in the tree
429    nodes: HashMap<NodeId, TreeNode<T>>,
430    /// Replica ID for this instance
431    replica: ReplicaId,
432}
433
434impl<T: Clone + PartialEq + Eq + Send + Sync> RemoveWinsTree<T> {
435    /// Create a new Remove-Wins tree
436    pub fn new(replica: ReplicaId) -> Self {
437        Self {
438            config: TreeConfig {
439                strategy: TreeStrategy::RemoveWins,
440                preserve_deleted: false,
441                max_depth: None,
442                max_children: None,
443            },
444            nodes: HashMap::new(),
445            replica,
446        }
447    }
448
449    /// Create with custom configuration
450    pub fn with_config(replica: ReplicaId, config: TreeConfig) -> Self {
451        Self {
452            config,
453            nodes: HashMap::new(),
454            replica,
455        }
456    }
457
458    /// Add a root node to the tree
459    pub fn add_root(&mut self, value: T, timestamp: u64) -> NodeId {
460        let node = TreeNode::new(value, self.replica, timestamp);
461        let id = node.id.clone();
462        self.nodes.insert(id.clone(), node);
463        id
464    }
465
466    /// Add a child node
467    pub fn add_child(&mut self, parent_id: &NodeId, value: T, timestamp: u64) -> Result<NodeId, TreeError> {
468        if !self.nodes.contains_key(parent_id) {
469            return Err(TreeError::new("Parent node not found".to_string()));
470        }
471
472        let node = TreeNode::new_child(value, self.replica, timestamp, parent_id.clone());
473        let id = node.id.clone();
474        
475        // Add the child node
476        self.nodes.insert(id.clone(), node);
477        
478        // Update parent's children list
479        if let Some(parent) = self.nodes.get_mut(parent_id) {
480            parent.add_child(id.clone());
481        }
482        
483        Ok(id)
484    }
485
486    /// Update an existing node
487    pub fn update(&mut self, id: &NodeId, value: T, timestamp: u64) -> Result<(), TreeError> {
488        if let Some(node) = self.nodes.get_mut(id) {
489            node.value = value;
490            node.mark_modified(self.replica, timestamp);
491            Ok(())
492        } else {
493            Err(TreeError::new("Node not found".to_string()))
494        }
495    }
496
497    /// Remove a node completely
498    pub fn remove(&mut self, id: &NodeId) -> Result<(), TreeError> {
499        // Get the parent ID first
500        let parent_id = self.nodes.get(id).and_then(|node| node.parent.clone());
501        
502        // Remove from parent's children list
503        if let Some(parent_id) = parent_id {
504            if let Some(parent) = self.nodes.get_mut(&parent_id) {
505                parent.remove_child(id);
506            }
507        }
508        
509        // Remove the node
510        if self.nodes.remove(id).is_some() {
511            Ok(())
512        } else {
513            Err(TreeError::new("Node not found".to_string()))
514        }
515    }
516
517    /// Move a node to a new parent
518    pub fn move_node(&mut self, id: &NodeId, new_parent_id: &NodeId) -> Result<(), TreeError> {
519        if !self.nodes.contains_key(id) || !self.nodes.contains_key(new_parent_id) {
520            return Err(TreeError::new("Node not found".to_string()));
521        }
522
523        // Get the old parent ID first
524        let old_parent_id = self.nodes.get(id).and_then(|node| node.parent.clone());
525        
526        // Remove from old parent
527        if let Some(old_parent_id) = old_parent_id {
528            if let Some(old_parent) = self.nodes.get_mut(&old_parent_id) {
529                old_parent.remove_child(id);
530            }
531        }
532        
533        // Update the node's parent reference
534        if let Some(node) = self.nodes.get_mut(id) {
535            node.parent = Some(new_parent_id.clone());
536        }
537        
538        // Add to new parent
539        if let Some(new_parent) = self.nodes.get_mut(new_parent_id) {
540            new_parent.add_child(id.clone());
541        }
542        
543        Ok(())
544    }
545
546    /// Get a node by ID
547    pub fn get(&self, id: &NodeId) -> Option<&TreeNode<T>> {
548        self.nodes.get(id)
549    }
550
551    /// Get all nodes
552    pub fn nodes(&self) -> Vec<&TreeNode<T>> {
553        self.nodes.values().collect()
554    }
555
556    /// Get root nodes
557    pub fn roots(&self) -> Vec<&TreeNode<T>> {
558        self.nodes
559            .values()
560            .filter(|n| n.parent.is_none())
561            .collect()
562    }
563
564    /// Get children of a node
565    pub fn children(&self, id: &NodeId) -> Vec<&TreeNode<T>> {
566        if let Some(node) = self.nodes.get(id) {
567            node.children
568                .iter()
569                .filter_map(|child_id| self.nodes.get(child_id))
570                .collect()
571        } else {
572            Vec::new()
573        }
574    }
575
576    /// Get descendants of a node (recursive)
577    pub fn descendants(&self, id: &NodeId) -> Vec<&TreeNode<T>> {
578        let mut descendants = Vec::new();
579        self.collect_descendants(id, &mut descendants);
580        descendants
581    }
582    
583    fn collect_descendants<'a>(&'a self, id: &NodeId, descendants: &mut Vec<&'a TreeNode<T>>) {
584        if let Some(node) = self.nodes.get(id) {
585            for child_id in &node.children {
586                if let Some(child_node) = self.nodes.get(child_id) {
587                    descendants.push(child_node);
588                    self.collect_descendants(child_id, descendants);
589                }
590            }
591        }
592    }
593
594    /// Check if the tree contains a node
595    pub fn contains(&self, id: &NodeId) -> bool {
596        self.nodes.contains_key(id)
597    }
598
599    /// Get the number of nodes
600    pub fn len(&self) -> usize {
601        self.nodes.len()
602    }
603
604    /// Check if the tree is empty
605    pub fn is_empty(&self) -> bool {
606        self.nodes.is_empty()
607    }
608
609    /// Clear all nodes
610    pub fn clear(&mut self) {
611        self.nodes.clear();
612    }
613}
614
615impl<T: Clone + PartialEq + Eq + Send + Sync> CRDT for RemoveWinsTree<T> {
616    fn replica_id(&self) -> &ReplicaId {
617        &self.replica
618    }
619}
620
621impl<T: Clone + PartialEq + Eq + Send + Sync> Mergeable for RemoveWinsTree<T> {
622    type Error = TreeError;
623
624    fn merge(&mut self, other: &Self) -> Result<(), Self::Error> {
625        for (id, node) in &other.nodes {
626            match self.nodes.get(id) {
627                Some(existing) => {
628                    // Conflict resolution: later timestamp wins
629                    if node.metadata.modified_at > existing.metadata.modified_at {
630                        self.nodes.insert(id.clone(), node.clone());
631                    }
632                }
633                None => {
634                    // New node, add it
635                    self.nodes.insert(id.clone(), node.clone());
636                }
637            }
638        }
639        Ok(())
640    }
641
642    fn has_conflict(&self, other: &Self) -> bool {
643        for (id, node) in &other.nodes {
644            if let Some(existing) = self.nodes.get(id) {
645                // Check for conflicts: same timestamp but different replica
646                if node.metadata.modified_at == existing.metadata.modified_at
647                    && node.metadata.last_modified_by != existing.metadata.last_modified_by
648                {
649                    return true;
650                }
651            }
652        }
653        false
654    }
655}
656
657#[cfg(test)]
658mod tests {
659    use super::*;
660    use super::super::ReplicaId;
661    use uuid::Uuid;
662
663    fn create_replica(id: u64) -> ReplicaId {
664        ReplicaId::from(Uuid::from_u64_pair(0, id))
665    }
666
667    #[test]
668    fn test_node_id_creation() {
669        let replica = create_replica(1);
670        let node_id = NodeId::new(replica);
671        
672        assert_eq!(node_id.replica, replica);
673        assert_ne!(node_id.id, Uuid::nil());
674    }
675
676    #[test]
677    fn test_tree_node_creation() {
678        let replica = create_replica(1);
679        let timestamp = 1234567890;
680        let node = TreeNode::new("test_value", replica, timestamp);
681        
682        assert_eq!(node.value, "test_value");
683        assert_eq!(node.metadata.created_at, timestamp);
684        assert_eq!(node.metadata.modified_at, timestamp);
685        assert_eq!(node.metadata.deleted, false);
686        assert_eq!(node.metadata.last_modified_by, replica);
687        assert!(node.parent.is_none());
688        assert!(node.children.is_empty());
689    }
690
691    #[test]
692    fn test_add_wins_tree_basic_operations() {
693        let replica = create_replica(1);
694        let mut tree = AddWinsTree::new(replica);
695        
696        // Add root
697        let root_id = tree.add_root("root", 1000);
698        assert_eq!(tree.len(), 1);
699        assert!(tree.contains(&root_id));
700        
701        // Add child
702        let child_id = tree.add_child(&root_id, "child", 2000).unwrap();
703        assert_eq!(tree.len(), 2);
704        assert!(tree.contains(&child_id));
705        
706        // Check hierarchy
707        let root = tree.get(&root_id).unwrap();
708        assert!(root.children.contains(&child_id));
709        
710        let child = tree.get(&child_id).unwrap();
711        assert_eq!(child.parent, Some(root_id));
712    }
713
714    #[test]
715    fn test_remove_wins_tree_basic_operations() {
716        let replica = create_replica(1);
717        let mut tree = RemoveWinsTree::new(replica);
718        
719        // Add root and child
720        let root_id = tree.add_root("root", 1000);
721        let child_id = tree.add_child(&root_id, "child", 2000).unwrap();
722        
723        assert_eq!(tree.len(), 2);
724        
725        // Remove child completely
726        tree.remove(&child_id).unwrap();
727        assert_eq!(tree.len(), 1);
728        assert!(!tree.contains(&child_id));
729        
730        // Root should have no children
731        let root = tree.get(&root_id).unwrap();
732        assert!(root.children.is_empty());
733    }
734
735    #[test]
736    fn test_tree_move_operation() {
737        let replica = create_replica(1);
738        let mut tree = AddWinsTree::new(replica);
739        
740        // Create tree: root -> child1 -> child2
741        let root_id = tree.add_root("root", 1000);
742        let child1_id = tree.add_child(&root_id, "child1", 2000).unwrap();
743        let child2_id = tree.add_child(&child1_id, "child2", 3000).unwrap();
744        
745        // Move child2 to root
746        tree.move_node(&child2_id, &root_id).unwrap();
747        
748        let child2 = tree.get(&child2_id).unwrap();
749        assert_eq!(child2.parent, Some(root_id.clone()));
750        
751        let root = tree.get(&root_id).unwrap();
752        assert!(root.children.contains(&child2_id));
753        
754        let child1 = tree.get(&child1_id).unwrap();
755        assert!(!child1.children.contains(&child2_id));
756    }
757
758    #[test]
759    fn test_tree_traversal() {
760        let replica = create_replica(1);
761        let mut tree = AddWinsTree::new(replica);
762        
763        // Create tree: root -> child1 -> child2
764        let root_id = tree.add_root("root", 1000);
765        let child1_id = tree.add_child(&root_id, "child1", 2000).unwrap();
766        let child2_id = tree.add_child(&child1_id, "child2", 3000).unwrap();
767        
768        // Test descendants
769        let descendants = tree.descendants(&root_id);
770        assert_eq!(descendants.len(), 2);
771        
772        // Test children
773        let root_children = tree.children(&root_id);
774        assert_eq!(root_children.len(), 1);
775        assert_eq!(root_children[0].id, child1_id);
776    }
777
778    #[test]
779    fn test_tree_merge() {
780        let replica1 = create_replica(1);
781        let replica2 = create_replica(2);
782        
783        let mut tree1 = AddWinsTree::new(replica1);
784        let mut tree2 = AddWinsTree::new(replica2);
785        
786        // Add nodes to both trees
787        let root1_id = tree1.add_root("root1", 1000);
788        let root2_id = tree2.add_root("root2", 2000);
789        
790        // Merge tree2 into tree1
791        tree1.merge(&tree2).unwrap();
792        
793        // Both roots should be present
794        assert_eq!(tree1.len(), 2);
795        assert!(tree1.contains(&root1_id));
796        assert!(tree1.contains(&root2_id));
797    }
798
799    #[test]
800    fn test_tree_configuration() {
801        let replica = create_replica(1);
802        let config = TreeConfig {
803            strategy: TreeStrategy::RemoveWins,
804            preserve_deleted: false,
805            max_depth: Some(5),
806            max_children: Some(10),
807        };
808        
809        let tree: AddWinsTree<String> = AddWinsTree::with_config(replica, config);
810        assert_eq!(tree.config.strategy, TreeStrategy::RemoveWins);
811        assert_eq!(tree.config.max_depth, Some(5));
812        assert_eq!(tree.config.max_children, Some(10));
813    }
814}
leptos_sync_core/crdt/tree.rs

leptos_sync_core/crdt/
tree.rs
