rollup merge of #20416: nikomatsakis/coherence

Conflicts:
	src/test/run-pass/issue-15734.rs
	src/test/run-pass/issue-3743.rs

45 files changed, 705 insertions, 172 deletions

diff --git a/src/liballoc/lib.rs b/src/liballoc/lib.rs
index 61b5d43d1cb..d17a54ce6e5 100644
--- a/src/liballoc/lib.rs
+++ b/src/liballoc/lib.rs
@@ -64,7 +64,8 @@
        html_root_url = "http://doc.rust-lang.org/nightly/")]
 
 #![no_std]
-#![feature(lang_items, phase, unsafe_destructor, default_type_params)]
+#![allow(unknown_features)]
+#![feature(lang_items, phase, unsafe_destructor, default_type_params, old_orphan_check)]
 
 #[phase(plugin, link)]
 extern crate core;
diff --git a/src/libcollections/lib.rs b/src/libcollections/lib.rs
index cbd8d4955b2..82175c39494 100644
--- a/src/libcollections/lib.rs
+++ b/src/libcollections/lib.rs
@@ -25,6 +25,7 @@
 #![feature(macro_rules, default_type_params, phase, globs)]
 #![feature(unsafe_destructor, slicing_syntax)]
 #![feature(unboxed_closures)]
+#![feature(old_orphan_check)]
 #![no_std]
 
 #[phase(plugin, link)] extern crate core;
diff --git a/src/libgraphviz/maybe_owned_vec.rs b/src/libgraphviz/maybe_owned_vec.rs
index 573f0926e29..d0396ddc7ad 100644
--- a/src/libgraphviz/maybe_owned_vec.rs
+++ b/src/libgraphviz/maybe_owned_vec.rs
@@ -98,9 +98,9 @@ impl<'a, T: Ord> Ord for MaybeOwnedVector<'a, T> {
 }
 
 #[allow(deprecated)]
-impl<'a, T: PartialEq, Sized? V: AsSlice<T>> Equiv<V> for MaybeOwnedVector<'a, T> {
-    fn equiv(&self, other: &V) -> bool {
-        self.as_slice() == other.as_slice()
+impl<'a, T: PartialEq> Equiv<[T]> for MaybeOwnedVector<'a, T> {
+    fn equiv(&self, other: &[T]) -> bool {
+        self.as_slice() == other
     }
 }
 
diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index 4647c92e3d1..cdc27244dde 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -22,10 +22,12 @@
       html_favicon_url = "http://www.rust-lang.org/favicon.ico",
       html_root_url = "http://doc.rust-lang.org/nightly/")]
 
+#![allow(unknown_features)]
 #![feature(default_type_params, globs, macro_rules, phase, quote)]
 #![feature(slicing_syntax, unsafe_destructor)]
 #![feature(rustc_diagnostic_macros)]
 #![feature(unboxed_closures)]
+#![feature(old_orphan_check)]
 
 extern crate arena;
 extern crate flate;
@@ -98,6 +100,7 @@ pub mod middle {
     pub mod traits;
     pub mod ty;
     pub mod ty_fold;
+    pub mod ty_walk;
     pub mod weak_lang_items;
 }
 
diff --git a/src/librustc/metadata/decoder.rs b/src/librustc/metadata/decoder.rs
index 0917135bee9..a25b6d8b8fa 100644
--- a/src/librustc/metadata/decoder.rs
+++ b/src/librustc/metadata/decoder.rs
@@ -443,9 +443,15 @@ pub fn get_impl_trait<'tcx>(cdata: Cmd,
                             -> Option<Rc<ty::TraitRef<'tcx>>>
 {
     let item_doc = lookup_item(id, cdata.data());
-    reader::maybe_get_doc(item_doc, tag_item_trait_ref).map(|tp| {
-        doc_trait_ref(tp, tcx, cdata)
-    })
+    let fam = item_family(item_doc);
+    match fam {
+        Family::Impl => {
+            reader::maybe_get_doc(item_doc, tag_item_trait_ref).map(|tp| {
+                doc_trait_ref(tp, tcx, cdata)
+            })
+        }
+        _ => None
+    }
 }
 
 pub fn get_impl_vtables<'tcx>(cdata: Cmd,
diff --git a/src/librustc/middle/stability.rs b/src/librustc/middle/stability.rs
index d793f49efe5..505352fa123 100644
--- a/src/librustc/middle/stability.rs
+++ b/src/librustc/middle/stability.rs
@@ -11,7 +11,8 @@
 //! A pass that annotates every item and method with its stability level,
 //! propagating default levels lexically from parent to children ast nodes.
 
-use util::nodemap::{NodeMap, DefIdMap};
+use middle::ty;
+use metadata::csearch;
 use syntax::codemap::Span;
 use syntax::{attr, visit};
 use syntax::ast;
@@ -21,8 +22,8 @@ use syntax::ast::{TypeMethod, Method, Generics, StructField, TypeTraitItem};
 use syntax::ast_util::is_local;
 use syntax::attr::Stability;
 use syntax::visit::{FnKind, FkMethod, Visitor};
-use middle::ty;
-use metadata::csearch;
+use util::nodemap::{NodeMap, DefIdMap};
+use util::ppaux::Repr;
 
 use std::mem::replace;
 
