compiler/rustc_data_structures/src/unord.rs

   1 //! This module contains collection types that don't expose their internal
   2 //! ordering. This is a useful property for deterministic computations, such
   3 //! as required by the query system.
   4
   5 use rustc_hash::{FxHashMap, FxHashSet};
   6 use smallvec::SmallVec;
   7 use std::{
   8     borrow::Borrow,
   9     hash::Hash,
  10     iter::{Product, Sum},
  11 };
  12
  13 use crate::{
  14     fingerprint::Fingerprint,
  15     stable_hasher::{HashStable, StableHasher, ToStableHashKey},
  16 };
  17
  18 /// `UnordItems` is the order-less version of `Iterator`. It only contains methods
  19 /// that don't (easily) expose an ordering of the underlying items.
  20 ///
  21 /// Most methods take an `Fn` where the `Iterator`-version takes an `FnMut`. This
  22 /// is to reduce the risk of accidentally leaking the internal order via the closure
  23 /// environment. Otherwise one could easily do something like
  24 ///
  25 /// ```rust,ignore (pseudo code)
  26 /// let mut ordered = vec![];
  27 /// unordered_items.all(|x| ordered.push(x));
  28 /// ```
  29 ///
  30 /// It's still possible to do the same thing with an `Fn` by using interior mutability,
  31 /// but the chance of doing it accidentally is reduced.
  32 pub struct UnordItems<T, I: Iterator<Item = T>>(I);
  33
  34 impl<T, I: Iterator<Item = T>> UnordItems<T, I> {
  35     #[inline]
  36     pub fn map<U, F: Fn(T) -> U>(self, f: F) -> UnordItems<U, impl Iterator<Item = U>> {
  37         UnordItems(self.0.map(f))
  38     }
  39
  40     #[inline]
  41     pub fn all<U, F: Fn(T) -> bool>(mut self, f: F) -> bool {
  42         self.0.all(f)
  43     }
  44
  45     #[inline]
  46     pub fn any<U, F: Fn(T) -> bool>(mut self, f: F) -> bool {
  47         self.0.any(f)
  48     }
  49
  50     #[inline]
  51     pub fn filter<U, F: Fn(&T) -> bool>(self, f: F) -> UnordItems<T, impl Iterator<Item = T>> {
  52         UnordItems(self.0.filter(f))
  53     }
  54
  55     #[inline]
  56     pub fn filter_map<U, F: Fn(T) -> Option<U>>(
  57         self,
  58         f: F,
  59     ) -> UnordItems<U, impl Iterator<Item = U>> {
  60         UnordItems(self.0.filter_map(f))
  61     }
  62
  63     #[inline]
  64     pub fn max(self) -> Option<T>
  65     where
  66         T: Ord,
  67     {
  68         self.0.max()
  69     }
  70
  71     #[inline]
  72     pub fn min(self) -> Option<T>
  73     where
  74         T: Ord,
  75     {
  76         self.0.min()
  77     }
  78
  79     #[inline]
  80     pub fn sum<S>(self) -> S
  81     where
  82         S: Sum<T>,
  83     {
  84         self.0.sum()
  85     }
  86
  87     #[inline]
  88     pub fn product<S>(self) -> S
  89     where
  90         S: Product<T>,
  91     {
  92         self.0.product()
  93     }
  94
  95     #[inline]
  96     pub fn count(self) -> usize {
  97         self.0.count()
  98     }
  99 }
 100
 101 impl<'a, T: Clone + 'a, I: Iterator<Item = &'a T>> UnordItems<&'a T, I> {
 102     #[inline]
 103     pub fn cloned(self) -> UnordItems<T, impl Iterator<Item = T>> {
 104         UnordItems(self.0.cloned())
 105     }
 106 }
 107
 108 impl<'a, T: Copy + 'a, I: Iterator<Item = &'a T>> UnordItems<&'a T, I> {
 109     #[inline]
 110     pub fn copied(self) -> UnordItems<T, impl Iterator<Item = T>> {
 111         UnordItems(self.0.copied())
 112     }
 113 }
 114
 115 impl<T: Ord, I: Iterator<Item = T>> UnordItems<T, I> {
 116     pub fn into_sorted<HCX>(self, hcx: &HCX) -> Vec<T>
 117     where
 118         T: ToStableHashKey<HCX>,
 119     {
 120         let mut items: Vec<T> = self.0.collect();
 121         items.sort_by_cached_key(|x| x.to_stable_hash_key(hcx));
 122         items
 123     }
 124
 125     pub fn into_sorted_small_vec<HCX, const LEN: usize>(self, hcx: &HCX) -> SmallVec<[T; LEN]>
 126     where
 127         T: ToStableHashKey<HCX>,
 128     {
 129         let mut items: SmallVec<[T; LEN]> = self.0.collect();
 130         items.sort_by_cached_key(|x| x.to_stable_hash_key(hcx));
 131         items
 132     }
 133 }
 134
 135 /// This is a set collection type that tries very hard to not expose
 136 /// any internal iteration. This is a useful property when trying to
 137 /// uphold the determinism invariants imposed by the query system.
 138 ///
 139 /// This collection type is a good choice for set-like collections the
 140 /// keys of which don't have a semantic ordering.
 141 ///
 142 /// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
 143 /// for more information.
 144 #[derive(Debug, Eq, PartialEq, Clone, Encodable, Decodable)]
 145 pub struct UnordSet<V: Eq + Hash> {
 146     inner: FxHashSet<V>,
 147 }
 148
 149 impl<V: Eq + Hash> Default for UnordSet<V> {
 150     fn default() -> Self {
 151         Self { inner: FxHashSet::default() }
 152     }
 153 }
 154
 155 impl<V: Eq + Hash> UnordSet<V> {
 156     #[inline]
 157     pub fn new() -> Self {
 158         Self { inner: Default::default() }
 159     }
 160
 161     #[inline]
 162     pub fn len(&self) -> usize {
 163         self.inner.len()
 164     }
 165
 166     #[inline]
 167     pub fn insert(&mut self, v: V) -> bool {
 168         self.inner.insert(v)
 169     }
 170
 171     #[inline]
 172     pub fn contains<Q: ?Sized>(&self, v: &Q) -> bool
 173     where
 174         V: Borrow<Q>,
 175         Q: Hash + Eq,
 176     {
 177         self.inner.contains(v)
 178     }
 179
 180     #[inline]
 181     pub fn items(&self) -> UnordItems<&V, impl Iterator<Item = &V>> {
 182         UnordItems(self.inner.iter())
 183     }
 184
 185     #[inline]
 186     pub fn into_items(self) -> UnordItems<V, impl Iterator<Item = V>> {
 187         UnordItems(self.inner.into_iter())
 188     }
 189
 190     // We can safely extend this UnordSet from a set of unordered values because that
 191     // won't expose the internal ordering anywhere.
 192     #[inline]
 193     pub fn extend<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) {
 194         self.inner.extend(items.0)
 195     }
 196 }
 197
 198 impl<V: Hash + Eq> Extend<V> for UnordSet<V> {
 199     fn extend<T: IntoIterator<Item = V>>(&mut self, iter: T) {
 200         self.inner.extend(iter)
 201     }
 202 }
 203
 204 impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordSet<V> {
 205     #[inline]
 206     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 207         hash_iter_order_independent(self.inner.iter(), hcx, hasher);
 208     }
 209 }
 210
 211 /// This is a map collection type that tries very hard to not expose
 212 /// any internal iteration. This is a useful property when trying to
 213 /// uphold the determinism invariants imposed by the query system.
 214 ///
 215 /// This collection type is a good choice for map-like collections the
 216 /// keys of which don't have a semantic ordering.
 217 ///
 218 /// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
 219 /// for more information.
 220 #[derive(Debug, Eq, PartialEq, Clone, Encodable, Decodable)]
 221 pub struct UnordMap<K: Eq + Hash, V> {
 222     inner: FxHashMap<K, V>,
 223 }
 224
 225 impl<K: Eq + Hash, V> Default for UnordMap<K, V> {
 226     fn default() -> Self {
 227         Self { inner: FxHashMap::default() }
 228     }
 229 }
 230
 231 impl<K: Hash + Eq, V> Extend<(K, V)> for UnordMap<K, V> {
 232     fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
 233         self.inner.extend(iter)
 234     }
 235 }
 236
 237 impl<K: Eq + Hash, V> UnordMap<K, V> {
 238     #[inline]
 239     pub fn len(&self) -> usize {
 240         self.inner.len()
 241     }
 242
 243     #[inline]
 244     pub fn insert(&mut self, k: K, v: V) -> Option<V> {
 245         self.inner.insert(k, v)
 246     }
 247
 248     #[inline]
 249     pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
 250     where
 251         K: Borrow<Q>,
 252         Q: Hash + Eq,
 253     {
 254         self.inner.contains_key(k)
 255     }
 256
 257     #[inline]
 258     pub fn items(&self) -> UnordItems<(&K, &V), impl Iterator<Item = (&K, &V)>> {
 259         UnordItems(self.inner.iter())
 260     }
 261
 262     #[inline]
 263     pub fn into_items(self) -> UnordItems<(K, V), impl Iterator<Item = (K, V)>> {
 264         UnordItems(self.inner.into_iter())
 265     }
 266
 267     // We can safely extend this UnordMap from a set of unordered values because that
 268     // won't expose the internal ordering anywhere.
 269     #[inline]
 270     pub fn extend<I: Iterator<Item = (K, V)>>(&mut self, items: UnordItems<(K, V), I>) {
 271         self.inner.extend(items.0)
 272     }
 273 }
 274
 275 impl<HCX, K: Hash + Eq + HashStable<HCX>, V: HashStable<HCX>> HashStable<HCX> for UnordMap<K, V> {
 276     #[inline]
 277     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 278         hash_iter_order_independent(self.inner.iter(), hcx, hasher);
 279     }
 280 }
 281
 282 /// This is a collection type that tries very hard to not expose
 283 /// any internal iteration. This is a useful property when trying to
 284 /// uphold the determinism invariants imposed by the query system.
 285 ///
 286 /// This collection type is a good choice for collections the
 287 /// keys of which don't have a semantic ordering and don't implement
 288 /// `Hash` or `Eq`.
 289 ///
 290 /// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
 291 /// for more information.
 292 #[derive(Default, Debug, Eq, PartialEq, Clone, Encodable, Decodable)]
 293 pub struct UnordBag<V> {
 294     inner: Vec<V>,
 295 }
 296
 297 impl<V> UnordBag<V> {
 298     #[inline]
 299     pub fn new() -> Self {
 300         Self { inner: Default::default() }
 301     }
 302
 303     #[inline]
 304     pub fn len(&self) -> usize {
 305         self.inner.len()
 306     }
 307
 308     #[inline]
 309     pub fn push(&mut self, v: V) {
 310         self.inner.push(v);
 311     }
 312
 313     #[inline]
 314     pub fn items(&self) -> UnordItems<&V, impl Iterator<Item = &V>> {
 315         UnordItems(self.inner.iter())
 316     }
 317
 318     #[inline]
 319     pub fn into_items(self) -> UnordItems<V, impl Iterator<Item = V>> {
 320         UnordItems(self.inner.into_iter())
 321     }
 322
 323     // We can safely extend this UnordSet from a set of unordered values because that
 324     // won't expose the internal ordering anywhere.
 325     #[inline]
 326     pub fn extend<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) {
 327         self.inner.extend(items.0)
 328     }
 329 }
 330
 331 impl<T> Extend<T> for UnordBag<T> {
 332     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
 333         self.inner.extend(iter)
 334     }
 335 }
 336
 337 impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordBag<V> {
 338     #[inline]
 339     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 340         hash_iter_order_independent(self.inner.iter(), hcx, hasher);
 341     }
 342 }
 343
 344 fn hash_iter_order_independent<
 345     HCX,
 346     T: HashStable<HCX>,
 347     I: Iterator<Item = T> + ExactSizeIterator,
 348 >(
 349     mut it: I,
 350     hcx: &mut HCX,
 351     hasher: &mut StableHasher,
 352 ) {
 353     let len = it.len();
 354     len.hash_stable(hcx, hasher);
 355
 356     match len {
 357         0 => {
 358             // We're done
 359         }
 360         1 => {
 361             // No need to instantiate a hasher
 362             it.next().unwrap().hash_stable(hcx, hasher);
 363         }
 364         _ => {
 365             let mut accumulator = Fingerprint::ZERO;
 366             for item in it {
 367                 let mut item_hasher = StableHasher::new();
 368                 item.hash_stable(hcx, &mut item_hasher);
 369                 let item_fingerprint: Fingerprint = item_hasher.finish();
 370                 accumulator = accumulator.combine_commutative(item_fingerprint);
 371             }
 372             accumulator.hash_stable(hcx, hasher);
 373         }
 374     }
 375 }
 376
 377 // Do not implement IntoIterator for the collections in this module.
 378 // They only exist to hide iteration order in the first place.
 379 impl<T> !IntoIterator for UnordBag<T> {}
 380 impl<V> !IntoIterator for UnordSet<V> {}
 381 impl<K, V> !IntoIterator for UnordMap<K, V> {}
 382 impl<T, I> !IntoIterator for UnordItems<T, I> {}