lattices/
set_union_with_tombstones.rs

Help
1//! Module containing the [`SetUnionWithTombstones`] lattice and aliases for different datastructures.
2
3use std::cmp::Ordering::{self, *};
4use std::collections::{BTreeSet, HashSet};
5
6use cc_traits::{Collection, Get, Remove};
7
8use crate::cc_traits::{Iter, Len, Set};
9use crate::collections::{ArraySet, EmptySet, OptionSet, SingletonSet};
10use crate::{IsBot, IsTop, LatticeFrom, LatticeOrd, Merge};
11
12/// Set-union lattice with tombstones.
13///
14/// When an item is deleted from the SetUnionWithTombstones, it is removed from `set` and added to `tombstones`.
15/// This also is an invariant, if an item appears in `tombstones` it must not also be in `set`.
16///
17/// Merging set-union lattices is done by unioning the keys of both the (set and tombstone) sets,
18/// and then performing `set` = `set` - `tombstones`, to preserve the above invariant.
19///
20/// TODO: I think there is even one more layer of abstraction that can be made here.
21/// this 'SetUnionWithTombstones' can be turned into a kind of interface, because there are multiple underlying implementations.
22/// This implementation is two separate sets. Another implementation could be MapUnion<Key, WithTop<()>>, this would be less hash lookups, but maybe gives you less options for cool storage tricks.
23/// This implementation with two separate sets means that the actual set implementation can be decided for both the regular set and the tombstone set. Lots of opportunities there for cool storage tricks.
24#[derive(Default, Clone, Debug)]
25pub struct SetUnionWithTombstones<Set, TombstoneSet> {
26    set: Set,
27    tombstones: TombstoneSet,
28}
29
30impl<Set, TombstoneSet> SetUnionWithTombstones<Set, TombstoneSet> {
31    /// Create a new `SetUnionWithTombstones` from a `Set` and `TombstoneSet`.
32    pub fn new(set: Set, tombstones: TombstoneSet) -> Self {
33        Self { set, tombstones }
34    }
35
36    /// Create a new `SetUnionWithTombstones` from an `Into<Set>` and an `Into<TombstonesSet>`.
37    pub fn new_from(set: impl Into<Set>, tombstones: impl Into<TombstoneSet>) -> Self {
38        Self::new(set.into(), tombstones.into())
39    }
40
41    /// Reveal the inner value as a shared reference.
42    pub fn as_reveal_ref(&self) -> (&Set, &TombstoneSet) {
43        (&self.set, &self.tombstones)
44    }
45
46    /// Reveal the inner value as an exclusive reference.
47    pub fn as_reveal_mut(&mut self) -> (&mut Set, &mut TombstoneSet) {
48        (&mut self.set, &mut self.tombstones)
49    }
50
51    /// Gets the inner by value, consuming self.
52    pub fn into_reveal(self) -> (Set, TombstoneSet) {
53        (self.set, self.tombstones)
54    }
55}
56
57impl<Item, SetSelf, TombstoneSetSelf, SetOther, TombstoneSetOther>
58    Merge<SetUnionWithTombstones<SetOther, TombstoneSetOther>>
59    for SetUnionWithTombstones<SetSelf, TombstoneSetSelf>
60where
61    SetSelf: Extend<Item> + Len + for<'a> Remove<&'a Item>,
62    SetOther: IntoIterator<Item = Item>,
63    TombstoneSetSelf: Extend<Item> + Len + for<'a> Get<&'a Item>,
64    TombstoneSetOther: IntoIterator<Item = Item>,
65{
66    fn merge(&mut self, other: SetUnionWithTombstones<SetOther, TombstoneSetOther>) -> bool {
67        let old_set_len = self.set.len();
68        let old_tombstones_len = self.tombstones.len();
69
70        // Merge other set into self, don't include anything deleted by the current tombstone set.
71        self.set.extend(
72            other
73                .set
74                .into_iter()
75                .filter(|x| !self.tombstones.contains(x)),
76        );
77
78        // Combine the tombstone sets. Also need to remove any items in the remote tombstone set that currently exist in the local set.
79        self.tombstones
80            .extend(other.tombstones.into_iter().inspect(|x| {
81                self.set.remove(x);
82            }));
83
84        // if either there are new items in the real set, or the tombstone set increased
85        old_set_len < self.set.len() || old_tombstones_len < self.tombstones.len()
86    }
87}
88
89impl<SetSelf, TombstoneSetSelf, SetOther, TombstoneSetOther, Item>
90    LatticeFrom<SetUnionWithTombstones<SetOther, TombstoneSetOther>>
91    for SetUnionWithTombstones<SetSelf, TombstoneSetSelf>
92where
93    SetSelf: FromIterator<Item>,
94    SetOther: IntoIterator<Item = Item>,
95    TombstoneSetSelf: FromIterator<Item>,
96    TombstoneSetOther: IntoIterator<Item = Item>,
97{
98    fn lattice_from(other: SetUnionWithTombstones<SetOther, TombstoneSetOther>) -> Self {
99        Self {
100            set: other.set.into_iter().collect(),
101            tombstones: other.tombstones.into_iter().collect(),
102        }
103    }
104}
105
106impl<SetSelf, TombstoneSetSelf, SetOther, TombstoneSetOther, Item>
107    PartialOrd<SetUnionWithTombstones<SetOther, TombstoneSetOther>>
108    for SetUnionWithTombstones<SetSelf, TombstoneSetSelf>
109where
110    SetSelf: Set<Item, Item = Item> + Iter,
111    SetOther: Set<Item, Item = Item> + Iter,
112    TombstoneSetSelf: Set<Item, Item = Item> + Iter,
113    TombstoneSetOther: Set<Item, Item = Item> + Iter,
114{
115    fn partial_cmp(
116        &self,
117        other: &SetUnionWithTombstones<SetOther, TombstoneSetOther>,
118    ) -> Option<Ordering> {
119        fn set_cmp<I, A, B>(a: &A, b: &B) -> Option<Ordering>
120        where
121            A: Collection<Item = I> + Iter + for<'a> Get<&'a I> + Len,
122            B: Collection<Item = I> + Iter + for<'a> Get<&'a I> + Len,
123        {
124            match a.len().cmp(&b.len()) {
125                Less => {
126                    if a.iter().all(|key| b.contains(&*key)) {
127                        Some(Less)
128                    } else {
129                        None
130                    }
131                }
132                Equal => {
133                    if a.iter().all(|key| b.contains(&*key)) {
134                        Some(Equal)
135                    } else {
136                        None
137                    }
138                }
139                Greater => {
140                    if b.iter().all(|key| a.contains(&*key)) {
141                        Some(Greater)
142                    } else {
143                        None
144                    }
145                }
146            }
147        }
148
149        fn set_cmp_filter<I, A, B, C, D>(a: &A, b: &B, f1: &C, f2: &D) -> Option<Ordering>
150        where
151            A: Collection<Item = I> + Iter + for<'a> Get<&'a I> + Len,
152            B: Collection<Item = I> + Iter + for<'a> Get<&'a I> + Len,
153            C: for<'a> Get<&'a I>,
154            D: for<'a> Get<&'a I>,
155        {
156            let is_a_greater_than_b = a
157                .iter()
158                .filter(|key| !f2.contains(key))
159                .any(|key| !b.contains(&*key));
160
161            let is_b_greater_than_a = b
162                .iter()
163                .filter(|key| !f1.contains(key))
164                .any(|key| !a.contains(&*key));
165
166            match (is_a_greater_than_b, is_b_greater_than_a) {
167                (true, true) => None,
168                (true, false) => Some(Greater),
169                (false, true) => Some(Less),
170                (false, false) => Some(Equal),
171            }
172        }
173
174        match set_cmp(&self.tombstones, &other.tombstones) {
175            Some(Less) => {
176                match set_cmp_filter(&self.set, &other.set, &self.tombstones, &other.tombstones) {
177                    Some(Greater) => None,
178                    Some(Less) => Some(Less),
179                    Some(Equal) => Some(Less),
180                    None => None,
181                }
182            }
183            Some(Equal) => set_cmp(&self.set, &other.set),
184            Some(Greater) => {
185                match set_cmp_filter(&self.set, &other.set, &self.tombstones, &other.tombstones) {
186                    Some(Greater) => Some(Greater),
187                    Some(Equal) => Some(Greater),
188                    Some(Less) => None,
189                    None => None,
190                }
191            }
192            None => None,
193        }
194    }
195}
196impl<SetSelf, TombstoneSetSelf, SetOther, TombstoneSetOther>
197    LatticeOrd<SetUnionWithTombstones<SetOther, TombstoneSetOther>>
198    for SetUnionWithTombstones<SetSelf, TombstoneSetSelf>
199where
200    Self: PartialOrd<SetUnionWithTombstones<SetOther, TombstoneSetOther>>,
201{
202}
203
204impl<SetSelf, TombstoneSetSelf, SetOther, TombstoneSetOther, Item>
205    PartialEq<SetUnionWithTombstones<SetOther, TombstoneSetOther>>
206    for SetUnionWithTombstones<SetSelf, TombstoneSetSelf>
207where
208    SetSelf: Set<Item, Item = Item> + Iter,
209    SetOther: Set<Item, Item = Item> + Iter,
210    TombstoneSetSelf: Set<Item, Item = Item> + Iter,
211    TombstoneSetOther: Set<Item, Item = Item> + Iter,
212{
213    fn eq(&self, other: &SetUnionWithTombstones<SetOther, TombstoneSetOther>) -> bool {
214        if self.set.len() != other.set.len() || self.tombstones.len() != other.tombstones.len() {
215            return false;
216        }
217
218        self.set.iter().all(|key| other.set.contains(&*key))
219            && self
220                .tombstones
221                .iter()
222                .all(|key| other.tombstones.contains(&*key))
223    }
224}
225impl<SetSelf, TombstoneSetSelf> Eq for SetUnionWithTombstones<SetSelf, TombstoneSetSelf> where
226    Self: PartialEq
227{
228}
229
230impl<Set, TombstoneSet> IsBot for SetUnionWithTombstones<Set, TombstoneSet>
231where
232    Set: Len,
233    TombstoneSet: Len,
234{
235    fn is_bot(&self) -> bool {
236        self.set.is_empty() && self.tombstones.is_empty()
237    }
238}
239
240impl<Set, TombstoneSet> IsTop for SetUnionWithTombstones<Set, TombstoneSet> {
241    fn is_top(&self) -> bool {
242        false
243    }
244}
245
246/// [`std::collections::HashSet`]-backed [`SetUnionWithTombstones`] lattice.
247pub type SetUnionWithTombstonesHashSet<Item> = SetUnionWithTombstones<HashSet<Item>, HashSet<Item>>;
248
249/// [`std::collections::BTreeSet`]-backed [`SetUnionWithTombstones`] lattice.
250pub type SetUnionWithTombstonesBTreeSet<Item> =
251    SetUnionWithTombstones<BTreeSet<Item>, BTreeSet<Item>>;
252
253/// [`Vec`]-backed [`SetUnionWithTombstones`] lattice.
254pub type SetUnionWithTombstonesVec<Item> = SetUnionWithTombstones<Vec<Item>, Vec<Item>>;
255
256/// [`crate::collections::ArraySet`]-backed [`SetUnionWithTombstones`] lattice.
257pub type SetUnionWithTombstonesArray<Item, const N: usize> =
258    SetUnionWithTombstones<ArraySet<Item, N>, ArraySet<Item, N>>;
259
260/// [`crate::collections::SingletonSet`]-backed [`SetUnionWithTombstones`] lattice.
261pub type SetUnionWithTombstonesSingletonSet<Item> =
262    SetUnionWithTombstones<SingletonSet<Item>, SingletonSet<Item>>;
263
264/// [`Option`]-backed [`SetUnionWithTombstones`] lattice.
265pub type SetUnionWithTombstonesOptionSet<Item> =
266    SetUnionWithTombstones<OptionSet<Item>, OptionSet<Item>>;
267
268/// [`crate::collections::SingletonSet`]-backed [`SetUnionWithTombstones`] lattice.
269pub type SetUnionWithTombstonesTombstoneOnlySet<Item> =
270    SetUnionWithTombstones<EmptySet<Item>, SingletonSet<Item>>;
271
272#[cfg(test)]
273mod test {
274    use super::*;
275    use crate::test::check_all;
276
277    #[test]
278    fn delete_one() {
279        let mut x = SetUnionWithTombstonesHashSet::new_from([1], []);
280        let y = SetUnionWithTombstonesTombstoneOnlySet::new_from(EmptySet::default(), 1);
281
282        assert_eq!(x.partial_cmp(&y), Some(Less));
283
284        x.merge(y);
285
286        assert!(x.as_reveal_mut().1.contains(&1));
287    }
288
289    #[test]
290    fn test_specific_cases() {
291        assert_eq!(
292            SetUnionWithTombstonesHashSet::new_from([], [0])
293                .partial_cmp(&SetUnionWithTombstonesHashSet::new_from([0], [])),
294            Some(Greater),
295        );
296
297        assert_eq!(
298            SetUnionWithTombstonesHashSet::new_from([0], [1])
299                .partial_cmp(&SetUnionWithTombstonesHashSet::new_from([], [])),
300            Some(Greater),
301        );
302
303        assert_eq!(
304            SetUnionWithTombstonesHashSet::new_from([], [0])
305                .partial_cmp(&SetUnionWithTombstonesHashSet::new_from([], [])),
306            Some(Greater),
307        );
308
309        assert_eq!(
310            SetUnionWithTombstonesHashSet::new_from([], [0])
311                .partial_cmp(&SetUnionWithTombstonesHashSet::new_from([], [])),
312            Some(Greater),
313        );
314    }
315
316    #[test]
317    fn consistency() {
318        check_all(&[
319            SetUnionWithTombstonesHashSet::new_from([], []),
320            SetUnionWithTombstonesHashSet::new_from([0], []),
321            SetUnionWithTombstonesHashSet::new_from([], [0]),
322            SetUnionWithTombstonesHashSet::new_from([1], []),
323            SetUnionWithTombstonesHashSet::new_from([], [1]),
324            SetUnionWithTombstonesHashSet::new_from([0, 1], []),
325            SetUnionWithTombstonesHashSet::new_from([], [0, 1]),
326            SetUnionWithTombstonesHashSet::new_from([0], [1]),
327            SetUnionWithTombstonesHashSet::new_from([1], [0]),
328        ]);
329    }
330}
lattices/set_union_with_tombstones.rs

lattices/
set_union_with_tombstones.rs
