Use hash-tables in trait selection

Puts implementations in bins hashed by the fast-reject key, and
only looks up the relevant impls, reducing O(n^2)-ishness

Before: 688.92user 5.08system 8:56.70elapsed 129%CPU (0avgtext+0avgdata 1208164maxresident)k, LLVM 379.142s
After: 637.78user 5.11system 8:17.48elapsed 129%CPU (0avgtext+0avgdata 1201448maxresident)k LLVM 375.552s

Performance increase is +7%-ish

10 files changed, 284 insertions, 191 deletions

diff --git a/src/librustc/metadata/decoder.rs b/src/librustc/metadata/decoder.rs
index 467919bcaca..00fc42341c3 100644
--- a/src/librustc/metadata/decoder.rs
+++ b/src/librustc/metadata/decoder.rs
@@ -30,7 +30,9 @@ use middle::subst;
 use middle::ty::{ImplContainer, TraitContainer};
 use middle::ty::{self, Ty};
 use middle::astencode::vtable_decoder_helpers;
+use util::nodemap::FnvHashMap;
 
+use std::cell::{Cell, RefCell};
 use std::collections::HashMap;
 use std::hash::{self, Hash, SipHasher};
 use std::io::prelude::*;
@@ -420,6 +422,9 @@ pub fn get_trait_def<'tcx>(cdata: Cmd,
         generics: generics,
         trait_ref: item_trait_ref(item_doc, tcx, cdata),
         associated_type_names: associated_type_names,
+        nonblanket_impls: RefCell::new(FnvHashMap()),
+        blanket_impls: RefCell::new(vec![]),
+        flags: Cell::new(ty::TraitFlags::NO_TRAIT_FLAGS)
     }
 }
 
diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index 4862497b325..90dd452e06b 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -974,16 +974,14 @@ fn encode_inherent_implementations(ecx: &EncodeContext,
 fn encode_extension_implementations(ecx: &EncodeContext,
                                     rbml_w: &mut Encoder,
                                     trait_def_id: DefId) {
-    match ecx.tcx.trait_impls.borrow().get(&trait_def_id) {
-        None => {}
-        Some(implementations) => {
-            for &impl_def_id in &*implementations.borrow() {
-                rbml_w.start_tag(tag_items_data_item_extension_impl);
-                encode_def_id(rbml_w, impl_def_id);
-                rbml_w.end_tag();
-            }
-        }
-    }
+    assert!(ast_util::is_local(trait_def_id));
+    let def = ty::lookup_trait_def(ecx.tcx, trait_def_id);
+
+    def.for_each_impl(ecx.tcx, |impl_def_id| {
+        rbml_w.start_tag(tag_items_data_item_extension_impl);
+        encode_def_id(rbml_w, impl_def_id);
+        rbml_w.end_tag();
+    });
 }
 
 fn encode_stability(rbml_w: &mut Encoder, stab_opt: Option<attr::Stability>) {
diff --git a/src/librustc/middle/traits/object_safety.rs b/src/librustc/middle/traits/object_safety.rs
index 3d6ed3c3440..ac3c9dfbb46 100644
--- a/src/librustc/middle/traits/object_safety.rs
+++ b/src/librustc/middle/traits/object_safety.rs
@@ -57,20 +57,18 @@ pub fn is_object_safe<'tcx>(tcx: &ty::ctxt<'tcx>,
                             -> bool
 {
     // Because we query yes/no results frequently, we keep a cache:
-    let cached_result =
-        tcx.object_safety_cache.borrow().get(&trait_def_id).cloned();
+    let def = ty::lookup_trait_def(tcx, trait_def_id);
 
-    let result =
-        cached_result.unwrap_or_else(|| {
-            let result = object_safety_violations(tcx, trait_def_id).is_empty();
+    let result = def.object_safety().unwrap_or_else(|| {
+        let result = object_safety_violations(tcx, trait_def_id).is_empty();
 
-            // Record just a yes/no result in the cache; this is what is
-            // queried most frequently. Note that this may overwrite a
-            // previous result, but always with the same thing.
-            tcx.object_safety_cache.borrow_mut().insert(trait_def_id, result);
+        // Record just a yes/no result in the cache; this is what is
+        // queried most frequently. Note that this may overwrite a
+        // previous result, but always with the same thing.
+        def.set_object_safety(result);
 
-            result
-        });
+        result
+    });
 
     debug!("is_object_safe({}) = {}", trait_def_id.repr(tcx), result);
 
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index f0390a6f5f0..2be1096ae30 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -1153,18 +1153,19 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     {
         debug!("assemble_candidates_from_impls(obligation={})", obligation.repr(self.tcx()));
 
-        let def_id = obligation.predicate.def_id();
-        let all_impls = self.all_impls(def_id);
-        for &impl_def_id in &all_impls {
-            self.infcx.probe(|snapshot| {
-                match self.match_impl(impl_def_id, obligation, snapshot) {
-                    Ok(_) => {
+        let def = ty::lookup_trait_def(self.tcx(), obligation.predicate.def_id());
+
+        def.for_each_relevant_impl(
+            self.tcx(),
+            obligation.predicate.0.trait_ref,
+            |impl_def_id| {
+                self.infcx.probe(|snapshot| {
+                    if let Ok(_) = self.match_impl(impl_def_id, obligation, snapshot) {
                         candidates.vec.push(ImplCandidate(impl_def_id));
                     }
-                    Err(()) => { }
-                }
-            });
-        }
+                });
+            }
+        );
 
         Ok(())
     }
@@ -2529,16 +2530,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         }
     }
 
-    /// Returns set of all impls for a given trait.
-    fn all_impls(&self, trait_def_id: ast::DefId) -> Vec<ast::DefId> {
-        ty::populate_implementations_for_trait_if_necessary(self.tcx(), trait_def_id);
-
-        match self.tcx().trait_impls.borrow().get(&trait_def_id) {
-            None => Vec::new(),
-            Some(impls) => impls.borrow().clone(),
-        }
-    }
-
     fn closure_trait_ref(&self,
                          obligation: &TraitObligation<'tcx>,
                          closure_def_id: ast::DefId,
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index f38bd40456b..f9ec39113b6 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -45,6 +45,7 @@ use middle::check_const;
 use middle::const_eval;
 use middle::def::{self, DefMap, ExportMap};
 use middle::dependency_format;
+use middle::fast_reject;
 use middle::free_region::FreeRegionMap;
 use middle::lang_items::{FnTraitLangItem, FnMutTraitLangItem, FnOnceTraitLangItem};
 use middle::mem_categorization as mc;
@@ -737,12 +738,6 @@ pub struct ctxt<'tcx> {
     /// A method will be in this list if and only if it is a destructor.
     pub destructors: RefCell<DefIdSet>,
 
-    /// Maps a trait onto a list of impls of that trait.
-    pub trait_impls: RefCell<DefIdMap<Rc<RefCell<Vec<ast::DefId>>>>>,
-
-    /// A set of traits that have a default impl
-    traits_with_default_impls: RefCell<DefIdMap<()>>,
-
     /// Maps a DefId of a type to a list of its inherent impls.
     /// Contains implementations of methods that are inherent to a type.
     /// Methods in these implementations don't need to be exported.
@@ -766,12 +761,8 @@ pub struct ctxt<'tcx> {
     /// The set of external nominal types whose implementations have been read.
     /// This is used for lazy resolution of methods.
     pub populated_external_types: RefCell<DefIdSet>,
-
-    /// The set of external traits whose implementations have been read. This
-    /// is used for lazy resolution of traits.
-    pub populated_external_traits: RefCell<DefIdSet>,
-
-    /// The set of external primitive inherent implementations that have been read.
+    /// The set of external primitive types whose implementations have been read.
+    /// FIXME(arielb1): why is this separate from populated_external_types?
     pub populated_external_primitive_impls: RefCell<DefIdSet>,
 
     /// Borrows
@@ -825,9 +816,6 @@ pub struct ctxt<'tcx> {
     /// results are dependent on the parameter environment.
     pub type_impls_sized_cache: RefCell<HashMap<Ty<'tcx>,bool>>,
 
-    /// Caches whether traits are object safe
-    pub object_safety_cache: RefCell<DefIdMap<bool>>,
-
     /// Maps Expr NodeId's to their constant qualification.
     pub const_qualif_map: RefCell<NodeMap<check_const::ConstQualif>>,
 }
@@ -966,6 +954,7 @@ impl fmt::Debug for TypeFlags {
 }
 
 impl<'tcx> PartialEq for TyS<'tcx> {
+    #[inline]
     fn eq(&self, other: &TyS<'tcx>) -> bool {
         // (self as *const _) == (other as *const _)
         (self as *const TyS<'tcx>) == (other as *const TyS<'tcx>)
@@ -2500,6 +2489,16 @@ pub struct TypeScheme<'tcx> {
     pub ty: Ty<'tcx>,
 }
 
+bitflags! {
+    flags TraitFlags: u32 {
+        const NO_TRAIT_FLAGS        = 0,
+        const HAS_DEFAULT_IMPL      = 1 << 0,
+        const IS_OBJECT_SAFE        = 1 << 1,
+        const OBJECT_SAFETY_VALID   = 1 << 2,
+        const IMPLS_VALID           = 1 << 3,
+    }
+}
+
 /// As `TypeScheme` but for a trait ref.
 pub struct TraitDef<'tcx> {
     pub unsafety: ast::Unsafety,
@@ -2522,6 +2521,103 @@ pub struct TraitDef<'tcx> {
     /// A list of the associated types defined in this trait. Useful
     /// for resolving `X::Foo` type markers.
     pub associated_type_names: Vec<ast::Name>,
+
+    /// Impls of the trait.
+    pub nonblanket_impls: RefCell<
+        FnvHashMap<fast_reject::SimplifiedType, Vec<DefId>>
+    >,
+
+    /// Blanket impls associated with the trait.
+    pub blanket_impls: RefCell<Vec<DefId>>,
+
+    pub flags: Cell<TraitFlags>
+}
+
+impl<'tcx> TraitDef<'tcx> {
+    // returns None if not yet calculated
+    pub fn object_safety(&self) -> Option<bool> {
+        if self.flags.get().intersects(TraitFlags::OBJECT_SAFETY_VALID) {
+            Some(self.flags.get().intersects(TraitFlags::IS_OBJECT_SAFE))
+        } else {
+            None
+        }
+    }
+
+    pub fn set_object_safety(&self, is_safe: bool) {
+        self.flags.set(
+            self.flags.get() | if is_safe {
+                TraitFlags::OBJECT_SAFETY_VALID | TraitFlags::IS_OBJECT_SAFE
+            } else {
+                TraitFlags::OBJECT_SAFETY_VALID
+            }
+        );
+    }
+
+    /// Records a trait-to-implementation mapping.
+    pub fn record_impl(&self,
+                       tcx: &ctxt<'tcx>,
+                       impl_def_id: DefId,
+                       impl_trait_ref: TraitRef<'tcx>) {
+        // We don't want to borrow_mut after we already populated all impls,
+        // so check if an impl is present with an immutable borrow first.
+
+        if let Some(sty) = fast_reject::simplify_type(tcx,
+                                                      impl_trait_ref.self_ty(), false) {
+            if !self.nonblanket_impls.borrow().get(&sty).map(
+                    |s| s.contains(&impl_def_id)).unwrap_or(false) {
+                self.nonblanket_impls.borrow_mut().entry(sty).or_insert(vec![]).push(impl_def_id)
+            }
+        } else {
+            if !self.blanket_impls.borrow().contains(&impl_def_id) {
+                self.blanket_impls.borrow_mut().push(impl_def_id)
+            }
+        }
+    }
+
+
+    pub fn for_each_impl<F: FnMut(DefId)>(&self, tcx: &ctxt<'tcx>, mut f: F)  {
+        ty::populate_implementations_for_trait_if_necessary(tcx, self.trait_ref.def_id);
+
+        for &impl_def_id in self.blanket_impls.borrow().iter() {
+            f(impl_def_id);
+        }
+
+        for v in self.nonblanket_impls.borrow().values() {
+            for &impl_def_id in v {
+                f(impl_def_id);
+            }
+        }
+    }
+
+    pub fn for_each_relevant_impl<F: FnMut(DefId)>(&self,
+                                                   tcx: &ctxt<'tcx>,
+                                                   trait_ref: TraitRef<'tcx>,
+                                                   mut f: F)
+    {
+        ty::populate_implementations_for_trait_if_necessary(tcx, self.trait_ref.def_id);
+
+        for &impl_def_id in self.blanket_impls.borrow().iter() {
+            f(impl_def_id);
+        }
+
+        if let Some(self_ty) = trait_ref.substs.self_ty() {
+            if let Some(simp) = fast_reject::simplify_type(tcx, self_ty, false) {
+                if let Some(impls) = self.nonblanket_impls.borrow().get(&simp) {
+                    for &impl_def_id in impls {
+                        f(impl_def_id);
+                    }
+                }
+                return; // don't process all non-blanket impls
+            }
+        }
+
+        for v in self.nonblanket_impls.borrow().values() {
+            for &impl_def_id in v {
+                f(impl_def_id);
+            }
+        }
+    }
+
 }
 
 /// Records the substitutions used to translate the polytype for an
@@ -2681,14 +2777,11 @@ pub fn mk_ctxt<'tcx>(s: Session,
         struct_fields: RefCell::new(DefIdMap()),
         destructor_for_type: RefCell::new(DefIdMap()),
         destructors: RefCell::new(DefIdSet()),
-        trait_impls: RefCell::new(DefIdMap()),
-        traits_with_default_impls: RefCell::new(DefIdMap()),
         inherent_impls: RefCell::new(DefIdMap()),
         impl_items: RefCell::new(DefIdMap()),
         used_unsafe: RefCell::new(NodeSet()),
         used_mut_nodes: RefCell::new(NodeSet()),
         populated_external_types: RefCell::new(DefIdSet()),
-        populated_external_traits: RefCell::new(DefIdSet()),
         populated_external_primitive_impls: RefCell::new(DefIdSet()),
         upvar_capture_map: RefCell::new(FnvHashMap()),
         extern_const_statics: RefCell::new(DefIdMap()),
@@ -2705,7 +2798,6 @@ pub fn mk_ctxt<'tcx>(s: Session,
         repr_hint_cache: RefCell::new(DefIdMap()),
         type_impls_copy_cache: RefCell::new(HashMap::new()),
         type_impls_sized_cache: RefCell::new(HashMap::new()),
-        object_safety_cache: RefCell::new(DefIdMap()),
         const_qualif_map: RefCell::new(NodeMap()),
    }
 }
