Use UnordMap instead of FxHashMap in define_id_collections!().

15 files changed, 254 insertions, 103 deletions

diff --git a/compiler/rustc_codegen_ssa/src/back/symbol_export.rs b/compiler/rustc_codegen_ssa/src/back/symbol_export.rs
index 8cb7d74b90d..b442483346d 100644
--- a/compiler/rustc_codegen_ssa/src/back/symbol_export.rs
+++ b/compiler/rustc_codegen_ssa/src/back/symbol_export.rs
@@ -173,11 +173,15 @@ fn exported_symbols_provider_local(
         return &[];
     }
 
-    let mut symbols: Vec<_> = tcx
-        .reachable_non_generics(LOCAL_CRATE)
-        .iter()
-        .map(|(&def_id, &info)| (ExportedSymbol::NonGeneric(def_id), info))
-        .collect();
+    // FIXME: Sorting this is unnecessary since we are sorting later anyway.
+    //        Can we skip the later sorting?
+    let mut symbols: Vec<_> = tcx.with_stable_hashing_context(|hcx| {
+        tcx.reachable_non_generics(LOCAL_CRATE)
+            .to_sorted(&hcx)
+            .into_iter()
+            .map(|(&def_id, &info)| (ExportedSymbol::NonGeneric(def_id), info))
+            .collect()
+    });
 
     if tcx.entry_fn(()).is_some() {
         let exported_symbol =
diff --git a/compiler/rustc_data_structures/src/fx.rs b/compiler/rustc_data_structures/src/fx.rs
index 11f9def34aa..9fce0e1e65c 100644
--- a/compiler/rustc_data_structures/src/fx.rs
+++ b/compiler/rustc_data_structures/src/fx.rs
@@ -11,7 +11,7 @@ pub type IndexEntry<'a, K, V> = indexmap::map::Entry<'a, K, V>;
 #[macro_export]
 macro_rules! define_id_collections {
     ($map_name:ident, $set_name:ident, $entry_name:ident, $key:ty) => {
-        pub type $map_name<T> = $crate::fx::FxHashMap<$key, T>;
+        pub type $map_name<T> = $crate::unord::UnordMap<$key, T>;
         pub type $set_name = $crate::unord::UnordSet<$key>;
         pub type $entry_name<'a, T> = $crate::fx::StdEntry<'a, $key, T>;
     };
diff --git a/compiler/rustc_data_structures/src/unord.rs b/compiler/rustc_data_structures/src/unord.rs
index cfd7ee097a3..1e71629a7c4 100644
--- a/compiler/rustc_data_structures/src/unord.rs
+++ b/compiler/rustc_data_structures/src/unord.rs
@@ -6,8 +6,10 @@ use rustc_hash::{FxHashMap, FxHashSet};
 use smallvec::SmallVec;
 use std::{
     borrow::Borrow,
+    collections::hash_map::Entry,
     hash::Hash,
     iter::{Product, Sum},
+    ops::Index,
 };
 
 use crate::{
@@ -187,7 +189,16 @@ impl<V: Eq + Hash> UnordSet<V> {
     }
 
     #[inline]
-    pub fn items(&self) -> UnordItems<&V, impl Iterator<Item = &V>> {
+    pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> bool
+    where
+        V: Borrow<Q>,
+        Q: Hash + Eq,
+    {
+        self.inner.remove(k)
+    }
+
+    #[inline]
+    pub fn items<'a>(&'a self) -> UnordItems<&'a V, impl Iterator<Item = &'a V>> {
         UnordItems(self.inner.iter())
     }
 
@@ -254,6 +265,18 @@ impl<K: Hash + Eq, V> Extend<(K, V)> for UnordMap<K, V> {
     }
 }
 
+impl<K: Hash + Eq, V> FromIterator<(K, V)> for UnordMap<K, V> {
+    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
+        UnordMap { inner: FxHashMap::from_iter(iter) }
+    }
+}
+
+impl<K: Hash + Eq, V, I: Iterator<Item = (K, V)>> From<UnordItems<(K, V), I>> for UnordMap<K, V> {
+    fn from(items: UnordItems<(K, V), I>) -> Self {
+        UnordMap { inner: FxHashMap::from_iter(items.0) }
+    }
+}
+
 impl<K: Eq + Hash, V> UnordMap<K, V> {
     #[inline]
     pub fn len(&self) -> usize {
@@ -275,7 +298,44 @@ impl<K: Eq + Hash, V> UnordMap<K, V> {
     }
 
     #[inline]
-    pub fn items(&self) -> UnordItems<(&K, &V), impl Iterator<Item = (&K, &V)>> {
+    pub fn is_empty(&self) -> bool {
+        self.inner.is_empty()
+    }
+
+    #[inline]
+    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
+        self.inner.entry(key)
+    }
+
+    #[inline]
+    pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
+    where
+        K: Borrow<Q>,
+        Q: Hash + Eq,
+    {
+        self.inner.get(k)
+    }
+
+    #[inline]
+    pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
+    where
+        K: Borrow<Q>,
+        Q: Hash + Eq,
+    {
+        self.inner.get_mut(k)
+    }
+
+    #[inline]
+    pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
+    where
+        K: Borrow<Q>,
+        Q: Hash + Eq,
+    {
+        self.inner.remove(k)
+    }
+
+    #[inline]
+    pub fn items<'a>(&'a self) -> UnordItems<(&'a K, &'a V), impl Iterator<Item = (&'a K, &'a V)>> {
         UnordItems(self.inner.iter())
     }
 
@@ -290,6 +350,46 @@ impl<K: Eq + Hash, V> UnordMap<K, V> {
     pub fn extend<I: Iterator<Item = (K, V)>>(&mut self, items: UnordItems<(K, V), I>) {
         self.inner.extend(items.0)
     }
+
+    pub fn to_sorted<HCX>(&self, hcx: &HCX) -> Vec<(&K, &V)>
+    where
+        K: ToStableHashKey<HCX>,
+    {
+        let mut items: Vec<(&K, &V)> = self.inner.iter().collect();
+        items.sort_by_cached_key(|(k, _)| k.to_stable_hash_key(hcx));
+        items
+    }
+
+    pub fn into_sorted<HCX>(self, hcx: &HCX) -> Vec<(K, V)>
+    where
+        K: ToStableHashKey<HCX>,
+    {
+        let mut items: Vec<(K, V)> = self.inner.into_iter().collect();
+        items.sort_by_cached_key(|(k, _)| k.to_stable_hash_key(hcx));
+        items
+    }
+
+    pub fn values_sorted<HCX>(&self, hcx: &HCX) -> impl Iterator<Item = &V>
+    where
+        K: ToStableHashKey<HCX>,
+    {
+        let mut items: Vec<(&K, &V)> = self.inner.iter().collect();
+        items.sort_by_cached_key(|(k, _)| k.to_stable_hash_key(hcx));
+        items.into_iter().map(|(_, v)| v)
+    }
+}
+
+impl<K, Q: ?Sized, V> Index<&Q> for UnordMap<K, V>
+where
+    K: Eq + Hash + Borrow<Q>,
+    Q: Eq + Hash,
+{
+    type Output = V;
+
+    #[inline]
+    fn index(&self, key: &Q) -> &V {
+        &self.inner[key]
+    }
 }
 
 impl<HCX, K: Hash + Eq + HashStable<HCX>, V: HashStable<HCX>> HashStable<HCX> for UnordMap<K, V> {
@@ -354,6 +454,12 @@ impl<T> Extend<T> for UnordBag<T> {
     }
 }
 
+impl<T, I: Iterator<Item = T>> From<UnordItems<T, I>> for UnordBag<T> {
+    fn from(value: UnordItems<T, I>) -> Self {
+        UnordBag { inner: Vec::from_iter(value.0) }
+    }
+}
+
 impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordBag<V> {
     #[inline]
     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
diff --git a/compiler/rustc_hir_analysis/src/variance/solve.rs b/compiler/rustc_hir_analysis/src/variance/solve.rs
index c9b59d35704..2d283532bdf 100644
--- a/compiler/rustc_hir_analysis/src/variance/solve.rs
+++ b/compiler/rustc_hir_analysis/src/variance/solve.rs
@@ -5,8 +5,7 @@
 //! optimal solution to the constraints. The final variance for each
 //! inferred is then written into the `variance_map` in the tcx.
 
-use rustc_data_structures::fx::FxHashMap;
-use rustc_hir::def_id::DefId;
+use rustc_hir::def_id::DefIdMap;
 use rustc_middle::ty;
 
 use super::constraints::*;
@@ -89,14 +88,12 @@ impl<'a, 'tcx> SolveContext<'a, 'tcx> {
         }
     }
 
-    fn create_map(&self) -> FxHashMap<DefId, &'tcx [ty::Variance]> {
+    fn create_map(&self) -> DefIdMap<&'tcx [ty::Variance]> {
         let tcx = self.terms_cx.tcx;
 
         let solutions = &self.solutions;
-        self.terms_cx
-            .inferred_starts
-            .iter()
-            .map(|(&def_id, &InferredIndex(start))| {
+        DefIdMap::from(self.terms_cx.inferred_starts.items().map(
+            |(&def_id, &InferredIndex(start))| {
                 let generics = tcx.generics_of(def_id);
                 let count = generics.count();
 
@@ -115,8 +112,8 @@ impl<'a, 'tcx> SolveContext<'a, 'tcx> {
                 }
 
                 (def_id.to_def_id(), &*variances)
-            })
-            .collect()
+            },
+        ))
     }
 
     fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance {
diff --git a/compiler/rustc_hir_typeck/src/writeback.rs b/compiler/rustc_hir_typeck/src/writeback.rs
index b8c1bcc5a28..6e6b63beca2 100644
--- a/compiler/rustc_hir_typeck/src/writeback.rs
+++ b/compiler/rustc_hir_typeck/src/writeback.rs
@@ -449,8 +449,11 @@ impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
         assert_eq!(fcx_typeck_results.hir_owner, self.typeck_results.hir_owner);
         let common_hir_owner = fcx_typeck_results.hir_owner;
 
-        for (id, origin) in fcx_typeck_results.closure_kind_origins().iter() {
-            let hir_id = hir::HirId { owner: common_hir_owner, local_id: *id };
+        let fcx_closure_kind_origins =
+            fcx_typeck_results.closure_kind_origins().items_in_stable_order(self.tcx());
+
+        for (&local_id, origin) in fcx_closure_kind_origins {
+            let hir_id = hir::HirId { owner: common_hir_owner, local_id };
             let place_span = origin.0;
             let place = self.resolve(origin.1.clone(), &place_span);
             self.typeck_results.closure_kind_origins_mut().insert(hir_id, (place_span, place));
@@ -477,22 +480,15 @@ impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
         assert_eq!(fcx_typeck_results.hir_owner, self.typeck_results.hir_owner);
         let common_hir_owner = fcx_typeck_results.hir_owner;
 
-        let mut errors_buffer = Vec::new();
-        for (&local_id, c_ty) in fcx_typeck_results.user_provided_types().iter() {
-            let hir_id = hir::HirId { owner: common_hir_owner, local_id };
-
-            if cfg!(debug_assertions) && c_ty.needs_infer() {
-                span_bug!(
-                    hir_id.to_span(self.fcx.tcx),
-                    "writeback: `{:?}` has inference variables",
-                    c_ty
-                );
-            };
+        if self.rustc_dump_user_substs {
+            let sorted_user_provided_types =
+                fcx_typeck_results.user_provided_types().items_in_stable_order(self.tcx());
 
-            self.typeck_results.user_provided_types_mut().insert(hir_id, *c_ty);
+            let mut errors_buffer = Vec::new();
+            for (&local_id, c_ty) in sorted_user_provided_types {
+                let hir_id = hir::HirId { owner: common_hir_owner, local_id };
 
-            if let ty::UserType::TypeOf(_, user_substs) = c_ty.value {
-                if self.rustc_dump_user_substs {
+                if let ty::UserType::TypeOf(_, user_substs) = c_ty.value {
                     // This is a unit-testing mechanism.
                     let span = self.tcx().hir().span(hir_id);
                     // We need to buffer the errors in order to guarantee a consistent
@@ -504,31 +500,49 @@ impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
                     err.buffer(&mut errors_buffer);
                 }
             }
-        }
 
-        if !errors_buffer.is_empty() {
-            errors_buffer.sort_by_key(|diag| diag.span.primary_span());
-            for mut diag in errors_buffer {
-                self.tcx().sess.diagnostic().emit_diagnostic(&mut diag);
+            if !errors_buffer.is_empty() {
+                errors_buffer.sort_by_key(|diag| diag.span.primary_span());
+                for mut diag in errors_buffer {
+                    self.tcx().sess.diagnostic().emit_diagnostic(&mut diag);
+                }
             }
         }
+
+        self.typeck_results.user_provided_types_mut().extend(
+            fcx_typeck_results.user_provided_types().items().map(|(local_id, c_ty)| {
+                let hir_id = hir::HirId { owner: common_hir_owner, local_id };
+
+                if cfg!(debug_assertions) && c_ty.needs_infer() {
+                    span_bug!(
+                        hir_id.to_span(self.fcx.tcx),
+                        "writeback: `{:?}` has inference variables",
+                        c_ty
+                    );
+                };
+
+                (hir_id, *c_ty)
+            }),
+        );
     }
 
     fn visit_user_provided_sigs(&mut self) {
         let fcx_typeck_results = self.fcx.typeck_results.borrow();
         assert_eq!(fcx_typeck_results.hir_owner, self.typeck_results.hir_owner);
 
-        for (&def_id, c_sig) in fcx_typeck_results.user_provided_sigs.iter() {
-            if cfg!(debug_assertions) && c_sig.needs_infer() {
-                span_bug!(
-                    self.fcx.tcx.def_span(def_id),
-                    "writeback: `{:?}` has inference variables",
-                    c_sig
-                );
-            };
-
-            self.typeck_results.user_provided_sigs.insert(def_id, *c_sig);
-        }
+        self.typeck_results.user_provided_sigs.extend(
+            fcx_typeck_results.user_provided_sigs.items().map(|(&def_id, c_sig)| {
+                if cfg!(debug_assertions) && c_sig.needs_infer() {
+                    span_bug!(
+                        self.fcx.tcx.def_span(def_id),
+                        "writeback: `{:?}` has inference variables",
+                        c_sig
+                    );
+                };
+
+                (def_id, *c_sig)
+            }),
+        );
     }
 
     fn visit_generator_interior_types(&mut self) {
@@ -647,7 +661,10 @@ impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
         assert_eq!(fcx_typeck_results.hir_owner, self.typeck_results.hir_owner);
         let common_hir_owner = fcx_typeck_results.hir_owner;
 
-        for (&local_id, &fn_sig) in fcx_typeck_results.liberated_fn_sigs().iter() {
+        let fcx_liberated_fn_sigs =
+            fcx_typeck_results.liberated_fn_sigs().items_in_stable_order(self.tcx());
+
+        for (&local_id, &fn_sig) in fcx_liberated_fn_sigs {
             let hir_id = hir::HirId { owner: common_hir_owner, local_id };
             let fn_sig = self.resolve(fn_sig, &hir_id);
             self.typeck_results.liberated_fn_sigs_mut().insert(hir_id, fn_sig);
@@ -659,7 +676,10 @@ impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
         assert_eq!(fcx_typeck_results.hir_owner, self.typeck_results.hir_owner);
         let common_hir_owner = fcx_typeck_results.hir_owner;
 
-        for (&local_id, ftys) in fcx_typeck_results.fru_field_types().iter() {
+        let fcx_fru_field_types =
+            fcx_typeck_results.fru_field_types().items_in_stable_order(self.tcx());
+
+        for (&local_id, ftys) in fcx_fru_field_types {
             let hir_id = hir::HirId { owner: common_hir_owner, local_id };
             let ftys = self.resolve(ftys.clone(), &hir_id);
             self.typeck_results.fru_field_types_mut().insert(hir_id, ftys);
diff --git a/compiler/rustc_lint_defs/src/lib.rs b/compiler/rustc_lint_defs/src/lib.rs
index f4b4c5168bf..9aca485e502 100644
--- a/compiler/rustc_lint_defs/src/lib.rs
+++ b/compiler/rustc_lint_defs/src/lib.rs
@@ -6,8 +6,9 @@
 extern crate rustc_macros;
 
 pub use self::Level::*;
-use rustc_ast::node_id::{NodeId, NodeMap};
+use rustc_ast::node_id::NodeId;
 use rustc_ast::{AttrId, Attribute};
+use rustc_data_structures::fx::FxIndexMap;
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher, ToStableHashKey};
 use rustc_error_messages::{DiagnosticMessage, MultiSpan};
 use rustc_hir::HashStableContext;
@@ -544,7 +545,7 @@ pub struct BufferedEarlyLint {
 
 #[derive(Default)]
 pub struct LintBuffer {
-    pub map: NodeMap<Vec<BufferedEarlyLint>>,
+    pub map: FxIndexMap<NodeId, Vec<BufferedEarlyLint>>,
 }
 
 impl LintBuffer {
diff --git a/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs b/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs
index cb451931dfe..78997961d17 100644
--- a/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs
+++ b/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs
@@ -382,7 +382,7 @@ pub(in crate::rmeta) fn provide(providers: &mut Providers) {
             // keys from the former.
             // This is a rudimentary check that does not catch all cases,
             // just the easiest.
-            let mut fallback_map: DefIdMap<DefId> = Default::default();
+            let mut fallback_map: Vec<(DefId, DefId)> = Default::default();
 
             // Issue 46112: We want the map to prefer the shortest
             // paths when reporting the path to an item. Therefore we
@@ -412,12 +412,12 @@ pub(in crate::rmeta) fn provide(providers: &mut Providers) {
 
                 if let Some(def_id) = child.res.opt_def_id() {
                     if child.ident.name == kw::Underscore {
-                        fallback_map.insert(def_id, parent);
+                        fallback_map.push((def_id, parent));
                         return;
                     }
 
                     if ty::util::is_doc_hidden(tcx, parent) {
-                        fallback_map.insert(def_id, parent);
+                        fallback_map.push((def_id, parent));
                         return;
                     }
 
@@ -451,6 +451,7 @@ pub(in crate::rmeta) fn provide(providers: &mut Providers) {
             // Fill in any missing entries with the less preferable path.
             // If this path re-exports the child as `_`, we still use this
             // path in a diagnostic that suggests importing `::*`.
+
             for (child, parent) in fallback_map {
                 visible_parent_map.entry(child).or_insert(parent);
             }
diff --git a/compiler/rustc_metadata/src/rmeta/encoder.rs b/compiler/rustc_metadata/src/rmeta/encoder.rs
index a3d44fa890d..c3292681cc6 100644
--- a/compiler/rustc_metadata/src/rmeta/encoder.rs
+++ b/compiler/rustc_metadata/src/rmeta/encoder.rs
@@ -1187,8 +1187,11 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
                 record!(self.tables.trait_impl_trait_tys[def_id] <- table);
             }
         }
-        let inherent_impls = tcx.crate_inherent_impls(());
-        for (def_id, implementations) in inherent_impls.inherent_impls.iter() {
+        let inherent_impls = tcx.with_stable_hashing_context(|hcx| {
+            tcx.crate_inherent_impls(()).inherent_impls.to_sorted(&hcx)
+        });
+
+        for (def_id, implementations) in inherent_impls {
             if implementations.is_empty() {
                 continue;
             }
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index d681df14af1..7dfcd1bb507 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -38,7 +38,7 @@ use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_data_structures::tagged_ptr::CopyTaggedPtr;
 use rustc_hir as hir;
 use rustc_hir::def::{CtorKind, CtorOf, DefKind, LifetimeRes, Res};
-use rustc_hir::def_id::{CrateNum, DefId, LocalDefId, LocalDefIdMap};
+use rustc_hir::def_id::{CrateNum, DefId, DefIdMap, LocalDefId, LocalDefIdMap};
 use rustc_hir::Node;
 use rustc_index::vec::IndexVec;
 use rustc_macros::HashStable;
@@ -436,7 +436,7 @@ pub struct CrateVariancesMap<'tcx> {
     /// For each item with generics, maps to a vector of the variance
     /// of its generics. If an item has no generics, it will have no
     /// entry.
-    pub variances: FxHashMap<DefId, &'tcx [ty::Variance]>,
+    pub variances: DefIdMap<&'tcx [ty::Variance]>,
 }
 
 // Contains information needed to resolve types and (in the future) look up
diff --git a/compiler/rustc_middle/src/ty/typeck_results.rs b/compiler/rustc_middle/src/ty/typeck_results.rs
index 18281b5175c..0eaa47178c0 100644
--- a/compiler/rustc_middle/src/ty/typeck_results.rs
+++ b/compiler/rustc_middle/src/ty/typeck_results.rs
@@ -6,7 +6,12 @@ use crate::{
         GenericArgKind, InternalSubsts, SubstsRef, Ty, UserSubsts,
     },
 };
-use rustc_data_structures::{fx::FxHashMap, sync::Lrc, unord::UnordSet, vec_map::VecMap};
+use rustc_data_structures::{
+    fx::FxHashMap,
+    sync::Lrc,
+    unord::{UnordItems, UnordSet},
+    vec_map::VecMap,
+};
 use rustc_errors::ErrorGuaranteed;
 use rustc_hir as hir;
 use rustc_hir::{
@@ -20,13 +25,9 @@ use rustc_macros::HashStable;
 use rustc_middle::mir::FakeReadCause;
 use rustc_session::Session;
 use rustc_span::Span;
-use std::{
-    collections::hash_map::{self, Entry},
-    hash::Hash,
-    iter,
-};
+use std::{collections::hash_map::Entry, hash::Hash, iter};
 
-use super::RvalueScopes;
+use super::{RvalueScopes, TyCtxt};
 
 #[derive(TyEncodable, TyDecodable, Debug, HashStable)]
 pub struct TypeckResults<'tcx> {
@@ -567,8 +568,16 @@ impl<'a, V> LocalTableInContext<'a, V> {
         self.data.get(&id.local_id)
     }
 
-    pub fn iter(&self) -> hash_map::Iter<'_, hir::ItemLocalId, V> {
-        self.data.iter()
+    pub fn items(
+        &'a self,
+    ) -> UnordItems<(hir::ItemLocalId, &'a V), impl Iterator<Item = (hir::ItemLocalId, &'a V)>>
+    {
+        self.data.items().map(|(id, value)| (*id, value))
+    }
+
+    #[allow(rustc::pass_by_value)]
+    pub fn items_in_stable_order(&self, tcx: TyCtxt<'_>) -> Vec<(&'a ItemLocalId, &'a V)> {
+        tcx.with_stable_hashing_context(|hcx| self.data.to_sorted(&hcx))
     }
 }
 
@@ -605,6 +614,16 @@ impl<'a, V> LocalTableInContextMut<'a, V> {
         validate_hir_id_for_typeck_results(self.hir_owner, id);
         self.data.remove(&id.local_id)
     }
+
+    pub fn extend(
+        &mut self,
+        items: UnordItems<(hir::HirId, V), impl Iterator<Item = (hir::HirId, V)>>,
+    ) {
+        self.data.extend(items.map(|(id, value)| {
+            validate_hir_id_for_typeck_results(self.hir_owner, id);
+            (id.local_id, value)
+        }))
+    }
 }
 
 rustc_index::newtype_index! {
diff --git a/compiler/rustc_resolve/src/check_unused.rs b/compiler/rustc_resolve/src/check_unused.rs
index 32fb5e18276..eae4c9992eb 100644
--- a/compiler/rustc_resolve/src/check_unused.rs
+++ b/compiler/rustc_resolve/src/check_unused.rs
@@ -28,9 +28,9 @@ use crate::module_to_string;
 use crate::Resolver;
 
 use rustc_ast as ast;
-use rustc_ast::node_id::NodeMap;
 use rustc_ast::visit::{self, Visitor};
-use rustc_data_structures::fx::FxHashSet;
+use rustc_data_structures::fx::FxIndexMap;
+use rustc_data_structures::unord::UnordSet;
 use rustc_errors::{pluralize, MultiSpan};
 use rustc_session::lint::builtin::{MACRO_USE_EXTERN_CRATE, UNUSED_IMPORTS};
 use rustc_session::lint::BuiltinLintDiagnostics;
@@ -40,7 +40,7 @@ struct UnusedImport<'a> {
     use_tree: &'a ast::UseTree,
     use_tree_id: ast::NodeId,
     item_span: Span,
-    unused: FxHashSet<ast::NodeId>,
+    unused: UnordSet<ast::NodeId>,
 }
 
 impl<'a> UnusedImport<'a> {
@@ -52,7 +52,7 @@ impl<'a> UnusedImport<'a> {
 struct UnusedImportCheckVisitor<'a, 'b> {
     r: &'a mut Resolver<'b>,
     /// All the (so far) unused imports, grouped path list
-    unused_imports: NodeMap<UnusedImport<'a>>,
+    unused_imports: FxIndexMap<ast::NodeId, UnusedImport<'a>>,
     base_use_tree: Option<&'a ast::UseTree>,
     base_id: ast::NodeId,
     item_span: Span,
@@ -89,7 +89,7 @@ impl<'a, 'b> UnusedImportCheckVisitor<'a, 'b> {
             use_tree,
             use_tree_id,
             item_span,
-            unused: FxHashSet::default(),
+            unused: Default::default(),
         })
     }
 }
diff --git a/src/tools/clippy/clippy_lints/src/inherent_impl.rs b/src/tools/clippy/clippy_lints/src/inherent_impl.rs
index c5abcc46254..81b37ce5dfc 100644
--- a/src/tools/clippy/clippy_lints/src/inherent_impl.rs
+++ b/src/tools/clippy/clippy_lints/src/inherent_impl.rs
@@ -52,21 +52,19 @@ impl<'tcx> LateLintPass<'tcx> for MultipleInherentImpl {
         // List of spans to lint. (lint_span, first_span)
         let mut lint_spans = Vec::new();
 
-        for (_, impl_ids) in cx
+        let inherent_impls = cx
             .tcx
-            .crate_inherent_impls(())
-            .inherent_impls
-            .iter()
-            .filter(|(&id, impls)| {
-                impls.len() > 1
-                    // Check for `#[allow]` on the type definition
-                    && !is_lint_allowed(
-                        cx,
-                        MULTIPLE_INHERENT_IMPL,
-                        cx.tcx.hir().local_def_id_to_hir_id(id),
-                    )
-            })
-        {
+            .with_stable_hashing_context(|hcx| cx.tcx.crate_inherent_impls(()).inherent_impls.to_sorted(&hcx));
+
+        for (_, impl_ids) in inherent_impls.into_iter().filter(|(&id, impls)| {
+            impls.len() > 1
+            // Check for `#[allow]` on the type definition
+            && !is_lint_allowed(
+                cx,
+                MULTIPLE_INHERENT_IMPL,
+                cx.tcx.hir().local_def_id_to_hir_id(id),
+            )
+        }) {
             for impl_id in impl_ids.iter().map(|id| id.expect_local()) {
                 match type_map.entry(cx.tcx.type_of(impl_id)) {
                     Entry::Vacant(e) => {
diff --git a/src/tools/clippy/clippy_lints/src/loops/while_immutable_condition.rs b/src/tools/clippy/clippy_lints/src/loops/while_immutable_condition.rs
index a63422d2a36..d1a1f773f87 100644
--- a/src/tools/clippy/clippy_lints/src/loops/while_immutable_condition.rs
+++ b/src/tools/clippy/clippy_lints/src/loops/while_immutable_condition.rs
@@ -35,7 +35,7 @@ pub(super) fn check<'tcx>(cx: &LateContext<'tcx>, cond: &'tcx Expr<'_>, expr: &'
         } else {
             return;
         };
-    let mutable_static_in_cond = var_visitor.def_ids.iter().any(|(_, v)| *v);
+    let mutable_static_in_cond = var_visitor.def_ids.items().any(|(_, v)| *v);
 
     let mut has_break_or_return_visitor = HasBreakOrReturnVisitor {
         has_break_or_return: false,
diff --git a/src/tools/clippy/clippy_lints/src/missing_trait_methods.rs b/src/tools/clippy/clippy_lints/src/missing_trait_methods.rs
index 68af8a672f6..1c61c6e551c 100644
--- a/src/tools/clippy/clippy_lints/src/missing_trait_methods.rs
+++ b/src/tools/clippy/clippy_lints/src/missing_trait_methods.rs
@@ -80,19 +80,21 @@ impl<'tcx> LateLintPass<'tcx> for MissingTraitMethods {
                 }
             }
 
-            for assoc in provided.values() {
-                let source_map = cx.tcx.sess.source_map();
-                let definition_span = source_map.guess_head_span(cx.tcx.def_span(assoc.def_id));
+            cx.tcx.with_stable_hashing_context(|hcx| {
+                for assoc in provided.values_sorted(&hcx) {
+                    let source_map = cx.tcx.sess.source_map();
+                    let definition_span = source_map.guess_head_span(cx.tcx.def_span(assoc.def_id));
 
-                span_lint_and_help(
-                    cx,
-                    MISSING_TRAIT_METHODS,
-                    source_map.guess_head_span(item.span),
-                    &format!("missing trait method provided by default: `{}`", assoc.name),
-                    Some(definition_span),
-                    "implement the method",
-                );
-            }
+                    span_lint_and_help(
+                        cx,
+                        MISSING_TRAIT_METHODS,
+                        source_map.guess_head_span(item.span),
+                        &format!("missing trait method provided by default: `{}`", assoc.name),
+                        Some(definition_span),
+                        "implement the method",
+                    );
+                }
+            })
         }
     }
 }
diff --git a/src/tools/clippy/clippy_lints/src/pass_by_ref_or_value.rs b/src/tools/clippy/clippy_lints/src/pass_by_ref_or_value.rs
index 870a1c7d88d..2d21aaa4f7f 100644
--- a/src/tools/clippy/clippy_lints/src/pass_by_ref_or_value.rs
+++ b/src/tools/clippy/clippy_lints/src/pass_by_ref_or_value.rs
@@ -190,10 +190,10 @@ impl<'tcx> PassByRefOrValue {
                             // Don't lint if an unsafe pointer is created.
                             // TODO: Limit the check only to unsafe pointers to the argument (or part of the argument)
                             //       which escape the current function.
-                            if typeck.node_types().iter().any(|(_, &ty)| ty.is_unsafe_ptr())
+                            if typeck.node_types().items().any(|(_, &ty)| ty.is_unsafe_ptr())
                                 || typeck
                                     .adjustments()
-                                    .iter()
+                                    .items()
                                     .flat_map(|(_, a)| a)
                                     .any(|a| matches!(a.kind, Adjust::Pointer(PointerCast::UnsafeFnPointer)))
                             {