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     /// Returns the items of this set in stable sort order (as defined by `ToStableHashKey`).
 212     ///
 213     /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or
 214     /// [slice::sort_unstable_by_key] will be used for sorting the vec. Use
 215     /// `cache_sort_key` when the [ToStableHashKey::to_stable_hash_key] implementation
 216     /// for `V` is expensive (e.g. a `DefId -> DefPathHash` lookup).
 217     #[inline]
 218     pub fn to_sorted<HCX>(&self, hcx: &HCX, cache_sort_key: bool) -> Vec<&V>
 219     where
 220         V: ToStableHashKey<HCX>,
 221     {
 222         to_sorted_vec(hcx, self.inner.iter(), cache_sort_key, |&x| x)
 223     }
 224
 225     /// Returns the items of this set in stable sort order (as defined by
 226     /// `StableOrd`). This method is much more efficient than
 227     /// `into_sorted` because it does not need to transform keys to their
 228     /// `ToStableHashKey` equivalent.
 229     #[inline]
 230     pub fn to_sorted_stable_ord(&self) -> Vec<V>
 231     where
 232         V: Ord + StableOrd + Copy,
 233     {
 234         let mut items: Vec<V> = self.inner.iter().copied().collect();
 235         items.sort_unstable();
 236         items
 237     }
 238
 239     /// Returns the items of this set in stable sort order (as defined by `ToStableHashKey`).
 240     ///
 241     /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or
 242     /// [slice::sort_unstable_by_key] will be used for sorting the vec. Use
 243     /// `cache_sort_key` when the [ToStableHashKey::to_stable_hash_key] implementation
 244     /// for `V` is expensive (e.g. a `DefId -> DefPathHash` lookup).
 245     #[inline]
 246     pub fn into_sorted<HCX>(self, hcx: &HCX, cache_sort_key: bool) -> Vec<V>
 247     where
 248         V: ToStableHashKey<HCX>,
 249     {
 250         to_sorted_vec(hcx, self.inner.into_iter(), cache_sort_key, |x| x)
 251     }
 252
 253     // We can safely extend this UnordSet from a set of unordered values because that
 254     // won't expose the internal ordering anywhere.
 255     #[inline]
 256     pub fn extend<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) {
 257         self.inner.extend(items.0)
 258     }
 259
 260     #[inline]
 261     pub fn clear(&mut self) {
 262         self.inner.clear();
 263     }
 264 }
 265
 266 impl<V: Hash + Eq> Extend<V> for UnordSet<V> {
 267     #[inline]
 268     fn extend<T: IntoIterator<Item = V>>(&mut self, iter: T) {
 269         self.inner.extend(iter)
 270     }
 271 }
 272
 273 impl<V: Hash + Eq> FromIterator<V> for UnordSet<V> {
 274     #[inline]
 275     fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
 276         UnordSet { inner: FxHashSet::from_iter(iter) }
 277     }
 278 }
 279
 280 impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordSet<V> {
 281     #[inline]
 282     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 283         hash_iter_order_independent(self.inner.iter(), hcx, hasher);
 284     }
 285 }
 286
 287 /// This is a map collection type that tries very hard to not expose
 288 /// any internal iteration. This is a useful property when trying to
 289 /// uphold the determinism invariants imposed by the query system.
 290 ///
 291 /// This collection type is a good choice for map-like collections the
 292 /// keys of which don't have a semantic ordering.
 293 ///
 294 /// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
 295 /// for more information.
 296 #[derive(Debug, Eq, PartialEq, Clone, Encodable, Decodable)]
 297 pub struct UnordMap<K: Eq + Hash, V> {
 298     inner: FxHashMap<K, V>,
 299 }
 300
 301 impl<K: Eq + Hash, V> Default for UnordMap<K, V> {
 302     #[inline]
 303     fn default() -> Self {
 304         Self { inner: FxHashMap::default() }
 305     }
 306 }
 307
 308 impl<K: Hash + Eq, V> Extend<(K, V)> for UnordMap<K, V> {
 309     #[inline]
 310     fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
 311         self.inner.extend(iter)
 312     }
 313 }
 314
 315 impl<K: Hash + Eq, V> FromIterator<(K, V)> for UnordMap<K, V> {
 316     #[inline]
 317     fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
 318         UnordMap { inner: FxHashMap::from_iter(iter) }
 319     }
 320 }
 321
 322 impl<K: Hash + Eq, V, I: Iterator<Item = (K, V)>> From<UnordItems<(K, V), I>> for UnordMap<K, V> {
 323     #[inline]
 324     fn from(items: UnordItems<(K, V), I>) -> Self {
 325         UnordMap { inner: FxHashMap::from_iter(items.0) }
 326     }
 327 }
 328
 329 impl<K: Eq + Hash, V> UnordMap<K, V> {
 330     #[inline]
 331     pub fn len(&self) -> usize {
 332         self.inner.len()
 333     }
 334
 335     #[inline]
 336     pub fn insert(&mut self, k: K, v: V) -> Option<V> {
 337         self.inner.insert(k, v)
 338     }
 339
 340     #[inline]
 341     pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
 342     where
 343         K: Borrow<Q>,
 344         Q: Hash + Eq,
 345     {
 346         self.inner.contains_key(k)
 347     }
 348
 349     #[inline]
 350     pub fn is_empty(&self) -> bool {
 351         self.inner.is_empty()
 352     }
 353
 354     #[inline]
 355     pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
 356         self.inner.entry(key)
 357     }
 358
 359     #[inline]
 360     pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
 361     where
 362         K: Borrow<Q>,
 363         Q: Hash + Eq,
 364     {
 365         self.inner.get(k)
 366     }
 367
 368     #[inline]
 369     pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
 370     where
 371         K: Borrow<Q>,
 372         Q: Hash + Eq,
 373     {
 374         self.inner.get_mut(k)
 375     }
 376
 377     #[inline]
 378     pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
 379     where
 380         K: Borrow<Q>,
 381         Q: Hash + Eq,
 382     {
 383         self.inner.remove(k)
 384     }
 385
 386     #[inline]
 387     pub fn items<'a>(&'a self) -> UnordItems<(&'a K, &'a V), impl Iterator<Item = (&'a K, &'a V)>> {
 388         UnordItems(self.inner.iter())
 389     }
 390
 391     #[inline]
 392     pub fn into_items(self) -> UnordItems<(K, V), impl Iterator<Item = (K, V)>> {
 393         UnordItems(self.inner.into_iter())
 394     }
 395
 396     // We can safely extend this UnordMap from a set of unordered values because that
 397     // won't expose the internal ordering anywhere.
 398     #[inline]
 399     pub fn extend<I: Iterator<Item = (K, V)>>(&mut self, items: UnordItems<(K, V), I>) {
 400         self.inner.extend(items.0)
 401     }
 402
 403     /// Returns the entries of this map in stable sort order (as defined by `ToStableHashKey`).
 404     ///
 405     /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or
 406     /// [slice::sort_unstable_by_key] will be used for sorting the vec. Use
 407     /// `cache_sort_key` when the [ToStableHashKey::to_stable_hash_key] implementation
 408     /// for `K` is expensive (e.g. a `DefId -> DefPathHash` lookup).
 409     #[inline]
 410     pub fn to_sorted<HCX>(&self, hcx: &HCX, cache_sort_key: bool) -> Vec<(&K, &V)>
 411     where
 412         K: ToStableHashKey<HCX>,
 413     {
 414         to_sorted_vec(hcx, self.inner.iter(), cache_sort_key, |&(k, _)| k)
 415     }
 416
 417     /// Returns the entries of this map in stable sort order (as defined by `StableOrd`).
 418     /// This method can be much more efficient than `into_sorted` because it does not need
 419     /// to transform keys to their `ToStableHashKey` equivalent.
 420     #[inline]
 421     pub fn to_sorted_stable_ord(&self) -> Vec<(K, &V)>
 422     where
 423         K: Ord + StableOrd + Copy,
 424     {
 425         let mut items: Vec<(K, &V)> = self.inner.iter().map(|(&k, v)| (k, v)).collect();
 426         items.sort_unstable_by_key(|&(k, _)| k);
 427         items
 428     }
 429
 430     /// Returns the entries of this map in stable sort order (as defined by `ToStableHashKey`).
 431     ///
 432     /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or
 433     /// [slice::sort_unstable_by_key] will be used for sorting the vec. Use
 434     /// `cache_sort_key` when the [ToStableHashKey::to_stable_hash_key] implementation
 435     /// for `K` is expensive (e.g. a `DefId -> DefPathHash` lookup).
 436     #[inline]
 437     pub fn into_sorted<HCX>(self, hcx: &HCX, cache_sort_key: bool) -> Vec<(K, V)>
 438     where
 439         K: ToStableHashKey<HCX>,
 440     {
 441         to_sorted_vec(hcx, self.inner.into_iter(), cache_sort_key, |(k, _)| k)
 442     }
 443
 444     /// Returns the values of this map in stable sort order (as defined by K's
 445     /// `ToStableHashKey` implementation).
 446     ///
 447     /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or
 448     /// [slice::sort_unstable_by_key] will be used for sorting the vec. Use
 449     /// `cache_sort_key` when the [ToStableHashKey::to_stable_hash_key] implementation
 450     /// for `K` is expensive (e.g. a `DefId -> DefPathHash` lookup).
 451     #[inline]
 452     pub fn values_sorted<HCX>(&self, hcx: &HCX, cache_sort_key: bool) -> impl Iterator<Item = &V>
 453     where
 454         K: ToStableHashKey<HCX>,
 455     {
 456         to_sorted_vec(hcx, self.inner.iter(), cache_sort_key, |&(k, _)| k)
 457             .into_iter()
 458             .map(|(_, v)| v)
 459     }
 460 }
 461
 462 impl<K, Q: ?Sized, V> Index<&Q> for UnordMap<K, V>
 463 where
 464     K: Eq + Hash + Borrow<Q>,
 465     Q: Eq + Hash,
 466 {
 467     type Output = V;
 468
 469     #[inline]
 470     fn index(&self, key: &Q) -> &V {
 471         &self.inner[key]
 472     }
 473 }
 474
 475 impl<HCX, K: Hash + Eq + HashStable<HCX>, V: HashStable<HCX>> HashStable<HCX> for UnordMap<K, V> {
 476     #[inline]
 477     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 478         hash_iter_order_independent(self.inner.iter(), hcx, hasher);
 479     }
 480 }
 481
 482 /// This is a collection type that tries very hard to not expose
 483 /// any internal iteration. This is a useful property when trying to
 484 /// uphold the determinism invariants imposed by the query system.
 485 ///
 486 /// This collection type is a good choice for collections the
 487 /// keys of which don't have a semantic ordering and don't implement
 488 /// `Hash` or `Eq`.
 489 ///
 490 /// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
 491 /// for more information.
 492 #[derive(Default, Debug, Eq, PartialEq, Clone, Encodable, Decodable)]
 493 pub struct UnordBag<V> {
 494     inner: Vec<V>,
 495 }
 496
 497 impl<V> UnordBag<V> {
 498     #[inline]
 499     pub fn new() -> Self {
 500         Self { inner: Default::default() }
 501     }
 502
 503     #[inline]
 504     pub fn len(&self) -> usize {
 505         self.inner.len()
 506     }
 507
 508     #[inline]
 509     pub fn push(&mut self, v: V) {
 510         self.inner.push(v);
 511     }
 512
 513     #[inline]
 514     pub fn items(&self) -> UnordItems<&V, impl Iterator<Item = &V>> {
 515         UnordItems(self.inner.iter())
 516     }
 517
 518     #[inline]
 519     pub fn into_items(self) -> UnordItems<V, impl Iterator<Item = V>> {
 520         UnordItems(self.inner.into_iter())
 521     }
 522
 523     // We can safely extend this UnordSet from a set of unordered values because that
 524     // won't expose the internal ordering anywhere.
 525     #[inline]
 526     pub fn extend<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) {
 527         self.inner.extend(items.0)
 528     }
 529 }
 530
 531 impl<T> Extend<T> for UnordBag<T> {
 532     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
 533         self.inner.extend(iter)
 534     }
 535 }
 536
 537 impl<T, I: Iterator<Item = T>> From<UnordItems<T, I>> for UnordBag<T> {
 538     fn from(value: UnordItems<T, I>) -> Self {
 539         UnordBag { inner: Vec::from_iter(value.0) }
 540     }
 541 }
 542
 543 impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordBag<V> {
 544     #[inline]
 545     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 546         hash_iter_order_independent(self.inner.iter(), hcx, hasher);
 547     }
 548 }
 549
 550 #[inline]
 551 fn to_sorted_vec<HCX, T, K, I>(
 552     hcx: &HCX,
 553     iter: I,
 554     cache_sort_key: bool,
 555     extract_key: fn(&T) -> &K,
 556 ) -> Vec<T>
 557 where
 558     I: Iterator<Item = T>,
 559     K: ToStableHashKey<HCX>,
 560 {
 561     let mut items: Vec<T> = iter.collect();
 562     if cache_sort_key {
 563         items.sort_by_cached_key(|x| extract_key(x).to_stable_hash_key(hcx));
 564     } else {
 565         items.sort_unstable_by_key(|x| extract_key(x).to_stable_hash_key(hcx));
 566     }
 567
 568     items
 569 }
 570
 571 fn hash_iter_order_independent<
 572     HCX,
 573     T: HashStable<HCX>,
 574     I: Iterator<Item = T> + ExactSizeIterator,
 575 >(
 576     mut it: I,
 577     hcx: &mut HCX,
 578     hasher: &mut StableHasher,
 579 ) {
 580     let len = it.len();
 581     len.hash_stable(hcx, hasher);
 582
 583     match len {
 584         0 => {
 585             // We're done
 586         }
 587         1 => {
 588             // No need to instantiate a hasher
 589             it.next().unwrap().hash_stable(hcx, hasher);
 590         }
 591         _ => {
 592             let mut accumulator = Fingerprint::ZERO;
 593             for item in it {
 594                 let mut item_hasher = StableHasher::new();
 595                 item.hash_stable(hcx, &mut item_hasher);
 596                 let item_fingerprint: Fingerprint = item_hasher.finish();
 597                 accumulator = accumulator.combine_commutative(item_fingerprint);
 598             }
 599             accumulator.hash_stable(hcx, hasher);
 600         }
 601     }
 602 }
 603
 604 // Do not implement IntoIterator for the collections in this module.
 605 // They only exist to hide iteration order in the first place.
 606 impl<T> !IntoIterator for UnordBag<T> {}
 607 impl<V> !IntoIterator for UnordSet<V> {}
 608 impl<K, V> !IntoIterator for UnordMap<K, V> {}
 609 impl<T, I> !IntoIterator for UnordItems<T, I> {}