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
;
14 fingerprint
::Fingerprint
,
15 stable_hasher
::{HashStable, StableHasher, ToStableHashKey}
,
18 /// `UnordItems` is the order-less version of `Iterator`. It only contains methods
19 /// that don't (easily) expose an ordering of the underlying items.
21 /// Most methods take an `Fn` where the `Iterator`-version takes an `FnMut`. This
22 /// is to reduce the risk of accidentally leaking the internal order via the closure
23 /// environment. Otherwise one could easily do something like
25 /// ```rust,ignore (pseudo code)
26 /// let mut ordered = vec![];
27 /// unordered_items.all(|x| ordered.push(x));
30 /// It's still possible to do the same thing with an `Fn` by using interior mutability,
31 /// but the chance of doing it accidentally is reduced.
32 pub struct UnordItems
<T
, I
: Iterator
<Item
= T
>>(I
);
34 impl<T
, I
: Iterator
<Item
= T
>> UnordItems
<T
, I
> {
36 pub fn map
<U
, F
: Fn(T
) -> U
>(self, f
: F
) -> UnordItems
<U
, impl Iterator
<Item
= U
>> {
37 UnordItems(self.0.map(f
))
41 pub fn all
<U
, F
: Fn(T
) -> bool
>(mut self, f
: F
) -> bool
{
46 pub fn any
<U
, F
: Fn(T
) -> bool
>(mut self, f
: F
) -> bool
{
51 pub fn filter
<U
, F
: Fn(&T
) -> bool
>(self, f
: F
) -> UnordItems
<T
, impl Iterator
<Item
= T
>> {
52 UnordItems(self.0.filter
(f
))
56 pub fn filter_map
<U
, F
: Fn(T
) -> Option
<U
>>(
59 ) -> UnordItems
<U
, impl Iterator
<Item
= U
>> {
60 UnordItems(self.0.filter_map
(f
))
64 pub fn max(self) -> Option
<T
>
72 pub fn min(self) -> Option
<T
>
80 pub fn sum
<S
>(self) -> S
88 pub fn product
<S
>(self) -> S
96 pub fn count(self) -> usize {
101 impl<'a
, T
: Clone
+ 'a
, I
: Iterator
<Item
= &'a T
>> UnordItems
<&'a T
, I
> {
103 pub fn cloned(self) -> UnordItems
<T
, impl Iterator
<Item
= T
>> {
104 UnordItems(self.0.cloned())
108 impl<'a
, T
: Copy
+ 'a
, I
: Iterator
<Item
= &'a T
>> UnordItems
<&'a T
, I
> {
110 pub fn copied(self) -> UnordItems
<T
, impl Iterator
<Item
= T
>> {
111 UnordItems(self.0.copied())
115 impl<T
: Ord
, I
: Iterator
<Item
= T
>> UnordItems
<T
, I
> {
116 pub fn into_sorted
<HCX
>(self, hcx
: &HCX
) -> Vec
<T
>
118 T
: ToStableHashKey
<HCX
>,
120 let mut items
: Vec
<T
> = self.0.collect();
121 items
.sort_by_cached_key(|x
| x
.to_stable_hash_key(hcx
));
125 pub fn into_sorted_small_vec
<HCX
, const LEN
: usize>(self, hcx
: &HCX
) -> SmallVec
<[T
; LEN
]>
127 T
: ToStableHashKey
<HCX
>,
129 let mut items
: SmallVec
<[T
; LEN
]> = self.0.collect();
130 items
.sort_by_cached_key(|x
| x
.to_stable_hash_key(hcx
));
135 /// This is a set collection type that tries very hard to not expose
136 /// any internal iteration. This is a useful property when trying to
137 /// uphold the determinism invariants imposed by the query system.
139 /// This collection type is a good choice for set-like collections the
140 /// keys of which don't have a semantic ordering.
142 /// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
143 /// for more information.
144 #[derive(Debug, Eq, PartialEq, Clone, Encodable, Decodable)]
145 pub struct UnordSet
<V
: Eq
+ Hash
> {
149 impl<V
: Eq
+ Hash
> Default
for UnordSet
<V
> {
150 fn default() -> Self {
151 Self { inner: FxHashSet::default() }
155 impl<V
: Eq
+ Hash
> UnordSet
<V
> {
157 pub fn new() -> Self {
158 Self { inner: Default::default() }
162 pub fn len(&self) -> usize {
167 pub fn insert(&mut self, v
: V
) -> bool
{
172 pub fn contains
<Q
: ?Sized
>(&self, v
: &Q
) -> bool
177 self.inner
.contains(v
)
181 pub fn items
<'a
>(&'a
self) -> UnordItems
<&'a V
, impl Iterator
<Item
= &'a V
>> {
182 UnordItems(self.inner
.iter())
186 pub fn into_items(self) -> UnordItems
<V
, impl Iterator
<Item
= V
>> {
187 UnordItems(self.inner
.into_iter())
190 // We can safely extend this UnordSet from a set of unordered values because that
191 // won't expose the internal ordering anywhere.
193 pub fn extend
<I
: Iterator
<Item
= V
>>(&mut self, items
: UnordItems
<V
, I
>) {
194 self.inner
.extend(items
.0)
198 impl<V
: Hash
+ Eq
> Extend
<V
> for UnordSet
<V
> {
199 fn extend
<T
: IntoIterator
<Item
= V
>>(&mut self, iter
: T
) {
200 self.inner
.extend(iter
)
204 impl<HCX
, V
: Hash
+ Eq
+ HashStable
<HCX
>> HashStable
<HCX
> for UnordSet
<V
> {
206 fn hash_stable(&self, hcx
: &mut HCX
, hasher
: &mut StableHasher
) {
207 hash_iter_order_independent(self.inner
.iter(), hcx
, hasher
);
211 /// This is a map collection type that tries very hard to not expose
212 /// any internal iteration. This is a useful property when trying to
213 /// uphold the determinism invariants imposed by the query system.
215 /// This collection type is a good choice for map-like collections the
216 /// keys of which don't have a semantic ordering.
218 /// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
219 /// for more information.
220 #[derive(Debug, Eq, PartialEq, Clone, Encodable, Decodable)]
221 pub struct UnordMap
<K
: Eq
+ Hash
, V
> {
222 inner
: FxHashMap
<K
, V
>,
225 impl<K
: Eq
+ Hash
, V
> Default
for UnordMap
<K
, V
> {
226 fn default() -> Self {
227 Self { inner: FxHashMap::default() }
231 impl<K
: Hash
+ Eq
, V
> Extend
<(K
, V
)> for UnordMap
<K
, V
> {
232 fn extend
<T
: IntoIterator
<Item
= (K
, V
)>>(&mut self, iter
: T
) {
233 self.inner
.extend(iter
)
237 impl<K
: Eq
+ Hash
, V
> UnordMap
<K
, V
> {
239 pub fn len(&self) -> usize {
244 pub fn insert(&mut self, k
: K
, v
: V
) -> Option
<V
> {
245 self.inner
.insert(k
, v
)
249 pub fn contains_key
<Q
: ?Sized
>(&self, k
: &Q
) -> bool
254 self.inner
.contains_key(k
)
258 pub fn items
<'a
>(&'a
self) -> UnordItems
<(&'a K
, &'a V
), impl Iterator
<Item
= (&'a K
, &'a V
)>> {
259 UnordItems(self.inner
.iter())
263 pub fn into_items(self) -> UnordItems
<(K
, V
), impl Iterator
<Item
= (K
, V
)>> {
264 UnordItems(self.inner
.into_iter())
267 // We can safely extend this UnordMap from a set of unordered values because that
268 // won't expose the internal ordering anywhere.
270 pub fn extend
<I
: Iterator
<Item
= (K
, V
)>>(&mut self, items
: UnordItems
<(K
, V
), I
>) {
271 self.inner
.extend(items
.0)
275 impl<HCX
, K
: Hash
+ Eq
+ HashStable
<HCX
>, V
: HashStable
<HCX
>> HashStable
<HCX
> for UnordMap
<K
, V
> {
277 fn hash_stable(&self, hcx
: &mut HCX
, hasher
: &mut StableHasher
) {
278 hash_iter_order_independent(self.inner
.iter(), hcx
, hasher
);
282 /// This is a collection type that tries very hard to not expose
283 /// any internal iteration. This is a useful property when trying to
284 /// uphold the determinism invariants imposed by the query system.
286 /// This collection type is a good choice for collections the
287 /// keys of which don't have a semantic ordering and don't implement
290 /// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
291 /// for more information.
292 #[derive(Default, Debug, Eq, PartialEq, Clone, Encodable, Decodable)]
293 pub struct UnordBag
<V
> {
297 impl<V
> UnordBag
<V
> {
299 pub fn new() -> Self {
300 Self { inner: Default::default() }
304 pub fn len(&self) -> usize {
309 pub fn push(&mut self, v
: V
) {
314 pub fn items
<'a
>(&'a
self) -> UnordItems
<&'a V
, impl Iterator
<Item
= &'a V
>> {
315 UnordItems(self.inner
.iter())
319 pub fn into_items(self) -> UnordItems
<V
, impl Iterator
<Item
= V
>> {
320 UnordItems(self.inner
.into_iter())
323 // We can safely extend this UnordSet from a set of unordered values because that
324 // won't expose the internal ordering anywhere.
326 pub fn extend
<I
: Iterator
<Item
= V
>>(&mut self, items
: UnordItems
<V
, I
>) {
327 self.inner
.extend(items
.0)
331 impl<T
> Extend
<T
> for UnordBag
<T
> {
332 fn extend
<I
: IntoIterator
<Item
= T
>>(&mut self, iter
: I
) {
333 self.inner
.extend(iter
)
337 impl<HCX
, V
: Hash
+ Eq
+ HashStable
<HCX
>> HashStable
<HCX
> for UnordBag
<V
> {
339 fn hash_stable(&self, hcx
: &mut HCX
, hasher
: &mut StableHasher
) {
340 hash_iter_order_independent(self.inner
.iter(), hcx
, hasher
);
344 fn hash_iter_order_independent
<
347 I
: Iterator
<Item
= T
> + ExactSizeIterator
,
351 hasher
: &mut StableHasher
,
354 len
.hash_stable(hcx
, hasher
);
361 // No need to instantiate a hasher
362 it
.next().unwrap().hash_stable(hcx
, hasher
);
365 let mut accumulator
= Fingerprint
::ZERO
;
367 let mut item_hasher
= StableHasher
::new();
368 item
.hash_stable(hcx
, &mut item_hasher
);
369 let item_fingerprint
: Fingerprint
= item_hasher
.finish();
370 accumulator
= accumulator
.combine_commutative(item_fingerprint
);
372 accumulator
.hash_stable(hcx
, hasher
);
377 // Do not implement IntoIterator for the collections in this module.
378 // They only exist to hide iteration order in the first place.
379 impl<T
> !IntoIterator
for UnordBag
<T
> {}
380 impl<V
> !IntoIterator
for UnordSet
<V
> {}
381 impl<K
, V
> !IntoIterator
for UnordMap
<K
, V
> {}
382 impl<T
, I
> !IntoIterator
for UnordItems
<T
, I
> {}