Implement new orphan rule that requires that impls of remote traits meet the following two criteria:

- the self type includes some local type; and,
- type parameters in the self type must be constrained by a local type.

A type parameter is called *constrained* if it appears in some type-parameter of a local type.

Here are some examples that are accepted. In all of these examples, I
assume that `Foo` is a trait defined in another crate. If `Foo` were
defined in the local crate, then all the examples would be legal.

- `impl Foo for LocalType`
- `impl<T> Foo<T> for LocalType` -- T does not appear in Self, so it is OK
- `impl<T> Foo<T> for LocalType<T>` -- T here is constrained by LocalType
- `impl<T> Foo<T> for (LocalType<T>, T)` -- T here is constrained by LocalType

Here are some illegal examples (again, these examples assume that
`Foo` is not local to the current crate):

- `impl Foo for int` -- the Self type is not local
- `impl<T> Foo for T` -- T appears in Self unconstrained by a local type
- `impl<T> Foo for (LocalType, T)` -- T appears in Self unconstrained by a local type

This is a [breaking-change]. For the time being, you can opt out of
the new rules by placing `#[old_orphan_check]` on the trait (and
enabling the feature gate where the trait is defined). Longer term,
you should restructure your traits to avoid the problem. Usually this
means changing the order of parameters so that the "central" type
parameter is in the `Self` position.

As an example of that refactoring, consider the `BorrowFrom` trait:

```rust
pub trait BorrowFrom<Sized? Owned> for Sized? {
    fn borrow_from(owned: &Owned) -> &Self;
}
```

As defined, this trait is commonly implemented for custom pointer
types, such as `Arc`. Those impls follow the pattern:

```rust
impl<T> BorrowFrom<Arc<T>> for T {...}
```

Unfortunately, this impl is illegal because the self type `T` is not
local to the current crate. Therefore, we are going to change the order of the parameters,
so that `BorrowFrom` becomes `Borrow`:

```rust
pub trait Borrow<Sized? Borrowed> for Sized? {
    fn borrow_from(owned: &Self) -> &Borrowed;
}
```

Now the `Arc` impl is written:

```rust
impl<T> Borrow<T> for Arc<T> { ... }
```

This impl is legal because the self type (`Arc<T>`) is local.

18 files changed, 68 insertions, 53 deletions

diff --git a/src/libcore/borrow.rs b/src/libcore/borrow.rs
index 7e4d73d598d..ebb4bd88cf1 100644
--- a/src/libcore/borrow.rs
+++ b/src/libcore/borrow.rs
@@ -53,12 +53,14 @@ use option::Option;
 use self::Cow::*;
 
 /// A trait for borrowing data.
+#[old_orphan_check]
 pub trait BorrowFrom<Sized? Owned> for Sized? {
     /// Immutably borrow from an owned value.
     fn borrow_from(owned: &Owned) -> &Self;
 }
 
 /// A trait for mutably borrowing data.
+#[old_orphan_check]
 pub trait BorrowFromMut<Sized? Owned> for Sized? : BorrowFrom<Owned> {
     /// Mutably borrow from an owned value.
     fn borrow_from_mut(owned: &mut Owned) -> &mut Self;
@@ -91,6 +93,7 @@ impl<'a, T, Sized? B> BorrowFrom<Cow<'a, T, B>> for B where B: ToOwned<T> {
 }
 
 /// Trait for moving into a `Cow`
+#[old_orphan_check]
 pub trait IntoCow<'a, T, Sized? B> {
     /// Moves `self` into `Cow`
     fn into_cow(self) -> Cow<'a, T, B>;
@@ -103,6 +106,7 @@ impl<'a, T, Sized? B> IntoCow<'a, T, B> for Cow<'a, T, B> where B: ToOwned<T> {
 }
 
 /// A generalization of Clone to borrowed data.
