lattices/
map_union_with_tombstones.rs

Help
1//! Module containing the [`MapUnionWithTombstones`] lattice and aliases for different datastructures.
2
3use std::cmp::Ordering::{self, *};
4use std::collections::{HashMap, HashSet};
5use std::fmt::Debug;
6
7use cc_traits::{Get, Iter, Len, Remove};
8
9use crate::cc_traits::{GetMut, Keyed, Map, MapIter, SimpleKeyedRef};
10use crate::collections::{EmptyMap, EmptySet, SingletonMap, SingletonSet};
11use crate::{IsBot, IsTop, LatticeFrom, LatticeOrd, Merge};
12
13/// Map-union-with-tombstones compound lattice.
14///
15/// When a key is deleted from the map-union-with-tombstones lattice, it is removed from the underlying `map` and placed into
16/// the `tombstones` set.
17///
18/// This forms the first invariant for this data structure. A key should appear either nowhere, in `map` or in `tombstones`.
19/// but never in `map` and `tombstones` at the same time.
20///
21/// merging is done by merging the underlying `map` and then merging the `tombstones` set, then doing `map` = `map` - `tombstones`.
22///
23/// The implementation of `tombstones` can be any set-like thing. This allows a user to plug in their own set-like implementation.
24/// For example, if the user knows that keys will be created and deleted strictly sequentially, then they could create a highly optimized set implementation
25/// which would just be a single integer, correpsonding to the current key value that the set is up to. Queries for keys below that integer would return true,
26/// queries for keys above it would return false.
27#[derive(Copy, Clone, Debug, Default)]
28#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
29pub struct MapUnionWithTombstones<Map, TombstoneSet> {
30    map: Map,
31    tombstones: TombstoneSet,
32}
33
34impl<Map, TombstoneSet> MapUnionWithTombstones<Map, TombstoneSet> {
35    /// Create a new `MapUnionWithTombstones` from a `Map` and a `TombstoneSet`.
36    pub fn new(map: Map, tombstones: TombstoneSet) -> Self {
37        Self { map, tombstones }
38    }
39
40    /// Create a new `MapUnionWithTombstones` from an `Into<Map>` and an `Into<TombstoneSet>`.
41    pub fn new_from(map: impl Into<Map>, tombstones: impl Into<TombstoneSet>) -> Self {
42        Self::new(map.into(), tombstones.into())
43    }
44
45    /// Reveal the inner value as a shared reference.
46    pub fn as_reveal_ref(&self) -> (&Map, &TombstoneSet) {
47        (&self.map, &self.tombstones)
48    }
49
50    /// Reveal the inner value as an exclusive reference.
51    pub fn as_reveal_mut(&mut self) -> (&mut Map, &mut TombstoneSet) {
52        (&mut self.map, &mut self.tombstones)
53    }
54
55    /// Gets the inner by value, consuming self.
56    pub fn into_reveal(self) -> (Map, TombstoneSet) {
57        (self.map, self.tombstones)
58    }
59}
60
61impl<MapSelf, MapOther, K, ValSelf, ValOther, TombstoneSetSelf, TombstoneSetOther>
62    Merge<MapUnionWithTombstones<MapOther, TombstoneSetOther>>
63    for MapUnionWithTombstones<MapSelf, TombstoneSetSelf>
64where
65    MapSelf: Keyed<Key = K, Item = ValSelf>
66        + Extend<(K, ValSelf)>
67        + for<'a> GetMut<&'a K, Item = ValSelf>
68        + for<'b> Remove<&'b K>,
69    MapOther: IntoIterator<Item = (K, ValOther)>,
70    ValSelf: Merge<ValOther> + LatticeFrom<ValOther>,
71    ValOther: IsBot,
72    TombstoneSetSelf: Extend<K> + Len + for<'a> Get<&'a K> + Iter<Item = K>,
73    TombstoneSetOther: IntoIterator<Item = K>,
74{
75    fn merge(&mut self, other: MapUnionWithTombstones<MapOther, TombstoneSetOther>) -> bool {
76        let mut changed = false;
77        // This vec collect is needed to prevent simultaneous mut references `self.0.extend` and
78        // `self.0.get_mut`.
79        // TODO(mingwei): This could be fixed with a different structure, maybe some sort of
80        // `Collection` entry API.
81        let iter: Vec<_> = other
82            .map
83            .into_iter()
84            .filter(|(k_other, val_other)| {
85                !val_other.is_bot() && !self.tombstones.contains(k_other)
86            })
87            .filter_map(|(k_other, val_other)| {
88                match self.map.get_mut(&k_other) {
89                    // Key collision, merge into `self`.
90                    Some(mut val_self) => {
91                        changed |= val_self.merge(val_other);
92                        None
93                    }
94                    // New value, convert for extending.
95                    None => {
96                        changed = true;
97                        Some((k_other, ValSelf::lattice_from(val_other)))
98                    }
99                }
100            })
101            .collect();
102        self.map.extend(iter);
103
104        let old_self_tombstones_len = self.tombstones.len();
105
106        self.tombstones
107            .extend(other.tombstones.into_iter().inspect(|k| {
108                self.map.remove(k);
109            }));
110
111        if old_self_tombstones_len != self.tombstones.len() {
112            changed = true;
113        }
114
115        changed
116    }
117}
118
119impl<MapSelf, MapOther, K, ValSelf, ValOther, TombstoneSetSelf, TombstoneSetOther>
120    LatticeFrom<MapUnionWithTombstones<MapOther, TombstoneSetOther>>
121    for MapUnionWithTombstones<MapSelf, TombstoneSetSelf>
122where
123    MapSelf: Keyed<Key = K, Item = ValSelf> + FromIterator<(K, ValSelf)>,
124    MapOther: IntoIterator<Item = (K, ValOther)>,
125    ValSelf: LatticeFrom<ValOther>,
126    TombstoneSetSelf: FromIterator<K>,
127    TombstoneSetOther: IntoIterator<Item = K>,
128{
129    fn lattice_from(other: MapUnionWithTombstones<MapOther, TombstoneSetOther>) -> Self {
130        Self {
131            map: other
132                .map
133                .into_iter()
134                .map(|(k_other, val_other)| (k_other, LatticeFrom::lattice_from(val_other)))
135                .collect(),
136            tombstones: other.tombstones.into_iter().collect(),
137        }
138    }
139}
140
141impl<MapSelf, MapOther, K, ValSelf, ValOther, TombstoneSetSelf, TombstoneSetOther>
142    PartialOrd<MapUnionWithTombstones<MapOther, TombstoneSetOther>>
143    for MapUnionWithTombstones<MapSelf, TombstoneSetSelf>
144where
145    MapSelf: Map<K, ValSelf, Key = K, Item = ValSelf> + MapIter + SimpleKeyedRef,
146    MapOther: Map<K, ValOther, Key = K, Item = ValOther> + MapIter + SimpleKeyedRef,
147    ValSelf: PartialOrd<ValOther> + IsBot,
148    ValOther: IsBot,
149    TombstoneSetSelf: Len + Iter<Item = K> + for<'a> Get<&'a K>,
150    TombstoneSetOther: Len + Iter<Item = K> + for<'a> Get<&'a K>,
151{
152    fn partial_cmp(
153        &self,
154        other: &MapUnionWithTombstones<MapOther, TombstoneSetOther>,
155    ) -> Option<Ordering> {
156        let self_tombstones_greater = self
157            .tombstones
158            .iter()
159            .any(|k| !other.tombstones.contains(&*k));
160
161        let other_tombstones_greater = other
162            .tombstones
163            .iter()
164            .any(|k| !self.tombstones.contains(&*k));
165
166        if self_tombstones_greater && other_tombstones_greater {
167            return None;
168        }
169
170        let mut self_any_greater = false;
171        let mut other_any_greater = false;
172        let self_keys = self
173            .map
174            .iter()
175            .filter(|(k, v)| {
176                !v.is_bot() && !self.tombstones.contains(k) && !other.tombstones.contains(k)
177            })
178            .map(|(k, _v)| <MapSelf as SimpleKeyedRef>::into_ref(k));
179        let other_keys = other
180            .map
181            .iter()
182            .filter(|(k, v)| {
183                !v.is_bot() && !self.tombstones.contains(k) && !other.tombstones.contains(k)
184            })
185            .map(|(k, _v)| <MapOther as SimpleKeyedRef>::into_ref(k));
186
187        for k in self_keys.chain(other_keys) {
188            match (self.map.get(k), other.map.get(k)) {
189                (Some(self_value), Some(other_value)) => {
190                    match self_value.partial_cmp(&*other_value)? {
191                        Less => {
192                            other_any_greater = true;
193                        }
194                        Greater => {
195                            self_any_greater = true;
196                        }
197                        Equal => {}
198                    }
199                }
200                (Some(_), None) => {
201                    self_any_greater = true;
202                }
203                (None, Some(_)) => {
204                    other_any_greater = true;
205                }
206                (None, None) => unreachable!(),
207            }
208            if self_any_greater && other_any_greater {
209                return None;
210            }
211        }
212        match (
213            self_any_greater,
214            other_any_greater,
215            self_tombstones_greater,
216            other_tombstones_greater,
217        ) {
218            (false, false, false, false) => Some(Equal),
219
220            (false, false, true, false) => Some(Greater),
221            (false, false, false, true) => Some(Less),
222
223            (true, false, false, false) => Some(Greater),
224            (false, true, false, false) => Some(Less),
225
226            (true, false, true, false) => Some(Greater),
227            (false, true, false, true) => Some(Less),
228
229            (true, false, false, true) => None,
230            (false, true, true, false) => None,
231
232            (true, true, _, _) => unreachable!(),
233            (_, _, true, true) => unreachable!(),
234        }
235    }
236}
237impl<MapSelf, MapOther, TombstoneSetSelf, TombstoneSetOther>
238    LatticeOrd<MapUnionWithTombstones<MapOther, TombstoneSetOther>>
239    for MapUnionWithTombstones<MapSelf, TombstoneSetSelf>
240where
241    Self: PartialOrd<MapUnionWithTombstones<MapOther, TombstoneSetOther>>,
242{
243}
244
245impl<MapSelf, MapOther, K, ValSelf, ValOther, TombstoneSetSelf, TombstoneSetOther>
246    PartialEq<MapUnionWithTombstones<MapOther, TombstoneSetOther>>
247    for MapUnionWithTombstones<MapSelf, TombstoneSetSelf>
248where
249    MapSelf: Map<K, ValSelf, Key = K, Item = ValSelf> + MapIter + SimpleKeyedRef,
250    MapOther: Map<K, ValOther, Key = K, Item = ValOther> + MapIter + SimpleKeyedRef,
251    ValSelf: PartialEq<ValOther> + IsBot,
252    ValOther: IsBot,
253    TombstoneSetSelf: Len + Iter<Item = K> + for<'a> Get<&'a K>,
254    TombstoneSetOther: Len + Iter<Item = K> + for<'b> Get<&'b K>,
255{
256    fn eq(&self, other: &MapUnionWithTombstones<MapOther, TombstoneSetOther>) -> bool {
257        if self.tombstones.len() != other.tombstones.len() {
258            return false;
259        }
260
261        if self
262            .tombstones
263            .iter()
264            .any(|k| !other.tombstones.contains(&*k))
265        {
266            return false;
267        }
268
269        if other
270            .tombstones
271            .iter()
272            .any(|k| !self.tombstones.contains(&*k))
273        {
274            return false;
275        }
276
277        let self_keys = self
278            .map
279            .iter()
280            .filter(|(_k, v)| !v.is_bot())
281            .map(|(k, _v)| <MapSelf as SimpleKeyedRef>::into_ref(k));
282        let other_keys = other
283            .map
284            .iter()
285            .filter(|(_k, v)| !v.is_bot())
286            .map(|(k, _v)| <MapOther as SimpleKeyedRef>::into_ref(k));
287        for k in self_keys.chain(other_keys) {
288            match (self.map.get(k), other.map.get(k)) {
289                (Some(self_value), Some(other_value)) => {
290                    if *self_value != *other_value {
291                        return false;
292                    }
293                }
294                (None, None) => unreachable!(),
295                _ => {
296                    return false;
297                }
298            }
299        }
300
301        true
302    }
303}
304impl<MapSelf, TombstoneSetSelf> Eq for MapUnionWithTombstones<MapSelf, TombstoneSetSelf> where
305    Self: PartialEq
306{
307}
308
309impl<Map, TombstoneSet> IsBot for MapUnionWithTombstones<Map, TombstoneSet>
310where
311    Map: Iter,
312    Map::Item: IsBot,
313    TombstoneSet: Len,
314{
315    fn is_bot(&self) -> bool {
316        self.map.iter().all(|v| v.is_bot()) && self.tombstones.is_empty()
317    }
318}
319
320impl<Map, TombstoneSet> IsTop for MapUnionWithTombstones<Map, TombstoneSet> {
321    fn is_top(&self) -> bool {
322        false
323    }
324}
325
326/// [`std::collections::HashMap`]-backed [`MapUnionWithTombstones`] lattice.
327pub type MapUnionHashMapWithTombstoneHashSet<K, Val> =
328    MapUnionWithTombstones<HashMap<K, Val>, HashSet<K>>;
329
330/// [`crate::collections::SingletonMap`]-backed [`MapUnionWithTombstones`] lattice.
331pub type MapUnionWithTombstonesSingletonMapOnly<K, Val> =
332    MapUnionWithTombstones<SingletonMap<K, Val>, EmptySet<K>>;
333
334/// [`crate::collections::SingletonSet`]-backed [`MapUnionWithTombstones`] lattice.
335pub type MapUnionWithTombstonesTombstoneSingletonSetOnly<K, Val> =
336    MapUnionWithTombstones<EmptyMap<K, Val>, SingletonSet<K>>;
337
338#[cfg(test)]
339mod test {
340    use super::*;
341    use crate::NaiveLatticeOrd;
342    use crate::set_union::{SetUnion, SetUnionHashSet, SetUnionSingletonSet};
343    use crate::test::check_all;
344
345    #[test]
346    fn test_map_union() {
347        type K = &'static str;
348        type V = usize;
349
350        type M = MapUnionWithTombstones<HashMap<K, SetUnionHashSet<V>>, HashSet<K>>;
351        type S = MapUnionWithTombstones<SingletonMap<K, SetUnionSingletonSet<V>>, EmptySet<K>>;
352        type T = MapUnionWithTombstones<EmptyMap<K, SetUnion<EmptySet<V>>>, SingletonSet<K>>;
353
354        let mut my_map_a = M::default();
355        let my_map_b = S::new(
356            SingletonMap("hello", SetUnion::new(SingletonSet(100))),
357            Default::default(),
358        );
359
360        let my_map_c = T::new(Default::default(), SingletonSet("hello"));
361
362        my_map_a.merge(my_map_b);
363        my_map_a.merge(my_map_c);
364
365        assert!(!my_map_a.as_reveal_ref().0.contains_key("hello"));
366    }
367
368    #[test]
369    fn contrain1() {
370        type T = MapUnionWithTombstones<HashMap<i32, SetUnion<HashSet<i32>>>, HashSet<i32>>;
371
372        let a = T::new_from([], HashSet::from_iter([0]));
373        let b = T::new_from(
374            [(0, SetUnionHashSet::new_from([0]))],
375            HashSet::from_iter([]),
376        );
377
378        assert_eq!(a.naive_cmp(&b), Some(Greater));
379        assert_eq!(a.partial_cmp(&b), Some(Greater));
380
381        let a = T::new_from([], HashSet::from_iter([1]));
382        let b = T::new_from([(0, SetUnionHashSet::new_from([0]))], HashSet::default());
383
384        assert_eq!(a.naive_cmp(&b), None);
385        assert_eq!(a.partial_cmp(&b), None);
386    }
387
388    #[test]
389    fn consistency() {
390        type K = &'static str;
391        type V = SetUnion<HashSet<i32>>;
392
393        type M = MapUnionWithTombstones<HashMap<K, V>, HashSet<K>>;
394
395        let mut test_vec = Vec::new();
396
397        #[rustfmt::skip]
398        {
399            test_vec.push(M::new_from([], HashSet::from_iter([])));
400
401            test_vec.push(M::new_from([], HashSet::from_iter(["a"])));
402            test_vec.push(M::new_from([], HashSet::from_iter(["b"])));
403            test_vec.push(M::new_from([], HashSet::from_iter(["a", "b"])));
404
405            test_vec.push(M::new_from([("a", SetUnionHashSet::new_from([]))], HashSet::from_iter([])));
406            test_vec.push(M::new_from([("a", SetUnionHashSet::new_from([0]))], HashSet::from_iter([])));
407            test_vec.push(M::new_from([("a", SetUnionHashSet::new_from([1]))], HashSet::from_iter([])));
408            test_vec.push(M::new_from([("a", SetUnionHashSet::new_from([0, 1]))], HashSet::from_iter([])));
409
410            test_vec.push(M::new_from([("b", SetUnionHashSet::new_from([]))], HashSet::from_iter([])));
411            test_vec.push(M::new_from([("b", SetUnionHashSet::new_from([0]))], HashSet::from_iter([])));
412            test_vec.push(M::new_from([("b", SetUnionHashSet::new_from([1]))], HashSet::from_iter([])));
413            test_vec.push(M::new_from([("b", SetUnionHashSet::new_from([0, 1]))], HashSet::from_iter([])));
414        };
415
416        check_all(&test_vec);
417    }
418
419    /// Check that a key with a value of bottom is the same as an empty map, etc.
420    #[test]
421    fn test_collapses_bot() {
422        type K = &'static str;
423        type V = SetUnion<HashSet<i32>>;
424
425        type A = MapUnionWithTombstones<HashMap<K, V>, HashSet<K>>;
426        type B = MapUnionWithTombstones<SingletonMap<K, V>, HashSet<K>>;
427
428        let map_empty = A::default();
429
430        let map_a_bot = B::new(SingletonMap("a", Default::default()), Default::default());
431        let map_b_bot = B::new(SingletonMap("b", Default::default()), Default::default());
432
433        assert_eq!(map_empty, map_a_bot);
434        assert_eq!(map_empty, map_b_bot);
435        assert_eq!(map_a_bot, map_b_bot);
436    }
437}
lattices/map_union_with_tombstones.rs

lattices/
map_union_with_tombstones.rs
