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).

2 files changed, 11 insertions, 10 deletions

diff --git a/compiler/rustc_lint/src/foreign_modules.rs b/compiler/rustc_lint/src/foreign_modules.rs
index 31d9c0d33fe..ecb7a157f39 100644
--- a/compiler/rustc_lint/src/foreign_modules.rs
+++ b/compiler/rustc_lint/src/foreign_modules.rs
@@ -1,5 +1,5 @@
-use rustc_data_structures::fx::{FxHashMap, FxHashSet};
 use rustc_data_structures::stack::ensure_sufficient_stack;
+use rustc_data_structures::unord::{UnordMap, UnordSet};
 use rustc_hir as hir;
 use rustc_hir::def::DefKind;
 use rustc_middle::query::Providers;
@@ -72,7 +72,7 @@ struct ClashingExternDeclarations {
     /// the symbol should be reported as a clashing declaration.
     // FIXME: Technically, we could just store a &'tcx str here without issue; however, the
     // `impl_lint_pass` macro doesn't currently support lints parametric over a lifetime.
-    seen_decls: FxHashMap<Symbol, hir::OwnerId>,
+    seen_decls: UnordMap<Symbol, hir::OwnerId>,
 }
 
 /// Differentiate between whether the name for an extern decl came from the link_name attribute or
@@ -96,7 +96,7 @@ impl SymbolName {
 
 impl ClashingExternDeclarations {
     pub(crate) fn new() -> Self {
-        ClashingExternDeclarations { seen_decls: FxHashMap::default() }
+        ClashingExternDeclarations { seen_decls: Default::default() }
     }
 
     /// Insert a new foreign item into the seen set. If a symbol with the same name already exists
@@ -209,12 +209,12 @@ fn structurally_same_type<'tcx>(
     b: Ty<'tcx>,
     ckind: types::CItemKind,
 ) -> bool {
-    let mut seen_types = FxHashSet::default();
+    let mut seen_types = UnordSet::default();
     structurally_same_type_impl(&mut seen_types, tcx, param_env, a, b, ckind)
 }
 
 fn structurally_same_type_impl<'tcx>(
-    seen_types: &mut FxHashSet<(Ty<'tcx>, Ty<'tcx>)>,
+    seen_types: &mut UnordSet<(Ty<'tcx>, Ty<'tcx>)>,
     tcx: TyCtxt<'tcx>,
     param_env: ty::ParamEnv<'tcx>,
     a: Ty<'tcx>,
diff --git a/compiler/rustc_lint/src/non_ascii_idents.rs b/compiler/rustc_lint/src/non_ascii_idents.rs
index 08b2bf6af37..3405dd3a916 100644
--- a/compiler/rustc_lint/src/non_ascii_idents.rs
+++ b/compiler/rustc_lint/src/non_ascii_idents.rs
@@ -4,7 +4,8 @@ use crate::lints::{
 };
 use crate::{EarlyContext, EarlyLintPass, LintContext};
 use rustc_ast as ast;
-use rustc_data_structures::fx::FxHashMap;
+use rustc_data_structures::fx::FxIndexMap;
+use rustc_data_structures::unord::UnordMap;
 use rustc_span::symbol::Symbol;
 
 declare_lint! {
@@ -194,8 +195,8 @@ impl EarlyLintPass for NonAsciiIdents {
         }
 
         if has_non_ascii_idents && check_confusable_idents {
-            let mut skeleton_map: FxHashMap<Symbol, (Symbol, Span, bool)> =
-                FxHashMap::with_capacity_and_hasher(symbols.len(), Default::default());
+            let mut skeleton_map: UnordMap<Symbol, (Symbol, Span, bool)> =
+                UnordMap::with_capacity(symbols.len());
             let mut skeleton_buf = String::new();
 
             for (&symbol, &sp) in symbols.iter() {
@@ -248,8 +249,8 @@ impl EarlyLintPass for NonAsciiIdents {
                 Verified,
             }
 
-            let mut script_states: FxHashMap<AugmentedScriptSet, ScriptSetUsage> =
-                FxHashMap::default();
+            let mut script_states: FxIndexMap<AugmentedScriptSet, ScriptSetUsage> =
+                Default::default();
             let latin_augmented_script_set = AugmentedScriptSet::for_char('A');
             script_states.insert(latin_augmented_script_set, ScriptSetUsage::Verified);