@@ -154,10 +155,13 @@ impl Index {
 /// Lookup the stability for a node, loading external crate
 /// metadata as necessary.
 pub fn lookup(tcx: &ty::ctxt, id: DefId) -> Option<Stability> {
+    debug!("lookup(id={})",
+           id.repr(tcx));
+
     // is this definition the implementation of a trait method?
     match ty::trait_item_of_item(tcx, id) {
-        Some(ty::MethodTraitItemId(trait_method_id))
-                if trait_method_id != id => {
+        Some(ty::MethodTraitItemId(trait_method_id)) if trait_method_id != id => {
+            debug!("lookup: trait_method_id={}", trait_method_id);
             return lookup(tcx, trait_method_id)
         }
         _ => {}
@@ -178,6 +182,7 @@ pub fn lookup(tcx: &ty::ctxt, id: DefId) -> Option<Stability> {
             // stability of the trait to determine the stability of any
             // unmarked impls for it. See FIXME above for more details.
 
+            debug!("lookup: trait_id={}", trait_id);
             lookup(tcx, trait_id)
         } else {
             None
diff --git a/src/librustc/middle/traits/coherence.rs b/src/librustc/middle/traits/coherence.rs
index d8b39d92c69..4aff36c2624 100644
--- a/src/librustc/middle/traits/coherence.rs
+++ b/src/librustc/middle/traits/coherence.rs
@@ -14,10 +14,10 @@ use super::SelectionContext;
 use super::{Obligation, ObligationCause};
 use super::util;
 
-use middle::subst;
 use middle::subst::Subst;
 use middle::ty::{mod, Ty};
 use middle::infer::InferCtxt;
+use std::collections::HashSet;
 use std::rc::Rc;
 use syntax::ast;
 use syntax::codemap::DUMMY_SP;
@@ -52,9 +52,21 @@ pub fn impl_can_satisfy(infcx: &InferCtxt,
     selcx.evaluate_impl(impl2_def_id, &obligation)
 }
 
-pub fn impl_is_local(tcx: &ty::ctxt,
-                     impl_def_id: ast::DefId)
-                     -> bool
+#[allow(missing_copy_implementations)]
+pub enum OrphanCheckErr {
+    NoLocalInputType,
+    UncoveredTypeParameter(ty::ParamTy),
+}
+
+/// 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>
 {
     debug!("impl_is_local({})", impl_def_id.repr(tcx));
 
@@ -63,20 +75,40 @@ pub fn impl_is_local(tcx: &ty::ctxt,
     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 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;
+        return Ok(());
     }
 
-    // Otherwise, at least one of the input types must be local to the
-    // crate.
-    trait_ref.input_types().iter().any(|&t| ty_is_local(tcx, t))
+    // 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);
+    }
+
+    // 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));
+    }
+
+    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))
 }
 
-pub fn ty_is_local<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
-    debug!("ty_is_local({})", ty.repr(tcx));
+fn ty_is_local_constructor<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
+    debug!("ty_is_local_constructor({})", ty.repr(tcx));
 
     match ty.sty {
         ty::ty_bool |
@@ -84,78 +116,33 @@ pub fn ty_is_local<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
         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_str(..) |
         ty::ty_bare_fn(..) |
-        ty::ty_closure(..) => {
+        ty::ty_closure(..) |
+        ty::ty_vec(..) |
+        ty::ty_ptr(..) |
+        ty::ty_rptr(..) |
+        ty::ty_tup(..) |
+        ty::ty_param(..) |
+        ty::ty_projection(..) => {
             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_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, _) |
+        ty::ty_struct(def_id, _) => {
+            def_id.krate == ast::LOCAL_CRATE
         }
 
-        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_uniq(_) => { // treat ~T like Box<T>
+            let krate = tcx.lang_items.owned_box().map(|d| d.krate);
+            krate == Some(ast::LOCAL_CRATE)
         }
 
         ty::ty_trait(ref tt) => {
             tt.principal_def_id().krate == ast::LOCAL_CRATE
         }
 
-        // Type parameters may be bound to types that are not local to
-        // the crate.
-        ty::ty_param(..) => {
-            false
-        }
-
-        // Associated types could be anything, I guess.
-        ty::ty_projection(..) => {
-            false
-        }
-
+        ty::ty_unboxed_closure(..) |
         ty::ty_infer(..) |
         ty::ty_open(..) |
         ty::ty_err => {
@@ -165,3 +152,27 @@ pub fn ty_is_local<'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>
+{
+    if ty_is_local_constructor(tcx, ty) {
+        type_parameters_reachable_from_ty(ty)
+    } else {
+        ty.walk_children().flat_map(|t| type_parameters_covered_by_ty(tcx, t).into_iter()).collect()
+    }
+}
+
+/// All type parameters reachable from `ty`
+fn type_parameters_reachable_from_ty<'tcx>(ty: Ty<'tcx>) -> HashSet<ty::ParamTy> {
+    ty.walk()
+        .filter_map(|t| {
+            match t.sty {
+                ty::ty_param(ref param_ty) => Some(param_ty.clone()),
+                _ => None,
+            }
+        })
+        .collect()
+}
+
diff --git a/src/librustc/middle/traits/mod.rs b/src/librustc/middle/traits/mod.rs
index b10dfa5b718..fc2eb43c8a5 100644
--- a/src/librustc/middle/traits/mod.rs
+++ b/src/librustc/middle/traits/mod.rs
@@ -25,6 +25,8 @@ use syntax::codemap::{Span, DUMMY_SP};
 use util::ppaux::Repr;
 
 pub use self::error_reporting::report_fulfillment_errors;
+pub use self::coherence::orphan_check;
+pub use self::coherence::OrphanCheckErr;
 pub use self::fulfill::{FulfillmentContext, RegionObligation};
 pub use self::project::MismatchedProjectionTypes;
 pub use self::project::normalize;
@@ -245,15 +247,6 @@ pub struct VtableBuiltinData<N> {
     pub nested: subst::VecPerParamSpace<N>
 }
 
-/// True if neither the trait nor self type is local. Note that `impl_def_id` must refer to an impl
-/// of a trait, not an inherent impl.
-pub fn is_orphan_impl(tcx: &ty::ctxt,
-                      impl_def_id: ast::DefId)
-                      -> bool
-{
-    !coherence::impl_is_local(tcx, impl_def_id)
-}
-
 /// True if there exist types that satisfy both of the two given impls.
 pub fn overlapping_impls(infcx: &InferCtxt,
                          impl1_def_id: ast::DefId,
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index e699ee2ec91..26a9cc5464e 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -59,6 +59,7 @@ use middle::subst::{mod, Subst, Substs, VecPerParamSpace};
 use middle::traits;
 use middle::ty;
 use middle::ty_fold::{mod, TypeFoldable, TypeFolder};
+use middle::ty_walk::TypeWalker;
 use util::ppaux::{note_and_explain_region, bound_region_ptr_to_string};
 use util::ppaux::{trait_store_to_string, ty_to_string};
 use util::ppaux::{Repr, UserString};
@@ -2831,59 +2832,61 @@ pub fn mk_param_from_def<'tcx>(cx: &ctxt<'tcx>, def: &TypeParameterDef) -> Ty<'t
 
 pub fn mk_open<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> { mk_t(cx, ty_open(ty)) }
 
-pub fn walk_ty<'tcx, F>(ty: Ty<'tcx>, mut f: F) where
-    F: FnMut(Ty<'tcx>),
+impl<'tcx> TyS<'tcx> {
+    /// Iterator that walks `self` and any types reachable from
+    /// `self`, in depth-first order. Note that just walks the types
+    /// that appear in `self`, it does not descend into the fields of
+    /// structs or variants. For example:
+    ///
+    /// ```notrust
+    /// int => { int }
+    /// Foo<Bar<int>> => { Foo<Bar<int>>, Bar<int>, int }
+    /// [int] => { [int], int }
+    /// ```
+    pub fn walk(&'tcx self) -> TypeWalker<'tcx> {
+        TypeWalker::new(self)
+    }
+
+    /// Iterator that walks types reachable from `self`, in
+    /// depth-first order. Note that this is a shallow walk. For
+    /// example:
+    ///
+    /// ```notrust
+    /// int => { }
+    /// Foo<Bar<int>> => { Bar<int>, int }
+    /// [int] => { int }
+    /// ```
+    pub fn walk_children(&'tcx self) -> TypeWalker<'tcx> {
+        // Walks type reachable from `self` but not `self
+        let mut walker = self.walk();
+        let r = walker.next();
+        assert_eq!(r, Some(self));
+        walker
+    }
+}
+
+pub fn walk_ty<'tcx, F>(ty_root: Ty<'tcx>, mut f: F)
+    where F: FnMut(Ty<'tcx>),
 {
-    maybe_walk_ty(ty, |ty| { f(ty); true });
+    for ty in ty_root.walk() {
+        f(ty);
+    }
 }
 
-pub fn maybe_walk_ty<'tcx, F>(ty: Ty<'tcx>, mut f: F) where F: FnMut(Ty<'tcx>) -> bool {
-    // FIXME(#19596) This is a workaround, but there should be a better way to do this
-    fn maybe_walk_ty_<'tcx, F>(ty: Ty<'tcx>, f: &mut F) where F: FnMut(Ty<'tcx>) -> bool {
-        if !(*f)(ty) {
-            return;
-        }
-        match ty.sty {
-            ty_bool | ty_char | ty_int(_) | ty_uint(_) | ty_float(_) |
-            ty_str | ty_infer(_) | ty_param(_) | ty_err => {}
-            ty_uniq(ty) | ty_vec(ty, _) | ty_open(ty) => maybe_walk_ty_(ty, f),
-            ty_ptr(ref tm) | ty_rptr(_, ref tm) => {
-                maybe_walk_ty_(tm.ty, f);
-            }
-            ty_trait(box TyTrait { ref principal, .. }) => {
-                for subty in principal.0.substs.types.iter() {
-                    maybe_walk_ty_(*subty, f);
-                }
-            }
-            ty_projection(ProjectionTy { ref trait_ref, .. }) => {
-                for subty in trait_ref.substs.types.iter() {
-                    maybe_walk_ty_(*subty, f);
-                }
-            }
-            ty_enum(_, ref substs) |
-            ty_struct(_, ref substs) |
-            ty_unboxed_closure(_, _, ref substs) => {
-                for subty in substs.types.iter() {
-                    maybe_walk_ty_(*subty, f);
-                }
-            }
-            ty_tup(ref ts) => { for tt in ts.iter() { maybe_walk_ty_(*tt, f); } }
-            ty_bare_fn(_, ref ft) => {
-                for a in ft.sig.0.inputs.iter() { maybe_walk_ty_(*a, f); }
-                if let ty::FnConverging(output) = ft.sig.0.output {
-                    maybe_walk_ty_(output, f);
-                }
-            }
-            ty_closure(ref ft) => {
-                for a in ft.sig.0.inputs.iter() { maybe_walk_ty_(*a, f); }
-                if let ty::FnConverging(output) = ft.sig.0.output {
-                    maybe_walk_ty_(output, f);
-                }
-            }
+/// Walks `ty` and any types appearing within `ty`, invoking the
+/// callback `f` on each type. If the callback returns false, then the
+/// children of the current type are ignored.
+///
+/// Note: prefer `ty.walk()` where possible.
+pub fn maybe_walk_ty<'tcx,F>(ty_root: Ty<'tcx>, mut f: F)
+    where F : FnMut(Ty<'tcx>) -> bool
+{
+    let mut walker = ty_root.walk();
+    while let Some(ty) = walker.next() {
+        if !f(ty) {
+            walker.skip_current_subtree();
         }
     }
-
-    maybe_walk_ty_(ty, &mut f);
 }
 
 // Folds types from the bottom up.
@@ -6122,22 +6125,9 @@ pub fn populate_implementations_for_trait_if_necessary(
 /// Given the def_id of an impl, return the def_id of the trait it implements.
 /// If it implements no trait, return `None`.
 pub fn trait_id_of_impl(tcx: &ctxt,
-                        def_id: ast::DefId) -> Option<ast::DefId> {
-    let node = match tcx.map.find(def_id.node) {
-        Some(node) => node,
-        None => return None
-    };
-    match node {
-        ast_map::NodeItem(item) => {
-            match item.node {
-                ast::ItemImpl(_, _, Some(ref trait_ref), _, _) => {
-                    Some(node_id_to_trait_ref(tcx, trait_ref.ref_id).def_id)
-                }
-                _ => None
-            }
-        }
-        _ => None
-    }
+                        def_id: ast::DefId)
+                        -> Option<ast::DefId> {
+    ty::impl_trait_ref(tcx, def_id).map(|tr| tr.def_id)
 }
 
 /// If the given def ID describes a method belonging to an impl, return the
diff --git a/src/librustc/middle/ty_walk.rs b/src/librustc/middle/ty_walk.rs
new file mode 100644
index 00000000000..406ebf4bc38
--- /dev/null
+++ b/src/librustc/middle/ty_walk.rs
@@ -0,0 +1,112 @@
+// Copyright 2012-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.
+
+//! An iterator over the type substructure.
+
+use middle::ty::{mod, Ty};
+use std::iter::Iterator;
+
+pub struct TypeWalker<'tcx> {
+    stack: Vec<Ty<'tcx>>,
+    last_subtree: uint,
+}
+
+impl<'tcx> TypeWalker<'tcx> {
+    pub fn new(ty: Ty<'tcx>) -> TypeWalker<'tcx> {
+        TypeWalker { stack: vec!(ty), last_subtree: 1, }
+    }
+
+    fn push_subtypes(&mut self, parent_ty: Ty<'tcx>) {
+        match parent_ty.sty {
+            ty::ty_bool | ty::ty_char | ty::ty_int(_) | ty::ty_uint(_) | ty::ty_float(_) |
+            ty::ty_str | ty::ty_infer(_) | ty::ty_param(_) | ty::ty_err => {
+            }
+            ty::ty_uniq(ty) | ty::ty_vec(ty, _) | ty::ty_open(ty) => {
+                self.stack.push(ty);
+            }
+            ty::ty_ptr(ref mt) | ty::ty_rptr(_, ref mt) => {
+                self.stack.push(mt.ty);
+            }
+            ty::ty_projection(ref data) => {
+                self.push_reversed(data.trait_ref.substs.types.as_slice());
+            }
+            ty::ty_trait(box ty::TyTrait { ref principal, .. }) => {
+                self.push_reversed(principal.substs().types.as_slice());
+            }
+            ty::ty_enum(_, ref substs) |
+            ty::ty_struct(_, ref substs) |
+            ty::ty_unboxed_closure(_, _, ref substs) => {
+                self.push_reversed(substs.types.as_slice());
+            }
+            ty::ty_tup(ref ts) => {
+                self.push_reversed(ts.as_slice());
+            }
+            ty::ty_bare_fn(_, ref ft) => {
+                self.push_sig_subtypes(&ft.sig);
+            }
+            ty::ty_closure(ref ft) => {
+                self.push_sig_subtypes(&ft.sig);
+            }
+        }
+    }
+
+    fn push_sig_subtypes(&mut self, sig: &ty::PolyFnSig<'tcx>) {
+        match sig.0.output {
+            ty::FnConverging(output) => { self.stack.push(output); }
+            ty::FnDiverging => { }
+        }
+        self.push_reversed(sig.0.inputs.as_slice());
+    }
+
+    fn push_reversed(&mut self, tys: &[Ty<'tcx>]) {
+        // We push slices on the stack in reverse order so as to
+        // maintain a pre-order traversal. As of the time of this
+        // writing, the fact that the traversal is pre-order is not
+        // known to be significant to any code, but it seems like the
+        // natural order one would expect (basically, the order of the
+        // types as they are written).
+        for &ty in tys.iter().rev() {
+            self.stack.push(ty);
+        }
+    }
+
+    /// Skips the subtree of types corresponding to the last type
+    /// returned by `next()`.
+    ///
+    /// Example: Imagine you are walking `Foo<Bar<int>, uint>`.
+    ///
+    /// ```rust
+    /// let mut iter: TypeWalker = ...;
+    /// iter.next(); // yields Foo
+    /// iter.next(); // yields Bar<int>
+    /// iter.skip_current_subtree(); // skips int
+    /// iter.next(); // yields uint
+    /// ```
+    pub fn skip_current_subtree(&mut self) {
+        self.stack.truncate(self.last_subtree);
+    }
+}
+
+impl<'tcx> Iterator<Ty<'tcx>> for TypeWalker<'tcx> {
+    fn next(&mut self) -> Option<Ty<'tcx>> {
+        debug!("next(): stack={}", self.stack);
+        match self.stack.pop() {
+            None => {
+                return None;
+            }
+            Some(ty) => {
+                self.last_subtree = self.stack.len();
+                self.push_subtypes(ty);
+                debug!("next: stack={}", self.stack);
+                Some(ty)
+            }
+        }
+    }
+}
diff --git a/src/librustc_back/lib.rs b/src/librustc_back/lib.rs
index cb547df7d9c..2bb99a7141f 100644
--- a/src/librustc_back/lib.rs
+++ b/src/librustc_back/lib.rs
@@ -32,6 +32,7 @@
 #![allow(unknown_features)]
 #![feature(globs, phase, macro_rules, slicing_syntax)]
 #![feature(unboxed_closures)]
+#![feature(old_orphan_check)]
 
 #[phase(plugin, link)]
 extern crate log;
diff --git a/src/librustc_borrowck/lib.rs b/src/librustc_borrowck/lib.rs
index 664d470b11b..b886883c73a 100644
--- a/src/librustc_borrowck/lib.rs
+++ b/src/librustc_borrowck/lib.rs
@@ -16,10 +16,12 @@
       html_favicon_url = "http://www.rust-lang.org/favicon.ico",
       html_root_url = "http://doc.rust-lang.org/nightly/")]
 
+#![allow(unknown_features)]
 #![feature(default_type_params, globs, macro_rules, phase, quote)]
 #![feature(slicing_syntax, unsafe_destructor)]
 #![feature(rustc_diagnostic_macros)]
 #![feature(unboxed_closures)]
+#![feature(old_orphan_check)]
 #![allow(non_camel_case_types)]
 
 #[phase(plugin, link)] extern crate log;
diff --git a/src/librustc_driver/test.rs b/src/librustc_driver/test.rs
index 6329acfb578..eddcc750068 100644
--- a/src/librustc_driver/test.rs
+++ b/src/librustc_driver/test.rs
@@ -34,8 +34,6 @@ use syntax::codemap::{Span, CodeMap, DUMMY_SP};
 use syntax::diagnostic::{Level, RenderSpan, Bug, Fatal, Error, Warning, Note, Help};
 use syntax::parse::token;
 
-use arena::TypedArena;
-
 struct Env<'a, 'tcx: 'a> {
     infcx: &'a infer::InferCtxt<'a, 'tcx>,
 }
@@ -831,3 +829,57 @@ fn subst_region_renumber_region() {
         assert_eq!(t_substituted, t_expected);
     })
 }
+
+#[test]
+fn walk_ty() {
+    test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
+        let tcx = env.infcx.tcx;
+        let int_ty = tcx.types.int;
+        let uint_ty = tcx.types.uint;
+        let tup1_ty = ty::mk_tup(tcx, vec!(int_ty, uint_ty, int_ty, uint_ty));
+        let tup2_ty = ty::mk_tup(tcx, vec!(tup1_ty, tup1_ty, uint_ty));
+        let uniq_ty = ty::mk_uniq(tcx, tup2_ty);
+        let walked: Vec<_> = uniq_ty.walk().collect();
+        assert_eq!(vec!(uniq_ty,
+                        tup2_ty,
+                        tup1_ty, int_ty, uint_ty, int_ty, uint_ty,
+                        tup1_ty, int_ty, uint_ty, int_ty, uint_ty,
+                        uint_ty),
+                   walked);
+    })
+}
+
+#[test]
+fn walk_ty_skip_subtree() {
+    test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
+        let tcx = env.infcx.tcx;
+        let int_ty = tcx.types.int;
+        let uint_ty = tcx.types.uint;
+        let tup1_ty = ty::mk_tup(tcx, vec!(int_ty, uint_ty, int_ty, uint_ty));
+        let tup2_ty = ty::mk_tup(tcx, vec!(tup1_ty, tup1_ty, uint_ty));
+        let uniq_ty = ty::mk_uniq(tcx, tup2_ty);
+
+        // types we expect to see (in order), plus a boolean saying
+        // whether to skip the subtree.
+        let mut expected = vec!((uniq_ty, false),
+                                (tup2_ty, false),
+                                (tup1_ty, false),
+                                (int_ty, false),
+                                (uint_ty, false),
+                                (int_ty, false),
+                                (uint_ty, false),
+                                (tup1_ty, true), // skip the int/uint/int/uint
+                                (uint_ty, false));
+        expected.reverse();
+
+        let mut walker = uniq_ty.walk();
+        while let Some(t) = walker.next() {
+            debug!("walked to {}", t);
+            let (expected_ty, skip) = expected.pop().unwrap();
+            assert_eq!(t, expected_ty);
+            if skip { walker.skip_current_subtree(); }
+        }
+
+        assert!(expected.is_empty());
+    })
+}
diff --git a/src/librustc_trans/lib.rs b/src/librustc_trans/lib.rs
index 784002287b7..5ffe9b2d647 100644
--- a/src/librustc_trans/lib.rs
+++ b/src/librustc_trans/lib.rs
@@ -22,10 +22,12 @@
       html_favicon_url = "http://www.rust-lang.org/favicon.ico",
       html_root_url = "http://doc.rust-lang.org/nightly/")]
 
