From 20431706a863f92cb37dc512fef6e48d192aaf2c Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:11:38 +0200 Subject: Merging upstream version 1.66.0+dfsg1. Signed-off-by: Daniel Baumann --- compiler/rustc_data_structures/src/unord.rs | 382 ++++++++++++++++++++++++++++ 1 file changed, 382 insertions(+) create mode 100644 compiler/rustc_data_structures/src/unord.rs (limited to 'compiler/rustc_data_structures/src/unord.rs') diff --git a/compiler/rustc_data_structures/src/unord.rs b/compiler/rustc_data_structures/src/unord.rs new file mode 100644 index 000000000..c015f1232 --- /dev/null +++ b/compiler/rustc_data_structures/src/unord.rs @@ -0,0 +1,382 @@ +//! This module contains collection types that don't expose their internal +//! ordering. This is a useful property for deterministic computations, such +//! as required by the query system. + +use rustc_hash::{FxHashMap, FxHashSet}; +use smallvec::SmallVec; +use std::{ + borrow::Borrow, + hash::Hash, + iter::{Product, Sum}, +}; + +use crate::{ + fingerprint::Fingerprint, + stable_hasher::{HashStable, StableHasher, ToStableHashKey}, +}; + +/// `UnordItems` is the order-less version of `Iterator`. It only contains methods +/// that don't (easily) expose an ordering of the underlying items. +/// +/// Most methods take an `Fn` where the `Iterator`-version takes an `FnMut`. This +/// is to reduce the risk of accidentally leaking the internal order via the closure +/// environment. Otherwise one could easily do something like +/// +/// ```rust,ignore (pseudo code) +/// let mut ordered = vec![]; +/// unordered_items.all(|x| ordered.push(x)); +/// ``` +/// +/// 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. +pub struct UnordItems>(I); + +impl> UnordItems { + #[inline] + pub fn map U>(self, f: F) -> UnordItems> { + UnordItems(self.0.map(f)) + } + + #[inline] + pub fn all bool>(mut self, f: F) -> bool { + self.0.all(f) + } + + #[inline] + pub fn any bool>(mut self, f: F) -> bool { + self.0.any(f) + } + + #[inline] + pub fn filter bool>(self, f: F) -> UnordItems> { + UnordItems(self.0.filter(f)) + } + + #[inline] + pub fn filter_map Option>( + self, + f: F, + ) -> UnordItems> { + UnordItems(self.0.filter_map(f)) + } + + #[inline] + pub fn max(self) -> Option + where + T: Ord, + { + self.0.max() + } + + #[inline] + pub fn min(self) -> Option + where + T: Ord, + { + self.0.min() + } + + #[inline] + pub fn sum(self) -> S + where + S: Sum, + { + self.0.sum() + } + + #[inline] + pub fn product(self) -> S + where + S: Product, + { + self.0.product() + } + + #[inline] + pub fn count(self) -> usize { + self.0.count() + } +} + +impl<'a, T: Clone + 'a, I: Iterator> UnordItems<&'a T, I> { + #[inline] + pub fn cloned(self) -> UnordItems> { + UnordItems(self.0.cloned()) + } +} + +impl<'a, T: Copy + 'a, I: Iterator> UnordItems<&'a T, I> { + #[inline] + pub fn copied(self) -> UnordItems> { + UnordItems(self.0.copied()) + } +} + +impl> UnordItems { + pub fn into_sorted(self, hcx: &HCX) -> Vec + where + T: ToStableHashKey, + { + let mut items: Vec = self.0.collect(); + items.sort_by_cached_key(|x| x.to_stable_hash_key(hcx)); + items + } + + pub fn into_sorted_small_vec(self, hcx: &HCX) -> SmallVec<[T; LEN]> + where + T: ToStableHashKey, + { + let mut items: SmallVec<[T; LEN]> = self.0.collect(); + items.sort_by_cached_key(|x| x.to_stable_hash_key(hcx)); + items + } +} + +/// 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. +/// +/// This collection type is a good choice for set-like collections the +/// keys of which don't have a semantic ordering. +/// +/// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533) +/// for more information. +#[derive(Debug, Eq, PartialEq, Clone, Encodable, Decodable)] +pub struct UnordSet { + inner: FxHashSet, +} + +impl Default for UnordSet { + fn default() -> Self { + Self { inner: FxHashSet::default() } + } +} + +impl UnordSet { + #[inline] + pub fn new() -> Self { + Self { inner: Default::default() } + } + + #[inline] + pub fn len(&self) -> usize { + self.inner.len() + } + + #[inline] + pub fn insert(&mut self, v: V) -> bool { + self.inner.insert(v) + } + + #[inline] + pub fn contains(&self, v: &Q) -> bool + where + V: Borrow, + Q: Hash + Eq, + { + self.inner.contains(v) + } + + #[inline] + pub fn items<'a>(&'a self) -> UnordItems<&'a V, impl Iterator> { + UnordItems(self.inner.iter()) + } + + #[inline] + pub fn into_items(self) -> UnordItems> { + 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>(&mut self, items: UnordItems) { + self.inner.extend(items.0) + } +} + +impl Extend for UnordSet { + fn extend>(&mut self, iter: T) { + self.inner.extend(iter) + } +} + +impl> HashStable for UnordSet { + #[inline] + fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { + hash_iter_order_independent(self.inner.iter(), hcx, hasher); + } +} + +/// This is a map 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. +/// +/// This collection type is a good choice for map-like collections the +/// keys of which don't have a semantic ordering. +/// +/// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533) +/// for more information. +#[derive(Debug, Eq, PartialEq, Clone, Encodable, Decodable)] +pub struct UnordMap { + inner: FxHashMap, +} + +impl Default for UnordMap { + fn default() -> Self { + Self { inner: FxHashMap::default() } + } +} + +impl Extend<(K, V)> for UnordMap { + fn extend>(&mut self, iter: T) { + self.inner.extend(iter) + } +} + +impl UnordMap { + #[inline] + pub fn len(&self) -> usize { + self.inner.len() + } + + #[inline] + pub fn insert(&mut self, k: K, v: V) -> Option { + self.inner.insert(k, v) + } + + #[inline] + pub fn contains_key(&self, k: &Q) -> bool + where + K: Borrow, + Q: Hash + Eq, + { + self.inner.contains_key(k) + } + + #[inline] + pub fn items<'a>(&'a self) -> UnordItems<(&'a K, &'a V), impl Iterator> { + UnordItems(self.inner.iter()) + } + + #[inline] + pub fn into_items(self) -> UnordItems<(K, V), impl Iterator> { + 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>(&mut self, items: UnordItems<(K, V), I>) { + self.inner.extend(items.0) + } +} + +impl, V: HashStable> HashStable for UnordMap { + #[inline] + fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { + hash_iter_order_independent(self.inner.iter(), hcx, hasher); + } +} + +/// This is a 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. +/// +/// This collection type is a good choice for collections the +/// keys of which don't have a semantic ordering and don't implement +/// `Hash` or `Eq`. +/// +/// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533) +/// for more information. +#[derive(Default, Debug, Eq, PartialEq, Clone, Encodable, Decodable)] +pub struct UnordBag { + inner: Vec, +} + +impl UnordBag { + #[inline] + pub fn new() -> Self { + Self { inner: Default::default() } + } + + #[inline] + pub fn len(&self) -> usize { + self.inner.len() + } + + #[inline] + pub fn push(&mut self, v: V) { + self.inner.push(v); + } + + #[inline] + pub fn items<'a>(&'a self) -> UnordItems<&'a V, impl Iterator> { + UnordItems(self.inner.iter()) + } + + #[inline] + pub fn into_items(self) -> UnordItems> { + 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>(&mut self, items: UnordItems) { + self.inner.extend(items.0) + } +} + +impl Extend for UnordBag { + fn extend>(&mut self, iter: I) { + self.inner.extend(iter) + } +} + +impl> HashStable for UnordBag { + #[inline] + fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { + hash_iter_order_independent(self.inner.iter(), hcx, hasher); + } +} + +fn hash_iter_order_independent< + HCX, + T: HashStable, + I: Iterator + ExactSizeIterator, +>( + mut it: I, + hcx: &mut HCX, + hasher: &mut StableHasher, +) { + let len = it.len(); + len.hash_stable(hcx, hasher); + + match len { + 0 => { + // We're done + } + 1 => { + // No need to instantiate a hasher + it.next().unwrap().hash_stable(hcx, hasher); + } + _ => { + let mut accumulator = Fingerprint::ZERO; + for item in it { + let mut item_hasher = StableHasher::new(); + item.hash_stable(hcx, &mut item_hasher); + let item_fingerprint: Fingerprint = item_hasher.finish(); + accumulator = accumulator.combine_commutative(item_fingerprint); + } + accumulator.hash_stable(hcx, hasher); + } + } +} + +// Do not implement IntoIterator for the collections in this module. +// They only exist to hide iteration order in the first place. +impl !IntoIterator for UnordBag {} +impl !IntoIterator for UnordSet {} +impl !IntoIterator for UnordMap {} +impl !IntoIterator for UnordItems {} -- cgit v1.2.3