lattices/
with_bot.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 "bot" value to the nested lattice type.
8///
9/// Given an existing lattice, wrap it into a new lattice with a new bottom element. The new bottom
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 bottom element.
14#[repr(transparent)]
15#[derive(Copy, Clone, Debug)]
16#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
17pub struct WithBot<Inner>(Option<Inner>);
18impl<Inner> WithBot<Inner> {
19    /// Create a new `WithBot` lattice instance from a value.
20    pub fn new(val: Option<Inner>) -> Self {
21        Self(val)
22    }
23
24    /// Create a new `WithBot` 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// Cannot auto derive because the generated implementation has the wrong trait bounds.
46// https://github.com/rust-lang/rust/issues/26925
47impl<Inner> Default for WithBot<Inner> {
48    fn default() -> Self {
49        Self(None)
50    }
51}
52
53impl<Inner> DeepReveal for WithBot<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<WithBot<Other>> for WithBot<Inner>
65where
66    Inner: Merge<Other> + LatticeFrom<Other>,
67    Other: IsBot,
68{
69    fn merge(&mut self, other: WithBot<Other>) -> bool {
70        match (&mut self.0, other.0) {
71            (this @ None, Some(other_inner)) if !other_inner.is_bot() => {
72                *this = Some(LatticeFrom::lattice_from(other_inner));
73                true
74            }
75            (Some(self_inner), Some(other_inner)) => self_inner.merge(other_inner),
76            (_self, _none_or_bot) => false,
77        }
78    }
79}
80
81impl<Inner, Other> LatticeFrom<WithBot<Other>> for WithBot<Inner>
82where
83    Inner: LatticeFrom<Other>,
84{
85    fn lattice_from(other: WithBot<Other>) -> Self {
86        Self(other.0.map(Inner::lattice_from))
87    }
88}
89
90impl<Inner, Other> PartialOrd<WithBot<Other>> for WithBot<Inner>
91where
92    Inner: PartialOrd<Other> + IsBot,
93    Other: IsBot,
94{
95    fn partial_cmp(&self, other: &WithBot<Other>) -> Option<Ordering> {
96        match (&self.0, &other.0) {
97            (None, None) => Some(Equal),
98            (None, Some(bot)) if bot.is_bot() => Some(Equal),
99            (Some(bot), None) if bot.is_bot() => Some(Equal),
100            (None, Some(_)) => Some(Less),
101            (Some(_), None) => Some(Greater),
102            (Some(this_inner), Some(other_inner)) => this_inner.partial_cmp(other_inner),
103        }
104    }
105}
106impl<Inner, Other> LatticeOrd<WithBot<Other>> for WithBot<Inner> where
107    Self: PartialOrd<WithBot<Other>>
108{
109}
110
111impl<Inner, Other> PartialEq<WithBot<Other>> for WithBot<Inner>
112where
113    Inner: PartialEq<Other> + IsBot,
114    Other: IsBot,
115{
116    fn eq(&self, other: &WithBot<Other>) -> bool {
117        match (&self.0, &other.0) {
118            (None, None) => true,
119            (None, Some(bot)) if bot.is_bot() => true,
120            (Some(bot), None) if bot.is_bot() => true,
121            (None, Some(_)) => false,
122            (Some(_), None) => false,
123            (Some(this_inner), Some(other_inner)) => this_inner == other_inner,
124        }
125    }
126}
127impl<Inner> Eq for WithBot<Inner> where Self: PartialEq {}
128
129impl<Inner> IsBot for WithBot<Inner>
130where
131    Inner: IsBot,
132{
133    fn is_bot(&self) -> bool {
134        self.0.as_ref().is_none_or(IsBot::is_bot)
135    }
136}
137
138impl<Inner> IsTop for WithBot<Inner>
139where
140    Inner: IsTop,
141{
142    fn is_top(&self) -> bool {
143        self.0.as_ref().is_some_and(IsTop::is_top)
144    }
145}
146
147#[cfg(feature = "alloc")]
148impl<Inner> Atomize for WithBot<Inner>
149where
150    Inner: 'static + Atomize + LatticeFrom<<Inner as Atomize>::Atom>,
151{
152    type Atom = WithBot<Inner::Atom>;
153
154    // TODO: use impl trait, then remove 'static.
155    type AtomIter = alloc::boxed::Box<dyn Iterator<Item = Self::Atom>>;
156
157    fn atomize(self) -> Self::AtomIter {
158        alloc::boxed::Box::new(
159            self.0
160                .into_iter()
161                .flat_map(Atomize::atomize)
162                .map(WithBot::new_from),
163        )
164    }
165}
166
167#[cfg(test)]
168mod test {
169    use super::*;
170    use crate::set_union::{SetUnionHashSet, SetUnionSingletonSet};
171    use crate::test::{check_all, check_atomize_each};
172
173    #[test]
174    fn test_singly_nested_singleton_example() {
175        let mut my_hash_set = WithBot::new_from(SetUnionHashSet::<&str>::default());
176        let my_delta_set = WithBot::new_from(SetUnionSingletonSet::new_from("hello world"));
177
178        assert!(my_hash_set.merge(my_delta_set)); // Changes
179        assert!(!my_hash_set.merge(my_delta_set)); // No changes
180    }
181
182    #[test]
183    fn test_doubly_nested_singleton_example() {
184        let mut my_hash_set =
185            WithBot::new_from(WithBot::new_from(SetUnionHashSet::<&str>::default()));
186        let my_delta_set = WithBot::new_from(WithBot::new_from(SetUnionSingletonSet::new_from(
187            "hello world",
188        )));
189
190        assert!(my_hash_set.merge(my_delta_set)); // Changes
191        assert!(!my_hash_set.merge(my_delta_set)); // No changes
192    }
193
194    #[test]
195    #[rustfmt::skip]
196    fn auto_derives() {
197        type B = WithBot<SetUnionHashSet<usize>>;
198
199        assert_eq!(B::default().partial_cmp(&B::default()), Some(Equal));
200
201        // Test bot collapsing - `WithBot(Some(Bot))` equals `WithBot(None)`.
202        assert_eq!(B::new_from(SetUnionHashSet::new_from([])).partial_cmp(&B::default()), Some(Equal));
203        assert_eq!(B::default().partial_cmp(&B::new_from(SetUnionHashSet::new_from([]))), Some(Equal));
204        assert!(B::new_from(SetUnionHashSet::new_from([])).eq(&B::default()));
205        assert!(B::default().eq(&B::new_from(SetUnionHashSet::new_from([]))));
206
207        // PartialOrd
208        assert_eq!(B::new_from(SetUnionHashSet::new_from([])).partial_cmp(&B::new_from(SetUnionHashSet::new_from([]))), Some(Equal));
209        assert_eq!(B::new_from(SetUnionHashSet::new_from([0])).partial_cmp(&B::new_from(SetUnionHashSet::new_from([]))), Some(Greater));
210        assert_eq!(B::new_from(SetUnionHashSet::new_from([])).partial_cmp(&B::new_from(SetUnionHashSet::new_from([0]))), Some(Less));
211        assert_eq!(B::new_from(SetUnionHashSet::new_from([0])).partial_cmp(&B::new_from(SetUnionHashSet::new_from([1]))), None);
212
213        // PartialEq
214        assert!(B::default().eq(&B::default()));
215        assert!(B::new_from(SetUnionHashSet::new_from([])).eq(&B::new_from(SetUnionHashSet::new_from([]))));
216        assert!(!B::new_from(SetUnionHashSet::new_from([0])).eq(&B::new_from(SetUnionHashSet::new_from([]))));
217        assert!(!B::new_from(SetUnionHashSet::new_from([])).eq(&B::new_from(SetUnionHashSet::new_from([0]))));
218        assert!(!B::new_from(SetUnionHashSet::new_from([0])).eq(&B::new_from(SetUnionHashSet::new_from([1]))));
219    }
220
221    #[test]
222    fn consistency() {
223        check_all(&[
224            WithBot::default(),
225            WithBot::new_from(SetUnionHashSet::new_from([])),
226            WithBot::new_from(SetUnionHashSet::new_from([0])),
227            WithBot::new_from(SetUnionHashSet::new_from([1])),
228            WithBot::new_from(SetUnionHashSet::new_from([0, 1])),
229        ])
230    }
231
232    #[test]
233    fn atomize() {
234        check_atomize_each(&[
235            WithBot::default(),
236            WithBot::new_from(SetUnionHashSet::new_from([])),
237            WithBot::new_from(SetUnionHashSet::new_from([0])),
238            WithBot::new_from(SetUnionHashSet::new_from([1])),
239            WithBot::new_from(SetUnionHashSet::new_from([0, 1])),
240            WithBot::new_from(SetUnionHashSet::new((0..10).collect())),
241        ]);
242    }
243}
lattices/with_bot.rs

lattices/
with_bot.rs
