Merging upstream version 1.66.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

11 files changed, 470 insertions, 67 deletions

diff --git a/compiler/rustc_data_structures/Cargo.toml b/compiler/rustc_data_structures/Cargo.toml
index 2d8658db5..9daa21ef6 100644
--- a/compiler/rustc_data_structures/Cargo.toml
+++ b/compiler/rustc_data_structures/Cargo.toml
@@ -4,7 +4,6 @@ version = "0.0.0"
 edition = "2021"
 
 [lib]
-doctest = false
 
 [dependencies]
 arrayvec = { version = "0.7", default-features = false }
diff --git a/compiler/rustc_data_structures/src/flock/linux.rs b/compiler/rustc_data_structures/src/flock/linux.rs
index bb3ecfbc3..9ed26e490 100644
--- a/compiler/rustc_data_structures/src/flock/linux.rs
+++ b/compiler/rustc_data_structures/src/flock/linux.rs
@@ -14,12 +14,7 @@ pub struct Lock {
 
 impl Lock {
     pub fn new(p: &Path, wait: bool, create: bool, exclusive: bool) -> io::Result<Lock> {
-        let file = OpenOptions::new()
-            .read(true)
-            .write(true)
-            .create(create)
-            .mode(libc::S_IRWXU as u32)
-            .open(p)?;
+        let file = OpenOptions::new().read(true).write(true).create(create).mode(0o600).open(p)?;
 
         let mut operation = if exclusive { libc::LOCK_EX } else { libc::LOCK_SH };
         if !wait {
diff --git a/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs b/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs
index 3d91bcade..e8efbd09a 100644
--- a/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs
+++ b/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs
@@ -29,8 +29,8 @@ impl<N: Idx + Ord> VecGraph<N> {
         // Store the *target* of each edge into `edge_targets`.
         let edge_targets: Vec<N> = edge_pairs.iter().map(|&(_, target)| target).collect();
 
-        // Create the *edge starts* array. We are iterating over over
-        // the (sorted) edge pairs. We maintain the invariant that the
+        // Create the *edge starts* array. We are iterating over the
+        // (sorted) edge pairs. We maintain the invariant that the
         // length of the `node_starts` array is enough to store the
         // current source node -- so when we see that the source node
         // for an edge is greater than the current length, we grow the
diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs
index 56f7823ef..3a2000233 100644
--- a/compiler/rustc_data_structures/src/lib.rs
+++ b/compiler/rustc_data_structures/src/lib.rs
@@ -13,7 +13,6 @@
 #![feature(cell_leak)]
 #![feature(control_flow_enum)]
 #![feature(extend_one)]
-#![cfg_attr(bootstrap, feature(let_else))]
 #![feature(hash_raw_entry)]
 #![feature(hasher_prefixfree_extras)]
 #![feature(maybe_uninit_uninit_array)]
@@ -23,6 +22,7 @@
 #![feature(new_uninit)]
 #![feature(once_cell)]
 #![feature(rustc_attrs)]
+#![feature(negative_impls)]
 #![feature(test)]
 #![feature(thread_id_value)]
 #![feature(vec_into_raw_parts)]
@@ -87,6 +87,7 @@ pub mod steal;
 pub mod tagged_ptr;
 pub mod temp_dir;
 pub mod unhash;
+pub mod unord;
 
 pub use ena::undo_log;
 pub use ena::unify;
diff --git a/compiler/rustc_data_structures/src/obligation_forest/mod.rs b/compiler/rustc_data_structures/src/obligation_forest/mod.rs
index e351b650a..10e673cd9 100644
--- a/compiler/rustc_data_structures/src/obligation_forest/mod.rs
+++ b/compiler/rustc_data_structures/src/obligation_forest/mod.rs
@@ -95,6 +95,10 @@ pub trait ForestObligation: Clone + Debug {
 pub trait ObligationProcessor {
     type Obligation: ForestObligation;
     type Error: Debug;
+    type OUT: OutcomeTrait<
+        Obligation = Self::Obligation,
+        Error = Error<Self::Obligation, Self::Error>,
+    >;
 
     fn needs_process_obligation(&self, obligation: &Self::Obligation) -> bool;
 
@@ -111,7 +115,11 @@ pub trait ObligationProcessor {
     /// In other words, if we had O1 which required O2 which required
     /// O3 which required O1, we would give an iterator yielding O1,
     /// O2, O3 (O1 is not yielded twice).
-    fn process_backedge<'c, I>(&mut self, cycle: I, _marker: PhantomData<&'c Self::Obligation>)
+    fn process_backedge<'c, I>(
+        &mut self,
+        cycle: I,
+        _marker: PhantomData<&'c Self::Obligation>,
+    ) -> Result<(), Self::Error>
     where
         I: Clone + Iterator<Item = &'c Self::Obligation>;
 }
@@ -402,12 +410,11 @@ impl<O: ForestObligation> ObligationForest<O> {
 
     /// Performs a fixpoint computation over the obligation list.
     #[inline(never)]
-    pub fn process_obligations<P, OUT>(&mut self, processor: &mut P) -> OUT
+    pub fn process_obligations<P>(&mut self, processor: &mut P) -> P::OUT
     where
         P: ObligationProcessor<Obligation = O>,
-        OUT: OutcomeTrait<Obligation = O, Error = Error<O, P::Error>>,
     {
-        let mut outcome = OUT::new();
+        let mut outcome = P::OUT::new();
 
         // Fixpoint computation: we repeat until the inner loop stalls.
         loop {
@@ -473,7 +480,7 @@ impl<O: ForestObligation> ObligationForest<O> {
             }
 
             self.mark_successes();
-            self.process_cycles(processor);
+            self.process_cycles(processor, &mut outcome);
             self.compress(|obl| outcome.record_completed(obl));
         }
 
@@ -558,7 +565,7 @@ impl<O: ForestObligation> ObligationForest<O> {
 
     /// Report cycles between all `Success` nodes, and convert all `Success`
     /// nodes to `Done`. This must be called after `mark_successes`.
-    fn process_cycles<P>(&mut self, processor: &mut P)
+    fn process_cycles<P>(&mut self, processor: &mut P, outcome: &mut P::OUT)
     where
         P: ObligationProcessor<Obligation = O>,
     {
@@ -568,7 +575,7 @@ impl<O: ForestObligation> ObligationForest<O> {
             // to handle the no-op cases immediately to avoid the cost of the
             // function call.
             if node.state.get() == NodeState::Success {
-                self.find_cycles_from_node(&mut stack, processor, index);
+                self.find_cycles_from_node(&mut stack, processor, index, outcome);
             }
         }
 
@@ -576,8 +583,13 @@ impl<O: ForestObligation> ObligationForest<O> {
         self.reused_node_vec = stack;
     }
 
-    fn find_cycles_from_node<P>(&self, stack: &mut Vec<usize>, processor: &mut P, index: usize)
-    where
+    fn find_cycles_from_node<P>(
+        &self,
+        stack: &mut Vec<usize>,
+        processor: &mut P,
+        index: usize,
+        outcome: &mut P::OUT,
+    ) where
         P: ObligationProcessor<Obligation = O>,
     {
         let node = &self.nodes[index];
@@ -586,17 +598,20 @@ impl<O: ForestObligation> ObligationForest<O> {
                 None => {
                     stack.push(index);
                     for &dep_index in node.dependents.iter() {
-                        self.find_cycles_from_node(stack, processor, dep_index);
+                        self.find_cycles_from_node(stack, processor, dep_index, outcome);
                     }
                     stack.pop();
                     node.state.set(NodeState::Done);
                 }
                 Some(rpos) => {
                     // Cycle detected.
-                    processor.process_backedge(
+                    let result = processor.process_backedge(
                         stack[rpos..].iter().map(|&i| &self.nodes[i].obligation),
                         PhantomData,
                     );
+                    if let Err(err) = result {
+                        outcome.record_error(Error { error: err, backtrace: self.error_at(index) });
+                    }
                 }
             }
         }
diff --git a/compiler/rustc_data_structures/src/obligation_forest/tests.rs b/compiler/rustc_data_structures/src/obligation_forest/tests.rs
index e2991aae1..bc252f772 100644
--- a/compiler/rustc_data_structures/src/obligation_forest/tests.rs
+++ b/compiler/rustc_data_structures/src/obligation_forest/tests.rs
@@ -64,6 +64,7 @@ where
 {
     type Obligation = O;
     type Error = E;
+    type OUT = TestOutcome<O, E>;
 
     fn needs_process_obligation(&self, _obligation: &Self::Obligation) -> bool {
         true
@@ -76,10 +77,15 @@ where
         (self.process_obligation)(obligation)
     }
 
-    fn process_backedge<'c, I>(&mut self, _cycle: I, _marker: PhantomData<&'c Self::Obligation>)
+    fn process_backedge<'c, I>(
+        &mut self,
+        _cycle: I,
+        _marker: PhantomData<&'c Self::Obligation>,
+    ) -> Result<(), Self::Error>
     where
         I: Clone + Iterator<Item = &'c Self::Obligation>,
     {
+        Ok(())
     }
 }
 
diff --git a/compiler/rustc_data_structures/src/profiling.rs b/compiler/rustc_data_structures/src/profiling.rs
index d8b26f984..ba1960805 100644
--- a/compiler/rustc_data_structures/src/profiling.rs
+++ b/compiler/rustc_data_structures/src/profiling.rs
@@ -158,30 +158,21 @@ pub struct SelfProfilerRef {
     // actually enabled.
     event_filter_mask: EventFilter,
 
-    // Print verbose generic activities to stdout
+    // Print verbose generic activities to stderr?
     print_verbose_generic_activities: bool,
-
-    // Print extra verbose generic activities to stdout
-    print_extra_verbose_generic_activities: bool,
 }
 
 impl SelfProfilerRef {
     pub fn new(
         profiler: Option<Arc<SelfProfiler>>,
         print_verbose_generic_activities: bool,
-        print_extra_verbose_generic_activities: bool,
     ) -> SelfProfilerRef {
         // If there is no SelfProfiler then the filter mask is set to NONE,
         // ensuring that nothing ever tries to actually access it.
         let event_filter_mask =
             profiler.as_ref().map_or(EventFilter::empty(), |p| p.event_filter_mask);
 
-        SelfProfilerRef {
-            profiler,
-            event_filter_mask,
-            print_verbose_generic_activities,
-            print_extra_verbose_generic_activities,
-        }
+        SelfProfilerRef { profiler, event_filter_mask, print_verbose_generic_activities }
     }
 
     /// This shim makes sure that calls only get executed if the filter mask
@@ -214,7 +205,7 @@ impl SelfProfilerRef {
     /// Start profiling a verbose generic activity. Profiling continues until the
     /// VerboseTimingGuard returned from this call is dropped. In addition to recording
     /// a measureme event, "verbose" generic activities also print a timing entry to
-    /// stdout if the compiler is invoked with -Ztime or -Ztime-passes.
+    /// stderr if the compiler is invoked with -Ztime-passes.
     pub fn verbose_generic_activity<'a>(
         &'a self,
         event_label: &'static str,
@@ -225,11 +216,8 @@ impl SelfProfilerRef {
         VerboseTimingGuard::start(message, self.generic_activity(event_label))
     }
 
-    /// Start profiling an extra verbose generic activity. Profiling continues until the
-    /// VerboseTimingGuard returned from this call is dropped. In addition to recording
-    /// a measureme event, "extra verbose" generic activities also print a timing entry to
-    /// stdout if the compiler is invoked with -Ztime-passes.
-    pub fn extra_verbose_generic_activity<'a, A>(
+    /// Like `verbose_generic_activity`, but with an extra arg.
+    pub fn verbose_generic_activity_with_arg<'a, A>(
         &'a self,
         event_label: &'static str,
         event_arg: A,
@@ -237,7 +225,7 @@ impl SelfProfilerRef {
     where
         A: Borrow<str> + Into<String>,
     {
-        let message = if self.print_extra_verbose_generic_activities {
+        let message = if self.print_verbose_generic_activities {
             Some(format!("{}({})", event_label, event_arg.borrow()))
         } else {
             None
@@ -745,27 +733,9 @@ impl Drop for VerboseTimingGuard<'_> {
         if let Some((start_time, start_rss, ref message)) = self.start_and_message {
             let end_rss = get_resident_set_size();
             let dur = start_time.elapsed();
-
-            if should_print_passes(dur, start_rss, end_rss) {
-                print_time_passes_entry(&message, dur, start_rss, end_rss);
-            }
-        }
-    }
-}
-
-fn should_print_passes(dur: Duration, start_rss: Option<usize>, end_rss: Option<usize>) -> bool {
-    if dur.as_millis() > 5 {
-        return true;
-    }
-
-    if let (Some(start_rss), Some(end_rss)) = (start_rss, end_rss) {
-        let change_rss = end_rss.abs_diff(start_rss);
-        if change_rss > 0 {
-            return true;
+            print_time_passes_entry(&message, dur, start_rss, end_rss);
         }
     }
-
-    false
 }
 
 pub fn print_time_passes_entry(
@@ -774,6 +744,26 @@ pub fn print_time_passes_entry(
     start_rss: Option<usize>,
     end_rss: Option<usize>,
 ) {
+    // Print the pass if its duration is greater than 5 ms, or it changed the
+    // measured RSS.
+    let is_notable = || {
+        if dur.as_millis() > 5 {
+            return true;
+        }
+
+        if let (Some(start_rss), Some(end_rss)) = (start_rss, end_rss) {
+            let change_rss = end_rss.abs_diff(start_rss);
+            if change_rss > 0 {
+                return true;
+            }
+        }
+
+        false
+    };
+    if !is_notable() {
+        return;
+    }
+
     let rss_to_mb = |rss| (rss as f64 / 1_000_000.0).round() as usize;
     let rss_change_to_mb = |rss| (rss as f64 / 1_000_000.0).round() as i128;
 
diff --git a/compiler/rustc_data_structures/src/sorted_map.rs b/compiler/rustc_data_structures/src/sorted_map.rs
index 937cb6715..fe257e102 100644
--- a/compiler/rustc_data_structures/src/sorted_map.rs
+++ b/compiler/rustc_data_structures/src/sorted_map.rs
@@ -96,6 +96,23 @@ impl<K: Ord, V> SortedMap<K, V> {
         }
     }
 
+    /// Gets a mutable reference to the value in the entry, or insert a new one.
+    #[inline]
+    pub fn get_mut_or_insert_default(&mut self, key: K) -> &mut V
+    where
+        K: Eq,
+        V: Default,
+    {
+        let index = match self.lookup_index_for(&key) {
+            Ok(index) => index,
+            Err(index) => {
+                self.data.insert(index, (key, V::default()));
+                index
+            }
+        };
+        unsafe { &mut self.data.get_unchecked_mut(index).1 }
+    }
+
     #[inline]
     pub fn clear(&mut self) {
         self.data.clear();
diff --git a/compiler/rustc_data_structures/src/sso/set.rs b/compiler/rustc_data_structures/src/sso/set.rs
index 4fda3adb7..406f0270d 100644
--- a/compiler/rustc_data_structures/src/sso/set.rs
+++ b/compiler/rustc_data_structures/src/sso/set.rs
@@ -27,7 +27,7 @@ pub struct SsoHashSet<T> {
     map: SsoHashMap<T, ()>,
 }
 
-/// Adapter function used ot return
+/// Adapter function used to return
 /// result if SsoHashMap functions into
 /// result SsoHashSet should return.
 #[inline(always)]
diff --git a/compiler/rustc_data_structures/src/transitive_relation.rs b/compiler/rustc_data_structures/src/transitive_relation.rs
index f016c391f..cf6162038 100644
--- a/compiler/rustc_data_structures/src/transitive_relation.rs
+++ b/compiler/rustc_data_structures/src/transitive_relation.rs
@@ -1,5 +1,5 @@
 use crate::frozen::Frozen;
-use crate::fx::FxIndexSet;
+use crate::fx::{FxHashSet, FxIndexSet};
 use rustc_index::bit_set::BitMatrix;
 use std::fmt::Debug;
 use std::hash::Hash;
@@ -16,7 +16,7 @@ pub struct TransitiveRelationBuilder<T> {
 
     // List of base edges in the graph. Require to compute transitive
     // closure.
-    edges: Vec<Edge>,
+    edges: FxHashSet<Edge>,
 }
 
 #[derive(Debug)]
@@ -52,10 +52,10 @@ impl<T: Eq + Hash> Default for TransitiveRelationBuilder<T> {
     }
 }
 
-#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Debug)]
+#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Debug, Hash)]
 struct Index(usize);
 
-#[derive(Clone, PartialEq, Eq, Debug)]
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
 struct Edge {
     source: Index,
     target: Index,
@@ -99,9 +99,7 @@ impl<T: Eq + Hash + Copy> TransitiveRelationBuilder<T> {
         let a = self.add_index(a);
         let b = self.add_index(b);
         let edge = Edge { source: a, target: b };
-        if !self.edges.contains(&edge) {
-            self.edges.push(edge);
-        }
+        self.edges.insert(edge);
     }
 
     /// Compute the transitive closure derived from the edges, and converted to
diff --git a/compiler/rustc_data_structures/src/unord.rs b/compiler/rustc_data_structures/src/unord.rs
new file mode 100644
index 000000000..c015f1232
--- /dev/null
+++ b/compiler/rustc_data_structures/src/unord.rs
@@ -0,0 +1,382 @@
+//! This module contains collection types that don't expose their internal
+//! ordering. This is a useful property for deterministic computations, such
+//! as required by the query system.
+
+use rustc_hash::{FxHashMap, FxHashSet};
+use smallvec::SmallVec;
+use std::{
+    borrow::Borrow,
+    hash::Hash,
+    iter::{Product, Sum},
+};
+
+use crate::{
+    fingerprint::Fingerprint,
+    stable_hasher::{HashStable, StableHasher, ToStableHashKey},
+};
+
+/// `UnordItems` is the order-less version of `Iterator`. It only contains methods
+/// that don't (easily) expose an ordering of the underlying items.
+///
+/// Most methods take an `Fn` where the `Iterator`-version takes an `FnMut`. This
+/// is to reduce the risk of accidentally leaking the internal order via the closure
+/// environment. Otherwise one could easily do something like
+///
+/// ```rust,ignore (pseudo code)
+/// let mut ordered = vec![];
+/// unordered_items.all(|x| ordered.push(x));
+/// ```
+///
+/// It's still possible to do the same thing with an `Fn` by using interior mutability,
+/// but the chance of doing it accidentally is reduced.
+pub struct UnordItems<T, I: Iterator<Item = T>>(I);
+
+impl<T, I: Iterator<Item = T>> UnordItems<T, I> {
+    #[inline]
+    pub fn map<U, F: Fn(T) -> U>(self, f: F) -> UnordItems<U, impl Iterator<Item = U>> {
+        UnordItems(self.0.map(f))
+    }
+
+    #[inline]
+    pub fn all<U, F: Fn(T) -> bool>(mut self, f: F) -> bool {
+        self.0.all(f)
+    }
+
+    #[inline]
+    pub fn any<U, F: Fn(T) -> bool>(mut self, f: F) -> bool {
+        self.0.any(f)
+    }
+
+    #[inline]
+    pub fn filter<U, F: Fn(&T) -> bool>(self, f: F) -> UnordItems<T, impl Iterator<Item = T>> {
+        UnordItems(self.0.filter(f))
+    }
+
+    #[inline]
+    pub fn filter_map<U, F: Fn(T) -> Option<U>>(
+        self,
+        f: F,
+    ) -> UnordItems<U, impl Iterator<Item = U>> {
+        UnordItems(self.0.filter_map(f))
+    }
+
+    #[inline]
+    pub fn max(self) -> Option<T>
+    where
+        T: Ord,
+    {
+        self.0.max()
+    }
+
+    #[inline]
+    pub fn min(self) -> Option<T>
+    where
+        T: Ord,
+    {
+        self.0.min()
+    }
+
+    #[inline]
+    pub fn sum<S>(self) -> S
+    where
+        S: Sum<T>,
+    {
+        self.0.sum()
+    }
+
+    #[inline]
+    pub fn product<S>(self) -> S
+    where
+        S: Product<T>,
+    {
+        self.0.product()
+    }
+
+    #[inline]
+    pub fn count(self) -> usize {
+        self.0.count()
+    }
+}
+
+impl<'a, T: Clone + 'a, I: Iterator<Item = &'a T>> UnordItems<&'a T, I> {
+    #[inline]
+    pub fn cloned(self) -> UnordItems<T, impl Iterator<Item = T>> {
+        UnordItems(self.0.cloned())
+    }
+}
+
+impl<'a, T: Copy + 'a, I: Iterator<Item = &'a T>> UnordItems<&'a T, I> {
+    #[inline]
+    pub fn copied(self) -> UnordItems<T, impl Iterator<Item = T>> {
+        UnordItems(self.0.copied())
+    }
+}
+
+impl<T: Ord, I: Iterator<Item = T>> UnordItems<T, I> {
+    pub fn into_sorted<HCX>(self, hcx: &HCX) -> Vec<T>
+    where
+        T: ToStableHashKey<HCX>,
+    {
+        let mut items: Vec<T> = self.0.collect();
+        items.sort_by_cached_key(|x| x.to_stable_hash_key(hcx));
+        items
+    }
+
+    pub fn into_sorted_small_vec<HCX, const LEN: usize>(self, hcx: &HCX) -> SmallVec<[T; LEN]>
+    where
+        T: ToStableHashKey<HCX>,
+    {
+        let mut items: SmallVec<[T; LEN]> = self.0.collect();
+        items.sort_by_cached_key(|x| x.to_stable_hash_key(hcx));
+        items
+    }
+}
+
+/// This is a set collection type that tries very hard to not expose
+/// any internal iteration. This is a useful property when trying to
+/// uphold the determinism invariants imposed by the query system.
+///
+/// This collection type is a good choice for set-like collections the
+/// keys of which don't have a semantic ordering.
+///
+/// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
+/// for more information.
+#[derive(Debug, Eq, PartialEq, Clone, Encodable, Decodable)]
+pub struct UnordSet<V: Eq + Hash> {
+    inner: FxHashSet<V>,
+}
+
+impl<V: Eq + Hash> Default for UnordSet<V> {
+    fn default() -> Self {
+        Self { inner: FxHashSet::default() }
+    }
+}
+
+impl<V: Eq + Hash> UnordSet<V> {
+    #[inline]
+    pub fn new() -> Self {
+        Self { inner: Default::default() }
+    }
+
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.inner.len()
+    }
+
+    #[inline]
+    pub fn insert(&mut self, v: V) -> bool {
+        self.inner.insert(v)
+    }
+
+    #[inline]
+    pub fn contains<Q: ?Sized>(&self, v: &Q) -> bool
+    where
+        V: Borrow<Q>,
+        Q: Hash + Eq,
+    {
+        self.inner.contains(v)
+    }
+
+    #[inline]
+    pub fn items<'a>(&'a self) -> UnordItems<&'a V, impl Iterator<Item = &'a V>> {
+        UnordItems(self.inner.iter())
+    }
+
+    #[inline]
+    pub fn into_items(self) -> UnordItems<V, impl Iterator<Item = V>> {
+        UnordItems(self.inner.into_iter())
+    }
+
+    // We can safely extend this UnordSet from a set of unordered values because that
+    // won't expose the internal ordering anywhere.
+    #[inline]
+    pub fn extend<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) {
+        self.inner.extend(items.0)
+    }
+}
+
+impl<V: Hash + Eq> Extend<V> for UnordSet<V> {
+    fn extend<T: IntoIterator<Item = V>>(&mut self, iter: T) {
+        self.inner.extend(iter)
+    }
+}
+
+impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordSet<V> {
+    #[inline]
+    fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
+        hash_iter_order_independent(self.inner.iter(), hcx, hasher);
+    }
+}
+
+/// This is a map collection type that tries very hard to not expose
+/// any internal iteration. This is a useful property when trying to
+/// uphold the determinism invariants imposed by the query system.
+///
+/// This collection type is a good choice for map-like collections the
+/// keys of which don't have a semantic ordering.
+///
+/// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
+/// for more information.
+#[derive(Debug, Eq, PartialEq, Clone, Encodable, Decodable)]
+pub struct UnordMap<K: Eq + Hash, V> {
+    inner: FxHashMap<K, V>,
+}
+
+impl<K: Eq + Hash, V> Default for UnordMap<K, V> {
+    fn default() -> Self {
+        Self { inner: FxHashMap::default() }
+    }
+}
+
+impl<K: Hash + Eq, V> Extend<(K, V)> for UnordMap<K, V> {
+    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
+        self.inner.extend(iter)
+    }
+}
+
+impl<K: Eq + Hash, V> UnordMap<K, V> {
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.inner.len()
+    }
+
+    #[inline]
+    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
+        self.inner.insert(k, v)
+    }
+
+    #[inline]
+    pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
+    where
+        K: Borrow<Q>,
+        Q: Hash + Eq,
+    {
+        self.inner.contains_key(k)
+    }
+
+    #[inline]
+    pub fn items<'a>(&'a self) -> UnordItems<(&'a K, &'a V), impl Iterator<Item = (&'a K, &'a V)>> {
+        UnordItems(self.inner.iter())
+    }
+
+    #[inline]
+    pub fn into_items(self) -> UnordItems<(K, V), impl Iterator<Item = (K, V)>> {
+        UnordItems(self.inner.into_iter())
+    }
+
+    // We can safely extend this UnordMap from a set of unordered values because that
+    // won't expose the internal ordering anywhere.
+    #[inline]
+    pub fn extend<I: Iterator<Item = (K, V)>>(&mut self, items: UnordItems<(K, V), I>) {
+        self.inner.extend(items.0)
+    }
+}
+
+impl<HCX, K: Hash + Eq + HashStable<HCX>, V: HashStable<HCX>> HashStable<HCX> for UnordMap<K, V> {
+    #[inline]
+    fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
+        hash_iter_order_independent(self.inner.iter(), hcx, hasher);
+    }
+}
+
+/// This is a collection type that tries very hard to not expose
+/// any internal iteration. This is a useful property when trying to
+/// uphold the determinism invariants imposed by the query system.
+///
+/// This collection type is a good choice for collections the
+/// keys of which don't have a semantic ordering and don't implement
+/// `Hash` or `Eq`.
+///
+/// See [MCP 533](https://github.com/rust-lang/compiler-team/issues/533)
+/// for more information.
+#[derive(Default, Debug, Eq, PartialEq, Clone, Encodable, Decodable)]
+pub struct UnordBag<V> {
+    inner: Vec<V>,
+}
+
+impl<V> UnordBag<V> {
+    #[inline]
+    pub fn new() -> Self {
+        Self { inner: Default::default() }
+    }
+
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.inner.len()
+    }
+
+    #[inline]
+    pub fn push(&mut self, v: V) {
+        self.inner.push(v);
+    }
+
+    #[inline]
+    pub fn items<'a>(&'a self) -> UnordItems<&'a V, impl Iterator<Item = &'a V>> {
+        UnordItems(self.inner.iter())
+    }
+
+    #[inline]
+    pub fn into_items(self) -> UnordItems<V, impl Iterator<Item = V>> {
+        UnordItems(self.inner.into_iter())
+    }
+
+    // We can safely extend this UnordSet from a set of unordered values because that
+    // won't expose the internal ordering anywhere.
+    #[inline]
+    pub fn extend<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) {
+        self.inner.extend(items.0)
+    }
+}
+
+impl<T> Extend<T> for UnordBag<T> {
+    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
+        self.inner.extend(iter)
+    }
+}
+
+impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordBag<V> {
+    #[inline]
+    fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
+        hash_iter_order_independent(self.inner.iter(), hcx, hasher);
+    }
+}
+
+fn hash_iter_order_independent<
+    HCX,
+    T: HashStable<HCX>,
+    I: Iterator<Item = T> + ExactSizeIterator,
+>(
+    mut it: I,
+    hcx: &mut HCX,
+    hasher: &mut StableHasher,
+) {
+    let len = it.len();
+    len.hash_stable(hcx, hasher);
+
+    match len {
+        0 => {
+            // We're done
+        }
+        1 => {
+            // No need to instantiate a hasher
+            it.next().unwrap().hash_stable(hcx, hasher);
+        }
+        _ => {
+            let mut accumulator = Fingerprint::ZERO;
+            for item in it {
+                let mut item_hasher = StableHasher::new();
+                item.hash_stable(hcx, &mut item_hasher);
+                let item_fingerprint: Fingerprint = item_hasher.finish();
+                accumulator = accumulator.combine_commutative(item_fingerprint);
+            }
+            accumulator.hash_stable(hcx, hasher);
+        }
+    }
+}
+
+// Do not implement IntoIterator for the collections in this module.
+// They only exist to hide iteration order in the first place.
+impl<T> !IntoIterator for UnordBag<T> {}
+impl<V> !IntoIterator for UnordSet<V> {}
+impl<K, V> !IntoIterator for UnordMap<K, V> {}
+impl<T, I> !IntoIterator for UnordItems<T, I> {}