ron_crdt/crdt/
set.rs

1//! 2-Phase Set
2
3use std::cmp::Ordering;
4use std::collections::HashSet;
5use std::default::Default;
6use std::str::FromStr;
7
8use uuid::UUID;
9
10use crate::{Atom, Frame, FrameOrd, Op, Terminator, CRDT};
11
12/// 2-Phase sets are sets of atoms.
13///
14/// Each element is associated with the timestamp of the Op that
15/// inserted it. Removing elements is done my inserting a tombstone. Thus, deletions override
16/// insertions.
17pub struct Set;
18
19impl Set {
20    /// Inserts `value` into the Set `state`. Returns the update Frame without modifying the Set.
21    pub fn insert<'a>(state: &Frame<'a>, value: Atom) -> Option<Frame<'a>> {
22        state.peek().map(|op| {
23            let &Op { ref ty, ref object, .. } = op;
24
25            Frame::compress(vec![Op {
26                ty: ty.clone(),
27                object: object.clone(),
28                event: UUID::now(),
29                location: UUID::zero(),
30                atoms: vec![value].into(),
31                term: Terminator::Raw,
32            }])
33        })
34    }
35
36    /// Removes `value` from the Set `state` by inserting a tombstone for all insertions of
37    /// `value`. Returns the update Frame without modifying the Set.
38    pub fn remove<'a>(state: Frame<'a>, value: &Atom) -> Option<Frame<'a>> {
39        Some(Frame::compress(
40            state
41                .filter_map(|op| {
42                    let Op { ty, object, event, location, atoms, .. } = op;
43
44                    if atoms.get(0) == Some(value) && location.is_zero() {
45                        Some(Op {
46                            ty: ty,
47                            object: object,
48                            event: UUID::now(),
49                            location: event,
50                            atoms: Default::default(),
51                            term: Terminator::Raw,
52                        })
53                    } else {
54                        None
55                    }
56                })
57                .collect::<Vec<_>>(),
58        ))
59    }
60}
61
62impl CRDT for Set {
63    type T = HashSet<Atom>;
64
65    fn new<'a>(obj: UUID) -> Frame<'a> {
66        Frame::compress(vec![Op {
67            ty: UUID::from_str("set").unwrap(),
68            object: obj,
69            event: UUID::now(),
70            location: UUID::zero(),
71            atoms: Default::default(),
72            term: Terminator::Header,
73        }])
74    }
75
76    fn reduce<'a>(
77        state: Frame<'a>, updates: Vec<Frame<'a>>,
78    ) -> Option<Frame<'a>> {
79        super::merge::<SetOrd>(state, updates)
80    }
81
82    fn map<'a>(state: Frame<'a>) -> Option<Self::T> {
83        use crate::Terminator::*;
84        use std::iter::FromIterator;
85
86        Some(HashSet::from_iter(state.filter_map(|mut op| {
87            match op {
88                Op { term: Header, .. } | Op { term: Query, .. } => None,
89                Op { ref location, ref mut atoms, .. }
90                    if location.is_zero() && atoms.len() == 1 =>
91                {
92                    Some(atoms.pop().unwrap())
93                }
94                Op { .. } => None,
95            }
96        })))
97    }
98}
99
100#[derive(Debug)]
101struct SetOrd<'a>(Frame<'a>);
102
103impl<'a> FrameOrd<'a> for SetOrd<'a> {
104    fn primary_cmp(a: &Op, b: &Op) -> Ordering {
105        let a = if a.location.is_zero() { &a.event } else { &a.location };
106        let b = if b.location.is_zero() { &b.event } else { &b.location };
107        UUID::weak_cmp(b, a)
108    }
109
110    fn secondary_cmp(a: &Op, b: &Op) -> Ordering {
111        UUID::weak_cmp(&b.location, &a.location)
112    }
113
114    fn peek(&self) -> Option<&Op> {
115        self.0.peek()
116    }
117}
118
119impl<'a> Iterator for SetOrd<'a> {
120    type Item = Op;
121
122    fn next(&mut self) -> Option<Op> {
123        self.0.next()
124    }
125}
126
127impl<'a> From<Frame<'a>> for SetOrd<'a> {
128    fn from(frame: Frame<'a>) -> Self {
129        SetOrd(frame)
130    }
131}
132
133#[cfg(test)]
134mod tests {
135    use super::*;
136
137    #[test]
138    fn set_basic_1() {
139        let f1 = Frame::parse("*set#test1@1=1;");
140        let f2 = Frame::parse("*set#test1@2=2;");
141        let exp = Frame::parse("*set#test1@2:0!:0=2@1=1");
142        let r = Set::reduce(f1, vec![f2]).unwrap();
143
144        eprintln!(
145            "expected: {:?}",
146            exp.clone().map(|x| format!("{} ", x)).collect::<Vec<_>>()
147        );
148        eprintln!(
149            "     got: {:?}",
150            r.clone().map(|x| format!("{} ", x)).collect::<Vec<_>>()
151        );
152        assert_eq!(exp.collect::<Vec<_>>(), r.collect::<Vec<_>>());
153    }
154
155    #[test]
156    fn set_basic_2() {
157        let f1 = Frame::parse("*set#test2@1!@=1");
158        let f2 = Frame::parse("*set#test2@2:1;");
159        let exp = Frame::parse("*set#test2@2!:1,");
160        let r = Set::reduce(f1, vec![f2]).unwrap();
161
162        eprintln!(
163            "expected: {:?}",
164            exp.clone().map(|x| format!("{} ", x)).collect::<Vec<_>>()
165        );
166        eprintln!(
167            "     got: {:?}",
168            r.clone().map(|x| format!("{} ", x)).collect::<Vec<_>>()
169        );
170        assert_eq!(exp.collect::<Vec<_>>(), r.collect::<Vec<_>>());
171    }
172
173    #[test]
174    fn set_basic_3() {
175        let f1 = Frame::parse("*set#test3@3:1;");
176        let f2 = Frame::parse("*set#test3@4:2;");
177        let exp = Frame::parse("*set#test3@4:3!:2,@3:1,");
178        let r = Set::reduce(f1, vec![f2]).unwrap();
179
180        eprintln!(
181            "expected: {:?}",
182            exp.clone().map(|x| format!("{} ", x)).collect::<Vec<_>>()
183        );
184        eprintln!(
185            "     got: {:?}",
186            r.clone().map(|x| format!("{} ", x)).collect::<Vec<_>>()
187        );
188        assert_eq!(exp.collect::<Vec<_>>(), r.collect::<Vec<_>>());
189    }
190
191    #[test]
192    fn set_basic_4() {
193        let f1 = Frame::parse("*set#test4@2:0!@=2@1=1");
194        let f2 = Frame::parse("*set#test4@5!@=5@3:2,@4:1,");
195        let exp = Frame::parse("*set#test4@5:0!@=5@3:2,@4:1,");
196        let r = Set::reduce(f1, vec![f2]).unwrap();
197
198        eprintln!(
199            "expected: {:?}",
200            exp.clone().map(|x| format!("{} ", x)).collect::<Vec<_>>()
201        );
202        eprintln!(
203            "     got: {:?}",
204            r.clone().map(|x| format!("{} ", x)).collect::<Vec<_>>()
205        );
206        assert_eq!(exp.collect::<Vec<_>>(), r.collect::<Vec<_>>());
207    }
208
209    #[test]
210    fn set_basic_5() {
211        let f1 = Frame::parse("*set#test5@2:0!@=2@1=1");
212        let f2 = Frame::parse("*set#test5@4!@3:2,@4:1,");
213        let f3 = Frame::parse("*set#test5@5:0!@=5");
214        let exp = Frame::parse("*set#test5@5:0!@5=5@3:2,@4:1,");
215        let r = Set::reduce(f1, vec![f2, f3]).unwrap();
216
217        eprintln!(
218            "expected: {:?}",
219            exp.clone().map(|x| format!("{} ", x)).collect::<Vec<_>>()
220        );
221        eprintln!(
222            "     got: {:?}",
223            r.clone().map(|x| format!("{} ", x)).collect::<Vec<_>>()
224        );
225        assert_eq!(exp.collect::<Vec<_>>(), r.collect::<Vec<_>>());
226    }
227
228    #[test]
229    fn set_basic_6() {
230        let f1 = Frame::parse("*set#test6@3!@:2,@4:1,");
231        let f2 = Frame::parse("*set#test6@5:0!@=5");
232        let f3 = Frame::parse("*set#test6@2!@=2@1=1");
233        let exp = Frame::parse("*set#test6@5:0!@5=5@3:2,@4:1,");
234        let r = Set::reduce(f1, vec![f2, f3]).unwrap();
235
236        eprintln!(
237            "expected: {:?}",
238            exp.clone().map(|x| format!("{} ", x)).collect::<Vec<_>>()
239        );
240        eprintln!(
241            "     got: {:?}",
242            r.clone().map(|x| format!("{} ", x)).collect::<Vec<_>>()
243        );
244        assert_eq!(exp.collect::<Vec<_>>(), r.collect::<Vec<_>>());
245    }
246
247    #[test]
248    fn set_basic_7() {
249        let f1 = Frame::parse("*set#mice@1YKDY54a01+1YKDY5!@>mouse$1YKDY5");
250        let f2 = Frame::parse("*set#mice@1YKDXO3201+1YKDXO!@>mouse$1YKDXO@(WBF901(WBY>mouse$1YKDWBY@[67H01[6>mouse$1YKDW6@(Uh4j01(Uh>mouse$1YKDUh@(S67V01(S6>mouse$1YKDS6@(Of(N3:1YKDN3DS01+1YKDN3,@(MvBV01(IuJ:0>mouse$1YKDIuJ@(LF:1YKDIuEY01+1YKDIuJ,:{A601,@(Io5l01[oA:0>mouse$1YKDIoA@[l7_01[l>mouse$1YKDIl@(57(4B:1YKD4B3f01+1YKD4B,@(0bB401+1YKCsd:0>mouse$1YKCsd        @1YKCu6+:1YKCsd7Q01+1YKCsd,");
251        let exp = Frame::parse("*set#mice@1YKDY54a01+1YKDY5!@(Y54a01(Y5>mouse$1YKDY5@(XO3201(XO>mouse$1YKDXO@(WBF901(WBY>mouse$1YKDWBY@[67H01[6>mouse$1YKDW6@(Uh4j01(Uh>mouse$1YKDUh@(S67V01(S6>mouse$1YKDS6@(Of(N3:1YKDN3DS01+1YKDN3,@(MvBV01(IuJ:0>mouse$1YKDIuJ@(LF:1YKDIuEY01+1YKDIuJ,:{A601,@(Io5l01[oA:0>mouse$1YKDIoA@[l7_01[l>mouse$1YKDIl@(57(4B:1YKD4B3f01+1YKD4B,@(0bB401+1YKCsd:0>mouse$1YKCsd  @1YKCu6+:1YKCsd7Q01+1YKCsd,");
252        let r = Set::reduce(f1, vec![f2]).unwrap();
253
254        eprintln!(
255            "expected: {:#?}",
256            exp.clone().map(|x| format!("{} ", x)).collect::<Vec<_>>()
257        );
258        eprintln!(
259            "     got: {:#?}",
260            r.clone().map(|x| format!("{} ", x)).collect::<Vec<_>>()
261        );
262        assert_eq!(exp.collect::<Vec<_>>(), r.collect::<Vec<_>>());
263    }
264
265    #[test]
266    fn map_basic_7() {
267        use std::str::FromStr;
268
269        let frm = Frame::parse("*set#mice@1YKDY54a01+1YKDY5!@(Y54a01(Y5>mouse$1YKDY5@(XO3201(XO>mouse$1YKDXO@(WBF901(WBY>mouse$1YKDWBY@[67H01[6>mouse$1YKDW6@(Uh4j01(Uh>mouse$1YKDUh@(S67V01(S6>mouse$1YKDS6@(Of(N3:1YKDN3DS01+1YKDN3,@(MvBV01(IuJ:0>mouse$1YKDIuJ@(LF:1YKDIuEY01+1YKDIuJ,:{A601,@(Io5l01[oA:0>mouse$1YKDIoA@[l7_01[l>mouse$1YKDIl@(57(4B:1YKD4B3f01+1YKD4B,@(0bB401+1YKCsd:0>mouse$1YKCsd@1YKCu6+:1YKCsd7Q01+1YKCsd,");
270        let r = Set::map(frm).unwrap();
271        let mut exp = HashSet::default();
272
273        exp.insert(Atom::UUID(UUID::from_str("mouse$1YKDY5").unwrap()));
274        exp.insert(Atom::UUID(UUID::from_str("mouse$1YKDXO").unwrap()));
275        exp.insert(Atom::UUID(UUID::from_str("mouse$1YKDWBY").unwrap()));
276        exp.insert(Atom::UUID(UUID::from_str("mouse$1YKDW6").unwrap()));
277        exp.insert(Atom::UUID(UUID::from_str("mouse$1YKDUh").unwrap()));
278        exp.insert(Atom::UUID(UUID::from_str("mouse$1YKDS6").unwrap()));
279        exp.insert(Atom::UUID(UUID::from_str("mouse$1YKDIuJ").unwrap()));
280        exp.insert(Atom::UUID(UUID::from_str("mouse$1YKDIoA").unwrap()));
281        exp.insert(Atom::UUID(UUID::from_str("mouse$1YKDIl").unwrap()));
282        exp.insert(Atom::UUID(UUID::from_str("mouse$1YKCsd").unwrap()));
283
284        assert_eq!(exp, r);
285    }
286
287    #[test]
288    fn map_empty() {
289        let frm = Set::new(UUID::now());
290        let r = Set::map(frm).unwrap();
291        let exp = HashSet::default();
292
293        assert_eq!(exp, r);
294    }
295
296    #[test]
297    fn map_insert_remove() {
298        use std::iter::FromIterator;
299
300        // empty set
301        let st0 = Set::new(UUID::now());
302        let exp0 = HashSet::default();
303        assert_eq!(exp0, Set::map(st0.clone()).unwrap());
304
305        // insert =1
306        let ch1 = Set::insert(&st0, Atom::Integer(1)).unwrap();
307        let st1 = Set::reduce(st0, vec![ch1]).unwrap();
308        let exp1 = HashSet::from_iter(vec![Atom::Integer(1)].into_iter());
309        assert_eq!(exp1, Set::map(st1.clone()).unwrap());
310
311        // insert =1
312        let ch2 = Set::insert(&st1, Atom::Integer(1)).unwrap();
313        let st2 = Set::reduce(st1, vec![ch2]).unwrap();
314        let exp2 = HashSet::from_iter(vec![Atom::Integer(1)].into_iter());
315        assert_eq!(exp2, Set::map(st2.clone()).unwrap());
316
317        // insert =2
318        let ch3 = Set::insert(&st2, Atom::Integer(2)).unwrap();
319        let st3 = Set::reduce(st2, vec![ch3]).unwrap();
320        let exp3 = HashSet::from_iter(
321            vec![Atom::Integer(1), Atom::Integer(2)].into_iter(),
322        );
323        assert_eq!(exp3, Set::map(st3.clone()).unwrap());
324
325        // remove =1
326        let ch4 = Set::remove(st3.clone(), &Atom::Integer(1)).unwrap();
327        let st4 = Set::reduce(st3, vec![ch4]).unwrap();
328        let exp4 = HashSet::from_iter(vec![Atom::Integer(2)].into_iter());
329        assert_eq!(exp4, Set::map(st4.clone()).unwrap());
330
331        //insert =1
332        let ch5 = Set::insert(&st4, Atom::Integer(1)).unwrap();
333        let st5 = Set::reduce(st4, vec![ch5]).unwrap();
334        let exp5 = HashSet::from_iter(
335            vec![Atom::Integer(1), Atom::Integer(2)].into_iter(),
336        );
337        assert_eq!(exp5, Set::map(st5.clone()).unwrap());
338
339        // remove =1
340        let ch6 = Set::remove(st5.clone(), &Atom::Integer(1)).unwrap();
341        let st6 = Set::reduce(st5, vec![ch6]).unwrap();
342        let exp6 = HashSet::from_iter(vec![Atom::Integer(2)].into_iter());
343        eprintln!("{:?}", st6);
344        assert_eq!(exp6, Set::map(st6.clone()).unwrap());
345
346        // remove =2
347        let ch7 = Set::remove(st6.clone(), &Atom::Integer(2)).unwrap();
348        let st7 = Set::reduce(st6, vec![ch7]).unwrap();
349        let exp7 = HashSet::default();
350        assert_eq!(exp7, Set::map(st7).unwrap());
351    }
352}
ron_crdt/crdt/set.rs

ron_crdt/crdt/
set.rs