+#![allow(unknown_features)]
 #![feature(default_type_params, globs, macro_rules, phase, quote)]
 #![feature(slicing_syntax, unsafe_destructor)]
 #![feature(rustc_diagnostic_macros)]
 #![feature(unboxed_closures)]
+#![feature(old_orphan_check)]
 
 extern crate arena;
 extern crate flate;
diff --git a/src/librustc_typeck/coherence/orphan.rs b/src/librustc_typeck/coherence/orphan.rs
index 49f150cf027..1da49799712 100644
--- a/src/librustc_typeck/coherence/orphan.rs
+++ b/src/librustc_typeck/coherence/orphan.rs
@@ -18,7 +18,7 @@ use syntax::ast;
 use syntax::ast_util;
 use syntax::codemap::Span;
 use syntax::visit;
-use util::ppaux::Repr;
+use util::ppaux::{Repr, UserString};
 
 pub fn check(tcx: &ty::ctxt) {
     let mut orphan = OrphanChecker { tcx: tcx };
@@ -72,10 +72,27 @@ 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));
-                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");
+                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");
+                    }
+                    Err(traits::OrphanCheckErr::UncoveredTypeParameter(param_ty)) => {
+                        if !self.tcx.sess.features.borrow().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());
+                            self.tcx.sess.span_note(
+                                item.span,
+                                format!("for a limited time, you can add \
+                                         `#![feature(old_orphan_check)]` to your crate \
+                                         to disable this rule").as_slice());
+                        }
+                    }
                 }
             }
             _ => {
diff --git a/src/librustdoc/lib.rs b/src/librustdoc/lib.rs
index 8eb4448c649..1beeeaf629d 100644
--- a/src/librustdoc/lib.rs
+++ b/src/librustdoc/lib.rs
@@ -20,6 +20,7 @@
 #![allow(unknown_features)]
 #![feature(globs, macro_rules, phase, slicing_syntax)]
 #![feature(unboxed_closures)]
+#![feature(old_orphan_check)]
 
 extern crate arena;
 extern crate getopts;
diff --git a/src/libserialize/json.rs b/src/libserialize/json.rs
index 2c83807aa4f..e0122ad106f 100644
--- a/src/libserialize/json.rs
+++ b/src/libserialize/json.rs
@@ -76,12 +76,13 @@
 //! Create a struct called `TestStruct` and serialize and deserialize it to and from JSON using the
 //! serialization API, using the derived serialization code.
 //!
-//! ```rust
+//! ```notrust
+//! // FIXME(#19470): this cannot be ```rust``` because it fails orphan checking at the moment
 //! extern crate serialize;
 //! use serialize::json;
 //!
 //! // Automatically generate `Decodable` and `Encodable` trait implementations
-//! #[deriving(Decodable, Encodable)]
+//! #[deriving(RustcDecodable, RustcEncodable)]
 //! pub struct TestStruct  {
 //!     data_int: u8,
 //!     data_str: String,
@@ -110,7 +111,8 @@
 //!
 //! ### Simple example of `ToJson` usage
 //!
-//! ```rust
+//! ```notrust
+//! // FIXME(#19470): this cannot be ```rust``` because it fails orphan checking at the moment
 //! extern crate serialize;
 //! use serialize::json::{mod, ToJson, Json};
 //!
@@ -149,7 +151,8 @@
 //!
 //! ### Verbose example of `ToJson` usage
 //!
-//! ```rust
+//! ```notrust
+//! // FIXME(#19470): this cannot be ```rust``` because it fails orphan checking at the moment
 //! extern crate serialize;
 //! use std::collections::BTreeMap;
 //! use serialize::json::{mod, Json, ToJson};
diff --git a/src/libstd/lib.rs b/src/libstd/lib.rs
index 6187593afd1..848d3604953 100644
--- a/src/libstd/lib.rs
+++ b/src/libstd/lib.rs
@@ -107,6 +107,7 @@
 #![feature(macro_rules, globs, linkage, thread_local, asm)]
 #![feature(default_type_params, phase, lang_items, unsafe_destructor)]
 #![feature(slicing_syntax, unboxed_closures)]
+#![feature(old_orphan_check)]
 
 // Don't link to std. We are std.
 #![no_std]
diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs
index 035b748a7db..545856a27af 100644
--- a/src/libsyntax/feature_gate.rs
+++ b/src/libsyntax/feature_gate.rs
@@ -78,8 +78,11 @@ static KNOWN_FEATURES: &'static [(&'static str, Status)] = &[
     // to bootstrap fix for #5723.
     ("issue_5723_bootstrap", Accepted),
 
-    // A way to temporary opt out of opt in copy. This will *never* be accepted.
-    ("opt_out_copy", Active),
+    // A way to temporarily opt out of opt in copy. This will *never* be accepted.
+    ("opt_out_copy", Deprecated),
+
+    // A way to temporarily opt out of the new orphan rules. This will *never* be accepted.
+    ("old_orphan_check", Deprecated),
 
     // These are used to test this portion of the compiler, they don't actually
     // mean anything
@@ -92,6 +95,10 @@ enum Status {
     /// currently being considered for addition/removal.
     Active,
 
+    /// Represents a feature gate that is temporarily enabling deprecated behavior.
+    /// This gate will never be accepted.
+    Deprecated,
+
     /// Represents a feature which has since been removed (it was once Active)
     Removed,
 
@@ -109,6 +116,7 @@ pub struct Features {
     pub visible_private_types: bool,
     pub quote: bool,
     pub opt_out_copy: bool,
+    pub old_orphan_check: bool,
 }
 
 impl Features {
@@ -121,6 +129,7 @@ impl Features {
             visible_private_types: false,
             quote: false,
             opt_out_copy: false,
+            old_orphan_check: false,
         }
     }
 }
@@ -453,7 +462,16 @@ fn check_crate_inner<F>(cm: &CodeMap, span_handler: &SpanHandler, krate: &ast::C
                     };
                     match KNOWN_FEATURES.iter()
                                         .find(|& &(n, _)| name == n) {
-                        Some(&(name, Active)) => { cx.features.push(name); }
+                        Some(&(name, Active)) => {
+                            cx.features.push(name);
+                        }
+                        Some(&(name, Deprecated)) => {
+                            cx.features.push(name);
+                            span_handler.span_warn(
+                                mi.span,
+                                "feature is deprecated and will only be available \
+                                 for a limited time, please rewrite code that relies on it");
+                        }
                         Some(&(_, Removed)) => {
                             span_handler.span_err(mi.span, "feature has been removed");
                         }
@@ -480,6 +498,7 @@ fn check_crate_inner<F>(cm: &CodeMap, span_handler: &SpanHandler, krate: &ast::C
         visible_private_types: cx.has_feature("visible_private_types"),
         quote: cx.has_feature("quote"),
         opt_out_copy: cx.has_feature("opt_out_copy"),
+        old_orphan_check: cx.has_feature("old_orphan_check"),
     },
     unknown_features)
 }
