Make lookup of associated item by name O(log n)

28 files changed, 216 insertions, 135 deletions

diff --git a/src/librustc/arena.rs b/src/librustc/arena.rs
index f5c83fed1fc..ca55d410ceb 100644
--- a/src/librustc/arena.rs
+++ b/src/librustc/arena.rs
@@ -48,6 +48,7 @@ macro_rules! arena_types {
             [] item_local_set: rustc_hir::ItemLocalSet,
             [decode] mir_const_qualif: rustc_index::bit_set::BitSet<rustc::mir::Local>,
             [] trait_impls_of: rustc::ty::trait_def::TraitImpls,
+            [] associated_items: rustc::ty::AssociatedItems,
             [] dropck_outlives:
                 rustc::infer::canonical::Canonical<'tcx,
                     rustc::infer::canonical::QueryResponse<'tcx,
diff --git a/src/librustc/query/mod.rs b/src/librustc/query/mod.rs
index 45ab3fc0b85..06e20d0a2ae 100644
--- a/src/librustc/query/mod.rs
+++ b/src/librustc/query/mod.rs
@@ -325,7 +325,7 @@ rustc_queries! {
         query associated_item(_: DefId) -> ty::AssocItem {}
 
         /// Collects the associated items defined on a trait or impl.
-        query associated_items(key: DefId) -> &'tcx [ty::AssocItem] {
+        query associated_items(key: DefId) -> &'tcx ty::AssociatedItems {
             desc { |tcx| "collecting associated items of {}", tcx.def_path_str(key) }
         }
 
diff --git a/src/librustc/traits/specialization_graph.rs b/src/librustc/traits/specialization_graph.rs
index 36a84369d4a..ee813bf606e 100644
--- a/src/librustc/traits/specialization_graph.rs
+++ b/src/librustc/traits/specialization_graph.rs
@@ -81,8 +81,8 @@ impl<'tcx> Node {
     }
 
     /// Iterate over the items defined directly by the given (impl or trait) node.
