Port coherence to use the new trait matching code

6 files changed, 400 insertions, 309 deletions

diff --git a/src/librustc/middle/dead.rs b/src/librustc/middle/dead.rs
index 46e3585912a..850c6ecffaa 100644
--- a/src/librustc/middle/dead.rs
+++ b/src/librustc/middle/dead.rs
@@ -470,7 +470,7 @@ impl<'a, 'tcx> DeadVisitor<'a, 'tcx> {
         match self.tcx.inherent_impls.borrow().find(&local_def(id)) {
             None => (),
             Some(impl_list) => {
-                for impl_did in impl_list.borrow().iter() {
+                for impl_did in impl_list.iter() {
                     for item_did in impl_items.get(impl_did).iter() {
                         if self.live_symbols.contains(&item_did.def_id()
                                                                .node) {
diff --git a/src/librustc/middle/traits/coherence.rs b/src/librustc/middle/traits/coherence.rs
new file mode 100644
index 00000000000..415eed380fc
--- /dev/null
+++ b/src/librustc/middle/traits/coherence.rs
@@ -0,0 +1,168 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+/*! See `doc.rs` for high-level documentation */
+
+use super::DUMMY_CAUSE;
+use super::{EvaluatedToMatch, EvaluatedToAmbiguity, EvaluatedToUnmatch};
+use super::{evaluate_impl};
+use super::util;
+
+use middle::subst;
+use middle::subst::Subst;
+use middle::ty;
+use middle::typeck::infer::InferCtxt;
+use syntax::ast;
+use syntax::codemap::DUMMY_SP;
+use util::nodemap::DefIdMap;
+use util::ppaux::Repr;
+
+pub fn impl_can_satisfy(infcx: &InferCtxt,
+                        impl1_def_id: ast::DefId,
+                        impl2_def_id: ast::DefId)
+                        -> bool
+{
+    // `impl1` provides an implementation of `Foo<X,Y> for Z`.
+    let impl1_substs =
+        util::fresh_substs_for_impl(infcx, DUMMY_SP, impl1_def_id);
+    let impl1_self_ty =
+        ty::impl_trait_ref(infcx.tcx, impl1_def_id).unwrap()
+            .self_ty()
+            .subst(infcx.tcx, &impl1_substs);
+
+    // Determine whether `impl2` can provide an implementation for those
+    // same types.
+    let param_env = ty::empty_parameter_environment();
+    let unboxed_closures = DefIdMap::new();
+    match evaluate_impl(infcx, &param_env, &unboxed_closures, DUMMY_CAUSE,
+                        impl2_def_id, impl1_self_ty) {
+        EvaluatedToMatch | EvaluatedToAmbiguity => true,
+        EvaluatedToUnmatch => false,
+    }
+}
+
+pub fn impl_is_local(tcx: &ty::ctxt,
+                     impl_def_id: ast::DefId)
+                     -> bool
+{
+    debug!("impl_is_local({})", impl_def_id.repr(tcx));
+
+    // We only except this routine to be invoked on implementations
+    // of a trait, not inherent implementations.
+    let trait_ref = ty::impl_trait_ref(tcx, impl_def_id).unwrap();
+    debug!("trait_ref={}", trait_ref.repr(tcx));
+
+    // If the trait is local to the crate, ok.
+    if trait_ref.def_id.krate == ast::LOCAL_CRATE {
+        debug!("trait {} is local to current crate",
+               trait_ref.def_id.repr(tcx));
+        return true;
+    }
+
+    // Otherwise, self type must be local to the crate.
+    let self_ty = ty::lookup_item_type(tcx, impl_def_id).ty;
+    return ty_is_local(tcx, self_ty);
+}
+
+pub fn ty_is_local(tcx: &ty::ctxt,
+                   ty: ty::t)
+                   -> bool
+{
+    debug!("ty_is_local({})", ty.repr(tcx));
+
+    match ty::get(ty).sty {
+        ty::ty_nil |
+        ty::ty_bot |
+        ty::ty_bool |
+        ty::ty_char |
+        ty::ty_int(..) |
+        ty::ty_uint(..) |
+        ty::ty_float(..) |
+        ty::ty_str(..) => {
+            false
+        }
+
+        ty::ty_unboxed_closure(..) => {
+            // This routine is invoked on types specified by users as
+            // part of an impl and hence an unboxed closure type
+            // cannot appear.
+            tcx.sess.bug("ty_is_local applied to unboxed closure type")
+        }
+
+        ty::ty_bare_fn(..) |
+        ty::ty_closure(..) => {
+            false
+        }
+
+        ty::ty_uniq(t) => {
+            let krate = tcx.lang_items.owned_box().map(|d| d.krate);
+            krate == Some(ast::LOCAL_CRATE) || ty_is_local(tcx, t)
+        }
+
+        ty::ty_box(t) => {
+            let krate = tcx.lang_items.gc().map(|d| d.krate);
+            krate == Some(ast::LOCAL_CRATE) || ty_is_local(tcx, t)
+        }
+
+        ty::ty_vec(t, _) |
+        ty::ty_ptr(ty::mt { ty: t, .. }) |
+        ty::ty_rptr(_, ty::mt { ty: t, .. }) => {
+            ty_is_local(tcx, t)
+        }
+
+        ty::ty_tup(ref ts) => {
+            ts.iter().any(|&t| ty_is_local(tcx, t))
+        }
+
+        ty::ty_enum(def_id, ref substs) |
+        ty::ty_struct(def_id, ref substs) => {
+            def_id.krate == ast::LOCAL_CRATE || {
+                let variances = ty::item_variances(tcx, def_id);
+                subst::ParamSpace::all().iter().any(|&space| {
+                    substs.types.get_slice(space).iter().enumerate().any(
+                        |(i, &t)| {
+                            match *variances.types.get(space, i) {
+                                ty::Bivariant => {
+                                    // If Foo<T> is bivariant with respect to
+                                    // T, then it doesn't matter whether T is
+                                    // local or not, because `Foo<U>` for any
+                                    // U will be a subtype of T.
+                                    false
+                                }
+                                ty::Contravariant |
+                                ty::Covariant |
+                                ty::Invariant => {
+                                    ty_is_local(tcx, t)
+                                }
+                            }
+                        })
+                })
+            }
+        }
+
+        ty::ty_trait(ref tt) => {
+            tt.def_id.krate == ast::LOCAL_CRATE
+        }
+
+        // Type parameters may be bound to types that are not local to
+        // the crate.
+        ty::ty_param(..) => {
+            false
+        }
+
+        ty::ty_infer(..) |
+        ty::ty_open(..) |
+        ty::ty_err => {
+            tcx.sess.bug(
+                format!("ty_is_local invoked on unexpected type: {}",
+                        ty.repr(tcx)).as_slice())
+        }
+    }
+}
diff --git a/src/librustc/middle/typeck/coherence.rs b/src/librustc/middle/typeck/coherence/mod.rs
index 8de17627e28..76c5cab234f 100644
--- a/src/librustc/middle/typeck/coherence.rs
+++ b/src/librustc/middle/typeck/coherence/mod.rs
@@ -1,4 +1,4 @@
-// Copyright 2012-2013 The Rust Project Developers. See the COPYRIGHT
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
 // file at the top-level directory of this distribution and at
 // http://rust-lang.org/COPYRIGHT.
 //
@@ -10,12 +10,13 @@
 
 // Coherence phase
 //
-// The job of the coherence phase of typechecking is to ensure that each trait
-// has at most one implementation for each type. Then we build a mapping from
-// each trait in the system to its implementations.
+// The job of the coherence phase of typechecking is to ensure that
+// each trait has at most one implementation for each type. This is
+// done by the orphan and overlap modules. Then we build up various
+// mappings. That mapping code resides here.
 
 
-use metadata::csearch::{each_impl, get_impl_trait, each_implementation_for_trait};
+use metadata::csearch::{each_impl, get_impl_trait};
 use metadata::csearch;
 use middle::subst;
 use middle::subst::{Substs};
@@ -35,27 +36,24 @@ use middle::typeck::CrateCtxt;
 use middle::typeck::infer::combine::Combine;
 use middle::typeck::infer::InferCtxt;
 use middle::typeck::infer::{new_infer_ctxt, resolve_ivar, resolve_type};
-use middle::typeck::infer;
-use util::ppaux::Repr;
-use middle::def::{DefStruct, DefTy};
+use std::collections::{HashSet};
+use std::cell::RefCell;
+use std::rc::Rc;
 use syntax::ast::{Crate, DefId};
-use syntax::ast::{Item, ItemEnum, ItemImpl, ItemMod, ItemStruct};
-use syntax::ast::{LOCAL_CRATE, TraitRef, TyPath};
+use syntax::ast::{Item, ItemImpl};
+use syntax::ast::{LOCAL_CRATE, TraitRef};
 use syntax::ast;
 use syntax::ast_map::NodeItem;
 use syntax::ast_map;
 use syntax::ast_util::{local_def};
-use syntax::codemap::{Span, DUMMY_SP};
+use syntax::codemap::{Span};
 use syntax::parse::token;
 use syntax::visit;
+use util::nodemap::{DefIdMap, FnvHashMap};
+use util::ppaux::Repr;
 
-use std::collections::HashSet;
-use std::cell::RefCell;
-use std::rc::Rc;
-
-struct UniversalQuantificationResult {
-    monotype: t
-}
+mod orphan;
+mod overlap;
 
 fn get_base_type(inference_context: &InferCtxt,
                  span: Span,
@@ -96,53 +94,6 @@ fn get_base_type(inference_context: &InferCtxt,
     }
 }
 
-fn type_is_defined_in_local_crate(tcx: &ty::ctxt, original_type: t) -> bool {
-    /*!
-     *
-     * For coherence, when we have `impl Trait for Type`, we need to
-     * guarantee that `Type` is "local" to the
-     * crate.  For our purposes, this means that it must contain
-     * some nominal type defined in this crate.
-     */
-
-    let mut found_nominal = false;
-    ty::walk_ty(original_type, |t| {
-        match get(t).sty {
-            ty_enum(def_id, _) |
-            ty_struct(def_id, _) |
-            ty_unboxed_closure(def_id, _) => {
-                if def_id.krate == ast::LOCAL_CRATE {
-                    found_nominal = true;
-                }
-            }
-            ty_trait(box ty::TyTrait { def_id, .. }) => {
-                if def_id.krate == ast::LOCAL_CRATE {
-                    found_nominal = true;
-                }
-            }
-            ty_uniq(..) => {
-                match tcx.lang_items.owned_box() {
-                    Some(did) if did.krate == ast::LOCAL_CRATE => {
-                        found_nominal = true;
-                    }
-                    _ => {}
-                }
-            }
-            ty_box(..) => {
-                match tcx.lang_items.gc() {
-                    Some(did) if did.krate == ast::LOCAL_CRATE => {
-                        found_nominal = true;
-                    }
-                    _ => {}
-                }
-            }
-
-            _ => { }
-        }
-    });
-    return found_nominal;
-}
-
 // Returns the def ID of the base type, if there is one.
 fn get_base_type_def_id(inference_context: &InferCtxt,
                         span: Span,
@@ -185,6 +136,7 @@ fn get_base_type_def_id(inference_context: &InferCtxt,
 struct CoherenceChecker<'a, 'tcx: 'a> {
     crate_context: &'a CrateCtxt<'a, 'tcx>,
     inference_context: InferCtxt<'a, 'tcx>,
+    inherent_impls: RefCell<DefIdMap<Rc<RefCell<Vec<ast::DefId>>>>>,
 }
 
 struct CoherenceCheckVisitor<'a, 'tcx: 'a> {
@@ -214,57 +166,6 @@ impl<'a, 'tcx, 'v> visit::Visitor<'v> for CoherenceCheckVisitor<'a, 'tcx> {
     }
 }
 
-struct PrivilegedScopeVisitor<'a, 'tcx: 'a> {
-    cc: &'a CoherenceChecker<'a, 'tcx>
-}
-
-impl<'a, 'tcx, 'v> visit::Visitor<'v> for PrivilegedScopeVisitor<'a, 'tcx> {
-    fn visit_item(&mut self, item: &Item) {
-
-        match item.node {
-            ItemMod(ref module_) => {
-                // Then visit the module items.
-                visit::walk_mod(self, module_);
-            }
-            ItemImpl(_, None, ref ast_ty, _) => {
-                if !self.cc.ast_type_is_defined_in_local_crate(&**ast_ty) {
-                    // This is an error.
-                    let session = &self.cc.crate_context.tcx.sess;
-                    span_err!(session, item.span, E0116,
-                              "cannot associate methods with a type outside the \
-                               crate the type is defined in; define and implement \
-                               a trait or new type instead");
-                }
-            }
-            ItemImpl(_, Some(ref trait_ref), _, _) => {
-                let tcx = self.cc.crate_context.tcx;
-                // `for_ty` is `Type` in `impl Trait for Type`
-                let for_ty = ty::node_id_to_type(tcx, item.id);
-                if !type_is_defined_in_local_crate(tcx, for_ty) {
-                    // This implementation is not in scope of its base
-                    // type. This still might be OK if the trait is
-                    // defined in the same crate.
-
-                    let trait_def_id =
-                        self.cc.trait_ref_to_trait_def_id(trait_ref);
-
-                    if trait_def_id.krate != LOCAL_CRATE {
-                        let session = &self.cc.crate_context.tcx.sess;
-                        span_err!(session, item.span, E0117,
-                                  "cannot provide an extension implementation \
-                                   where both trait and type are not defined in this crate");
-                    }
-                }
-
-                visit::walk_item(self, item);
-            }
-            _ => {
-                visit::walk_item(self, item);
-            }
-        }
-    }
-}
-
 impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
     fn check(&self, krate: &Crate) {
         // Check implementations and traits. This populates the tables
@@ -273,11 +174,14 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
         let mut visitor = CoherenceCheckVisitor { cc: self };
         visit::walk_crate(&mut visitor, krate);
 
-        // Check that there are no overlapping trait instances
-        self.check_implementation_coherence();
-
-        // Check whether traits with base types are in privileged scopes.
-        self.check_privileged_scopes(krate);
+        // Copy over the inherent impls we gathered up during the walk into
+        // the tcx.
+        let mut tcx_inherent_impls =
+            self.crate_context.tcx.inherent_impls.borrow_mut();
+        for (k, v) in self.inherent_impls.borrow().iter() {
+            tcx_inherent_impls.insert((*k).clone(),
+                                      Rc::new((*v.borrow()).clone()));
+        }
 
         // Bring in external crates. It's fine for this to happen after the
         // coherence checks, because we ensure by construction that no errors
@@ -290,7 +194,8 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
         self.populate_destructor_table();
     }
 
-    fn check_implementation(&self, item: &Item,
+    fn check_implementation(&self,
+                            item: &Item,
                             associated_traits: &[TraitRef]) {
         let tcx = self.crate_context.tcx;
         let impl_did = local_def(item.id);
@@ -299,25 +204,6 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
         // If there are no traits, then this implementation must have a
         // base type.
 
-        if associated_traits.len() == 0 {
-            debug!("(checking implementation) no associated traits for item '{}'",
-                   token::get_ident(item.ident));
-
-            match get_base_type_def_id(&self.inference_context,
-                                       item.span,
-                                       self_type.ty) {
-                None => {
-                    let session = &self.crate_context.tcx.sess;
-                    span_err!(session, item.span, E0118,
-                              "no base type found for inherent implementation; \
-                               implement a trait or new type instead");
-                }
-                Some(_) => {
-                    // Nothing to do.
-                }
-            }
-        }
-
         let impl_items = self.create_impl_from_item(item);
 
         for associated_trait in associated_traits.iter() {
@@ -408,8 +294,7 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
     }
 
     fn add_inherent_impl(&self, base_def_id: DefId, impl_def_id: DefId) {
-        let tcx = self.crate_context.tcx;
-        match tcx.inherent_impls.borrow().find(&base_def_id) {
+        match self.inherent_impls.borrow().find(&base_def_id) {
             Some(implementation_list) => {
                 implementation_list.borrow_mut().push(impl_def_id);
                 return;
@@ -417,178 +302,24 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
             None => {}
         }
 
-        tcx.inherent_impls.borrow_mut().insert(base_def_id,
-                                               Rc::new(RefCell::new(vec!(impl_def_id))));
+        self.inherent_impls.borrow_mut().insert(
+            base_def_id,
+            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 check_implementation_coherence(&self) {
-        for trait_id in self.crate_context.tcx.trait_impls.borrow().keys() {
-            self.check_implementation_coherence_of(*trait_id);
-        }
-    }
-
-    fn check_implementation_coherence_of(&self, trait_def_id: DefId) {
-        // Unify pairs of polytypes.
-        self.iter_impls_of_trait_local(trait_def_id, |impl_a| {
-            let polytype_a =
-                self.get_self_type_for_implementation(impl_a);
-
-            // "We have an impl of trait <trait_def_id> for type <polytype_a>,
-            // and that impl is <impl_a>"
-            self.iter_impls_of_trait(trait_def_id, |impl_b| {
-
-                // An impl is coherent with itself
-                if impl_a != impl_b {
-                    let polytype_b = self.get_self_type_for_implementation(
-                            impl_b);
-
-                    if self.polytypes_unify(polytype_a.clone(), polytype_b) {
-                        let session = &self.crate_context.tcx.sess;
-                        span_err!(session, self.span_of_impl(impl_a), E0119,
-                                  "conflicting implementations for trait `{}`",
-                                  ty::item_path_str(self.crate_context.tcx, trait_def_id));
-                        if impl_b.krate == LOCAL_CRATE {
-                            span_note!(session, self.span_of_impl(impl_b),
-                                       "note conflicting implementation here");
-                        } else {
-                            let crate_store = &self.crate_context.tcx.sess.cstore;
-                            let cdata = crate_store.get_crate_data(impl_b.krate);
-                            span_note!(session, self.span_of_impl(impl_a),
-                                       "conflicting implementation in crate `{}`",
-                                       cdata.name);
-                        }
-                    }
-                }
-            })
-        })
-    }
-
-    fn iter_impls_of_trait(&self, trait_def_id: DefId, f: |DefId|) {
-        self.iter_impls_of_trait_local(trait_def_id, |x| f(x));
-
-        if trait_def_id.krate == LOCAL_CRATE {
-            return;
-        }
-
-        let crate_store = &self.crate_context.tcx.sess.cstore;
-        csearch::each_implementation_for_trait(crate_store, trait_def_id, |impl_def_id| {
-            // Is this actually necessary?
-            let _ = lookup_item_type(self.crate_context.tcx, impl_def_id);
-            f(impl_def_id);
-        });
-    }
-
-    fn iter_impls_of_trait_local(&self, trait_def_id: DefId, f: |DefId|) {
-        match self.crate_context.tcx.trait_impls.borrow().find(&trait_def_id) {
-            Some(impls) => {
-                for &impl_did in impls.borrow().iter() {
-                    f(impl_did);
-                }
-            }
-            None => { /* no impls? */ }
-        }
-    }
-
-    fn polytypes_unify(&self,
-                       polytype_a: Polytype,
-                       polytype_b: Polytype)
-                       -> bool {
-        let universally_quantified_a =
-            self.universally_quantify_polytype(polytype_a);
-        let universally_quantified_b =
-            self.universally_quantify_polytype(polytype_b);
-
-        return self.can_unify_universally_quantified(
-            &universally_quantified_a, &universally_quantified_b) ||
-            self.can_unify_universally_quantified(
-            &universally_quantified_b, &universally_quantified_a);
-    }
-
-    // Converts a polytype to a monotype by replacing all parameters with
-    // type variables. Returns the monotype and the type variables created.
-    fn universally_quantify_polytype(&self, polytype: Polytype)
-                                     -> UniversalQuantificationResult
-    {
-        let substitutions =
-            self.inference_context.fresh_substs_for_type(DUMMY_SP,
-                                                         &polytype.generics);
-        let monotype = polytype.ty.subst(self.crate_context.tcx, &substitutions);
-
-        UniversalQuantificationResult {
-            monotype: monotype
-        }
-    }
-
-    fn can_unify_universally_quantified<'a>(&self,
-                                            a: &'a UniversalQuantificationResult,
-                                            b: &'a UniversalQuantificationResult)
-                                            -> bool
-    {
-        infer::can_mk_subty(&self.inference_context,
-                            a.monotype,
-                            b.monotype).is_ok()
-    }
-
     fn get_self_type_for_implementation(&self, impl_did: DefId)
                                         -> Polytype {
         self.crate_context.tcx.tcache.borrow().get_copy(&impl_did)
     }
 
-    // Privileged scope checking
-    fn check_privileged_scopes(&self, krate: &Crate) {
-        let mut visitor = PrivilegedScopeVisitor{ cc: self };
-        visit::walk_crate(&mut visitor, krate);
-    }
-
-    fn trait_ref_to_trait_def_id(&self, trait_ref: &TraitRef) -> DefId {
-        let def_map = &self.crate_context.tcx.def_map;
-        let trait_def = def_map.borrow().get_copy(&trait_ref.ref_id);
-        let trait_id = trait_def.def_id();
-        return trait_id;
-    }
-
-    /// For coherence, when we have `impl Type`, we need to guarantee that
-    /// `Type` is "local" to the crate. For our purposes, this means that it
-    /// must precisely name some nominal type defined in this crate.
-    fn ast_type_is_defined_in_local_crate(&self, original_type: &ast::Ty) -> bool {
-        match original_type.node {
-            TyPath(_, _, path_id) => {
-                match self.crate_context.tcx.def_map.borrow().get_copy(&path_id) {
-                    DefTy(def_id) | DefStruct(def_id) => {
-                        if def_id.krate != LOCAL_CRATE {
-                            return false;
-                        }
-
-                        // Make sure that this type precisely names a nominal
-                        // type.
-                        match self.crate_context.tcx.map.find(def_id.node) {
-                            None => {
-                                self.crate_context.tcx.sess.span_bug(
-                                    original_type.span,
-                                    "resolve didn't resolve this type?!");
-                            }
-                            Some(NodeItem(item)) => {
-                                match item.node {
-                                    ItemStruct(..) | ItemEnum(..) => true,
-                                    _ => false,
-                                }
-                            }
-                            Some(_) => false,
-                        }
-                    }
-                    _ => false
-                }
-            }
-            _ => false
-        }
-    }
-
     // Converts an implementation in the AST to a vector of items.
     fn create_impl_from_item(&self, item: &Item) -> Vec<ImplOrTraitItemId> {
         match item.node {
@@ -623,11 +354,6 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
         }
     }
 
-    fn span_of_impl(&self, impl_did: DefId) -> Span {
-        assert_eq!(impl_did.krate, LOCAL_CRATE);
-        self.crate_context.tcx.map.span(impl_did.node)
-    }
-
     // External crate handling
 
     fn add_external_impl(&self,
@@ -824,5 +550,8 @@ pub fn check_coherence(crate_context: &CrateCtxt) {
     CoherenceChecker {
         crate_context: crate_context,
         inference_context: new_infer_ctxt(crate_context.tcx),
+        inherent_impls: RefCell::new(FnvHashMap::new()),
     }.check(crate_context.tcx.map.krate());
+    orphan::check(crate_context.tcx);
+    overlap::check(crate_context.tcx);
 }
diff --git a/src/librustc/middle/typeck/coherence/orphan.rs b/src/librustc/middle/typeck/coherence/orphan.rs
new file mode 100644
index 00000000000..e7139e1229b
--- /dev/null
+++ b/src/librustc/middle/typeck/coherence/orphan.rs
@@ -0,0 +1,75 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+/*!
+ * Orphan checker: every impl either implements a trait defined in this
+ * crate or pertains to a type defined in this crate.
+ */
+
+use middle::traits;
+use middle::ty;
+use syntax::ast::{Item, ItemImpl};
+use syntax::ast;
+use syntax::ast_util;
+use syntax::visit;
+use util::ppaux::Repr;
+
+pub fn check(tcx: &ty::ctxt) {
+    let mut orphan = OrphanChecker { tcx: tcx };
+    visit::walk_crate(&mut orphan, tcx.map.krate());
+}
+
+struct OrphanChecker<'cx, 'tcx:'cx> {
+    tcx: &'cx ty::ctxt<'tcx>
+}
+
+impl<'cx, 'tcx,'v> visit::Visitor<'v> for OrphanChecker<'cx, 'tcx> {
+    fn visit_item(&mut self, item: &'v ast::Item) {
+        let def_id = ast_util::local_def(item.id);
+        match item.node {
+            ast::ItemImpl(_, None, _, _) => {
+                // For inherent impls, self type must be a nominal type
+                // defined in this crate.
+                debug!("coherence2::orphan check: inherent impl {}", item.repr(self.tcx));
+                let self_ty = ty::lookup_item_type(self.tcx, def_id).ty;
+                match ty::get(self_ty).sty {
+                    ty::ty_enum(def_id, _) |
+                    ty::ty_struct(def_id, _) => {
+                        if def_id.krate != ast::LOCAL_CRATE {
+                            span_err!(self.tcx.sess, item.span, E0116,
+                                      "cannot associate methods with a type outside the \
+                                      crate the type is defined in; define and implement \
+                                      a trait or new type instead");
+                        }
+                    }
+                    _ => {
+                        span_err!(self.tcx.sess, item.span, E0118,
+                                  "no base type found for inherent implementation; \
+                                   implement a trait or new type instead");
+                    }
+                }
+            }
+            ast::ItemImpl(_, Some(_), _, _) => {
+                // "Trait" impl
+                debug!("coherence2::orphan check: trait impl {}", item.repr(self.tcx));
+                if traits::is_orphan_impl(self.tcx, def_id) {
+                    span_err!(self.tcx.sess, item.span, E0117,
+                              "cannot provide an extension implementation \
+                               where both trait and type are not defined in this crate");
+                }
+            }
+            _ => {
+                // Not an impl
+            }
+        }
+
+        visit::walk_item(self, item);
+    }
+}
diff --git a/src/librustc/middle/typeck/coherence/overlap.rs b/src/librustc/middle/typeck/coherence/overlap.rs
new file mode 100644
index 00000000000..48f71d95c42
--- /dev/null
+++ b/src/librustc/middle/typeck/coherence/overlap.rs
@@ -0,0 +1,119 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+/*!
+ * Overlap: No two impls for the same trait are implemented for the
+ * same type.
+ */
+
+use middle::traits;
+use middle::ty;
+use middle::typeck::infer::{new_infer_ctxt};
+use middle::typeck::infer;
+use syntax::ast::{DefId};
+use syntax::ast::{LOCAL_CRATE};
+use syntax::ast;
+use syntax::codemap::{Span};
+use util::ppaux::Repr;
+
+pub fn check(tcx: &ty::ctxt) {
+    let overlap = OverlapChecker { tcx: tcx };
+    overlap.check_for_overlapping_impls();
+}
+
+struct OverlapChecker<'cx, 'tcx:'cx> {
+    tcx: &'cx ty::ctxt<'tcx>
+}
+
+impl<'cx, 'tcx> OverlapChecker<'cx, 'tcx> {
+    fn check_for_overlapping_impls(&self) {
+        debug!("check_for_overlapping_impls");
+        let trait_impls = self.tcx.trait_impls.borrow();
+        for trait_def_id in trait_impls.keys() {
+            self.check_for_overlapping_impls_of_trait(*trait_def_id);
+        }
+    }
+
+    fn check_for_overlapping_impls_of_trait(&self,
+                                            trait_def_id: ast::DefId)
+    {
+        debug!("check_for_overlapping_impls_of_trait(trait_def_id={})",
+               trait_def_id.repr(self.tcx));
+
+        // FIXME -- it seems like this method actually pushes
+        // duplicate impls onto the list
+        ty::populate_implementations_for_type_if_necessary(self.tcx,
+                                                           trait_def_id);
+
+        let mut impls = Vec::new();
+        self.push_impls_of_trait(trait_def_id, &mut impls);
+
+        for (i, &impl1_def_id) in 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;
+            }
+
+            for &impl2_def_id in impls.slice_from(i+1).iter() {
+                self.check_if_impls_overlap(trait_def_id,
+                                            impl1_def_id,
+                                            impl2_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;
+        }
+
+        span_err!(self.tcx.sess, self.span_of_impl(impl1_def_id), E0119,
+                  "conflicting implementations for trait `{}`",
+                  ty::item_path_str(self.tcx, trait_def_id));
+
+        if impl2_def_id.krate == ast::LOCAL_CRATE {
+            span_note!(self.tcx.sess, self.span_of_impl(impl2_def_id),
+                       "note conflicting implementation here");
+        } else {
+            let crate_store = &self.tcx.sess.cstore;
+            let cdata = crate_store.get_crate_data(impl2_def_id.krate);
+            span_note!(self.tcx.sess, self.span_of_impl(impl1_def_id),
+                       "conflicting implementation in crate `{}`",
+                       cdata.name);
+        }
+    }
+
+    fn push_impls_of_trait(&self,
+                           trait_def_id: ast::DefId,
+                           out: &mut Vec<ast::DefId>) {
+        match self.tcx.trait_impls.borrow().find(&trait_def_id) {
+            Some(impls) => { out.push_all(impls.borrow().as_slice()); }
+            None => { /* no impls */ }
+        }
+    }
+
+    fn span_of_impl(&self, impl_did: ast::DefId) -> Span {
+        assert_eq!(impl_did.krate, ast::LOCAL_CRATE);
+        self.tcx.map.span(impl_did.node)
+    }
+}
diff --git a/src/librustdoc/clean/inline.rs b/src/librustdoc/clean/inline.rs
index e0afb80ad37..7272425761e 100644
--- a/src/librustdoc/clean/inline.rs
+++ b/src/librustdoc/clean/inline.rs
@@ -226,7 +226,7 @@ fn build_impls(cx: &DocContext, tcx: &ty::ctxt,
     match tcx.inherent_impls.borrow().find(&did) {
         None => {}
         Some(i) => {
-            impls.extend(i.borrow().iter().map(|&did| { build_impl(cx, tcx, did) }));
+            impls.extend(i.iter().map(|&did| { build_impl(cx, tcx, did) }));
         }
     }