@@ -6223,50 +6315,36 @@ pub fn item_variances(tcx: &ctxt, item_id: ast::DefId) -> Rc<ItemVariances> {
 
 pub fn trait_has_default_impl(tcx: &ctxt, trait_def_id: DefId) -> bool {
     populate_implementations_for_trait_if_necessary(tcx, trait_def_id);
-    tcx.traits_with_default_impls.borrow().contains_key(&trait_def_id)
-}
 
-/// Records a trait-to-implementation mapping.
-pub fn record_trait_has_default_impl(tcx: &ctxt, trait_def_id: DefId) {
-    // We're using the latest implementation found as the reference one.
-    // Duplicated implementations are caught and reported in the coherence
-    // step.
-    tcx.traits_with_default_impls.borrow_mut().insert(trait_def_id, ());
+    let def = lookup_trait_def(tcx, trait_def_id);
+    def.flags.get().intersects(TraitFlags::HAS_DEFAULT_IMPL)
 }
 
 /// Records a trait-to-implementation mapping.
-pub fn record_trait_implementation(tcx: &ctxt,
-                                   trait_def_id: DefId,
-                                   impl_def_id: DefId) {
-
-    match tcx.trait_impls.borrow().get(&trait_def_id) {
-        Some(impls_for_trait) => {
-            impls_for_trait.borrow_mut().push(impl_def_id);
-            return;
-        }
-        None => {}
-    }
-
-    tcx.trait_impls.borrow_mut().insert(trait_def_id, Rc::new(RefCell::new(vec!(impl_def_id))));
+pub fn record_trait_has_default_impl(tcx: &ctxt, trait_def_id: DefId) {
+    let def = lookup_trait_def(tcx, trait_def_id);
+    def.flags.set(def.flags.get() | TraitFlags::HAS_DEFAULT_IMPL)
 }
 
 /// Load primitive inherent implementations if necessary
-pub fn populate_implementations_for_primitive_if_necessary(tcx: &ctxt, lang_def_id: ast::DefId) {
-    if lang_def_id.krate == LOCAL_CRATE {
+pub fn populate_implementations_for_primitive_if_necessary(tcx: &ctxt,
+                                                           primitive_def_id: ast::DefId) {
+    if primitive_def_id.krate == LOCAL_CRATE {
         return
     }
-    if tcx.populated_external_primitive_impls.borrow().contains(&lang_def_id) {
+
+    if tcx.populated_external_primitive_impls.borrow().contains(&primitive_def_id) {
         return
     }
 
-    debug!("populate_implementations_for_primitive_if_necessary: searching for {:?}", lang_def_id);
+    debug!("populate_implementations_for_primitive_if_necessary: searching for {:?}",
+           primitive_def_id);
 
-    let impl_items = csearch::get_impl_items(&tcx.sess.cstore, lang_def_id);
+    let impl_items = csearch::get_impl_items(&tcx.sess.cstore, primitive_def_id);
 
     // Store the implementation info.
-    tcx.impl_items.borrow_mut().insert(lang_def_id, impl_items);
-
-    tcx.populated_external_primitive_impls.borrow_mut().insert(lang_def_id);
+    tcx.impl_items.borrow_mut().insert(primitive_def_id, impl_items);
+    tcx.populated_external_primitive_impls.borrow_mut().insert(primitive_def_id);
 }
 
 /// Populates the type context with all the implementations for the given type
@@ -6276,6 +6354,7 @@ pub fn populate_implementations_for_type_if_necessary(tcx: &ctxt,
     if type_id.krate == LOCAL_CRATE {
         return
     }
+
     if tcx.populated_external_types.borrow().contains(&type_id) {
         return
     }
@@ -6286,10 +6365,12 @@ pub fn populate_implementations_for_type_if_necessary(tcx: &ctxt,
     csearch::each_implementation_for_type(&tcx.sess.cstore, type_id, |impl_def_id| {
         let impl_items = csearch::get_impl_items(&tcx.sess.cstore, impl_def_id);
 
-        // Record the trait->implementation mappings, if applicable.
-        let associated_traits = csearch::get_impl_trait(tcx, impl_def_id);
-        if let Some(ref trait_ref) = associated_traits {
-            record_trait_implementation(tcx, trait_ref.def_id, impl_def_id);
+        // Record the implementation, if needed
+        if let Some(trait_ref) = csearch::get_impl_trait(tcx, impl_def_id) {
+            let trait_def = lookup_trait_def(tcx, trait_ref.def_id);
+            trait_def.record_impl(tcx, impl_def_id, trait_ref);
+        } else {
+            inherent_impls.push(impl_def_id);
         }
 
         // For any methods that use a default implementation, add them to
@@ -6310,11 +6391,6 @@ pub fn populate_implementations_for_type_if_necessary(tcx: &ctxt,
 
         // Store the implementation info.
         tcx.impl_items.borrow_mut().insert(impl_def_id, impl_items);
-
-        // If this is an inherent implementation, record it.
-        if associated_traits.is_none() {
-            inherent_impls.push(impl_def_id);
-        }
     });
 
     tcx.inherent_impls.borrow_mut().insert(type_id, Rc::new(inherent_impls));
@@ -6330,7 +6406,8 @@ pub fn populate_implementations_for_trait_if_necessary(
         return
     }
 
-    if tcx.populated_external_traits.borrow().contains(&trait_id) {
+    let def = lookup_trait_def(tcx, trait_id);
+    if def.flags.get().intersects(TraitFlags::IMPLS_VALID) {
         return
     }
 
@@ -6340,9 +6417,9 @@ pub fn populate_implementations_for_trait_if_necessary(
 
     csearch::each_implementation_for_trait(&tcx.sess.cstore, trait_id, |implementation_def_id| {
         let impl_items = csearch::get_impl_items(&tcx.sess.cstore, implementation_def_id);
-
+        let trait_ref = impl_trait_ref(tcx, implementation_def_id).unwrap();
         // Record the trait->implementation mapping.
-        record_trait_implementation(tcx, trait_id, implementation_def_id);
+        def.record_impl(tcx, implementation_def_id, trait_ref);
 
         // For any methods that use a default implementation, add them to
         // the map. This is a bit unfortunate.
@@ -6364,7 +6441,7 @@ pub fn populate_implementations_for_trait_if_necessary(
         tcx.impl_items.borrow_mut().insert(implementation_def_id, impl_items);
     });
 
-    tcx.populated_external_traits.borrow_mut().insert(trait_id);
+    def.flags.set(def.flags.get() | TraitFlags::IMPLS_VALID);
 }
 
 /// Given the def_id of an impl, return the def_id of the trait it implements.
diff --git a/src/librustc_lint/builtin.rs b/src/librustc_lint/builtin.rs
index cc2c9b735ea..19e71d6e40d 100644
--- a/src/librustc_lint/builtin.rs
+++ b/src/librustc_lint/builtin.rs
@@ -1745,17 +1745,16 @@ impl LintPass for MissingDebugImplementations {
         };
 
         if self.impling_types.is_none() {
-            let impls = cx.tcx.trait_impls.borrow();
-            let impls = match impls.get(&debug) {
-                Some(impls) => {
-                    impls.borrow().iter()
-                         .filter(|d| d.krate == ast::LOCAL_CRATE)
-                         .filter_map(|d| ty::ty_to_def_id(ty::node_id_to_type(cx.tcx, d.node)))
-                         .map(|d| d.node)
-                         .collect()
+            let debug_def = ty::lookup_trait_def(cx.tcx, debug);
+            let mut impls = NodeSet();
+            debug_def.for_each_impl(cx.tcx, |d| {
+                if d.krate == ast::LOCAL_CRATE {
+                    if let Some(ty_def) = ty::ty_to_def_id(ty::node_id_to_type(cx.tcx, d.node)) {
+                        impls.insert(ty_def.node);
+                    }
                 }
-                None => NodeSet(),
-            };
+            });
+
             self.impling_types = Some(impls);
             debug!("{:?}", self.impling_types);
         }
diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs
index 2f6b57217ff..c94fa037026 100644
--- a/src/librustc_typeck/check/method/probe.rs
+++ b/src/librustc_typeck/check/method/probe.rs
@@ -624,23 +624,16 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
                                                      item: ty::ImplOrTraitItem<'tcx>,
                                                      item_index: usize)
     {
-        ty::populate_implementations_for_trait_if_necessary(self.tcx(),
-                                                            trait_def_id);
-
-        let trait_impls = self.tcx().trait_impls.borrow();
-        let impl_def_ids = trait_impls.get(&trait_def_id);
-        let impl_def_ids = match impl_def_ids {
-            None => { return; }
-            Some(impls) => impls,
-        };
+        let trait_def = ty::lookup_trait_def(self.tcx(), trait_def_id);
 
-        for &impl_def_id in &*impl_def_ids.borrow() {
+        // FIXME(arielb1): can we use for_each_relevant_impl here?
+        trait_def.for_each_impl(self.tcx(), |impl_def_id| {
             debug!("assemble_extension_candidates_for_trait_impl: trait_def_id={} impl_def_id={}",
                    trait_def_id.repr(self.tcx()),
                    impl_def_id.repr(self.tcx()));
 
             if !self.impl_can_possibly_match(impl_def_id) {
-                continue;
+                return;
             }
 
             let (_, impl_substs) = self.impl_ty_and_substs(impl_def_id);
@@ -667,7 +660,7 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
                 item: item.clone(),
                 kind: ExtensionImplCandidate(impl_def_id, impl_trait_ref, impl_substs, item_index)
             });
-        }
+        });
     }
 
     fn impl_can_possibly_match(&self, impl_def_id: ast::DefId) -> bool {
diff --git a/src/librustc_typeck/coherence/mod.rs b/src/librustc_typeck/coherence/mod.rs
index 7ba92feafcd..05b74a5cc22 100644
--- a/src/librustc_typeck/coherence/mod.rs
+++ b/src/librustc_typeck/coherence/mod.rs
@@ -163,7 +163,7 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
             enforce_trait_manually_implementable(self.crate_context.tcx,
                                                  item.span,
                                                  trait_ref.def_id);
-            self.add_trait_impl(trait_ref.def_id, impl_did);
+            self.add_trait_impl(trait_ref, impl_did);
         }
 
         // Add the implementation to the mapping from implementation to base
@@ -259,12 +259,12 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
             Rc::new(RefCell::new(vec!(impl_def_id))));
     }
 
-    fn add_trait_impl(&self, base_def_id: DefId, impl_def_id: DefId) {
-        debug!("add_trait_impl: base_def_id={:?} impl_def_id={:?}",
-               base_def_id, impl_def_id);
-        ty::record_trait_implementation(self.crate_context.tcx,
-                                        base_def_id,
-                                        impl_def_id);
+    fn add_trait_impl(&self, impl_trait_ref: ty::TraitRef<'tcx>, impl_def_id: DefId) {
+        debug!("add_trait_impl: impl_trait_ref={:?} impl_def_id={:?}",
+               impl_trait_ref, impl_def_id);
+        let trait_def = ty::lookup_trait_def(self.crate_context.tcx,
+                                             impl_trait_ref.def_id);
+        trait_def.record_impl(self.crate_context.tcx, impl_def_id, impl_trait_ref);
     }
 
     fn get_self_type_for_implementation(&self, impl_did: DefId)
@@ -337,7 +337,7 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
 
         // Record all the trait items.
         if let Some(trait_ref) = associated_traits {
-            self.add_trait_impl(trait_ref.def_id, impl_def_id);
+            self.add_trait_impl(trait_ref, impl_def_id);
         }
 
         // For any methods that use a default implementation, add them to
@@ -382,18 +382,16 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
         let drop_trait = match tcx.lang_items.drop_trait() {
             Some(id) => id, None => { return }
         };
+        ty::populate_implementations_for_trait_if_necessary(tcx, drop_trait);
+        let drop_trait = ty::lookup_trait_def(tcx, drop_trait);
 
         let impl_items = tcx.impl_items.borrow();
-        let trait_impls = match tcx.trait_impls.borrow().get(&drop_trait).cloned() {
-            None => return, // No types with (new-style) dtors present.
-            Some(found_impls) => found_impls
-        };
 
-        for &impl_did in &*trait_impls.borrow() {
+        drop_trait.for_each_impl(tcx, |impl_did| {
             let items = impl_items.get(&impl_did).unwrap();
             if items.is_empty() {
                 // We'll error out later. For now, just don't ICE.
-                continue;
+                return;
             }
             let method_def_id = items[0];
 
@@ -430,7 +428,7 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
                     }
                 }
             }
-        }
+        });
     }
 
     /// Ensures that implementations of the built-in trait `Copy` are legal.
@@ -440,30 +438,17 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
             Some(id) => id,
             None => return,
         };
+        ty::populate_implementations_for_trait_if_necessary(tcx, copy_trait);
+        let copy_trait = ty::lookup_trait_def(tcx, copy_trait);
 
-        let trait_impls = match tcx.trait_impls
-                                   .borrow()
-                                   .get(&copy_trait)
-                                   .cloned() {
-            None => {
-                debug!("check_implementations_of_copy(): no types with \
-                        implementations of `Copy` found");
-                return
-            }
-            Some(found_impls) => found_impls
-        };
-
-        // Clone first to avoid a double borrow error.
-        let trait_impls = trait_impls.borrow().clone();
-
-        for &impl_did in &trait_impls {
+        copy_trait.for_each_impl(tcx, |impl_did| {
             debug!("check_implementations_of_copy: impl_did={}",
                    impl_did.repr(tcx));
 
             if impl_did.krate != ast::LOCAL_CRATE {
                 debug!("check_implementations_of_copy(): impl not in this \
                         crate");
-                continue
+                return
             }
 
             let self_type = self.get_self_type_for_implementation(impl_did);
@@ -506,7 +491,7 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
                                the type has a destructor");
                 }
             }
-        }
+        });
     }
 }
 