-    pub fn items(&self, tcx: TyCtxt<'tcx>) -> &'tcx [ty::AssocItem] {
-        tcx.associated_items(self.def_id())
+    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.
@@ -99,7 +99,7 @@ impl<'tcx> Node {
         use crate::ty::AssocKind::*;
 
         tcx.associated_items(self.def_id())
-            .iter()
+            .filter_by_name_unhygienic(trait_item_name.name)
             .find(move |impl_item| {
                 match (trait_item_kind, impl_item.kind) {
                 | (Const, Const)
diff --git a/src/librustc/ty/adjustment.rs b/src/librustc/ty/adjustment.rs
index f4006a1cd40..851bffc2065 100644
--- a/src/librustc/ty/adjustment.rs
+++ b/src/librustc/ty/adjustment.rs
@@ -122,7 +122,7 @@ impl<'tcx> OverloadedDeref<'tcx> {
         };
         let method_def_id = tcx
             .associated_items(trait_def_id.unwrap())
-            .iter()
+            .in_definition_order()
             .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 332fd0bf46f..0ec30bc583c 100644
--- a/src/librustc/ty/instance.rs
+++ b/src/librustc/ty/instance.rs
@@ -337,7 +337,7 @@ impl<'tcx> Instance<'tcx> {
         let fn_once = tcx.lang_items().fn_once_trait().unwrap();
         let call_once = tcx
             .associated_items(fn_once)
-            .iter()
+            .in_definition_order()
             .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 c70a296e34b..fa46f521ba5 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -30,6 +30,7 @@ use rustc_attr as attr;
 use rustc_data_structures::captures::Captures;
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::fx::FxIndexMap;
+use rustc_data_structures::sorted_map::SortedIndexMultiMap;
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_data_structures::sync::{self, par_iter, Lrc, ParallelIterator};
 use rustc_hir as hir;
@@ -264,6 +265,81 @@ impl AssocItem {
     }
 }
 
+/// A list of `ty::AssocItem`s in definition order that allows for efficient lookup by name.
+///
+/// When doing lookup by name, we try to postpone hygienic comparison for as long as possible since
+/// it is relatively expensive. Instead, items are indexed by `Symbol` and hygienic comparison is
+/// done only on items with the same name.
+#[derive(Debug, Clone, PartialEq, HashStable)]
+pub struct AssociatedItems {
+    items: SortedIndexMultiMap<u32, Symbol, ty::AssocItem>,
+}
+
+impl AssociatedItems {
+    /// Constructs an `AssociatedItems` map from a series of `ty::AssocItem`s in definition order.
+    pub fn new(items_in_def_order: Vec<ty::AssocItem>) -> Self {
+        let items = items_in_def_order.into_iter().map(|item| (item.ident.name, item)).collect();
+        AssociatedItems { items }
+    }
+
+    /// Returns a slice of associated items in the order they were defined.
+    ///
+    /// New code should avoid relying on definition order. If you need a particular associated item
+    /// for a known trait, make that trait a lang item instead of indexing this array.
+    pub fn in_definition_order(&self) -> impl '_ + Iterator<Item = &ty::AssocItem> {
+        self.items.iter().map(|(_, v)| v)
+    }
+
+    /// Returns an iterator over all associated items with the given name, ignoring hygiene.
+    pub fn filter_by_name_unhygienic(
+        &self,
+        name: Symbol,
+    ) -> impl '_ + Iterator<Item = &ty::AssocItem> {
+        self.items.get_by_key(&name)
+    }
+
+    /// Returns an iterator over all associated items with the given name.
+    ///
+    /// Multiple items may have the same name if they are in different `Namespace`s. For example,
+    /// an associated type can have the same name as a method. Use one of the `find_by_name_and_*`
+    /// methods below if you know which item you are looking for.
+    pub fn filter_by_name(
+        &'a self,
+        tcx: TyCtxt<'a>,
+        ident: Ident,
+        parent_def_id: DefId,
+    ) -> impl 'a + Iterator<Item = &'a ty::AssocItem> {
+        self.filter_by_name_unhygienic(ident.name)
+            .filter(move |item| tcx.hygienic_eq(ident, item.ident, parent_def_id))
+    }
+
+    /// Returns the associated item with the given name and `AssocKind`, if one exists.
+    pub fn find_by_name_and_kind(
+        &self,
+        tcx: TyCtxt<'_>,
+        ident: Ident,
+        kind: AssocKind,
+        parent_def_id: DefId,
+    ) -> Option<&ty::AssocItem> {
+        self.filter_by_name_unhygienic(ident.name)
+            .filter(|item| item.kind == kind)
+            .find(|item| tcx.hygienic_eq(ident, item.ident, parent_def_id))
+    }
+
+    /// Returns the associated item with the given name in the given `Namespace`, if one exists.
+    pub fn find_by_name_and_namespace(
+        &self,
+        tcx: TyCtxt<'_>,
+        ident: Ident,
+        ns: Namespace,
+        parent_def_id: DefId,
+    ) -> Option<&ty::AssocItem> {
+        self.filter_by_name_unhygienic(ident.name)
+            .filter(|item| item.kind.namespace() == ns)
+            .find(|item| tcx.hygienic_eq(ident, item.ident, parent_def_id))
+    }
+}
+
 #[derive(Clone, Debug, PartialEq, Eq, Copy, RustcEncodable, RustcDecodable, HashStable)]
 pub enum Visibility {
     /// Visible everywhere (including in other crates).
@@ -2738,14 +2814,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) -> impl Iterator<Item = &'tcx AssocItem> {
+    pub fn provided_trait_methods(self, id: DefId) -> impl 'tcx + Iterator<Item = &'tcx AssocItem> {
         self.associated_items(id)
-            .iter()
+            .in_definition_order()
             .filter(|item| item.kind == AssocKind::Method && item.defaultness.has_value())
     }
 
     pub fn trait_relevant_for_never(self, did: DefId) -> bool {
-        self.associated_items(did).iter().any(|item| item.relevant_for_never())
+        self.associated_items(did).in_definition_order().any(|item| item.relevant_for_never())
     }
 
     pub fn opt_item_name(self, def_id: DefId) -> Option<Ident> {
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index 9cf61ebe88a..c3698f402a9 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -1066,11 +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)
-            })
+            .find_by_name_and_kind(tcx, item_name, ty::AssocKind::Type, trait_ref.def_id)
             .unwrap()
             .def_id;
 
diff --git a/src/librustc/ty/util.rs b/src/librustc/ty/util.rs
index cb43f7475b8..eec6893d357 100644
--- a/src/librustc/ty/util.rs
+++ b/src/librustc/ty/util.rs
@@ -357,7 +357,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).first() {
+            if let Some(item) = self.associated_items(impl_did).in_definition_order().nth(0) {
                 if validate(self, impl_did).is_ok() {
                     dtor_did = Some(item.def_id);
                 }
diff --git a/src/librustc_infer/traits/mod.rs b/src/librustc_infer/traits/mod.rs
index 06c6d651813..b49f0062a9c 100644
--- a/src/librustc_infer/traits/mod.rs
+++ b/src/librustc_infer/traits/mod.rs
@@ -537,7 +537,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()
+            .in_definition_order()
             .filter(|item| item.kind == ty::AssocKind::Method);
 
         // Now list each method's DefId and InternalSubsts (for within its trait).
diff --git a/src/librustc_infer/traits/object_safety.rs b/src/librustc_infer/traits/object_safety.rs
index d36d66e4e25..93eeb42a594 100644
--- a/src/librustc_infer/traits/object_safety.rs
+++ b/src/librustc_infer/traits/object_safety.rs
@@ -213,7 +213,7 @@ fn object_safety_violations_for_trait(
     // Check methods for violations.
     let mut violations: Vec<_> = tcx
         .associated_items(trait_def_id)
-        .iter()
+        .in_definition_order()
         .filter(|item| item.kind == ty::AssocKind::Method)
         .filter_map(|item| {
             object_safety_violation_for_method(tcx, trait_def_id, &item)
@@ -289,7 +289,7 @@ fn object_safety_violations_for_trait(
 
     violations.extend(
         tcx.associated_items(trait_def_id)
-            .iter()
+            .in_definition_order()
             .filter(|item| item.kind == ty::AssocKind::Const)
             .map(|item| ObjectSafetyViolation::AssocConst(item.ident.name, item.ident.span)),
     );
@@ -646,7 +646,7 @@ 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())
-                .iter()
+                .in_definition_order()
                 .map(move |item| (super_trait_ref, item))
         })
         .filter(|(_, item)| item.kind == ty::AssocKind::Type)
diff --git a/src/librustc_infer/traits/util.rs b/src/librustc_infer/traits/util.rs
index c1612a3b9a7..1dca01b3468 100644
--- a/src/librustc_infer/traits/util.rs
+++ b/src/librustc_infer/traits/util.rs
@@ -586,7 +586,7 @@ pub fn count_own_vtable_entries(tcx: TyCtxt<'tcx>, trait_ref: ty::PolyTraitRef<'
     let mut entries = 0;
     // Count number of methods and add them to the total offset.
     // Skip over associated types and constants.
-    for trait_item in tcx.associated_items(trait_ref.def_id()) {
+    for trait_item in tcx.associated_items(trait_ref.def_id()).in_definition_order() {
         if trait_item.kind == ty::AssocKind::Method {
             entries += 1;
         }
@@ -606,7 +606,7 @@ pub fn get_vtable_index_of_object_method<N>(
     // add them to the total offset.
     // Skip over associated types and constants.
     let mut entries = object.vtable_base;
-    for trait_item in tcx.associated_items(object.upcast_trait_ref.def_id()) {
+    for trait_item in tcx.associated_items(object.upcast_trait_ref.def_id()).in_definition_order() {
         if trait_item.def_id == method_def_id {
             // The item with the ID we were given really ought to be a method.
             assert_eq!(trait_item.kind, ty::AssocKind::Method);
diff --git a/src/librustc_infer/traits/wf.rs b/src/librustc_infer/traits/wf.rs
index 89a271d0111..993eb41b9b1 100644
--- a/src/librustc_infer/traits/wf.rs
+++ b/src/librustc_infer/traits/wf.rs
@@ -318,7 +318,10 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
             };
 
         if let Elaborate::All = elaborate {
-            let trait_assoc_items = tcx.associated_items(trait_ref.def_id);
+            // FIXME: Make `extend_cause_with_original_assoc_item_obligation` take an iterator
+            // instead of a slice.
+            let trait_assoc_items: Vec<_> =
+                tcx.associated_items(trait_ref.def_id).in_definition_order().copied().collect();
 
             let predicates = obligations.iter().map(|obligation| obligation.predicate).collect();
             let implied_obligations = traits::elaborate_predicates(tcx, predicates);
@@ -327,7 +330,7 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
                 extend_cause_with_original_assoc_item_obligation(
                     &mut cause,
                     &pred,
-                    trait_assoc_items,
+                    &*trait_assoc_items,
                 );
                 traits::Obligation::new(cause, param_env, pred)
             });
diff --git a/src/librustc_mir/shim.rs b/src/librustc_mir/shim.rs
index bfd30ff5da5..1f7db2861a2 100644
--- a/src/librustc_mir/shim.rs
+++ b/src/librustc_mir/shim.rs
@@ -68,7 +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()
+                .in_definition_order()
                 .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 091ae1bbb79..fab64e37cbc 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)[0];
+        let drop_fn = tcx.associated_items(drop_trait).in_definition_order().nth(0).unwrap();
         let ty = self.place_ty(self.place);
         let substs = tcx.mk_substs_trait(ty, &[]);
 
diff --git a/src/librustc_mir_build/hair/cx/mod.rs b/src/librustc_mir_build/hair/cx/mod.rs
index ee62af7f851..f4f7ab4bba6 100644
--- a/src/librustc_mir_build/hair/cx/mod.rs
+++ b/src/librustc_mir_build/hair/cx/mod.rs
@@ -167,17 +167,19 @@ impl<'a, 'tcx> Cx<'a, 'tcx> {
         params: &[GenericArg<'tcx>],
     ) -> &'tcx ty::Const<'tcx> {
         let substs = self.tcx.mk_substs_trait(self_ty, params);
-        for item in self.tcx.associated_items(trait_def_id) {
-            // The unhygienic comparison here is acceptable because this is only
-            // used on known traits.
-            if item.kind == ty::AssocKind::Method && item.ident.name == method_name {
-                let method_ty = self.tcx.type_of(item.def_id);
-                let method_ty = method_ty.subst(self.tcx, substs);
-                return ty::Const::zero_sized(self.tcx, method_ty);
-            }
-        }
 
-        bug!("found no method `{}` in `{:?}`", method_name, trait_def_id);
+        // The unhygienic comparison here is acceptable because this is only
+        // used on known traits.
+        let item = self
+            .tcx
+            .associated_items(trait_def_id)
+            .filter_by_name_unhygienic(method_name)
+            .find(|item| item.kind == ty::AssocKind::Method)
+            .expect("trait method not found");
+
+        let method_ty = self.tcx.type_of(item.def_id);
+        let method_ty = method_ty.subst(self.tcx, substs);
+        ty::Const::zero_sized(self.tcx, method_ty)
     }
 
     crate fn all_fields(&mut self, adt_def: &ty::AdtDef, variant_index: VariantIdx) -> Vec<Field> {
diff --git a/src/librustc_passes/stability.rs b/src/librustc_passes/stability.rs
index 99f005c29e8..5c2abb1efa4 100644
--- a/src/librustc_passes/stability.rs
+++ b/src/librustc_passes/stability.rs
@@ -468,8 +468,8 @@ 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)
+                            .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.
diff --git a/src/librustc_save_analysis/lib.rs b/src/librustc_save_analysis/lib.rs
index 6a34e47130f..6e7ecf92441 100644
--- a/src/librustc_save_analysis/lib.rs
+++ b/src/librustc_save_analysis/lib.rs
@@ -408,7 +408,6 @@ impl<'l, 'tcx> SaveContext<'l, 'tcx> {
                         qualname.push_str(&self.tcx.hir().hir_to_pretty_string(self_ty.hir_id));
 
                         let trait_id = self.tcx.trait_id_of_impl(impl_id);
-                        let mut decl_id = None;
                         let mut docs = String::new();
                         let mut attrs = vec![];
                         let hir_id = self.tcx.hir().node_to_hir_id(id);
@@ -417,15 +416,18 @@ impl<'l, 'tcx> SaveContext<'l, 'tcx> {
                             attrs = item.attrs.to_vec();
                         }
 
+                        let mut decl_id = None;
                         if let Some(def_id) = trait_id {
                             // A method in a trait impl.
                             qualname.push_str(" as ");
                             qualname.push_str(&self.tcx.def_path_str(def_id));
-                            self.tcx
+
+                            decl_id = self
+                                .tcx
                                 .associated_items(def_id)
-                                .iter()
-                                .find(|item| item.ident.name == ident.name)
-                                .map(|item| decl_id = Some(item.def_id));
+                                .filter_by_name_unhygienic(ident.name)
+                                .next()
+                                .map(|item| item.def_id);
                         }
                         qualname.push_str(">");
 
@@ -716,12 +718,11 @@ impl<'l, 'tcx> SaveContext<'l, 'tcx> {
             Res::Def(HirDefKind::Method, 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())
-                        .iter()
-                        .find(|item| {
-                            item.ident.name == ti.ident.name && item.defaultness.has_value()
-                        })
+                        .filter_by_name_unhygienic(ti.ident.name)
+                        .find(|item| item.defaultness.has_value())
                         .map(|item| item.def_id)
                 } else {
                     None
diff --git a/src/librustc_ty/ty.rs b/src/librustc_ty/ty.rs
index f9b2ee3cb8e..916a819090c 100644
--- a/src/librustc_ty/ty.rs
+++ b/src/librustc_ty/ty.rs
@@ -210,10 +210,10 @@ fn associated_item_def_ids(tcx: TyCtxt<'_>, def_id: DefId) -> &[DefId] {
     }
 }
 
-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 associated_items<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> &'tcx ty::AssociatedItems {
+    let items =
+        tcx.associated_item_def_ids(def_id).iter().map(|did| tcx.associated_item(*did)).collect();
+    tcx.arena.alloc(ty::AssociatedItems::new(items))
 }
 
 fn def_span(tcx: TyCtxt<'_>, def_id: DefId) -> Span {
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index 635c3038e0a..572d3f3264f 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -1108,10 +1108,10 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         trait_def_id: DefId,
         assoc_name: ast::Ident,
     ) -> bool {
-        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)
-        })
+        self.tcx()
+            .associated_items(trait_def_id)
+            .find_by_name_and_kind(self.tcx(), assoc_name, ty::AssocKind::Type, trait_def_id)
+            .is_some()
     }
 
     // Returns `true` if a bounds list includes `?Sized`.
@@ -1344,9 +1344,11 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
 
         let (assoc_ident, def_scope) =
             tcx.adjust_ident_and_get_scope(binding.item_name, candidate.def_id(), hir_ref_id);
+
+        // FIXME(ecstaticmorse): Can this use `find_by_name_and_kind` instead?
         let assoc_ty = tcx
             .associated_items(candidate.def_id())
-            .iter()
+            .filter_by_name_unhygienic(assoc_ident.name)
             .find(|i| i.kind == ty::AssocKind::Type && i.ident.modern() == assoc_ident)
             .expect("missing associated type");
 
@@ -1512,7 +1514,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()
+                                .in_definition_order()
                                 .filter(|item| item.kind == ty::AssocKind::Type)
                                 .map(|item| item.def_id),
                         );
@@ -1967,14 +1969,11 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
 
             let mut where_bounds = vec![];
             for bound in bounds {
+                let bound_id = bound.def_id();
                 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())
-                    })
+                    .associated_items(bound_id)
+                    .find_by_name_and_kind(self.tcx(), assoc_name, ty::AssocKind::Type, bound_id)
                     .and_then(|item| self.tcx().hir().span_if_local(item.def_id));
 
                 if let Some(bound_span) = bound_span {
@@ -2052,7 +2051,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         );
 
         let all_candidate_names: Vec<_> = all_candidates()
-            .map(|r| self.tcx().associated_items(r.def_id()))
+            .map(|r| self.tcx().associated_items(r.def_id()).in_definition_order())
             .flatten()
             .filter_map(
                 |item| if item.kind == ty::AssocKind::Type { Some(item.ident.name) } else { None },
@@ -2198,9 +2197,11 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         let trait_did = bound.def_id();
         let (assoc_ident, def_scope) =
             tcx.adjust_ident_and_get_scope(assoc_ident, trait_did, hir_ref_id);
+
+        // FIXME(ecstaticmorse): Can this use `find_by_name_and_namespace` instead?
         let item = tcx
             .associated_items(trait_did)
-            .iter()
+            .in_definition_order()
             .find(|i| i.kind.namespace() == Namespace::TypeNS && 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 e17c65faf1f..816de5dadbc 100644
--- a/src/librustc_typeck/check/closure.rs
+++ b/src/librustc_typeck/check/closure.rs
@@ -248,7 +248,8 @@ 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)[1].def_id;
+            let return_assoc_item =
+                self.tcx.associated_items(gen_trait).in_definition_order().nth(1).unwrap().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 +674,8 @@ 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)[0].def_id;
+        let output_assoc_item =
+            self.tcx.associated_items(future_trait).in_definition_order().nth(0).unwrap().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 bf74ab696d6..63ebf612964 100644
--- a/src/librustc_typeck/check/demand.rs
+++ b/src/librustc_typeck/check/demand.rs
@@ -539,7 +539,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                 let item_def_id = self
                     .tcx
                     .associated_items(deref_trait)
-                    .iter()
+                    .in_definition_order()
                     .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 84e00244942..de824648a25 100644
--- a/src/librustc_typeck/check/method/mod.rs
+++ b/src/librustc_typeck/check/method/mod.rs
@@ -483,11 +483,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
     ) -> Option<ty::AssocItem> {
         self.tcx
             .associated_items(def_id)
-            .iter()
-            .find(|item| {
-                Namespace::from(item.kind) == ns
-                    && self.tcx.hygienic_eq(item_name, item.ident, def_id)
-            })
+            .find_by_name_and_namespace(self.tcx, item_name, ns, def_id)
             .copied()
     }
 }
diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs
index 5ed39f04b07..ea90aef4868 100644
--- a/src/librustc_typeck/check/method/probe.rs
+++ b/src/librustc_typeck/check/method/probe.rs
@@ -1696,7 +1696,7 @@ impl<'a, 'tcx> ProbeContext<'a, 'tcx> {
                 let max_dist = max(name.as_str().len(), 3) / 3;
                 self.tcx
                     .associated_items(def_id)
-                    .iter()
+                    .in_definition_order()
                     .filter(|x| {
                         let dist = lev_distance(&*name.as_str(), &x.ident.as_str());
                         x.kind.namespace() == Namespace::ValueNS && dist > 0 && dist <= max_dist
@@ -1709,7 +1709,7 @@ impl<'a, 'tcx> ProbeContext<'a, 'tcx> {
                     .map_or(Vec::new(), |x| vec![x])
             }
         } else {
-            self.tcx.associated_items(def_id).to_vec()
+            self.tcx.associated_items(def_id).in_definition_order().copied().collect()
         }
     }
 }
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index d6acd8dd894..2f6d8b644c0 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -1975,16 +1975,12 @@ 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)
-            })
+            .find_by_name_and_namespace(tcx, ty_impl_item.ident, namespace, impl_trait_ref.def_id)
             .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))
