Auto merge of #106977 - michaelwoerister:unord_id_collections, r=oli-obk

Use UnordMap and UnordSet for id collections (DefIdMap, LocalDefIdMap, etc)

This PR changes the `rustc_data_structures::define_id_collections!` macro to use `UnordMap` and `UnordSet` instead of `FxHashMap` and `FxHashSet`. This should account for a large portion of hash-maps being used in places where they can cause trouble.

The changes required are moderate but non-zero:
- In some places the collections are extracted into sorted vecs.
- There are a few instances where for-loops have been changed to extends.

~~Let's see what the performance impact is. With a bit more refactoring, we might be able to get rid of some of the additional sorting -- but the change set is already big enough. Unless there's a performance impact, I'd like to do further changes in subsequent PRs.~~

Performance does not seem to be negatively affected ([perf-run here](https://github.com/rust-lang/rust/pull/106977#issuecomment-1396776699)).

Part of [MCP 533](https://github.com/rust-lang/compiler-team/issues/533).

r? `@ghost`

1 files changed, 6 insertions, 9 deletions

diff --git a/compiler/rustc_hir_analysis/src/variance/solve.rs b/compiler/rustc_hir_analysis/src/variance/solve.rs
index eab01b20094..a17edb598ad 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 {