Auto merge of #75008 - eddyb:rmeta-indexed-trait-impls, r=nikomatsakis

rustc_metadata: track the simplified Self type for every trait impl.

For the `traits_impls_of` query, we index the impls by `fast_reject::SimplifiedType` (a "shallow type"), which allows some simple cases like `impl Trait<..> for Foo<..>` to be efficiently iterated over, by e.g. `for_each_relevant_impl`.

This PR encodes the `fast_reject::SimplifiedType` cross-crate to avoid needing to deserialize the `Self` type of every `impl` in order to simplify it - the simplification itself should be cheap, but the deserialization is less so.

We could go further from here and make loading the list of impls lazy, for a given simplified `Self` type, but that would have more complicated implications for performance, and this PR doesn't do anything in that regard.

r? @nikomatsakis cc @Mark-Simulacrum

3 files changed, 23 insertions, 12 deletions

diff --git a/src/librustc_metadata/rmeta/decoder.rs b/src/librustc_metadata/rmeta/decoder.rs
index 10dc407c060..9fb4e08e284 100644
--- a/src/librustc_metadata/rmeta/decoder.rs
+++ b/src/librustc_metadata/rmeta/decoder.rs
@@ -78,7 +78,8 @@ 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), Lazy<[DefIndex]>>,
+    trait_impls:
+        FxHashMap<(u32, DefIndex), Lazy<[(DefIndex, Option<ty::fast_reject::SimplifiedType>)]>>,
     /// 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.
@@ -1289,7 +1290,7 @@ impl<'a, 'tcx> CrateMetadataRef<'a> {
         &self,
         tcx: TyCtxt<'tcx>,
         filter: Option<DefId>,
-    ) -> &'tcx [DefId] {
+    ) -> &'tcx [(DefId, Option<ty::fast_reject::SimplifiedType>)] {
         if self.root.is_proc_macro_crate() {
             // proc-macro crates export no trait impls.
             return &[];
@@ -1305,16 +1306,20 @@ impl<'a, 'tcx> CrateMetadataRef<'a> {
 
         if let Some(filter) = filter {
             if let Some(impls) = self.trait_impls.get(&filter) {
-                tcx.arena.alloc_from_iter(impls.decode(self).map(|idx| self.local_def_id(idx)))
+                tcx.arena.alloc_from_iter(
+                    impls.decode(self).map(|(idx, simplified_self_ty)| {
+                        (self.local_def_id(idx), simplified_self_ty)
+                    }),
+                )
             } else {
                 &[]
             }
         } else {
-            tcx.arena.alloc_from_iter(
-                self.trait_impls
-                    .values()
-                    .flat_map(|impls| impls.decode(self).map(|idx| self.local_def_id(idx))),
-            )
+            tcx.arena.alloc_from_iter(self.trait_impls.values().flat_map(|impls| {
+                impls
+                    .decode(self)
+                    .map(|(idx, simplified_self_ty)| (self.local_def_id(idx), simplified_self_ty))
+            }))
         }
     }
 
diff --git a/src/librustc_metadata/rmeta/encoder.rs b/src/librustc_metadata/rmeta/encoder.rs
index aec9e8daa0f..acae44e6bf7 100644
--- a/src/librustc_metadata/rmeta/encoder.rs
+++ b/src/librustc_metadata/rmeta/encoder.rs
@@ -1610,7 +1610,7 @@ impl EncodeContext<'a, 'tcx> {
             .into_iter()
             .map(|(trait_def_id, mut impls)| {
                 // Bring everything into deterministic order for hashing
-                impls.sort_by_cached_key(|&index| {
+                impls.sort_by_cached_key(|&(index, _)| {
                     tcx.hir().definitions().def_path_hash(LocalDefId { local_def_index: index })
                 });
 
@@ -1852,7 +1852,7 @@ impl EncodeContext<'a, 'tcx> {
 
 struct ImplVisitor<'tcx> {
     tcx: TyCtxt<'tcx>,
-    impls: FxHashMap<DefId, Vec<DefIndex>>,
+    impls: FxHashMap<DefId, Vec<(DefIndex, Option<ty::fast_reject::SimplifiedType>)>>,
 }
 
 impl<'tcx, 'v> ItemLikeVisitor<'v> for ImplVisitor<'tcx> {
@@ -1860,7 +1860,13 @@ impl<'tcx, 'v> ItemLikeVisitor<'v> for ImplVisitor<'tcx> {
         if let hir::ItemKind::Impl { .. } = item.kind {
             let impl_id = self.tcx.hir().local_def_id(item.hir_id);
             if let Some(trait_ref) = self.tcx.impl_trait_ref(impl_id.to_def_id()) {
-                self.impls.entry(trait_ref.def_id).or_default().push(impl_id.local_def_index);
+                let simplified_self_ty =
+                    ty::fast_reject::simplify_type(self.tcx, trait_ref.self_ty(), false);
+
+                self.impls
+                    .entry(trait_ref.def_id)
+                    .or_default()
+                    .push((impl_id.local_def_index, simplified_self_ty));
             }
         }
     }
diff --git a/src/librustc_metadata/rmeta/mod.rs b/src/librustc_metadata/rmeta/mod.rs
index 465461ebf97..1c287be9f6b 100644
--- a/src/librustc_metadata/rmeta/mod.rs
+++ b/src/librustc_metadata/rmeta/mod.rs
@@ -233,7 +233,7 @@ crate struct CrateDep {
 #[derive(RustcEncodable, RustcDecodable)]
 crate struct TraitImpls {
     trait_id: (u32, DefIndex),
-    impls: Lazy<[DefIndex]>,
+    impls: Lazy<[(DefIndex, Option<ty::fast_reject::SimplifiedType>)]>,
 }
 
 /// Define `LazyTables` and `TableBuilders` at the same time.