+                    .filter_by_name(tcx, ty_impl_item.ident, impl_trait_ref.def_id)
+                    .next()
             });
 
         // Check that impl definition matches trait definition
@@ -2088,7 +2084,7 @@ fn check_impl_items_against_trait<'tcx>(
     let mut missing_items = Vec::new();
     let mut invalidated_items = Vec::new();
     let associated_type_overridden = overridden_associated_type.is_some();
-    for trait_item in tcx.associated_items(impl_trait_ref.def_id) {
+    for trait_item in tcx.associated_items(impl_trait_ref.def_id).in_definition_order() {
         let is_implemented = trait_def
             .ancestors(tcx, impl_id)
             .leaf_def(tcx, trait_item.ident, trait_item.kind)
@@ -5224,7 +5220,13 @@ 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)[0].def_id;
+                let item_def_id = self
+                    .tcx
+                    .associated_items(future_trait)
+                    .in_definition_order()
+                    .nth(0)
+                    .unwrap()
+                    .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 ad0e462afc7..fcded27463e 100644
--- a/src/librustc_typeck/coherence/inherent_impls_overlap.rs
+++ b/src/librustc_typeck/coherence/inherent_impls_overlap.rs
@@ -1,4 +1,4 @@
-use rustc::ty::{AssocItem, TyCtxt};
+use rustc::ty::TyCtxt;
 use rustc_errors::struct_span_err;
 use rustc_hir as hir;
 use rustc_hir::def_id::{CrateNum, DefId, LOCAL_CRATE};
@@ -22,18 +22,18 @@ impl InherentOverlapChecker<'tcx> {
         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)
