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.
5 use rustc_hash::{FxHashMap, FxHashSet};
6 use smallvec::SmallVec;
9 collections::hash_map::Entry,
16 fingerprint::Fingerprint,
17 stable_hasher::{HashStable, StableHasher, StableOrd, ToStableHashKey},
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.
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
27 /// ```rust,ignore (pseudo code)
28 /// let mut ordered = vec![];
29 /// unordered_items.all(|x| ordered.push(x));
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);
36 impl<T, I: Iterator<Item = T>> UnordItems<T, I> {
38 pub fn map<U, F: Fn(T) -> U>(self, f: F) -> UnordItems<U, impl Iterator<Item = U>> {
39 UnordItems(self.0.map(f))
43 pub fn all<F: Fn(T) -> bool>(mut self, f: F) -> bool {
48 pub fn any<F: Fn(T) -> bool>(mut self, f: F) -> bool {
53 pub fn filter<F: Fn(&T) -> bool>(self, f: F) -> UnordItems<T, impl Iterator<Item = T>> {
54 UnordItems(self.0.filter(f))
58 pub fn filter_map<U, F: Fn(T) -> Option<U>>(
61 ) -> UnordItems<U, impl Iterator<Item = U>> {
62 UnordItems(self.0.filter_map(f))
66 pub fn max(self) -> Option<T>
74 pub fn min(self) -> Option<T>
82 pub fn sum<S>(self) -> S
90 pub fn product<S>(self) -> S
98 pub fn count(self) -> usize {
103 pub fn flat_map<U, F, O>(self, f: F) -> UnordItems<O, impl Iterator<Item = O>>
105 U: IntoIterator<Item = O>,
108 UnordItems(self.0.flat_map(f))
112 impl<'a, T: Clone + 'a, I: Iterator<Item = &'a T>> UnordItems<&'a T, I> {
114 pub fn cloned(self) -> UnordItems<T, impl Iterator<Item = T>> {
115 UnordItems(self.0.cloned())
119 impl<'a, T: Copy + 'a, I: Iterator<Item = &'a T>> UnordItems<&'a T, I> {
121 pub fn copied(self) -> UnordItems<T, impl Iterator<Item = T>> {
122 UnordItems(self.0.copied())
126 impl<T: Ord, I: Iterator<Item = T>> UnordItems<T, I> {
127 pub fn into_sorted<HCX>(self, hcx: &HCX) -> Vec<T>
129 T: ToStableHashKey<HCX>,
131 let mut items: Vec<T> = self.0.collect();
132 items.sort_by_cached_key(|x| x.to_stable_hash_key(hcx));
136 pub fn into_sorted_small_vec<HCX, const LEN: usize>(self, hcx: &HCX) -> SmallVec<[T; LEN]>
138 T: ToStableHashKey<HCX>,
140 let mut items: SmallVec<[T; LEN]> = self.0.collect();
141 items.sort_by_cached_key(|x| x.to_stable_hash_key(hcx));
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.
150 /// This collection type is a good choice for set-like collections the
151 /// keys of which don't have a semantic ordering.
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> {
160 impl<V: Eq + Hash> Default for UnordSet<V> {
162 fn default() -> Self {
163 Self { inner: FxHashSet::default() }
167 impl<V: Eq + Hash> UnordSet<V> {
169 pub fn new() -> Self {
170 Self { inner: Default::default() }
174 pub fn len(&self) -> usize {
179 pub fn insert(&mut self, v: V) -> bool {
184 pub fn contains<Q: ?Sized>(&self, v: &Q) -> bool
189 self.inner.contains(v)
193 pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> bool
202 pub fn items<'a>(&'a self) -> UnordItems<&'a V, impl Iterator<Item = &'a V>> {
203 UnordItems(self.inner.iter())
207 pub fn into_items(self) -> UnordItems<V, impl Iterator<Item = V>> {
208 UnordItems(self.inner.into_iter())
211 /// Returns the items of this set in stable sort order (as defined by `ToStableHashKey`).
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).
218 pub fn to_sorted<HCX>(&self, hcx: &HCX, cache_sort_key: bool) -> Vec<&V>
220 V: ToStableHashKey<HCX>,
222 to_sorted_vec(hcx, self.inner.iter(), cache_sort_key, |&x| x)
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.
230 pub fn to_sorted_stable_ord(&self) -> Vec<V>
232 V: Ord + StableOrd + Copy,
234 let mut items: Vec<V> = self.inner.iter().copied().collect();
235 items.sort_unstable();
239 /// Returns the items of this set in stable sort order (as defined by `ToStableHashKey`).
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).
246 pub fn into_sorted<HCX>(self, hcx: &HCX, cache_sort_key: bool) -> Vec<V>
248 V: ToStableHashKey<HCX>,
250 to_sorted_vec(hcx, self.inner.into_iter(), cache_sort_key, |x| x)
253 // We can safely extend this UnordSet from a set of unordered values because that
254 // won't expose the internal ordering anywhere.
256 pub fn extend<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) {
257 self.inner.extend(items.0)
261 pub fn clear(&mut self) {
266 impl<V: Hash + Eq> Extend<V> for UnordSet<V> {
268 fn extend<T: IntoIterator<Item = V>>(&mut self, iter: T) {
269 self.inner.extend(iter)
273 impl<V: Hash + Eq> FromIterator<V> for UnordSet<V> {
275 fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
276 UnordSet { inner: FxHashSet::from_iter(iter) }
280 impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordSet<V> {
282 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
283 hash_iter_order_independent(self.inner.iter(), hcx, hasher);
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.
291 /// This collection type is a good choice for map-like collections the
292 /// keys of which don't have a semantic ordering.
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>,
301 impl<K: Eq + Hash, V> Default for UnordMap<K, V> {
303 fn default() -> Self {
304 Self { inner: FxHashMap::default() }
308 impl<K: Hash + Eq, V> Extend<(K, V)> for UnordMap<K, V> {
310 fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
311 self.inner.extend(iter)
315 impl<K: Hash + Eq, V> FromIterator<(K, V)> for UnordMap<K, V> {
317 fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
318 UnordMap { inner: FxHashMap::from_iter(iter) }
322 impl<K: Hash + Eq, V, I: Iterator<Item = (K, V)>> From<UnordItems<(K, V), I>> for UnordMap<K, V> {
324 fn from(items: UnordItems<(K, V), I>) -> Self {
325 UnordMap { inner: FxHashMap::from_iter(items.0) }
329 impl<K: Eq + Hash, V> UnordMap<K, V> {
331 pub fn len(&self) -> usize {
336 pub fn insert(&mut self, k: K, v: V) -> Option<V> {
337 self.inner.insert(k, v)
341 pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
346 self.inner.contains_key(k)
350 pub fn is_empty(&self) -> bool {
351 self.inner.is_empty()
355 pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
356 self.inner.entry(key)
360 pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
369 pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
374 self.inner.get_mut(k)
378 pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
387 pub fn items<'a>(&'a self) -> UnordItems<(&'a K, &'a V), impl Iterator<Item = (&'a K, &'a V)>> {
388 UnordItems(self.inner.iter())
392 pub fn into_items(self) -> UnordItems<(K, V), impl Iterator<Item = (K, V)>> {
393 UnordItems(self.inner.into_iter())
396 // We can safely extend this UnordMap from a set of unordered values because that
397 // won't expose the internal ordering anywhere.
399 pub fn extend<I: Iterator<Item = (K, V)>>(&mut self, items: UnordItems<(K, V), I>) {
400 self.inner.extend(items.0)
403 /// Returns the entries of this map in stable sort order (as defined by `ToStableHashKey`).
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).
410 pub fn to_sorted<HCX>(&self, hcx: &HCX, cache_sort_key: bool) -> Vec<(&K, &V)>
412 K: ToStableHashKey<HCX>,
414 to_sorted_vec(hcx, self.inner.iter(), cache_sort_key, |&(k, _)| k)
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.
421 pub fn to_sorted_stable_ord(&self) -> Vec<(K, &V)>
423 K: Ord + StableOrd + Copy,
425 let mut items: Vec<(K, &V)> = self.inner.iter().map(|(&k, v)| (k, v)).collect();
426 items.sort_unstable_by_key(|&(k, _)| k);
430 /// Returns the entries of this map in stable sort order (as defined by `ToStableHashKey`).
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).
437 pub fn into_sorted<HCX>(self, hcx: &HCX, cache_sort_key: bool) -> Vec<(K, V)>
439 K: ToStableHashKey<HCX>,
441 to_sorted_vec(hcx, self.inner.into_iter(), cache_sort_key, |(k, _)| k)
444 /// Returns the values of this map in stable sort order (as defined by K's
445 /// `ToStableHashKey` implementation).
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).
452 pub fn values_sorted<HCX>(&self, hcx: &HCX, cache_sort_key: bool) -> impl Iterator<Item = &V>
454 K: ToStableHashKey<HCX>,
456 to_sorted_vec(hcx, self.inner.iter(), cache_sort_key, |&(k, _)| k)
462 impl<K, Q: ?Sized, V> Index<&Q> for UnordMap<K, V>
464 K: Eq + Hash + Borrow<Q>,
470 fn index(&self, key: &Q) -> &V {
475 impl<HCX, K: Hash + Eq + HashStable<HCX>, V: HashStable<HCX>> HashStable<HCX> for UnordMap<K, V> {
477 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
478 hash_iter_order_independent(self.inner.iter(), hcx, hasher);
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.
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
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> {
497 impl<V> UnordBag<V> {
499 pub fn new() -> Self {
500 Self { inner: Default::default() }
504 pub fn len(&self) -> usize {
509 pub fn push(&mut self, v: V) {
514 pub fn items(&self) -> UnordItems<&V, impl Iterator<Item = &V>> {
515 UnordItems(self.inner.iter())
519 pub fn into_items(self) -> UnordItems<V, impl Iterator<Item = V>> {
520 UnordItems(self.inner.into_iter())
523 // We can safely extend this UnordSet from a set of unordered values because that
524 // won't expose the internal ordering anywhere.
526 pub fn extend<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) {
527 self.inner.extend(items.0)
531 impl<T> Extend<T> for UnordBag<T> {
532 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
533 self.inner.extend(iter)
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) }
543 impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordBag<V> {
545 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
546 hash_iter_order_independent(self.inner.iter(), hcx, hasher);
551 fn to_sorted_vec<HCX, T, K, I>(
554 cache_sort_key: bool,
555 extract_key: fn(&T) -> &K,
558 I: Iterator<Item = T>,
559 K: ToStableHashKey<HCX>,
561 let mut items: Vec<T> = iter.collect();
563 items.sort_by_cached_key(|x| extract_key(x).to_stable_hash_key(hcx));
565 items.sort_unstable_by_key(|x| extract_key(x).to_stable_hash_key(hcx));
571 fn hash_iter_order_independent<
574 I: Iterator<Item = T> + ExactSizeIterator,
578 hasher: &mut StableHasher,
581 len.hash_stable(hcx, hasher);
588 // No need to instantiate a hasher
589 it.next().unwrap().hash_stable(hcx, hasher);
592 let mut accumulator = Fingerprint::ZERO;
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);
599 accumulator.hash_stable(hcx, hasher);
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> {}