lattices/
with_top.rs

1use core::cmp::Ordering::{self, *};
2
3use crate::{Atomize, DeepReveal, IsBot, IsTop, LatticeFrom, LatticeOrd, Merge};
4
5/// Adds a new "top" value to the nested lattice type.
6///
7/// Given an existing lattice, wrap it into a new lattice with a new top element. The new top
8/// element compares as less than all the values of the wrapped lattice.  This can be used for
9/// giving a sensible default/bottom element to lattices that don't necessarily have one.
10///
11/// The implementation wraps an [`Option`], with [`None`] representing the top element.
12#[repr(transparent)]
13#[derive(Copy, Clone, Debug, Eq)]
14#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
15pub struct WithTop<Inner>(Option<Inner>);
16impl<Inner> WithTop<Inner> {
17    /// Create a new `WithTop` lattice instance from a value.
18    pub fn new(val: Option<Inner>) -> Self {
19        Self(val)
20    }
21
22    /// Create a new `WithTop` lattice instance from a value using `Into`.
23    pub fn new_from(val: impl Into<Option<Inner>>) -> Self {
24        Self::new(val.into())
25    }
26
27    /// Reveal the inner value as a shared reference.
28    pub fn as_reveal_ref(&self) -> Option<&Inner> {
29        self.0.as_ref()
30    }
31
32    /// Reveal the inner value as an exclusive reference.
33    pub fn as_reveal_mut(&mut self) -> Option<&mut Inner> {
34        self.0.as_mut()
35    }
36
37    /// Gets the inner by value, consuming self.
38    pub fn into_reveal(self) -> Option<Inner> {
39        self.0
40    }
41}
42
43// Use inner's default rather than `None` (which is top, not bot).
44impl<Inner> Default for WithTop<Inner>
45where
46    Inner: Default,
47{
48    fn default() -> Self {
49        Self(Some(Inner::default()))
50    }
51}
52
53impl<Inner> DeepReveal for WithTop<Inner>
54where
55    Inner: DeepReveal,
56{
57    type Revealed = Option<Inner::Revealed>;
58
59    fn deep_reveal(self) -> Self::Revealed {
60        self.0.map(DeepReveal::deep_reveal)
61    }
62}
63
64impl<Inner, Other> Merge<WithTop<Other>> for WithTop<Inner>
65where
66    Inner: Merge<Other> + LatticeFrom<Other>,
67{
68    fn merge(&mut self, other: WithTop<Other>) -> bool {
69        match (&mut self.0, other.0) {
70            (None, None) => false,
71            (this @ Some(_), None) => {
72                *this = None;
73                true
74            }
75            (None, Some(_)) => false,
76            (Some(self_inner), Some(other_inner)) => self_inner.merge(other_inner),
77        }
78    }
79}
80
81impl<Inner, Other> LatticeFrom<WithTop<Other>> for WithTop<Inner>
82where
83    Inner: LatticeFrom<Other>,
84{
85    fn lattice_from(other: WithTop<Other>) -> Self {
86        Self(other.0.map(Inner::lattice_from))
87    }
88}
89
90impl<Inner, Other> PartialOrd<WithTop<Other>> for WithTop<Inner>
91where
92    Inner: PartialOrd<Other>,
93{
94    fn partial_cmp(&self, other: &WithTop<Other>) -> Option<Ordering> {
95        match (&self.0, &other.0) {
96            (None, None) => Some(Equal),
97            (None, Some(_)) => Some(Greater),
98            (Some(_), None) => Some(Less),
99            (Some(this_inner), Some(other_inner)) => this_inner.partial_cmp(other_inner),
100        }
101    }
102}
103impl<Inner, Other> LatticeOrd<WithTop<Other>> for WithTop<Inner> where
104    Self: PartialOrd<WithTop<Other>>
105{
106}
107
108impl<Inner, Other> PartialEq<WithTop<Other>> for WithTop<Inner>
109where
110    Inner: PartialEq<Other>,
111{
112    fn eq(&self, other: &WithTop<Other>) -> bool {
113        match (&self.0, &other.0) {
114            (None, None) => true,
115            (None, Some(_)) => false,
116            (Some(_), None) => false,
117            (Some(this_inner), Some(other_inner)) => this_inner == other_inner,
118        }
119    }
120}
121
122impl<Inner> IsBot for WithTop<Inner>
123where
124    Inner: IsBot,
125{
126    fn is_bot(&self) -> bool {
127        self.0.as_ref().is_some_and(IsBot::is_bot)
128    }
129}
130
131impl<Inner> IsTop for WithTop<Inner>
132where
133    Inner: IsTop,
134{
135    fn is_top(&self) -> bool {
136        self.0.as_ref().is_none_or(IsTop::is_top)
137    }
138}
139
140#[cfg(feature = "alloc")]
141impl<Inner> Atomize for WithTop<Inner>
142where
143    Inner: Atomize + LatticeFrom<<Inner as Atomize>::Atom>,
144{
145    type Atom = WithTop<Inner::Atom>;
146
147    // TODO: use impl trait, then remove 'static.
148    type AtomIter = alloc::boxed::Box<dyn Iterator<Item = Self::Atom>>;
149
150    fn atomize(self) -> Self::AtomIter {
151        match self.0 {
152            Some(inner) => alloc::boxed::Box::new(inner.atomize().map(WithTop::new_from)),
153            None => alloc::boxed::Box::new(core::iter::once(WithTop::new(None))),
154        }
155    }
156}
157
158#[cfg(test)]
159mod test {
160    use super::*;
161    use crate::set_union::{SetUnionHashSet, SetUnionSingletonSet};
162    use crate::test::{check_all, check_atomize_each, check_lattice_is_top};
163
164    #[test]
165    fn test_singly_nested_singleton_example() {
166        let mut my_hash_set = WithTop::new_from(SetUnionHashSet::<&str>::default());
167        let my_delta_set = WithTop::new_from(SetUnionSingletonSet::new_from("hello world"));
168
169        assert!(my_hash_set.merge(my_delta_set)); // Changes
170        assert!(!my_hash_set.merge(my_delta_set)); // No changes
171    }
172
173    #[test]
174    fn test_doubly_nested_singleton_example() {
175        let mut my_hash_set =
176            WithTop::new_from(WithTop::new_from(SetUnionHashSet::<&str>::default()));
177        let my_delta_set = WithTop::new_from(WithTop::new_from(SetUnionSingletonSet::new_from(
178            "hello world",
179        )));
180
181        assert!(my_hash_set.merge(my_delta_set)); // Changes
182        assert!(!my_hash_set.merge(my_delta_set)); // No changes
183    }
184
185    #[test]
186    #[rustfmt::skip]
187    fn auto_derives() {
188        type B = WithTop<SetUnionHashSet<usize>>;
189
190        assert_eq!(B::new(None).partial_cmp(&B::new(None)), Some(Equal));
191        assert_eq!(B::new_from(SetUnionHashSet::new_from([])).partial_cmp(&B::new(None)), Some(Less));
192        assert_eq!(B::new(None).partial_cmp(&B::new_from(SetUnionHashSet::new_from([]))), Some(Greater));
193        assert_eq!(B::new_from(SetUnionHashSet::new_from([])).partial_cmp(&B::new_from(SetUnionHashSet::new_from([]))), Some(Equal));
194        assert_eq!(B::new_from(SetUnionHashSet::new_from([0])).partial_cmp(&B::new_from(SetUnionHashSet::new_from([]))), Some(Greater));
195        assert_eq!(B::new_from(SetUnionHashSet::new_from([])).partial_cmp(&B::new_from(SetUnionHashSet::new_from([0]))), Some(Less));
196        assert_eq!(B::new_from(SetUnionHashSet::new_from([0])).partial_cmp(&B::new_from(SetUnionHashSet::new_from([1]))), None);
197
198        assert!(B::new(None).eq(&B::new(None)));
199        assert!(!B::new_from(SetUnionHashSet::new_from([])).eq(&B::new(None)));
200        assert!(!B::new(None).eq(&B::new_from(SetUnionHashSet::new_from([]))));
201        assert!(B::new_from(SetUnionHashSet::new_from([])).eq(&B::new_from(SetUnionHashSet::new_from([]))));
202        assert!(!B::new_from(SetUnionHashSet::new_from([0])).eq(&B::new_from(SetUnionHashSet::new_from([]))));
203        assert!(!B::new_from(SetUnionHashSet::new_from([])).eq(&B::new_from(SetUnionHashSet::new_from([0]))));
204        assert!(!B::new_from(SetUnionHashSet::new_from([0])).eq(&B::new_from(SetUnionHashSet::new_from([1]))));
205    }
206
207    #[test]
208    fn consistency() {
209        let items = &[
210            WithTop::new(None),
211            WithTop::new_from(SetUnionHashSet::new_from([])),
212            WithTop::new_from(SetUnionHashSet::new_from([0])),
213            WithTop::new_from(SetUnionHashSet::new_from([1])),
214            WithTop::new_from(SetUnionHashSet::new_from([0, 1])),
215        ];
216        check_all(items);
217        check_lattice_is_top(items);
218    }
219
220    #[test]
221    fn atomize() {
222        check_atomize_each(&[
223            WithTop::new(None),
224            WithTop::new_from(SetUnionHashSet::new_from([])),
225            WithTop::new_from(SetUnionHashSet::new_from([0])),
226            WithTop::new_from(SetUnionHashSet::new_from([1])),
227            WithTop::new_from(SetUnionHashSet::new_from([0, 1])),
228            WithTop::new_from(SetUnionHashSet::new((0..10).collect())),
229        ]);
230    }
231}
lattices/with_top.rs

lattices/
with_top.rs