diff --git a/src/librustc_typeck/coherence/overlap.rs b/src/librustc_typeck/coherence/overlap.rs
index 99b6d4154e9..8d402a8c1ee 100644
--- a/src/librustc_typeck/coherence/overlap.rs
+++ b/src/librustc_typeck/coherence/overlap.rs
@@ -48,59 +48,103 @@ impl<'cx, 'tcx> OverlapChecker<'cx, 'tcx> {
         // check_for_overlapping_impls_of_trait() check, since that
         // check can populate this table further with impls from other
         // crates.
-        let trait_def_ids: Vec<(ast::DefId, Vec<ast::DefId>)> =
-            self.tcx.trait_impls.borrow().iter().map(|(&k, v)| {
-                // FIXME -- it seems like this method actually pushes
-                // duplicate impls onto the list
-                ty::populate_implementations_for_trait_if_necessary(self.tcx, k);
-                (k, v.borrow().clone())
-            }).collect();
-
-        for &(trait_def_id, ref impls) in &trait_def_ids {
-            self.check_for_overlapping_impls_of_trait(trait_def_id, impls);
+        let trait_defs : Vec<&ty::TraitDef> = {
+            let d = self.tcx.trait_defs.borrow();
+            d.values().map(|&v|v).collect()
+        };
+
+        for trait_def in trait_defs {
+            // FIXME -- it seems like this method actually pushes
+            // duplicate impls onto the list
+            ty::populate_implementations_for_trait_if_necessary(
+                self.tcx,
+                trait_def.trait_ref.def_id);
+            self.check_for_overlapping_impls_of_trait(trait_def);
         }
     }
 
     fn check_for_overlapping_impls_of_trait(&self,
-                                            trait_def_id: ast::DefId,
-                                            trait_impls: &Vec<ast::DefId>)
+                                            trait_def: &'tcx ty::TraitDef<'tcx>)
     {
-        debug!("check_for_overlapping_impls_of_trait(trait_def_id={})",
-               trait_def_id.repr(self.tcx));
+        debug!("check_for_overlapping_impls_of_trait(trait_def={})",
+               trait_def.repr(self.tcx));
 
-        for (i, &impl1_def_id) in trait_impls.iter().enumerate() {
-            if impl1_def_id.krate != ast::LOCAL_CRATE {
-                // we don't need to check impls if both are external;
-                // that's the other crate's job.
-                continue;
-            }
+        // We should already know all impls of this trait, so these
+        // borrows are safe.
+        let blanket_impls = trait_def.blanket_impls.borrow();
+        let nonblanket_impls = trait_def.nonblanket_impls.borrow();
+        let trait_def_id = trait_def.trait_ref.def_id;
 
-            for &impl2_def_id in &trait_impls[(i+1)..] {
+        // Conflicts can only occur between a blanket impl and another impl,
+        // or between 2 non-blanket impls of the same kind.
+
+        for (i, &impl1_def_id) in blanket_impls.iter().enumerate() {
+            for &impl2_def_id in &blanket_impls[(i+1)..] {
                 self.check_if_impls_overlap(trait_def_id,
                                             impl1_def_id,
                                             impl2_def_id);
             }
+
+            for v in nonblanket_impls.values() {
+                for &impl2_def_id in v {
+                    self.check_if_impls_overlap(trait_def_id,
+                                                impl1_def_id,
+                                                impl2_def_id);
+                }
+            }
+        }
+
+        for impl_group in nonblanket_impls.values() {
+            for (i, &impl1_def_id) in impl_group.iter().enumerate() {
+                for &impl2_def_id in &impl_group[(i+1)..] {
+                    self.check_if_impls_overlap(trait_def_id,
+                                                impl1_def_id,
+                                                impl2_def_id);
+                }
+            }
         }
     }
 
+    // We need to coherently pick which impl will be displayed
+    // as causing the error message, and it must be the in the current
+    // crate. Just pick the smaller impl in the file.
+    fn order_impls(&self, impl1_def_id: ast::DefId, impl2_def_id: ast::DefId)
+            -> Option<(ast::DefId, ast::DefId)> {
+        if impl1_def_id.krate != ast::LOCAL_CRATE {
+            if impl2_def_id.krate != ast::LOCAL_CRATE {
+                // we don't need to check impls if both are external;
+                // that's the other crate's job.
+                None
+            } else {
+                Some((impl2_def_id, impl1_def_id))
+            }
+        } else if impl2_def_id.krate != ast::LOCAL_CRATE {
+            Some((impl1_def_id, impl2_def_id))
+        } else if impl1_def_id.node < impl2_def_id.node {
+            Some((impl1_def_id, impl2_def_id))
+        } else {
+            Some((impl2_def_id, impl1_def_id))
+        }
+    }
+
+
     fn check_if_impls_overlap(&self,
                               trait_def_id: ast::DefId,
                               impl1_def_id: ast::DefId,
                               impl2_def_id: ast::DefId)
     {
-        assert_eq!(impl1_def_id.krate, ast::LOCAL_CRATE);
-
-        debug!("check_if_impls_overlap({}, {}, {})",
-               trait_def_id.repr(self.tcx),
-               impl1_def_id.repr(self.tcx),
-               impl2_def_id.repr(self.tcx));
-
-        let infcx = infer::new_infer_ctxt(self.tcx);
-        if !traits::overlapping_impls(&infcx, impl1_def_id, impl2_def_id) {
-            return;
+        if let Some((impl1_def_id, impl2_def_id)) = self.order_impls(
+            impl1_def_id, impl2_def_id) {
+            debug!("check_if_impls_overlap({}, {}, {})",
+                   trait_def_id.repr(self.tcx),
+                   impl1_def_id.repr(self.tcx),
+                   impl2_def_id.repr(self.tcx));
+
+            let infcx = infer::new_infer_ctxt(self.tcx);
+            if traits::overlapping_impls(&infcx, impl1_def_id, impl2_def_id) {
+                self.report_overlap_error(trait_def_id, impl1_def_id, impl2_def_id);
+            }
         }
-
-        self.report_overlap_error(trait_def_id, impl1_def_id, impl2_def_id);
     }
 
     fn report_overlap_error(&self, trait_def_id: ast::DefId,
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index b6672065e64..6f78e853ebe 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -83,7 +83,7 @@ use util::ppaux;
 use util::ppaux::{Repr,UserString};
 use write_ty_to_tcx;
 
-use std::cell::RefCell;
+use std::cell::{Cell, RefCell};
 use std::collections::HashSet;
 use std::rc::Rc;
 
@@ -1257,6 +1257,9 @@ fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
         generics: ty_generics,
         trait_ref: trait_ref,
         associated_type_names: associated_type_names,
+        nonblanket_impls: RefCell::new(FnvHashMap()),
+        blanket_impls: RefCell::new(vec![]),
+        flags: Cell::new(ty::TraitFlags::NO_TRAIT_FLAGS)
     };
 
     return tcx.intern_trait_def(trait_def);