lattices/
with_bot.rs

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

lattices/
with_bot.rs
