]>
Commit | Line | Data |
---|---|---|
2b03887a FG |
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, | |
9c376795 | 9 | collections::hash_map::Entry, |
2b03887a FG |
10 | hash::Hash, |
11 | iter::{Product, Sum}, | |
9c376795 | 12 | ops::Index, |
2b03887a FG |
13 | }; |
14 | ||
15 | use crate::{ | |
16 | fingerprint::Fingerprint, | |
9c376795 | 17 | stable_hasher::{HashStable, StableHasher, StableOrd, ToStableHashKey}, |
2b03887a FG |
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] | |
9c376795 | 43 | pub fn all<F: Fn(T) -> bool>(mut self, f: F) -> bool { |
2b03887a FG |
44 | self.0.all(f) |
45 | } | |
46 | ||
47 | #[inline] | |
9c376795 | 48 | pub fn any<F: Fn(T) -> bool>(mut self, f: F) -> bool { |
2b03887a FG |
49 | self.0.any(f) |
50 | } | |
51 | ||
52 | #[inline] | |
9c376795 | 53 | pub fn filter<F: Fn(&T) -> bool>(self, f: F) -> UnordItems<T, impl Iterator<Item = T>> { |
2b03887a FG |
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 | } | |
9c376795 FG |
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 | } | |
2b03887a FG |
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> { | |
9c376795 | 161 | #[inline] |
2b03887a FG |
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 | ||
9c376795 FG |
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 | ||
2b03887a FG |
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 | ||
9c376795 FG |
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 | ||
2b03887a FG |
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 | } | |
9c376795 FG |
259 | |
260 | #[inline] | |
261 | pub fn clear(&mut self) { | |
262 | self.inner.clear(); | |
263 | } | |
2b03887a FG |
264 | } |
265 | ||
266 | impl<V: Hash + Eq> Extend<V> for UnordSet<V> { | |
9c376795 | 267 | #[inline] |
2b03887a FG |
268 | fn extend<T: IntoIterator<Item = V>>(&mut self, iter: T) { |
269 | self.inner.extend(iter) | |
270 | } | |
271 | } | |
272 | ||
9c376795 FG |
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 | ||
2b03887a FG |
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> { | |
9c376795 | 302 | #[inline] |
2b03887a FG |
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> { | |
9c376795 | 309 | #[inline] |
2b03887a FG |
310 | fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) { |
311 | self.inner.extend(iter) | |
312 | } | |
313 | } | |
314 | ||
9c376795 FG |
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 | ||
2b03887a FG |
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 | ||
9c376795 FG |
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 | ||
2b03887a FG |
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 | } | |
9c376795 FG |
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 | } | |
2b03887a FG |
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] | |
9c376795 | 514 | pub fn items(&self) -> UnordItems<&V, impl Iterator<Item = &V>> { |
2b03887a FG |
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 | ||
9c376795 FG |
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 | ||
2b03887a FG |
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 | ||
9c376795 FG |
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 | ||
2b03887a FG |
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> {} |