lattices/
dom_pair.rs

Help
1use std::cmp::Ordering::{self, *};
2
3use crate::{DeepReveal, IsBot, IsTop, LatticeFrom, LatticeOrd, Merge};
4
5/// Dominating pair compound lattice.
6///
7/// When merging if one `Key` (usually a timestamp) fully dominates (is greater than) the other,
8/// then both that `Key` and corresponding `Val` are selected. If the `Key`s are equal or
9/// incomparable, then both the `Key`s and `Val`s are merged.
10///
11/// `Key` specifies the key lattice (usually a timestamp), and `Val` specifies the value lattice.
12///
13/// Note that this is not a proper lattice, it fails associativity. However it will behave like a
14/// proper lattice if `Key` is a totally ordered lattice or a properly formed vector clock lattice.
15/// The exact meaning of "properly formed" is still TBD, but each node always incrementing its
16/// entry for each operation sent should be sufficient.
17#[derive(Copy, Clone, Debug, Default, Eq)]
18#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
19pub struct DomPair<Key, Val> {
20    /// The `Key` of the  dominating pair lattice, usually a timestamp.
21    ///
22    /// This field is public as it is always monotonically increasing in its lattice.
23    pub key: Key,
24    /// The `Val` of the dominating pair lattice.
25    val: Val,
26}
27
28impl<Key, Val> DomPair<Key, Val> {
29    /// Create a `DomPair` from the given `Key` and `Val`.
30    pub fn new(key: Key, val: Val) -> Self {
31        Self { key, val }
32    }
33
34    /// Create a `DomPair` from the given `Into<Key>` and `Into<Val>`.
35    pub fn new_from(key: impl Into<Key>, val: impl Into<Val>) -> Self {
36        Self::new(key.into(), val.into())
37    }
38
39    /// Reveal the inner value as a shared reference.
40    pub fn as_reveal_ref(&self) -> (&Key, &Val) {
41        (&self.key, &self.val)
42    }
43
44    /// Reveal the inner value as an exclusive reference.
45    pub fn as_reveal_mut(&mut self) -> (&mut Key, &mut Val) {
46        (&mut self.key, &mut self.val)
47    }
48
49    /// Gets the inner by value, consuming self.
50    pub fn into_reveal(self) -> (Key, Val) {
51        (self.key, self.val)
52    }
53}
54
55impl<Key, Val> DeepReveal for DomPair<Key, Val>
56where
57    Key: DeepReveal,
58    Val: DeepReveal,
59{
60    type Revealed = (Key::Revealed, Val::Revealed);
61
62    fn deep_reveal(self) -> Self::Revealed {
63        (self.key.deep_reveal(), self.val.deep_reveal())
64    }
65}
66
67impl<KeySelf, KeyOther, ValSelf, ValOther> Merge<DomPair<KeyOther, ValOther>>
68    for DomPair<KeySelf, ValSelf>
69where
70    KeySelf: Merge<KeyOther> + LatticeFrom<KeyOther> + PartialOrd<KeyOther>,
71    ValSelf: Merge<ValOther> + LatticeFrom<ValOther>,
72{
73    fn merge(&mut self, other: DomPair<KeyOther, ValOther>) -> bool {
74        match self.key.partial_cmp(&other.key) {
75            None => {
76                assert!(self.key.merge(other.key));
77                self.val.merge(other.val);
78                true
79            }
80            Some(Equal) => self.val.merge(other.val),
81            Some(Less) => {
82                *self = LatticeFrom::lattice_from(other);
83                true
84            }
85            Some(Greater) => false,
86        }
87    }
88}
89
90impl<KeySelf, KeyOther, ValSelf, ValOther> LatticeFrom<DomPair<KeyOther, ValOther>>
91    for DomPair<KeySelf, ValSelf>
92where
93    KeySelf: LatticeFrom<KeyOther>,
94    ValSelf: LatticeFrom<ValOther>,
95{
96    fn lattice_from(other: DomPair<KeyOther, ValOther>) -> Self {
97        Self {
98            key: LatticeFrom::lattice_from(other.key),
99            val: LatticeFrom::lattice_from(other.val),
100        }
101    }
102}
103
104impl<KeySelf, KeyOther, ValSelf, ValOther> PartialOrd<DomPair<KeyOther, ValOther>>
105    for DomPair<KeySelf, ValSelf>
106where
107    KeySelf: PartialOrd<KeyOther>,
108    ValSelf: PartialOrd<ValOther>,
109{
110    fn partial_cmp(&self, other: &DomPair<KeyOther, ValOther>) -> Option<Ordering> {
111        match self.key.partial_cmp(&other.key) {
112            Some(Equal) => self.val.partial_cmp(&other.val),
113            otherwise => otherwise,
114        }
115    }
116}
117impl<KeySelf, KeyOther, ValSelf, ValOther> LatticeOrd<DomPair<KeyOther, ValOther>>
118    for DomPair<KeySelf, ValSelf>
119where
120    Self: PartialOrd<DomPair<KeyOther, ValOther>>,
121{
122}
123
124impl<KeySelf, KeyOther, ValSelf, ValOther> PartialEq<DomPair<KeyOther, ValOther>>
125    for DomPair<KeySelf, ValSelf>
126where
127    KeySelf: PartialEq<KeyOther>,
128    ValSelf: PartialEq<ValOther>,
129{
130    fn eq(&self, other: &DomPair<KeyOther, ValOther>) -> bool {
131        if self.key != other.key {
132            return false;
133        }
134
135        if self.val != other.val {
136            return false;
137        }
138
139        true
140    }
141}
142
143impl<Key, Val> IsBot for DomPair<Key, Val>
144where
145    Key: IsBot,
146    Val: IsBot,
147{
148    fn is_bot(&self) -> bool {
149        self.key.is_bot() && self.val.is_bot()
150    }
151}
152
153impl<Key, Val> IsTop for DomPair<Key, Val>
154where
155    Key: IsTop,
156    Val: IsTop,
157{
158    fn is_top(&self) -> bool {
159        self.key.is_top() && self.val.is_top()
160    }
161}
162
163#[cfg(test)]
164mod test {
165    use std::collections::HashSet;
166
167    use super::*;
168    use crate::WithTop;
169    use crate::ord::Max;
170    use crate::set_union::SetUnionHashSet;
171    use crate::test::{
172        check_lattice_is_bot, check_lattice_is_top, check_lattice_ord, check_lattice_properties,
173        check_partial_ord_properties,
174    };
175
176    #[test]
177    fn consistency() {
178        let mut test_vec = Vec::new();
179
180        for a in [vec![], vec![0], vec![1], vec![0, 1]] {
181            for b in [vec![], vec![0], vec![1], vec![0, 1]] {
182                test_vec.push(DomPair::new(
183                    SetUnionHashSet::new_from(HashSet::from_iter(a.clone())),
184                    SetUnionHashSet::new_from(HashSet::from_iter(b.clone())),
185                ));
186            }
187        }
188
189        check_lattice_ord(&test_vec);
190        check_partial_ord_properties(&test_vec);
191        check_lattice_is_bot(&test_vec);
192        // DomPair is not actually a lattice.
193        assert!(std::panic::catch_unwind(|| check_lattice_properties(&test_vec)).is_err());
194    }
195
196    #[test]
197    fn consistency_withtop() {
198        let mut test_vec = vec![];
199
200        let sub_items = &[
201            Some(&[] as &[usize]),
202            Some(&[0]),
203            Some(&[1]),
204            Some(&[0, 1]),
205            None,
206        ];
207
208        for a in sub_items {
209            for b in sub_items {
210                test_vec.push(DomPair::new(
211                    WithTop::new(
212                        a.map(|x| SetUnionHashSet::new_from(HashSet::from_iter(x.iter().cloned()))),
213                    ),
214                    WithTop::new(
215                        b.map(|x| SetUnionHashSet::new_from(HashSet::from_iter(x.iter().cloned()))),
216                    ),
217                ));
218            }
219        }
220
221        check_lattice_ord(&test_vec);
222        check_partial_ord_properties(&test_vec);
223        check_lattice_is_bot(&test_vec);
224        check_lattice_is_top(&test_vec);
225        // DomPair is not actually a lattice.
226        assert!(std::panic::catch_unwind(|| check_lattice_properties(&test_vec)).is_err());
227    }
228
229    #[test]
230    fn consistency_with_ord_lhs() {
231        let mut test_vec = Vec::new();
232
233        for a in [0, 1, 2] {
234            for b in [vec![], vec![0], vec![1], vec![0, 1]] {
235                test_vec.push(DomPair::new(
236                    Max::new(a),
237                    SetUnionHashSet::new_from(HashSet::from_iter(b.clone())),
238                ));
239            }
240        }
241
242        check_lattice_ord(&test_vec);
243        check_lattice_properties(&test_vec);
244        check_partial_ord_properties(&test_vec);
245    }
246}
lattices/dom_pair.rs

lattices/
dom_pair.rs
