lattices/
with_top.rs

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

lattices/
with_top.rs
