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(&self) -> UnordItems<&V, impl Iterator<Item = &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(&self) -> UnordItems<(&K, &V), impl Iterator<Item = (&K, &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(&self) -> UnordItems<&V, impl Iterator<Item = &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> {}