diff --git a/src/libsyntax/lib.rs b/src/libsyntax/lib.rs
index d5093c5055c..7a6824ac27c 100644
--- a/src/libsyntax/lib.rs
+++ b/src/libsyntax/lib.rs
@@ -26,6 +26,7 @@
 #![feature(macro_rules, globs, default_type_params, phase, slicing_syntax)]
 #![feature(quote, unsafe_destructor)]
 #![feature(unboxed_closures)]
+#![feature(old_orphan_check)]
 
 extern crate arena;
 extern crate fmt_macros;
diff --git a/src/libtest/lib.rs b/src/libtest/lib.rs
index 2ea5ee3e16d..b2d3611fc64 100644
--- a/src/libtest/lib.rs
+++ b/src/libtest/lib.rs
@@ -31,8 +31,10 @@
        html_favicon_url = "http://www.rust-lang.org/favicon.ico",
        html_root_url = "http://doc.rust-lang.org/nightly/")]
 
+#![allow(unknown_features)]
 #![feature(asm, macro_rules, phase, globs, slicing_syntax)]
 #![feature(unboxed_closures, default_type_params)]
+#![feature(old_orphan_check)]
 
 extern crate getopts;
 extern crate regex;
diff --git a/src/libtime/lib.rs b/src/libtime/lib.rs
index d9db2d80ada..bc5d0c21aae 100644
--- a/src/libtime/lib.rs
+++ b/src/libtime/lib.rs
@@ -20,7 +20,10 @@
        html_favicon_url = "http://www.rust-lang.org/favicon.ico",
        html_root_url = "http://doc.rust-lang.org/nightly/",
        html_playground_url = "http://play.rust-lang.org/")]
