lattices/
with_top.rs

Help
1use std::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
140impl<Inner> Atomize for WithTop<Inner>
141where
142    Inner: Atomize + LatticeFrom<<Inner as Atomize>::Atom>,
143{
144    type Atom = WithTop<Inner::Atom>;
145
146    // TODO: use impl trait, then remove 'static.
147    type AtomIter = Box<dyn Iterator<Item = Self::Atom>>;
148
149    fn atomize(self) -> Self::AtomIter {
150        match self.0 {
151            Some(inner) => Box::new(inner.atomize().map(WithTop::new_from)),
152            None => Box::new(std::iter::once(WithTop::new(None))),
153        }
154    }
155}
156
157#[cfg(test)]
158mod test {
159    use super::*;
160    use crate::set_union::{SetUnionHashSet, SetUnionSingletonSet};
161    use crate::test::{check_all, check_atomize_each, check_lattice_is_top};
162
163    #[test]
164    fn test_singly_nested_singleton_example() {
165        let mut my_hash_set = WithTop::new_from(SetUnionHashSet::<&str>::default());
166        let my_delta_set = WithTop::new_from(SetUnionSingletonSet::new_from("hello world"));
167
168        assert!(my_hash_set.merge(my_delta_set)); // Changes
169        assert!(!my_hash_set.merge(my_delta_set)); // No changes
170    }
171
172    #[test]
173    fn test_doubly_nested_singleton_example() {
174        let mut my_hash_set =
175            WithTop::new_from(WithTop::new_from(SetUnionHashSet::<&str>::default()));
176        let my_delta_set = WithTop::new_from(WithTop::new_from(SetUnionSingletonSet::new_from(
177            "hello world",
178        )));
179
180        assert!(my_hash_set.merge(my_delta_set)); // Changes
181        assert!(!my_hash_set.merge(my_delta_set)); // No changes
182    }
183
184    #[test]
185    #[rustfmt::skip]
186    fn auto_derives() {
187        type B = WithTop<SetUnionHashSet<usize>>;
188
189        assert_eq!(B::new(None).partial_cmp(&B::new(None)), Some(Equal));
190        assert_eq!(B::new_from(SetUnionHashSet::new_from([])).partial_cmp(&B::new(None)), Some(Less));
191        assert_eq!(B::new(None).partial_cmp(&B::new_from(SetUnionHashSet::new_from([]))), Some(Greater));
192        assert_eq!(B::new_from(SetUnionHashSet::new_from([])).partial_cmp(&B::new_from(SetUnionHashSet::new_from([]))), Some(Equal));
193        assert_eq!(B::new_from(SetUnionHashSet::new_from([0])).partial_cmp(&B::new_from(SetUnionHashSet::new_from([]))), Some(Greater));
194        assert_eq!(B::new_from(SetUnionHashSet::new_from([])).partial_cmp(&B::new_from(SetUnionHashSet::new_from([0]))), Some(Less));
195        assert_eq!(B::new_from(SetUnionHashSet::new_from([0])).partial_cmp(&B::new_from(SetUnionHashSet::new_from([1]))), None);
196
197        assert!(B::new(None).eq(&B::new(None)));
198        assert!(!B::new_from(SetUnionHashSet::new_from([])).eq(&B::new(None)));
199        assert!(!B::new(None).eq(&B::new_from(SetUnionHashSet::new_from([]))));
200        assert!(B::new_from(SetUnionHashSet::new_from([])).eq(&B::new_from(SetUnionHashSet::new_from([]))));
201        assert!(!B::new_from(SetUnionHashSet::new_from([0])).eq(&B::new_from(SetUnionHashSet::new_from([]))));
202        assert!(!B::new_from(SetUnionHashSet::new_from([])).eq(&B::new_from(SetUnionHashSet::new_from([0]))));
203        assert!(!B::new_from(SetUnionHashSet::new_from([0])).eq(&B::new_from(SetUnionHashSet::new_from([1]))));
204    }
205
206    #[test]
207    fn consistency() {
208        let items = &[
209            WithTop::new(None),
210            WithTop::new_from(SetUnionHashSet::new_from([])),
211            WithTop::new_from(SetUnionHashSet::new_from([0])),
212            WithTop::new_from(SetUnionHashSet::new_from([1])),
213            WithTop::new_from(SetUnionHashSet::new_from([0, 1])),
214        ];
215        check_all(items);
216        check_lattice_is_top(items);
217    }
218
219    #[test]
220    fn atomize() {
221        check_atomize_each(&[
222            WithTop::new(None),
223            WithTop::new_from(SetUnionHashSet::new_from([])),
224            WithTop::new_from(SetUnionHashSet::new_from([0])),
225            WithTop::new_from(SetUnionHashSet::new_from([1])),
226            WithTop::new_from(SetUnionHashSet::new_from([0, 1])),
227            WithTop::new_from(SetUnionHashSet::new((0..10).collect())),
228        ]);
229    }
230}
lattices/with_top.rs

lattices/
with_top.rs
