diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-30 03:59:35 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-30 03:59:35 +0000 |
commit | d1b2d29528b7794b41e66fc2136e395a02f8529b (patch) | |
tree | a4a17504b260206dec3cf55b2dca82929a348ac2 /compiler/rustc_data_structures/src/unord.rs | |
parent | Releasing progress-linux version 1.72.1+dfsg1-1~progress7.99u1. (diff) | |
download | rustc-d1b2d29528b7794b41e66fc2136e395a02f8529b.tar.xz rustc-d1b2d29528b7794b41e66fc2136e395a02f8529b.zip |
Merging upstream version 1.73.0+dfsg1.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'compiler/rustc_data_structures/src/unord.rs')
-rw-r--r-- | compiler/rustc_data_structures/src/unord.rs | 73 |
1 files changed, 51 insertions, 22 deletions
diff --git a/compiler/rustc_data_structures/src/unord.rs b/compiler/rustc_data_structures/src/unord.rs index 2b21815b6..47c56eba7 100644 --- a/compiler/rustc_data_structures/src/unord.rs +++ b/compiler/rustc_data_structures/src/unord.rs @@ -31,6 +31,7 @@ use crate::{ /// /// It's still possible to do the same thing with an `Fn` by using interior mutability, /// but the chance of doing it accidentally is reduced. +#[derive(Clone)] pub struct UnordItems<T, I: Iterator<Item = T>>(I); impl<T, I: Iterator<Item = T>> UnordItems<T, I> { @@ -167,6 +168,14 @@ impl<T: Ord, I: Iterator<Item = T>> UnordItems<T, I> { } } +/// A marker trait specifying that `Self` can consume `UnordItems<_>` without +/// exposing any internal ordering. +/// +/// Note: right now this is just a marker trait. It could be extended to contain +/// some useful, common methods though, like `len`, `clear`, or the various +/// kinds of `to_sorted`. +trait UnordCollection {} + /// This is a set collection type that tries very hard to not expose /// any internal iteration. This is a useful property when trying to /// uphold the determinism invariants imposed by the query system. @@ -181,6 +190,8 @@ pub struct UnordSet<V: Eq + Hash> { inner: FxHashSet<V>, } +impl<V: Eq + Hash> UnordCollection for UnordSet<V> {} + impl<V: Eq + Hash> Default for UnordSet<V> { #[inline] fn default() -> Self { @@ -195,6 +206,11 @@ impl<V: Eq + Hash> UnordSet<V> { } #[inline] + pub fn with_capacity(capacity: usize) -> Self { + Self { inner: FxHashSet::with_capacity_and_hasher(capacity, Default::default()) } + } + + #[inline] pub fn len(&self) -> usize { self.inner.len() } @@ -258,9 +274,9 @@ impl<V: Eq + Hash> UnordSet<V> { #[inline] pub fn to_sorted_stable_ord(&self) -> Vec<V> where - V: Ord + StableOrd + Copy, + V: Ord + StableOrd + Clone, { - let mut items: Vec<V> = self.inner.iter().copied().collect(); + let mut items: Vec<V> = self.inner.iter().cloned().collect(); items.sort_unstable(); items } @@ -279,16 +295,28 @@ impl<V: Eq + Hash> UnordSet<V> { to_sorted_vec(hcx, self.inner.into_iter(), cache_sort_key, |x| x) } - // We can safely extend this UnordSet from a set of unordered values because that - // won't expose the internal ordering anywhere. #[inline] - pub fn extend_unord<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) { - self.inner.extend(items.0) + pub fn clear(&mut self) { + self.inner.clear(); } +} + +pub trait ExtendUnord<T> { + /// Extend this unord collection with the given `UnordItems`. + /// This method is called `extend_unord` instead of just `extend` so it + /// does not conflict with `Extend::extend`. Otherwise there would be many + /// places where the two methods would have to be explicitly disambiguated + /// via UFCS. + fn extend_unord<I: Iterator<Item = T>>(&mut self, items: UnordItems<T, I>); +} +// Note: it is important that `C` implements `UnordCollection` in addition to +// `Extend`, otherwise this impl would leak the internal iteration order of +// `items`, e.g. when calling `some_vec.extend_unord(some_unord_items)`. +impl<C: Extend<T> + UnordCollection, T> ExtendUnord<T> for C { #[inline] - pub fn clear(&mut self) { - self.inner.clear(); + fn extend_unord<I: Iterator<Item = T>>(&mut self, items: UnordItems<T, I>) { + self.extend(items.0) } } @@ -312,6 +340,12 @@ impl<V: Hash + Eq> From<FxHashSet<V>> for UnordSet<V> { } } +impl<V: Hash + Eq, I: Iterator<Item = V>> From<UnordItems<V, I>> for UnordSet<V> { + fn from(value: UnordItems<V, I>) -> Self { + UnordSet { inner: FxHashSet::from_iter(value.0) } + } +} + impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordSet<V> { #[inline] fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { @@ -333,6 +367,8 @@ pub struct UnordMap<K: Eq + Hash, V> { inner: FxHashMap<K, V>, } +impl<K: Eq + Hash, V> UnordCollection for UnordMap<K, V> {} + impl<K: Eq + Hash, V> Default for UnordMap<K, V> { #[inline] fn default() -> Self { @@ -363,6 +399,11 @@ impl<K: Hash + Eq, V, I: Iterator<Item = (K, V)>> From<UnordItems<(K, V), I>> fo impl<K: Eq + Hash, V> UnordMap<K, V> { #[inline] + pub fn with_capacity(capacity: usize) -> Self { + Self { inner: FxHashMap::with_capacity_and_hasher(capacity, Default::default()) } + } + + #[inline] pub fn len(&self) -> usize { self.inner.len() } @@ -428,13 +469,6 @@ impl<K: Eq + Hash, V> UnordMap<K, V> { UnordItems(self.inner.into_iter()) } - // We can safely extend this UnordMap from a set of unordered values because that - // won't expose the internal ordering anywhere. - #[inline] - pub fn extend<I: Iterator<Item = (K, V)>>(&mut self, items: UnordItems<(K, V), I>) { - self.inner.extend(items.0) - } - /// Returns the entries of this map in stable sort order (as defined by `ToStableHashKey`). /// /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or @@ -554,15 +588,10 @@ impl<V> UnordBag<V> { pub fn into_items(self) -> UnordItems<V, impl Iterator<Item = V>> { UnordItems(self.inner.into_iter()) } - - // We can safely extend this UnordSet from a set of unordered values because that - // won't expose the internal ordering anywhere. - #[inline] - pub fn extend<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) { - self.inner.extend(items.0) - } } +impl<T> UnordCollection for UnordBag<T> {} + impl<T> Extend<T> for UnordBag<T> { fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { self.inner.extend(iter) |