rustc_data_structures/
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
5use std::borrow::{Borrow, BorrowMut};
6use std::collections::hash_map::{Entry, OccupiedError};
7use std::hash::Hash;
8use std::iter::{Product, Sum};
9use std::ops::Index;
10
11use rustc_hash::{FxHashMap, FxHashSet};
12use rustc_macros::{Decodable_NoContext, Encodable_NoContext};
13
14use crate::fingerprint::Fingerprint;
15use crate::stable_hasher::{HashStable, StableCompare, StableHasher, ToStableHashKey};
16
17/// `UnordItems` is the order-less version of `Iterator`. It only contains methods
18/// that don't (easily) expose an ordering of the underlying items.
19///
20/// Most methods take an `Fn` where the `Iterator`-version takes an `FnMut`. This
21/// is to reduce the risk of accidentally leaking the internal order via the closure
22/// environment. Otherwise one could easily do something like
23///
24/// ```rust,ignore (pseudo code)
25/// let mut ordered = vec![];
26/// unordered_items.all(|x| ordered.push(x));
27/// ```
28///
29/// It's still possible to do the same thing with an `Fn` by using interior mutability,
30/// but the chance of doing it accidentally is reduced.
31#[derive(Clone)]
32pub struct UnordItems<T, I: Iterator<Item = T>>(I);
33
34impl<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<F: Fn(T) -> bool>(mut self, f: F) -> bool {
42        self.0.all(f)
43    }
44
45    #[inline]
46    pub fn any<F: Fn(T) -> bool>(mut self, f: F) -> bool {
47        self.0.any(f)
48    }
49
50    #[inline]
51    pub fn filter<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    #[inline]
101    pub fn flat_map<U, F, O>(self, f: F) -> UnordItems<O, impl Iterator<Item = O>>
102    where
103        U: IntoIterator<Item = O>,
104        F: Fn(T) -> U,
105    {
106        UnordItems(self.0.flat_map(f))
107    }
108
109    pub fn collect<C: From<UnordItems<T, I>>>(self) -> C {
110        self.into()
111    }
112}
113
114impl<T> UnordItems<T, std::iter::Empty<T>> {
115    pub fn empty() -> Self {
116        UnordItems(std::iter::empty())
117    }
118}
119
120impl<'a, T: Clone + 'a, I: Iterator<Item = &'a T>> UnordItems<&'a T, I> {
121    #[inline]
122    pub fn cloned(self) -> UnordItems<T, impl Iterator<Item = T>> {
123        UnordItems(self.0.cloned())
124    }
125}
126
127impl<'a, T: Copy + 'a, I: Iterator<Item = &'a T>> UnordItems<&'a T, I> {
128    #[inline]
129    pub fn copied(self) -> UnordItems<T, impl Iterator<Item = T>> {
130        UnordItems(self.0.copied())
131    }
132}
133
134impl<T, I: Iterator<Item = T>> UnordItems<T, I> {
135    #[inline]
136    pub fn into_sorted<HCX>(self, hcx: &HCX) -> Vec<T>
137    where
138        T: ToStableHashKey<HCX>,
139    {
140        self.collect_sorted(hcx, true)
141    }
142
143    #[inline]
144    pub fn into_sorted_stable_ord(self) -> Vec<T>
145    where
146        T: StableCompare,
147    {
148        self.collect_stable_ord_by_key(|x| x)
149    }
150
151    #[inline]
152    pub fn into_sorted_stable_ord_by_key<K, C>(self, project_to_key: C) -> Vec<T>
153    where
154        K: StableCompare,
155        C: for<'a> Fn(&'a T) -> &'a K,
156    {
157        self.collect_stable_ord_by_key(project_to_key)
158    }
159
160    #[inline]
161    pub fn collect_sorted<HCX, C>(self, hcx: &HCX, cache_sort_key: bool) -> C
162    where
163        T: ToStableHashKey<HCX>,
164        C: FromIterator<T> + BorrowMut<[T]>,
165    {
166        let mut items: C = self.0.collect();
167
168        let slice = items.borrow_mut();
169        if slice.len() > 1 {
170            if cache_sort_key {
171                slice.sort_by_cached_key(|x| x.to_stable_hash_key(hcx));
172            } else {
173                slice.sort_by_key(|x| x.to_stable_hash_key(hcx));
174            }
175        }
176
177        items
178    }
179
180    #[inline]
181    pub fn collect_stable_ord_by_key<K, C, P>(self, project_to_key: P) -> C
182    where
183        K: StableCompare,
184        P: for<'a> Fn(&'a T) -> &'a K,
185        C: FromIterator<T> + BorrowMut<[T]>,
186    {
187        let mut items: C = self.0.collect();
188
189        let slice = items.borrow_mut();
190        if slice.len() > 1 {
191            if !K::CAN_USE_UNSTABLE_SORT {
192                slice.sort_by(|a, b| {
193                    let a_key = project_to_key(a);
194                    let b_key = project_to_key(b);
195                    a_key.stable_cmp(b_key)
196                });
197            } else {
198                slice.sort_unstable_by(|a, b| {
199                    let a_key = project_to_key(a);
200                    let b_key = project_to_key(b);
201                    a_key.stable_cmp(b_key)
202                });
203            }
204        }
205
206        items
207    }
208}
209
210/// A marker trait specifying that `Self` can consume `UnordItems<_>` without
211/// exposing any internal ordering.
212///
213/// Note: right now this is just a marker trait. It could be extended to contain
214/// some useful, common methods though, like `len`, `clear`, or the various
215/// kinds of `to_sorted`.
216trait UnordCollection {}
217
218/// This is a set collection type that tries very hard to not expose
219/// any internal iteration. This is a useful property when trying to
220/// uphold the determinism invariants imposed by the query system.
221///
222/// This collection type is a good choice for set-like collections the
223/// keys of which don't have a semantic ordering.
224///
225/// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
226/// for more information.
227#[derive(Debug, Eq, PartialEq, Clone, Encodable_NoContext, Decodable_NoContext)]
228pub struct UnordSet<V: Eq + Hash> {
229    inner: FxHashSet<V>,
230}
231
232impl<V: Eq + Hash> UnordCollection for UnordSet<V> {}
233
234impl<V: Eq + Hash> Default for UnordSet<V> {
235    #[inline]
236    fn default() -> Self {
237        Self { inner: FxHashSet::default() }
238    }
239}
240
241impl<V: Eq + Hash> UnordSet<V> {
242    #[inline]
243    pub fn new() -> Self {
244        Self { inner: Default::default() }
245    }
246
247    #[inline]
248    pub fn with_capacity(capacity: usize) -> Self {
249        Self { inner: FxHashSet::with_capacity_and_hasher(capacity, Default::default()) }
250    }
251
252    #[inline]
253    pub fn len(&self) -> usize {
254        self.inner.len()
255    }
256
257    #[inline]
258    pub fn is_empty(&self) -> bool {
259        self.inner.is_empty()
260    }
261
262    /// If the set has only one element, returns it, otherwise returns `None`.
263    #[inline]
264    pub fn get_only(&self) -> Option<&V> {
265        if self.inner.len() == 1 { self.inner.iter().next() } else { None }
266    }
267
268    #[inline]
269    pub fn insert(&mut self, v: V) -> bool {
270        self.inner.insert(v)
271    }
272
273    #[inline]
274    pub fn contains<Q: ?Sized>(&self, v: &Q) -> bool
275    where
276        V: Borrow<Q>,
277        Q: Hash + Eq,
278    {
279        self.inner.contains(v)
280    }
281
282    #[inline]
283    pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> bool
284    where
285        V: Borrow<Q>,
286        Q: Hash + Eq,
287    {
288        self.inner.remove(k)
289    }
290
291    #[inline]
292    pub fn items(&self) -> UnordItems<&V, impl Iterator<Item = &V>> {
293        UnordItems(self.inner.iter())
294    }
295
296    #[inline]
297    pub fn into_items(self) -> UnordItems<V, impl Iterator<Item = V>> {
298        UnordItems(self.inner.into_iter())
299    }
300
301    /// Returns the items of this set in stable sort order (as defined by `ToStableHashKey`).
302    ///
303    /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or
304    /// [slice::sort_unstable_by_key] will be used for sorting the vec. Use
305    /// `cache_sort_key` when the [ToStableHashKey::to_stable_hash_key] implementation
306    /// for `V` is expensive (e.g. a `DefId -> DefPathHash` lookup).
307    #[inline]
308    pub fn to_sorted<HCX>(&self, hcx: &HCX, cache_sort_key: bool) -> Vec<&V>
309    where
310        V: ToStableHashKey<HCX>,
311    {
312        to_sorted_vec(hcx, self.inner.iter(), cache_sort_key, |&x| x)
313    }
314
315    /// Returns the items of this set in stable sort order (as defined by
316    /// `StableCompare`). This method is much more efficient than
317    /// `into_sorted` because it does not need to transform keys to their
318    /// `ToStableHashKey` equivalent.
319    #[inline]
320    pub fn to_sorted_stable_ord(&self) -> Vec<&V>
321    where
322        V: StableCompare,
323    {
324        let mut items: Vec<&V> = self.inner.iter().collect();
325        items.sort_unstable_by(|a, b| a.stable_cmp(*b));
326        items
327    }
328
329    /// Returns the items of this set in stable sort order (as defined by
330    /// `StableCompare`). This method is much more efficient than
331    /// `into_sorted` because it does not need to transform keys to their
332    /// `ToStableHashKey` equivalent.
333    #[inline]
334    pub fn into_sorted_stable_ord(self) -> Vec<V>
335    where
336        V: StableCompare,
337    {
338        let mut items: Vec<V> = self.inner.into_iter().collect();
339        items.sort_unstable_by(V::stable_cmp);
340        items
341    }
342
343    /// Returns the items of this set in stable sort order (as defined by `ToStableHashKey`).
344    ///
345    /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or
346    /// [slice::sort_unstable_by_key] will be used for sorting the vec. Use
347    /// `cache_sort_key` when the [ToStableHashKey::to_stable_hash_key] implementation
348    /// for `V` is expensive (e.g. a `DefId -> DefPathHash` lookup).
349    #[inline]
350    pub fn into_sorted<HCX>(self, hcx: &HCX, cache_sort_key: bool) -> Vec<V>
351    where
352        V: ToStableHashKey<HCX>,
353    {
354        to_sorted_vec(hcx, self.inner.into_iter(), cache_sort_key, |x| x)
355    }
356
357    #[inline]
358    pub fn clear(&mut self) {
359        self.inner.clear();
360    }
361}
362
363pub trait ExtendUnord<T> {
364    /// Extend this unord collection with the given `UnordItems`.
365    /// This method is called `extend_unord` instead of just `extend` so it
366    /// does not conflict with `Extend::extend`. Otherwise there would be many
367    /// places where the two methods would have to be explicitly disambiguated
368    /// via UFCS.
369    fn extend_unord<I: Iterator<Item = T>>(&mut self, items: UnordItems<T, I>);
370}
371
372// Note: it is important that `C` implements `UnordCollection` in addition to
373// `Extend`, otherwise this impl would leak the internal iteration order of
374// `items`, e.g. when calling `some_vec.extend_unord(some_unord_items)`.
375impl<C: Extend<T> + UnordCollection, T> ExtendUnord<T> for C {
376    #[inline]
377    fn extend_unord<I: Iterator<Item = T>>(&mut self, items: UnordItems<T, I>) {
378        self.extend(items.0)
379    }
380}
381
382impl<V: Hash + Eq> Extend<V> for UnordSet<V> {
383    #[inline]
384    fn extend<T: IntoIterator<Item = V>>(&mut self, iter: T) {
385        self.inner.extend(iter)
386    }
387}
388
389impl<V: Hash + Eq> FromIterator<V> for UnordSet<V> {
390    #[inline]
391    fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
392        UnordSet { inner: FxHashSet::from_iter(iter) }
393    }
394}
395
396impl<V: Hash + Eq> From<FxHashSet<V>> for UnordSet<V> {
397    fn from(value: FxHashSet<V>) -> Self {
398        UnordSet { inner: value }
399    }
400}
401
402impl<V: Hash + Eq, I: Iterator<Item = V>> From<UnordItems<V, I>> for UnordSet<V> {
403    fn from(value: UnordItems<V, I>) -> Self {
404        UnordSet { inner: FxHashSet::from_iter(value.0) }
405    }
406}
407
408impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordSet<V> {
409    #[inline]
410    fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
411        hash_iter_order_independent(self.inner.iter(), hcx, hasher);
412    }
413}
414
415/// This is a map collection type that tries very hard to not expose
416/// any internal iteration. This is a useful property when trying to
417/// uphold the determinism invariants imposed by the query system.
418///
419/// This collection type is a good choice for map-like collections the
420/// keys of which don't have a semantic ordering.
421///
422/// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
423/// for more information.
424#[derive(Debug, Eq, PartialEq, Clone, Encodable_NoContext, Decodable_NoContext)]
425pub struct UnordMap<K: Eq + Hash, V> {
426    inner: FxHashMap<K, V>,
427}
428
429impl<K: Eq + Hash, V> UnordCollection for UnordMap<K, V> {}
430
431impl<K: Eq + Hash, V> Default for UnordMap<K, V> {
432    #[inline]
433    fn default() -> Self {
434        Self { inner: FxHashMap::default() }
435    }
436}
437
438impl<K: Hash + Eq, V> Extend<(K, V)> for UnordMap<K, V> {
439    #[inline]
440    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
441        self.inner.extend(iter)
442    }
443}
444
445impl<K: Hash + Eq, V> FromIterator<(K, V)> for UnordMap<K, V> {
446    #[inline]
447    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
448        UnordMap { inner: FxHashMap::from_iter(iter) }
449    }
450}
451
452impl<K: Hash + Eq, V, I: Iterator<Item = (K, V)>> From<UnordItems<(K, V), I>> for UnordMap<K, V> {
453    #[inline]
454    fn from(items: UnordItems<(K, V), I>) -> Self {
455        UnordMap { inner: FxHashMap::from_iter(items.0) }
456    }
457}
458
459impl<K: Eq + Hash, V> UnordMap<K, V> {
460    #[inline]
461    pub fn with_capacity(capacity: usize) -> Self {
462        Self { inner: FxHashMap::with_capacity_and_hasher(capacity, Default::default()) }
463    }
464
465    #[inline]
466    pub fn len(&self) -> usize {
467        self.inner.len()
468    }
469
470    #[inline]
471    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
472        self.inner.insert(k, v)
473    }
474
475    #[inline]
476    pub fn try_insert(&mut self, k: K, v: V) -> Result<&mut V, OccupiedError<'_, K, V>> {
477        self.inner.try_insert(k, v)
478    }
479
480    #[inline]
481    pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
482    where
483        K: Borrow<Q>,
484        Q: Hash + Eq,
485    {
486        self.inner.contains_key(k)
487    }
488
489    #[inline]
490    pub fn is_empty(&self) -> bool {
491        self.inner.is_empty()
492    }
493
494    #[inline]
495    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
496        self.inner.entry(key)
497    }
498
499    #[inline]
500    pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
501    where
502        K: Borrow<Q>,
503        Q: Hash + Eq,
504    {
505        self.inner.get(k)
506    }
507
508    #[inline]
509    pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
510    where
511        K: Borrow<Q>,
512        Q: Hash + Eq,
513    {
514        self.inner.get_mut(k)
515    }
516
517    #[inline]
518    pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
519    where
520        K: Borrow<Q>,
521        Q: Hash + Eq,
522    {
523        self.inner.remove(k)
524    }
525
526    #[inline]
527    pub fn items(&self) -> UnordItems<(&K, &V), impl Iterator<Item = (&K, &V)>> {
528        UnordItems(self.inner.iter())
529    }
530
531    #[inline]
532    pub fn into_items(self) -> UnordItems<(K, V), impl Iterator<Item = (K, V)>> {
533        UnordItems(self.inner.into_iter())
534    }
535
536    #[inline]
537    pub fn keys(&self) -> UnordItems<&K, impl Iterator<Item = &K>> {
538        UnordItems(self.inner.keys())
539    }
540
541    /// Returns the entries of this map in stable sort order (as defined by `ToStableHashKey`).
542    ///
543    /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or
544    /// [slice::sort_unstable_by_key] will be used for sorting the vec. Use
545    /// `cache_sort_key` when the [ToStableHashKey::to_stable_hash_key] implementation
546    /// for `K` is expensive (e.g. a `DefId -> DefPathHash` lookup).
547    #[inline]
548    pub fn to_sorted<HCX>(&self, hcx: &HCX, cache_sort_key: bool) -> Vec<(&K, &V)>
549    where
550        K: ToStableHashKey<HCX>,
551    {
552        to_sorted_vec(hcx, self.inner.iter(), cache_sort_key, |&(k, _)| k)
553    }
554
555    /// Returns the entries of this map in stable sort order (as defined by `StableCompare`).
556    /// This method can be much more efficient than `into_sorted` because it does not need
557    /// to transform keys to their `ToStableHashKey` equivalent.
558    #[inline]
559    pub fn to_sorted_stable_ord(&self) -> Vec<(&K, &V)>
560    where
561        K: StableCompare,
562    {
563        let mut items: Vec<_> = self.inner.iter().collect();
564        items.sort_unstable_by(|(a, _), (b, _)| a.stable_cmp(*b));
565        items
566    }
567
568    /// Returns the entries of this map in stable sort order (as defined by `ToStableHashKey`).
569    ///
570    /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or
571    /// [slice::sort_unstable_by_key] will be used for sorting the vec. Use
572    /// `cache_sort_key` when the [ToStableHashKey::to_stable_hash_key] implementation
573    /// for `K` is expensive (e.g. a `DefId -> DefPathHash` lookup).
574    #[inline]
575    pub fn into_sorted<HCX>(self, hcx: &HCX, cache_sort_key: bool) -> Vec<(K, V)>
576    where
577        K: ToStableHashKey<HCX>,
578    {
579        to_sorted_vec(hcx, self.inner.into_iter(), cache_sort_key, |(k, _)| k)
580    }
581
582    /// Returns the entries of this map in stable sort order (as defined by `StableCompare`).
583    /// This method can be much more efficient than `into_sorted` because it does not need
584    /// to transform keys to their `ToStableHashKey` equivalent.
585    #[inline]
586    pub fn into_sorted_stable_ord(self) -> Vec<(K, V)>
587    where
588        K: StableCompare,
589    {
590        let mut items: Vec<(K, V)> = self.inner.into_iter().collect();
591        items.sort_unstable_by(|a, b| a.0.stable_cmp(&b.0));
592        items
593    }
594
595    /// Returns the values of this map in stable sort order (as defined by K's
596    /// `ToStableHashKey` implementation).
597    ///
598    /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or
599    /// [slice::sort_unstable_by_key] will be used for sorting the vec. Use
600    /// `cache_sort_key` when the [ToStableHashKey::to_stable_hash_key] implementation
601    /// for `K` is expensive (e.g. a `DefId -> DefPathHash` lookup).
602    #[inline]
603    pub fn values_sorted<HCX>(&self, hcx: &HCX, cache_sort_key: bool) -> impl Iterator<Item = &V>
604    where
605        K: ToStableHashKey<HCX>,
606    {
607        to_sorted_vec(hcx, self.inner.iter(), cache_sort_key, |&(k, _)| k)
608            .into_iter()
609            .map(|(_, v)| v)
610    }
611
612    #[inline]
613    pub fn clear(&mut self) {
614        self.inner.clear()
615    }
616}
617
618impl<K, Q: ?Sized, V> Index<&Q> for UnordMap<K, V>
619where
620    K: Eq + Hash + Borrow<Q>,
621    Q: Eq + Hash,
622{
623    type Output = V;
624
625    #[inline]
626    fn index(&self, key: &Q) -> &V {
627        &self.inner[key]
628    }
629}
630
631impl<HCX, K: Hash + Eq + HashStable<HCX>, V: HashStable<HCX>> HashStable<HCX> for UnordMap<K, V> {
632    #[inline]
633    fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
634        hash_iter_order_independent(self.inner.iter(), hcx, hasher);
635    }
636}
637
638/// This is a collection type that tries very hard to not expose
639/// any internal iteration. This is a useful property when trying to
640/// uphold the determinism invariants imposed by the query system.
641///
642/// This collection type is a good choice for collections the
643/// keys of which don't have a semantic ordering and don't implement
644/// `Hash` or `Eq`.
645///
646/// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
647/// for more information.
648#[derive(Default, Debug, Eq, PartialEq, Clone, Encodable_NoContext, Decodable_NoContext)]
649pub struct UnordBag<V> {
650    inner: Vec<V>,
651}
652
653impl<V> UnordBag<V> {
654    #[inline]
655    pub fn new() -> Self {
656        Self { inner: Default::default() }
657    }
658
659    #[inline]
660    pub fn len(&self) -> usize {
661        self.inner.len()
662    }
663
664    #[inline]
665    pub fn push(&mut self, v: V) {
666        self.inner.push(v);
667    }
668
669    #[inline]
670    pub fn items(&self) -> UnordItems<&V, impl Iterator<Item = &V>> {
671        UnordItems(self.inner.iter())
672    }
673
674    #[inline]
675    pub fn into_items(self) -> UnordItems<V, impl Iterator<Item = V>> {
676        UnordItems(self.inner.into_iter())
677    }
678}
679
680impl<T> UnordCollection for UnordBag<T> {}
681
682impl<T> Extend<T> for UnordBag<T> {
683    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
684        self.inner.extend(iter)
685    }
686}
687
688impl<T, I: Iterator<Item = T>> From<UnordItems<T, I>> for UnordBag<T> {
689    fn from(value: UnordItems<T, I>) -> Self {
690        UnordBag { inner: Vec::from_iter(value.0) }
691    }
692}
693
694impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordBag<V> {
695    #[inline]
696    fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
697        hash_iter_order_independent(self.inner.iter(), hcx, hasher);
698    }
699}
700
701#[inline]
702fn to_sorted_vec<HCX, T, K, I>(
703    hcx: &HCX,
704    iter: I,
705    cache_sort_key: bool,
706    extract_key: fn(&T) -> &K,
707) -> Vec<T>
708where
709    I: Iterator<Item = T>,
710    K: ToStableHashKey<HCX>,
711{
712    let mut items: Vec<T> = iter.collect();
713    if cache_sort_key {
714        items.sort_by_cached_key(|x| extract_key(x).to_stable_hash_key(hcx));
715    } else {
716        items.sort_unstable_by_key(|x| extract_key(x).to_stable_hash_key(hcx));
717    }
718
719    items
720}
721
722fn hash_iter_order_independent<
723    HCX,
724    T: HashStable<HCX>,
725    I: Iterator<Item = T> + ExactSizeIterator,
726>(
727    mut it: I,
728    hcx: &mut HCX,
729    hasher: &mut StableHasher,
730) {
731    let len = it.len();
732    len.hash_stable(hcx, hasher);
733
734    match len {
735        0 => {
736            // We're done
737        }
738        1 => {
739            // No need to instantiate a hasher
740            it.next().unwrap().hash_stable(hcx, hasher);
741        }
742        _ => {
743            let mut accumulator = Fingerprint::ZERO;
744            for item in it {
745                let mut item_hasher = StableHasher::new();
746                item.hash_stable(hcx, &mut item_hasher);
747                let item_fingerprint: Fingerprint = item_hasher.finish();
748                accumulator = accumulator.combine_commutative(item_fingerprint);
749            }
750            accumulator.hash_stable(hcx, hasher);
751        }
752    }
753}
754
755// Do not implement IntoIterator for the collections in this module.
756// They only exist to hide iteration order in the first place.
757impl<T> !IntoIterator for UnordBag<T> {}
758impl<V> !IntoIterator for UnordSet<V> {}
759impl<K, V> !IntoIterator for UnordMap<K, V> {}
760impl<T, I> !IntoIterator for UnordItems<T, I> {}
rustc_data_structures/unord.rs

rustc_data_structures/
unord.rs