+
+#![allow(unknown_features)]
 #![feature(phase, globs)]
+#![feature(old_orphan_check)]
 
 #[cfg(test)] #[phase(plugin, link)] extern crate log;
 
diff --git a/src/test/auxiliary/coherence-lib.rs b/src/test/auxiliary/coherence-lib.rs
new file mode 100644
index 00000000000..daa123849e4
--- /dev/null
+++ b/src/test/auxiliary/coherence-lib.rs
@@ -0,0 +1,25 @@
+// Copyright 2012 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.
+
+#![crate_type="lib"]
+
+pub trait Remote {
+    fn foo(&self) { }
+}
+
+pub trait Remote1<T> {
+    fn foo(&self, t: T) { }
+}
+
+pub trait Remote2<T, U> {
+    fn foo(&self, t: T, u: U) { }
+}
+
+pub struct Pair<T,U>(T,U);
diff --git a/src/test/compile-fail/coherence-all-remote.rs b/src/test/compile-fail/coherence-all-remote.rs
new file mode 100644
index 00000000000..67d96aa95a6
--- /dev/null
+++ b/src/test/compile-fail/coherence-all-remote.rs
@@ -0,0 +1,19 @@
+// 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.
+
+// aux-build:coherence-lib.rs
+
+extern crate "coherence-lib" as lib;
+use lib::Remote;
+
+impl<T> Remote for int { }
+//~^ ERROR cannot provide an extension implementation
+
+fn main() { }
diff --git a/src/test/compile-fail/coherence-bigint-param.rs b/src/test/compile-fail/coherence-bigint-param.rs
new file mode 100644
index 00000000000..a04dfd36c98
--- /dev/null
+++ b/src/test/compile-fail/coherence-bigint-param.rs
@@ -0,0 +1,21 @@
+// 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.
+
+// aux-build:coherence-lib.rs
+
+extern crate "coherence-lib" as lib;
+use lib::Remote1;
+
+pub struct BigInt;
+
+impl<T> Remote1<BigInt> for T { }
+//~^ ERROR type parameter `T` must also appear
+
+fn main() { }
diff --git a/src/test/compile-fail/coherence-iterator-vec-any-elem.rs b/src/test/compile-fail/coherence-iterator-vec-any-elem.rs
new file mode 100644
index 00000000000..2ed7a6db7ae
--- /dev/null
+++ b/src/test/compile-fail/coherence-iterator-vec-any-elem.rs
@@ -0,0 +1,21 @@
+// 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.
+
+// aux-build:coherence-lib.rs
+
+extern crate "coherence-lib" as lib;
+use lib::Remote1;
+
+struct Foo<T>(T);
+
+impl<T,U> Remote1<U> for Foo<T> { }
+//~^ ERROR type parameter `U` must also appear
+
+fn main() { }
diff --git a/src/test/compile-fail/coherence-lone-type-parameter.rs b/src/test/compile-fail/coherence-lone-type-parameter.rs
new file mode 100644
index 00000000000..0223dacd8ec
--- /dev/null
+++ b/src/test/compile-fail/coherence-lone-type-parameter.rs
@@ -0,0 +1,18 @@
+// 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.
+
+// aux-build:coherence-lib.rs
+
+extern crate "coherence-lib" as lib;
+use lib::Remote;
+
+impl<T> Remote for T { } //~ ERROR E0117
+
+fn main() { }
diff --git a/src/test/compile-fail/coherence-overlapping-pairs.rs b/src/test/compile-fail/coherence-overlapping-pairs.rs
new file mode 100644
index 00000000000..d42bd529b66
--- /dev/null
+++ b/src/test/compile-fail/coherence-overlapping-pairs.rs
@@ -0,0 +1,21 @@
+// 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.
+
+// aux-build:coherence-lib.rs
+
+extern crate "coherence-lib" as lib;
+use lib::Remote;
+
+struct Foo;
+
+impl<T> Remote for lib::Pair<T,Foo> { }
+//~^ ERROR type parameter `T` must also appear
+
+fn main() { }
diff --git a/src/test/compile-fail/coherence-pair-covered-uncovered.rs b/src/test/compile-fail/coherence-pair-covered-uncovered.rs
new file mode 100644
index 00000000000..09895ec11db
--- /dev/null
+++ b/src/test/compile-fail/coherence-pair-covered-uncovered.rs
@@ -0,0 +1,21 @@
+// 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.
+
+// aux-build:coherence-lib.rs
+
+extern crate "coherence-lib" as lib;
+use lib::{Remote, Pair};
+
+struct Local<T>(T);
+
+impl<T,U> Remote for Pair<T,Local<U>> { }
+//~^ ERROR type parameter `T` must also appear
+
+fn main() { }
diff --git a/src/test/compile-fail/opt-out-copy-bad.rs b/src/test/compile-fail/opt-out-copy-bad.rs
index 80f8a154d58..4aae8fa87da 100644
--- a/src/test/compile-fail/opt-out-copy-bad.rs
+++ b/src/test/compile-fail/opt-out-copy-bad.rs
@@ -9,6 +9,8 @@
 // except according to those terms.
 
 #![feature(opt_out_copy)]
