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     collections::hash_map::Entry,
  10     hash::Hash,
  11     iter::{Product, Sum},
  12     ops::Index,
  13 };
  14
  15 use crate::{
  16     fingerprint::Fingerprint,
  17     stable_hasher::{HashStable, StableHasher, StableOrd, ToStableHashKey},
  18 };
  19
  20 /// `UnordItems` is the order-less version of `Iterator`. It only contains methods
  21 /// that don't (easily) expose an ordering of the underlying items.
  22 ///
  23 /// Most methods take an `Fn` where the `Iterator`-version takes an `FnMut`. This
  24 /// is to reduce the risk of accidentally leaking the internal order via the closure
  25 /// environment. Otherwise one could easily do something like
  26 ///
  27 /// ```rust,ignore (pseudo code)
  28 /// let mut ordered = vec![];
  29 /// unordered_items.all(|x| ordered.push(x));
  30 /// ```
  31 ///
  32 /// It's still possible to do the same thing with an `Fn` by using interior mutability,
  33 /// but the chance of doing it accidentally is reduced.
  34 pub struct UnordItems<T, I: Iterator<Item = T>>(I);
  35
  36 impl<T, I: Iterator<Item = T>> UnordItems<T, I> {
  37     #[inline]
  38     pub fn map<U, F: Fn(T) -> U>(self, f: F) -> UnordItems<U, impl Iterator<Item = U>> {
  39         UnordItems(self.0.map(f))
  40     }
  41
  42     #[inline]
  43     pub fn all<F: Fn(T) -> bool>(mut self, f: F) -> bool {
  44         self.0.all(f)
  45     }
  46
  47     #[inline]
  48     pub fn any<F: Fn(T) -> bool>(mut self, f: F) -> bool {
  49         self.0.any(f)
  50     }
  51
  52     #[inline]
  53     pub fn filter<F: Fn(&T) -> bool>(self, f: F) -> UnordItems<T, impl Iterator<Item = T>> {
  54         UnordItems(self.0.filter(f))
  55     }
  56
  57     #[inline]
  58     pub fn filter_map<U, F: Fn(T) -> Option<U>>(
  59         self,
  60         f: F,
  61     ) -> UnordItems<U, impl Iterator<Item = U>> {
  62         UnordItems(self.0.filter_map(f))
  63     }
  64
  65     #[inline]
  66     pub fn max(self) -> Option<T>
  67     where
  68         T: Ord,
  69     {
  70         self.0.max()
  71     }
  72
  73     #[inline]
  74     pub fn min(self) -> Option<T>
  75     where
  76         T: Ord,
  77     {
  78         self.0.min()
  79     }
  80
  81     #[inline]
  82     pub fn sum<S>(self) -> S
  83     where
  84         S: Sum<T>,
  85     {
  86         self.0.sum()
  87     }
  88
  89     #[inline]
  90     pub fn product<S>(self) -> S
  91     where
  92         S: Product<T>,
  93     {
  94         self.0.product()
  95     }
  96
  97     #[inline]
  98     pub fn count(self) -> usize {
  99         self.0.count()
 100     }
 101
 102     #[inline]
 103     pub fn flat_map<U, F, O>(self, f: F) -> UnordItems<O, impl Iterator<Item = O>>
 104     where
 105         U: IntoIterator<Item = O>,
 106         F: Fn(T) -> U,
 107     {
 108         UnordItems(self.0.flat_map(f))
 109     }
 110 }
 111
 112 impl<'a, T: Clone + 'a, I: Iterator<Item = &'a T>> UnordItems<&'a T, I> {
 113     #[inline]
 114     pub fn cloned(self) -> UnordItems<T, impl Iterator<Item = T>> {
 115         UnordItems(self.0.cloned())
 116     }
 117 }
 118
 119 impl<'a, T: Copy + 'a, I: Iterator<Item = &'a T>> UnordItems<&'a T, I> {
 120     #[inline]
 121     pub fn copied(self) -> UnordItems<T, impl Iterator<Item = T>> {
 122         UnordItems(self.0.copied())
 123     }
 124 }
 125
 126 impl<T: Ord, I: Iterator<Item = T>> UnordItems<T, I> {
 127     pub fn into_sorted<HCX>(self, hcx: &HCX) -> Vec<T>
 128     where
 129         T: ToStableHashKey<HCX>,
 130     {
 131         let mut items: Vec<T> = self.0.collect();
 132         items.sort_by_cached_key(|x| x.to_stable_hash_key(hcx));
 133         items
 134     }
 135
 136     pub fn into_sorted_small_vec<HCX, const LEN: usize>(self, hcx: &HCX) -> SmallVec<[T; LEN]>
 137     where
 138         T: ToStableHashKey<HCX>,
 139     {
 140         let mut items: SmallVec<[T; LEN]> = self.0.collect();
 141         items.sort_by_cached_key(|x| x.to_stable_hash_key(hcx));
 142         items
 143     }
 144 }
 145
 146 /// This is a set collection type that tries very hard to not expose
 147 /// any internal iteration. This is a useful property when trying to
 148 /// uphold the determinism invariants imposed by the query system.
 149 ///
 150 /// This collection type is a good choice for set-like collections the
 151 /// keys of which don't have a semantic ordering.
 152 ///
 153 /// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
 154 /// for more information.
 155 #[derive(Debug, Eq, PartialEq, Clone, Encodable, Decodable)]
 156 pub struct UnordSet<V: Eq + Hash> {
 157     inner: FxHashSet<V>,
 158 }
 159
 160 impl<V: Eq + Hash> Default for UnordSet<V> {
 161     #[inline]
 162     fn default() -> Self {
 163         Self { inner: FxHashSet::default() }
 164     }
 165 }
 166
 167 impl<V: Eq + Hash> UnordSet<V> {
 168     #[inline]
 169     pub fn new() -> Self {
 170         Self { inner: Default::default() }
 171     }
 172
 173     #[inline]
 174     pub fn len(&self) -> usize {
 175         self.inner.len()
 176     }
 177
 178     #[inline]
 179     pub fn insert(&mut self, v: V) -> bool {
 180         self.inner.insert(v)
 181     }
 182
 183     #[inline]
 184     pub fn contains<Q: ?Sized>(&self, v: &Q) -> bool
 185     where
 186         V: Borrow<Q>,
 187         Q: Hash + Eq,
 188     {
 189         self.inner.contains(v)
 190     }
 191
 192     #[inline]
 193     pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> bool
 194     where
 195         V: Borrow<Q>,
 196         Q: Hash + Eq,
 197     {
 198         self.inner.remove(k)
 199     }
 200
 201     #[inline]
 202     pub fn items<'a>(&'a self) -> UnordItems<&'a V, impl Iterator<Item = &'a V>> {
 203         UnordItems(self.inner.iter())
 204     }
 205
 206     #[inline]
 207     pub fn into_items(self) -> UnordItems<V, impl Iterator<Item = V>> {
 208         UnordItems(self.inner.into_iter())
 209     }
 210
 211     #[inline]
 212     pub fn to_sorted<HCX>(&self, hcx: &HCX, cache_sort_key: bool) -> Vec<&V>
 213     where
 214         V: ToStableHashKey<HCX>,
 215     {
 216         let mut items: Vec<&V> = self.inner.iter().collect();
 217         if cache_sort_key {
 218             items.sort_by_cached_key(|k| k.to_stable_hash_key(hcx));
 219         } else {
 220             items.sort_unstable_by_key(|k| k.to_stable_hash_key(hcx));
 221         }
 222
 223         items
 224     }
 225
 226     #[inline]
 227     pub fn to_sorted_stable_ord(&self) -> Vec<V>
 228     where
 229         V: Ord + StableOrd + Copy,
 230     {
 231         let mut items: Vec<V> = self.inner.iter().copied().collect();
 232         items.sort_unstable();
 233         items
 234     }
 235
 236     #[inline]
 237     pub fn into_sorted<HCX>(self, hcx: &HCX, cache_sort_key: bool) -> Vec<V>
 238     where
 239         V: ToStableHashKey<HCX>,
 240     {
 241         let mut items: Vec<V> = self.inner.into_iter().collect();
 242         if cache_sort_key {
 243             items.sort_by_cached_key(|k| k.to_stable_hash_key(hcx));
 244         } else {
 245             items.sort_unstable_by_key(|k| k.to_stable_hash_key(hcx));
 246         }
 247
 248         items
 249     }
 250
 251     // We can safely extend this UnordSet from a set of unordered values because that
 252     // won't expose the internal ordering anywhere.
 253     #[inline]
 254     pub fn extend<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) {
 255         self.inner.extend(items.0)
 256     }
 257
 258     #[inline]
 259     pub fn clear(&mut self) {
 260         self.inner.clear();
 261     }
 262 }
 263
 264 impl<V: Hash + Eq> Extend<V> for UnordSet<V> {
 265     #[inline]
 266     fn extend<T: IntoIterator<Item = V>>(&mut self, iter: T) {
 267         self.inner.extend(iter)
 268     }
 269 }
 270
 271 impl<V: Hash + Eq> FromIterator<V> for UnordSet<V> {
 272     #[inline]
 273     fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
 274         UnordSet { inner: FxHashSet::from_iter(iter) }
 275     }
 276 }
 277
 278 impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordSet<V> {
 279     #[inline]
 280     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 281         hash_iter_order_independent(self.inner.iter(), hcx, hasher);
 282     }
 283 }
 284
 285 /// This is a map collection type that tries very hard to not expose
 286 /// any internal iteration. This is a useful property when trying to
 287 /// uphold the determinism invariants imposed by the query system.
 288 ///
 289 /// This collection type is a good choice for map-like collections the
 290 /// keys of which don't have a semantic ordering.
 291 ///
 292 /// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
 293 /// for more information.
 294 #[derive(Debug, Eq, PartialEq, Clone, Encodable, Decodable)]
 295 pub struct UnordMap<K: Eq + Hash, V> {
 296     inner: FxHashMap<K, V>,
 297 }
 298
 299 impl<K: Eq + Hash, V> Default for UnordMap<K, V> {
 300     #[inline]
 301     fn default() -> Self {
 302         Self { inner: FxHashMap::default() }
 303     }
 304 }
 305
 306 impl<K: Hash + Eq, V> Extend<(K, V)> for UnordMap<K, V> {
 307     #[inline]
 308     fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
 309         self.inner.extend(iter)
 310     }
 311 }
 312
 313 impl<K: Hash + Eq, V> FromIterator<(K, V)> for UnordMap<K, V> {
 314     #[inline]
 315     fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
 316         UnordMap { inner: FxHashMap::from_iter(iter) }
 317     }
 318 }
 319
 320 impl<K: Hash + Eq, V, I: Iterator<Item = (K, V)>> From<UnordItems<(K, V), I>> for UnordMap<K, V> {
 321     #[inline]
 322     fn from(items: UnordItems<(K, V), I>) -> Self {
 323         UnordMap { inner: FxHashMap::from_iter(items.0) }
 324     }
 325 }
 326
 327 impl<K: Eq + Hash, V> UnordMap<K, V> {
 328     #[inline]
 329     pub fn len(&self) -> usize {
 330         self.inner.len()
 331     }
 332
 333     #[inline]
 334     pub fn insert(&mut self, k: K, v: V) -> Option<V> {
 335         self.inner.insert(k, v)
 336     }
 337
 338     #[inline]
 339     pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
 340     where
 341         K: Borrow<Q>,
 342         Q: Hash + Eq,
 343     {
 344         self.inner.contains_key(k)
 345     }
 346
 347     #[inline]
 348     pub fn is_empty(&self) -> bool {
 349         self.inner.is_empty()
 350     }
 351
 352     #[inline]
 353     pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
 354         self.inner.entry(key)
 355     }
 356
 357     #[inline]
 358     pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
 359     where
 360         K: Borrow<Q>,
 361         Q: Hash + Eq,
 362     {
 363         self.inner.get(k)
 364     }
 365
 366     #[inline]
 367     pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
 368     where
 369         K: Borrow<Q>,
 370         Q: Hash + Eq,
 371     {
 372         self.inner.get_mut(k)
 373     }
 374
 375     #[inline]
 376     pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
 377     where
 378         K: Borrow<Q>,
 379         Q: Hash + Eq,
 380     {
 381         self.inner.remove(k)
 382     }
 383
 384     #[inline]
 385     pub fn items<'a>(&'a self) -> UnordItems<(&'a K, &'a V), impl Iterator<Item = (&'a K, &'a V)>> {
 386         UnordItems(self.inner.iter())
 387     }
 388
 389     #[inline]
 390     pub fn into_items(self) -> UnordItems<(K, V), impl Iterator<Item = (K, V)>> {
 391         UnordItems(self.inner.into_iter())
 392     }
 393
 394     // We can safely extend this UnordMap from a set of unordered values because that
 395     // won't expose the internal ordering anywhere.
 396     #[inline]
 397     pub fn extend<I: Iterator<Item = (K, V)>>(&mut self, items: UnordItems<(K, V), I>) {
 398         self.inner.extend(items.0)
 399     }
 400
 401     #[inline]
 402     pub fn to_sorted<HCX>(&self, hcx: &HCX, cache_sort_key: bool) -> Vec<(&K, &V)>
 403     where
 404         K: ToStableHashKey<HCX>,
 405     {
 406         let mut items: Vec<(&K, &V)> = self.inner.iter().collect();
 407         if cache_sort_key {
 408             items.sort_by_cached_key(|(k, _)| k.to_stable_hash_key(hcx));
 409         } else {
 410             items.sort_unstable_by_key(|(k, _)| k.to_stable_hash_key(hcx));
 411         }
 412
 413         items
 414     }
 415
 416     #[inline]
 417     pub fn to_sorted_stable_ord(&self) -> Vec<(K, &V)>
 418     where
 419         K: Ord + StableOrd + Copy,
 420     {
 421         let mut items: Vec<(K, &V)> = self.inner.iter().map(|(&k, v)| (k, v)).collect();
 422         items.sort_unstable_by_key(|&(k, _)| k);
 423         items
 424     }
 425
 426     #[inline]
 427     pub fn into_sorted<HCX>(self, hcx: &HCX, cache_sort_key: bool) -> Vec<(K, V)>
 428     where
 429         K: ToStableHashKey<HCX>,
 430     {
 431         let mut items: Vec<(K, V)> = self.inner.into_iter().collect();
 432         if cache_sort_key {
 433             items.sort_by_cached_key(|(k, _)| k.to_stable_hash_key(hcx));
 434         } else {
 435             items.sort_unstable_by_key(|(k, _)| k.to_stable_hash_key(hcx));
 436         }
 437         items
 438     }
 439
 440     #[inline]
 441     pub fn values_sorted<HCX>(&self, hcx: &HCX, cache_sort_key: bool) -> impl Iterator<Item = &V>
 442     where
 443         K: ToStableHashKey<HCX>,
 444     {
 445         let mut items: Vec<(&K, &V)> = self.inner.iter().collect();
 446         if cache_sort_key {
 447             items.sort_by_cached_key(|(k, _)| k.to_stable_hash_key(hcx));
 448         } else {
 449             items.sort_unstable_by_key(|(k, _)| k.to_stable_hash_key(hcx));
 450         }
 451         items.into_iter().map(|(_, v)| v)
 452     }
 453 }
 454
 455 impl<K, Q: ?Sized, V> Index<&Q> for UnordMap<K, V>
 456 where
 457     K: Eq + Hash + Borrow<Q>,
 458     Q: Eq + Hash,
 459 {
 460     type Output = V;
 461
 462     #[inline]
 463     fn index(&self, key: &Q) -> &V {
 464         &self.inner[key]
 465     }
 466 }
 467
 468 impl<HCX, K: Hash + Eq + HashStable<HCX>, V: HashStable<HCX>> HashStable<HCX> for UnordMap<K, V> {
 469     #[inline]
 470     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 471         hash_iter_order_independent(self.inner.iter(), hcx, hasher);
 472     }
 473 }
 474
 475 /// This is a collection type that tries very hard to not expose
 476 /// any internal iteration. This is a useful property when trying to
 477 /// uphold the determinism invariants imposed by the query system.
 478 ///
 479 /// This collection type is a good choice for collections the
 480 /// keys of which don't have a semantic ordering and don't implement
 481 /// `Hash` or `Eq`.
 482 ///
 483 /// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
 484 /// for more information.
 485 #[derive(Default, Debug, Eq, PartialEq, Clone, Encodable, Decodable)]
 486 pub struct UnordBag<V> {
 487     inner: Vec<V>,
 488 }
 489
 490 impl<V> UnordBag<V> {
 491     #[inline]
 492     pub fn new() -> Self {
 493         Self { inner: Default::default() }
 494     }
 495
 496     #[inline]
 497     pub fn len(&self) -> usize {
 498         self.inner.len()
 499     }
 500
 501     #[inline]
 502     pub fn push(&mut self, v: V) {
 503         self.inner.push(v);
 504     }
 505
 506     #[inline]
 507     pub fn items(&self) -> UnordItems<&V, impl Iterator<Item = &V>> {
 508         UnordItems(self.inner.iter())
 509     }
 510
 511     #[inline]
 512     pub fn into_items(self) -> UnordItems<V, impl Iterator<Item = V>> {
 513         UnordItems(self.inner.into_iter())
 514     }
 515
 516     // We can safely extend this UnordSet from a set of unordered values because that
 517     // won't expose the internal ordering anywhere.
 518     #[inline]
 519     pub fn extend<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) {
 520         self.inner.extend(items.0)
 521     }
 522 }
 523
 524 impl<T> Extend<T> for UnordBag<T> {
 525     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
 526         self.inner.extend(iter)
 527     }
 528 }
 529
 530 impl<T, I: Iterator<Item = T>> From<UnordItems<T, I>> for UnordBag<T> {
 531     fn from(value: UnordItems<T, I>) -> Self {
 532         UnordBag { inner: Vec::from_iter(value.0) }
 533     }
 534 }
 535
 536 impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordBag<V> {
 537     #[inline]
 538     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 539         hash_iter_order_independent(self.inner.iter(), hcx, hasher);
 540     }
 541 }
 542
 543 fn hash_iter_order_independent<
 544     HCX,
 545     T: HashStable<HCX>,
 546     I: Iterator<Item = T> + ExactSizeIterator,
 547 >(
 548     mut it: I,
 549     hcx: &mut HCX,
 550     hasher: &mut StableHasher,
 551 ) {
 552     let len = it.len();
 553     len.hash_stable(hcx, hasher);
 554
 555     match len {
 556         0 => {
 557             // We're done
 558         }
 559         1 => {
 560             // No need to instantiate a hasher
 561             it.next().unwrap().hash_stable(hcx, hasher);
 562         }
 563         _ => {
 564             let mut accumulator = Fingerprint::ZERO;
 565             for item in it {
 566                 let mut item_hasher = StableHasher::new();
 567                 item.hash_stable(hcx, &mut item_hasher);
 568                 let item_fingerprint: Fingerprint = item_hasher.finish();
 569                 accumulator = accumulator.combine_commutative(item_fingerprint);
 570             }
 571             accumulator.hash_stable(hcx, hasher);
 572         }
 573     }
 574 }
 575
 576 // Do not implement IntoIterator for the collections in this module.
 577 // They only exist to hide iteration order in the first place.
 578 impl<T> !IntoIterator for UnordBag<T> {}
 579 impl<V> !IntoIterator for UnordSet<V> {}
 580 impl<K, V> !IntoIterator for UnordMap<K, V> {}
 581 impl<T, I> !IntoIterator for UnordItems<T, I> {}