Auto merge of #120812 - compiler-errors:impl-sorting, r=lcnr

Remove unnecessary impl sorting in queries and metadata

Removes unnecessary impl sorting because queries already return their keys in HIR definition order: https://github.com/rust-lang/rust/issues/120371#issuecomment-1926422838

r? `@cjgillot` or `@lcnr` -- unless I totally misunderstood what was being asked for here? 😆

fixes #120371

5 files changed, 59 insertions, 78 deletions

diff --git a/compiler/rustc_infer/src/traits/error_reporting/mod.rs b/compiler/rustc_infer/src/traits/error_reporting/mod.rs
index 7730fe29e09..83df1fd6510 100644
--- a/compiler/rustc_infer/src/traits/error_reporting/mod.rs
+++ b/compiler/rustc_infer/src/traits/error_reporting/mod.rs
@@ -177,13 +177,12 @@ pub fn report_object_safety_error<'tcx>(
             )));
         }
         impls => {
-            let mut types = impls
+            let types = impls
                 .iter()
                 .map(|t| {
                     with_no_trimmed_paths!(format!("  {}", tcx.type_of(*t).instantiate_identity(),))
                 })
                 .collect::<Vec<_>>();
-            types.sort();
             err.help(format!(
                 "the following types implement the trait, consider defining an enum where each \
                  variant holds one of these types, implementing `{}` for this new enum and using \
diff --git a/compiler/rustc_metadata/src/rmeta/decoder.rs b/compiler/rustc_metadata/src/rmeta/decoder.rs
index 0ba9b940eed..e5e430bc90d 100644
--- a/compiler/rustc_metadata/src/rmeta/decoder.rs
+++ b/compiler/rustc_metadata/src/rmeta/decoder.rs
@@ -7,6 +7,7 @@ use crate::rmeta::*;
 use rustc_ast as ast;
 use rustc_data_structures::captures::Captures;
 use rustc_data_structures::fingerprint::Fingerprint;
+use rustc_data_structures::fx::FxIndexMap;
 use rustc_data_structures::owned_slice::OwnedSlice;
 use rustc_data_structures::sync::{Lock, Lrc, OnceLock};
 use rustc_data_structures::unhash::UnhashMap;
@@ -83,12 +84,12 @@ pub(crate) struct CrateMetadata {
     /// Trait impl data.
     /// FIXME: Used only from queries and can use query cache,
     /// so pre-decoding can probably be avoided.
-    trait_impls: FxHashMap<(u32, DefIndex), LazyArray<(DefIndex, Option<SimplifiedType>)>>,
+    trait_impls: FxIndexMap<(u32, DefIndex), LazyArray<(DefIndex, Option<SimplifiedType>)>>,
     /// Inherent impls which do not follow the normal coherence rules.
     ///
     /// These can be introduced using either `#![rustc_coherence_is_core]`
     /// or `#[rustc_allow_incoherent_impl]`.
-    incoherent_impls: FxHashMap<SimplifiedType, LazyArray<DefIndex>>,
+    incoherent_impls: FxIndexMap<SimplifiedType, LazyArray<DefIndex>>,
     /// Proc macro descriptions for this crate, if it's a proc macro crate.
     raw_proc_macros: Option<&'static [ProcMacro]>,
     /// Source maps for code from the crate.
diff --git a/compiler/rustc_metadata/src/rmeta/encoder.rs b/compiler/rustc_metadata/src/rmeta/encoder.rs
index 8596a0645e4..6f31c0fa520 100644
--- a/compiler/rustc_metadata/src/rmeta/encoder.rs
+++ b/compiler/rustc_metadata/src/rmeta/encoder.rs
@@ -2,7 +2,7 @@ use crate::errors::{FailCreateFileEncoder, FailWriteFile};
 use crate::rmeta::*;
 
 use rustc_ast::Attribute;
-use rustc_data_structures::fx::FxIndexSet;
+use rustc_data_structures::fx::{FxIndexMap, FxIndexSet};
 use rustc_data_structures::memmap::{Mmap, MmapMut};
 use rustc_data_structures::sync::{join, par_for_each_in, Lrc};
 use rustc_data_structures::temp_dir::MaybeTempDir;
@@ -13,7 +13,6 @@ use rustc_hir_pretty::id_to_string;
 use rustc_middle::middle::dependency_format::Linkage;
 use rustc_middle::middle::exported_symbols::metadata_symbol_name;
 use rustc_middle::mir::interpret;
-use rustc_middle::query::LocalCrate;
 use rustc_middle::query::Providers;
 use rustc_middle::traits::specialization_graph;
 use rustc_middle::ty::codec::TyEncoder;
@@ -1509,10 +1508,7 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
             }
         }
 
-        let inherent_impls = tcx.with_stable_hashing_context(|hcx| {
-            tcx.crate_inherent_impls(()).unwrap().inherent_impls.to_sorted(&hcx, true)
-        });
-        for (def_id, impls) in inherent_impls {
+        for (def_id, impls) in &tcx.crate_inherent_impls(()).unwrap().inherent_impls {
             record_defaulted_array!(self.tables.inherent_impls[def_id.to_def_id()] <- impls.iter().map(|def_id| {
                 assert!(def_id.is_local());
                 def_id.index
@@ -2002,8 +1998,8 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
     fn encode_impls(&mut self) -> LazyArray<TraitImpls> {
         empty_proc_macro!(self);
         let tcx = self.tcx;
-        let mut fx_hash_map: FxHashMap<DefId, Vec<(DefIndex, Option<SimplifiedType>)>> =
-            FxHashMap::default();
+        let mut trait_impls: FxIndexMap<DefId, Vec<(DefIndex, Option<SimplifiedType>)>> =
+            FxIndexMap::default();
 
         for id in tcx.hir().items() {
             let DefKind::Impl { of_trait } = tcx.def_kind(id.owner_id) else {
@@ -2022,7 +2018,7 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
                     trait_ref.self_ty(),
                     TreatParams::AsCandidateKey,
                 );
-                fx_hash_map
+                trait_impls
                     .entry(trait_ref.def_id)
                     .or_default()
                     .push((id.owner_id.def_id.local_def_index, simplified_self_ty));
@@ -2043,47 +2039,30 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
             }
         }
 
-        let mut all_impls: Vec<_> = fx_hash_map.into_iter().collect();
-
-        // Bring everything into deterministic order for hashing
-        all_impls.sort_by_cached_key(|&(trait_def_id, _)| tcx.def_path_hash(trait_def_id));
-
-        let all_impls: Vec<_> = all_impls
+        let trait_impls: Vec<_> = trait_impls
             .into_iter()
-            .map(|(trait_def_id, mut impls)| {
-                // Bring everything into deterministic order for hashing
-                impls.sort_by_cached_key(|&(index, _)| {
-                    tcx.hir().def_path_hash(LocalDefId { local_def_index: index })
-                });
-
-                TraitImpls {
-                    trait_id: (trait_def_id.krate.as_u32(), trait_def_id.index),
-                    impls: self.lazy_array(&impls),
-                }
+            .map(|(trait_def_id, impls)| TraitImpls {
+                trait_id: (trait_def_id.krate.as_u32(), trait_def_id.index),
+                impls: self.lazy_array(&impls),
             })
             .collect();
 
-        self.lazy_array(&all_impls)
+        self.lazy_array(&trait_impls)
     }
 
     #[instrument(level = "debug", skip(self))]
     fn encode_incoherent_impls(&mut self) -> LazyArray<IncoherentImpls> {
         empty_proc_macro!(self);
         let tcx = self.tcx;
-        let all_impls = tcx.with_stable_hashing_context(|hcx| {
-            tcx.crate_inherent_impls(()).unwrap().incoherent_impls.to_sorted(&hcx, true)
-        });
 
-        let all_impls: Vec<_> = all_impls
-            .into_iter()
-            .map(|(&simp, impls)| {
-                let mut impls: Vec<_> =
-                    impls.into_iter().map(|def_id| def_id.local_def_index).collect();
-                impls.sort_by_cached_key(|&local_def_index| {
-                    tcx.hir().def_path_hash(LocalDefId { local_def_index })
-                });
-
-                IncoherentImpls { self_ty: simp, impls: self.lazy_array(impls) }
+        let all_impls: Vec<_> = tcx
+            .crate_inherent_impls(())
+            .unwrap()
+            .incoherent_impls
+            .iter()
+            .map(|(&simp, impls)| IncoherentImpls {
+                self_ty: simp,
+                impls: self.lazy_array(impls.iter().map(|def_id| def_id.local_def_index)),
             })
             .collect();
 
@@ -2327,32 +2306,6 @@ pub fn provide(providers: &mut Providers) {
                 span_bug!(tcx.def_span(def_id), "no traits in scope for a doc link")
             })
         },
-        traits: |tcx, LocalCrate| {
-            let mut traits = Vec::new();
-            for id in tcx.hir().items() {
-                if matches!(tcx.def_kind(id.owner_id), DefKind::Trait | DefKind::TraitAlias) {
-                    traits.push(id.owner_id.to_def_id())
-                }
-            }
-
-            // Bring everything into deterministic order.
-            traits.sort_by_cached_key(|&def_id| tcx.def_path_hash(def_id));
-            tcx.arena.alloc_slice(&traits)
-        },
-        trait_impls_in_crate: |tcx, LocalCrate| {
-            let mut trait_impls = Vec::new();
-            for id in tcx.hir().items() {
-                if matches!(tcx.def_kind(id.owner_id), DefKind::Impl { .. })
-                    && tcx.impl_trait_ref(id.owner_id).is_some()
-                {
-                    trait_impls.push(id.owner_id.to_def_id())
-                }
-            }
-
-            // Bring everything into deterministic order.
-            trait_impls.sort_by_cached_key(|&def_id| tcx.def_path_hash(def_id));
-            tcx.arena.alloc_slice(&trait_impls)
-        },
 
         ..*providers
     }
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index bd073cd891f..558590af7ec 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -40,7 +40,6 @@ use rustc_data_structures::intern::Interned;
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_data_structures::steal::Steal;
 use rustc_data_structures::tagged_ptr::CopyTaggedPtr;
-use rustc_data_structures::unord::UnordMap;
 use rustc_errors::{Diag, ErrorGuaranteed, StashKey};
 use rustc_hir as hir;
 use rustc_hir::def::{CtorKind, CtorOf, DefKind, DocLinkResMap, LifetimeRes, Res};
@@ -2083,6 +2082,8 @@ pub fn provide(providers: &mut Providers) {
     *providers = Providers {
         trait_impls_of: trait_def::trait_impls_of_provider,
         incoherent_impls: trait_def::incoherent_impls_provider,
+        trait_impls_in_crate: trait_def::trait_impls_in_crate_provider,
+        traits: trait_def::traits_provider,
         const_param_default: consts::const_param_default,
         vtable_allocation: vtable::vtable_allocation_provider,
         ..*providers
@@ -2096,8 +2097,8 @@ pub fn provide(providers: &mut Providers) {
 /// (constructing this map requires touching the entire crate).
 #[derive(Clone, Debug, Default, HashStable)]
 pub struct CrateInherentImpls {
-    pub inherent_impls: LocalDefIdMap<Vec<DefId>>,
-    pub incoherent_impls: UnordMap<SimplifiedType, Vec<LocalDefId>>,
+    pub inherent_impls: FxIndexMap<LocalDefId, Vec<DefId>>,
+    pub incoherent_impls: FxIndexMap<SimplifiedType, Vec<LocalDefId>>,
 }
 
 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, TyEncodable, HashStable)]
diff --git a/compiler/rustc_middle/src/ty/trait_def.rs b/compiler/rustc_middle/src/ty/trait_def.rs
index da5860043c9..3bd9f6ad11b 100644
--- a/compiler/rustc_middle/src/ty/trait_def.rs
+++ b/compiler/rustc_middle/src/ty/trait_def.rs
@@ -1,16 +1,19 @@
-use crate::traits::specialization_graph;
-use crate::ty::fast_reject::{self, SimplifiedType, TreatParams};
-use crate::ty::{Ident, Ty, TyCtxt};
-use hir::def_id::LOCAL_CRATE;
-use rustc_hir as hir;
-use rustc_hir::def_id::DefId;
 use std::iter;
 use tracing::debug;
 
 use rustc_data_structures::fx::FxIndexMap;
 use rustc_errors::ErrorGuaranteed;
+use rustc_hir as hir;
+use rustc_hir::def::DefKind;
+use rustc_hir::def_id::DefId;
+use rustc_hir::def_id::LOCAL_CRATE;
 use rustc_macros::{Decodable, Encodable, HashStable};
 
+use crate::query::LocalCrate;
+use crate::traits::specialization_graph;
+use crate::ty::fast_reject::{self, SimplifiedType, TreatParams};
+use crate::ty::{Ident, Ty, TyCtxt};
+
 /// A trait's definition with type information.
 #[derive(HashStable, Encodable, Decodable)]
 pub struct TraitDef {
@@ -274,3 +277,27 @@ pub(super) fn incoherent_impls_provider(
 
     Ok(tcx.arena.alloc_slice(&impls))
 }
+
+pub(super) fn traits_provider(tcx: TyCtxt<'_>, _: LocalCrate) -> &[DefId] {
+    let mut traits = Vec::new();
+    for id in tcx.hir().items() {
+        if matches!(tcx.def_kind(id.owner_id), DefKind::Trait | DefKind::TraitAlias) {
+            traits.push(id.owner_id.to_def_id())
+        }
+    }
+
+    tcx.arena.alloc_slice(&traits)
+}
+
+pub(super) fn trait_impls_in_crate_provider(tcx: TyCtxt<'_>, _: LocalCrate) -> &[DefId] {
+    let mut trait_impls = Vec::new();
+    for id in tcx.hir().items() {
+        if matches!(tcx.def_kind(id.owner_id), DefKind::Impl { .. })
+            && tcx.impl_trait_ref(id.owner_id).is_some()
+        {
+            trait_impls.push(id.owner_id.to_def_id())
+        }
+    }
+
+    tcx.arena.alloc_slice(&trait_impls)
+}