+//~^ WARNING feature is deprecated
+//~| WARNING feature is deprecated
 
 // Test that when using the `opt-out-copy` feature we still consider
 // destructors to be non-movable
diff --git a/src/test/run-pass/coherence-bigint-int.rs b/src/test/run-pass/coherence-bigint-int.rs
new file mode 100644
index 00000000000..1e90453980f
--- /dev/null
+++ b/src/test/run-pass/coherence-bigint-int.rs
@@ -0,0 +1,20 @@
+// 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.
+
+// aux-build:coherence-lib.rs
+
+extern crate "coherence-lib" as lib;
+use lib::Remote1;
+
+pub struct BigInt;
+
+impl Remote1<BigInt> for int { }
+
+fn main() { }
diff --git a/src/test/run-pass/coherence-bigint-vecint.rs b/src/test/run-pass/coherence-bigint-vecint.rs
new file mode 100644
index 00000000000..b100455eb33
--- /dev/null
+++ b/src/test/run-pass/coherence-bigint-vecint.rs
@@ -0,0 +1,20 @@
+// 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.
+
+// aux-build:coherence-lib.rs
+
+extern crate "coherence-lib" as lib;
+use lib::Remote1;
+
+pub struct BigInt;
+
+impl Remote1<BigInt> for Vec<int> { }
+
+fn main() { }
diff --git a/src/test/run-pass/coherence-blanket.rs b/src/test/run-pass/coherence-blanket.rs
new file mode 100644
index 00000000000..e02117d1ca2
--- /dev/null
+++ b/src/test/run-pass/coherence-blanket.rs
@@ -0,0 +1,22 @@
+// 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.
+
+// aux-build:coherence-lib.rs
+
+extern crate "coherence-lib" as lib;
+use lib::Remote1;
+
+pub trait Local {
+    fn foo(&self) { }
+}
+
+impl<T> Local for T { }
+
+fn main() { }
diff --git a/src/test/run-pass/coherence-covered-type-parameter.rs b/src/test/run-pass/coherence-covered-type-parameter.rs
new file mode 100644
index 00000000000..27f1f2dafb0
--- /dev/null
+++ b/src/test/run-pass/coherence-covered-type-parameter.rs
@@ -0,0 +1,20 @@
+// 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.
+
+// aux-build:coherence-lib.rs
+
+extern crate "coherence-lib" as lib;
+use lib::Remote;
+
+struct Foo<T>(T);
+
+impl<T> Remote for Foo<T> { }
+
+fn main() { }
diff --git a/src/test/run-pass/coherence-iterator-vec.rs b/src/test/run-pass/coherence-iterator-vec.rs
new file mode 100644
index 00000000000..7077503f73f
--- /dev/null
+++ b/src/test/run-pass/coherence-iterator-vec.rs
@@ -0,0 +1,20 @@
+// 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.
+
+// aux-build:coherence-lib.rs
+
+extern crate "coherence-lib" as lib;
+use lib::Remote1;
+
+struct Foo<T>(T);
+
+impl<T> Remote1<T> for Foo<T> { }
+
+fn main() { }
diff --git a/src/test/run-pass/coherence-local-1.rs b/src/test/run-pass/coherence-local-1.rs
new file mode 100644
index 00000000000..a9bc3dc0e2f
--- /dev/null
+++ b/src/test/run-pass/coherence-local-1.rs
@@ -0,0 +1,20 @@
+// 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.
+
+// aux-build:coherence-lib.rs
+
+extern crate "coherence-lib" as lib;
+use lib::Remote;
+
+struct Local;
+
+impl Remote for Vec<Local> { }
+
+fn main() { }
diff --git a/src/test/run-pass/coherence-local-2.rs b/src/test/run-pass/coherence-local-2.rs
new file mode 100644
index 00000000000..07a830cb1ac
--- /dev/null
+++ b/src/test/run-pass/coherence-local-2.rs
@@ -0,0 +1,20 @@
+// 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.
+
+// aux-build:coherence-lib.rs
+
+extern crate "coherence-lib" as lib;
+use lib::Remote;
+
+struct Local<T>(T);
+
+impl<T> Remote for Vec<Local<T>> { }
+
+fn main() { }
diff --git a/src/test/run-pass/deriving-encodable-decodable-box.rs b/src/test/run-pass/deriving-encodable-decodable-box.rs
index e21f64cd74c..a24ae22b224 100644
--- a/src/test/run-pass/deriving-encodable-decodable-box.rs
+++ b/src/test/run-pass/deriving-encodable-decodable-box.rs
@@ -8,6 +8,8 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+#![feature(old_orphan_check)]
+
 extern crate serialize;
 
 use serialize::{Encodable, Decodable};