-                {
+        for item1 in impl_items1.in_definition_order() {
+            let collision = impl_items2
+                .filter_by_name_unhygienic(item1.ident.name)
+                .find(|item2| {
                     // Symbols and namespace match, compare hygienically.
-                    if item1.ident.modern() == item2.ident.modern() {
-                        return true;
-                    }
-                }
+                    item1.kind.namespace() == item2.kind.namespace()
+                        && item1.ident.modern() == item2.ident.modern()
+                })
+                .is_some();
+
+            if collision {
+                return true;
             }
         }
 
@@ -46,43 +46,43 @@ impl InherentOverlapChecker<'tcx> {
         impl2: DefId,
         overlap: traits::OverlapResult<'_>,
     ) {
-        let name_and_namespace =
-            |assoc: &AssocItem| (assoc.ident.modern(), Namespace::from(assoc.kind));
-
         let impl_items1 = self.tcx.associated_items(impl1);
         let impl_items2 = self.tcx.associated_items(impl2);
 
-        for item1 in &impl_items1[..] {
-            let (name, namespace) = name_and_namespace(item1);
-
-            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.def_id).unwrap(),
-                        E0592,
-                        "duplicate definitions with name `{}`",
-                        name
-                    );
-                    err.span_label(
-                        self.tcx.span_of_impl(item1.def_id).unwrap(),
-                        format!("duplicate definitions for `{}`", name),
-                    );
-                    err.span_label(
-                        self.tcx.span_of_impl(item2.def_id).unwrap(),
-                        format!("other definition for `{}`", name),
-                    );
-
-                    for cause in &overlap.intercrate_ambiguity_causes {
-                        cause.add_intercrate_ambiguity_hint(&mut err);
-                    }
-
-                    if overlap.involves_placeholder {
-                        traits::add_placeholder_note(&mut err);
-                    }
+        for item1 in impl_items1.in_definition_order() {
+            let collision = impl_items2.filter_by_name_unhygienic(item1.ident.name).find(|item2| {
+                // Symbols and namespace match, compare hygienically.
+                item1.kind.namespace() == item2.kind.namespace()
+                    && item1.ident.modern() == item2.ident.modern()
+            });
+
+            if let Some(item2) = collision {
+                let name = item1.ident.modern();
+                let mut err = struct_span_err!(
+                    self.tcx.sess,
+                    self.tcx.span_of_impl(item1.def_id).unwrap(),
+                    E0592,
+                    "duplicate definitions with name `{}`",
+                    name
+                );
+                err.span_label(
+                    self.tcx.span_of_impl(item1.def_id).unwrap(),
+                    format!("duplicate definitions for `{}`", name),
+                );
+                err.span_label(
+                    self.tcx.span_of_impl(item2.def_id).unwrap(),
+                    format!("other definition for `{}`", name),
+                );
+
+                for cause in &overlap.intercrate_ambiguity_causes {
+                    cause.add_intercrate_ambiguity_hint(&mut err);
+                }
 
-                    err.emit();
+                if overlap.involves_placeholder {
+                    traits::add_placeholder_note(&mut err);
                 }
+
+                err.emit();
             }
         }
     }
