Auto merge of #90639 - matthewjasper:leaf-def-cache, r=cjgillot

Add a query for resolving an impl item from the trait item

This makes finding the item in an impl that implements a given trait item a query. This is for a few reasons:

- To slightly improve performance
- To avoid having to do name resolution during monomorphisation
- To make it easier to implement potential future features that create anonymous associated items

25 files changed, 483 insertions, 448 deletions

diff --git a/compiler/rustc_metadata/src/rmeta/decoder.rs b/compiler/rustc_metadata/src/rmeta/decoder.rs
index bb9a58a0b62..5c275279579 100644
--- a/compiler/rustc_metadata/src/rmeta/decoder.rs
+++ b/compiler/rustc_metadata/src/rmeta/decoder.rs
@@ -1008,6 +1008,10 @@ impl<'a, 'tcx> CrateMetadataRef<'a> {
         self.get_impl_data(id).constness
     }
 
+    fn get_trait_item_def_id(&self, id: DefIndex) -> Option<DefId> {
+        self.root.tables.trait_item_def_id.get(self, id).map(|d| d.decode(self))
+    }
+
     fn get_coerce_unsized_info(&self, id: DefIndex) -> Option<ty::adjustment::CoerceUnsizedInfo> {
         self.get_impl_data(id).coerce_unsized_info
     }
@@ -1258,6 +1262,16 @@ impl<'a, 'tcx> CrateMetadataRef<'a> {
         }
     }
 
+    fn get_associated_item_def_ids(&self, tcx: TyCtxt<'tcx>, id: DefIndex) -> &'tcx [DefId] {
+        if let Some(children) = self.root.tables.children.get(self, id) {
+            tcx.arena.alloc_from_iter(
+                children.decode((self, tcx.sess)).map(|child_index| self.local_def_id(child_index)),
+            )
+        } else {
+            &[]
+        }
+    }
+
     fn get_associated_item(&self, id: DefIndex, sess: &Session) -> ty::AssocItem {
         let def_key = self.def_key(id);
         let parent = self.local_def_id(def_key.parent.unwrap());
@@ -1279,6 +1293,7 @@ impl<'a, 'tcx> CrateMetadataRef<'a> {
             vis: self.get_visibility(id),
             defaultness: container.defaultness(),
             def_id: self.local_def_id(id),
+            trait_item_def_id: self.get_trait_item_def_id(id),
             container: container.with_def_id(parent),
             fn_has_self_parameter: has_self,
         }
diff --git a/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs b/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs
index aac0aa61ea6..804f277e26e 100644
--- a/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs
+++ b/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs
@@ -103,12 +103,7 @@ provide! { <'tcx> tcx, def_id, other, cdata,
         tcx.calculate_dtor(def_id, |_,_| Ok(()))
     }
     variances_of => { tcx.arena.alloc_from_iter(cdata.get_item_variances(def_id.index)) }
-    associated_item_def_ids => {
-        let mut result = SmallVec::<[_; 8]>::new();
-        cdata.each_child_of_item(def_id.index,
-          |child| result.push(child.res.def_id()), tcx.sess);
-        tcx.arena.alloc_slice(&result)
-    }
+    associated_item_def_ids => { cdata.get_associated_item_def_ids(tcx, def_id.index) }
     associated_item => { cdata.get_associated_item(def_id.index, tcx.sess) }
     impl_trait_ref => { cdata.get_impl_trait(def_id.index, tcx) }
     impl_polarity => { cdata.get_impl_polarity(def_id.index) }
diff --git a/compiler/rustc_metadata/src/rmeta/encoder.rs b/compiler/rustc_metadata/src/rmeta/encoder.rs
index 12d66f4fc45..11a986f0a7c 100644
--- a/compiler/rustc_metadata/src/rmeta/encoder.rs
+++ b/compiler/rustc_metadata/src/rmeta/encoder.rs
@@ -1294,6 +1294,9 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
         }
         self.encode_ident_span(def_id, impl_item.ident);
         self.encode_item_type(def_id);
+        if let Some(trait_item_def_id) = impl_item.trait_item_def_id {
+            record!(self.tables.trait_item_def_id[def_id] <- trait_item_def_id);
+        }
         if impl_item.kind == ty::AssocKind::Fn {
             record!(self.tables.fn_sig[def_id] <- tcx.fn_sig(def_id));
         }