diff --git a/src/test/run-pass/deriving-encodable-decodable-cell-refcell.rs b/src/test/run-pass/deriving-encodable-decodable-cell-refcell.rs
index a846f852694..f5df1940fa4 100644
--- a/src/test/run-pass/deriving-encodable-decodable-cell-refcell.rs
+++ b/src/test/run-pass/deriving-encodable-decodable-cell-refcell.rs
@@ -11,6 +11,8 @@
 // This briefly tests the capability of `Cell` and `RefCell` to implement the
 // `Encodable` and `Decodable` traits via `#[deriving(Encodable, Decodable)]`
 
+#![feature(old_orphan_check)]
+
 extern crate serialize;
 
 use std::cell::{Cell, RefCell};
diff --git a/src/test/run-pass/deriving-global.rs b/src/test/run-pass/deriving-global.rs
index 2322675661c..9ece4af278b 100644
--- a/src/test/run-pass/deriving-global.rs
+++ b/src/test/run-pass/deriving-global.rs
@@ -8,6 +8,8 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+#![feature(old_orphan_check)]
+
 extern crate serialize;
 extern crate rand;
 
diff --git a/src/test/run-pass/issue-11881.rs b/src/test/run-pass/issue-11881.rs
index 0e0aea081f6..06c63743555 100644
--- a/src/test/run-pass/issue-11881.rs
+++ b/src/test/run-pass/issue-11881.rs
@@ -8,6 +8,8 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+#![feature(old_orphan_check)]
+
 extern crate rbml;
 extern crate serialize;
 
