Auto merge of #119192 - michaelwoerister:mcp533-push, r=cjgillot

Replace a number of FxHashMaps/Sets with stable-iteration-order alternatives

This PR replaces almost all of the remaining `FxHashMap`s in query results with either `FxIndexMap` or `UnordMap`. The only case that is missing is the `EffectiveVisibilities` struct which turned out to not be straightforward to transform. Once that is done too, we can remove the `HashStable` implementation from `HashMap`.

The first commit adds the `StableCompare` trait which is a companion trait to `StableOrd`. Some types like `Symbol` can be compared in a cross-session stable way, but their `Ord` implementation is not stable. In such cases, a `StableCompare` implementation can be provided to offer a lightweight way for stable sorting. The more heavyweight option is to sort via `ToStableHashKey`, but then sorting needs to have access to a stable hashing context and `ToStableHashKey` can also be expensive as in the case of `Symbol` where it has to allocate a `String`.

The rest of the commits are rather mechanical and don't overlap, so they are best reviewed individually.

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

3 files changed, 8 insertions, 6 deletions

diff --git a/compiler/rustc_hir_analysis/src/astconv/errors.rs b/compiler/rustc_hir_analysis/src/astconv/errors.rs
index d22c4fe201d..5e1c29440a5 100644
--- a/compiler/rustc_hir_analysis/src/astconv/errors.rs
+++ b/compiler/rustc_hir_analysis/src/astconv/errors.rs
@@ -6,6 +6,7 @@ use crate::errors::{
 use crate::fluent_generated as fluent;
 use crate::traits::error_reporting::report_object_safety_error;
 use rustc_data_structures::fx::{FxHashMap, FxIndexMap, FxIndexSet};
+use rustc_data_structures::unord::UnordMap;
 use rustc_errors::{pluralize, struct_span_err, Applicability, Diagnostic, ErrorGuaranteed};
 use rustc_hir as hir;
 use rustc_hir::def_id::{DefId, LocalDefId};
@@ -673,7 +674,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
                 }))
             })
             .flatten()
-            .collect::<FxHashMap<Symbol, &ty::AssocItem>>();
+            .collect::<UnordMap<Symbol, &ty::AssocItem>>();
 
         let mut names = names
             .into_iter()
@@ -709,7 +710,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         let mut where_constraints = vec![];
         let mut already_has_generics_args_suggestion = false;
         for (span, assoc_items) in &associated_types {
-            let mut names: FxHashMap<_, usize> = FxHashMap::default();
+            let mut names: UnordMap<_, usize> = Default::default();
             for item in assoc_items {
                 types_count += 1;
                 *names.entry(item.name).or_insert(0) += 1;
diff --git a/compiler/rustc_hir_analysis/src/check/compare_impl_item.rs b/compiler/rustc_hir_analysis/src/check/compare_impl_item.rs
index dbcaa244f29..cc4dc5aca0d 100644
--- a/compiler/rustc_hir_analysis/src/check/compare_impl_item.rs
+++ b/compiler/rustc_hir_analysis/src/check/compare_impl_item.rs
@@ -1,6 +1,6 @@
 use super::potentially_plural_count;
 use crate::errors::LifetimesOrBoundsMismatchOnTrait;
-use hir::def_id::{DefId, LocalDefId};
+use hir::def_id::{DefId, DefIdMap, LocalDefId};
 use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexSet};
 use rustc_errors::{pluralize, struct_span_err, Applicability, DiagnosticId, ErrorGuaranteed};
 use rustc_hir as hir;
@@ -478,7 +478,7 @@ fn compare_asyncness<'tcx>(
 pub(super) fn collect_return_position_impl_trait_in_trait_tys<'tcx>(
     tcx: TyCtxt<'tcx>,
     impl_m_def_id: LocalDefId,
-) -> Result<&'tcx FxHashMap<DefId, ty::EarlyBinder<Ty<'tcx>>>, ErrorGuaranteed> {
+) -> Result<&'tcx DefIdMap<ty::EarlyBinder<Ty<'tcx>>>, ErrorGuaranteed> {
     let impl_m = tcx.opt_associated_item(impl_m_def_id.to_def_id()).unwrap();
     let trait_m = tcx.opt_associated_item(impl_m.trait_item_def_id.unwrap()).unwrap();
     let impl_trait_ref =
@@ -706,7 +706,7 @@ pub(super) fn collect_return_position_impl_trait_in_trait_tys<'tcx>(
     );
     ocx.resolve_regions_and_report_errors(impl_m_def_id, &outlives_env)?;
 
-    let mut remapped_types = FxHashMap::default();
+    let mut remapped_types = DefIdMap::default();
     for (def_id, (ty, args)) in collected_types {
         match infcx.fully_resolve((ty, args)) {
             Ok((ty, args)) => {
diff --git a/compiler/rustc_hir_analysis/src/collect.rs b/compiler/rustc_hir_analysis/src/collect.rs
index 8aeab2ca67e..0a13949a688 100644
--- a/compiler/rustc_hir_analysis/src/collect.rs
+++ b/compiler/rustc_hir_analysis/src/collect.rs
@@ -16,6 +16,7 @@
 
 use rustc_data_structures::captures::Captures;
 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use rustc_data_structures::unord::UnordMap;
 use rustc_errors::{Applicability, DiagnosticBuilder, ErrorGuaranteed, StashKey};
 use rustc_hir as hir;
 use rustc_hir::def::DefKind;
@@ -979,7 +980,7 @@ fn trait_def(tcx: TyCtxt<'_>, def_id: LocalDefId) -> ty::TraitDef {
         })
         // Check for duplicates
         .and_then(|list| {
-            let mut set: FxHashMap<Symbol, Span> = FxHashMap::default();
+            let mut set: UnordMap<Symbol, Span> = Default::default();
             let mut no_dups = true;
 
             for ident in &*list {