uni_crdt/
orset.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4use crate::CrdtMerge;
5use fxhash::{FxHashMap, FxHashSet};
6use serde::{Deserialize, Serialize};
7use std::hash::Hash;
8use uuid::Uuid;
9
10/// An Observed-Remove Set (ORSet).
11///
12/// Supports both add and remove operations. Uses unique tags to track element provenance.
13/// Conflict resolution: Add-wins (concurrent add + remove results in the element being present).
14#[derive(Debug, Clone, Serialize, Deserialize, PartialEq)]
15pub struct ORSet<T: Hash + Eq + Clone> {
16    /// element -> {tags}
17    elements: FxHashMap<T, FxHashSet<Uuid>>,
18    /// removed tags
19    tombstones: FxHashSet<Uuid>,
20}
21
22impl<T: Hash + Eq + Clone> Default for ORSet<T> {
23    fn default() -> Self {
24        Self {
25            elements: FxHashMap::default(),
26            tombstones: FxHashSet::default(),
27        }
28    }
29}
30
31impl<T: Hash + Eq + Clone> ORSet<T> {
32    /// Create a new, empty ORSet.
33    pub fn new() -> Self {
34        Self::default()
35    }
36
37    /// Add an element to the set. Returns the generated tag.
38    pub fn add(&mut self, element: T) -> Uuid {
39        let tag = Uuid::new_v4();
40        self.elements.entry(element).or_default().insert(tag);
41        tag
42    }
43
44    /// Remove an element from the set.
45    /// All currently observed tags for this element are added to the tombstones.
46    pub fn remove(&mut self, element: &T) {
47        if let Some(tags) = self.elements.get(element) {
48            self.tombstones.extend(tags.iter().copied());
49        }
50    }
51
52    /// An element is visible if it has at least one tag that hasn't been tombstoned.
53    fn is_visible(&self, tags: &FxHashSet<Uuid>) -> bool {
54        tags.iter().any(|tag| !self.tombstones.contains(tag))
55    }
56
57    /// Check if an element is in the set.
58    /// An element is present if it has at least one tag that hasn't been tombstoned.
59    pub fn contains(&self, element: &T) -> bool {
60        self.elements
61            .get(element)
62            .is_some_and(|tags| self.is_visible(tags))
63    }
64
65    /// Returns a vector of all visible elements in the set.
66    pub fn elements(&self) -> Vec<T> {
67        self.elements
68            .iter()
69            .filter(|(_, tags)| self.is_visible(tags))
70            .map(|(elem, _)| elem.clone())
71            .collect()
72    }
73
74    /// Returns the number of visible elements.
75    pub fn len(&self) -> usize {
76        self.elements
77            .values()
78            .filter(|tags| self.is_visible(tags))
79            .count()
80    }
81
82    /// Returns true if the set has no visible elements.
83    pub fn is_empty(&self) -> bool {
84        self.len() == 0
85    }
86}
87
88impl<T: Hash + Eq + Clone> CrdtMerge for ORSet<T> {
89    fn merge(&mut self, other: &Self) {
90        // Merge elements and their tags
91        for (element, other_tags) in &other.elements {
92            self.elements
93                .entry(element.clone())
94                .or_default()
95                .extend(other_tags.iter().copied());
96        }
97        // Merge tombstones
98        self.tombstones.extend(other.tombstones.iter().copied());
99    }
100}
101
102#[cfg(test)]
103mod tests {
104    use super::*;
105
106    #[test]
107    fn test_add_remove() {
108        let mut os = ORSet::new();
109        os.add("apple".to_string());
110        assert!(os.contains(&"apple".to_string()));
111
112        os.remove(&"apple".to_string());
113        assert!(!os.contains(&"apple".to_string()));
114    }
115
116    #[test]
117    fn test_add_wins() {
118        let mut a = ORSet::new();
119        a.add("apple".to_string());
120
121        let mut b = a.clone();
122        b.remove(&"apple".to_string());
123
124        // Concurrent add on 'a'
125        a.add("apple".to_string());
126
127        a.merge(&b);
128
129        // Add wins because the new tag in 'a' was not tombstoned in 'b'
130        assert!(a.contains(&"apple".to_string()));
131    }
132
133    #[test]
134    fn test_merge() {
135        let mut a = ORSet::new();
136        a.add(1);
137        a.add(2);
138
139        let mut b = ORSet::new();
140        b.add(2);
141        b.add(3);
142
143        a.merge(&b);
144
145        let elements = a.elements();
146        assert!(elements.contains(&1));
147        assert!(elements.contains(&2));
148        assert!(elements.contains(&3));
149        assert_eq!(elements.len(), 3);
150    }
151}
uni_crdt/orset.rs

uni_crdt/
orset.rs
