Rollup merge of #68911 - jonas-schievink:inherent-overlap, r=petrochenkov

Speed up the inherent impl overlap check

This gives a ~7% improvement in compile times for the stm32f0(x2) crate.

Also addresses @eddyb's comment in https://github.com/rust-lang/rust/pull/68837#discussion_r375701767.

28 files changed, 129 insertions, 99 deletions

diff --git a/src/librustc/query/mod.rs b/src/librustc/query/mod.rs
index d1bccb961c4..7cb1f3aa0e8 100644
--- a/src/librustc/query/mod.rs
+++ b/src/librustc/query/mod.rs
@@ -323,7 +323,7 @@ rustc_queries! {
         query associated_item(_: DefId) -> ty::AssocItem {}
 
         /// Collects the associated items defined on a trait or impl.
-        query associated_items(key: DefId) -> ty::AssocItemsIterator<'tcx> {
+        query associated_items(key: DefId) -> &'tcx [ty::AssocItem] {
             desc { |tcx| "collecting associated items of {}", tcx.def_path_str(key) }
         }
 
diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index 25bb54033f1..783807b5c3b 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -541,6 +541,7 @@ fn vtable_methods<'tcx>(
     tcx.arena.alloc_from_iter(supertraits(tcx, trait_ref).flat_map(move |trait_ref| {
         let trait_methods = tcx
             .associated_items(trait_ref.def_id())
+            .iter()
             .filter(|item| item.kind == ty::AssocKind::Method);
 
         // Now list each method's DefId and InternalSubsts (for within its trait).
diff --git a/src/librustc/traits/object_safety.rs b/src/librustc/traits/object_safety.rs
index d0dbfe73c91..3c886ce7f3e 100644
--- a/src/librustc/traits/object_safety.rs
+++ b/src/librustc/traits/object_safety.rs
@@ -212,6 +212,7 @@ fn object_safety_violations_for_trait(
     // Check methods for violations.
     let mut violations: Vec<_> = tcx
         .associated_items(trait_def_id)
+        .iter()
         .filter(|item| item.kind == ty::AssocKind::Method)
         .filter_map(|item| {
             object_safety_violation_for_method(tcx, trait_def_id, &item)
@@ -277,6 +278,7 @@ fn object_safety_violations_for_trait(
 
     violations.extend(
         tcx.associated_items(trait_def_id)
+            .iter()
             .filter(|item| item.kind == ty::AssocKind::Const)
             .map(|item| ObjectSafetyViolation::AssocConst(item.ident.name, item.ident.span)),
     );
@@ -632,7 +634,9 @@ fn object_ty_for_trait<'tcx>(
 
     let mut associated_types = traits::supertraits(tcx, ty::Binder::dummy(trait_ref))
         .flat_map(|super_trait_ref| {
-            tcx.associated_items(super_trait_ref.def_id()).map(move |item| (super_trait_ref, item))
+            tcx.associated_items(super_trait_ref.def_id())
+                .iter()
+                .map(move |item| (super_trait_ref, item))
         })
         .filter(|(_, item)| item.kind == ty::AssocKind::Type)
         .collect::<Vec<_>>();
diff --git a/src/librustc/traits/project.rs b/src/librustc/traits/project.rs
index a1d785cf444..e0eb731f9b2 100644
--- a/src/librustc/traits/project.rs
+++ b/src/librustc/traits/project.rs
@@ -1473,7 +1473,7 @@ fn assoc_ty_def(
         {
             return specialization_graph::NodeItem {
                 node: specialization_graph::Node::Impl(impl_def_id),
-                item,
+                item: *item,
             };
         }
     }
diff --git a/src/librustc/traits/types/specialization_graph.rs b/src/librustc/traits/types/specialization_graph.rs
index 3086850db6d..36a84369d4a 100644
--- a/src/librustc/traits/types/specialization_graph.rs
+++ b/src/librustc/traits/types/specialization_graph.rs
@@ -81,7 +81,7 @@ impl<'tcx> Node {
     }
 
     /// Iterate over the items defined directly by the given (impl or trait) node.
-    pub fn items(&self, tcx: TyCtxt<'tcx>) -> ty::AssocItemsIterator<'tcx> {
+    pub fn items(&self, tcx: TyCtxt<'tcx>) -> &'tcx [ty::AssocItem] {
         tcx.associated_items(self.def_id())
     }
 
@@ -98,8 +98,10 @@ impl<'tcx> Node {
     ) -> Option<ty::AssocItem> {
         use crate::ty::AssocKind::*;
 
-        tcx.associated_items(self.def_id()).find(move |impl_item| {
-            match (trait_item_kind, impl_item.kind) {
+        tcx.associated_items(self.def_id())
+            .iter()
+            .find(move |impl_item| {
+                match (trait_item_kind, impl_item.kind) {
                 | (Const, Const)
                 | (Method, Method)
                 | (Type, Type)
@@ -112,7 +114,8 @@ impl<'tcx> Node {
                 | (OpaqueTy, _)
                 => false,
             }
-        })
+            })
+            .copied()
     }
 
     pub fn def_id(&self) -> DefId {
diff --git a/src/librustc/traits/wf.rs b/src/librustc/traits/wf.rs
index fbcb77a4031..1c47b535316 100644
--- a/src/librustc/traits/wf.rs
+++ b/src/librustc/traits/wf.rs
@@ -166,7 +166,7 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
         let extend_cause_with_original_assoc_item_obligation =
             |cause: &mut traits::ObligationCause<'_>,
              pred: &ty::Predicate<'_>,
-             trait_assoc_items: ty::AssocItemsIterator<'_>| {
+             trait_assoc_items: &[ty::AssocItem]| {
                 let trait_item = tcx
                     .hir()
                     .as_local_hir_id(trait_ref.def_id)
@@ -283,6 +283,7 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
                         ) = (&proj.skip_binder().self_ty().kind, item.map(|i| &i.kind))
                         {
                             if let Some((impl_item, trait_assoc_item)) = trait_assoc_items
+                                .iter()
                                 .filter(|i| i.def_id == *item_def_id)
                                 .next()
                                 .and_then(|trait_assoc_item| {
@@ -325,7 +326,7 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
                 extend_cause_with_original_assoc_item_obligation(
                     &mut cause,
                     &pred,
-                    trait_assoc_items.clone(),
+                    trait_assoc_items,
                 );
                 traits::Obligation::new(cause, param_env, pred)
             });
diff --git a/src/librustc/ty/adjustment.rs b/src/librustc/ty/adjustment.rs
index db034d1618c..f4006a1cd40 100644
--- a/src/librustc/ty/adjustment.rs
+++ b/src/librustc/ty/adjustment.rs
@@ -122,6 +122,7 @@ impl<'tcx> OverloadedDeref<'tcx> {
         };
         let method_def_id = tcx
             .associated_items(trait_def_id.unwrap())
+            .iter()
             .find(|m| m.kind == ty::AssocKind::Method)
             .unwrap()
             .def_id;
diff --git a/src/librustc/ty/instance.rs b/src/librustc/ty/instance.rs
index 51a18f8eae2..c7f19513f66 100644
--- a/src/librustc/ty/instance.rs
+++ b/src/librustc/ty/instance.rs
@@ -376,6 +376,7 @@ impl<'tcx> Instance<'tcx> {
         let fn_once = tcx.lang_items().fn_once_trait().unwrap();
         let call_once = tcx
             .associated_items(fn_once)
+            .iter()
             .find(|it| it.kind == ty::AssocKind::Method)
             .unwrap()
             .def_id;
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 2538322431e..0118fc4c8ac 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -2705,14 +2705,14 @@ impl<'tcx> TyCtxt<'tcx> {
             .for_each(|&body_id| f(self.hir().body_owner_def_id(body_id)));
     }
 
-    pub fn provided_trait_methods(self, id: DefId) -> Vec<AssocItem> {
+    pub fn provided_trait_methods(self, id: DefId) -> impl Iterator<Item = &'tcx AssocItem> {
         self.associated_items(id)
+            .iter()
             .filter(|item| item.kind == AssocKind::Method && item.defaultness.has_value())
-            .collect()
     }
 
     pub fn trait_relevant_for_never(self, did: DefId) -> bool {
-        self.associated_items(did).any(|item| item.relevant_for_never())
+        self.associated_items(did).iter().any(|item| item.relevant_for_never())
     }
 
     pub fn opt_item_name(self, def_id: DefId) -> Option<Ident> {
@@ -2974,25 +2974,6 @@ impl<'tcx> TyCtxt<'tcx> {
     }
 }
 
-#[derive(Copy, Clone, HashStable)]
-pub struct AssocItemsIterator<'tcx> {
-    pub items: &'tcx [AssocItem],
-}
-
-impl<'tcx> Iterator for AssocItemsIterator<'tcx> {
-    type Item = AssocItem;
-
-    #[inline]
-    fn next(&mut self) -> Option<AssocItem> {
-        if let Some((first, rest)) = self.items.split_first() {
-            self.items = rest;
-            Some(*first)
-        } else {
-            None
-        }
-    }
-}
-
 #[derive(Clone, HashStable)]
 pub struct AdtSizedConstraint<'tcx>(pub &'tcx [Ty<'tcx>]);
 
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index 4c5bc3debde..0718853b1df 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -1066,6 +1066,7 @@ impl<'tcx> ProjectionTy<'tcx> {
     ) -> ProjectionTy<'tcx> {
         let item_def_id = tcx
             .associated_items(trait_ref.def_id)
+            .iter()
             .find(|item| {
                 item.kind == ty::AssocKind::Type
                     && tcx.hygienic_eq(item_name, item.ident, trait_ref.def_id)
diff --git a/src/librustc/ty/util.rs b/src/librustc/ty/util.rs
index 4dfff85d531..5d5fa4090c8 100644
--- a/src/librustc/ty/util.rs
+++ b/src/librustc/ty/util.rs
@@ -355,7 +355,7 @@ impl<'tcx> TyCtxt<'tcx> {
         let mut dtor_did = None;
         let ty = self.type_of(adt_did);
         self.for_each_relevant_impl(drop_trait, ty, |impl_did| {
-            if let Some(item) = self.associated_items(impl_did).next() {
+            if let Some(item) = self.associated_items(impl_did).first() {
                 if validate(self, impl_did).is_ok() {
                     dtor_did = Some(item.def_id);
                 }
diff --git a/src/librustc_mir/shim.rs b/src/librustc_mir/shim.rs
index 94a5f2b3bf8..a8c66be359c 100644
--- a/src/librustc_mir/shim.rs
+++ b/src/librustc_mir/shim.rs
@@ -68,6 +68,7 @@ fn make_shim<'tcx>(tcx: TyCtxt<'tcx>, instance: ty::InstanceDef<'tcx>) -> &'tcx
             let fn_mut = tcx.lang_items().fn_mut_trait().unwrap();
             let call_mut = tcx
                 .associated_items(fn_mut)
+                .iter()
                 .find(|it| it.kind == ty::AssocKind::Method)
                 .unwrap()
                 .def_id;
diff --git a/src/librustc_mir/util/elaborate_drops.rs b/src/librustc_mir/util/elaborate_drops.rs
index 1be3da4b3d8..091ae1bbb79 100644
--- a/src/librustc_mir/util/elaborate_drops.rs
+++ b/src/librustc_mir/util/elaborate_drops.rs
@@ -539,7 +539,7 @@ where
         debug!("destructor_call_block({:?}, {:?})", self, succ);
         let tcx = self.tcx();
         let drop_trait = tcx.lang_items().drop_trait().unwrap();
-        let drop_fn = tcx.associated_items(drop_trait).next().unwrap();
+        let drop_fn = tcx.associated_items(drop_trait)[0];
         let ty = self.place_ty(self.place);
         let substs = tcx.mk_substs_trait(ty, &[]);
 
diff --git a/src/librustc_passes/reachable.rs b/src/librustc_passes/reachable.rs
index 667898046ac..888f4370dd5 100644
--- a/src/librustc_passes/reachable.rs
+++ b/src/librustc_passes/reachable.rs
@@ -362,12 +362,12 @@ impl<'a, 'tcx> ItemLikeVisitor<'tcx> for CollectPrivateImplItemsVisitor<'a, 'tcx
                     return;
                 }
 
-                let provided_trait_methods = self.tcx.provided_trait_methods(trait_def_id);
-                self.worklist.reserve(provided_trait_methods.len());
-                for default_method in provided_trait_methods {
-                    let hir_id = self.tcx.hir().as_local_hir_id(default_method.def_id).unwrap();
-                    self.worklist.push(hir_id);
-                }
+                // FIXME(#53488) remove `let`
+                let tcx = self.tcx;
+                self.worklist.extend(
+                    tcx.provided_trait_methods(trait_def_id)
+                        .map(|assoc| tcx.hir().as_local_hir_id(assoc.def_id).unwrap()),
+                );
             }
         }
     }
diff --git a/src/librustc_passes/stability.rs b/src/librustc_passes/stability.rs
index 4009cc6d725..12debfb66a4 100644
--- a/src/librustc_passes/stability.rs
+++ b/src/librustc_passes/stability.rs
@@ -468,6 +468,7 @@ impl Visitor<'tcx> for Checker<'tcx> {
                         let trait_item_def_id = self
                             .tcx
                             .associated_items(trait_did)
+                            .iter()
                             .find(|item| item.ident.name == impl_item.ident.name)
                             .map(|item| item.def_id);
                         if let Some(def_id) = trait_item_def_id {
diff --git a/src/librustc_save_analysis/lib.rs b/src/librustc_save_analysis/lib.rs
index e32f4744366..401e1722751 100644
--- a/src/librustc_save_analysis/lib.rs
+++ b/src/librustc_save_analysis/lib.rs
@@ -423,6 +423,7 @@ impl<'l, 'tcx> SaveContext<'l, 'tcx> {
                             qualname.push_str(&self.tcx.def_path_str(def_id));
                             self.tcx
                                 .associated_items(def_id)
+                                .iter()
                                 .find(|item| item.ident.name == ident.name)
                                 .map(|item| decl_id = Some(item.def_id));
                         }
@@ -717,6 +718,7 @@ impl<'l, 'tcx> SaveContext<'l, 'tcx> {
                     let ti = self.tcx.associated_item(decl_id);
                     self.tcx
                         .associated_items(ti.container.id())
+                        .iter()
                         .find(|item| {
                             item.ident.name == ti.ident.name && item.defaultness.has_value()
                         })
diff --git a/src/librustc_ty/ty.rs b/src/librustc_ty/ty.rs
index aa05165e3de..b032acf82f5 100644
--- a/src/librustc_ty/ty.rs
+++ b/src/librustc_ty/ty.rs
@@ -206,12 +206,10 @@ fn associated_item_def_ids(tcx: TyCtxt<'_>, def_id: DefId) -> &[DefId] {
     }
 }
 
-fn associated_items<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> ty::AssocItemsIterator<'tcx> {
-    ty::AssocItemsIterator {
-        items: tcx.arena.alloc_from_iter(
-            tcx.associated_item_def_ids(def_id).iter().map(|did| tcx.associated_item(*did)),
-        ),
-    }
+fn associated_items<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> &'tcx [ty::AssocItem] {
+    tcx.arena.alloc_from_iter(
+        tcx.associated_item_def_ids(def_id).iter().map(|did| tcx.associated_item(*did)),
+    )
 }
 
 fn def_span(tcx: TyCtxt<'_>, def_id: DefId) -> Span {
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index 6bd120d818d..2909d0f8c54 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -1109,7 +1109,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         trait_def_id: DefId,
         assoc_name: ast::Ident,
     ) -> bool {
-        self.tcx().associated_items(trait_def_id).any(|item| {
+        self.tcx().associated_items(trait_def_id).iter().any(|item| {
             item.kind == ty::AssocKind::Type
                 && self.tcx().hygienic_eq(assoc_name, item.ident, trait_def_id)
         })
@@ -1347,6 +1347,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
             tcx.adjust_ident_and_get_scope(binding.item_name, candidate.def_id(), hir_ref_id);
         let assoc_ty = tcx
             .associated_items(candidate.def_id())
+            .iter()
             .find(|i| i.kind == ty::AssocKind::Type && i.ident.modern() == assoc_ident)
             .expect("missing associated type");
 
@@ -1512,6 +1513,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
                     ty::Predicate::Trait(pred, _) => {
                         associated_types.entry(span).or_default().extend(
                             tcx.associated_items(pred.def_id())
+                                .iter()
                                 .filter(|item| item.kind == ty::AssocKind::Type)
                                 .map(|item| item.def_id),
                         );
@@ -1969,6 +1971,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
                 let bound_span = self
                     .tcx()
                     .associated_items(bound.def_id())
+                    .iter()
                     .find(|item| {
                         item.kind == ty::AssocKind::Type
                             && self.tcx().hygienic_eq(assoc_name, item.ident, bound.def_id())
@@ -2198,6 +2201,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
             tcx.adjust_ident_and_get_scope(assoc_ident, trait_did, hir_ref_id);
         let item = tcx
             .associated_items(trait_did)
+            .iter()
             .find(|i| Namespace::from(i.kind) == Namespace::Type && i.ident.modern() == assoc_ident)
             .expect("missing associated type");
 
diff --git a/src/librustc_typeck/check/closure.rs b/src/librustc_typeck/check/closure.rs
index 26777b3b010..707125b3fd5 100644
--- a/src/librustc_typeck/check/closure.rs
+++ b/src/librustc_typeck/check/closure.rs
@@ -248,7 +248,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
         if is_gen {
             // Check that we deduce the signature from the `<_ as std::ops::Generator>::Return`
             // associated item and not yield.
-            let return_assoc_item = self.tcx.associated_items(gen_trait).nth(1).unwrap().def_id;
+            let return_assoc_item = self.tcx.associated_items(gen_trait)[1].def_id;
             if return_assoc_item != projection.projection_def_id() {
                 debug!("deduce_sig_from_projection: not return assoc item of generator");
                 return None;
@@ -673,7 +673,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
 
         // The `Future` trait has only one associted item, `Output`,
         // so check that this is what we see.
-        let output_assoc_item = self.tcx.associated_items(future_trait).nth(0).unwrap().def_id;
+        let output_assoc_item = self.tcx.associated_items(future_trait)[0].def_id;
         if output_assoc_item != predicate.projection_ty.item_def_id {
             span_bug!(
                 cause_span,
diff --git a/src/librustc_typeck/check/demand.rs b/src/librustc_typeck/check/demand.rs
index e0f9fcc6932..8c7f1330820 100644
--- a/src/librustc_typeck/check/demand.rs
+++ b/src/librustc_typeck/check/demand.rs
@@ -536,6 +536,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                 let item_def_id = self
                     .tcx
                     .associated_items(deref_trait)
+                    .iter()
                     .find(|item| item.kind == ty::AssocKind::Type)
                     .unwrap()
                     .def_id;
diff --git a/src/librustc_typeck/check/method/mod.rs b/src/librustc_typeck/check/method/mod.rs
index e90c2ef5e43..67d8030a9d6 100644
--- a/src/librustc_typeck/check/method/mod.rs
+++ b/src/librustc_typeck/check/method/mod.rs
@@ -474,8 +474,13 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
         item_name: ast::Ident,
         ns: Namespace,
     ) -> Option<ty::AssocItem> {
-        self.tcx.associated_items(def_id).find(|item| {
-            Namespace::from(item.kind) == ns && self.tcx.hygienic_eq(item_name, item.ident, def_id)
-        })
+        self.tcx
+            .associated_items(def_id)
+            .iter()
+            .find(|item| {
+                Namespace::from(item.kind) == ns
+                    && self.tcx.hygienic_eq(item_name, item.ident, def_id)
+            })
+            .copied()
     }
 }
diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs
index 2444fc60f77..497a401a031 100644
--- a/src/librustc_typeck/check/method/probe.rs
+++ b/src/librustc_typeck/check/method/probe.rs
@@ -1696,10 +1696,12 @@ impl<'a, 'tcx> ProbeContext<'a, 'tcx> {
                 let max_dist = max(name.as_str().len(), 3) / 3;
                 self.tcx
                     .associated_items(def_id)
+                    .iter()
                     .filter(|x| {
                         let dist = lev_distance(&*name.as_str(), &x.ident.as_str());
                         Namespace::from(x.kind) == Namespace::Value && dist > 0 && dist <= max_dist
                     })
+                    .copied()
                     .collect()
             } else {
                 self.fcx
@@ -1707,7 +1709,7 @@ impl<'a, 'tcx> ProbeContext<'a, 'tcx> {
                     .map_or(Vec::new(), |x| vec![x])
             }
         } else {
-            self.tcx.associated_items(def_id).collect()
+            self.tcx.associated_items(def_id).to_vec()
         }
     }
 }
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 15cf05a7f7f..f7cba1521cb 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -1976,6 +1976,7 @@ fn check_impl_items_against_trait<'tcx>(
         let ty_impl_item = tcx.associated_item(tcx.hir().local_def_id(impl_item.hir_id));
         let ty_trait_item = tcx
             .associated_items(impl_trait_ref.def_id)
+            .iter()
             .find(|ac| {
                 Namespace::from(&impl_item.kind) == Namespace::from(ac.kind)
                     && tcx.hygienic_eq(ty_impl_item.ident, ac.ident, impl_trait_ref.def_id)
@@ -1983,6 +1984,7 @@ fn check_impl_items_against_trait<'tcx>(
             .or_else(|| {
                 // Not compatible, but needed for the error message
                 tcx.associated_items(impl_trait_ref.def_id)
+                    .iter()
                     .find(|ac| tcx.hygienic_eq(ty_impl_item.ident, ac.ident, impl_trait_ref.def_id))
             });
 
@@ -2096,7 +2098,7 @@ fn check_impl_items_against_trait<'tcx>(
 
         if !is_implemented && !traits::impl_is_default(tcx, impl_id) {
             if !trait_item.defaultness.has_value() {
-                missing_items.push(trait_item);
+                missing_items.push(*trait_item);
             } else if associated_type_overridden {
                 invalidated_items.push(trait_item.ident);
             }
@@ -5175,7 +5177,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                 // Check for `Future` implementations by constructing a predicate to
                 // prove: `<T as Future>::Output == U`
                 let future_trait = self.tcx.lang_items().future_trait().unwrap();
-                let item_def_id = self.tcx.associated_items(future_trait).next().unwrap().def_id;
+                let item_def_id = self.tcx.associated_items(future_trait)[0].def_id;
                 let predicate =
                     ty::Predicate::Projection(ty::Binder::bind(ty::ProjectionPredicate {
                         // `<T as Future>::Output`
diff --git a/src/librustc_typeck/coherence/inherent_impls_overlap.rs b/src/librustc_typeck/coherence/inherent_impls_overlap.rs
index 3e17b661cf4..fb9c173f520 100644
--- a/src/librustc_typeck/coherence/inherent_impls_overlap.rs
+++ b/src/librustc_typeck/coherence/inherent_impls_overlap.rs
@@ -1,6 +1,6 @@
 use crate::namespace::Namespace;
 use rustc::traits::{self, IntercrateMode, SkipLeakCheck};
-use rustc::ty::TyCtxt;
+use rustc::ty::{AssocItem, TyCtxt};
 use rustc_errors::struct_span_err;
 use rustc_hir as hir;
 use rustc_hir::def_id::{CrateNum, DefId, LOCAL_CRATE};
@@ -17,38 +17,60 @@ struct InherentOverlapChecker<'tcx> {
 }
 
 impl InherentOverlapChecker<'tcx> {
+    /// Checks whether any associated items in impls 1 and 2 share the same identifier and
+    /// namespace.
+    fn impls_have_common_items(&self, impl1: DefId, impl2: DefId) -> bool {
+        let impl_items1 = self.tcx.associated_items(impl1);
+        let impl_items2 = self.tcx.associated_items(impl2);
+
+        for item1 in &impl_items1[..] {
+            for item2 in &impl_items2[..] {
+                // Avoid costly `.modern()` calls as much as possible by doing them as late as we
+                // can. Compare raw symbols first.
+                if item1.ident.name == item2.ident.name
+                    && Namespace::from(item1.kind) == Namespace::from(item2.kind)
+                {
+                    // Symbols and namespace match, compare hygienically.
+                    if item1.ident.modern() == item2.ident.modern() {
+                        return true;
+                    }
+                }
+            }
+        }
+
+        false
+    }
+
     fn check_for_common_items_in_impls(
         &self,
         impl1: DefId,
         impl2: DefId,
         overlap: traits::OverlapResult<'_>,
     ) {
-        let name_and_namespace = |def_id| {
-            let item = self.tcx.associated_item(def_id);
-            (item.ident.modern(), Namespace::from(item.kind))
-        };
+        let name_and_namespace =
+            |assoc: &AssocItem| (assoc.ident.modern(), Namespace::from(assoc.kind));
 
-        let impl_items1 = self.tcx.associated_item_def_ids(impl1);
-        let impl_items2 = self.tcx.associated_item_def_ids(impl2);
+        let impl_items1 = self.tcx.associated_items(impl1);
+        let impl_items2 = self.tcx.associated_items(impl2);
 
-        for &item1 in &impl_items1[..] {
+        for item1 in &impl_items1[..] {
             let (name, namespace) = name_and_namespace(item1);
 
-            for &item2 in &impl_items2[..] {
+            for item2 in &impl_items2[..] {
                 if (name, namespace) == name_and_namespace(item2) {
                     let mut err = struct_span_err!(
                         self.tcx.sess,
-                        self.tcx.span_of_impl(item1).unwrap(),
+                        self.tcx.span_of_impl(item1.def_id).unwrap(),
                         E0592,
                         "duplicate definitions with name `{}`",
                         name
                     );
                     err.span_label(
-                        self.tcx.span_of_impl(item1).unwrap(),
+                        self.tcx.span_of_impl(item1.def_id).unwrap(),
                         format!("duplicate definitions for `{}`", name),
                     );
                     err.span_label(
-                        self.tcx.span_of_impl(item2).unwrap(),
+                        self.tcx.span_of_impl(item2.def_id).unwrap(),
                         format!("other definition for `{}`", name),
                     );
 
@@ -66,27 +88,21 @@ impl InherentOverlapChecker<'tcx> {
         }
     }
 
-    fn check_for_overlapping_inherent_impls(&self, ty_def_id: DefId) {
-        let impls = self.tcx.inherent_impls(ty_def_id);
-
-        for (i, &impl1_def_id) in impls.iter().enumerate() {
-            for &impl2_def_id in &impls[(i + 1)..] {
-                traits::overlapping_impls(
-                    self.tcx,
-                    impl1_def_id,
-                    impl2_def_id,
-                    IntercrateMode::Issue43355,
-                    // We go ahead and just skip the leak check for
-                    // inherent impls without warning.
-                    SkipLeakCheck::Yes,
-                    |overlap| {
-                        self.check_for_common_items_in_impls(impl1_def_id, impl2_def_id, overlap);
-                        false
-                    },
-                    || true,
-                );
-            }
-        }
+    fn check_for_overlapping_inherent_impls(&self, impl1_def_id: DefId, impl2_def_id: DefId) {
+        traits::overlapping_impls(
+            self.tcx,
+            impl1_def_id,
+            impl2_def_id,
+            IntercrateMode::Issue43355,
+            // We go ahead and just skip the leak check for
+            // inherent impls without warning.
+            SkipLeakCheck::Yes,
+            |overlap| {
+                self.check_for_common_items_in_impls(impl1_def_id, impl2_def_id, overlap);
+                false
+            },
+            || true,
+        );
     }
 }
 
@@ -97,8 +113,16 @@ impl ItemLikeVisitor<'v> for InherentOverlapChecker<'tcx> {
             | hir::ItemKind::Struct(..)
             | hir::ItemKind::Trait(..)
             | hir::ItemKind::Union(..) => {
-                let type_def_id = self.tcx.hir().local_def_id(item.hir_id);
-                self.check_for_overlapping_inherent_impls(type_def_id);
+                let ty_def_id = self.tcx.hir().local_def_id(item.hir_id);
+                let impls = self.tcx.inherent_impls(ty_def_id);
+
+                for (i, &impl1_def_id) in impls.iter().enumerate() {
+                    for &impl2_def_id in &impls[(i + 1)..] {
+                        if self.impls_have_common_items(impl1_def_id, impl2_def_id) {
+                            self.check_for_overlapping_inherent_impls(impl1_def_id, impl2_def_id);
+                        }
+                    }
+                }
             }
             _ => {}
         }
diff --git a/src/librustdoc/clean/blanket_impl.rs b/src/librustdoc/clean/blanket_impl.rs
index 18ebd254507..288446b6219 100644
--- a/src/librustdoc/clean/blanket_impl.rs
+++ b/src/librustdoc/clean/blanket_impl.rs
@@ -87,7 +87,6 @@ impl<'a, 'tcx> BlanketImplFinder<'a, 'tcx> {
                     .cx
                     .tcx
                     .provided_trait_methods(trait_def_id)
-                    .into_iter()
                     .map(|meth| meth.ident.to_string())
                     .collect();
 
@@ -115,6 +114,8 @@ impl<'a, 'tcx> BlanketImplFinder<'a, 'tcx> {
                             .cx
                             .tcx
                             .associated_items(impl_def_id)
+                            .iter()
+                            .copied()
                             .collect::<Vec<_>>()
                             .clean(self.cx),
                         polarity: None,
diff --git a/src/librustdoc/clean/inline.rs b/src/librustdoc/clean/inline.rs
index df72bf0b56e..90ce8802f65 100644
--- a/src/librustdoc/clean/inline.rs
+++ b/src/librustdoc/clean/inline.rs
@@ -191,7 +191,7 @@ pub fn record_extern_fqn(cx: &DocContext<'_>, did: DefId, kind: clean::TypeKind)
 
 pub fn build_external_trait(cx: &DocContext<'_>, did: DefId) -> clean::Trait {
     let auto_trait = cx.tcx.trait_def(did).has_auto_impl;
-    let trait_items = cx.tcx.associated_items(did).map(|item| item.clean(cx)).collect();
+    let trait_items = cx.tcx.associated_items(did).iter().map(|item| item.clean(cx)).collect();
     let predicates = cx.tcx.predicates_of(did);
     let generics = (cx.tcx.generics_of(did), predicates).clean(cx);
     let generics = filter_non_trait_generics(did, generics);
@@ -376,6 +376,7 @@ pub fn build_impl(
     } else {
         (
             tcx.associated_items(did)
+                .iter()
                 .filter_map(|item| {
                     if associated_trait.is_some() || item.vis == ty::Visibility::Public {
                         Some(item.clean(cx))
@@ -401,9 +402,7 @@ pub fn build_impl(
 
     let provided = trait_
         .def_id()
-        .map(|did| {
-            tcx.provided_trait_methods(did).into_iter().map(|meth| meth.ident.to_string()).collect()
-        })
+        .map(|did| tcx.provided_trait_methods(did).map(|meth| meth.ident.to_string()).collect())
         .unwrap_or_default();
 
     debug!("build_impl: impl {:?} for {:?}", trait_.def_id(), for_.def_id());
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index f140f11b090..87edc88611f 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -2108,11 +2108,7 @@ impl Clean<Vec<Item>> for doctree::Impl<'_> {
         let provided: FxHashSet<String> = trait_
             .def_id()
             .map(|did| {
-                cx.tcx
-                    .provided_trait_methods(did)
-                    .into_iter()
-                    .map(|meth| meth.ident.to_string())
-                    .collect()
+                cx.tcx.provided_trait_methods(did).map(|meth| meth.ident.to_string()).collect()
             })
             .unwrap_or_default();
 
diff --git a/src/librustdoc/passes/collect_intra_doc_links.rs b/src/librustdoc/passes/collect_intra_doc_links.rs
index 332d19fbfae..9ecf6d53129 100644
--- a/src/librustdoc/passes/collect_intra_doc_links.rs
+++ b/src/librustdoc/passes/collect_intra_doc_links.rs
@@ -206,6 +206,7 @@ impl<'a, 'tcx> LinkCollector<'a, 'tcx> {
                 return cx
                     .tcx
                     .associated_items(did)
+                    .iter()
                     .find(|item| item.ident.name == item_name)
                     .and_then(|item| match item.kind {
                         ty::AssocKind::Method => Some("method"),