teleparse/syntax/
lit_set.rs

1use std::collections::BTreeSet;
2
3use derivative::Derivative;
4
5/// A set of literal constants
6#[derive(Derivative, Clone, PartialEq)]
7#[derivative(Default(new = "true"))]
8#[cfg_attr(feature = "serde", derive(serde::Serialize))]
9#[cfg_attr(feature = "serde", serde(tag = "type", content = "set"))]
10pub enum LitSet {
11    /// A finite set
12    #[derivative(Default)]
13    Match(BTreeSet<&'static str>),
14    /// Universal set
15    Any,
16}
17
18impl std::fmt::Debug for LitSet {
19    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
20        match self {
21            Self::Match(set) => write!(f, "{set:?}"),
22            Self::Any => write!(f, "*"),
23        }
24    }
25}
26
27impl<T: IntoIterator<Item = &'static str>> From<T> for LitSet {
28    #[inline]
29    fn from(set: T) -> Self {
30        Self::Match(set.into_iter().collect())
31    }
32}
33
34impl LitSet {
35    /// Create the universal set `U` that contains all literals
36    #[inline]
37    pub fn universe() -> Self {
38        Self::Any
39    }
40
41    /// Check if this set is the universal set `U`
42    #[inline]
43    pub fn is_universe(&self) -> bool {
44        matches!(self, Self::Any)
45    }
46
47    /// Clear the set
48    #[inline]
49    pub fn clear(&mut self) {
50        match self {
51            Self::Match(set) => set.clear(),
52            Self::Any => {}
53        }
54    }
55
56    /// Check if the set is empty
57    #[inline]
58    pub fn is_empty(&self) -> bool {
59        match self {
60            Self::Match(set) => set.is_empty(),
61            Self::Any => false,
62        }
63    }
64
65    /// Insert a literal constants into the set
66    ///
67    /// Returns if the set is changed (i.e. not already containing the literal)
68    #[inline]
69    pub fn insert(&mut self, lit: &'static str) -> bool {
70        match self {
71            Self::Match(set) => set.insert(lit),
72            Self::Any => false,
73        }
74    }
75
76    /// Check if the set contains a literal constant
77    #[inline]
78    pub fn contains(&self, lit: &str) -> bool {
79        match self {
80            Self::Match(set) => set.contains(lit),
81            Self::Any => true,
82        }
83    }
84
85    /// Union this set with the universal set `U` to make self the universal set.
86    ///
87    /// Returns if the set is changed (i.e. not already equal to `U`)
88    #[inline]
89    pub fn union_universe(&mut self) -> bool {
90        match self {
91            Self::Match(_) => {
92                *self = Self::Any;
93                true
94            }
95            Self::Any => false,
96        }
97    }
98
99    /// Union other into self (self = self U other). Return if self is changed
100    pub fn union(&mut self, other: &Self) -> bool {
101        match (self, other) {
102            (Self::Match(set), Self::Match(other_set)) => {
103                let old_size = set.len();
104                set.extend(other_set.iter());
105                old_size != set.len()
106            }
107            (s, _) => {
108                let is_self_any = matches!(s, Self::Any);
109                *s = Self::Any;
110                !is_self_any
111            }
112        }
113    }
114
115    /// Test if this set intersects with another set
116    pub fn intersects(&self, other: &Self) -> bool {
117        match (self, other) {
118            (Self::Match(set), Self::Match(other_set)) => {
119                set.intersection(other_set).next().is_some()
120            }
121            (Self::Any, s) | (s, Self::Any) => !s.is_empty(),
122        }
123    }
124
125    /// Create a new set containing the intersection of this set and another set
126    pub fn intersection(&self, other: &Self) -> Self {
127        match (self, other) {
128            (Self::Match(set), Self::Match(other_set)) => {
129                Self::Match(set.intersection(other_set).copied().collect())
130            }
131            (Self::Any, Self::Any) => Self::Any,
132            (Self::Any, s) | (s, Self::Any) => s.clone(),
133        }
134    }
135
136    /// Get an iterator over the literals in the set
137    ///
138    /// If the set is the universal set `U`, `None` is returned since the set has infinite size
139    pub fn iter(&self) -> Option<impl Iterator<Item = &&'static str>> {
140        match self {
141            Self::Match(set) => Some(set.iter()),
142            Self::Any => None,
143        }
144    }
145}
146
147#[cfg(test)]
148mod tests {
149    use super::*;
150    #[test]
151    fn universe_contains_everything() {
152        let set = LitSet::universe();
153        assert!(set.contains(""));
154        assert!(set.contains("a"));
155        assert!(set.contains("b"));
156        assert!(set.contains("c"));
157    }
158
159    #[test]
160    fn contains_static() {
161        let mut set = LitSet::new();
162        set.insert("a");
163        assert!(set.contains("a"));
164    }
165
166    #[test]
167    fn contains_static_not() {
168        let mut set = LitSet::new();
169        set.insert("a");
170        assert!(!set.contains("b"));
171    }
172
173    #[test]
174    fn contains_dynamic() {
175        let a = "a";
176        let b = "a".to_string();
177        assert!(!std::ptr::eq(a, b.as_str()));
178        let mut set = LitSet::new();
179        set.insert(a);
180        assert!(set.contains(&b));
181    }
182
183    #[test]
184    fn union_universe_from_empty() {
185        let mut set = LitSet::new();
186        assert!(set.union_universe());
187        assert_eq!(set, LitSet::universe());
188    }
189
190    #[test]
191    fn union_universe_from_some() {
192        let mut set = LitSet::from(["a"]);
193        assert!(set.union_universe());
194        assert_eq!(set, LitSet::universe());
195    }
196
197    #[test]
198    fn union_universe_from_universe() {
199        let mut set = LitSet::universe();
200        assert!(!set.union_universe());
201        assert_eq!(set, LitSet::universe());
202    }
203
204    #[test]
205    fn union() {
206        let mut set1 = LitSet::from(["a", "b"]);
207        let set2 = LitSet::from(["b", "c"]);
208        let expected = LitSet::from(["a", "b", "c"]);
209        assert!(set1.union(&set2));
210        assert_eq!(set1, expected);
211    }
212
213    #[test]
214    fn union_no_change_empty() {
215        let mut set1 = LitSet::from(["a", "b"]);
216        let set2 = LitSet::new();
217        assert!(!set1.union(&set2));
218    }
219
220    #[test]
221    fn union_no_change_subset() {
222        let mut set1 = LitSet::from(["a", "b"]);
223        let set2 = LitSet::from(["a"]);
224        assert!(!set1.union(&set2));
225    }
226
227    #[test]
228    fn union_no_change_equal() {
229        let mut set1 = LitSet::from(["a", "b"]);
230        let set2 = set1.clone();
231        assert!(!set1.union(&set2));
232    }
233
234    #[test]
235    fn union_disjoint() {
236        let mut set1 = LitSet::from(["a", "b"]);
237        let set2 = LitSet::from(["d", "c"]);
238        let expected = LitSet::from(["a", "b", "c", "d"]);
239        assert!(set1.union(&set2));
240        assert_eq!(set1, expected);
241    }
242
243    #[test]
244    #[allow(clippy::bool_assert_comparison)] //it's clearer
245    fn intersect_empty_universe() {
246        let set1 = LitSet::new();
247        let set2 = LitSet::universe();
248        assert_eq!(set1.intersects(&set1), false);
249        assert_eq!(set1.intersects(&set2), false);
250        assert_eq!(set2.intersects(&set1), false);
251        assert_eq!(set2.intersects(&set2), true);
252    }
253
254    #[test]
255    fn intersect_universe() {
256        let u = LitSet::universe();
257        let set = LitSet::from(["a", "b"]);
258
259        assert!(u.intersects(&set));
260        assert!(set.intersects(&u));
261        assert_eq!(u.intersection(&set), set);
262        assert_eq!(set.intersection(&u), set);
263    }
264
265    #[test]
266    fn intersect_disjoint() {
267        let set1 = LitSet::from(["a", "b"]);
268        let set2 = LitSet::from(["c", "d"]);
269        assert!(!set1.intersects(&set2));
270        assert!(!set2.intersects(&set1));
271        assert_eq!(set2.intersection(&set1), LitSet::new());
272        assert_eq!(set1.intersection(&set2), LitSet::new());
273    }
274
275    #[test]
276    fn intersect_subset() {
277        let set1 = LitSet::from(["a", "b"]);
278        let set2 = LitSet::from(["a"]);
279        assert!(set1.intersects(&set2));
280        assert!(set2.intersects(&set1));
281        assert_eq!(set2.intersection(&set1), set2);
282        assert_eq!(set1.intersection(&set2), set2);
283    }
284
285    #[test]
286    fn intersect_empty() {
287        let set1 = LitSet::from(["a", "b"]);
288        let set2 = LitSet::new();
289        assert!(!set1.intersects(&set2));
290        assert!(!set2.intersects(&set1));
291        assert_eq!(set2.intersection(&set1), set2);
292        assert_eq!(set1.intersection(&set2), set2);
293    }
294
295    #[test]
296    fn intersection() {
297        let set1 = LitSet::from(["a", "b", "c"]);
298        let set2 = LitSet::from(["a", "c", "d"]);
299        let expected = LitSet::from(["a", "c"]);
300        assert_eq!(set1.intersection(&set2), expected);
301        assert_eq!(set2.intersection(&set1), expected);
302    }
303}
teleparse/syntax/lit_set.rs

teleparse/syntax/
lit_set.rs
