diff options
Diffstat (limited to '')
| -rw-r--r-- | third_party/rust/hashbrown/src/set.rs | 516 |
1 files changed, 348 insertions, 168 deletions
diff --git a/third_party/rust/hashbrown/src/set.rs b/third_party/rust/hashbrown/src/set.rs index 2a4dcea52c..2125a7ac81 100644 --- a/third_party/rust/hashbrown/src/set.rs +++ b/third_party/rust/hashbrown/src/set.rs @@ -1,14 +1,14 @@ -use crate::TryReserveError; +#[cfg(feature = "raw")] +use crate::raw::RawTable; +use crate::{Equivalent, TryReserveError}; use alloc::borrow::ToOwned; -use core::borrow::Borrow; use core::fmt; use core::hash::{BuildHasher, Hash}; -use core::iter::{Chain, FromIterator, FusedIterator}; -use core::mem; +use core::iter::{Chain, FusedIterator}; use core::ops::{BitAnd, BitOr, BitXor, Sub}; -use super::map::{self, ConsumeAllOnDrop, DefaultHashBuilder, DrainFilterInner, HashMap, Keys}; -use crate::raw::{Allocator, Global}; +use super::map::{self, DefaultHashBuilder, HashMap, Keys}; +use crate::raw::{Allocator, Global, RawExtractIf}; // Future Optimization (FIXME!) // ============================= @@ -102,7 +102,7 @@ use crate::raw::{Allocator, Global}; /// use hashbrown::HashSet; /// /// let viking_names: HashSet<&'static str> = -/// [ "Einar", "Olaf", "Harald" ].iter().cloned().collect(); +/// [ "Einar", "Olaf", "Harald" ].into_iter().collect(); /// // use the values stored in the set /// ``` /// @@ -112,7 +112,7 @@ use crate::raw::{Allocator, Global}; /// [`HashMap`]: struct.HashMap.html /// [`PartialEq`]: https://doc.rust-lang.org/std/cmp/trait.PartialEq.html /// [`RefCell`]: https://doc.rust-lang.org/std/cell/struct.RefCell.html -pub struct HashSet<T, S = DefaultHashBuilder, A: Allocator + Clone = Global> { +pub struct HashSet<T, S = DefaultHashBuilder, A: Allocator = Global> { pub(crate) map: HashMap<T, (), S, A>, } @@ -135,6 +135,18 @@ impl<T> HashSet<T, DefaultHashBuilder> { /// The hash set is initially created with a capacity of 0, so it will not allocate until it /// is first inserted into. /// + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashSet` to be protected against attacks such as [`HashDoS`]. + /// Users who require HashDoS resistance should explicitly use + /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`] + /// as the hasher when creating a [`HashSet`], for example with + /// [`with_hasher`](HashSet::with_hasher) method. + /// + /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack + /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html + /// /// # Examples /// /// ``` @@ -153,6 +165,18 @@ impl<T> HashSet<T, DefaultHashBuilder> { /// The hash set will be able to hold at least `capacity` elements without /// reallocating. If `capacity` is 0, the hash set will not allocate. /// + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashSet` to be protected against attacks such as [`HashDoS`]. + /// Users who require HashDoS resistance should explicitly use + /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`] + /// as the hasher when creating a [`HashSet`], for example with + /// [`with_capacity_and_hasher`](HashSet::with_capacity_and_hasher) method. + /// + /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack + /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html + /// /// # Examples /// /// ``` @@ -169,12 +193,24 @@ impl<T> HashSet<T, DefaultHashBuilder> { } #[cfg(feature = "ahash")] -impl<T: Hash + Eq, A: Allocator + Clone> HashSet<T, DefaultHashBuilder, A> { +impl<T: Hash + Eq, A: Allocator> HashSet<T, DefaultHashBuilder, A> { /// Creates an empty `HashSet`. /// /// The hash set is initially created with a capacity of 0, so it will not allocate until it /// is first inserted into. /// + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashSet` to be protected against attacks such as [`HashDoS`]. + /// Users who require HashDoS resistance should explicitly use + /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`] + /// as the hasher when creating a [`HashSet`], for example with + /// [`with_hasher_in`](HashSet::with_hasher_in) method. + /// + /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack + /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html + /// /// # Examples /// /// ``` @@ -193,6 +229,18 @@ impl<T: Hash + Eq, A: Allocator + Clone> HashSet<T, DefaultHashBuilder, A> { /// The hash set will be able to hold at least `capacity` elements without /// reallocating. If `capacity` is 0, the hash set will not allocate. /// + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashSet` to be protected against attacks such as [`HashDoS`]. + /// Users who require HashDoS resistance should explicitly use + /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`] + /// as the hasher when creating a [`HashSet`], for example with + /// [`with_capacity_and_hasher_in`](HashSet::with_capacity_and_hasher_in) method. + /// + /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack + /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html + /// /// # Examples /// /// ``` @@ -208,7 +256,7 @@ impl<T: Hash + Eq, A: Allocator + Clone> HashSet<T, DefaultHashBuilder, A> { } } -impl<T, S, A: Allocator + Clone> HashSet<T, S, A> { +impl<T, S, A: Allocator> HashSet<T, S, A> { /// Returns the number of elements the set can hold without reallocating. /// /// # Examples @@ -287,7 +335,7 @@ impl<T, S, A: Allocator + Clone> HashSet<T, S, A> { /// ``` /// use hashbrown::HashSet; /// - /// let mut set: HashSet<_> = [1, 2, 3].iter().cloned().collect(); + /// let mut set: HashSet<_> = [1, 2, 3].into_iter().collect(); /// assert!(!set.is_empty()); /// /// // print 1, 2, 3 in an arbitrary order @@ -314,7 +362,7 @@ impl<T, S, A: Allocator + Clone> HashSet<T, S, A> { /// use hashbrown::HashSet; /// /// let xs = [1,2,3,4,5,6]; - /// let mut set: HashSet<i32> = xs.iter().cloned().collect(); + /// let mut set: HashSet<i32> = xs.into_iter().collect(); /// set.retain(|&k| k % 2 == 0); /// assert_eq!(set.len(), 3); /// ``` @@ -331,8 +379,11 @@ impl<T, S, A: Allocator + Clone> HashSet<T, S, A> { /// In other words, move all elements `e` such that `f(&e)` returns `true` out /// into another iterator. /// - /// When the returned DrainedFilter is dropped, any remaining elements that satisfy - /// the predicate are dropped from the set. + /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating + /// or the iteration short-circuits, then the remaining elements will be retained. + /// Use [`retain()`] with a negated predicate if you do not need the returned iterator. + /// + /// [`retain()`]: HashSet::retain /// /// # Examples /// @@ -340,7 +391,7 @@ impl<T, S, A: Allocator + Clone> HashSet<T, S, A> { /// use hashbrown::HashSet; /// /// let mut set: HashSet<i32> = (0..8).collect(); - /// let drained: HashSet<i32> = set.drain_filter(|v| v % 2 == 0).collect(); + /// let drained: HashSet<i32> = set.extract_if(|v| v % 2 == 0).collect(); /// /// let mut evens = drained.into_iter().collect::<Vec<_>>(); /// let mut odds = set.into_iter().collect::<Vec<_>>(); @@ -351,13 +402,13 @@ impl<T, S, A: Allocator + Clone> HashSet<T, S, A> { /// assert_eq!(odds, vec![1, 3, 5, 7]); /// ``` #[cfg_attr(feature = "inline-more", inline)] - pub fn drain_filter<F>(&mut self, f: F) -> DrainFilter<'_, T, F, A> + pub fn extract_if<F>(&mut self, f: F) -> ExtractIf<'_, T, F, A> where F: FnMut(&T) -> bool, { - DrainFilter { + ExtractIf { f, - inner: DrainFilterInner { + inner: RawExtractIf { iter: unsafe { self.map.table.iter() }, table: &mut self.map.table, }, @@ -386,16 +437,23 @@ impl<T, S> HashSet<T, S, Global> { /// Creates a new empty hash set which will use the given hasher to hash /// keys. /// - /// The hash set is also created with the default initial capacity. + /// The hash set is initially created with a capacity of 0, so it will not + /// allocate until it is first inserted into. + /// + /// # HashDoS resistance /// - /// Warning: `hasher` is normally randomly generated, and - /// is designed to allow `HashSet`s to be resistant to attacks that - /// cause many collisions and very poor performance. Setting it - /// manually using this function can expose a DoS attack vector. + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashSet` to be protected against attacks such as [`HashDoS`]. + /// Users who require HashDoS resistance should explicitly use + /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`] + /// as the hasher when creating a [`HashSet`]. /// /// The `hash_builder` passed should implement the [`BuildHasher`] trait for - /// the HashMap to be useful, see its documentation for details. + /// the HashSet to be useful, see its documentation for details. /// + /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack + /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html + /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html /// /// # Examples /// @@ -407,8 +465,6 @@ impl<T, S> HashSet<T, S, Global> { /// let mut set = HashSet::with_hasher(s); /// set.insert(2); /// ``` - /// - /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html #[cfg_attr(feature = "inline-more", inline)] pub const fn with_hasher(hasher: S) -> Self { Self { @@ -422,13 +478,20 @@ impl<T, S> HashSet<T, S, Global> { /// The hash set will be able to hold at least `capacity` elements without /// reallocating. If `capacity` is 0, the hash set will not allocate. /// - /// Warning: `hasher` is normally randomly generated, and - /// is designed to allow `HashSet`s to be resistant to attacks that - /// cause many collisions and very poor performance. Setting it - /// manually using this function can expose a DoS attack vector. + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashSet` to be protected against attacks such as [`HashDoS`]. + /// Users who require HashDoS resistance should explicitly use + /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`] + /// as the hasher when creating a [`HashSet`]. /// /// The `hash_builder` passed should implement the [`BuildHasher`] trait for - /// the HashMap to be useful, see its documentation for details. + /// the HashSet to be useful, see its documentation for details. + /// + /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack + /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html + /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html /// /// # Examples /// @@ -440,8 +503,6 @@ impl<T, S> HashSet<T, S, Global> { /// let mut set = HashSet::with_capacity_and_hasher(10, s); /// set.insert(1); /// ``` - /// - /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html #[cfg_attr(feature = "inline-more", inline)] pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self { Self { @@ -452,7 +513,7 @@ impl<T, S> HashSet<T, S, Global> { impl<T, S, A> HashSet<T, S, A> where - A: Allocator + Clone, + A: Allocator, { /// Returns a reference to the underlying allocator. #[inline] @@ -463,12 +524,23 @@ where /// Creates a new empty hash set which will use the given hasher to hash /// keys. /// - /// The hash set is also created with the default initial capacity. + /// The hash set is initially created with a capacity of 0, so it will not + /// allocate until it is first inserted into. + /// + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashSet` to be protected against attacks such as [`HashDoS`]. + /// Users who require HashDoS resistance should explicitly use + /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`] + /// as the hasher when creating a [`HashSet`]. + /// + /// The `hash_builder` passed should implement the [`BuildHasher`] trait for + /// the HashSet to be useful, see its documentation for details. /// - /// Warning: `hasher` is normally randomly generated, and - /// is designed to allow `HashSet`s to be resistant to attacks that - /// cause many collisions and very poor performance. Setting it - /// manually using this function can expose a DoS attack vector. + /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack + /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html + /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html /// /// # Examples /// @@ -481,7 +553,7 @@ where /// set.insert(2); /// ``` #[cfg_attr(feature = "inline-more", inline)] - pub fn with_hasher_in(hasher: S, alloc: A) -> Self { + pub const fn with_hasher_in(hasher: S, alloc: A) -> Self { Self { map: HashMap::with_hasher_in(hasher, alloc), } @@ -493,10 +565,20 @@ where /// The hash set will be able to hold at least `capacity` elements without /// reallocating. If `capacity` is 0, the hash set will not allocate. /// - /// Warning: `hasher` is normally randomly generated, and - /// is designed to allow `HashSet`s to be resistant to attacks that - /// cause many collisions and very poor performance. Setting it - /// manually using this function can expose a DoS attack vector. + /// # HashDoS resistance + /// + /// The `hash_builder` normally use a fixed key by default and that does + /// not allow the `HashSet` to be protected against attacks such as [`HashDoS`]. + /// Users who require HashDoS resistance should explicitly use + /// [`ahash::RandomState`] or [`std::collections::hash_map::RandomState`] + /// as the hasher when creating a [`HashSet`]. + /// + /// The `hash_builder` passed should implement the [`BuildHasher`] trait for + /// the HashSet to be useful, see its documentation for details. + /// + /// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack + /// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html + /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html /// /// # Examples /// @@ -539,7 +621,7 @@ impl<T, S, A> HashSet<T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { /// Reserves capacity for at least `additional` more elements to be inserted /// in the `HashSet`. The collection may reserve more space to avoid @@ -547,7 +629,12 @@ where /// /// # Panics /// - /// Panics if the new allocation size overflows `usize`. + /// Panics if the new capacity exceeds [`isize::MAX`] bytes and [`abort`] the program + /// in case of allocation error. Use [`try_reserve`](HashSet::try_reserve) instead + /// if you want to handle memory allocation failure. + /// + /// [`isize::MAX`]: https://doc.rust-lang.org/std/primitive.isize.html + /// [`abort`]: https://doc.rust-lang.org/alloc/alloc/fn.handle_alloc_error.html /// /// # Examples /// @@ -637,8 +724,8 @@ where /// /// ``` /// use hashbrown::HashSet; - /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect(); - /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect(); + /// let a: HashSet<_> = [1, 2, 3].into_iter().collect(); + /// let b: HashSet<_> = [4, 2, 3, 4].into_iter().collect(); /// /// // Can be seen as `a - b`. /// for x in a.difference(&b) { @@ -668,8 +755,8 @@ where /// /// ``` /// use hashbrown::HashSet; - /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect(); - /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect(); + /// let a: HashSet<_> = [1, 2, 3].into_iter().collect(); + /// let b: HashSet<_> = [4, 2, 3, 4].into_iter().collect(); /// /// // Print 1, 4 in arbitrary order. /// for x in a.symmetric_difference(&b) { @@ -696,8 +783,8 @@ where /// /// ``` /// use hashbrown::HashSet; - /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect(); - /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect(); + /// let a: HashSet<_> = [1, 2, 3].into_iter().collect(); + /// let b: HashSet<_> = [4, 2, 3, 4].into_iter().collect(); /// /// // Print 2, 3 in arbitrary order. /// for x in a.intersection(&b) { @@ -727,8 +814,8 @@ where /// /// ``` /// use hashbrown::HashSet; - /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect(); - /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect(); + /// let a: HashSet<_> = [1, 2, 3].into_iter().collect(); + /// let b: HashSet<_> = [4, 2, 3, 4].into_iter().collect(); /// /// // Print 1, 2, 3, 4 in arbitrary order. /// for x in a.union(&b) { @@ -763,7 +850,7 @@ where /// ``` /// use hashbrown::HashSet; /// - /// let set: HashSet<_> = [1, 2, 3].iter().cloned().collect(); + /// let set: HashSet<_> = [1, 2, 3].into_iter().collect(); /// assert_eq!(set.contains(&1), true); /// assert_eq!(set.contains(&4), false); /// ``` @@ -773,8 +860,7 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool where - T: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<T>, { self.map.contains_key(value) } @@ -790,7 +876,7 @@ where /// ``` /// use hashbrown::HashSet; /// - /// let set: HashSet<_> = [1, 2, 3].iter().cloned().collect(); + /// let set: HashSet<_> = [1, 2, 3].into_iter().collect(); /// assert_eq!(set.get(&2), Some(&2)); /// assert_eq!(set.get(&4), None); /// ``` @@ -800,8 +886,7 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T> where - T: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<T>, { // Avoid `Option::map` because it bloats LLVM IR. match self.map.get_key_value(value) { @@ -818,7 +903,7 @@ where /// ``` /// use hashbrown::HashSet; /// - /// let mut set: HashSet<_> = [1, 2, 3].iter().cloned().collect(); + /// let mut set: HashSet<_> = [1, 2, 3].into_iter().collect(); /// assert_eq!(set.len(), 3); /// assert_eq!(set.get_or_insert(2), &2); /// assert_eq!(set.get_or_insert(100), &100); @@ -856,8 +941,7 @@ where #[inline] pub fn get_or_insert_owned<Q: ?Sized>(&mut self, value: &Q) -> &T where - T: Borrow<Q>, - Q: Hash + Eq + ToOwned<Owned = T>, + Q: Hash + Equivalent<T> + ToOwned<Owned = T>, { // Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with // `get`. Key mutation is "raw" because you're not supposed to affect `Eq` or `Hash`. @@ -889,8 +973,7 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn get_or_insert_with<Q: ?Sized, F>(&mut self, value: &Q, f: F) -> &T where - T: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<T>, F: FnOnce(&Q) -> T, { // Although the raw entry gives us `&mut T`, we only return `&T` to be consistent with @@ -951,7 +1034,7 @@ where /// ``` /// use hashbrown::HashSet; /// - /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect(); + /// let a: HashSet<_> = [1, 2, 3].into_iter().collect(); /// let mut b = HashSet::new(); /// /// assert_eq!(a.is_disjoint(&b), true); @@ -972,7 +1055,7 @@ where /// ``` /// use hashbrown::HashSet; /// - /// let sup: HashSet<_> = [1, 2, 3].iter().cloned().collect(); + /// let sup: HashSet<_> = [1, 2, 3].into_iter().collect(); /// let mut set = HashSet::new(); /// /// assert_eq!(set.is_subset(&sup), true); @@ -993,7 +1076,7 @@ where /// ``` /// use hashbrown::HashSet; /// - /// let sub: HashSet<_> = [1, 2].iter().cloned().collect(); + /// let sub: HashSet<_> = [1, 2].into_iter().collect(); /// let mut set = HashSet::new(); /// /// assert_eq!(set.is_superset(&sub), false); @@ -1106,8 +1189,7 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool where - T: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<T>, { self.map.remove(value).is_some() } @@ -1123,7 +1205,7 @@ where /// ``` /// use hashbrown::HashSet; /// - /// let mut set: HashSet<_> = [1, 2, 3].iter().cloned().collect(); + /// let mut set: HashSet<_> = [1, 2, 3].into_iter().collect(); /// assert_eq!(set.take(&2), Some(2)); /// assert_eq!(set.take(&2), None); /// ``` @@ -1133,8 +1215,7 @@ where #[cfg_attr(feature = "inline-more", inline)] pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> where - T: Borrow<Q>, - Q: Hash + Eq, + Q: Hash + Equivalent<T>, { // Avoid `Option::map` because it bloats LLVM IR. match self.map.remove_entry(value) { @@ -1144,11 +1225,53 @@ where } } +impl<T, S, A: Allocator> HashSet<T, S, A> { + /// Returns a reference to the [`RawTable`] used underneath [`HashSet`]. + /// This function is only available if the `raw` feature of the crate is enabled. + /// + /// # Note + /// + /// Calling this function is safe, but using the raw hash table API may require + /// unsafe functions or blocks. + /// + /// `RawTable` API gives the lowest level of control under the set that can be useful + /// for extending the HashSet's API, but may lead to *[undefined behavior]*. + /// + /// [`HashSet`]: struct.HashSet.html + /// [`RawTable`]: crate::raw::RawTable + /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html + #[cfg(feature = "raw")] + #[cfg_attr(feature = "inline-more", inline)] + pub fn raw_table(&self) -> &RawTable<(T, ()), A> { + self.map.raw_table() + } + + /// Returns a mutable reference to the [`RawTable`] used underneath [`HashSet`]. + /// This function is only available if the `raw` feature of the crate is enabled. + /// + /// # Note + /// + /// Calling this function is safe, but using the raw hash table API may require + /// unsafe functions or blocks. + /// + /// `RawTable` API gives the lowest level of control under the set that can be useful + /// for extending the HashSet's API, but may lead to *[undefined behavior]*. + /// + /// [`HashSet`]: struct.HashSet.html + /// [`RawTable`]: crate::raw::RawTable + /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html + #[cfg(feature = "raw")] + #[cfg_attr(feature = "inline-more", inline)] + pub fn raw_table_mut(&mut self) -> &mut RawTable<(T, ()), A> { + self.map.raw_table_mut() + } +} + impl<T, S, A> PartialEq for HashSet<T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { fn eq(&self, other: &Self) -> bool { if self.len() != other.len() { @@ -1163,14 +1286,14 @@ impl<T, S, A> Eq for HashSet<T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { } impl<T, S, A> fmt::Debug for HashSet<T, S, A> where T: fmt::Debug, - A: Allocator + Clone, + A: Allocator, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_set().entries(self.iter()).finish() @@ -1179,7 +1302,7 @@ where impl<T, S, A> From<HashMap<T, (), S, A>> for HashSet<T, S, A> where - A: Allocator + Clone, + A: Allocator, { fn from(map: HashMap<T, (), S, A>) -> Self { Self { map } @@ -1190,7 +1313,7 @@ impl<T, S, A> FromIterator<T> for HashSet<T, S, A> where T: Eq + Hash, S: BuildHasher + Default, - A: Default + Allocator + Clone, + A: Default + Allocator, { #[cfg_attr(feature = "inline-more", inline)] fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { @@ -1205,7 +1328,7 @@ where impl<T, A, const N: usize> From<[T; N]> for HashSet<T, DefaultHashBuilder, A> where T: Eq + Hash, - A: Default + Allocator + Clone, + A: Default + Allocator, { /// # Examples /// @@ -1225,7 +1348,7 @@ impl<T, S, A> Extend<T> for HashSet<T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { #[cfg_attr(feature = "inline-more", inline)] fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { @@ -1249,7 +1372,7 @@ impl<'a, T, S, A> Extend<&'a T> for HashSet<T, S, A> where T: 'a + Eq + Hash + Copy, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { #[cfg_attr(feature = "inline-more", inline)] fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { @@ -1272,7 +1395,7 @@ where impl<T, S, A> Default for HashSet<T, S, A> where S: Default, - A: Default + Allocator + Clone, + A: Default + Allocator, { /// Creates an empty `HashSet<T, S>` with the `Default` value for the hasher. #[cfg_attr(feature = "inline-more", inline)] @@ -1287,7 +1410,7 @@ impl<T, S, A> BitOr<&HashSet<T, S, A>> for &HashSet<T, S, A> where T: Eq + Hash + Clone, S: BuildHasher + Default, - A: Allocator + Clone, + A: Allocator, { type Output = HashSet<T, S>; @@ -1320,7 +1443,7 @@ impl<T, S, A> BitAnd<&HashSet<T, S, A>> for &HashSet<T, S, A> where T: Eq + Hash + Clone, S: BuildHasher + Default, - A: Allocator + Clone, + A: Allocator, { type Output = HashSet<T, S>; @@ -1431,7 +1554,7 @@ pub struct Iter<'a, K> { /// /// [`HashSet`]: struct.HashSet.html /// [`into_iter`]: struct.HashSet.html#method.into_iter -pub struct IntoIter<K, A: Allocator + Clone = Global> { +pub struct IntoIter<K, A: Allocator = Global> { iter: map::IntoIter<K, (), A>, } @@ -1442,23 +1565,24 @@ pub struct IntoIter<K, A: Allocator + Clone = Global> { /// /// [`HashSet`]: struct.HashSet.html /// [`drain`]: struct.HashSet.html#method.drain -pub struct Drain<'a, K, A: Allocator + Clone = Global> { +pub struct Drain<'a, K, A: Allocator = Global> { iter: map::Drain<'a, K, (), A>, } /// A draining iterator over entries of a `HashSet` which don't satisfy the predicate `f`. /// -/// This `struct` is created by the [`drain_filter`] method on [`HashSet`]. See its +/// This `struct` is created by the [`extract_if`] method on [`HashSet`]. See its /// documentation for more. /// -/// [`drain_filter`]: struct.HashSet.html#method.drain_filter +/// [`extract_if`]: struct.HashSet.html#method.extract_if /// [`HashSet`]: struct.HashSet.html -pub struct DrainFilter<'a, K, F, A: Allocator + Clone = Global> +#[must_use = "Iterators are lazy unless consumed"] +pub struct ExtractIf<'a, K, F, A: Allocator = Global> where F: FnMut(&K) -> bool, { f: F, - inner: DrainFilterInner<'a, K, (), A>, + inner: RawExtractIf<'a, (K, ()), A>, } /// A lazy iterator producing elements in the intersection of `HashSet`s. @@ -1468,7 +1592,7 @@ where /// /// [`HashSet`]: struct.HashSet.html /// [`intersection`]: struct.HashSet.html#method.intersection -pub struct Intersection<'a, T, S, A: Allocator + Clone = Global> { +pub struct Intersection<'a, T, S, A: Allocator = Global> { // iterator of the first set iter: Iter<'a, T>, // the second set @@ -1482,7 +1606,7 @@ pub struct Intersection<'a, T, S, A: Allocator + Clone = Global> { /// /// [`HashSet`]: struct.HashSet.html /// [`difference`]: struct.HashSet.html#method.difference -pub struct Difference<'a, T, S, A: Allocator + Clone = Global> { +pub struct Difference<'a, T, S, A: Allocator = Global> { // iterator of the first set iter: Iter<'a, T>, // the second set @@ -1496,7 +1620,7 @@ pub struct Difference<'a, T, S, A: Allocator + Clone = Global> { /// /// [`HashSet`]: struct.HashSet.html /// [`symmetric_difference`]: struct.HashSet.html#method.symmetric_difference -pub struct SymmetricDifference<'a, T, S, A: Allocator + Clone = Global> { +pub struct SymmetricDifference<'a, T, S, A: Allocator = Global> { iter: Chain<Difference<'a, T, S, A>, Difference<'a, T, S, A>>, } @@ -1507,11 +1631,11 @@ pub struct SymmetricDifference<'a, T, S, A: Allocator + Clone = Global> { /// /// [`HashSet`]: struct.HashSet.html /// [`union`]: struct.HashSet.html#method.union -pub struct Union<'a, T, S, A: Allocator + Clone = Global> { +pub struct Union<'a, T, S, A: Allocator = Global> { iter: Chain<Iter<'a, T>, Difference<'a, T, S, A>>, } -impl<'a, T, S, A: Allocator + Clone> IntoIterator for &'a HashSet<T, S, A> { +impl<'a, T, S, A: Allocator> IntoIterator for &'a HashSet<T, S, A> { type Item = &'a T; type IntoIter = Iter<'a, T>; @@ -1521,7 +1645,7 @@ impl<'a, T, S, A: Allocator + Clone> IntoIterator for &'a HashSet<T, S, A> { } } -impl<T, S, A: Allocator + Clone> IntoIterator for HashSet<T, S, A> { +impl<T, S, A: Allocator> IntoIterator for HashSet<T, S, A> { type Item = T; type IntoIter = IntoIter<T, A>; @@ -1572,6 +1696,14 @@ impl<'a, K> Iterator for Iter<'a, K> { fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } + #[cfg_attr(feature = "inline-more", inline)] + fn fold<B, F>(self, init: B, f: F) -> B + where + Self: Sized, + F: FnMut(B, Self::Item) -> B, + { + self.iter.fold(init, f) + } } impl<'a, K> ExactSizeIterator for Iter<'a, K> { #[cfg_attr(feature = "inline-more", inline)] @@ -1587,7 +1719,7 @@ impl<K: fmt::Debug> fmt::Debug for Iter<'_, K> { } } -impl<K, A: Allocator + Clone> Iterator for IntoIter<K, A> { +impl<K, A: Allocator> Iterator for IntoIter<K, A> { type Item = K; #[cfg_attr(feature = "inline-more", inline)] @@ -1602,23 +1734,31 @@ impl<K, A: Allocator + Clone> Iterator for IntoIter<K, A> { fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } + #[cfg_attr(feature = "inline-more", inline)] + fn fold<B, F>(self, init: B, mut f: F) -> B + where + Self: Sized, + F: FnMut(B, Self::Item) -> B, + { + self.iter.fold(init, |acc, (k, ())| f(acc, k)) + } } -impl<K, A: Allocator + Clone> ExactSizeIterator for IntoIter<K, A> { +impl<K, A: Allocator> ExactSizeIterator for IntoIter<K, A> { #[cfg_attr(feature = "inline-more", inline)] fn len(&self) -> usize { self.iter.len() } } -impl<K, A: Allocator + Clone> FusedIterator for IntoIter<K, A> {} +impl<K, A: Allocator> FusedIterator for IntoIter<K, A> {} -impl<K: fmt::Debug, A: Allocator + Clone> fmt::Debug for IntoIter<K, A> { +impl<K: fmt::Debug, A: Allocator> fmt::Debug for IntoIter<K, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { let entries_iter = self.iter.iter().map(|(k, _)| k); f.debug_list().entries(entries_iter).finish() } } -impl<K, A: Allocator + Clone> Iterator for Drain<'_, K, A> { +impl<K, A: Allocator> Iterator for Drain<'_, K, A> { type Item = K; #[cfg_attr(feature = "inline-more", inline)] @@ -1633,37 +1773,31 @@ impl<K, A: Allocator + Clone> Iterator for Drain<'_, K, A> { fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } + #[cfg_attr(feature = "inline-more", inline)] + fn fold<B, F>(self, init: B, mut f: F) -> B + where + Self: Sized, + F: FnMut(B, Self::Item) -> B, + { + self.iter.fold(init, |acc, (k, ())| f(acc, k)) + } } -impl<K, A: Allocator + Clone> ExactSizeIterator for Drain<'_, K, A> { +impl<K, A: Allocator> ExactSizeIterator for Drain<'_, K, A> { #[cfg_attr(feature = "inline-more", inline)] fn len(&self) -> usize { self.iter.len() } } -impl<K, A: Allocator + Clone> FusedIterator for Drain<'_, K, A> {} +impl<K, A: Allocator> FusedIterator for Drain<'_, K, A> {} -impl<K: fmt::Debug, A: Allocator + Clone> fmt::Debug for Drain<'_, K, A> { +impl<K: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, K, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { let entries_iter = self.iter.iter().map(|(k, _)| k); f.debug_list().entries(entries_iter).finish() } } -impl<'a, K, F, A: Allocator + Clone> Drop for DrainFilter<'a, K, F, A> -where - F: FnMut(&K) -> bool, -{ - #[cfg_attr(feature = "inline-more", inline)] - fn drop(&mut self) { - while let Some(item) = self.next() { - let guard = ConsumeAllOnDrop(self); - drop(item); - mem::forget(guard); - } - } -} - -impl<K, F, A: Allocator + Clone> Iterator for DrainFilter<'_, K, F, A> +impl<K, F, A: Allocator> Iterator for ExtractIf<'_, K, F, A> where F: FnMut(&K) -> bool, { @@ -1671,9 +1805,9 @@ where #[cfg_attr(feature = "inline-more", inline)] fn next(&mut self) -> Option<Self::Item> { - let f = &mut self.f; - let (k, _) = self.inner.next(&mut |k, _| f(k))?; - Some(k) + self.inner + .next(|&mut (ref k, ())| (self.f)(k)) + .map(|(k, ())| k) } #[inline] @@ -1682,12 +1816,9 @@ where } } -impl<K, F, A: Allocator + Clone> FusedIterator for DrainFilter<'_, K, F, A> where - F: FnMut(&K) -> bool -{ -} +impl<K, F, A: Allocator> FusedIterator for ExtractIf<'_, K, F, A> where F: FnMut(&K) -> bool {} -impl<T, S, A: Allocator + Clone> Clone for Intersection<'_, T, S, A> { +impl<T, S, A: Allocator> Clone for Intersection<'_, T, S, A> { #[cfg_attr(feature = "inline-more", inline)] fn clone(&self) -> Self { Intersection { @@ -1701,7 +1832,7 @@ impl<'a, T, S, A> Iterator for Intersection<'a, T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { type Item = &'a T; @@ -1720,13 +1851,27 @@ where let (_, upper) = self.iter.size_hint(); (0, upper) } + #[cfg_attr(feature = "inline-more", inline)] + fn fold<B, F>(self, init: B, mut f: F) -> B + where + Self: Sized, + F: FnMut(B, Self::Item) -> B, + { + self.iter.fold(init, |acc, elt| { + if self.other.contains(elt) { + f(acc, elt) + } else { + acc + } + }) + } } impl<T, S, A> fmt::Debug for Intersection<'_, T, S, A> where T: fmt::Debug + Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self.clone()).finish() @@ -1737,11 +1882,11 @@ impl<T, S, A> FusedIterator for Intersection<'_, T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { } -impl<T, S, A: Allocator + Clone> Clone for Difference<'_, T, S, A> { +impl<T, S, A: Allocator> Clone for Difference<'_, T, S, A> { #[cfg_attr(feature = "inline-more", inline)] fn clone(&self) -> Self { Difference { @@ -1755,7 +1900,7 @@ impl<'a, T, S, A> Iterator for Difference<'a, T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { type Item = &'a T; @@ -1774,13 +1919,27 @@ where let (_, upper) = self.iter.size_hint(); (0, upper) } + #[cfg_attr(feature = "inline-more", inline)] + fn fold<B, F>(self, init: B, mut f: F) -> B + where + Self: Sized, + F: FnMut(B, Self::Item) -> B, + { + self.iter.fold(init, |acc, elt| { + if self.other.contains(elt) { + acc + } else { + f(acc, elt) + } + }) + } } impl<T, S, A> FusedIterator for Difference<'_, T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { } @@ -1788,14 +1947,14 @@ impl<T, S, A> fmt::Debug for Difference<'_, T, S, A> where T: fmt::Debug + Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self.clone()).finish() } } -impl<T, S, A: Allocator + Clone> Clone for SymmetricDifference<'_, T, S, A> { +impl<T, S, A: Allocator> Clone for SymmetricDifference<'_, T, S, A> { #[cfg_attr(feature = "inline-more", inline)] fn clone(&self) -> Self { SymmetricDifference { @@ -1808,7 +1967,7 @@ impl<'a, T, S, A> Iterator for SymmetricDifference<'a, T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { type Item = &'a T; @@ -1820,13 +1979,21 @@ where fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } + #[cfg_attr(feature = "inline-more", inline)] + fn fold<B, F>(self, init: B, f: F) -> B + where + Self: Sized, + F: FnMut(B, Self::Item) -> B, + { + self.iter.fold(init, f) + } } impl<T, S, A> FusedIterator for SymmetricDifference<'_, T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { } @@ -1834,14 +2001,14 @@ impl<T, S, A> fmt::Debug for SymmetricDifference<'_, T, S, A> where T: fmt::Debug + Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self.clone()).finish() } } -impl<T, S, A: Allocator + Clone> Clone for Union<'_, T, S, A> { +impl<T, S, A: Allocator> Clone for Union<'_, T, S, A> { #[cfg_attr(feature = "inline-more", inline)] fn clone(&self) -> Self { Union { @@ -1854,7 +2021,7 @@ impl<T, S, A> FusedIterator for Union<'_, T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { } @@ -1862,7 +2029,7 @@ impl<T, S, A> fmt::Debug for Union<'_, T, S, A> where T: fmt::Debug + Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self.clone()).finish() @@ -1873,7 +2040,7 @@ impl<'a, T, S, A> Iterator for Union<'a, T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { type Item = &'a T; @@ -1885,6 +2052,14 @@ where fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } + #[cfg_attr(feature = "inline-more", inline)] + fn fold<B, F>(self, init: B, f: F) -> B + where + Self: Sized, + F: FnMut(B, Self::Item) -> B, + { + self.iter.fold(init, f) + } } /// A view into a single entry in a set, which may either be vacant or occupied. @@ -1925,7 +2100,7 @@ where /// ``` pub enum Entry<'a, T, S, A = Global> where - A: Allocator + Clone, + A: Allocator, { /// An occupied entry. /// @@ -1958,7 +2133,7 @@ where Vacant(VacantEntry<'a, T, S, A>), } -impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for Entry<'_, T, S, A> { +impl<T: fmt::Debug, S, A: Allocator> fmt::Debug for Entry<'_, T, S, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { match *self { Entry::Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(), @@ -2003,11 +2178,11 @@ impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for Entry<'_, T, S, A> { /// assert_eq!(set.get(&"c"), None); /// assert_eq!(set.len(), 2); /// ``` -pub struct OccupiedEntry<'a, T, S, A: Allocator + Clone = Global> { +pub struct OccupiedEntry<'a, T, S, A: Allocator = Global> { inner: map::OccupiedEntry<'a, T, (), S, A>, } -impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for OccupiedEntry<'_, T, S, A> { +impl<T: fmt::Debug, S, A: Allocator> fmt::Debug for OccupiedEntry<'_, T, S, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_struct("OccupiedEntry") .field("value", self.get()) @@ -2041,17 +2216,17 @@ impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for OccupiedEntry<'_, T, /// } /// assert!(set.contains("b") && set.len() == 2); /// ``` -pub struct VacantEntry<'a, T, S, A: Allocator + Clone = Global> { +pub struct VacantEntry<'a, T, S, A: Allocator = Global> { inner: map::VacantEntry<'a, T, (), S, A>, } -impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for VacantEntry<'_, T, S, A> { +impl<T: fmt::Debug, S, A: Allocator> fmt::Debug for VacantEntry<'_, T, S, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_tuple("VacantEntry").field(self.get()).finish() } } -impl<'a, T, S, A: Allocator + Clone> Entry<'a, T, S, A> { +impl<'a, T, S, A: Allocator> Entry<'a, T, S, A> { /// Sets the value of the entry, and returns an OccupiedEntry. /// /// # Examples @@ -2128,7 +2303,7 @@ impl<'a, T, S, A: Allocator + Clone> Entry<'a, T, S, A> { } } -impl<T, S, A: Allocator + Clone> OccupiedEntry<'_, T, S, A> { +impl<T, S, A: Allocator> OccupiedEntry<'_, T, S, A> { /// Gets a reference to the value in the entry. /// /// # Examples @@ -2215,7 +2390,7 @@ impl<T, S, A: Allocator + Clone> OccupiedEntry<'_, T, S, A> { } } -impl<'a, T, S, A: Allocator + Clone> VacantEntry<'a, T, S, A> { +impl<'a, T, S, A: Allocator> VacantEntry<'a, T, S, A> { /// Gets a reference to the value that would be used when inserting /// through the `VacantEntry`. /// @@ -2295,34 +2470,30 @@ fn assert_covariance() { fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> { v } - fn into_iter<'new, A: Allocator + Clone>( - v: IntoIter<&'static str, A>, - ) -> IntoIter<&'new str, A> { + fn into_iter<'new, A: Allocator>(v: IntoIter<&'static str, A>) -> IntoIter<&'new str, A> { v } - fn difference<'a, 'new, A: Allocator + Clone>( + fn difference<'a, 'new, A: Allocator>( v: Difference<'a, &'static str, DefaultHashBuilder, A>, ) -> Difference<'a, &'new str, DefaultHashBuilder, A> { v } - fn symmetric_difference<'a, 'new, A: Allocator + Clone>( + fn symmetric_difference<'a, 'new, A: Allocator>( v: SymmetricDifference<'a, &'static str, DefaultHashBuilder, A>, ) -> SymmetricDifference<'a, &'new str, DefaultHashBuilder, A> { v } - fn intersection<'a, 'new, A: Allocator + Clone>( + fn intersection<'a, 'new, A: Allocator>( v: Intersection<'a, &'static str, DefaultHashBuilder, A>, ) -> Intersection<'a, &'new str, DefaultHashBuilder, A> { v } - fn union<'a, 'new, A: Allocator + Clone>( + fn union<'a, 'new, A: Allocator>( v: Union<'a, &'static str, DefaultHashBuilder, A>, ) -> Union<'a, &'new str, DefaultHashBuilder, A> { v } - fn drain<'new, A: Allocator + Clone>( - d: Drain<'static, &'static str, A>, - ) -> Drain<'new, &'new str, A> { + fn drain<'new, A: Allocator>(d: Drain<'static, &'static str, A>) -> Drain<'new, &'new str, A> { d } } @@ -2613,10 +2784,10 @@ mod test_set { set.insert(1); set.insert(2); - let set_str = format!("{:?}", set); + let set_str = format!("{set:?}"); assert!(set_str == "{1, 2}" || set_str == "{2, 1}"); - assert_eq!(format!("{:?}", empty), "{}"); + assert_eq!(format!("{empty:?}"), "{}"); } #[test] @@ -2649,7 +2820,7 @@ mod test_set { assert_eq!(last_i, 49); } - for _ in &s { + if !s.is_empty() { panic!("s should be empty!"); } @@ -2663,6 +2834,7 @@ mod test_set { use core::hash; #[derive(Debug)] + #[allow(dead_code)] struct Foo(&'static str, i32); impl PartialEq for Foo { @@ -2691,11 +2863,12 @@ mod test_set { } #[test] + #[allow(clippy::needless_borrow)] fn test_extend_ref() { let mut a = HashSet::new(); a.insert(1); - a.extend(&[2, 3, 4]); + a.extend([2, 3, 4]); assert_eq!(a.len(), 4); assert!(a.contains(&1)); @@ -2730,10 +2903,10 @@ mod test_set { } #[test] - fn test_drain_filter() { + fn test_extract_if() { { let mut set: HashSet<i32> = (0..8).collect(); - let drained = set.drain_filter(|&k| k % 2 == 0); + let drained = set.extract_if(|&k| k % 2 == 0); let mut out = drained.collect::<Vec<_>>(); out.sort_unstable(); assert_eq!(vec![0, 2, 4, 6], out); @@ -2741,7 +2914,7 @@ mod test_set { } { let mut set: HashSet<i32> = (0..8).collect(); - drop(set.drain_filter(|&k| k % 2 == 0)); + set.extract_if(|&k| k % 2 == 0).for_each(drop); assert_eq!(set.len(), 4, "Removes non-matching items on drop"); } } @@ -2787,4 +2960,11 @@ mod test_set { set.insert(i); } } + + #[test] + fn collect() { + // At the time of writing, this hits the ZST case in from_base_index + // (and without the `map`, it does not). + let mut _set: HashSet<_> = (0..3).map(|_| ()).collect(); + } } |