diff --git a/src/librustdoc/clean/blanket_impl.rs b/src/librustdoc/clean/blanket_impl.rs
index f7968bf7722..4a1e2570d06 100644
--- a/src/librustdoc/clean/blanket_impl.rs
+++ b/src/librustdoc/clean/blanket_impl.rs
@@ -114,8 +114,7 @@ impl<'a, 'tcx> BlanketImplFinder<'a, 'tcx> {
                             .cx
                             .tcx
                             .associated_items(impl_def_id)
-                            .iter()
-                            .copied()
+                            .in_definition_order()
                             .collect::<Vec<_>>()
                             .clean(self.cx),
                         polarity: None,
diff --git a/src/librustdoc/clean/inline.rs b/src/librustdoc/clean/inline.rs
index 90ce8802f65..78222d21b93 100644
--- a/src/librustdoc/clean/inline.rs
+++ b/src/librustdoc/clean/inline.rs
@@ -190,8 +190,10 @@ pub fn record_extern_fqn(cx: &DocContext<'_>, did: DefId, kind: clean::TypeKind)
 }
 
 pub fn build_external_trait(cx: &DocContext<'_>, did: DefId) -> clean::Trait {
+    let trait_items =
+        cx.tcx.associated_items(did).in_definition_order().map(|item| item.clean(cx)).collect();
+
     let auto_trait = cx.tcx.trait_def(did).has_auto_impl;
-    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,7 +378,7 @@ pub fn build_impl(
     } else {
         (
             tcx.associated_items(did)
-                .iter()
+                .in_definition_order()
                 .filter_map(|item| {
                     if associated_trait.is_some() || item.vis == ty::Visibility::Public {
                         Some(item.clean(cx))
diff --git a/src/librustdoc/passes/collect_intra_doc_links.rs b/src/librustdoc/passes/collect_intra_doc_links.rs
index 79bcfe7aee7..0b27e5cf806 100644
--- a/src/librustdoc/passes/collect_intra_doc_links.rs
+++ b/src/librustdoc/passes/collect_intra_doc_links.rs
@@ -95,7 +95,7 @@ impl<'a, 'tcx> LinkCollector<'a, 'tcx> {
                     .tcx
                     .inherent_impls(did)
                     .iter()
-                    .flat_map(|imp| cx.tcx.associated_items(*imp))
+                    .flat_map(|imp| cx.tcx.associated_items(*imp).in_definition_order())
                     .any(|item| item.ident.name == variant_name)
                 {
                     return Err(ErrorKind::ResolutionFailure);
@@ -206,8 +206,8 @@ impl<'a, 'tcx> LinkCollector<'a, 'tcx> {
                 return cx
                     .tcx
                     .associated_items(did)
-                    .iter()
-                    .find(|item| item.ident.name == item_name)
+                    .filter_by_name_unhygienic(item_name)
+                    .next()
                     .and_then(|item| match item.kind {
                         ty::AssocKind::Method => Some("method"),
                         _ => None,
@@ -234,7 +234,7 @@ impl<'a, 'tcx> LinkCollector<'a, 'tcx> {
                         .tcx
                         .inherent_impls(did)
                         .iter()
-                        .flat_map(|imp| cx.tcx.associated_items(*imp))
+                        .flat_map(|imp| cx.tcx.associated_items(*imp).in_definition_order())
                         .find(|item| item.ident.name == item_name);
                     if let Some(item) = item {
                         let out = match item.kind {