wasmparser/collections/
set.rs

1//! Type definitions for a default set.
2
3use core::{
4    borrow::Borrow,
5    fmt::{self, Debug},
6    hash::Hash,
7    iter::FusedIterator,
8    ops::{BitAnd, BitOr, BitXor, Sub},
9};
10
11#[cfg(not(feature = "no-hash-maps"))]
12mod detail {
13    use crate::collections::hash;
14    use hashbrown::hash_set;
15
16    pub type SetImpl<T> = hash_set::HashSet<T, hash::RandomState>;
17    pub type IterImpl<'a, T> = hash_set::Iter<'a, T>;
18    pub type IntoIterImpl<T> = hash_set::IntoIter<T>;
19    pub type DifferenceImpl<'a, T> = hash_set::Difference<'a, T, hash::RandomState>;
20    pub type IntersectionImpl<'a, T> = hash_set::Intersection<'a, T, hash::RandomState>;
21    pub type SymmetricDifferenceImpl<'a, T> =
22        hash_set::SymmetricDifference<'a, T, hash::RandomState>;
23    pub type UnionImpl<'a, T> = hash_set::Union<'a, T, hash::RandomState>;
24}
25
26#[cfg(feature = "no-hash-maps")]
27mod detail {
28    use alloc::collections::btree_set;
29
30    pub type SetImpl<T> = btree_set::BTreeSet<T>;
31    pub type IterImpl<'a, T> = btree_set::Iter<'a, T>;
32    pub type IntoIterImpl<T> = btree_set::IntoIter<T>;
33    pub type DifferenceImpl<'a, T> = btree_set::Difference<'a, T>;
34    pub type IntersectionImpl<'a, T> = btree_set::Intersection<'a, T>;
35    pub type SymmetricDifferenceImpl<'a, T> = btree_set::SymmetricDifference<'a, T>;
36    pub type UnionImpl<'a, T> = btree_set::Union<'a, T>;
37}
38
39/// A default set of values.
40///
41/// Provides an API compatible with both [`HashSet`] and [`BTreeSet`].
42///
43/// [`HashSet`]: hashbrown::HashSet
44/// [`BTreeSet`]: alloc::collections::BTreeSet
45#[derive(Debug, Clone)]
46pub struct Set<T> {
47    /// The underlying hash-set or btree-set data structure used.
48    inner: detail::SetImpl<T>,
49}
50
51impl<T> Default for Set<T> {
52    #[inline]
53    fn default() -> Self {
54        Self {
55            inner: detail::SetImpl::default(),
56        }
57    }
58}
59
60impl<T> Set<T> {
61    /// Clears the [`Set`], removing all elements.
62    #[inline]
63    pub fn clear(&mut self) {
64        self.inner.clear()
65    }
66
67    /// Retains only the elements specified by the predicate.
68    ///
69    /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
70    /// The elements are visited in unsorted (and unspecified) order.
71    #[inline]
72    pub fn retain<F>(&mut self, f: F)
73    where
74        T: Ord,
75        F: FnMut(&T) -> bool,
76    {
77        self.inner.retain(f)
78    }
79
80    /// Returns the number of elements in the [`Set`].
81    #[inline]
82    pub fn len(&self) -> usize {
83        self.inner.len()
84    }
85
86    /// Returns `true` if the [`Set`] contains no elements.
87    #[inline]
88    pub fn is_empty(&self) -> bool {
89        self.inner.is_empty()
90    }
91
92    /// Returns an iterator that yields the items in the [`Set`].
93    #[inline]
94    pub fn iter(&self) -> Iter<'_, T> {
95        Iter {
96            inner: self.inner.iter(),
97        }
98    }
99}
100
101impl<T> Set<T>
102where
103    T: Eq + Hash + Ord,
104{
105    /// Reserves capacity for at least `additional` more elements to be inserted in the [`Set`].
106    #[inline]
107    pub fn reserve(&mut self, additional: usize) {
108        #[cfg(not(feature = "no-hash-maps"))]
109        self.inner.reserve(additional);
110        #[cfg(feature = "no-hash-maps")]
111        let _ = additional;
112    }
113
114    /// Returns true if the [`Set`] contains an element equal to the `value`.
115    #[inline]
116    pub fn contains<Q>(&self, value: &Q) -> bool
117    where
118        T: Borrow<Q>,
119        Q: ?Sized + Hash + Eq + Ord,
120    {
121        self.inner.contains(value)
122    }
123
124    /// Returns a reference to the element in the [`Set`], if any, that is equal to the `value`.
125    #[inline]
126    pub fn get<Q>(&self, value: &Q) -> Option<&T>
127    where
128        T: Borrow<Q>,
129        Q: ?Sized + Hash + Eq + Ord,
130    {
131        self.inner.get(value)
132    }
133
134    /// Adds `value` to the [`Set`].
135    ///
136    /// Returns whether the value was newly inserted:
137    ///
138    /// - Returns `true` if the set did not previously contain an equal value.
139    /// - Returns `false` otherwise and the entry is not updated.
140    #[inline]
141    pub fn insert(&mut self, value: T) -> bool {
142        self.inner.insert(value)
143    }
144
145    /// If the set contains an element equal to the value, removes it from the [`Set`] and drops it.
146    ///
147    /// Returns `true` if such an element was present, otherwise `false`.
148    #[inline]
149    pub fn remove<Q>(&mut self, value: &Q) -> bool
150    where
151        T: Borrow<Q>,
152        Q: ?Sized + Hash + Eq + Ord,
153    {
154        self.inner.remove(value)
155    }
156
157    /// Removes and returns the element in the [`Set`], if any, that is equal to
158    /// the value.
159    ///
160    /// The value may be any borrowed form of the set's element type,
161    /// but the ordering on the borrowed form *must* match the
162    /// ordering on the element type.
163    #[inline]
164    pub fn take<Q>(&mut self, value: &Q) -> Option<T>
165    where
166        T: Borrow<Q>,
167        Q: ?Sized + Hash + Ord,
168    {
169        self.inner.take(value)
170    }
171
172    /// Adds a value to the [`Set`], replacing the existing value, if any, that is equal to the given
173    /// one. Returns the replaced value.
174    #[inline]
175    pub fn replace(&mut self, value: T) -> Option<T> {
176        self.inner.replace(value)
177    }
178
179    /// Returns `true` if `self` has no elements in common with `other`.
180    /// This is equivalent to checking for an empty intersection.
181    #[inline]
182    pub fn is_disjoint(&self, other: &Self) -> bool {
183        self.inner.is_disjoint(&other.inner)
184    }
185
186    /// Returns `true` if the [`Set`] is a subset of another,
187    /// i.e., `other` contains at least all the values in `self`.
188    #[inline]
189    pub fn is_subset(&self, other: &Self) -> bool {
190        self.inner.is_subset(&other.inner)
191    }
192
193    /// Returns `true` if the [`Set`] is a superset of another,
194    /// i.e., `self` contains at least all the values in `other`.
195    #[inline]
196    pub fn is_superset(&self, other: &Self) -> bool {
197        self.inner.is_superset(&other.inner)
198    }
199
200    /// Visits the values representing the difference,
201    /// i.e., the values that are in `self` but not in `other`.
202    #[inline]
203    pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T> {
204        Difference {
205            inner: self.inner.difference(&other.inner),
206        }
207    }
208
209    /// Visits the values representing the symmetric difference,
210    /// i.e., the values that are in `self` or in `other` but not in both.
211    #[inline]
212    pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, T> {
213        SymmetricDifference {
214            inner: self.inner.symmetric_difference(&other.inner),
215        }
216    }
217
218    /// Visits the values representing the intersection,
219    /// i.e., the values that are both in `self` and `other`.
220    ///
221    /// When an equal element is present in `self` and `other`
222    /// then the resulting `Intersection` may yield references to
223    /// one or the other. This can be relevant if `T` contains fields which
224    /// are not compared by its `Eq` implementation, and may hold different
225    /// value between the two equal copies of `T` in the two sets.
226    #[inline]
227    pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T> {
228        Intersection {
229            inner: self.inner.intersection(&other.inner),
230        }
231    }
232
233    /// Visits the values representing the union,
234    /// i.e., all the values in `self` or `other`, without duplicates.
235    #[inline]
236    pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T> {
237        Union {
238            inner: self.inner.union(&other.inner),
239        }
240    }
241}
242
243impl<T> PartialEq for Set<T>
244where
245    T: Eq + Hash,
246{
247    #[inline]
248    fn eq(&self, other: &Self) -> bool {
249        self.inner == other.inner
250    }
251}
252
253impl<T> Eq for Set<T> where T: Eq + Hash {}
254
255impl<T> FromIterator<T> for Set<T>
256where
257    T: Hash + Eq + Ord,
258{
259    #[inline]
260    fn from_iter<I>(iter: I) -> Self
261    where
262        I: IntoIterator<Item = T>,
263    {
264        Self {
265            inner: <detail::SetImpl<T>>::from_iter(iter),
266        }
267    }
268}
269
270impl<'a, T> IntoIterator for &'a Set<T> {
271    type Item = &'a T;
272    type IntoIter = Iter<'a, T>;
273
274    #[inline]
275    fn into_iter(self) -> Self::IntoIter {
276        self.iter()
277    }
278}
279
280impl<'a, T> Extend<&'a T> for Set<T>
281where
282    T: Hash + Eq + Ord + Copy + 'a,
283{
284    #[inline]
285    fn extend<Iter: IntoIterator<Item = &'a T>>(&mut self, iter: Iter) {
286        self.inner.extend(iter)
287    }
288}
289
290impl<T> Extend<T> for Set<T>
291where
292    T: Hash + Eq + Ord,
293{
294    #[inline]
295    fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
296        self.inner.extend(iter)
297    }
298}
299
300impl<'a, T> BitAnd<Self> for &'a Set<T>
301where
302    T: Eq + Hash + Ord + Clone + 'a,
303{
304    type Output = Set<T>;
305
306    #[inline]
307    fn bitand(self, rhs: Self) -> Set<T> {
308        Set {
309            inner: BitAnd::bitand(&self.inner, &rhs.inner),
310        }
311    }
312}
313
314impl<'a, T> BitOr<Self> for &'a Set<T>
315where
316    T: Eq + Hash + Ord + Clone + 'a,
317{
318    type Output = Set<T>;
319
320    #[inline]
321    fn bitor(self, rhs: Self) -> Set<T> {
322        Set {
323            inner: BitOr::bitor(&self.inner, &rhs.inner),
324        }
325    }
326}
327
328impl<'a, T> BitXor<Self> for &'a Set<T>
329where
330    T: Eq + Hash + Ord + Clone + 'a,
331{
332    type Output = Set<T>;
333
334    #[inline]
335    fn bitxor(self, rhs: Self) -> Set<T> {
336        Set {
337            inner: BitXor::bitxor(&self.inner, &rhs.inner),
338        }
339    }
340}
341
342impl<'a, T> Sub<Self> for &'a Set<T>
343where
344    T: Eq + Hash + Ord + Clone + 'a,
345{
346    type Output = Set<T>;
347
348    #[inline]
349    fn sub(self, rhs: Self) -> Set<T> {
350        Set {
351            inner: Sub::sub(&self.inner, &rhs.inner),
352        }
353    }
354}
355
356/// An iterator over the items of a [`Set`].
357#[derive(Debug, Clone)]
358pub struct Iter<'a, T> {
359    inner: detail::IterImpl<'a, T>,
360}
361
362impl<'a, T: 'a> Iterator for Iter<'a, T> {
363    type Item = &'a T;
364
365    #[inline]
366    fn size_hint(&self) -> (usize, Option<usize>) {
367        self.inner.size_hint()
368    }
369
370    #[inline]
371    fn next(&mut self) -> Option<Self::Item> {
372        self.inner.next()
373    }
374}
375
376impl<'a, T: 'a> ExactSizeIterator for Iter<'a, T> {
377    #[inline]
378    fn len(&self) -> usize {
379        self.inner.len()
380    }
381}
382
383impl<'a, T: 'a> FusedIterator for Iter<'a, T> where detail::IterImpl<'a, T>: FusedIterator {}
384
385impl<T> IntoIterator for Set<T> {
386    type Item = T;
387    type IntoIter = IntoIter<T>;
388
389    #[inline]
390    fn into_iter(self) -> Self::IntoIter {
391        IntoIter {
392            inner: self.inner.into_iter(),
393        }
394    }
395}
396
397/// An iterator over the owned items of an [`Set`].
398#[derive(Debug)]
399pub struct IntoIter<T> {
400    inner: detail::IntoIterImpl<T>,
401}
402
403impl<T> Iterator for IntoIter<T> {
404    type Item = T;
405
406    #[inline]
407    fn size_hint(&self) -> (usize, Option<usize>) {
408        self.inner.size_hint()
409    }
410
411    #[inline]
412    fn next(&mut self) -> Option<Self::Item> {
413        self.inner.next()
414    }
415}
416
417impl<T> ExactSizeIterator for IntoIter<T> {
418    #[inline]
419    fn len(&self) -> usize {
420        self.inner.len()
421    }
422}
423
424impl<T> FusedIterator for IntoIter<T> where detail::IntoIterImpl<T>: FusedIterator {}
425
426/// A lazy iterator producing elements in the difference of [`Set`]s.
427///
428/// This `struct` is created by the [`difference`] method on [`Set`].
429/// See its documentation for more.
430///
431/// [`difference`]: Set::difference
432pub struct Difference<'a, T: 'a> {
433    inner: detail::DifferenceImpl<'a, T>,
434}
435
436impl<T> Debug for Difference<'_, T>
437where
438    T: Debug + Hash + Eq,
439{
440    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
441        self.inner.fmt(f)
442    }
443}
444
445impl<T> Clone for Difference<'_, T> {
446    #[inline]
447    fn clone(&self) -> Self {
448        Self {
449            inner: self.inner.clone(),
450        }
451    }
452}
453
454impl<'a, T> Iterator for Difference<'a, T>
455where
456    T: Hash + Eq + Ord,
457{
458    type Item = &'a T;
459
460    #[inline]
461    fn next(&mut self) -> Option<Self::Item> {
462        self.inner.next()
463    }
464
465    #[inline]
466    fn size_hint(&self) -> (usize, Option<usize>) {
467        self.inner.size_hint()
468    }
469}
470
471impl<'a, T> FusedIterator for Difference<'a, T>
472where
473    T: Hash + Eq + Ord,
474    detail::DifferenceImpl<'a, T>: FusedIterator,
475{
476}
477
478/// A lazy iterator producing elements in the intersection of [`Set`]s.
479///
480/// This `struct` is created by the [`intersection`] method on [`Set`].
481/// See its documentation for more.
482///
483/// [`intersection`]: Set::intersection
484pub struct Intersection<'a, T: 'a> {
485    inner: detail::IntersectionImpl<'a, T>,
486}
487
488impl<T> Debug for Intersection<'_, T>
489where
490    T: Debug + Hash + Eq,
491{
492    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
493        self.inner.fmt(f)
494    }
495}
496
497impl<T> Clone for Intersection<'_, T> {
498    #[inline]
499    fn clone(&self) -> Self {
500        Self {
501            inner: self.inner.clone(),
502        }
503    }
504}
505
506impl<'a, T> Iterator for Intersection<'a, T>
507where
508    T: Hash + Eq + Ord,
509{
510    type Item = &'a T;
511
512    #[inline]
513    fn next(&mut self) -> Option<Self::Item> {
514        self.inner.next()
515    }
516
517    #[inline]
518    fn size_hint(&self) -> (usize, Option<usize>) {
519        self.inner.size_hint()
520    }
521}
522
523impl<'a, T> FusedIterator for Intersection<'a, T>
524where
525    T: Hash + Eq + Ord,
526    detail::IntersectionImpl<'a, T>: FusedIterator,
527{
528}
529
530/// A lazy iterator producing elements in the symmetric difference of [`Set`]s.
531///
532/// This `struct` is created by the [`symmetric_difference`] method on
533/// [`Set`]. See its documentation for more.
534///
535/// [`symmetric_difference`]: Set::symmetric_difference
536pub struct SymmetricDifference<'a, T: 'a> {
537    inner: detail::SymmetricDifferenceImpl<'a, T>,
538}
539
540impl<T> Debug for SymmetricDifference<'_, T>
541where
542    T: Debug + Hash + Eq,
543{
544    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
545        self.inner.fmt(f)
546    }
547}
548
549impl<T> Clone for SymmetricDifference<'_, T> {
550    #[inline]
551    fn clone(&self) -> Self {
552        Self {
553            inner: self.inner.clone(),
554        }
555    }
556}
557
558impl<'a, T> Iterator for SymmetricDifference<'a, T>
559where
560    T: Hash + Eq + Ord,
561{
562    type Item = &'a T;
563
564    #[inline]
565    fn next(&mut self) -> Option<Self::Item> {
566        self.inner.next()
567    }
568
569    #[inline]
570    fn size_hint(&self) -> (usize, Option<usize>) {
571        self.inner.size_hint()
572    }
573}
574
575impl<'a, T> FusedIterator for SymmetricDifference<'a, T>
576where
577    T: Hash + Eq + Ord,
578    detail::SymmetricDifferenceImpl<'a, T>: FusedIterator,
579{
580}
581
582/// A lazy iterator producing elements in the union of [`Set`]s.
583///
584/// This `struct` is created by the [`union`] method on
585/// [`Set`]. See its documentation for more.
586///
587/// [`union`]: Set::union
588pub struct Union<'a, T: 'a> {
589    inner: detail::UnionImpl<'a, T>,
590}
591
592impl<T> Debug for Union<'_, T>
593where
594    T: Debug + Hash + Eq,
595{
596    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
597        self.inner.fmt(f)
598    }
599}
600
601impl<T> Clone for Union<'_, T> {
602    #[inline]
603    fn clone(&self) -> Self {
604        Self {
605            inner: self.inner.clone(),
606        }
607    }
608}
609
610impl<'a, T> Iterator for Union<'a, T>
611where
612    T: Hash + Eq + Ord,
613{
614    type Item = &'a T;
615
616    #[inline]
617    fn next(&mut self) -> Option<Self::Item> {
618        self.inner.next()
619    }
620
621    #[inline]
622    fn size_hint(&self) -> (usize, Option<usize>) {
623        self.inner.size_hint()
624    }
625}
626
627impl<'a, T> FusedIterator for Union<'a, T>
628where
629    T: Hash + Eq + Ord,
630    detail::UnionImpl<'a, T>: FusedIterator,
631{
632}
633
634#[cfg(feature = "serde")]
635impl<T> serde::Serialize for Set<T>
636where
637    T: serde::Serialize + Eq + Hash + Ord,
638{
639    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
640    where
641        S: serde::ser::Serializer,
642    {
643        serde::Serialize::serialize(&self.inner, serializer)
644    }
645}
646
647#[cfg(feature = "serde")]
648impl<'a, T> serde::Deserialize<'a> for Set<T>
649where
650    T: serde::Deserialize<'a> + Eq + Hash + Ord,
651{
652    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
653    where
654        D: serde::de::Deserializer<'a>,
655    {
656        Ok(Set {
657            inner: serde::Deserialize::deserialize(deserializer)?,
658        })
659    }
660}
wasmparser/collections/set.rs

wasmparser/collections/
set.rs
