leptos_sync_core/crdt/
list.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 list operations
8#[derive(Debug, Clone, PartialEq, Eq)]
9pub struct ListError {
10    message: String,
11}
12
13impl ListError {
14    pub fn new(message: String) -> Self {
15        Self { message }
16    }
17}
18
19impl std::fmt::Display for ListError {
20    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
21        write!(f, "ListError: {}", self.message)
22    }
23}
24
25impl Error for ListError {}
26
27/// Unique identifier for a list element
28#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
29pub struct ElementId {
30    /// Unique identifier for the element
31    pub id: Uuid,
32    /// Replica that created the element
33    pub replica: ReplicaId,
34}
35
36impl ElementId {
37    /// Create a new element ID
38    pub fn new(replica: ReplicaId) -> Self {
39        Self {
40            id: Uuid::new_v4(),
41            replica,
42        }
43    }
44
45    /// Create an element 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 list element
52#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
53pub struct ElementMetadata {
54    /// When the element was created
55    pub created_at: u64,
56    /// When the element was last modified
57    pub modified_at: u64,
58    /// Whether the element is marked as deleted
59    pub deleted: bool,
60    /// Replica that last modified the element
61    pub last_modified_by: ReplicaId,
62}
63
64impl ElementMetadata {
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 list element with its metadata
89#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
90pub struct ListElement<T> {
91    /// Unique identifier
92    pub id: ElementId,
93    /// The actual value
94    pub value: T,
95    /// Metadata
96    pub metadata: ElementMetadata,
97}
98
99impl<T> ListElement<T> {
100    /// Create a new list element
101    pub fn new(value: T, replica: ReplicaId, timestamp: u64) -> Self {
102        Self {
103            id: ElementId::new(replica),
104            value,
105            metadata: ElementMetadata::new(replica, timestamp),
106        }
107    }
108
109    /// Mark as modified
110    pub fn mark_modified(&mut self, replica: ReplicaId, timestamp: u64) {
111        self.metadata.mark_modified(replica, timestamp);
112    }
113
114    /// Mark as deleted
115    pub fn mark_deleted(&mut self, replica: ReplicaId, timestamp: u64) {
116        self.metadata.mark_deleted(replica, timestamp);
117    }
118}
119
120/// Strategy for handling list conflicts
121#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
122pub enum ListStrategy {
123    /// Add-Wins: Elements are never removed, only marked as deleted
124    AddWins,
125    /// Remove-Wins: Deleted elements are completely removed
126    RemoveWins,
127    /// Last-Write-Wins: Most recent modification wins
128    LastWriteWins,
129}
130
131/// Configuration for list CRDTs
132#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
133pub struct ListConfig {
134    /// Conflict resolution strategy
135    pub strategy: ListStrategy,
136    /// Whether to preserve deleted elements in metadata
137    pub preserve_deleted: bool,
138    /// Maximum number of elements to keep in memory
139    pub max_elements: Option<usize>,
140}
141
142impl Default for ListConfig {
143    fn default() -> Self {
144        Self {
145            strategy: ListStrategy::AddWins,
146            preserve_deleted: true,
147            max_elements: None,
148        }
149    }
150}
151
152/// Add-Wins List CRDT implementation
153/// 
154/// This implementation ensures that elements are never completely lost.
155/// Deleted elements are marked as deleted but preserved for potential recovery.
156#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
157pub struct AddWinsList<T> {
158    /// Configuration
159    config: ListConfig,
160    /// Elements in the list
161    elements: HashMap<ElementId, ListElement<T>>,
162    /// Replica ID for this instance
163    replica: ReplicaId,
164}
165
166impl<T: Clone + PartialEq + Eq + Send + Sync> AddWinsList<T> {
167    /// Create a new Add-Wins list
168    pub fn new(replica: ReplicaId) -> Self {
169        Self {
170            config: ListConfig::default(),
171            elements: HashMap::new(),
172            replica,
173        }
174    }
175
176    /// Create with custom configuration
177    pub fn with_config(replica: ReplicaId, config: ListConfig) -> Self {
178        Self {
179            config,
180            elements: HashMap::new(),
181            replica,
182        }
183    }
184
185    /// Add an element to the list
186    pub fn add(&mut self, value: T, timestamp: u64) -> ElementId {
187        let element = ListElement::new(value, self.replica, timestamp);
188        let id = element.id.clone();
189        self.elements.insert(id.clone(), element);
190        id
191    }
192
193    /// Update an existing element
194    pub fn update(&mut self, id: &ElementId, value: T, timestamp: u64) -> Result<(), ListError> {
195        if let Some(element) = self.elements.get_mut(id) {
196            element.value = value;
197            element.mark_modified(self.replica, timestamp);
198            Ok(())
199        } else {
200            Err(ListError::new("Element not found".to_string()))
201        }
202    }
203
204    /// Mark an element as deleted
205    pub fn remove(&mut self, id: &ElementId, timestamp: u64) -> Result<(), ListError> {
206        if let Some(element) = self.elements.get_mut(id) {
207            element.mark_deleted(self.replica, timestamp);
208            Ok(())
209        } else {
210            Err(ListError::new("Element not found".to_string()))
211        }
212    }
213
214    /// Get an element by ID
215    pub fn get(&self, id: &ElementId) -> Option<&ListElement<T>> {
216        self.elements.get(id)
217    }
218
219    /// Get all visible elements (not deleted)
220    pub fn visible_elements(&self) -> Vec<&ListElement<T>> {
221        self.elements
222            .values()
223            .filter(|e| !e.metadata.deleted)
224            .collect()
225    }
226
227    /// Get all elements including deleted ones
228    pub fn all_elements(&self) -> Vec<&ListElement<T>> {
229        self.elements.values().collect()
230    }
231
232    /// Check if the list contains an element
233    pub fn contains(&self, id: &ElementId) -> bool {
234        self.elements.contains_key(id)
235    }
236
237    /// Get the length of visible elements
238    pub fn len(&self) -> usize {
239        self.visible_elements().len()
240    }
241
242    /// Check if the list is empty
243    pub fn is_empty(&self) -> bool {
244        self.len() == 0
245    }
246
247    /// Clear all elements
248    pub fn clear(&mut self) {
249        self.elements.clear();
250    }
251}
252
253impl<T: Clone + PartialEq + Eq + Send + Sync> CRDT for AddWinsList<T> {
254    fn replica_id(&self) -> &ReplicaId {
255        &self.replica
256    }
257}
258
259impl<T: Clone + PartialEq + Eq + Send + Sync> Mergeable for AddWinsList<T> {
260    type Error = ListError;
261
262    fn merge(&mut self, other: &Self) -> Result<(), Self::Error> {
263        for (id, element) in &other.elements {
264            match self.elements.get(id) {
265                Some(existing) => {
266                    // Conflict resolution: later timestamp wins
267                    if element.metadata.modified_at > existing.metadata.modified_at {
268                        self.elements.insert(id.clone(), element.clone());
269                    }
270                }
271                None => {
272                    // New element, add it
273                    self.elements.insert(id.clone(), element.clone());
274                }
275            }
276        }
277        Ok(())
278    }
279
280    fn has_conflict(&self, other: &Self) -> bool {
281        for (id, element) in &other.elements {
282            if let Some(existing) = self.elements.get(id) {
283                // Check for conflicts: same timestamp but different replica
284                if element.metadata.modified_at == existing.metadata.modified_at
285                    && element.metadata.last_modified_by != existing.metadata.last_modified_by
286                {
287                    return true;
288                }
289            }
290        }
291        false
292    }
293}
294
295/// Remove-Wins List CRDT implementation
296/// 
297/// This implementation completely removes deleted elements.
298/// It's more memory-efficient but elements cannot be recovered.
299#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
300pub struct RemoveWinsList<T> {
301    /// Configuration
302    config: ListConfig,
303    /// Elements in the list
304    elements: HashMap<ElementId, ListElement<T>>,
305    /// Replica ID for this instance
306    replica: ReplicaId,
307}
308
309impl<T: Clone + PartialEq + Eq + Send + Sync> RemoveWinsList<T> {
310    /// Create a new Remove-Wins list
311    pub fn new(replica: ReplicaId) -> Self {
312        Self {
313            config: ListConfig {
314                strategy: ListStrategy::RemoveWins,
315                preserve_deleted: false,
316                max_elements: None,
317            },
318            elements: HashMap::new(),
319            replica,
320        }
321    }
322
323    /// Create with custom configuration
324    pub fn with_config(replica: ReplicaId, config: ListConfig) -> Self {
325        Self {
326            config,
327            elements: HashMap::new(),
328            replica,
329        }
330    }
331
332    /// Add an element to the list
333    pub fn add(&mut self, value: T, timestamp: u64) -> ElementId {
334        let element = ListElement::new(value, self.replica, timestamp);
335        let id = element.id.clone();
336        self.elements.insert(id.clone(), element);
337        id
338    }
339
340    /// Update an existing element
341    pub fn update(&mut self, id: &ElementId, value: T, timestamp: u64) -> Result<(), ListError> {
342        if let Some(element) = self.elements.get_mut(id) {
343            element.value = value;
344            element.mark_modified(self.replica, timestamp);
345            Ok(())
346        } else {
347            Err(ListError::new("Element not found".to_string()))
348        }
349    }
350
351    /// Remove an element completely
352    pub fn remove(&mut self, id: &ElementId) -> Result<(), ListError> {
353        if self.elements.remove(id).is_some() {
354            Ok(())
355        } else {
356            Err(ListError::new("Element not found".to_string()))
357        }
358    }
359
360    /// Get an element by ID
361    pub fn get(&self, id: &ElementId) -> Option<&ListElement<T>> {
362        self.elements.get(id)
363    }
364
365    /// Get all elements
366    pub fn elements(&self) -> Vec<&ListElement<T>> {
367        self.elements.values().collect()
368    }
369
370    /// Check if the list contains an element
371    pub fn contains(&self, id: &ElementId) -> bool {
372        self.elements.contains_key(id)
373    }
374
375    /// Get the length
376    pub fn len(&self) -> usize {
377        self.elements.len()
378    }
379
380    /// Check if the list is empty
381    pub fn is_empty(&self) -> bool {
382        self.elements.is_empty()
383    }
384
385    /// Clear all elements
386    pub fn clear(&mut self) {
387        self.elements.clear();
388    }
389}
390
391impl<T: Clone + PartialEq + Eq + Send + Sync> CRDT for RemoveWinsList<T> {
392    fn replica_id(&self) -> &ReplicaId {
393        &self.replica
394    }
395}
396
397impl<T: Clone + PartialEq + Eq + Send + Sync> Mergeable for RemoveWinsList<T> {
398    type Error = ListError;
399
400    fn merge(&mut self, other: &Self) -> Result<(), Self::Error> {
401        for (id, element) in &other.elements {
402            match self.elements.get(id) {
403                Some(existing) => {
404                    // Conflict resolution: later timestamp wins
405                    if element.metadata.modified_at > existing.metadata.modified_at {
406                        self.elements.insert(id.clone(), element.clone());
407                    }
408                }
409                None => {
410                    // New element, add it
411                    self.elements.insert(id.clone(), element.clone());
412                }
413            }
414        }
415        Ok(())
416    }
417
418    fn has_conflict(&self, other: &Self) -> bool {
419        for (id, element) in &other.elements {
420            if let Some(existing) = self.elements.get(id) {
421                // Check for conflicts: same timestamp but different replica
422                if element.metadata.modified_at == existing.metadata.modified_at
423                    && element.metadata.last_modified_by != existing.metadata.last_modified_by
424                {
425                    return true;
426                }
427            }
428        }
429        false
430    }
431}
432
433/// Last-Write-Wins List CRDT implementation
434/// 
435/// This implementation uses timestamps to resolve conflicts.
436/// The most recent modification always wins.
437#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
438pub struct LwwList<T> {
439    /// Configuration
440    config: ListConfig,
441    /// Elements in the list
442    elements: HashMap<ElementId, ListElement<T>>,
443    /// Replica ID for this instance
444    replica: ReplicaId,
445}
446
447impl<T: Clone + PartialEq + Eq + Send + Sync> LwwList<T> {
448    /// Create a new LWW list
449    pub fn new(replica: ReplicaId) -> Self {
450        Self {
451            config: ListConfig {
452                strategy: ListStrategy::LastWriteWins,
453                preserve_deleted: true,
454                max_elements: None,
455            },
456            elements: HashMap::new(),
457            replica,
458        }
459    }
460
461    /// Create with custom configuration
462    pub fn with_config(replica: ReplicaId, config: ListConfig) -> Self {
463        Self {
464            config,
465            elements: HashMap::new(),
466            replica,
467        }
468    }
469
470    /// Add an element to the list
471    pub fn add(&mut self, value: T, timestamp: u64) -> ElementId {
472        let element = ListElement::new(value, self.replica, timestamp);
473        let id = element.id.clone();
474        self.elements.insert(id.clone(), element);
475        id
476    }
477
478    /// Update an existing element
479    pub fn update(&mut self, id: &ElementId, value: T, timestamp: u64) -> Result<(), ListError> {
480        if let Some(element) = self.elements.get_mut(id) {
481            element.value = value;
482            element.mark_modified(self.replica, timestamp);
483            Ok(())
484        } else {
485            Err(ListError::new("Element not found".to_string()))
486        }
487    }
488
489    /// Mark an element as deleted
490    pub fn remove(&mut self, id: &ElementId, timestamp: u64) -> Result<(), ListError> {
491        if let Some(element) = self.elements.get_mut(id) {
492            element.mark_deleted(self.replica, timestamp);
493            Ok(())
494        } else {
495            Err(ListError::new("Element not found".to_string()))
496        }
497    }
498
499    /// Get an element by ID
500    pub fn get(&self, id: &ElementId) -> Option<&ListElement<T>> {
501        self.elements.get(id)
502    }
503
504    /// Get all visible elements (not deleted)
505    pub fn visible_elements(&self) -> Vec<&ListElement<T>> {
506        self.elements
507            .values()
508            .filter(|e| !e.metadata.deleted)
509            .collect()
510    }
511
512    /// Get all elements including deleted ones
513    pub fn all_elements(&self) -> Vec<&ListElement<T>> {
514        self.elements.values().collect()
515    }
516
517    /// Check if the list contains an element
518    pub fn contains(&self, id: &ElementId) -> bool {
519        self.elements.contains_key(id)
520    }
521
522    /// Get the length of visible elements
523    pub fn len(&self) -> usize {
524        self.visible_elements().len()
525    }
526
527    /// Check if the list is empty
528    pub fn is_empty(&self) -> bool {
529        self.len() == 0
530    }
531
532    /// Clear all elements
533    pub fn clear(&mut self) {
534        self.elements.clear();
535    }
536}
537
538impl<T: Clone + PartialEq + Eq + Send + Sync> CRDT for LwwList<T> {
539    fn replica_id(&self) -> &ReplicaId {
540        &self.replica
541    }
542}
543
544impl<T: Clone + PartialEq + Eq + Send + Sync> Mergeable for LwwList<T> {
545    type Error = ListError;
546
547    fn merge(&mut self, other: &Self) -> Result<(), Self::Error> {
548        for (id, element) in &other.elements {
549            match self.elements.get(id) {
550                Some(existing) => {
551                    // Conflict resolution: later timestamp wins
552                    if element.metadata.modified_at > existing.metadata.modified_at {
553                        self.elements.insert(id.clone(), element.clone());
554                    }
555                }
556                None => {
557                    // New element, add it
558                    self.elements.insert(id.clone(), element.clone());
559                }
560            }
561        }
562        Ok(())
563    }
564
565    fn has_conflict(&self, other: &Self) -> bool {
566        for (id, element) in &other.elements {
567            if let Some(existing) = self.elements.get(id) {
568                // Check for conflicts: same timestamp but different replica
569                if element.metadata.modified_at == existing.metadata.modified_at
570                    && element.metadata.last_modified_by != existing.metadata.last_modified_by
571                {
572                    return true;
573                }
574            }
575        }
576        false
577    }
578}
579
580#[cfg(test)]
581mod tests {
582    use super::*;
583    use super::super::ReplicaId;
584    use uuid::Uuid;
585
586    fn create_replica(id: u64) -> ReplicaId {
587        ReplicaId::from(Uuid::from_u64_pair(0, id))
588    }
589
590    #[test]
591    fn test_element_id_creation() {
592        let replica = create_replica(1);
593        let element_id = ElementId::new(replica);
594        
595        assert_eq!(element_id.replica, replica);
596        assert_ne!(element_id.id, Uuid::nil());
597    }
598
599    #[test]
600    fn test_list_element_creation() {
601        let replica = create_replica(1);
602        let timestamp = 1234567890;
603        let element = ListElement::new("test_value", replica, timestamp);
604        
605        assert_eq!(element.value, "test_value");
606        assert_eq!(element.metadata.created_at, timestamp);
607        assert_eq!(element.metadata.modified_at, timestamp);
608        assert_eq!(element.metadata.deleted, false);
609        assert_eq!(element.metadata.last_modified_by, replica);
610    }
611
612    #[test]
613    fn test_add_wins_list_basic_operations() {
614        let replica = create_replica(1);
615        let mut list = AddWinsList::new(replica);
616        
617        // Add elements
618        let id1 = list.add("first", 1000);
619        let id2 = list.add("second", 2000);
620        
621        assert_eq!(list.len(), 2);
622        assert!(list.contains(&id1));
623        assert!(list.contains(&id2));
624        
625        // Update element
626        list.update(&id1, "updated_first", 3000).unwrap();
627        assert_eq!(list.get(&id1).unwrap().value, "updated_first");
628        
629        // Remove element (marks as deleted)
630        list.remove(&id2, 4000).unwrap();
631        assert_eq!(list.len(), 1); // Only visible elements
632        assert!(list.get(&id2).unwrap().metadata.deleted);
633    }
634
635    #[test]
636    fn test_remove_wins_list_basic_operations() {
637        let replica = create_replica(1);
638        let mut list = RemoveWinsList::new(replica);
639        
640        // Add elements
641        let id1 = list.add("first", 1000);
642        let id2 = list.add("second", 2000);
643        
644        assert_eq!(list.len(), 2);
645        
646        // Remove element completely
647        list.remove(&id2).unwrap();
648        assert_eq!(list.len(), 1);
649        assert!(!list.contains(&id2));
650    }
651
652    #[test]
653    fn test_lww_list_basic_operations() {
654        let replica = create_replica(1);
655        let mut list = LwwList::new(replica);
656        
657        // Add elements
658        let id1 = list.add("first", 1000);
659        let id2 = list.add("second", 2000);
660        
661        assert_eq!(list.len(), 2);
662        
663        // Update element
664        list.update(&id1, "updated_first", 3000).unwrap();
665        assert_eq!(list.get(&id1).unwrap().value, "updated_first");
666        
667        // Remove element (marks as deleted)
668        list.remove(&id2, 4000).unwrap();
669        assert_eq!(list.len(), 1);
670        assert!(list.get(&id2).unwrap().metadata.deleted);
671    }
672
673    #[test]
674    fn test_list_merge() {
675        let replica1 = create_replica(1);
676        let replica2 = create_replica(2);
677        
678        let mut list1 = AddWinsList::new(replica1);
679        let mut list2 = AddWinsList::new(replica2);
680        
681        // Add elements to both lists
682        let id1 = list1.add("from_replica1", 1000);
683        let id2 = list2.add("from_replica2", 2000);
684        
685        // Merge list2 into list1
686        list1.merge(&list2).unwrap();
687        
688        // Both elements should be present
689        assert_eq!(list1.len(), 2);
690        assert!(list1.contains(&id1));
691        assert!(list1.contains(&id2));
692    }
693
694    #[test]
695    fn test_list_merge_conflict_resolution() {
696        let replica1 = create_replica(1);
697        let replica2 = create_replica(2);
698        
699        let mut list1 = AddWinsList::new(replica1);
700        let mut list2 = AddWinsList::new(replica2);
701        
702        // Create same element with different values
703        let id = list1.add("value1", 1000);
704        list2.elements.insert(id.clone(), ListElement::new("value2", replica2, 2000));
705        
706        // Merge - later timestamp should win
707        list1.merge(&list2).unwrap();
708        assert_eq!(list1.get(&id).unwrap().value, "value2");
709    }
710
711    #[test]
712    fn test_list_configuration() {
713        let replica = create_replica(1);
714        let config = ListConfig {
715            strategy: ListStrategy::RemoveWins,
716            preserve_deleted: false,
717            max_elements: Some(100),
718        };
719        
720        let list: AddWinsList<String> = AddWinsList::with_config(replica, config);
721        assert_eq!(list.config.strategy, ListStrategy::RemoveWins);
722        assert_eq!(list.config.max_elements, Some(100));
723    }
724}
leptos_sync_core/crdt/list.rs

leptos_sync_core/crdt/
list.rs