diff --git a/src/test/run-pass/issue-14021.rs b/src/test/run-pass/issue-14021.rs
index a55cded87e5..39b4a726d45 100644
--- a/src/test/run-pass/issue-14021.rs
+++ b/src/test/run-pass/issue-14021.rs
@@ -8,6 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+#![feature(old_orphan_check)]
 
 extern crate serialize;
 
diff --git a/src/test/run-pass/issue-15734.rs b/src/test/run-pass/issue-15734.rs
index 8aa7447ccd2..e99b1dc5bef 100644
--- a/src/test/run-pass/issue-15734.rs
+++ b/src/test/run-pass/issue-15734.rs
@@ -8,6 +8,10 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+// If `Index` used an associated type for its output, this test would
+// work more smoothly.
+#![feature(old_orphan_check)]
+
 use std::ops::Index;
 
 struct Mat<T> { data: Vec<T>, cols: uint, }
diff --git a/src/test/run-pass/issue-3743.rs b/src/test/run-pass/issue-3743.rs
index c88022f3eb7..cb4f1b7d20f 100644
--- a/src/test/run-pass/issue-3743.rs
+++ b/src/test/run-pass/issue-3743.rs
@@ -8,6 +8,10 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+// If `Mul` used an associated type for its output, this test would
+// work more smoothly.
+#![feature(old_orphan_check)]
+
 use std::ops::Mul;
 
 struct Vec2 {
diff --git a/src/test/run-pass/overloaded-calls-param-vtables.rs b/src/test/run-pass/overloaded-calls-param-vtables.rs
index 95df1ed0d83..bdaccee65d7 100644
--- a/src/test/run-pass/overloaded-calls-param-vtables.rs
+++ b/src/test/run-pass/overloaded-calls-param-vtables.rs
@@ -15,9 +15,9 @@
 use std::ops::Fn;
 use std::ops::Add;
 
-struct G;
+struct G<A>;
 
-impl<'a, A: Add<int, int>> Fn<(A,), int> for G {
+impl<'a, A: Add<int, int>> Fn<(A,), int> for G<A> {
     extern "rust-call" fn call(&self, (arg,): (A,)) -> int {
         arg.add(1)
     }