lattices/
set_union.rs

1//! Module containing the [`SetUnion`] lattice and aliases for different datastructures.
2
3#[cfg(feature = "alloc")]
4use alloc::collections::BTreeSet;
5use core::cmp::Ordering::{self, *};
6use core::marker::PhantomData;
7#[cfg(feature = "std")]
8use std::collections::HashSet;
9
10use cc_traits::SimpleCollectionRef;
11
12#[cfg(feature = "alloc")]
13use crate::Atomize;
14use crate::cc_traits::{Iter, Len, Set};
15use crate::collections::{ArraySet, OptionSet, SingletonSet};
16use crate::{DeepReveal, IsBot, IsTop, LatticeBimorphism, LatticeFrom, LatticeOrd, Merge};
17
18/// Set-union lattice.
19///
20/// Merging set-union lattices is done by unioning the keys.
21#[repr(transparent)]
22#[derive(Copy, Clone, Debug, Default)]
23#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
24pub struct SetUnion<Set>(pub Set);
25impl<Set> SetUnion<Set> {
26    /// Create a new `SetUnion` from a `Set`.
27    pub fn new(val: Set) -> Self {
28        Self(val)
29    }
30
31    /// Create a new `SetUnion` from an `Into<Set>`.
32    pub fn new_from(val: impl Into<Set>) -> Self {
33        Self::new(val.into())
34    }
35
36    /// Reveal the inner value as a shared reference.
37    pub fn as_reveal_ref(&self) -> &Set {
38        &self.0
39    }
40
41    /// Reveal the inner value as an exclusive reference.
42    pub fn as_reveal_mut(&mut self) -> &mut Set {
43        &mut self.0
44    }
45
46    /// Gets the inner by value, consuming self.
47    pub fn into_reveal(self) -> Set {
48        self.0
49    }
50}
51
52impl<Set> DeepReveal for SetUnion<Set> {
53    type Revealed = Set;
54
55    fn deep_reveal(self) -> Self::Revealed {
56        self.0
57    }
58}
59
60impl<SetSelf, SetOther, Item> Merge<SetUnion<SetOther>> for SetUnion<SetSelf>
61where
62    SetSelf: Extend<Item> + Len,
63    SetOther: IntoIterator<Item = Item>,
64{
65    fn merge(&mut self, other: SetUnion<SetOther>) -> bool {
66        let old_len = self.0.len();
67        self.0.extend(other.0);
68        self.0.len() > old_len
69    }
70}
71
72impl<SetSelf, SetOther, Item> LatticeFrom<SetUnion<SetOther>> for SetUnion<SetSelf>
73where
74    SetSelf: FromIterator<Item>,
75    SetOther: IntoIterator<Item = Item>,
76{
77    fn lattice_from(other: SetUnion<SetOther>) -> Self {
78        Self(other.0.into_iter().collect())
79    }
80}
81
82impl<SetSelf, SetOther, Item> PartialOrd<SetUnion<SetOther>> for SetUnion<SetSelf>
83where
84    SetSelf: Set<Item, Item = Item> + Iter,
85    SetOther: Set<Item, Item = Item> + Iter,
86{
87    fn partial_cmp(&self, other: &SetUnion<SetOther>) -> Option<Ordering> {
88        match self.0.len().cmp(&other.0.len()) {
89            Greater => {
90                if other.0.iter().all(|key| self.0.contains(&*key)) {
91                    Some(Greater)
92                } else {
93                    None
94                }
95            }
96            Equal => {
97                if self.0.iter().all(|key| other.0.contains(&*key)) {
98                    Some(Equal)
99                } else {
100                    None
101                }
102            }
103            Less => {
104                if self.0.iter().all(|key| other.0.contains(&*key)) {
105                    Some(Less)
106                } else {
107                    None
108                }
109            }
110        }
111    }
112}
113impl<SetSelf, SetOther> LatticeOrd<SetUnion<SetOther>> for SetUnion<SetSelf> where
114    Self: PartialOrd<SetUnion<SetOther>>
115{
116}
117
118impl<SetSelf, SetOther, Item> PartialEq<SetUnion<SetOther>> for SetUnion<SetSelf>
119where
120    SetSelf: Set<Item, Item = Item> + Iter,
121    SetOther: Set<Item, Item = Item> + Iter,
122{
123    fn eq(&self, other: &SetUnion<SetOther>) -> bool {
124        if self.0.len() != other.0.len() {
125            return false;
126        }
127
128        self.0.iter().all(|key| other.0.contains(&*key))
129    }
130}
131impl<SetSelf> Eq for SetUnion<SetSelf> where Self: PartialEq {}
132
133impl<Set> IsBot for SetUnion<Set>
134where
135    Set: Len,
136{
137    fn is_bot(&self) -> bool {
138        self.0.is_empty()
139    }
140}
141
142impl<Set> IsTop for SetUnion<Set> {
143    fn is_top(&self) -> bool {
144        false
145    }
146}
147
148#[cfg(feature = "alloc")]
149impl<Set, Item> Atomize for SetUnion<Set>
150where
151    Set: Len + IntoIterator<Item = Item> + Extend<Item>,
152    Set::IntoIter: 'static,
153    Item: 'static,
154{
155    type Atom = SetUnionSingletonSet<Item>;
156
157    // TODO: use impl trait, then remove 'static.
158    type AtomIter = alloc::boxed::Box<dyn Iterator<Item = Self::Atom>>;
159
160    fn atomize(self) -> Self::AtomIter {
161        alloc::boxed::Box::new(self.0.into_iter().map(SetUnionSingletonSet::new_from))
162    }
163}
164
165/// [`std::collections::HashSet`]-backed [`SetUnion`] lattice.
166#[cfg(feature = "std")]
167pub type SetUnionHashSet<Item> = SetUnion<HashSet<Item>>;
168
169/// [`std::collections::BTreeSet`]-backed [`SetUnion`] lattice.
170#[cfg(feature = "alloc")]
171pub type SetUnionBTreeSet<Item> = SetUnion<BTreeSet<Item>>;
172
173/// [`Vec`](alloc::vec::Vec)-backed [`SetUnion`] lattice.
174#[cfg(feature = "alloc")]
175pub type SetUnionVec<Item> = SetUnion<alloc::vec::Vec<Item>>;
176
177/// [`crate::collections::ArraySet`]-backed [`SetUnion`] lattice.
178pub type SetUnionArray<Item, const N: usize> = SetUnion<ArraySet<Item, N>>;
179
180/// [`crate::collections::SingletonSet`]-backed [`SetUnion`] lattice.
181pub type SetUnionSingletonSet<Item> = SetUnion<SingletonSet<Item>>;
182
183/// [`Option`]-backed [`SetUnion`] lattice.
184pub type SetUnionOptionSet<Item> = SetUnion<OptionSet<Item>>;
185
186/// Bimorphism for the cartesian product of two sets. Output is a set of all possible pairs of
187/// items from the two input sets.
188pub struct CartesianProductBimorphism<SetOut> {
189    _phantom: PhantomData<fn() -> SetOut>,
190}
191impl<SetOut> Default for CartesianProductBimorphism<SetOut> {
192    fn default() -> Self {
193        Self {
194            _phantom: Default::default(),
195        }
196    }
197}
198impl<SetA, SetB, SetOut> LatticeBimorphism<SetUnion<SetA>, SetUnion<SetB>>
199    for CartesianProductBimorphism<SetOut>
200where
201    SetA: IntoIterator,
202    SetB: Iter + SimpleCollectionRef,
203    SetA::Item: Clone,
204    SetB::Item: Clone,
205    SetOut: FromIterator<(SetA::Item, SetB::Item)>,
206{
207    type Output = SetUnion<SetOut>;
208
209    fn call(&mut self, lat_a: SetUnion<SetA>, lat_b: SetUnion<SetB>) -> Self::Output {
210        let set_a = lat_a.into_reveal();
211        let set_b = lat_b.into_reveal();
212        let set_out = set_a
213            .into_iter()
214            .flat_map(|a_item| {
215                set_b
216                    .iter()
217                    .map(<SetB as SimpleCollectionRef>::into_ref)
218                    .cloned()
219                    .map(move |b_item| (a_item.clone(), b_item))
220            })
221            .collect::<SetOut>();
222        SetUnion::new(set_out)
223    }
224}
225
226#[cfg(test)]
227mod test {
228    use super::*;
229    use crate::test::{check_all, check_atomize_each, check_lattice_bimorphism};
230
231    #[test]
232    fn test_set_union() {
233        let mut my_set_a = SetUnionHashSet::<&str>::new(HashSet::new());
234        let my_set_b = SetUnionBTreeSet::<&str>::new(BTreeSet::new());
235        let my_set_c = SetUnionSingletonSet::new(SingletonSet("hello world"));
236
237        assert_eq!(Some(Equal), my_set_a.partial_cmp(&my_set_a));
238        assert_eq!(Some(Equal), my_set_a.partial_cmp(&my_set_b));
239        assert_eq!(Some(Less), my_set_a.partial_cmp(&my_set_c));
240        assert_eq!(Some(Equal), my_set_b.partial_cmp(&my_set_a));
241        assert_eq!(Some(Equal), my_set_b.partial_cmp(&my_set_b));
242        assert_eq!(Some(Less), my_set_b.partial_cmp(&my_set_c));
243        assert_eq!(Some(Greater), my_set_c.partial_cmp(&my_set_a));
244        assert_eq!(Some(Greater), my_set_c.partial_cmp(&my_set_b));
245        assert_eq!(Some(Equal), my_set_c.partial_cmp(&my_set_c));
246
247        assert!(!my_set_a.merge(my_set_b));
248        assert!(my_set_a.merge(my_set_c));
249    }
250
251    #[test]
252    fn test_singleton_example() {
253        let mut my_hash_set = SetUnionHashSet::<&str>::default();
254        let my_delta_set = SetUnionSingletonSet::new_from("hello world");
255        let my_array_set = SetUnionArray::new_from(["hello world", "b", "c", "d"]);
256
257        assert_eq!(Some(Equal), my_delta_set.partial_cmp(&my_delta_set));
258        assert_eq!(Some(Less), my_delta_set.partial_cmp(&my_array_set));
259        assert_eq!(Some(Greater), my_array_set.partial_cmp(&my_delta_set));
260        assert_eq!(Some(Equal), my_array_set.partial_cmp(&my_array_set));
261
262        assert!(my_hash_set.merge(my_array_set)); // Changes
263        assert!(!my_hash_set.merge(my_delta_set)); // No changes
264    }
265
266    #[test]
267    fn consistency() {
268        check_all(&[
269            SetUnionHashSet::new_from([]),
270            SetUnionHashSet::new_from([0]),
271            SetUnionHashSet::new_from([1]),
272            SetUnionHashSet::new_from([0, 1]),
273        ]);
274    }
275
276    #[test]
277    fn atomize() {
278        check_atomize_each(&[
279            SetUnionHashSet::new_from([]),
280            SetUnionHashSet::new_from([0]),
281            SetUnionHashSet::new_from([1]),
282            SetUnionHashSet::new_from([0, 1]),
283            SetUnionHashSet::new((0..10).collect()),
284        ]);
285    }
286
287    #[test]
288    fn cartesian_product() {
289        let items_a = &[
290            SetUnionHashSet::new_from([]),
291            SetUnionHashSet::new_from([0]),
292            SetUnionHashSet::new_from([1]),
293            SetUnionHashSet::new_from([0, 1]),
294        ];
295        let items_b = &[
296            SetUnionBTreeSet::new("hello".chars().collect()),
297            SetUnionBTreeSet::new("world".chars().collect()),
298        ];
299
300        check_lattice_bimorphism(
301            CartesianProductBimorphism::<HashSet<_>>::default(),
302            items_a,
303            items_a,
304        );
305        check_lattice_bimorphism(
306            CartesianProductBimorphism::<HashSet<_>>::default(),
307            items_a,
308            items_b,
309        );
310        check_lattice_bimorphism(
311            CartesianProductBimorphism::<HashSet<_>>::default(),
312            items_b,
313            items_a,
314        );
315        check_lattice_bimorphism(
316            CartesianProductBimorphism::<HashSet<_>>::default(),
317            items_b,
318            items_b,
319        );
320    }
321}
lattices/set_union.rs

lattices/
set_union.rs
