Add query to avoid name comparison in `leaf_def`

8 files changed, 114 insertions, 89 deletions

diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs
index b3db2e63400..f1c2be660bc 100644
--- a/compiler/rustc_middle/src/query/mod.rs
+++ b/compiler/rustc_middle/src/query/mod.rs
@@ -630,6 +630,32 @@ rustc_queries! {
         desc { |tcx| "collecting associated items of {}", tcx.def_path_str(key) }
     }
 
+    /// Maps from associated items on a trait to the corresponding associated
+    /// item on the impl specified by `impl_id`.
+    ///
+    /// For example, with the following code
+    ///
+    /// ```
+    /// struct Type {}
+    ///                         // DefId
+    /// trait Trait {           // trait_id
+    ///     fn f();             // trait_f
+    ///     fn g() {}           // trait_g
+    /// }
+    ///
+    /// impl Trait for Type {   // impl_id
+    ///     fn f() {}           // impl_f
+    ///     fn g() {}           // impl_g
+    /// }
+    /// ```
+    ///
+    /// The map returned for `tcx.impl_item_implementor_ids(impl_id)` would be
+    ///`{ trait_f: impl_f, trait_g: impl_g }`
+    query impl_item_implementor_ids(impl_id: DefId) -> FxHashMap<DefId, DefId> {
+        desc { |tcx| "comparing impl items against trait for {}", tcx.def_path_str(impl_id) }
+        storage(ArenaCacheSelector<'tcx>)
+    }
+
     /// Given an `impl_id`, return the trait it implements.
     /// Return `None` if this is an inherent impl.
     query impl_trait_ref(impl_id: DefId) -> Option<ty::TraitRef<'tcx>> {
diff --git a/compiler/rustc_middle/src/traits/specialization_graph.rs b/compiler/rustc_middle/src/traits/specialization_graph.rs
index 3e9cd6b46b2..087be313b26 100644
--- a/compiler/rustc_middle/src/traits/specialization_graph.rs
+++ b/compiler/rustc_middle/src/traits/specialization_graph.rs
@@ -4,7 +4,6 @@ use crate::ty::{self, TyCtxt};
 use rustc_data_structures::fx::FxIndexMap;
 use rustc_errors::ErrorReported;
 use rustc_hir::def_id::{DefId, DefIdMap};
-use rustc_span::symbol::Ident;
 
 /// A per-trait graph of impls in specialization order. At the moment, this
 /// graph forms a tree rooted with the trait itself, with all other nodes
@@ -75,34 +74,28 @@ pub enum Node {
     Trait(DefId),
 }
 
-impl<'tcx> Node {
+impl Node {
     pub fn is_from_trait(&self) -> bool {
         matches!(self, Node::Trait(..))
     }
 
-    /// Iterate over the items defined directly by the given (impl or trait) node.
-    pub fn items(&self, tcx: TyCtxt<'tcx>) -> impl 'tcx + Iterator<Item = &'tcx ty::AssocItem> {
-        tcx.associated_items(self.def_id()).in_definition_order()
-    }
-
-    /// Finds an associated item defined in this node.
+    /// Trys to find the associated item that implements `trait_item_def_id`
+    /// defined in this node.
     ///
     /// If this returns `None`, the item can potentially still be found in
     /// parents of this node.
-    pub fn item(
+    pub fn item<'tcx>(
         &self,
         tcx: TyCtxt<'tcx>,
-        trait_item_name: Ident,
-        trait_item_kind: ty::AssocKind,
-        trait_def_id: DefId,
-    ) -> Option<ty::AssocItem> {
-        tcx.associated_items(self.def_id())
-            .filter_by_name_unhygienic(trait_item_name.name)
-            .find(move |impl_item| {
-                trait_item_kind == impl_item.kind
-                    && tcx.hygienic_eq(impl_item.ident, trait_item_name, trait_def_id)
-            })
-            .copied()
+        trait_item_def_id: DefId,
+    ) -> Option<&'tcx ty::AssocItem> {
+        match *self {
+            Node::Trait(_) => Some(tcx.associated_item(trait_item_def_id)),
+            Node::Impl(impl_def_id) => {
+                let id = tcx.impl_item_implementor_ids(impl_def_id).get(&trait_item_def_id)?;
+                Some(tcx.associated_item(*id))
+            }
+        }
     }
 
     pub fn def_id(&self) -> DefId {
@@ -181,17 +174,11 @@ impl LeafDef {
 impl<'tcx> Ancestors<'tcx> {
     /// Finds the bottom-most (ie. most specialized) definition of an associated
     /// item.
-    pub fn leaf_def(
-        mut self,
-        tcx: TyCtxt<'tcx>,
-        trait_item_name: Ident,
-        trait_item_kind: ty::AssocKind,
-    ) -> Option<LeafDef> {
-        let trait_def_id = self.trait_def_id;
+    pub fn leaf_def(mut self, tcx: TyCtxt<'tcx>, trait_item_def_id: DefId) -> Option<LeafDef> {
         let mut finalizing_node = None;
 
         self.find_map(|node| {
-            if let Some(item) = node.item(tcx, trait_item_name, trait_item_kind, trait_def_id) {
+            if let Some(item) = node.item(tcx, trait_item_def_id) {
                 if finalizing_node.is_none() {
                     let is_specializable = item.defaultness.is_default()
                         || tcx.impl_defaultness(node.def_id()).is_default();
@@ -201,7 +188,7 @@ impl<'tcx> Ancestors<'tcx> {
                     }
                 }
 
-                Some(LeafDef { item, defining_node: node, finalizing_node })
+                Some(LeafDef { item: *item, defining_node: node, finalizing_node })
             } else {
                 // Item not mentioned. This "finalizes" any defaulted item provided by an ancestor.
                 finalizing_node = Some(node);
diff --git a/compiler/rustc_monomorphize/src/collector.rs b/compiler/rustc_monomorphize/src/collector.rs
index b70c24b76d5..3e06e7f36d4 100644
--- a/compiler/rustc_monomorphize/src/collector.rs
+++ b/compiler/rustc_monomorphize/src/collector.rs
@@ -1310,10 +1310,9 @@ fn create_mono_items_for_default_impls<'tcx>(
             if let Some(trait_ref) = tcx.impl_trait_ref(item.def_id) {
                 let param_env = ty::ParamEnv::reveal_all();
                 let trait_ref = tcx.normalize_erasing_regions(param_env, trait_ref);
-                let overridden_methods: FxHashSet<_> =
-                    impl_.items.iter().map(|iiref| iiref.ident.normalize_to_macros_2_0()).collect();
+                let overridden_methods = tcx.impl_item_implementor_ids(item.def_id);
                 for method in tcx.provided_trait_methods(trait_ref.def_id) {
-                    if overridden_methods.contains(&method.ident.normalize_to_macros_2_0()) {
+                    if overridden_methods.contains_key(&method.def_id) {
                         continue;
                     }
 
diff --git a/compiler/rustc_passes/src/check_const.rs b/compiler/rustc_passes/src/check_const.rs
index a5a65740707..b755f686f6a 100644
--- a/compiler/rustc_passes/src/check_const.rs
+++ b/compiler/rustc_passes/src/check_const.rs
@@ -93,26 +93,29 @@ impl<'tcx> hir::itemlikevisit::ItemLikeVisitor<'tcx> for CheckConstTraitVisitor<
                     for trait_item in self.tcx.associated_items(trait_def_id).in_definition_order()
                     {
                         if let ty::AssocItem {
-                            kind: ty::AssocKind::Fn, ident, defaultness, ..
-                        } = trait_item
+                            kind: ty::AssocKind::Fn,
+                            defaultness,
+                            def_id: trait_item_id,
+                            ..
+                        } = *trait_item
                         {
                             // we can ignore functions that do not have default bodies:
                             // if those are unimplemented it will be catched by typeck.
                             if !defaultness.has_value()
                                 || self
                                     .tcx
-                                    .has_attr(trait_item.def_id, sym::default_method_body_is_const)
+                                    .has_attr(trait_item_id, sym::default_method_body_is_const)
                             {
                                 continue;
                             }
 
                             let is_implemented = ancestors
-                                .leaf_def(self.tcx, trait_item.ident, trait_item.kind)
+                                .leaf_def(self.tcx, trait_item_id)
                                 .map(|node_item| !node_item.defining_node.is_from_trait())
                                 .unwrap_or(false);
 
                             if !is_implemented {
-                                to_implement.push(ident.to_string());
+                                to_implement.push(self.tcx.item_name(trait_item_id).to_string());
                             }
                         }
                     }
diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs
index 23f615a9618..51bd505366c 100644
--- a/compiler/rustc_trait_selection/src/traits/project.rs
+++ b/compiler/rustc_trait_selection/src/traits/project.rs
@@ -1883,7 +1883,6 @@ fn assoc_ty_def(
     assoc_ty_def_id: DefId,
 ) -> Result<specialization_graph::LeafDef, ErrorReported> {
     let tcx = selcx.tcx();
-    let assoc_ty_name = tcx.associated_item(assoc_ty_def_id).ident;
     let trait_def_id = tcx.impl_trait_ref(impl_def_id).unwrap().def_id;
     let trait_def = tcx.trait_def(trait_def_id);
 
@@ -1893,21 +1892,18 @@ fn assoc_ty_def(
     // for the associated item at the given impl.
     // If there is no such item in that impl, this function will fail with a
     // cycle error if the specialization graph is currently being built.
-    let impl_node = specialization_graph::Node::Impl(impl_def_id);
-    for item in impl_node.items(tcx) {
-        if matches!(item.kind, ty::AssocKind::Type)
-            && tcx.hygienic_eq(item.ident, assoc_ty_name, trait_def_id)
-        {
-            return Ok(specialization_graph::LeafDef {
-                item: *item,
-                defining_node: impl_node,
-                finalizing_node: if item.defaultness.is_default() { None } else { Some(impl_node) },
-            });
-        }
+    if let Some(&impl_item_id) = tcx.impl_item_implementor_ids(impl_def_id).get(&assoc_ty_def_id) {
+        let item = tcx.associated_item(impl_item_id);
+        let impl_node = specialization_graph::Node::Impl(impl_def_id);
+        return Ok(specialization_graph::LeafDef {
+            item: *item,
+            defining_node: impl_node,
+            finalizing_node: if item.defaultness.is_default() { None } else { Some(impl_node) },
+        });
     }
 
     let ancestors = trait_def.ancestors(tcx, impl_def_id)?;
-    if let Some(assoc_item) = ancestors.leaf_def(tcx, assoc_ty_name, ty::AssocKind::Type) {
+    if let Some(assoc_item) = ancestors.leaf_def(tcx, assoc_ty_def_id) {
         Ok(assoc_item)
     } else {
         // This is saying that neither the trait nor
@@ -1916,7 +1912,11 @@ fn assoc_ty_def(
         // could only arise through a compiler bug --
         // if the user wrote a bad item name, it
         // should have failed in astconv.
-        bug!("No associated type `{}` for {}", assoc_ty_name, tcx.def_path_str(impl_def_id))
+        bug!(
+            "No associated type `{}` for {}",
+            tcx.item_name(assoc_ty_def_id),
+            tcx.def_path_str(impl_def_id)
+        )
     }
 }
 
diff --git a/compiler/rustc_trait_selection/src/traits/wf.rs b/compiler/rustc_trait_selection/src/traits/wf.rs
index 4bd73ef68aa..72ffe9085cb 100644
--- a/compiler/rustc_trait_selection/src/traits/wf.rs
+++ b/compiler/rustc_trait_selection/src/traits/wf.rs
@@ -197,14 +197,13 @@ fn extend_cause_with_original_assoc_item_obligation<'tcx>(
     item: Option<&hir::Item<'tcx>>,
     cause: &mut traits::ObligationCause<'tcx>,
     pred: &ty::Predicate<'tcx>,
-    mut trait_assoc_items: impl Iterator<Item = &'tcx ty::AssocItem>,
 ) {
     debug!(
         "extended_cause_with_original_assoc_item_obligation {:?} {:?} {:?} {:?}",
         trait_ref, item, cause, pred
     );
-    let items = match item {
-        Some(hir::Item { kind: hir::ItemKind::Impl(impl_), .. }) => impl_.items,
+    let (items, impl_def_id) = match item {
+        Some(hir::Item { kind: hir::ItemKind::Impl(impl_), def_id, .. }) => (impl_.items, *def_id),
         _ => return,
     };
     let fix_span =
@@ -222,11 +221,16 @@ fn extend_cause_with_original_assoc_item_obligation<'tcx>(
             // `src/test/ui/associated-types/point-at-type-on-obligation-failure.rs` and
             // `traits-assoc-type-in-supertrait-bad.rs`.
             if let ty::Projection(projection_ty) = proj.ty.kind() {
-                let trait_assoc_item = tcx.associated_item(projection_ty.item_def_id);
-                if let Some(impl_item_span) =
-                    items.iter().find(|item| item.ident == trait_assoc_item.ident).map(fix_span)
+                if let Some(&impl_item_id) =
+                    tcx.impl_item_implementor_ids(impl_def_id).get(&projection_ty.item_def_id)
                 {
-                    cause.span = impl_item_span;
+                    if let Some(impl_item_span) = items
+                        .iter()
+                        .find(|item| item.id.def_id.to_def_id() == impl_item_id)
+                        .map(fix_span)
+                    {
+                        cause.span = impl_item_span;
+                    }
                 }
             }
         }
@@ -235,13 +239,16 @@ fn extend_cause_with_original_assoc_item_obligation<'tcx>(
             // can be seen in `ui/associated-types/point-at-type-on-obligation-failure-2.rs`.
             debug!("extended_cause_with_original_assoc_item_obligation trait proj {:?}", pred);
             if let ty::Projection(ty::ProjectionTy { item_def_id, .. }) = *pred.self_ty().kind() {
-                if let Some(impl_item_span) = trait_assoc_items
-                    .find(|i| i.def_id == item_def_id)
-                    .and_then(|trait_assoc_item| {
-                        items.iter().find(|i| i.ident == trait_assoc_item.ident).map(fix_span)
-                    })
+                if let Some(&impl_item_id) =
+                    tcx.impl_item_implementor_ids(impl_def_id).get(&item_def_id)
                 {
-                    cause.span = impl_item_span;
+                    if let Some(impl_item_span) = items
+                        .iter()
+                        .find(|item| item.id.def_id.to_def_id() == impl_item_id)
+                        .map(fix_span)
+                    {
+                        cause.span = impl_item_span;
+                    }
                 }
             }
         }
@@ -312,7 +319,6 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
                 item,
                 &mut cause,
                 &obligation.predicate,
-                tcx.associated_items(trait_ref.def_id).in_definition_order(),
             );
             traits::Obligation::with_depth(cause, depth, param_env, obligation.predicate)
         };
diff --git a/compiler/rustc_ty_utils/src/assoc.rs b/compiler/rustc_ty_utils/src/assoc.rs
index 37c2f987b77..b1d47f6c29a 100644
--- a/compiler/rustc_ty_utils/src/assoc.rs
+++ b/compiler/rustc_ty_utils/src/assoc.rs
@@ -1,3 +1,4 @@
+use rustc_data_structures::fx::FxHashMap;
 use rustc_errors::struct_span_err;
 use rustc_hir as hir;
 use rustc_hir::def_id::{DefId, LocalDefId};
@@ -8,6 +9,7 @@ pub fn provide(providers: &mut ty::query::Providers) {
         associated_item,
         associated_item_def_ids,
         associated_items,
+        impl_item_implementor_ids,
         trait_of_item,
         ..*providers
     };
@@ -32,6 +34,13 @@ fn associated_items(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AssocItems<'_> {
     ty::AssocItems::new(items)
 }
 
+fn impl_item_implementor_ids(tcx: TyCtxt<'_>, impl_id: DefId) -> FxHashMap<DefId, DefId> {
+    tcx.associated_items(impl_id)
+        .in_definition_order()
+        .filter_map(|item| item.trait_item_def_id.map(|trait_item| (trait_item, item.def_id)))
+        .collect()
+}
+
 /// If the given `DefId` describes an item belonging to a trait,
 /// returns the `DefId` of the trait that the trait item belongs to;
 /// otherwise, returns `None`.
diff --git a/compiler/rustc_ty_utils/src/instance.rs b/compiler/rustc_ty_utils/src/instance.rs
index 13ffb2a5adc..e0aea786b83 100644
--- a/compiler/rustc_ty_utils/src/instance.rs
+++ b/compiler/rustc_ty_utils/src/instance.rs
@@ -152,8 +152,7 @@ fn inner_resolve_instance<'tcx>(
 
     let result = if let Some(trait_def_id) = tcx.trait_of_item(def.did) {
         debug!(" => associated item, attempting to find impl in param_env {:#?}", param_env);
-        let item = tcx.associated_item(def.did);
-        resolve_associated_item(tcx, &item, param_env, trait_def_id, substs)
+        resolve_associated_item(tcx, def.did, param_env, trait_def_id, substs)
     } else {
         let ty = tcx.type_of(def.def_id_for_type_of());
         let item_type = tcx.subst_and_normalize_erasing_regions(substs, param_env, ty);
@@ -204,19 +203,12 @@ fn inner_resolve_instance<'tcx>(
 
 fn resolve_associated_item<'tcx>(
     tcx: TyCtxt<'tcx>,
-    trait_item: &ty::AssocItem,
+    trait_item_id: DefId,
     param_env: ty::ParamEnv<'tcx>,
     trait_id: DefId,
     rcvr_substs: SubstsRef<'tcx>,
 ) -> Result<Option<Instance<'tcx>>, ErrorReported> {
-    let def_id = trait_item.def_id;
-    debug!(
-        "resolve_associated_item(trait_item={:?}, \
-            param_env={:?}, \
-            trait_id={:?}, \
-            rcvr_substs={:?})",
-        def_id, param_env, trait_id, rcvr_substs
-    );
+    debug!(?trait_item_id, ?param_env, ?trait_id, ?rcvr_substs, "resolve_associated_item");
 
     let trait_ref = ty::TraitRef::from_method(tcx, trait_id, rcvr_substs);
 
@@ -232,7 +224,7 @@ fn resolve_associated_item<'tcx>(
         traits::ImplSource::UserDefined(impl_data) => {
             debug!(
                 "resolving ImplSource::UserDefined: {:?}, {:?}, {:?}, {:?}",
-                param_env, trait_item, rcvr_substs, impl_data
+                param_env, trait_item_id, rcvr_substs, impl_data
             );
             assert!(!rcvr_substs.needs_infer());
             assert!(!trait_ref.needs_infer());
@@ -241,9 +233,9 @@ fn resolve_associated_item<'tcx>(
             let trait_def = tcx.trait_def(trait_def_id);
             let leaf_def = trait_def
                 .ancestors(tcx, impl_data.impl_def_id)?
-                .leaf_def(tcx, trait_item.ident, trait_item.kind)
+                .leaf_def(tcx, trait_item_id)
                 .unwrap_or_else(|| {
-                    bug!("{:?} not found in {:?}", trait_item, impl_data.impl_def_id);
+                    bug!("{:?} not found in {:?}", trait_item_id, impl_data.impl_def_id);
                 });
 
             let substs = tcx.infer_ctxt().enter(|infcx| {
@@ -297,22 +289,22 @@ fn resolve_associated_item<'tcx>(
             // performs (i.e. that the definition's type in the `impl` matches
             // the declaration in the `trait`), so that we can cheaply check
             // here if it failed, instead of approximating it.
-            if trait_item.kind == ty::AssocKind::Const
-                && trait_item.def_id != leaf_def.item.def_id
+            if leaf_def.item.kind == ty::AssocKind::Const
+                && trait_item_id != leaf_def.item.def_id
                 && leaf_def.item.def_id.is_local()
             {
                 let normalized_type_of = |def_id, substs| {
                     tcx.subst_and_normalize_erasing_regions(substs, param_env, tcx.type_of(def_id))
                 };
 
-                let original_ty = normalized_type_of(trait_item.def_id, rcvr_substs);
+                let original_ty = normalized_type_of(trait_item_id, rcvr_substs);
                 let resolved_ty = normalized_type_of(leaf_def.item.def_id, substs);
 
                 if original_ty != resolved_ty {
                     let msg = format!(
                         "Instance::resolve: inconsistent associated `const` type: \
                          was `{}: {}` but resolved to `{}: {}`",
-                        tcx.def_path_str_with_substs(trait_item.def_id, rcvr_substs),
+                        tcx.def_path_str_with_substs(trait_item_id, rcvr_substs),
                         original_ty,
                         tcx.def_path_str_with_substs(leaf_def.item.def_id, substs),
                         resolved_ty,
@@ -343,19 +335,22 @@ fn resolve_associated_item<'tcx>(
         }
         traits::ImplSource::FnPointer(ref data) => match data.fn_ty.kind() {
             ty::FnDef(..) | ty::FnPtr(..) => Some(Instance {
-                def: ty::InstanceDef::FnPtrShim(trait_item.def_id, data.fn_ty),
+                def: ty::InstanceDef::FnPtrShim(trait_item_id, data.fn_ty),
                 substs: rcvr_substs,
             }),
             _ => None,
         },
         traits::ImplSource::Object(ref data) => {
-            let index = traits::get_vtable_index_of_object_method(tcx, data, def_id);
-            Some(Instance { def: ty::InstanceDef::Virtual(def_id, index), substs: rcvr_substs })
+            let index = traits::get_vtable_index_of_object_method(tcx, data, trait_item_id);
+            Some(Instance {
+                def: ty::InstanceDef::Virtual(trait_item_id, index),
+                substs: rcvr_substs,
+            })
         }
         traits::ImplSource::Builtin(..) => {
             if Some(trait_ref.def_id) == tcx.lang_items().clone_trait() {
                 // FIXME(eddyb) use lang items for methods instead of names.
-                let name = tcx.item_name(def_id);
+                let name = tcx.item_name(trait_item_id);
                 if name == sym::clone {
                     let self_ty = trait_ref.self_ty();
 
@@ -367,7 +362,7 @@ fn resolve_associated_item<'tcx>(
                     };
 
                     Some(Instance {
-                        def: ty::InstanceDef::CloneShim(def_id, self_ty),
+                        def: ty::InstanceDef::CloneShim(trait_item_id, self_ty),
                         substs: rcvr_substs,
                     })
                 } else {
@@ -375,7 +370,7 @@ fn resolve_associated_item<'tcx>(
 
                     // Use the default `fn clone_from` from `trait Clone`.
                     let substs = tcx.erase_regions(rcvr_substs);
-                    Some(ty::Instance::new(def_id, substs))
+                    Some(ty::Instance::new(trait_item_id, substs))
                 }
             } else {
                 None