leptos_sync_core/crdt/
advanced.rs

1//! Advanced CRDT Types
2//!
3//! This module provides advanced CRDT implementations including:
4//! - RGA (Replicated Growable Array) for collaborative text editing
5//! - LSEQ (Logoot Sequence) for ordered sequences
6//! - Yjs-style trees for hierarchical data
7//! - DAG (Directed Acyclic Graph) for complex relationships
8
9use crate::crdt::{CRDT, Mergeable, ReplicaId};
10use serde::{Deserialize, Serialize};
11use std::collections::{HashMap, BTreeMap, HashSet};
12use std::error::Error;
13use std::fmt;
14use uuid::Uuid;
15
16/// Error types for advanced CRDT operations
17#[derive(Debug, Clone, PartialEq)]
18pub enum AdvancedCrdtError {
19    /// Invalid position in sequence
20    InvalidPosition(String),
21    /// Element not found
22    ElementNotFound(String),
23    /// Invalid parent-child relationship
24    InvalidRelationship(String),
25    /// Cycle detected in DAG
26    CycleDetected(String),
27    /// Invalid operation for CRDT type
28    InvalidOperation(String),
29    /// Merge operation failed
30    MergeError(String),
31}
32
33impl fmt::Display for AdvancedCrdtError {
34    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
35        match self {
36            AdvancedCrdtError::InvalidPosition(msg) => write!(f, "Invalid position: {}", msg),
37            AdvancedCrdtError::ElementNotFound(msg) => write!(f, "Element not found: {}", msg),
38            AdvancedCrdtError::InvalidRelationship(msg) => write!(f, "Invalid relationship: {}", msg),
39            AdvancedCrdtError::CycleDetected(msg) => write!(f, "Cycle detected: {}", msg),
40            AdvancedCrdtError::InvalidOperation(msg) => write!(f, "Invalid operation: {}", msg),
41            AdvancedCrdtError::MergeError(msg) => write!(f, "Merge error: {}", msg),
42        }
43    }
44}
45
46impl Error for AdvancedCrdtError {}
47
48/// Position identifier for RGA and LSEQ
49#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
50pub struct PositionId {
51    /// Replica ID that created this position
52    pub replica_id: ReplicaId,
53    /// Logical timestamp
54    pub timestamp: u64,
55    /// Additional disambiguation value
56    pub disambiguation: u64,
57}
58
59impl PositionId {
60    /// Create a new position ID
61    pub fn new(replica_id: ReplicaId, timestamp: u64, disambiguation: u64) -> Self {
62        Self {
63            replica_id,
64            timestamp,
65            disambiguation,
66        }
67    }
68}
69
70/// RGA (Replicated Growable Array) element
71#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
72pub struct RgaElement<T> {
73    /// Unique position identifier
74    pub position: PositionId,
75    /// Element value
76    pub value: T,
77    /// Whether the element is visible (not deleted)
78    pub visible: bool,
79    /// Reference to previous element
80    pub prev: Option<PositionId>,
81}
82
83impl<T> RgaElement<T> {
84    /// Create a new RGA element
85    pub fn new(position: PositionId, value: T, prev: Option<PositionId>) -> Self {
86        Self {
87            position,
88            value,
89            visible: true,
90            prev,
91        }
92    }
93}
94
95/// RGA (Replicated Growable Array) for collaborative text editing
96#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
97pub struct Rga<T> {
98    /// Replica ID
99    replica_id: ReplicaId,
100    /// Elements indexed by position
101    elements: HashMap<PositionId, RgaElement<T>>,
102    /// Logical timestamp counter
103    timestamp_counter: u64,
104    /// Disambiguation counter
105    disambiguation_counter: u64,
106}
107
108impl<T: Clone + PartialEq> Rga<T> {
109    /// Create a new RGA
110    pub fn new(replica_id: ReplicaId) -> Self {
111        Self {
112            replica_id,
113            elements: HashMap::new(),
114            timestamp_counter: 0,
115            disambiguation_counter: 0,
116        }
117    }
118    
119    /// Insert an element after the given position
120    pub fn insert_after(&mut self, value: T, after: Option<PositionId>) -> Result<PositionId, AdvancedCrdtError> {
121        self.timestamp_counter += 1;
122        self.disambiguation_counter += 1;
123        
124        let position = PositionId::new(
125            self.replica_id.clone(),
126            self.timestamp_counter,
127            self.disambiguation_counter,
128        );
129        
130        let element = RgaElement::new(position.clone(), value, after);
131        self.elements.insert(position.clone(), element);
132        
133        Ok(position)
134    }
135    
136    /// Delete an element at the given position
137    pub fn delete(&mut self, position: &PositionId) -> Result<(), AdvancedCrdtError> {
138        if let Some(element) = self.elements.get_mut(position) {
139            element.visible = false;
140            Ok(())
141        } else {
142            Err(AdvancedCrdtError::ElementNotFound(format!("Position {:?}", position)))
143        }
144    }
145    
146    /// Get the visible elements in order
147    pub fn to_vec(&self) -> Vec<T> {
148        let mut result = Vec::new();
149        
150        // For RGA, we need to handle multiple root elements (elements with prev: None)
151        // We'll collect all visible elements and sort them by position
152        let mut elements: Vec<_> = self.elements.values()
153            .filter(|e| e.visible)
154            .collect();
155        
156        // Sort by position (replica_id, timestamp, disambiguation)
157        elements.sort_by(|a, b| a.position.cmp(&b.position));
158        
159        // Add values to result
160        for element in elements {
161            result.push(element.value.clone());
162        }
163        
164        result
165    }
166    
167    /// Find the first element in the sequence
168    fn find_first_element(&self) -> Option<PositionId> {
169        // Find element with no previous element
170        self.elements.values()
171            .find(|e| e.prev.is_none())
172            .map(|e| e.position.clone())
173    }
174    
175    /// Find the next element after the given position
176    fn find_next_element(&self, position: &PositionId) -> Option<PositionId> {
177        self.elements.values()
178            .find(|e| e.prev.as_ref() == Some(position))
179            .map(|e| e.position.clone())
180    }
181    
182    /// Get element count
183    pub fn len(&self) -> usize {
184        self.elements.len()
185    }
186    
187    /// Check if RGA is empty
188    pub fn is_empty(&self) -> bool {
189        self.elements.is_empty()
190    }
191}
192
193impl<T: Clone + PartialEq> CRDT for Rga<T> {
194    fn replica_id(&self) -> &ReplicaId {
195        &self.replica_id
196    }
197}
198
199impl<T: Clone + PartialEq + Send + Sync> Mergeable for Rga<T> {
200    type Error = AdvancedCrdtError;
201    
202    fn merge(&mut self, other: &Self) -> Result<(), Self::Error> {
203        // Merge all elements from other RGA
204        for (position, other_element) in &other.elements {
205            if let Some(self_element) = self.elements.get_mut(position) {
206                // Element exists in both, keep the one with higher timestamp
207                if other_element.position.timestamp > self_element.position.timestamp {
208                    *self_element = other_element.clone();
209                }
210            } else {
211                // Element only exists in other, add it
212                self.elements.insert(position.clone(), other_element.clone());
213            }
214        }
215        
216        Ok(())
217    }
218    
219    fn has_conflict(&self, other: &Self) -> bool {
220        // Check for conflicting elements (same position, different values)
221        for (position, self_element) in &self.elements {
222            if let Some(other_element) = other.elements.get(position) {
223                if self_element.value != other_element.value {
224                    return true;
225                }
226            }
227        }
228        false
229    }
230}
231
232/// LSEQ (Logoot Sequence) element
233#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
234pub struct LseqElement<T> {
235    /// Unique position identifier
236    pub position: PositionId,
237    /// Element value
238    pub value: T,
239    /// Whether the element is visible (not deleted)
240    pub visible: bool,
241}
242
243impl<T> LseqElement<T> {
244    /// Create a new LSEQ element
245    pub fn new(position: PositionId, value: T) -> Self {
246        Self {
247            position,
248            value,
249            visible: true,
250        }
251    }
252}
253
254/// LSEQ (Logoot Sequence) for ordered sequences
255#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
256pub struct Lseq<T> {
257    /// Replica ID
258    replica_id: ReplicaId,
259    /// Elements indexed by position
260    elements: BTreeMap<PositionId, LseqElement<T>>,
261    /// Logical timestamp counter
262    timestamp_counter: u64,
263    /// Disambiguation counter
264    disambiguation_counter: u64,
265}
266
267impl<T: Clone + PartialEq> Lseq<T> {
268    /// Create a new LSEQ
269    pub fn new(replica_id: ReplicaId) -> Self {
270        Self {
271            replica_id,
272            elements: BTreeMap::new(),
273            timestamp_counter: 0,
274            disambiguation_counter: 0,
275        }
276    }
277    
278    /// Insert an element at the given position
279    pub fn insert(&mut self, value: T, _position: Option<PositionId>) -> Result<PositionId, AdvancedCrdtError> {
280        self.timestamp_counter += 1;
281        self.disambiguation_counter += 1;
282        
283        let new_position = PositionId::new(
284            self.replica_id.clone(),
285            self.timestamp_counter,
286            self.disambiguation_counter,
287        );
288        
289        let element = LseqElement::new(new_position.clone(), value);
290        self.elements.insert(new_position.clone(), element);
291        
292        Ok(new_position)
293    }
294    
295    /// Delete an element at the given position
296    pub fn delete(&mut self, position: &PositionId) -> Result<(), AdvancedCrdtError> {
297        if let Some(element) = self.elements.get_mut(position) {
298            element.visible = false;
299            Ok(())
300        } else {
301            Err(AdvancedCrdtError::ElementNotFound(format!("Position {:?}", position)))
302        }
303    }
304    
305    /// Get the visible elements in order
306    pub fn to_vec(&self) -> Vec<T> {
307        self.elements.values()
308            .filter(|e| e.visible)
309            .map(|e| e.value.clone())
310            .collect()
311    }
312    
313    /// Get element count
314    pub fn len(&self) -> usize {
315        self.elements.len()
316    }
317    
318    /// Check if LSEQ is empty
319    pub fn is_empty(&self) -> bool {
320        self.elements.is_empty()
321    }
322    
323    /// Get all elements (for debugging/inspection)
324    pub fn get_elements(&self) -> &BTreeMap<PositionId, LseqElement<T>> {
325        &self.elements
326    }
327}
328
329impl<T: Clone + PartialEq> CRDT for Lseq<T> {
330    fn replica_id(&self) -> &ReplicaId {
331        &self.replica_id
332    }
333}
334
335impl<T: Clone + PartialEq + Send + Sync> Mergeable for Lseq<T> {
336    type Error = AdvancedCrdtError;
337    
338    fn merge(&mut self, other: &Self) -> Result<(), Self::Error> {
339        // Merge all elements from other LSEQ
340        for (position, other_element) in &other.elements {
341            if let Some(self_element) = self.elements.get_mut(position) {
342                // Element exists in both, keep the one with higher timestamp
343                if other_element.position.timestamp > self_element.position.timestamp {
344                    *self_element = other_element.clone();
345                }
346            } else {
347                // Element only exists in other, add it
348                self.elements.insert(position.clone(), other_element.clone());
349            }
350        }
351        
352        Ok(())
353    }
354    
355    fn has_conflict(&self, other: &Self) -> bool {
356        // Check for conflicting elements (same position, different values)
357        for (position, self_element) in &self.elements {
358            if let Some(other_element) = other.elements.get(position) {
359                if self_element.value != other_element.value {
360                    return true;
361                }
362            }
363        }
364        false
365    }
366}
367
368/// Yjs-style tree node
369#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
370pub struct YjsNode<T> {
371    /// Unique node identifier
372    pub id: PositionId,
373    /// Node value
374    pub value: T,
375    /// Parent node ID
376    pub parent: Option<PositionId>,
377    /// Child node IDs
378    pub children: Vec<PositionId>,
379    /// Whether the node is visible (not deleted)
380    pub visible: bool,
381}
382
383impl<T> YjsNode<T> {
384    /// Create a new Yjs node
385    pub fn new(id: PositionId, value: T, parent: Option<PositionId>) -> Self {
386        Self {
387            id,
388            value,
389            parent,
390            children: Vec::new(),
391            visible: true,
392        }
393    }
394}
395
396/// Yjs-style tree for hierarchical data
397#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
398pub struct YjsTree<T> {
399    /// Replica ID
400    replica_id: ReplicaId,
401    /// Nodes indexed by ID
402    nodes: HashMap<PositionId, YjsNode<T>>,
403    /// Root node ID
404    root: Option<PositionId>,
405    /// Logical timestamp counter
406    timestamp_counter: u64,
407    /// Disambiguation counter
408    disambiguation_counter: u64,
409}
410
411impl<T: Clone + PartialEq> YjsTree<T> {
412    /// Create a new Yjs tree
413    pub fn new(replica_id: ReplicaId) -> Self {
414        Self {
415            replica_id,
416            nodes: HashMap::new(),
417            root: None,
418            timestamp_counter: 0,
419            disambiguation_counter: 0,
420        }
421    }
422    
423    /// Add a root node
424    pub fn add_root(&mut self, value: T) -> Result<PositionId, AdvancedCrdtError> {
425        self.timestamp_counter += 1;
426        self.disambiguation_counter += 1;
427        
428        let id = PositionId::new(
429            self.replica_id.clone(),
430            self.timestamp_counter,
431            self.disambiguation_counter,
432        );
433        
434        let node = YjsNode::new(id.clone(), value, None);
435        self.nodes.insert(id.clone(), node);
436        self.root = Some(id.clone());
437        
438        Ok(id)
439    }
440    
441    /// Add a child node
442    pub fn add_child(&mut self, parent_id: &PositionId, value: T) -> Result<PositionId, AdvancedCrdtError> {
443        if !self.nodes.contains_key(parent_id) {
444            return Err(AdvancedCrdtError::ElementNotFound(format!("Parent {:?}", parent_id)));
445        }
446        
447        self.timestamp_counter += 1;
448        self.disambiguation_counter += 1;
449        
450        let id = PositionId::new(
451            self.replica_id.clone(),
452            self.timestamp_counter,
453            self.disambiguation_counter,
454        );
455        
456        let node = YjsNode::new(id.clone(), value, Some(parent_id.clone()));
457        self.nodes.insert(id.clone(), node);
458        
459        // Add to parent's children
460        if let Some(parent) = self.nodes.get_mut(parent_id) {
461            parent.children.push(id.clone());
462        }
463        
464        Ok(id)
465    }
466    
467    /// Delete a node
468    pub fn delete(&mut self, node_id: &PositionId) -> Result<(), AdvancedCrdtError> {
469        if let Some(node) = self.nodes.get_mut(node_id) {
470            node.visible = false;
471            Ok(())
472        } else {
473            Err(AdvancedCrdtError::ElementNotFound(format!("Node {:?}", node_id)))
474        }
475    }
476    
477    /// Get the tree structure as a nested structure
478    pub fn to_tree(&self) -> Option<YjsTreeNode<T>> {
479        if let Some(root_id) = &self.root {
480            self.build_tree_node(root_id)
481        } else {
482            None
483        }
484    }
485    
486    /// Build a tree node recursively
487    fn build_tree_node(&self, node_id: &PositionId) -> Option<YjsTreeNode<T>> {
488        if let Some(node) = self.nodes.get(node_id) {
489            if !node.visible {
490                return None;
491            }
492            
493            let children: Vec<YjsTreeNode<T>> = node.children
494                .iter()
495                .filter_map(|child_id| self.build_tree_node(child_id))
496                .collect();
497            
498            Some(YjsTreeNode {
499                id: node.id.clone(),
500                value: node.value.clone(),
501                children,
502            })
503        } else {
504            None
505        }
506    }
507    
508    /// Get node count
509    pub fn len(&self) -> usize {
510        self.nodes.len()
511    }
512    
513    /// Check if tree is empty
514    pub fn is_empty(&self) -> bool {
515        self.nodes.is_empty()
516    }
517}
518
519/// Tree node for display purposes
520#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
521pub struct YjsTreeNode<T> {
522    /// Node ID
523    pub id: PositionId,
524    /// Node value
525    pub value: T,
526    /// Child nodes
527    pub children: Vec<YjsTreeNode<T>>,
528}
529
530impl<T: Clone + PartialEq> CRDT for YjsTree<T> {
531    fn replica_id(&self) -> &ReplicaId {
532        &self.replica_id
533    }
534}
535
536impl<T: Clone + PartialEq + Send + Sync> Mergeable for YjsTree<T> {
537    type Error = AdvancedCrdtError;
538    
539    fn merge(&mut self, other: &Self) -> Result<(), Self::Error> {
540        // Merge all nodes from other tree
541        for (node_id, other_node) in &other.nodes {
542            if let Some(self_node) = self.nodes.get_mut(node_id) {
543                // Node exists in both, keep the one with higher timestamp
544                if other_node.id.timestamp > self_node.id.timestamp {
545                    *self_node = other_node.clone();
546                }
547            } else {
548                // Node only exists in other, add it
549                self.nodes.insert(node_id.clone(), other_node.clone());
550            }
551        }
552        
553        // Update root if other has a root and we don't, or if other's root is newer
554        if let Some(other_root) = &other.root {
555            if self.root.is_none() {
556                self.root = Some(other_root.clone());
557            } else if let Some(self_root) = &self.root {
558                if let (Some(other_root_node), Some(self_root_node)) = (
559                    other.nodes.get(other_root),
560                    self.nodes.get(self_root)
561                ) {
562                    if other_root_node.id.timestamp > self_root_node.id.timestamp {
563                        self.root = Some(other_root.clone());
564                    }
565                }
566            }
567        }
568        
569        Ok(())
570    }
571    
572    fn has_conflict(&self, other: &Self) -> bool {
573        // Check for conflicting nodes (same ID, different values)
574        for (node_id, self_node) in &self.nodes {
575            if let Some(other_node) = other.nodes.get(node_id) {
576                if self_node.value != other_node.value {
577                    return true;
578                }
579            }
580        }
581        false
582    }
583}
584
585/// DAG (Directed Acyclic Graph) node
586#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
587pub struct DagNode<T> {
588    /// Unique node identifier
589    pub id: PositionId,
590    /// Node value
591    pub value: T,
592    /// Incoming edges (dependencies)
593    pub incoming: HashSet<PositionId>,
594    /// Outgoing edges (dependents)
595    pub outgoing: HashSet<PositionId>,
596    /// Whether the node is visible (not deleted)
597    pub visible: bool,
598}
599
600impl<T> DagNode<T> {
601    /// Create a new DAG node
602    pub fn new(id: PositionId, value: T) -> Self {
603        Self {
604            id,
605            value,
606            incoming: HashSet::new(),
607            outgoing: HashSet::new(),
608            visible: true,
609        }
610    }
611}
612
613/// DAG (Directed Acyclic Graph) for complex relationships
614#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
615pub struct Dag<T> {
616    /// Replica ID
617    replica_id: ReplicaId,
618    /// Nodes indexed by ID
619    nodes: HashMap<PositionId, DagNode<T>>,
620    /// Logical timestamp counter
621    timestamp_counter: u64,
622    /// Disambiguation counter
623    disambiguation_counter: u64,
624}
625
626impl<T: Clone + PartialEq> Dag<T> {
627    /// Create a new DAG
628    pub fn new(replica_id: ReplicaId) -> Self {
629        Self {
630            replica_id,
631            nodes: HashMap::new(),
632            timestamp_counter: 0,
633            disambiguation_counter: 0,
634        }
635    }
636    
637    /// Add a node
638    pub fn add_node(&mut self, value: T) -> Result<PositionId, AdvancedCrdtError> {
639        self.timestamp_counter += 1;
640        self.disambiguation_counter += 1;
641        
642        let id = PositionId::new(
643            self.replica_id.clone(),
644            self.timestamp_counter,
645            self.disambiguation_counter,
646        );
647        
648        let node = DagNode::new(id.clone(), value);
649        self.nodes.insert(id.clone(), node);
650        
651        Ok(id)
652    }
653    
654    /// Add an edge from source to target
655    pub fn add_edge(&mut self, from: &PositionId, to: &PositionId) -> Result<(), AdvancedCrdtError> {
656        if !self.nodes.contains_key(from) || !self.nodes.contains_key(to) {
657            return Err(AdvancedCrdtError::ElementNotFound("Node not found".to_string()));
658        }
659        
660        // Check for cycle
661        if self.would_create_cycle(from, to) {
662            return Err(AdvancedCrdtError::CycleDetected("Adding edge would create cycle".to_string()));
663        }
664        
665        // Add edge
666        if let Some(from_node) = self.nodes.get_mut(from) {
667            from_node.outgoing.insert(to.clone());
668        }
669        if let Some(to_node) = self.nodes.get_mut(to) {
670            to_node.incoming.insert(from.clone());
671        }
672        
673        Ok(())
674    }
675    
676    /// Remove an edge
677    pub fn remove_edge(&mut self, from: &PositionId, to: &PositionId) -> Result<(), AdvancedCrdtError> {
678        if let Some(from_node) = self.nodes.get_mut(from) {
679            from_node.outgoing.remove(to);
680        }
681        if let Some(to_node) = self.nodes.get_mut(to) {
682            to_node.incoming.remove(from);
683        }
684        
685        Ok(())
686    }
687    
688    /// Delete a node
689    pub fn delete_node(&mut self, node_id: &PositionId) -> Result<(), AdvancedCrdtError> {
690        if let Some(node) = self.nodes.get(node_id) {
691            let incoming_edges = node.incoming.clone();
692            let outgoing_edges = node.outgoing.clone();
693            
694            // Mark node as invisible
695            if let Some(node) = self.nodes.get_mut(node_id) {
696                node.visible = false;
697            }
698            
699            // Remove all edges involving this node
700            for incoming in &incoming_edges {
701                if let Some(incoming_node) = self.nodes.get_mut(incoming) {
702                    incoming_node.outgoing.remove(node_id);
703                }
704            }
705            for outgoing in &outgoing_edges {
706                if let Some(outgoing_node) = self.nodes.get_mut(outgoing) {
707                    outgoing_node.incoming.remove(node_id);
708                }
709            }
710            
711            Ok(())
712        } else {
713            Err(AdvancedCrdtError::ElementNotFound(format!("Node {:?}", node_id)))
714        }
715    }
716    
717    /// Check if adding an edge would create a cycle
718    fn would_create_cycle(&self, from: &PositionId, to: &PositionId) -> bool {
719        if from == to {
720            return true;
721        }
722        
723        // Use DFS to check for path from 'to' to 'from'
724        let mut visited = HashSet::new();
725        self.dfs_cycle_check(to, from, &mut visited)
726    }
727    
728    /// DFS helper for cycle detection
729    fn dfs_cycle_check(&self, current: &PositionId, target: &PositionId, visited: &mut HashSet<PositionId>) -> bool {
730        if current == target {
731            return true;
732        }
733        
734        if visited.contains(current) {
735            return false;
736        }
737        
738        visited.insert(current.clone());
739        
740        if let Some(node) = self.nodes.get(current) {
741            for next in &node.outgoing {
742                if self.dfs_cycle_check(next, target, visited) {
743                    return true;
744                }
745            }
746        }
747        
748        false
749    }
750    
751    /// Get topological sort of the DAG
752    pub fn topological_sort(&self) -> Vec<PositionId> {
753        let mut result = Vec::new();
754        let mut visited = HashSet::new();
755        
756        for node_id in self.nodes.keys() {
757            if !visited.contains(node_id) {
758                self.dfs_topological(node_id, &mut visited, &mut result);
759            }
760        }
761        
762        result.reverse();
763        result
764    }
765    
766    /// DFS helper for topological sort
767    fn dfs_topological(&self, node_id: &PositionId, visited: &mut HashSet<PositionId>, result: &mut Vec<PositionId>) {
768        if visited.contains(node_id) {
769            return;
770        }
771        
772        visited.insert(node_id.clone());
773        
774        if let Some(node) = self.nodes.get(node_id) {
775            for next in &node.outgoing {
776                self.dfs_topological(next, visited, result);
777            }
778        }
779        
780        result.push(node_id.clone());
781    }
782    
783    /// Get node count
784    pub fn len(&self) -> usize {
785        self.nodes.len()
786    }
787    
788    /// Check if DAG is empty
789    pub fn is_empty(&self) -> bool {
790        self.nodes.is_empty()
791    }
792    
793    /// Get all nodes (for debugging/inspection)
794    pub fn get_nodes(&self) -> &HashMap<PositionId, DagNode<T>> {
795        &self.nodes
796    }
797}
798
799impl<T: Clone + PartialEq> CRDT for Dag<T> {
800    fn replica_id(&self) -> &ReplicaId {
801        &self.replica_id
802    }
803}
804
805impl<T: Clone + PartialEq + Send + Sync> Mergeable for Dag<T> {
806    type Error = AdvancedCrdtError;
807    
808    fn merge(&mut self, other: &Self) -> Result<(), Self::Error> {
809        // Merge all nodes from other DAG
810        for (node_id, other_node) in &other.nodes {
811            if let Some(self_node) = self.nodes.get_mut(node_id) {
812                // Node exists in both, keep the one with higher timestamp
813                if other_node.id.timestamp > self_node.id.timestamp {
814                    *self_node = other_node.clone();
815                }
816            } else {
817                // Node only exists in other, add it
818                self.nodes.insert(node_id.clone(), other_node.clone());
819            }
820        }
821        
822        Ok(())
823    }
824    
825    fn has_conflict(&self, other: &Self) -> bool {
826        // Check for conflicting nodes (same ID, different values)
827        for (node_id, self_node) in &self.nodes {
828            if let Some(other_node) = other.nodes.get(node_id) {
829                if self_node.value != other_node.value {
830                    return true;
831                }
832            }
833        }
834        false
835    }
836}
837
838#[cfg(test)]
839mod tests {
840    use super::*;
841    use crate::crdt::ReplicaId;
842    use uuid::Uuid;
843    
844    fn create_replica(id: u64) -> ReplicaId {
845        ReplicaId::from(Uuid::from_u64_pair(0, id))
846    }
847    
848    #[test]
849    fn test_rga_creation() {
850        let replica_id = create_replica(1);
851        let rga = Rga::<String>::new(replica_id.clone());
852        
853        assert_eq!(rga.replica_id(), &replica_id);
854        assert!(rga.is_empty());
855        assert_eq!(rga.len(), 0);
856    }
857    
858    #[test]
859    fn test_rga_insert_and_delete() {
860        let replica_id = create_replica(1);
861        let mut rga = Rga::<String>::new(replica_id);
862        
863        // Insert elements
864        let pos1 = rga.insert_after("hello".to_string(), None).unwrap();
865        let pos2 = rga.insert_after("world".to_string(), Some(pos1.clone())).unwrap();
866        let pos3 = rga.insert_after("!".to_string(), Some(pos2.clone())).unwrap();
867        
868        assert_eq!(rga.len(), 3);
869        assert_eq!(rga.to_vec(), vec!["hello", "world", "!"]);
870        
871        // Delete middle element
872        rga.delete(&pos2).unwrap();
873        assert_eq!(rga.to_vec(), vec!["hello", "!"]);
874        
875        // Delete first element
876        rga.delete(&pos1).unwrap();
877        assert_eq!(rga.to_vec(), vec!["!"]);
878        
879        // Delete last element
880        rga.delete(&pos3).unwrap();
881        assert_eq!(rga.to_vec(), Vec::<String>::new());
882    }
883    
884    #[test]
885    fn test_rga_merge() {
886        let replica_id1 = create_replica(1);
887        let replica_id2 = create_replica(2);
888        
889        let mut rga1 = Rga::<String>::new(replica_id1);
890        let mut rga2 = Rga::<String>::new(replica_id2);
891        
892        // Insert different elements
893        let _pos1 = rga1.insert_after("hello".to_string(), None).unwrap();
894        let _pos2 = rga2.insert_after("world".to_string(), None).unwrap();
895        
896        // Merge
897        rga1.merge(&rga2).unwrap();
898        
899        // Should contain both elements (RGA merge adds all elements)
900        let elements = rga1.to_vec();
901        assert!(elements.contains(&"hello".to_string()));
902        assert!(elements.contains(&"world".to_string()));
903    }
904    
905    #[test]
906    fn test_lseq_creation() {
907        let replica_id = create_replica(1);
908        let lseq = Lseq::<String>::new(replica_id.clone());
909        
910        assert_eq!(lseq.replica_id(), &replica_id);
911        assert!(lseq.is_empty());
912        assert_eq!(lseq.len(), 0);
913    }
914    
915    #[test]
916    fn test_lseq_insert_and_delete() {
917        let replica_id = create_replica(1);
918        let mut lseq = Lseq::<String>::new(replica_id);
919        
920        // Insert elements
921        let pos1 = lseq.insert("hello".to_string(), None).unwrap();
922        let pos2 = lseq.insert("world".to_string(), None).unwrap();
923        let pos3 = lseq.insert("!".to_string(), None).unwrap();
924        
925        assert_eq!(lseq.len(), 3);
926        let elements = lseq.to_vec();
927        assert!(elements.contains(&"hello".to_string()));
928        assert!(elements.contains(&"world".to_string()));
929        assert!(elements.contains(&"!".to_string()));
930        
931        // Delete element
932        lseq.delete(&pos2).unwrap();
933        let elements = lseq.to_vec();
934        assert!(elements.contains(&"hello".to_string()));
935        assert!(!elements.contains(&"world".to_string()));
936        assert!(elements.contains(&"!".to_string()));
937    }
938    
939    #[test]
940    fn test_lseq_merge() {
941        let replica_id1 = create_replica(1);
942        let replica_id2 = create_replica(2);
943        
944        let mut lseq1 = Lseq::<String>::new(replica_id1);
945        let mut lseq2 = Lseq::<String>::new(replica_id2);
946        
947        // Insert different elements
948        lseq1.insert("hello".to_string(), None).unwrap();
949        lseq2.insert("world".to_string(), None).unwrap();
950        
951        // Merge
952        lseq1.merge(&lseq2).unwrap();
953        
954        // Should contain both elements
955        let elements = lseq1.to_vec();
956        assert!(elements.contains(&"hello".to_string()));
957        assert!(elements.contains(&"world".to_string()));
958    }
959    
960    #[test]
961    fn test_yjs_tree_creation() {
962        let replica_id = create_replica(1);
963        let tree = YjsTree::<String>::new(replica_id.clone());
964        
965        assert_eq!(tree.replica_id(), &replica_id);
966        assert!(tree.is_empty());
967        assert_eq!(tree.len(), 0);
968    }
969    
970    #[test]
971    fn test_yjs_tree_operations() {
972        let replica_id = create_replica(1);
973        let mut tree = YjsTree::<String>::new(replica_id);
974        
975        // Add root
976        let root_id = tree.add_root("root".to_string()).unwrap();
977        assert_eq!(tree.len(), 1);
978        
979        // Add children
980        let child1_id = tree.add_child(&root_id, "child1".to_string()).unwrap();
981        let child2_id = tree.add_child(&root_id, "child2".to_string()).unwrap();
982        assert_eq!(tree.len(), 3);
983        
984        // Add grandchild
985        let grandchild_id = tree.add_child(&child1_id, "grandchild".to_string()).unwrap();
986        assert_eq!(tree.len(), 4);
987        
988        // Delete node
989        tree.delete(&child2_id).unwrap();
990        assert_eq!(tree.len(), 4); // Node still exists but is invisible
991        
992        // Check tree structure
993        let tree_structure = tree.to_tree().unwrap();
994        assert_eq!(tree_structure.value, "root");
995        assert_eq!(tree_structure.children.len(), 1); // Only child1 is visible
996        assert_eq!(tree_structure.children[0].value, "child1");
997        assert_eq!(tree_structure.children[0].children.len(), 1);
998        assert_eq!(tree_structure.children[0].children[0].value, "grandchild");
999    }
1000    
1001    #[test]
1002    fn test_yjs_tree_merge() {
1003        let replica_id1 = create_replica(1);
1004        let replica_id2 = create_replica(2);
1005        
1006        let mut tree1 = YjsTree::<String>::new(replica_id1);
1007        let mut tree2 = YjsTree::<String>::new(replica_id2);
1008        
1009        // Add different roots
1010        let root1_id = tree1.add_root("root1".to_string()).unwrap();
1011        let root2_id = tree2.add_root("root2".to_string()).unwrap();
1012        
1013        // Add children
1014        tree1.add_child(&root1_id, "child1".to_string()).unwrap();
1015        tree2.add_child(&root2_id, "child2".to_string()).unwrap();
1016        
1017        // Merge
1018        tree1.merge(&tree2).unwrap();
1019        
1020        // Should contain both trees
1021        assert_eq!(tree1.len(), 4); // 2 roots + 2 children
1022    }
1023    
1024    #[test]
1025    fn test_dag_creation() {
1026        let replica_id = create_replica(1);
1027        let dag = Dag::<String>::new(replica_id.clone());
1028        
1029        assert_eq!(dag.replica_id(), &replica_id);
1030        assert!(dag.is_empty());
1031        assert_eq!(dag.len(), 0);
1032    }
1033    
1034    #[test]
1035    fn test_dag_operations() {
1036        let replica_id = create_replica(1);
1037        let mut dag = Dag::<String>::new(replica_id);
1038        
1039        // Add nodes
1040        let node1_id = dag.add_node("node1".to_string()).unwrap();
1041        let node2_id = dag.add_node("node2".to_string()).unwrap();
1042        let node3_id = dag.add_node("node3".to_string()).unwrap();
1043        
1044        assert_eq!(dag.len(), 3);
1045        
1046        // Add edges
1047        dag.add_edge(&node1_id, &node2_id).unwrap();
1048        dag.add_edge(&node2_id, &node3_id).unwrap();
1049        
1050        // Test topological sort
1051        let sorted = dag.topological_sort();
1052        assert_eq!(sorted.len(), 3);
1053        assert_eq!(sorted[0], node1_id);
1054        assert_eq!(sorted[1], node2_id);
1055        assert_eq!(sorted[2], node3_id);
1056        
1057        // Remove edge
1058        dag.remove_edge(&node1_id, &node2_id).unwrap();
1059        
1060        // Delete node
1061        dag.delete_node(&node2_id).unwrap();
1062        assert_eq!(dag.len(), 3); // Node still exists but is invisible
1063    }
1064    
1065    #[test]
1066    fn test_dag_cycle_detection() {
1067        let replica_id = create_replica(1);
1068        let mut dag = Dag::<String>::new(replica_id);
1069        
1070        // Add nodes
1071        let node1_id = dag.add_node("node1".to_string()).unwrap();
1072        let node2_id = dag.add_node("node2".to_string()).unwrap();
1073        let node3_id = dag.add_node("node3".to_string()).unwrap();
1074        
1075        // Add edges to create a cycle
1076        dag.add_edge(&node1_id, &node2_id).unwrap();
1077        dag.add_edge(&node2_id, &node3_id).unwrap();
1078        
1079        // Try to add edge that would create cycle
1080        let result = dag.add_edge(&node3_id, &node1_id);
1081        assert!(result.is_err());
1082        assert_eq!(result.unwrap_err(), AdvancedCrdtError::CycleDetected("Adding edge would create cycle".to_string()));
1083    }
1084    
1085    #[test]
1086    fn test_dag_merge() {
1087        let replica_id1 = create_replica(1);
1088        let replica_id2 = create_replica(2);
1089        
1090        let mut dag1 = Dag::<String>::new(replica_id1);
1091        let mut dag2 = Dag::<String>::new(replica_id2);
1092        
1093        // Add different nodes
1094        let node1_id = dag1.add_node("node1".to_string()).unwrap();
1095        let node2_id = dag2.add_node("node2".to_string()).unwrap();
1096        
1097        // Add edges (no self-loops in DAG)
1098        // Just add nodes without edges for merge test
1099        
1100        // Merge
1101        dag1.merge(&dag2).unwrap();
1102        
1103        // Should contain both nodes
1104        assert_eq!(dag1.len(), 2);
1105    }
1106    
1107    #[test]
1108    fn test_advanced_crdt_traits() {
1109        let replica_id = create_replica(1);
1110        
1111        // Test that all advanced CRDT types implement the required traits
1112        let rga: Rga<String> = Rga::new(replica_id.clone());
1113        let lseq: Lseq<String> = Lseq::new(replica_id.clone());
1114        let tree: YjsTree<String> = YjsTree::new(replica_id.clone());
1115        let dag: Dag<String> = Dag::new(replica_id);
1116        
1117        // This should compile if all types implement CRDT trait
1118        let _: &dyn CRDT = &rga;
1119        let _: &dyn CRDT = &lseq;
1120        let _: &dyn CRDT = &tree;
1121        let _: &dyn CRDT = &dag;
1122    }
1123}
leptos_sync_core/crdt/advanced.rs

leptos_sync_core/crdt/
advanced.rs