diff --git a/compiler/rustc_metadata/src/rmeta/mod.rs b/compiler/rustc_metadata/src/rmeta/mod.rs
index 4076e0b9e0f..fa44cbc2d55 100644
--- a/compiler/rustc_metadata/src/rmeta/mod.rs
+++ b/compiler/rustc_metadata/src/rmeta/mod.rs
@@ -302,6 +302,7 @@ define_tables! {
     ty: Table<DefIndex, Lazy!(Ty<'tcx>)>,
     fn_sig: Table<DefIndex, Lazy!(ty::PolyFnSig<'tcx>)>,
     impl_trait_ref: Table<DefIndex, Lazy!(ty::TraitRef<'tcx>)>,
+    trait_item_def_id: Table<DefIndex, Lazy<DefId>>,
     inherent_impls: Table<DefIndex, Lazy<[DefIndex]>>,
     variances: Table<DefIndex, Lazy<[ty::Variance]>>,
     generics: Table<DefIndex, Lazy<ty::Generics>>,
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_middle/src/ty/assoc.rs b/compiler/rustc_middle/src/ty/assoc.rs
index bf5a3e68250..5af4eef40d4 100644
--- a/compiler/rustc_middle/src/ty/assoc.rs
+++ b/compiler/rustc_middle/src/ty/assoc.rs
@@ -40,6 +40,7 @@ impl AssocItemContainer {
     }
 }
 
+/// Information about an associated item
 #[derive(Copy, Clone, Debug, PartialEq, HashStable, Eq, Hash)]
 pub struct AssocItem {
     pub def_id: DefId,
@@ -50,6 +51,10 @@ pub struct AssocItem {
     pub defaultness: hir::Defaultness,
     pub container: AssocItemContainer,
 
+    /// If this is an item in an impl of a trait then this is the `DefId` of
+    /// the associated item on the trait that this implements.
+    pub trait_item_def_id: Option<DefId>,
+
     /// Whether this is a method with an explicit self
     /// as its first parameter, allowing method calls.
     pub fn_has_self_parameter: bool,
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_passes/src/stability.rs b/compiler/rustc_passes/src/stability.rs
index 5f19991f9c7..c136411df27 100644
--- a/compiler/rustc_passes/src/stability.rs
+++ b/compiler/rustc_passes/src/stability.rs
@@ -794,19 +794,12 @@ impl<'tcx> Visitor<'tcx> for Checker<'tcx> {
                     }
                 }
 
-                if let Res::Def(DefKind::Trait, trait_did) = t.path.res {
-                    for impl_item_ref in items {
-                        let impl_item = self.tcx.hir().impl_item(impl_item_ref.id);
-                        let trait_item_def_id = self
-                            .tcx
-                            .associated_items(trait_did)
-                            .filter_by_name_unhygienic(impl_item.ident.name)
-                            .next()
-                            .map(|item| item.def_id);
-                        if let Some(def_id) = trait_item_def_id {
-                            // Pass `None` to skip deprecation warnings.
-                            self.tcx.check_stability(def_id, None, impl_item.span, None);
-                        }
+                for impl_item_ref in items {
+                    let impl_item = self.tcx.associated_item(impl_item_ref.id.def_id);
+
+                    if let Some(def_id) = impl_item.trait_item_def_id {
+                        // Pass `None` to skip deprecation warnings.
+                        self.tcx.check_stability(def_id, None, impl_item_ref.span, None);
                     }
                 }
             }
diff --git a/compiler/rustc_save_analysis/src/lib.rs b/compiler/rustc_save_analysis/src/lib.rs
index 7ec619e07ff..a83f0230814 100644
--- a/compiler/rustc_save_analysis/src/lib.rs
+++ b/compiler/rustc_save_analysis/src/lib.rs
@@ -710,13 +710,11 @@ impl<'tcx> SaveContext<'tcx> {
             }
             Res::Def(HirDefKind::AssocFn, decl_id) => {
                 let def_id = if decl_id.is_local() {
-                    let ti = self.tcx.associated_item(decl_id);
-
-                    self.tcx
-                        .associated_items(ti.container.id())
-                        .filter_by_name_unhygienic(ti.ident.name)
-                        .find(|item| item.defaultness.has_value())
-                        .map(|item| item.def_id)
+                    if self.tcx.associated_item(decl_id).defaultness.has_value() {
+                        Some(decl_id)
+                    } else {
+                        None
+                    }
                 } else {
                     None
                 };
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_traits/src/chalk/db.rs b/compiler/rustc_traits/src/chalk/db.rs
index c38680651af..3f51442277f 100644
--- a/compiler/rustc_traits/src/chalk/db.rs
+++ b/compiler/rustc_traits/src/chalk/db.rs
@@ -436,23 +436,13 @@ impl<'tcx> chalk_solve::RustIrDatabase<RustInterner<'tcx>> for RustIrDatabase<'t
     ) -> Arc<chalk_solve::rust_ir::AssociatedTyValue<RustInterner<'tcx>>> {
         let def_id = associated_ty_id.0;
         let assoc_item = self.interner.tcx.associated_item(def_id);
-        let (impl_id, trait_id) = match assoc_item.container {
-            AssocItemContainer::TraitContainer(def_id) => (def_id, def_id),
-            AssocItemContainer::ImplContainer(def_id) => {
-                (def_id, self.interner.tcx.impl_trait_ref(def_id).unwrap().def_id)
-            }
-        };
+        let impl_id = assoc_item.container.id();
         match assoc_item.kind {
             AssocKind::Type => {}
             _ => unimplemented!("Not possible??"),
         }
 
-        let trait_item = self
-            .interner
-            .tcx
-            .associated_items(trait_id)
-            .find_by_name_and_kind(self.interner.tcx, assoc_item.ident, assoc_item.kind, trait_id)
-            .unwrap();
+        let trait_item_id = assoc_item.trait_item_def_id.expect("assoc_ty with no trait version");
         let bound_vars = bound_vars_for_item(self.interner.tcx, def_id);
         let binders = binders_for(self.interner, bound_vars);
         let ty = self
@@ -464,7 +454,7 @@ impl<'tcx> chalk_solve::RustIrDatabase<RustInterner<'tcx>> for RustIrDatabase<'t
 
         Arc::new(chalk_solve::rust_ir::AssociatedTyValue {
             impl_id: chalk_ir::ImplId(impl_id),
-            associated_ty_id: chalk_ir::AssocTypeId(trait_item.def_id),
+            associated_ty_id: chalk_ir::AssocTypeId(trait_item_id),
             value: chalk_ir::Binders::new(
                 binders,
                 chalk_solve::rust_ir::AssociatedTyValueBound { ty },
diff --git a/compiler/rustc_ty_utils/src/assoc.rs b/compiler/rustc_ty_utils/src/assoc.rs
new file mode 100644
index 00000000000..b1d47f6c29a
--- /dev/null
+++ b/compiler/rustc_ty_utils/src/assoc.rs
@@ -0,0 +1,239 @@
+use rustc_data_structures::fx::FxHashMap;
+use rustc_errors::struct_span_err;
+use rustc_hir as hir;
+use rustc_hir::def_id::{DefId, LocalDefId};
+use rustc_middle::ty::{self, TyCtxt, TypeFoldable};
+
+pub fn provide(providers: &mut ty::query::Providers) {
+    *providers = ty::query::Providers {
+        associated_item,
+        associated_item_def_ids,
+        associated_items,
+        impl_item_implementor_ids,
+        trait_of_item,
+        ..*providers
+    };
+}
+
+fn associated_item_def_ids(tcx: TyCtxt<'_>, def_id: DefId) -> &[DefId] {
+    let item = tcx.hir().expect_item(def_id.expect_local());
+    match item.kind {
+        hir::ItemKind::Trait(.., ref trait_item_refs) => tcx.arena.alloc_from_iter(
+            trait_item_refs.iter().map(|trait_item_ref| trait_item_ref.id.def_id.to_def_id()),
+        ),
+        hir::ItemKind::Impl(ref impl_) => tcx.arena.alloc_from_iter(
+            impl_.items.iter().map(|impl_item_ref| impl_item_ref.id.def_id.to_def_id()),
+        ),
+        hir::ItemKind::TraitAlias(..) => &[],
+        _ => span_bug!(item.span, "associated_item_def_ids: not impl or trait"),
+    }
+}
+
+fn associated_items(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AssocItems<'_> {
+    let items = tcx.associated_item_def_ids(def_id).iter().map(|did| tcx.associated_item(*did));
+    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`.
+fn trait_of_item(tcx: TyCtxt<'_>, def_id: DefId) -> Option<DefId> {
+    tcx.opt_associated_item(def_id).and_then(|associated_item| match associated_item.container {
+        ty::TraitContainer(def_id) => Some(def_id),
+        ty::ImplContainer(_) => None,
+    })
+}
+
+fn associated_item(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AssocItem {
+    let id = tcx.hir().local_def_id_to_hir_id(def_id.expect_local());
+    let parent_id = tcx.hir().get_parent_item(id);
+    let parent_def_id = tcx.hir().local_def_id(parent_id);
+    let parent_item = tcx.hir().expect_item(parent_def_id);
+    match parent_item.kind {
+        hir::ItemKind::Impl(ref impl_) => {
+            if let Some(impl_item_ref) =
+                impl_.items.iter().find(|i| i.id.def_id.to_def_id() == def_id)
+            {
+                let assoc_item =
+                    associated_item_from_impl_item_ref(tcx, parent_def_id, impl_item_ref);
+                debug_assert_eq!(assoc_item.def_id, def_id);
+                return assoc_item;
+            }
+        }
+
+        hir::ItemKind::Trait(.., ref trait_item_refs) => {
+            if let Some(trait_item_ref) =
+                trait_item_refs.iter().find(|i| i.id.def_id.to_def_id() == def_id)
+            {
+                let assoc_item =
+                    associated_item_from_trait_item_ref(tcx, parent_def_id, trait_item_ref);
+                debug_assert_eq!(assoc_item.def_id, def_id);
+                return assoc_item;
+            }
+        }
+
+        _ => {}
+    }
+
+    span_bug!(
+        parent_item.span,
+        "unexpected parent of trait or impl item or item not found: {:?}",
+        parent_item.kind
+    )
+}
+
+fn associated_item_from_trait_item_ref(
+    tcx: TyCtxt<'_>,
+    parent_def_id: LocalDefId,
+    trait_item_ref: &hir::TraitItemRef,
+) -> ty::AssocItem {
+    let def_id = trait_item_ref.id.def_id;
+    let (kind, has_self) = match trait_item_ref.kind {
+        hir::AssocItemKind::Const => (ty::AssocKind::Const, false),
+        hir::AssocItemKind::Fn { has_self } => (ty::AssocKind::Fn, has_self),
+        hir::AssocItemKind::Type => (ty::AssocKind::Type, false),
+    };
+
+    ty::AssocItem {
+        ident: trait_item_ref.ident,
+        kind,
+        vis: tcx.visibility(def_id),
+        defaultness: trait_item_ref.defaultness,
+        def_id: def_id.to_def_id(),
+        trait_item_def_id: Some(def_id.to_def_id()),
+        container: ty::TraitContainer(parent_def_id.to_def_id()),
+        fn_has_self_parameter: has_self,
+    }
+}
+
+fn associated_item_from_impl_item_ref(
+    tcx: TyCtxt<'_>,
+    parent_def_id: LocalDefId,
+    impl_item_ref: &hir::ImplItemRef,
+) -> ty::AssocItem {
+    let def_id = impl_item_ref.id.def_id;
+    let (kind, has_self) = match impl_item_ref.kind {
+        hir::AssocItemKind::Const => (ty::AssocKind::Const, false),
+        hir::AssocItemKind::Fn { has_self } => (ty::AssocKind::Fn, has_self),
+        hir::AssocItemKind::Type => (ty::AssocKind::Type, false),
+    };
+
+    let trait_item_def_id = impl_item_base_id(tcx, parent_def_id, impl_item_ref);
+
+    ty::AssocItem {
+        ident: impl_item_ref.ident,
+        kind,
+        vis: tcx.visibility(def_id),
+        defaultness: impl_item_ref.defaultness,
+        def_id: def_id.to_def_id(),
+        trait_item_def_id,
+        container: ty::ImplContainer(parent_def_id.to_def_id()),
+        fn_has_self_parameter: has_self,
+    }
+}
+
+fn impl_item_base_id<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    parent_def_id: LocalDefId,
+    impl_item: &hir::ImplItemRef,
+) -> Option<DefId> {
+    let impl_trait_ref = tcx.impl_trait_ref(parent_def_id)?;
+
+    // If the trait reference itself is erroneous (so the compilation is going
+    // to fail), skip checking the items here -- the `impl_item` table in `tcx`
+    // isn't populated for such impls.
+    if impl_trait_ref.references_error() {
+        return None;
+    }
+
+    // Locate trait items
+    let associated_items = tcx.associated_items(impl_trait_ref.def_id);
+
+    // Match item against trait
+    let mut items = associated_items.filter_by_name(tcx, impl_item.ident, impl_trait_ref.def_id);
+
+    let mut trait_item = items.next()?;
+
+    let is_compatible = |ty: &&ty::AssocItem| match (ty.kind, &impl_item.kind) {
+        (ty::AssocKind::Const, hir::AssocItemKind::Const) => true,
+        (ty::AssocKind::Fn, hir::AssocItemKind::Fn { .. }) => true,
+        (ty::AssocKind::Type, hir::AssocItemKind::Type) => true,
+        _ => false,
+    };
+
+    // If we don't have a compatible item, we'll use the first one whose name matches
+    // to report an error.
+    let mut compatible_kind = is_compatible(&trait_item);
+
+    if !compatible_kind {
+        if let Some(ty_trait_item) = items.find(is_compatible) {
+            compatible_kind = true;
+            trait_item = ty_trait_item;
+        }
+    }
+
+    if compatible_kind {
+        Some(trait_item.def_id)
+    } else {
+        report_mismatch_error(tcx, trait_item.def_id, impl_trait_ref, impl_item);
+        None
+    }
+}
+
+#[inline(never)]
+#[cold]
+fn report_mismatch_error<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    trait_item_def_id: DefId,
+    impl_trait_ref: ty::TraitRef<'tcx>,
+    impl_item: &hir::ImplItemRef,
+) {
+    let mut err = match impl_item.kind {
+        hir::AssocItemKind::Const => {
+            // Find associated const definition.
+            struct_span_err!(
+                tcx.sess,
+                impl_item.span,
+                E0323,
+                "item `{}` is an associated const, which doesn't match its trait `{}`",
+                impl_item.ident,
+                impl_trait_ref.print_only_trait_path()
+            )
+        }
+
+        hir::AssocItemKind::Fn { .. } => {
+            struct_span_err!(
+                tcx.sess,
+                impl_item.span,
+                E0324,
+                "item `{}` is an associated method, which doesn't match its trait `{}`",
+                impl_item.ident,
+                impl_trait_ref.print_only_trait_path()
+            )
+        }
+
+        hir::AssocItemKind::Type => {
+            struct_span_err!(
+                tcx.sess,
+                impl_item.span,
+                E0325,
+                "item `{}` is an associated type, which doesn't match its trait `{}`",
+                impl_item.ident,
+                impl_trait_ref.print_only_trait_path()
+            )
+        }
+    };
+
+    err.span_label(impl_item.span, "does not match trait");
+    if let Some(trait_span) = tcx.hir().span_if_local(trait_item_def_id) {
+        err.span_label(trait_span, "item in trait");
+    }
+    err.emit();
+}
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
diff --git a/compiler/rustc_ty_utils/src/lib.rs b/compiler/rustc_ty_utils/src/lib.rs
index 60f8e196bcb..55e19990761 100644
--- a/compiler/rustc_ty_utils/src/lib.rs
+++ b/compiler/rustc_ty_utils/src/lib.rs
@@ -16,6 +16,7 @@ extern crate tracing;
 
 use rustc_middle::ty::query::Providers;
 
+mod assoc;
 mod common_traits;
 pub mod instance;
 mod needs_drop;
@@ -23,6 +24,7 @@ pub mod representability;
 mod ty;
 
 pub fn provide(providers: &mut Providers) {
+    assoc::provide(providers);
     common_traits::provide(providers);
     needs_drop::provide(providers);
     ty::provide(providers);
diff --git a/compiler/rustc_ty_utils/src/ty.rs b/compiler/rustc_ty_utils/src/ty.rs
index 6c2657bd64b..8f50e3e0fe1 100644
--- a/compiler/rustc_ty_utils/src/ty.rs
+++ b/compiler/rustc_ty_utils/src/ty.rs
@@ -1,6 +1,6 @@
 use rustc_data_structures::fx::FxIndexSet;
 use rustc_hir as hir;
-use rustc_hir::def_id::{DefId, LocalDefId};
+use rustc_hir::def_id::DefId;
 use rustc_middle::ty::subst::Subst;
 use rustc_middle::ty::{self, Binder, Predicate, PredicateKind, ToPredicate, Ty, TyCtxt};
 use rustc_span::{sym, Span};
@@ -71,90 +71,6 @@ fn sized_constraint_for_ty<'tcx>(
     result
 }
 
-fn associated_item_from_trait_item_ref(
-    tcx: TyCtxt<'_>,
-    parent_def_id: LocalDefId,
-    trait_item_ref: &hir::TraitItemRef,
-) -> ty::AssocItem {
-    let def_id = trait_item_ref.id.def_id;
-    let (kind, has_self) = match trait_item_ref.kind {
-        hir::AssocItemKind::Const => (ty::AssocKind::Const, false),
-        hir::AssocItemKind::Fn { has_self } => (ty::AssocKind::Fn, has_self),
-        hir::AssocItemKind::Type => (ty::AssocKind::Type, false),
-    };
-
-    ty::AssocItem {
-        ident: trait_item_ref.ident,
-        kind,
-        vis: tcx.visibility(def_id),
-        defaultness: trait_item_ref.defaultness,
-        def_id: def_id.to_def_id(),
-        container: ty::TraitContainer(parent_def_id.to_def_id()),
-        fn_has_self_parameter: has_self,
-    }
-}
-
-fn associated_item_from_impl_item_ref(
-    tcx: TyCtxt<'_>,
-    parent_def_id: LocalDefId,
-    impl_item_ref: &hir::ImplItemRef,
-) -> ty::AssocItem {
-    let def_id = impl_item_ref.id.def_id;
-    let (kind, has_self) = match impl_item_ref.kind {
-        hir::AssocItemKind::Const => (ty::AssocKind::Const, false),
-        hir::AssocItemKind::Fn { has_self } => (ty::AssocKind::Fn, has_self),
-        hir::AssocItemKind::Type => (ty::AssocKind::Type, false),
-    };
-
-    ty::AssocItem {
-        ident: impl_item_ref.ident,
-        kind,
-        vis: tcx.visibility(def_id),
-        defaultness: impl_item_ref.defaultness,
-        def_id: def_id.to_def_id(),
-        container: ty::ImplContainer(parent_def_id.to_def_id()),
-        fn_has_self_parameter: has_self,
-    }
-}
-
-fn associated_item(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AssocItem {
-    let id = tcx.hir().local_def_id_to_hir_id(def_id.expect_local());
-    let parent_id = tcx.hir().get_parent_item(id);
-    let parent_def_id = tcx.hir().local_def_id(parent_id);
-    let parent_item = tcx.hir().expect_item(parent_def_id);
-    match parent_item.kind {
-        hir::ItemKind::Impl(ref impl_) => {
-            if let Some(impl_item_ref) =
-                impl_.items.iter().find(|i| i.id.def_id.to_def_id() == def_id)
-            {
-                let assoc_item =
-                    associated_item_from_impl_item_ref(tcx, parent_def_id, impl_item_ref);
-                debug_assert_eq!(assoc_item.def_id, def_id);
-                return assoc_item;
-            }
-        }
-
-        hir::ItemKind::Trait(.., ref trait_item_refs) => {
-            if let Some(trait_item_ref) =
-                trait_item_refs.iter().find(|i| i.id.def_id.to_def_id() == def_id)
-            {
-                let assoc_item =
-                    associated_item_from_trait_item_ref(tcx, parent_def_id, trait_item_ref);
-                debug_assert_eq!(assoc_item.def_id, def_id);
-                return assoc_item;
-            }
-        }
-
-        _ => {}
-    }
-
-    span_bug!(
-        parent_item.span,
-        "unexpected parent of trait or impl item or item not found: {:?}",
-        parent_item.kind
-    )
-}
-
 fn impl_defaultness(tcx: TyCtxt<'_>, def_id: DefId) -> hir::Defaultness {
     let item = tcx.hir().expect_item(def_id.expect_local());
     if let hir::ItemKind::Impl(impl_) = &item.kind {
@@ -197,25 +113,6 @@ fn adt_sized_constraint(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AdtSizedConstrain
     ty::AdtSizedConstraint(result)
 }
 
-fn associated_item_def_ids(tcx: TyCtxt<'_>, def_id: DefId) -> &[DefId] {
-    let item = tcx.hir().expect_item(def_id.expect_local());
-    match item.kind {
-        hir::ItemKind::Trait(.., ref trait_item_refs) => tcx.arena.alloc_from_iter(
-            trait_item_refs.iter().map(|trait_item_ref| trait_item_ref.id.def_id.to_def_id()),
-        ),
-        hir::ItemKind::Impl(ref impl_) => tcx.arena.alloc_from_iter(
-            impl_.items.iter().map(|impl_item_ref| impl_item_ref.id.def_id.to_def_id()),
-        ),
-        hir::ItemKind::TraitAlias(..) => &[],
-        _ => span_bug!(item.span, "associated_item_def_ids: not impl or trait"),
-    }
-}
-
-fn associated_items(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AssocItems<'_> {
-    let items = tcx.associated_item_def_ids(def_id).iter().map(|did| tcx.associated_item(*did));
-    ty::AssocItems::new(items)
-}
-
 fn def_ident_span(tcx: TyCtxt<'_>, def_id: DefId) -> Option<Span> {
     tcx.hir()
         .get_if_local(def_id)
@@ -231,16 +128,6 @@ fn def_ident_span(tcx: TyCtxt<'_>, def_id: DefId) -> Option<Span> {
         .map(|ident| ident.span)
 }
 
-/// 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`.
-fn trait_of_item(tcx: TyCtxt<'_>, def_id: DefId) -> Option<DefId> {
-    tcx.opt_associated_item(def_id).and_then(|associated_item| match associated_item.container {
-        ty::TraitContainer(def_id) => Some(def_id),
-        ty::ImplContainer(_) => None,
-    })
-}
-
 /// See `ParamEnv` struct definition for details.
 #[instrument(level = "debug", skip(tcx))]
 fn param_env(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ParamEnv<'_> {
@@ -620,14 +507,10 @@ pub fn conservative_is_privately_uninhabited_raw<'tcx>(
 pub fn provide(providers: &mut ty::query::Providers) {
     *providers = ty::query::Providers {
         asyncness,
-        associated_item,
-        associated_item_def_ids,
-        associated_items,
         adt_sized_constraint,
         def_ident_span,
         param_env,
         param_env_reveal_all_normalized,
-        trait_of_item,
         instance_def_size_estimate,
         issue33140_self_ty,
         impl_defaultness,
diff --git a/compiler/rustc_typeck/src/check/check.rs b/compiler/rustc_typeck/src/check/check.rs
index fd7b3a55dfb..dcf42e1aefe 100644
--- a/compiler/rustc_typeck/src/check/check.rs
+++ b/compiler/rustc_typeck/src/check/check.rs
@@ -841,14 +841,8 @@ pub(super) fn check_specialization_validity<'tcx>(
     trait_def: &ty::TraitDef,
     trait_item: &ty::AssocItem,
     impl_id: DefId,
-    impl_item: &hir::ImplItem<'_>,
+    impl_item: &hir::ImplItemRef,
 ) {
-    let kind = match impl_item.kind {
-        hir::ImplItemKind::Const(..) => ty::AssocKind::Const,
-        hir::ImplItemKind::Fn(..) => ty::AssocKind::Fn,
-        hir::ImplItemKind::TyAlias(_) => ty::AssocKind::Type,
-    };
-
     let ancestors = match trait_def.ancestors(tcx, impl_id) {
         Ok(ancestors) => ancestors,
         Err(_) => return,
@@ -857,7 +851,7 @@ pub(super) fn check_specialization_validity<'tcx>(
         if parent.is_from_trait() {
             None
         } else {
-            Some((parent, parent.item(tcx, trait_item.ident, kind, trait_def.def_id)))
+            Some((parent, parent.item(tcx, trait_item.def_id)))
         }
     });
 
@@ -894,7 +888,7 @@ pub(super) fn check_specialization_validity<'tcx>(
     }
 }
 
-pub(super) fn check_impl_items_against_trait<'tcx>(
+fn check_impl_items_against_trait<'tcx>(
     tcx: TyCtxt<'tcx>,
     full_impl_span: Span,
     impl_id: LocalDefId,
@@ -926,174 +920,82 @@ pub(super) fn check_impl_items_against_trait<'tcx>(
         }
     }
 
-    // Locate trait definition and items
     let trait_def = tcx.trait_def(impl_trait_ref.def_id);
-    let impl_items = impl_item_refs.iter().map(|iiref| tcx.hir().impl_item(iiref.id));
-    let associated_items = tcx.associated_items(impl_trait_ref.def_id);
-
-    // Check existing impl methods to see if they are both present in trait
-    // and compatible with trait signature
-    for impl_item in impl_items {
-        let ty_impl_item = tcx.associated_item(impl_item.def_id);
-
-        let mut items =
-            associated_items.filter_by_name(tcx, ty_impl_item.ident, impl_trait_ref.def_id);
-
-        let (compatible_kind, ty_trait_item) = if let Some(ty_trait_item) = items.next() {
-            let is_compatible = |ty: &&ty::AssocItem| match (ty.kind, &impl_item.kind) {
-                (ty::AssocKind::Const, hir::ImplItemKind::Const(..)) => true,
-                (ty::AssocKind::Fn, hir::ImplItemKind::Fn(..)) => true,
-                (ty::AssocKind::Type, hir::ImplItemKind::TyAlias(..)) => true,
-                _ => false,
-            };
-
-            // If we don't have a compatible item, we'll use the first one whose name matches
-            // to report an error.
-            let mut compatible_kind = is_compatible(&ty_trait_item);
-            let mut trait_item = ty_trait_item;
-
-            if !compatible_kind {
-                if let Some(ty_trait_item) = items.find(is_compatible) {
-                    compatible_kind = true;
-                    trait_item = ty_trait_item;
-                }
-            }
 
-            (compatible_kind, trait_item)
+    for impl_item in impl_item_refs {
+        let ty_impl_item = tcx.associated_item(impl_item.id.def_id);
+        let ty_trait_item = if let Some(trait_item_id) = ty_impl_item.trait_item_def_id {
+            tcx.associated_item(trait_item_id)
         } else {
+            // Checked in `associated_item`.
+            tcx.sess.delay_span_bug(impl_item.span, "missing associated item in trait");
             continue;
         };
-
-        if compatible_kind {
-            match impl_item.kind {
-                hir::ImplItemKind::Const(..) => {
-                    // Find associated const definition.
-                    compare_const_impl(
-                        tcx,
-                        &ty_impl_item,
-                        impl_item.span,
-                        &ty_trait_item,
-                        impl_trait_ref,
-                    );
-                }
-                hir::ImplItemKind::Fn(..) => {
-                    let opt_trait_span = tcx.hir().span_if_local(ty_trait_item.def_id);
-                    compare_impl_method(
-                        tcx,
-                        &ty_impl_item,
-                        impl_item.span,
-                        &ty_trait_item,
-                        impl_trait_ref,
-                        opt_trait_span,
-                    );
-                }
-                hir::ImplItemKind::TyAlias(impl_ty) => {
-                    let opt_trait_span = tcx.hir().span_if_local(ty_trait_item.def_id);
-                    compare_ty_impl(
-                        tcx,
-                        &ty_impl_item,
-                        impl_ty.span,
-                        &ty_trait_item,
-                        impl_trait_ref,
-                        opt_trait_span,
-                    );
-                }
+        let impl_item_full = tcx.hir().impl_item(impl_item.id);
+        match impl_item_full.kind {
+            hir::ImplItemKind::Const(..) => {
+                // Find associated const definition.
+                compare_const_impl(
+                    tcx,
+                    &ty_impl_item,
+                    impl_item.span,
+                    &ty_trait_item,
+                    impl_trait_ref,
+                );
+            }
+            hir::ImplItemKind::Fn(..) => {
+                let opt_trait_span = tcx.hir().span_if_local(ty_trait_item.def_id);
+                compare_impl_method(
+                    tcx,
+                    &ty_impl_item,
+                    impl_item.span,
+                    &ty_trait_item,
+                    impl_trait_ref,
+                    opt_trait_span,
+                );
+            }
+            hir::ImplItemKind::TyAlias(impl_ty) => {
+                let opt_trait_span = tcx.hir().span_if_local(ty_trait_item.def_id);
+                compare_ty_impl(
+                    tcx,
+                    &ty_impl_item,
+                    impl_ty.span,
+                    &ty_trait_item,
+                    impl_trait_ref,
+                    opt_trait_span,
+                );
             }
-
-            check_specialization_validity(
-                tcx,
-                trait_def,
-                &ty_trait_item,
-                impl_id.to_def_id(),
-                impl_item,
-            );
-        } else {
-            report_mismatch_error(
-                tcx,
-                ty_trait_item.def_id,
-                impl_trait_ref,
-                impl_item,
-                &ty_impl_item,
-            );
         }
+
+        check_specialization_validity(
+            tcx,
+            trait_def,
+            &ty_trait_item,
+            impl_id.to_def_id(),
+            impl_item,
+        );
     }
 
     if let Ok(ancestors) = trait_def.ancestors(tcx, impl_id.to_def_id()) {
-        let impl_span = tcx.sess.source_map().guess_head_span(full_impl_span);
-
         // Check for missing items from trait
         let mut missing_items = Vec::new();
-        for trait_item in tcx.associated_items(impl_trait_ref.def_id).in_definition_order() {
+        for &trait_item_id in tcx.associated_item_def_ids(impl_trait_ref.def_id) {
             let is_implemented = ancestors
-                .leaf_def(tcx, trait_item.ident, trait_item.kind)
-                .map(|node_item| !node_item.defining_node.is_from_trait())
-                .unwrap_or(false);
+                .leaf_def(tcx, trait_item_id)
+                .map_or(false, |node_item| node_item.item.defaultness.has_value());
 
             if !is_implemented && tcx.impl_defaultness(impl_id).is_final() {
-                if !trait_item.defaultness.has_value() {
-                    missing_items.push(*trait_item);
-                }
+                missing_items.push(tcx.associated_item(trait_item_id));
             }
         }
 
         if !missing_items.is_empty() {
+            let impl_span = tcx.sess.source_map().guess_head_span(full_impl_span);
             missing_items_err(tcx, impl_span, &missing_items, full_impl_span);
         }
     }
 }
 
-#[inline(never)]
-#[cold]
-fn report_mismatch_error<'tcx>(
-    tcx: TyCtxt<'tcx>,
-    trait_item_def_id: DefId,
-    impl_trait_ref: ty::TraitRef<'tcx>,
-    impl_item: &hir::ImplItem<'_>,
-    ty_impl_item: &ty::AssocItem,
-) {
-    let mut err = match impl_item.kind {
-        hir::ImplItemKind::Const(..) => {
-            // Find associated const definition.
-            struct_span_err!(
-                tcx.sess,
-                impl_item.span,
-                E0323,
-                "item `{}` is an associated const, which doesn't match its trait `{}`",
-                ty_impl_item.ident,
-                impl_trait_ref.print_only_trait_path()
-            )
-        }
-
-        hir::ImplItemKind::Fn(..) => {
-            struct_span_err!(
-                tcx.sess,
-                impl_item.span,
-                E0324,
-                "item `{}` is an associated method, which doesn't match its trait `{}`",
-                ty_impl_item.ident,
-                impl_trait_ref.print_only_trait_path()
-            )
-        }
-
-        hir::ImplItemKind::TyAlias(_) => {
-            struct_span_err!(
-                tcx.sess,
-                impl_item.span,
-                E0325,
-                "item `{}` is an associated type, which doesn't match its trait `{}`",
-                ty_impl_item.ident,
-                impl_trait_ref.print_only_trait_path()
-            )
-        }
-    };
-
-    err.span_label(impl_item.span, "does not match trait");
-    if let Some(trait_span) = tcx.hir().span_if_local(trait_item_def_id) {
-        err.span_label(trait_span, "item in trait");
-    }
-    err.emit();
-}
-
 /// Checks whether a type can be represented in memory. In particular, it
 /// identifies types that contain themselves without indirection through a
 /// pointer, which would mean their size is unbounded.
diff --git a/compiler/rustc_typeck/src/check/mod.rs b/compiler/rustc_typeck/src/check/mod.rs
index a9e6b1caff0..d576154ff90 100644
--- a/compiler/rustc_typeck/src/check/mod.rs
+++ b/compiler/rustc_typeck/src/check/mod.rs
@@ -566,7 +566,7 @@ fn maybe_check_static_with_link_section(tcx: TyCtxt<'_>, id: LocalDefId, span: S
 
 fn report_forbidden_specialization(
     tcx: TyCtxt<'_>,
-    impl_item: &hir::ImplItem<'_>,
+    impl_item: &hir::ImplItemRef,
     parent_impl: DefId,
 ) {
     let mut err = struct_span_err!(
@@ -598,7 +598,7 @@ fn report_forbidden_specialization(
 fn missing_items_err(
     tcx: TyCtxt<'_>,
     impl_span: Span,
-    missing_items: &[ty::AssocItem],
+    missing_items: &[&ty::AssocItem],
     full_impl_span: Span,
 ) {
     let missing_items_msg = missing_items
diff --git a/compiler/rustc_typeck/src/collect.rs b/compiler/rustc_typeck/src/collect.rs
index 41c8a37a71a..d4d4baa3f71 100644
--- a/compiler/rustc_typeck/src/collect.rs
+++ b/compiler/rustc_typeck/src/collect.rs
@@ -3150,21 +3150,12 @@ fn codegen_fn_attrs(tcx: TyCtxt<'_>, id: DefId) -> CodegenFnAttrs {
 /// applied to the method prototype.
 fn should_inherit_track_caller(tcx: TyCtxt<'_>, def_id: DefId) -> bool {
     if let Some(impl_item) = tcx.opt_associated_item(def_id) {
-        if let ty::AssocItemContainer::ImplContainer(impl_def_id) = impl_item.container {
-            if let Some(trait_def_id) = tcx.trait_id_of_impl(impl_def_id) {
-                if let Some(trait_item) = tcx
-                    .associated_items(trait_def_id)
-                    .filter_by_name_unhygienic(impl_item.ident.name)
-                    .find(move |trait_item| {
-                        trait_item.kind == ty::AssocKind::Fn
-                            && tcx.hygienic_eq(impl_item.ident, trait_item.ident, trait_def_id)
-                    })
-                {
-                    return tcx
-                        .codegen_fn_attrs(trait_item.def_id)
-                        .flags
-                        .intersects(CodegenFnAttrFlags::TRACK_CALLER);
-                }
+        if let ty::AssocItemContainer::ImplContainer(_) = impl_item.container {
+            if let Some(trait_item) = impl_item.trait_item_def_id {
+                return tcx
+                    .codegen_fn_attrs(trait_item)
+                    .flags
+                    .intersects(CodegenFnAttrFlags::TRACK_CALLER);
             }
         }
     }
diff --git a/src/test/ui/span/impl-wrong-item-for-trait.stderr b/src/test/ui/span/impl-wrong-item-for-trait.stderr
index de200ca0721..d805bbc7926 100644
--- a/src/test/ui/span/impl-wrong-item-for-trait.stderr
+++ b/src/test/ui/span/impl-wrong-item-for-trait.stderr
@@ -4,6 +4,15 @@ error[E0437]: type `bar` is not a member of trait `Foo`
 LL |     type bar = u64;
    |     ^^^^^^^^^^^^^^^ not a member of trait `Foo`
 
+error[E0324]: item `MY_CONST` is an associated method, which doesn't match its trait `Foo`
+  --> $DIR/impl-wrong-item-for-trait.rs:22:5
+   |
+LL |     const MY_CONST: u32;
+   |     -------------------- item in trait
+...
+LL |     fn MY_CONST() {}
+   |     ^^^^^^^^^^^^^^^^ does not match trait
+
 error[E0323]: item `bar` is an associated const, which doesn't match its trait `Foo`
   --> $DIR/impl-wrong-item-for-trait.rs:12:5
    |
@@ -13,6 +22,15 @@ LL |     fn bar(&self);
 LL |     const bar: u64 = 1;
    |     ^^^^^^^^^^^^^^^^^^^ does not match trait
 
+error[E0325]: item `bar` is an associated type, which doesn't match its trait `Foo`
+  --> $DIR/impl-wrong-item-for-trait.rs:30:5
+   |
+LL |     fn bar(&self);
+   |     -------------- item in trait
+...
+LL |     type bar = u64;
+   |     ^^^^^^^^^^^^^^^ does not match trait
+
 error[E0046]: not all trait items implemented, missing: `bar`
   --> $DIR/impl-wrong-item-for-trait.rs:10:1
    |
@@ -22,15 +40,6 @@ LL |     fn bar(&self);
 LL | impl Foo for FooConstForMethod {
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ missing `bar` in implementation
 
-error[E0324]: item `MY_CONST` is an associated method, which doesn't match its trait `Foo`
-  --> $DIR/impl-wrong-item-for-trait.rs:22:5
-   |
-LL |     const MY_CONST: u32;
-   |     -------------------- item in trait
-...
-LL |     fn MY_CONST() {}
-   |     ^^^^^^^^^^^^^^^^ does not match trait
-
 error[E0046]: not all trait items implemented, missing: `MY_CONST`
   --> $DIR/impl-wrong-item-for-trait.rs:19:1
    |
@@ -40,15 +49,6 @@ LL |     const MY_CONST: u32;
 LL | impl Foo for FooMethodForConst {
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ missing `MY_CONST` in implementation
 
-error[E0325]: item `bar` is an associated type, which doesn't match its trait `Foo`
-  --> $DIR/impl-wrong-item-for-trait.rs:30:5
-   |
-LL |     fn bar(&self);
-   |     -------------- item in trait
-...
-LL |     type bar = u64;
-   |     ^^^^^^^^^^^^^^^ does not match trait
-
 error[E0046]: not all trait items implemented, missing: `bar`
   --> $DIR/impl-wrong-item-for-trait.rs:28:1
    |
diff --git a/src/tools/clippy/clippy_lints/src/len_zero.rs b/src/tools/clippy/clippy_lints/src/len_zero.rs
index 20e6220ec7d..64f6d62fbdc 100644
--- a/src/tools/clippy/clippy_lints/src/len_zero.rs
+++ b/src/tools/clippy/clippy_lints/src/len_zero.rs
@@ -214,14 +214,14 @@ fn check_trait_items(cx: &LateContext<'_>, visited_trait: &Item<'_>, trait_items
     {
         let mut current_and_super_traits = DefIdSet::default();
         fill_trait_set(visited_trait.def_id.to_def_id(), &mut current_and_super_traits, cx);
+        let is_empty = sym!(is_empty);
 
         let is_empty_method_found = current_and_super_traits
             .iter()
-            .flat_map(|&i| cx.tcx.associated_items(i).in_definition_order())
+            .flat_map(|&i| cx.tcx.associated_items(i).filter_by_name_unhygienic(is_empty))
             .any(|i| {
                 i.kind == ty::AssocKind::Fn
                     && i.fn_has_self_parameter
-                    && i.ident.name == sym!(is_empty)
                     && cx.tcx.fn_sig(i.def_id).inputs().skip_binder().len() == 1
             });
 
@@ -458,7 +458,7 @@ fn is_empty_array(expr: &Expr<'_>) -> bool {
 fn has_is_empty(cx: &LateContext<'_>, expr: &Expr<'_>) -> bool {
     /// Gets an `AssocItem` and return true if it matches `is_empty(self)`.
     fn is_is_empty(cx: &LateContext<'_>, item: &ty::AssocItem) -> bool {
-        if item.kind == ty::AssocKind::Fn && item.ident.name.as_str() == "is_empty" {
+        if item.kind == ty::AssocKind::Fn {
             let sig = cx.tcx.fn_sig(item.def_id);
             let ty = sig.skip_binder();
             ty.inputs().len() == 1
@@ -469,10 +469,11 @@ fn has_is_empty(cx: &LateContext<'_>, expr: &Expr<'_>) -> bool {
 
     /// Checks the inherent impl's items for an `is_empty(self)` method.
     fn has_is_empty_impl(cx: &LateContext<'_>, id: DefId) -> bool {
+        let is_empty = sym!(is_empty);
         cx.tcx.inherent_impls(id).iter().any(|imp| {
             cx.tcx
                 .associated_items(*imp)
-                .in_definition_order()
+                .filter_by_name_unhygienic(is_empty)
                 .any(|item| is_is_empty(cx, item))
         })
     }
@@ -480,9 +481,10 @@ fn has_is_empty(cx: &LateContext<'_>, expr: &Expr<'_>) -> bool {
     let ty = &cx.typeck_results().expr_ty(expr).peel_refs();
     match ty.kind() {
         ty::Dynamic(tt, ..) => tt.principal().map_or(false, |principal| {
+            let is_empty = sym!(is_empty);
             cx.tcx
                 .associated_items(principal.def_id())
-                .in_definition_order()
+                .filter_by_name_unhygienic(is_empty)
                 .any(|item| is_is_empty(cx, item))
         }),
         ty::Projection(ref proj) => has_is_empty_impl(cx, proj.item_def_id),
diff --git a/src/tools/clippy/clippy_lints/src/non_copy_const.rs b/src/tools/clippy/clippy_lints/src/non_copy_const.rs
index 074ba9e92ba..7d2ff083b7e 100644
--- a/src/tools/clippy/clippy_lints/src/non_copy_const.rs
+++ b/src/tools/clippy/clippy_lints/src/non_copy_const.rs
@@ -12,11 +12,10 @@ use rustc_hir::def_id::DefId;
 use rustc_hir::{
     BodyId, Expr, ExprKind, HirId, Impl, ImplItem, ImplItemKind, Item, ItemKind, Node, TraitItem, TraitItemKind, UnOp,
 };
-use rustc_infer::traits::specialization_graph;
 use rustc_lint::{LateContext, LateLintPass, Lint};
 use rustc_middle::mir::interpret::{ConstValue, ErrorHandled};
 use rustc_middle::ty::adjustment::Adjust;
-use rustc_middle::ty::{self, AssocKind, Const, Ty};
+use rustc_middle::ty::{self, Const, Ty};
 use rustc_session::{declare_lint_pass, declare_tool_lint};
 use rustc_span::{InnerSpan, Span, DUMMY_SP};
 use rustc_typeck::hir_ty_to_ty;
@@ -293,8 +292,10 @@ impl<'tcx> LateLintPass<'tcx> for NonCopyConst {
                         // Lint a trait impl item only when the definition is a generic type,
                         // assuming an assoc const is not meant to be an interior mutable type.
                         if let Some(of_trait_def_id) = of_trait_ref.trait_def_id();
-                        if let Some(of_assoc_item) = specialization_graph::Node::Trait(of_trait_def_id)
-                            .item(cx.tcx, impl_item.ident, AssocKind::Const, of_trait_def_id);
+                        if let Some(of_assoc_item) = cx
+                            .tcx
+                            .associated_item(impl_item.def_id)
+                            .trait_item_def_id;
                         if cx
                             .tcx
                             .layout_of(cx.tcx.param_env(of_trait_def_id).and(
@@ -303,7 +304,7 @@ impl<'tcx> LateLintPass<'tcx> for NonCopyConst {
                                 // and, in that case, the definition is *not* generic.
                                 cx.tcx.normalize_erasing_regions(
                                     cx.tcx.param_env(of_trait_def_id),
-                                    cx.tcx.type_of(of_assoc_item.def_id),
+                                    cx.tcx.type_of(of_assoc_item),
                                 ),
                             ))
                             .is_err();
diff --git a/src/tools/clippy/clippy_lints/src/use_self.rs b/src/tools/clippy/clippy_lints/src/use_self.rs
index 059f7f647f8..a86db58741e 100644
--- a/src/tools/clippy/clippy_lints/src/use_self.rs
+++ b/src/tools/clippy/clippy_lints/src/use_self.rs
@@ -13,7 +13,6 @@ use rustc_hir::{
 };
 use rustc_lint::{LateContext, LateLintPass, LintContext};
 use rustc_middle::hir::map::Map;
-use rustc_middle::ty::AssocKind;
 use rustc_semver::RustcVersion;
 use rustc_session::{declare_tool_lint, impl_lint_pass};
 use rustc_span::Span;
@@ -143,10 +142,10 @@ impl<'tcx> LateLintPass<'tcx> for UseSelf {
                 // trait, not in the impl of the trait.
                 let trait_method = cx
                     .tcx
-                    .associated_items(impl_trait_ref.def_id)
-                    .find_by_name_and_kind(cx.tcx, impl_item.ident, AssocKind::Fn, impl_trait_ref.def_id)
+                    .associated_item(impl_item.def_id)
+                    .trait_item_def_id
                     .expect("impl method matches a trait method");
-                let trait_method_sig = cx.tcx.fn_sig(trait_method.def_id);
+                let trait_method_sig = cx.tcx.fn_sig(trait_method);
                 let trait_method_sig = cx.tcx.erase_late_bound_regions(trait_method_sig);
 
                 // `impl_inputs_outputs` is an iterator over the types (`hir::Ty`) declared in the