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

wasmparser/collections/
set.rs
