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

rustc_data_structures/
unord.rs