+#[old_orphan_check]
 pub trait ToOwned<Owned> for Sized?: BorrowFrom<Owned> {
     /// Create owned data from borrowed data, usually by copying.
     fn to_owned(&self) -> Owned;
diff --git a/src/libcore/cmp.rs b/src/libcore/cmp.rs
index 13f9f5ccee9..90ff174c2bd 100644
--- a/src/libcore/cmp.rs
+++ b/src/libcore/cmp.rs
@@ -69,6 +69,7 @@ use option::Option::{self, Some, None};
 /// only if `a != b`.
 #[lang="eq"]
 #[stable]
+#[old_orphan_check]
 pub trait PartialEq<Sized? Rhs = Self> for Sized? {
     /// This method tests for `self` and `other` values to be equal, and is used by `==`.
     #[stable]
diff --git a/src/librustc/lint/builtin.rs b/src/librustc/lint/builtin.rs
index 8f03f882128..cf5ca5956f4 100644
--- a/src/librustc/lint/builtin.rs
+++ b/src/librustc/lint/builtin.rs
@@ -670,6 +670,9 @@ impl LintPass for UnusedAttributes {
             "must_use",
             "stable",
             "unstable",
+
+            // FIXME: #19470 this shouldn't be needed forever
+            "old_orphan_check",
         ];
 
         static CRATE_ATTRS: &'static [&'static str] = &[
diff --git a/src/librustc/middle/traits/coherence.rs b/src/librustc/middle/traits/coherence.rs
index e6805cddae0..96b94ab298a 100644
--- a/src/librustc/middle/traits/coherence.rs
+++ b/src/librustc/middle/traits/coherence.rs
@@ -14,7 +14,7 @@ use super::SelectionContext;
 use super::{Obligation, ObligationCause};
 use super::util;
 
-use middle::subst::Subst;
+use middle::subst::{Subst};
 use middle::ty::{self, Ty};
 use middle::infer::InferCtxt;
 use std::collections::HashSet;
@@ -53,20 +53,20 @@ pub fn impl_can_satisfy(infcx: &InferCtxt,
 }
 
 #[allow(missing_copy_implementations)]
-pub enum OrphanCheckErr {
+pub enum OrphanCheckErr<'tcx> {
     NoLocalInputType,
-    UncoveredTypeParameter(ty::ParamTy),
+    UncoveredTy(Ty<'tcx>),
 }
 
 /// Checks the coherence orphan rules. `impl_def_id` should be the
 /// def-id of a trait impl. To pass, either the trait must be local, or else
 /// two conditions must be satisfied:
 ///
-/// 1. At least one of the input types must involve a local type.
-/// 2. All type parameters must be covered by a local type.
-pub fn orphan_check(tcx: &ty::ctxt,
-                    impl_def_id: ast::DefId)
-                    -> Result<(), OrphanCheckErr>
+/// 1. All type parameters in `Self` must be "covered" by some local type constructor.
+/// 2. Some local type must appear in `Self`.
+pub fn orphan_check<'tcx>(tcx: &ty::ctxt<'tcx>,
+                          impl_def_id: ast::DefId)
+                          -> Result<(), OrphanCheckErr<'tcx>>
 {
     debug!("impl_is_local({})", impl_def_id.repr(tcx));
 
@@ -82,31 +82,21 @@ pub fn orphan_check(tcx: &ty::ctxt,
         return Ok(());
     }
 
-    // Check condition 1: at least one type must be local.
-    if !trait_ref.input_types().iter().any(|&t| ty_reaches_local(tcx, t)) {
-        return Err(OrphanCheckErr::NoLocalInputType);
+    // Otherwise, check that (1) all type parameters are covered.
+    let covered_params = type_parameters_covered_by_ty(tcx, trait_ref.self_ty());
+    let all_params = type_parameters_reachable_from_ty(trait_ref.self_ty());
+    for &param in all_params.difference(&covered_params) {
+        return Err(OrphanCheckErr::UncoveredTy(param));
     }
 
-    // Check condition 2: type parameters must be "covered" by a local type.
-    let covered_params: HashSet<_> =
-        trait_ref.input_types().iter()
-                               .flat_map(|&t| type_parameters_covered_by_ty(tcx, t).into_iter())
-                               .collect();
-    let all_params: HashSet<_> =
-        trait_ref.input_types().iter()
-                               .flat_map(|&t| type_parameters_reachable_from_ty(t).into_iter())
-                               .collect();
-    for &param in all_params.difference(&covered_params) {
-        return Err(OrphanCheckErr::UncoveredTypeParameter(param));
+    // And (2) some local type appears.
+    if !trait_ref.self_ty().walk().any(|t| ty_is_local_constructor(tcx, t)) {
+        return Err(OrphanCheckErr::NoLocalInputType);
     }
 
     return Ok(());
 }
 
-fn ty_reaches_local<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
-    ty.walk().any(|t| ty_is_local_constructor(tcx, t))
-}
-
 fn ty_is_local_constructor<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
     debug!("ty_is_local_constructor({})", ty.repr(tcx));
 
@@ -154,8 +144,8 @@ fn ty_is_local_constructor<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
 }
 
 fn type_parameters_covered_by_ty<'tcx>(tcx: &ty::ctxt<'tcx>,
-                                 ty: Ty<'tcx>)
-                                 -> HashSet<ty::ParamTy>
+                                       ty: Ty<'tcx>)
+                                       -> HashSet<Ty<'tcx>>
 {
     if ty_is_local_constructor(tcx, ty) {
         type_parameters_reachable_from_ty(ty)
@@ -165,14 +155,14 @@ fn type_parameters_covered_by_ty<'tcx>(tcx: &ty::ctxt<'tcx>,
 }
 
 /// All type parameters reachable from `ty`
-fn type_parameters_reachable_from_ty<'tcx>(ty: Ty<'tcx>) -> HashSet<ty::ParamTy> {
+fn type_parameters_reachable_from_ty<'tcx>(ty: Ty<'tcx>) -> HashSet<Ty<'tcx>> {
     ty.walk()
-        .filter_map(|t| {
+        .filter(|&t| {
             match t.sty {
-                ty::ty_param(ref param_ty) => Some(param_ty.clone()),
-                _ => None,
+                // FIXME(#20590) straighten story about projection types
+                ty::ty_projection(..) | ty::ty_param(..) => true,
+                _ => false,
             }
         })
         .collect()
 }
-
diff --git a/src/librustc_typeck/check/callee.rs b/src/librustc_typeck/check/callee.rs
index 153c6463fbe..0bc76e1baab 100644
--- a/src/librustc_typeck/check/callee.rs
+++ b/src/librustc_typeck/check/callee.rs
@@ -22,7 +22,7 @@ use super::TupleArgumentsFlag;
 use super::write_call;
 
 use middle::infer;
-use middle::ty::{mod, Ty};
+use middle::ty::{self, Ty};
 use syntax::ast;
 use syntax::codemap::Span;
 use syntax::parse::token;
diff --git a/src/librustc_typeck/coherence/orphan.rs b/src/librustc_typeck/coherence/orphan.rs
index 1da49799712..dc22fd597e6 100644
--- a/src/librustc_typeck/coherence/orphan.rs
+++ b/src/librustc_typeck/coherence/orphan.rs
@@ -72,20 +72,30 @@ impl<'cx, 'tcx,'v> visit::Visitor<'v> for OrphanChecker<'cx, 'tcx> {
             ast::ItemImpl(_, _, Some(_), _, _) => {
                 // "Trait" impl
                 debug!("coherence2::orphan check: trait impl {}", item.repr(self.tcx));
+                let trait_def_id = ty::impl_trait_ref(self.tcx, def_id).unwrap().def_id;
                 match traits::orphan_check(self.tcx, def_id) {
                     Ok(()) => { }
                     Err(traits::OrphanCheckErr::NoLocalInputType) => {
-                        span_err!(self.tcx.sess, item.span, E0117,
-                                  "cannot provide an extension implementation \
-                                   where both trait and type are not defined in this crate");
+                        if !ty::has_attr(self.tcx, trait_def_id, "old_orphan_check") {
+                            let self_ty = ty::lookup_item_type(self.tcx, def_id).ty;
+                            span_err!(
+                                self.tcx.sess, item.span, E0117,
+                                "the type `{}` does not reference any \
+                                 types defined in this crate; \
+                                 only traits defined in the current crate can be \
+                                 implemented for arbitrary types",
+                                self_ty.user_string(self.tcx));
+                        }
                     }
-                    Err(traits::OrphanCheckErr::UncoveredTypeParameter(param_ty)) => {
-                        if !self.tcx.sess.features.borrow().old_orphan_check {
+                    Err(traits::OrphanCheckErr::UncoveredTy(param_ty)) => {
+                        if !ty::has_attr(self.tcx, trait_def_id, "old_orphan_check") {
                             self.tcx.sess.span_err(
                                 item.span,
-                                format!("type parameter `{}` must also appear as a type parameter \
-                                         of some type defined within this crate",
-                                        param_ty.user_string(self.tcx)).as_slice());
+                                format!(
+                                    "type parameter `{}` is not constrained by any local type; \
+                                     only traits defined in the current crate can be implemented \
+                                     for a type parameter",
+                                    param_ty.user_string(self.tcx)).as_slice());
                             self.tcx.sess.span_note(
                                 item.span,
                                 format!("for a limited time, you can add \
diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs
index f75873ac1c0..f08c40ff099 100644
--- a/src/libsyntax/feature_gate.rs
+++ b/src/libsyntax/feature_gate.rs
@@ -301,6 +301,14 @@ impl<'a, 'v> Visitor<'v> for PostExpansionVisitor<'a> {
                                        removed in the future");
                 }
 
+                if attr::contains_name(i.attrs[],
+                                       "old_orphan_check") {
+                    self.gate_feature(
+                        "old_orphan_check",
+                        i.span,
+                        "the new orphan check rules will eventually be strictly enforced");
+                }
+
                 for item in items.iter() {
                     match *item {
                         ast::MethodImplItem(_) => {}
diff --git a/src/test/compile-fail/coherence-all-remote.rs b/src/test/compile-fail/coherence-all-remote.rs
index 67d96aa95a6..d88b8751ea7 100644
--- a/src/test/compile-fail/coherence-all-remote.rs
+++ b/src/test/compile-fail/coherence-all-remote.rs
@@ -14,6 +14,6 @@ extern crate "coherence-lib" as lib;
 use lib::Remote;
 
 impl<T> Remote for int { }
-//~^ ERROR cannot provide an extension implementation
+//~^ ERROR E0117
 
 fn main() { }
diff --git a/src/test/run-pass/coherence-bigint-int.rs b/src/test/compile-fail/coherence-bigint-int.rs
index 1e90453980f..b4917d0c29f 100644
--- a/src/test/run-pass/coherence-bigint-int.rs
+++ b/src/test/compile-fail/coherence-bigint-int.rs
@@ -15,6 +15,6 @@ use lib::Remote1;
 
 pub struct BigInt;
 
-impl Remote1<BigInt> for int { }
+impl Remote1<BigInt> for int { } //~ ERROR E0117
 
 fn main() { }
diff --git a/src/test/compile-fail/coherence-bigint-param.rs b/src/test/compile-fail/coherence-bigint-param.rs
index a04dfd36c98..b8e48436a41 100644
--- a/src/test/compile-fail/coherence-bigint-param.rs
+++ b/src/test/compile-fail/coherence-bigint-param.rs
@@ -16,6 +16,6 @@ use lib::Remote1;
 pub struct BigInt;
 
 impl<T> Remote1<BigInt> for T { }
-//~^ ERROR type parameter `T` must also appear
+//~^ ERROR type parameter `T` is not constrained
 
 fn main() { }
diff --git a/src/test/run-pass/coherence-bigint-vecint.rs b/src/test/compile-fail/coherence-bigint-vecint.rs
index b100455eb33..de4e656110f 100644
--- a/src/test/run-pass/coherence-bigint-vecint.rs
+++ b/src/test/compile-fail/coherence-bigint-vecint.rs
@@ -15,6 +15,6 @@ use lib::Remote1;
 
 pub struct BigInt;
 
-impl Remote1<BigInt> for Vec<int> { }
+impl Remote1<BigInt> for Vec<int> { } //~ ERROR E0117
 
 fn main() { }
diff --git a/src/test/compile-fail/coherence-cross-crate-conflict.rs b/src/test/compile-fail/coherence-cross-crate-conflict.rs
index 99446be43ac..8bdd5c58f31 100644
--- a/src/test/compile-fail/coherence-cross-crate-conflict.rs
+++ b/src/test/compile-fail/coherence-cross-crate-conflict.rs
@@ -16,7 +16,7 @@ extern crate trait_impl_conflict;
 use trait_impl_conflict::Foo;
 
 impl<A> Foo for A {
-    //~^ ERROR E0117
+    //~^ ERROR type parameter `A` is not constrained
     //~^^ ERROR E0119
 }
 
diff --git a/src/test/compile-fail/coherence-lone-type-parameter.rs b/src/test/compile-fail/coherence-lone-type-parameter.rs
index 0223dacd8ec..917438722de 100644
--- a/src/test/compile-fail/coherence-lone-type-parameter.rs
+++ b/src/test/compile-fail/coherence-lone-type-parameter.rs
@@ -13,6 +13,6 @@
 extern crate "coherence-lib" as lib;
 use lib::Remote;
 
-impl<T> Remote for T { } //~ ERROR E0117
+impl<T> Remote for T { } //~ ERROR type parameter `T` is not constrained
 
 fn main() { }
diff --git a/src/test/compile-fail/coherence-orphan.rs b/src/test/compile-fail/coherence-orphan.rs
index c44b0da5b15..30a382c143d 100644
--- a/src/test/compile-fail/coherence-orphan.rs
+++ b/src/test/compile-fail/coherence-orphan.rs
@@ -18,7 +18,7 @@ struct TheType;
 
 impl TheTrait<uint> for int { } //~ ERROR E0117
 
-impl TheTrait<TheType> for int { }
+impl TheTrait<TheType> for int { } //~ ERROR E0117
 
 impl TheTrait<int> for TheType { }
 
diff --git a/src/test/compile-fail/coherence-overlapping-pairs.rs b/src/test/compile-fail/coherence-overlapping-pairs.rs
index d42bd529b66..9354e66af0d 100644
--- a/src/test/compile-fail/coherence-overlapping-pairs.rs
+++ b/src/test/compile-fail/coherence-overlapping-pairs.rs
@@ -16,6 +16,6 @@ use lib::Remote;
 struct Foo;
 
 impl<T> Remote for lib::Pair<T,Foo> { }
-//~^ ERROR type parameter `T` must also appear
+//~^ ERROR type parameter `T` is not constrained
 
 fn main() { }
diff --git a/src/test/compile-fail/coherence-pair-covered-uncovered.rs b/src/test/compile-fail/coherence-pair-covered-uncovered.rs
index 09895ec11db..92a07b35852 100644
--- a/src/test/compile-fail/coherence-pair-covered-uncovered.rs
+++ b/src/test/compile-fail/coherence-pair-covered-uncovered.rs
@@ -16,6 +16,6 @@ use lib::{Remote, Pair};
 struct Local<T>(T);
 
 impl<T,U> Remote for Pair<T,Local<U>> { }
-//~^ ERROR type parameter `T` must also appear
+//~^ ERROR type parameter `T` is not constrained
 
 fn main() { }
diff --git a/src/test/compile-fail/drop-on-non-struct.rs b/src/test/compile-fail/drop-on-non-struct.rs
index 8304afa1141..238700254b8 100644
--- a/src/test/compile-fail/drop-on-non-struct.rs
+++ b/src/test/compile-fail/drop-on-non-struct.rs
@@ -10,7 +10,7 @@
 
 impl Drop for int {
     //~^ ERROR the Drop trait may only be implemented on structures
-    //~^^ ERROR cannot provide an extension implementation
+    //~^^ ERROR E0117
     fn drop(&mut self) {
         println!("kaboom");
     }
diff --git a/src/test/compile-fail/coherence-iterator-vec-any-elem.rs b/src/test/run-pass/coherence-iterator-vec-any-elem.rs
index 2ed7a6db7ae..6dc2ff4588b 100644
--- a/src/test/compile-fail/coherence-iterator-vec-any-elem.rs
+++ b/src/test/run-pass/coherence-iterator-vec-any-elem.rs
@@ -16,6 +16,5 @@ use lib::Remote1;
 struct Foo<T>(T);
 
 impl<T,U> Remote1<U> for Foo<T> { }
-//~^ ERROR type parameter `U` must also appear
 
 fn main() { }