Rollup merge of #23867 - nikomatsakis:issue-23086-take-3, r=pnkfelix

This PR implements rust-lang/rfcs#1023. In the process it fixes #23086 and #23516. A few impls in libcore had to be updated, but the impact is generally pretty minimal. Most of the fallout is in the tests that probed the limits of today's coherence.

I tested and we were able to build the most popular crates along with iron (modulo errors around errors being sendable).

Fixes #23918.

40 files changed, 808 insertions, 227 deletions

diff --git a/src/liballoc/boxed.rs b/src/liballoc/boxed.rs
index 550b25ac3a7..c4541e34cdb 100644
--- a/src/liballoc/boxed.rs
+++ b/src/liballoc/boxed.rs
@@ -86,6 +86,7 @@ pub static HEAP: () = ();
 /// See the [module-level documentation](../../std/boxed/index.html) for more.
 #[lang = "owned_box"]
 #[stable(feature = "rust1", since = "1.0.0")]
+#[fundamental]
 pub struct Box<T>(Unique<T>);
 
 impl<T> Box<T> {
@@ -278,13 +279,6 @@ impl<T: fmt::Debug + ?Sized> fmt::Debug for Box<T> {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl fmt::Debug for Box<Any> {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        f.pad("Box<Any>")
-    }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
 impl<T: ?Sized> Deref for Box<T> {
     type Target = T;
 
diff --git a/src/liballoc/boxed_test.rs b/src/liballoc/boxed_test.rs
index 682d5f407c4..fc44ac4eac6 100644
--- a/src/liballoc/boxed_test.rs
+++ b/src/liballoc/boxed_test.rs
@@ -55,17 +55,17 @@ fn test_show() {
     let b = Box::new(Test) as Box<Any>;
     let a_str = format!("{:?}", a);
     let b_str = format!("{:?}", b);
-    assert_eq!(a_str, "Box<Any>");
-    assert_eq!(b_str, "Box<Any>");
+    assert_eq!(a_str, "Any");
+    assert_eq!(b_str, "Any");
 
     static EIGHT: usize = 8;
     static TEST: Test = Test;
     let a = &EIGHT as &Any;
     let b = &TEST as &Any;
     let s = format!("{:?}", a);
-    assert_eq!(s, "&Any");
+    assert_eq!(s, "Any");
     let s = format!("{:?}", b);
-    assert_eq!(s, "&Any");
+    assert_eq!(s, "Any");
 }
 
 #[test]
diff --git a/src/liballoc/lib.rs b/src/liballoc/lib.rs
index b92dfa9117e..a8be63d6373 100644
--- a/src/liballoc/lib.rs
+++ b/src/liballoc/lib.rs
@@ -71,6 +71,8 @@
 #![feature(no_std)]
 #![no_std]
 #![feature(allocator)]
+#![feature(custom_attribute)]
+#![feature(fundamental)]
 #![feature(lang_items, unsafe_destructor)]
 #![feature(box_syntax)]
 #![feature(optin_builtin_traits)]
diff --git a/src/libcore/any.rs b/src/libcore/any.rs
index 0ffc4a229b5..320fdd50b35 100644
--- a/src/libcore/any.rs
+++ b/src/libcore/any.rs
@@ -71,6 +71,7 @@
 
 #![stable(feature = "rust1", since = "1.0.0")]
 
+use fmt;
 use marker::Send;
 use mem::transmute;
 use option::Option::{self, Some, None};
@@ -105,6 +106,13 @@ impl<T> Any for T
 // Extension methods for Any trait objects.
 ///////////////////////////////////////////////////////////////////////////////
 
+#[stable(feature = "rust1", since = "1.0.0")]
+impl fmt::Debug for Any {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.pad("Any")
+    }
+}
+
 impl Any {
     /// Returns true if the boxed type is the same as `T`
     #[stable(feature = "rust1", since = "1.0.0")]
diff --git a/src/libcore/fmt/mod.rs b/src/libcore/fmt/mod.rs
index ffb358cdac8..3f8bbeb1feb 100644
--- a/src/libcore/fmt/mod.rs
+++ b/src/libcore/fmt/mod.rs
@@ -12,7 +12,6 @@
 
 #![stable(feature = "rust1", since = "1.0.0")]
 
-use any;
 use cell::{Cell, RefCell, Ref, RefMut, BorrowState};
 use char::CharExt;
 use iter::Iterator;
@@ -998,11 +997,6 @@ macro_rules! tuple {
 tuple! { T0, T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<'a> Debug for &'a (any::Any+'a) {
-    fn fmt(&self, f: &mut Formatter) -> Result { f.pad("&Any") }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
 impl<T: Debug> Debug for [T] {
     fn fmt(&self, f: &mut Formatter) -> Result {
         self.iter().fold(f.debug_list(), |b, e| b.entry(e)).finish()
diff --git a/src/libcore/lib.rs b/src/libcore/lib.rs
index 5e8b7fba1f1..3a9af50fefb 100644
--- a/src/libcore/lib.rs
+++ b/src/libcore/lib.rs
@@ -70,8 +70,10 @@
 #![feature(unboxed_closures)]
 #![feature(rustc_attrs)]
 #![feature(optin_builtin_traits)]
+#![feature(fundamental)]
 #![feature(concat_idents)]
 #![feature(reflect)]
+#![feature(custom_attribute)]
 
 #[macro_use]
 mod macros;
diff --git a/src/libcore/marker.rs b/src/libcore/marker.rs
index f755c912fcd..97bde9fc96e 100644
--- a/src/libcore/marker.rs
+++ b/src/libcore/marker.rs
@@ -49,6 +49,7 @@ impl !Send for Managed { }
 #[stable(feature = "rust1", since = "1.0.0")]
 #[lang="sized"]
 #[rustc_on_unimplemented = "`{Self}` does not have a constant size known at compile-time"]
+#[fundamental] // for Default, for example, which requires that `[T]: !Default` be evaluatable
 pub trait Sized : MarkerTrait {
     // Empty.
 }
diff --git a/src/libcore/ops.rs b/src/libcore/ops.rs
index 862eb16d0bf..399aec9afd4 100644
--- a/src/libcore/ops.rs
+++ b/src/libcore/ops.rs
@@ -1117,6 +1117,7 @@ impl<'a, T: ?Sized> DerefMut for &'a mut T {
 #[lang="fn"]
 #[stable(feature = "rust1", since = "1.0.0")]
 #[rustc_paren_sugar]
+#[fundamental] // so that regex can rely that `&str: !FnMut`
 pub trait Fn<Args> : FnMut<Args> {
     /// This is called when the call operator is used.
     extern "rust-call" fn call(&self, args: Args) -> Self::Output;
@@ -1126,6 +1127,7 @@ pub trait Fn<Args> : FnMut<Args> {
 #[lang="fn_mut"]
 #[stable(feature = "rust1", since = "1.0.0")]
 #[rustc_paren_sugar]
+#[fundamental] // so that regex can rely that `&str: !FnMut`
 pub trait FnMut<Args> : FnOnce<Args> {
     /// This is called when the call operator is used.
     extern "rust-call" fn call_mut(&mut self, args: Args) -> Self::Output;
@@ -1135,6 +1137,7 @@ pub trait FnMut<Args> : FnOnce<Args> {
 #[lang="fn_once"]
 #[stable(feature = "rust1", since = "1.0.0")]
 #[rustc_paren_sugar]
+#[fundamental] // so that regex can rely that `&str: !FnMut`
 pub trait FnOnce<Args> {
     /// The returned type after the call operator is used.
     type Output;
diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index a8f83bee7f6..862ced78c08 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -34,8 +34,7 @@ use std::io::prelude::*;
 use std::io::{Cursor, SeekFrom};
 use syntax::abi;
 use syntax::ast::{self, DefId, NodeId};
-use syntax::ast_map::{PathElem, PathElems};
-use syntax::ast_map;
+use syntax::ast_map::{self, LinkedPath, PathElem, PathElems};
 use syntax::ast_util::*;
 use syntax::ast_util;
 use syntax::attr;
@@ -1513,7 +1512,7 @@ fn encode_info_for_items(ecx: &EncodeContext,
                         &krate.module,
                         &[],
                         ast::CRATE_NODE_ID,
-                        [].iter().cloned().chain(None),
+                        [].iter().cloned().chain(LinkedPath::empty()),
                         syntax::parse::token::special_idents::invalid,
                         ast::Public);
 
@@ -1874,7 +1873,7 @@ fn encode_misc_info(ecx: &EncodeContext,
     }
 
     // Encode reexports for the root module.
-    encode_reexports(ecx, rbml_w, 0, [].iter().cloned().chain(None));
+    encode_reexports(ecx, rbml_w, 0, [].iter().cloned().chain(LinkedPath::empty()));
 
     rbml_w.end_tag();
     rbml_w.end_tag();
diff --git a/src/librustc/middle/traits/coherence.rs b/src/librustc/middle/traits/coherence.rs
index 11d073ce72e..411be28b896 100644
--- a/src/librustc/middle/traits/coherence.rs
+++ b/src/librustc/middle/traits/coherence.rs
@@ -17,15 +17,17 @@ use super::PredicateObligation;
 use super::project;
 use super::util;
 
-use middle::subst::{Subst, TypeSpace};
+use middle::subst::{Subst, Substs, TypeSpace};
 use middle::ty::{self, ToPolyTraitRef, Ty};
 use middle::infer::{self, InferCtxt};
-use std::collections::HashSet;
 use std::rc::Rc;
 use syntax::ast;
-use syntax::codemap::DUMMY_SP;
+use syntax::codemap::{DUMMY_SP, Span};
 use util::ppaux::Repr;
 
+#[derive(Copy)]
+struct ParamIsLocal(bool);
+
 /// True if there exist types that satisfy both of the two given impls.
 pub fn overlapping_impls(infcx: &InferCtxt,
                          impl1_def_id: ast::DefId,
@@ -56,10 +58,16 @@ fn overlap(selcx: &mut SelectionContext,
            a_def_id.repr(selcx.tcx()),
            b_def_id.repr(selcx.tcx()));
 
-    let (a_trait_ref, a_obligations) = impl_trait_ref_and_oblig(selcx, a_def_id);
-    let (b_trait_ref, b_obligations) = impl_trait_ref_and_oblig(selcx, b_def_id);
+    let (a_trait_ref, a_obligations) = impl_trait_ref_and_oblig(selcx,
+                                                                a_def_id,
+                                                                util::free_substs_for_impl);
+
+    let (b_trait_ref, b_obligations) = impl_trait_ref_and_oblig(selcx,
+                                                                b_def_id,
+                                                                util::fresh_type_vars_for_impl);
 
     debug!("overlap: a_trait_ref={}", a_trait_ref.repr(selcx.tcx()));
+
     debug!("overlap: b_trait_ref={}", b_trait_ref.repr(selcx.tcx()));
 
     // Does `a <: b` hold? If not, no overlap.
@@ -74,28 +82,68 @@ fn overlap(selcx: &mut SelectionContext,
     debug!("overlap: subtraitref check succeeded");
 
     // Are any of the obligations unsatisfiable? If so, no overlap.
+    let tcx = selcx.tcx();
+    let infcx = selcx.infcx();
     let opt_failing_obligation =
         a_obligations.iter()
                      .chain(b_obligations.iter())
+                     .map(|o| infcx.resolve_type_vars_if_possible(o))
                      .find(|o| !selcx.evaluate_obligation(o));
 
     if let Some(failing_obligation) = opt_failing_obligation {
-        debug!("overlap: obligation unsatisfiable {}", failing_obligation.repr(selcx.tcx()));
-        return false;
+        debug!("overlap: obligation unsatisfiable {}", failing_obligation.repr(tcx));
+        return false
     }
 
     true
 }
 
+pub fn trait_ref_is_knowable<'tcx>(tcx: &ty::ctxt<'tcx>, trait_ref: &ty::TraitRef<'tcx>) -> bool
+{
+    debug!("trait_ref_is_knowable(trait_ref={})", trait_ref.repr(tcx));
+
+    // if the orphan rules pass, that means that no ancestor crate can
+    // impl this, so it's up to us.
+    if orphan_check_trait_ref(tcx, trait_ref, ParamIsLocal(false)).is_ok() {
+        debug!("trait_ref_is_knowable: orphan check passed");
+        return true;
+    }
+
+    // if the trait is not marked fundamental, then it's always possible that
+    // an ancestor crate will impl this in the future, if they haven't
+    // already
+    if
+        trait_ref.def_id.krate != ast::LOCAL_CRATE &&
+        !ty::has_attr(tcx, trait_ref.def_id, "fundamental")
+    {
+        debug!("trait_ref_is_knowable: trait is neither local nor fundamental");
+        return false;
+    }
+
+    // find out when some downstream (or cousin) crate could impl this
+    // trait-ref, presuming that all the parameters were instantiated
+    // with downstream types. If not, then it could only be
+    // implemented by an upstream crate, which means that the impl
+    // must be visible to us, and -- since the trait is fundamental
+    // -- we can test.
+    orphan_check_trait_ref(tcx, trait_ref, ParamIsLocal(true)).is_err()
+}
+
+type SubstsFn = for<'a,'tcx> fn(infcx: &InferCtxt<'a, 'tcx>,
+                                span: Span,
+                                impl_def_id: ast::DefId)
+                                -> Substs<'tcx>;
+
 /// Instantiate fresh variables for all bound parameters of the impl
 /// and return the impl trait ref with those variables substituted.
 fn impl_trait_ref_and_oblig<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
-                                     impl_def_id: ast::DefId)
+                                     impl_def_id: ast::DefId,
+                                     substs_fn: SubstsFn)
                                      -> (Rc<ty::TraitRef<'tcx>>,
                                          Vec<PredicateObligation<'tcx>>)
 {
     let impl_substs =
-        &util::fresh_substs_for_impl(selcx.infcx(), DUMMY_SP, impl_def_id);
+        &substs_fn(selcx.infcx(), DUMMY_SP, impl_def_id);
     let impl_trait_ref =
         ty::impl_trait_ref(selcx.tcx(), impl_def_id).unwrap();
     let impl_trait_ref =
@@ -134,12 +182,12 @@ 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));
+    debug!("orphan_check({})", 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));
+    debug!("orphan_check: trait_ref={}", trait_ref.repr(tcx));
 
     // If the *trait* is local to the crate, ok.
     if trait_ref.def_id.krate == ast::LOCAL_CRATE {
@@ -148,34 +196,106 @@ pub fn orphan_check<'tcx>(tcx: &ty::ctxt<'tcx>,
         return Ok(());
     }
 
+    orphan_check_trait_ref(tcx, &trait_ref, ParamIsLocal(false))
+}
+
+fn orphan_check_trait_ref<'tcx>(tcx: &ty::ctxt<'tcx>,
+                                trait_ref: &ty::TraitRef<'tcx>,
+                                param_is_local: ParamIsLocal)
+                                -> Result<(), OrphanCheckErr<'tcx>>
+{
+    debug!("orphan_check_trait_ref(trait_ref={}, param_is_local={})",
+           trait_ref.repr(tcx), param_is_local.0);
+
     // First, create an ordered iterator over all the type parameters to the trait, with the self
     // type appearing first.
     let input_tys = Some(trait_ref.self_ty());
     let input_tys = input_tys.iter().chain(trait_ref.substs.types.get_slice(TypeSpace).iter());
-    let mut input_tys = input_tys;
 
     // Find the first input type that either references a type parameter OR
     // some local type.
-    match input_tys.find(|&&input_ty| references_local_or_type_parameter(tcx, input_ty)) {
-        Some(&input_ty) => {
-            // Within this first type, check that all type parameters are covered by a local
-            // type constructor. Note that if there is no local type constructor, then any
-            // type parameter at all will be an error.
-            let covered_params = type_parameters_covered_by_ty(tcx, input_ty);
-            let all_params = type_parameters_reachable_from_ty(input_ty);
-            for &param in all_params.difference(&covered_params) {
-                return Err(OrphanCheckErr::UncoveredTy(param));
+    for input_ty in input_tys {
+        if ty_is_local(tcx, input_ty, param_is_local) {
+            debug!("orphan_check_trait_ref: ty_is_local `{}`", input_ty.repr(tcx));
+
+            // First local input type. Check that there are no
+            // uncovered type parameters.
+            let uncovered_tys = uncovered_tys(tcx, input_ty, param_is_local);
+            for uncovered_ty in uncovered_tys {
+                if let Some(param) = uncovered_ty.walk().find(|t| is_type_parameter(t)) {
+                    debug!("orphan_check_trait_ref: uncovered type `{}`", param.repr(tcx));
+                    return Err(OrphanCheckErr::UncoveredTy(param));
+                }
             }
+
+            // OK, found local type, all prior types upheld invariant.
+            return Ok(());
         }
-        None => {
-            return Err(OrphanCheckErr::NoLocalInputType);
+
+        // Otherwise, enforce invariant that there are no type
+        // parameters reachable.
+        if !param_is_local.0 {
+            if let Some(param) = input_ty.walk().find(|t| is_type_parameter(t)) {
+                debug!("orphan_check_trait_ref: uncovered type `{}`", param.repr(tcx));
+                return Err(OrphanCheckErr::UncoveredTy(param));
+            }
         }
     }
 
-    return Ok(());
+    // If we exit above loop, never found a local type.
+    debug!("orphan_check_trait_ref: no local type");
+    return Err(OrphanCheckErr::NoLocalInputType);
+}
+
+fn uncovered_tys<'tcx>(tcx: &ty::ctxt<'tcx>,
+                       ty: Ty<'tcx>,
+                       param_is_local: ParamIsLocal)
+                       -> Vec<Ty<'tcx>>
+{
+    if ty_is_local_constructor(tcx, ty, param_is_local) {
+        vec![]
+    } else if fundamental_ty(tcx, ty) {
+        ty.walk_shallow()
+          .flat_map(|t| uncovered_tys(tcx, t, param_is_local).into_iter())
+          .collect()
+    } else {
+        vec![ty]
+    }
 }
 
-fn ty_is_local_constructor<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
+fn is_type_parameter<'tcx>(ty: Ty<'tcx>) -> bool {
+    match ty.sty {
+        // FIXME(#20590) straighten story about projection types
+        ty::ty_projection(..) | ty::ty_param(..) => true,
+        _ => false,
+    }
+}
+
+fn ty_is_local<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>, param_is_local: ParamIsLocal) -> bool
+{
+    ty_is_local_constructor(tcx, ty, param_is_local) ||
+        fundamental_ty(tcx, ty) && ty.walk_shallow().any(|t| ty_is_local(tcx, t, param_is_local))
+}
+
+fn fundamental_ty<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool
+{
+    match ty.sty {
+        ty::ty_uniq(..) | ty::ty_rptr(..) =>
+            true,
+        ty::ty_enum(def_id, _) | ty::ty_struct(def_id, _) =>
+            ty::has_attr(tcx, def_id, "fundamental"),
+        ty::ty_trait(ref data) =>
+            ty::has_attr(tcx, data.principal_def_id(), "fundamental"),
+        _ =>
+            false
+    }
+}
+
+fn ty_is_local_constructor<'tcx>(tcx: &ty::ctxt<'tcx>,
+                                 ty: Ty<'tcx>,
+                                 param_is_local: ParamIsLocal)
+                                 -> bool
+{
     debug!("ty_is_local_constructor({})", ty.repr(tcx));
 
     match ty.sty {
@@ -190,11 +310,15 @@ fn ty_is_local_constructor<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
         ty::ty_ptr(..) |
         ty::ty_rptr(..) |
         ty::ty_tup(..) |
-        ty::ty_param(..) |
+        ty::ty_infer(..) |
         ty::ty_projection(..) => {
             false
         }
 
+        ty::ty_param(..) => {
+            param_is_local.0
+        }
+
         ty::ty_enum(def_id, _) |
         ty::ty_struct(def_id, _) => {
             def_id.krate == ast::LOCAL_CRATE
@@ -210,7 +334,6 @@ fn ty_is_local_constructor<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
         }
 
         ty::ty_closure(..) |
-        ty::ty_infer(..) |
         ty::ty_err => {
             tcx.sess.bug(
                 &format!("ty_is_local invoked on unexpected type: {}",
@@ -219,30 +342,4 @@ 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<'tcx>>
-{
-    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<'tcx>> {
-    ty.walk().filter(|&t| is_type_parameter(t)).collect()
-}
-
-fn references_local_or_type_parameter<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
-    ty.walk().any(|ty| is_type_parameter(ty) || ty_is_local_constructor(tcx, ty))
-}
 
-fn is_type_parameter<'tcx>(ty: Ty<'tcx>) -> bool {
-    match ty.sty {
-        // FIXME(#20590) straighten story about projection types
-        ty::ty_projection(..) | ty::ty_param(..) => true,
-        _ => false,
-    }
-}
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index 9e4f63dca45..cb9d90744a4 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -17,6 +17,7 @@ use self::SelectionCandidate::*;
 use self::BuiltinBoundConditions::*;
 use self::EvaluationResult::*;
 
+use super::coherence;
 use super::DerivedObligationCause;
 use super::project;
 use super::project::{normalize_with_depth, Normalized};
@@ -81,7 +82,7 @@ struct TraitObligationStack<'prev, 'tcx: 'prev> {
     /// selection-context's freshener. Used to check for recursion.
     fresh_trait_ref: ty::PolyTraitRef<'tcx>,
 
-    previous: Option<&'prev TraitObligationStack<'prev, 'tcx>>
+    previous: TraitObligationStackList<'prev, 'tcx>,
 }
 
 #[derive(Clone)]
@@ -245,7 +246,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         debug!("select({})", obligation.repr(self.tcx()));
         assert!(!obligation.predicate.has_escaping_regions());
 
-        let stack = self.push_stack(None, obligation);
+        let stack = self.push_stack(TraitObligationStackList::empty(), obligation);
         match try!(self.candidate_from_obligation(&stack)) {
             None => {
                 self.consider_unification_despite_ambiguity(obligation);
@@ -327,7 +328,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         debug!("evaluate_obligation({})",
                obligation.repr(self.tcx()));
 
-        self.evaluate_predicate_recursively(None, obligation).may_apply()
+        self.evaluate_predicate_recursively(TraitObligationStackList::empty(), obligation)
+            .may_apply()
     }
 
     fn evaluate_builtin_bound_recursively<'o>(&mut self,
@@ -346,7 +348,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
         match obligation {
             Ok(obligation) => {
-                self.evaluate_predicate_recursively(Some(previous_stack), &obligation)
+                self.evaluate_predicate_recursively(previous_stack.list(), &obligation)
             }
             Err(ErrorReported) => {
                 EvaluatedToOk
@@ -355,7 +357,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 
     fn evaluate_predicates_recursively<'a,'o,I>(&mut self,
-                                                stack: Option<&TraitObligationStack<'o, 'tcx>>,
+                                                stack: TraitObligationStackList<'o, 'tcx>,
                                                 predicates: I)
                                                 -> EvaluationResult<'tcx>
         where I : Iterator<Item=&'a PredicateObligation<'tcx>>, 'tcx:'a
@@ -372,7 +374,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 
     fn evaluate_predicate_recursively<'o>(&mut self,
-                                          previous_stack: Option<&TraitObligationStack<'o, 'tcx>>,
+                                          previous_stack: TraitObligationStackList<'o, 'tcx>,
                                           obligation: &PredicateObligation<'tcx>)
                                            -> EvaluationResult<'tcx>
     {
@@ -423,14 +425,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 
     fn evaluate_obligation_recursively<'o>(&mut self,
-                                           previous_stack: Option<&TraitObligationStack<'o, 'tcx>>,
+                                           previous_stack: TraitObligationStackList<'o, 'tcx>,
                                            obligation: &TraitObligation<'tcx>)
                                            -> EvaluationResult<'tcx>
     {
         debug!("evaluate_obligation_recursively({})",
                obligation.repr(self.tcx()));
 
-        let stack = self.push_stack(previous_stack.map(|x| x), obligation);
+        let stack = self.push_stack(previous_stack, obligation);
 
         let result = self.evaluate_stack(&stack);
 
@@ -538,7 +540,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                                        obligation.recursion_depth + 1,
                                                        skol_map,
                                                        snapshot);
-                    self.winnow_selection(None, VtableImpl(vtable_impl)).may_apply()
+                    self.winnow_selection(TraitObligationStackList::empty(),
+                                          VtableImpl(vtable_impl)).may_apply()
                 }
                 Err(()) => {
                     false
@@ -607,6 +610,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             return Ok(Some(ErrorCandidate));
         }
 
+        if !self.is_knowable(stack) {
+            debug!("intercrate not knowable");
+            return Ok(None);
+        }
+
         let candidate_set = try!(self.assemble_candidates(stack));
 
         if candidate_set.ambiguous {
@@ -707,6 +715,27 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         Ok(Some(candidate))
     }
 
+    fn is_knowable<'o>(&mut self,
+                       stack: &TraitObligationStack<'o, 'tcx>)
+                       -> bool
+    {
+        debug!("is_knowable(intercrate={})", self.intercrate);
+
+        if !self.intercrate {
+            return true;
+        }
+
+        let obligation = &stack.obligation;
+        let predicate = self.infcx().resolve_type_vars_if_possible(&obligation.predicate);
+
+        // ok to skip binder because of the nature of the
+        // trait-ref-is-knowable check, which does not care about
+        // bound regions
+        let trait_ref = &predicate.skip_binder().trait_ref;
+
+        coherence::trait_ref_is_knowable(self.tcx(), trait_ref)
+    }
+
     fn pick_candidate_cache(&self) -> &SelectionCache<'tcx> {
         // If there are any where-clauses in scope, then we always use
         // a cache local to this particular scope. Otherwise, we
@@ -1026,7 +1055,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         self.infcx().probe(move |_| {
             match self.match_where_clause_trait_ref(stack.obligation, where_clause_trait_ref) {
                 Ok(obligations) => {
-                    self.evaluate_predicates_recursively(Some(stack), obligations.iter())
+                    self.evaluate_predicates_recursively(stack.list(), obligations.iter())
                 }
                 Err(()) => {
                     EvaluatedToErr(Unimplemented)
@@ -1310,7 +1339,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         let result = self.infcx.probe(|_| {
             let candidate = (*candidate).clone();
             match self.confirm_candidate(stack.obligation, candidate) {
-                Ok(selection) => self.winnow_selection(Some(stack), selection),
+                Ok(selection) => self.winnow_selection(stack.list(),
+                                                       selection),
                 Err(error) => EvaluatedToErr(error),
             }
         });
@@ -1320,7 +1350,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 
     fn winnow_selection<'o>(&mut self,
-                            stack: Option<&TraitObligationStack<'o, 'tcx>>,
+                            stack: TraitObligationStackList<'o,'tcx>,
                             selection: Selection<'tcx>)
                             -> EvaluationResult<'tcx>
     {
@@ -2303,9 +2333,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             return Err(());
         }
 
-        let impl_substs = util::fresh_substs_for_impl(self.infcx,
-                                                      obligation.cause.span,
-                                                      impl_def_id);
+        let impl_substs = util::fresh_type_vars_for_impl(self.infcx,
+                                                         obligation.cause.span,
+                                                         impl_def_id);
 
         let impl_trait_ref = impl_trait_ref.subst(self.tcx(),
                                                   &impl_substs);
@@ -2423,9 +2453,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     {
         // Create fresh type variables for each type parameter declared
         // on the impl etc.
-        let impl_substs = util::fresh_substs_for_impl(self.infcx,
-                                                      obligation_cause.span,
-                                                      impl_def_id);
+        let impl_substs = util::fresh_type_vars_for_impl(self.infcx,
+                                                         obligation_cause.span,
+                                                         impl_def_id);
 
         // Find the self type for the impl.
         let impl_self_ty = ty::lookup_item_type(self.tcx(), impl_def_id).ty;
@@ -2476,7 +2506,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     // Miscellany
 
     fn push_stack<'o,'s:'o>(&mut self,
-                            previous_stack: Option<&'s TraitObligationStack<'s, 'tcx>>,
+                            previous_stack: TraitObligationStackList<'s, 'tcx>,
                             obligation: &'o TraitObligation<'tcx>)
                             -> TraitObligationStack<'o, 'tcx>
     {
@@ -2486,7 +2516,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         TraitObligationStack {
             obligation: obligation,
             fresh_trait_ref: fresh_trait_ref,
-            previous: previous_stack.map(|p| p), // FIXME variance
+            previous: previous_stack,
         }
     }
 
@@ -2639,17 +2669,36 @@ impl<'tcx> SelectionCache<'tcx> {
     }
 }
 
-impl<'o, 'tcx> TraitObligationStack<'o, 'tcx> {
-    fn iter(&self) -> Option<&TraitObligationStack<'o, 'tcx>> {
-        Some(self)
+impl<'o,'tcx> TraitObligationStack<'o,'tcx> {
+    fn list(&'o self) -> TraitObligationStackList<'o,'tcx> {
+        TraitObligationStackList::with(self)
+    }
+
+    fn iter(&'o self) -> TraitObligationStackList<'o,'tcx> {
+        self.list()
     }
 }
 
-impl<'o, 'tcx> Iterator for Option<&'o TraitObligationStack<'o, 'tcx>> {
+#[derive(Copy, Clone)]
+struct TraitObligationStackList<'o,'tcx:'o> {
+    head: Option<&'o TraitObligationStack<'o,'tcx>>
+}
+
+impl<'o,'tcx> TraitObligationStackList<'o,'tcx> {
+    fn empty() -> TraitObligationStackList<'o,'tcx> {
+        TraitObligationStackList { head: None }
+    }
+
+    fn with(r: &'o TraitObligationStack<'o,'tcx>) -> TraitObligationStackList<'o,'tcx> {
+        TraitObligationStackList { head: Some(r) }
+    }
+}
+
+impl<'o,'tcx> Iterator for TraitObligationStackList<'o,'tcx>{
     type Item = &'o TraitObligationStack<'o,'tcx>;
 
-    fn next(&mut self) -> Option<&'o TraitObligationStack<'o, 'tcx>> {
-        match *self {
+    fn next(&mut self) -> Option<&'o TraitObligationStack<'o,'tcx>> {
+        match self.head {
             Some(o) => {
                 *self = o.previous;
                 Some(o)
@@ -2659,7 +2708,7 @@ impl<'o, 'tcx> Iterator for Option<&'o TraitObligationStack<'o, 'tcx>> {
     }
 }
 
-impl<'o, 'tcx> Repr<'tcx> for TraitObligationStack<'o, 'tcx> {
+impl<'o,'tcx> Repr<'tcx> for TraitObligationStack<'o,'tcx> {
     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
         format!("TraitObligationStack({})",
                 self.obligation.repr(tcx))
diff --git a/src/librustc/middle/traits/util.rs b/src/librustc/middle/traits/util.rs
index 7c7db4a64c0..297cea13207 100644
--- a/src/librustc/middle/traits/util.rs
+++ b/src/librustc/middle/traits/util.rs
@@ -8,6 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use middle::region;
 use middle::subst::{Substs, VecPerParamSpace};
 use middle::infer::InferCtxt;
 use middle::ty::{self, Ty, AsPredicate, ToPolyTraitRef};
@@ -285,7 +286,6 @@ impl<'tcx,I:Iterator<Item=ty::Predicate<'tcx>>> Iterator for FilterToTraits<I> {
     }
 }
 
-
 ///////////////////////////////////////////////////////////////////////////
 // Other
 ///////////////////////////////////////////////////////////////////////////
@@ -294,16 +294,44 @@ impl<'tcx,I:Iterator<Item=ty::Predicate<'tcx>>> Iterator for FilterToTraits<I> {
 // declared on the impl declaration e.g., `impl<A,B> for Box<[(A,B)]>`
 // would return ($0, $1) where $0 and $1 are freshly instantiated type
 // variables.
-pub fn fresh_substs_for_impl<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>,
-                                       span: Span,
-                                       impl_def_id: ast::DefId)
-                                       -> Substs<'tcx>
+pub fn fresh_type_vars_for_impl<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>,
+                                          span: Span,
+                                          impl_def_id: ast::DefId)
+                                          -> Substs<'tcx>
 {
     let tcx = infcx.tcx;
     let impl_generics = ty::lookup_item_type(tcx, impl_def_id).generics;
     infcx.fresh_substs_for_generics(span, &impl_generics)
 }
 
+// determine the `self` type, using fresh variables for all variables
+// declared on the impl declaration e.g., `impl<A,B> for Box<[(A,B)]>`
+// would return ($0, $1) where $0 and $1 are freshly instantiated type
+// variables.
+pub fn free_substs_for_impl<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>,
+                                      _span: Span,
+                                      impl_def_id: ast::DefId)
+                                      -> Substs<'tcx>
+{
+    let tcx = infcx.tcx;
+    let impl_generics = ty::lookup_item_type(tcx, impl_def_id).generics;
+
+    let some_types = impl_generics.types.map(|def| {
+        ty::mk_param_from_def(tcx, def)
+    });
+
+    let some_regions = impl_generics.regions.map(|def| {
+        // FIXME. This destruction scope information is pretty darn
+        // bogus; after all, the impl might not even be in this crate!
+        // But given what we do in coherence, it is harmless enough
+        // for now I think. -nmatsakis
+        let extent = region::DestructionScopeData::new(ast::DUMMY_NODE_ID);
+        ty::free_region_from_def(extent, def)
+    });
+
+    Substs::new(some_types, some_regions)
+}
+
 impl<'tcx, N> fmt::Debug for VtableImplData<'tcx, N> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         write!(f, "VtableImpl({:?})", self.impl_def_id)
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 6e81d14d73c..0814ec2c84e 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -58,7 +58,7 @@ use middle::subst::{self, ParamSpace, Subst, Substs, VecPerParamSpace};
 use middle::traits;
 use middle::ty;
 use middle::ty_fold::{self, TypeFoldable, TypeFolder};
-use middle::ty_walk::TypeWalker;
+use middle::ty_walk::{self, TypeWalker};
 use util::ppaux::{note_and_explain_region, bound_region_ptr_to_string};
 use util::ppaux::ty_to_string;
 use util::ppaux::{Repr, UserString};
@@ -89,7 +89,8 @@ use syntax::codemap::Span;
 use syntax::parse::token::{self, InternedString, special_idents};
 use syntax::print::pprust;
 use syntax::ptr::P;
-use syntax::{ast, ast_map};
+use syntax::ast;
+use syntax::ast_map::{self, LinkedPath};
 
 pub type Disr = u64;
 
@@ -3167,21 +3168,11 @@ impl<'tcx> TyS<'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
-    /// isize => { }
-    /// Foo<Bar<isize>> => { Bar<isize>, isize }
-    /// [isize] => { isize }
-    /// ```
-    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
+    /// Iterator that walks the immediate children of `self`.  Hence
+    /// `Foo<Bar<i32>, u32>` yields the sequence `[Bar<i32>, u32]`
+    /// (but not `i32`, like `walk`).
+    pub fn walk_shallow(&'tcx self) -> IntoIter<Ty<'tcx>> {
+        ty_walk::walk_shallow(self)
     }
 
     pub fn as_opt_param_ty(&self) -> Option<ty::ParamTy> {
@@ -5484,7 +5475,7 @@ pub fn with_path<T, F>(cx: &ctxt, id: ast::DefId, f: F) -> T where
     if id.krate == ast::LOCAL_CRATE {
         cx.map.with_path(id.node, f)
     } else {
-        f(csearch::get_item_path(cx, id).iter().cloned().chain(None))
+        f(csearch::get_item_path(cx, id).iter().cloned().chain(LinkedPath::empty()))
     }
 }
 
diff --git a/src/librustc/middle/ty_walk.rs b/src/librustc/middle/ty_walk.rs
index 5d492f1c95e..ec09d6dcc1e 100644
--- a/src/librustc/middle/ty_walk.rs
+++ b/src/librustc/middle/ty_walk.rs
@@ -12,6 +12,7 @@
 
 use middle::ty::{self, Ty};
 use std::iter::Iterator;
+use std::vec::IntoIter;
 
 pub struct TypeWalker<'tcx> {
     stack: Vec<Ty<'tcx>>,
@@ -23,60 +24,6 @@ impl<'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, _) => {
-                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, ref bounds }) => {
-                self.push_reversed(principal.substs().types.as_slice());
-                self.push_reversed(&bounds.projection_bounds.iter().map(|pred| {
-                    pred.0.ty
-                }).collect::<Vec<_>>());
-            }
-            ty::ty_enum(_, ref substs) |
-            ty::ty_struct(_, ref substs) |
-            ty::ty_closure(_, ref substs) => {
-                self.push_reversed(substs.types.as_slice());
-            }
-            ty::ty_tup(ref ts) => {
-                self.push_reversed(ts);
-            }
-            ty::ty_bare_fn(_, 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);
-    }
-
-    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()`.
     ///
@@ -105,10 +52,70 @@ impl<'tcx> Iterator for TypeWalker<'tcx> {
             }
             Some(ty) => {
                 self.last_subtree = self.stack.len();
-                self.push_subtypes(ty);
+                push_subtypes(&mut self.stack, ty);
                 debug!("next: stack={:?}", self.stack);
                 Some(ty)
             }
         }
     }
 }
+
+pub fn walk_shallow<'tcx>(ty: Ty<'tcx>) -> IntoIter<Ty<'tcx>> {
+    let mut stack = vec![];
+    push_subtypes(&mut stack, ty);
+    stack.into_iter()
+}
+
+fn push_subtypes<'tcx>(stack: &mut Vec<Ty<'tcx>>, 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, _) => {
+            stack.push(ty);
+        }
+        ty::ty_ptr(ref mt) | ty::ty_rptr(_, ref mt) => {
+            stack.push(mt.ty);
+        }
+        ty::ty_projection(ref data) => {
+            push_reversed(stack, data.trait_ref.substs.types.as_slice());
+        }
+        ty::ty_trait(box ty::TyTrait { ref principal, ref bounds }) => {
+            push_reversed(stack, principal.substs().types.as_slice());
+            push_reversed(stack, &bounds.projection_bounds.iter().map(|pred| {
+                pred.0.ty
+            }).collect::<Vec<_>>());
+        }
+        ty::ty_enum(_, ref substs) |
+        ty::ty_struct(_, ref substs) |
+        ty::ty_closure(_, ref substs) => {
+            push_reversed(stack, substs.types.as_slice());
+        }
+        ty::ty_tup(ref ts) => {
+            push_reversed(stack, ts);
+        }
+        ty::ty_bare_fn(_, ref ft) => {
+            push_sig_subtypes(stack, &ft.sig);
+        }
+    }
+}
+
+fn push_sig_subtypes<'tcx>(stack: &mut Vec<Ty<'tcx>>, sig: &ty::PolyFnSig<'tcx>) {
+    match sig.0.output {
+        ty::FnConverging(output) => { stack.push(output); }
+        ty::FnDiverging => { }
+    }
+    push_reversed(stack, &sig.0.inputs);
+}
+
+fn push_reversed<'tcx>(stack: &mut Vec<Ty<'tcx>>, 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() {
+        stack.push(ty);
+    }
+}
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 452589a2407..4405a9d75ee 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -384,13 +384,7 @@ pub fn ty_to_string<'tcx>(cx: &ctxt<'tcx>, typ: &ty::TyS<'tcx>) -> String {
         }
         ty_infer(infer_ty) => infer_ty_to_string(cx, infer_ty),
         ty_err => "[type error]".to_string(),
-        ty_param(ref param_ty) => {
-            if cx.sess.verbose() {
-                param_ty.repr(cx)
-            } else {
-                param_ty.user_string(cx)
-            }
-        }
+        ty_param(ref param_ty) => param_ty.user_string(cx),
         ty_enum(did, substs) | ty_struct(did, substs) => {
             let base = ty::item_path_str(cx, did);
             parameterized(cx, &base, substs, did, &[],
diff --git a/src/libsyntax/ast_map/mod.rs b/src/libsyntax/ast_map/mod.rs
index 48bb044cb18..2b5cb7076f4 100644
--- a/src/libsyntax/ast_map/mod.rs
+++ b/src/libsyntax/ast_map/mod.rs
@@ -53,18 +53,29 @@ impl fmt::Display for PathElem {
 }
 
 #[derive(Clone)]
-struct LinkedPathNode<'a> {
+pub struct LinkedPathNode<'a> {
     node: PathElem,
     next: LinkedPath<'a>,
 }
 
-type LinkedPath<'a> = Option<&'a LinkedPathNode<'a>>;
+#[derive(Copy, Clone)]
+pub struct LinkedPath<'a>(Option<&'a LinkedPathNode<'a>>);
+
+impl<'a> LinkedPath<'a> {
+    pub fn empty() -> LinkedPath<'a> {
+        LinkedPath(None)
+    }
+
+    pub fn from(node: &'a LinkedPathNode) -> LinkedPath<'a> {
+        LinkedPath(Some(node))
+    }
+}
 
 impl<'a> Iterator for LinkedPath<'a> {
     type Item = PathElem;
 
     fn next(&mut self) -> Option<PathElem> {
-        match *self {
+        match self.0 {
             Some(node) => {
                 *self = node.next;
                 Some(node.node)
@@ -384,7 +395,7 @@ impl<'ast> Map<'ast> {
     pub fn with_path<T, F>(&self, id: NodeId, f: F) -> T where
         F: FnOnce(PathElems) -> T,
     {
-        self.with_path_next(id, None, f)
+        self.with_path_next(id, LinkedPath::empty(), f)
     }
 
     pub fn path_to_string(&self, id: NodeId) -> String {
@@ -422,7 +433,7 @@ impl<'ast> Map<'ast> {
                 _ => f([].iter().cloned().chain(next))
             }
         } else {
-            self.with_path_next(parent, Some(&LinkedPathNode {
+            self.with_path_next(parent, LinkedPath::from(&LinkedPathNode {
                 node: self.get_path_elem(id),
                 next: next
             }), f)
diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs
index f88381fb36f..113827a3b40 100644
--- a/src/libsyntax/feature_gate.rs
+++ b/src/libsyntax/feature_gate.rs
@@ -91,6 +91,8 @@ const KNOWN_FEATURES: &'static [(&'static str, &'static str, Status)] = &[
     ("start", "1.0.0", Active),
     ("main", "1.0.0", Active),
 
+    ("fundamental", "1.0.0", Active),
+
     // Deprecate after snapshot
     // SNAP 5520801
     ("unsafe_destructor", "1.0.0", Active),
@@ -237,6 +239,10 @@ pub const KNOWN_ATTRIBUTES: &'static [(&'static str, AttributeType)] = &[
     ("allow_internal_unstable", Gated("allow_internal_unstable",
                                       EXPLAIN_ALLOW_INTERNAL_UNSTABLE)),
 
+    ("fundamental", Gated("fundamental",
+                          "the `#[fundamental]` attribute \
+                           is an experimental feature")),
+
     // FIXME: #14408 whitelist docs since rustdoc looks at them
     ("doc", Whitelisted),
 
diff --git a/src/test/auxiliary/coherence_copy_like_lib.rs b/src/test/auxiliary/coherence_copy_like_lib.rs
new file mode 100644
index 00000000000..a1e1b48c2c4
--- /dev/null
+++ b/src/test/auxiliary/coherence_copy_like_lib.rs
@@ -0,0 +1,22 @@
+// Copyright 2015 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 = "rlib"]
+#![feature(fundamental)]
+
+use std::marker::MarkerTrait;
+
+pub trait MyCopy : MarkerTrait { }
+impl MyCopy for i32 { }
+
+pub struct MyStruct<T>(T);
+
+#[fundamental]
+pub struct MyFundamentalStruct<T>(T);
diff --git a/src/test/run-pass/coherence-cow-1.rs b/src/test/compile-fail/coherence-cow-1.rs
index 31f6c9af020..530bbf57d91 100644
--- a/src/test/run-pass/coherence-cow-1.rs
+++ b/src/test/compile-fail/coherence-cow-1.rs
@@ -10,16 +10,19 @@
 
 // aux-build:coherence_lib.rs
 
-// Test that it's ok for T to appear first in the self-type, as long
-// as it's covered somewhere.
-
 // pretty-expanded FIXME #23616
 
+// Test that the `Pair` type reports an error if it contains type
+// parameters, even when they are covered by local types. This test
+// was originally intended to test the opposite, but the rules changed
+// with RFC 1023 and this became illegal.
+
 extern crate coherence_lib as lib;
 use lib::{Remote,Pair};
 
 pub struct Cover<T>(T);
 
 impl<T> Remote for Pair<T,Cover<T>> { }
+//~^ ERROR E0210
 
 fn main() { }
diff --git a/src/test/run-pass/coherence-cow-2.rs b/src/test/compile-fail/coherence-cow-2.rs
index ccda8440ea2..52abceab98b 100644
--- a/src/test/run-pass/coherence-cow-2.rs
+++ b/src/test/compile-fail/coherence-cow-2.rs
@@ -10,8 +10,10 @@
 
 // aux-build:coherence_lib.rs
 
-// Test that it's ok for T to appear second in the self-type, as long
-// as it's covered somewhere.
+// Test that the `Pair` type reports an error if it contains type
+// parameters, even when they are covered by local types. This test
+// was originally intended to test the opposite, but the rules changed
+// with RFC 1023 and this became illegal.
 
 // pretty-expanded FIXME #23616
 
@@ -20,6 +22,6 @@ use lib::{Remote,Pair};
 
 pub struct Cover<T>(T);
 
-impl<T> Remote for Pair<Cover<T>,T> { }
+impl<T> Remote for Pair<Cover<T>,T> { } //~ ERROR E0210
 
 fn main() { }
diff --git a/src/test/compile-fail/coherence-cow-no-cover.rs b/src/test/compile-fail/coherence-cow-no-cover.rs
index 475d7df1fdb..cd32e797ae9 100644
--- a/src/test/compile-fail/coherence-cow-no-cover.rs
+++ b/src/test/compile-fail/coherence-cow-no-cover.rs
@@ -10,7 +10,7 @@
 
 // aux-build:coherence_lib.rs
 
-// Test that it's not ok for U to appear uncovered
+// Test that it's not ok for T to appear uncovered
 
 extern crate coherence_lib as lib;
 use lib::{Remote,Pair};
@@ -18,6 +18,6 @@ use lib::{Remote,Pair};
 pub struct Cover<T>(T);
 
 impl<T,U> Remote for Pair<Cover<T>,U> { }
-//~^ ERROR type parameter `U` must be used as the type parameter for some local type
+//~^ ERROR type parameter `T` must be used as the type parameter for some local type
 
 fn main() { }
diff --git a/src/test/compile-fail/coherence-impls-copy.rs b/src/test/compile-fail/coherence-impls-copy.rs
index 3034be177ca..b99b2e1205b 100644
--- a/src/test/compile-fail/coherence-impls-copy.rs
+++ b/src/test/compile-fail/coherence-impls-copy.rs
@@ -23,17 +23,24 @@ impl !Sync for NotSync {}
 
 impl Copy for TestE {}
 impl Copy for MyType {}
+
+impl Copy for &'static mut MyType {}
+//~^ ERROR E0206
+
 impl Copy for (MyType, MyType) {}
 //~^ ERROR E0206
+//~| ERROR E0117
 
 impl Copy for &'static NotSync {}
 //~^ ERROR E0206
 
 impl Copy for [MyType] {}
 //~^ ERROR E0206
+//~| ERROR E0117
 
 impl Copy for &'static [NotSync] {}
 //~^ ERROR E0206
+//~| ERROR E0117
 
 fn main() {
 }
diff --git a/src/test/compile-fail/coherence-impls-send.rs b/src/test/compile-fail/coherence-impls-send.rs
index b05c1ff0f0b..f130a935351 100644
--- a/src/test/compile-fail/coherence-impls-send.rs
+++ b/src/test/compile-fail/coherence-impls-send.rs
@@ -24,17 +24,17 @@ impl !Sync for NotSync {}
 unsafe impl Send for TestE {}
 unsafe impl Send for MyType {}
 unsafe impl Send for (MyType, MyType) {}
-//~^ ERROR E0321
+//~^ ERROR E0117
 
 unsafe impl Send for &'static NotSync {}
 //~^ ERROR E0321
 
 unsafe impl Send for [MyType] {}
-//~^ ERROR E0321
+//~^ ERROR E0117
 
 unsafe impl Send for &'static [NotSync] {}
-//~^ ERROR E0321
-//~| ERROR conflicting implementations
+//~^ ERROR E0117
+//~| ERROR E0119
 
 fn main() {
 }
diff --git a/src/test/compile-fail/coherence-impls-sized.rs b/src/test/compile-fail/coherence-impls-sized.rs
index a9a3ebaffb7..2ac4bb0492b 100644
--- a/src/test/compile-fail/coherence-impls-sized.rs
+++ b/src/test/compile-fail/coherence-impls-sized.rs
@@ -22,12 +22,17 @@ struct NotSync;
 impl !Sync for NotSync {}
 
 impl Sized for TestE {} //~ ERROR E0322
+
 impl Sized for MyType {} //~ ERROR E0322
-impl Sized for (MyType, MyType) {} //~ ERROR E0322
+
+impl Sized for (MyType, MyType) {} //~ ERROR E0117
+
 impl Sized for &'static NotSync {} //~ ERROR E0322
-impl Sized for [MyType] {} //~ ERROR E0322
+
+impl Sized for [MyType] {} //~ ERROR E0117
 //~^ ERROR E0277
-impl Sized for &'static [NotSync] {} //~ ERROR E0322
+
+impl Sized for &'static [NotSync] {} //~ ERROR E0117
 
 fn main() {
 }
diff --git a/src/test/compile-fail/coherence-overlap-issue-23516.rs b/src/test/compile-fail/coherence-overlap-issue-23516.rs
new file mode 100644
index 00000000000..d7f060a3bfe
--- /dev/null
+++ b/src/test/compile-fail/coherence-overlap-issue-23516.rs
@@ -0,0 +1,19 @@
+// Copyright 2015 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.
+
+// Tests that we consider `Box<U>: !Sugar` to be ambiguous, even
+// though we see no impl of `Sugar` for `Box`. Therefore, an overlap
+// error is reported for the following pair of impls (#23516).
+
+pub trait Sugar { fn dummy(&self) { } }
+pub trait Sweet { fn dummy(&self) { } }
+impl<T:Sugar> Sweet for T { } //~ ERROR E0119
+impl<U:Sugar> Sweet for Box<U> { }
+fn main() { }
diff --git a/src/test/run-pass/coherence-local-2.rs b/src/test/compile-fail/coherence-vec-local-2.rs
index 5fd3e8ca86e..5f0b56af2c2 100644
--- a/src/test/run-pass/coherence-local-2.rs
+++ b/src/test/compile-fail/coherence-vec-local-2.rs
@@ -8,6 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+// Test that a local, generic type appearing within a
+// *non-fundamental* remote type like `Vec` is not considered local.
+
 // aux-build:coherence_lib.rs
 
 // pretty-expanded FIXME #23616
@@ -17,6 +20,6 @@ use lib::Remote;
 
 struct Local<T>(T);
 
-impl<T> Remote for Vec<Local<T>> { }
+impl<T> Remote for Vec<Local<T>> { } //~ ERROR E0210
 
 fn main() { }
diff --git a/src/test/run-pass/coherence-local-1.rs b/src/test/compile-fail/coherence-vec-local.rs
index 21faa30245d..c354caac2b5 100644
--- a/src/test/run-pass/coherence-local-1.rs
+++ b/src/test/compile-fail/coherence-vec-local.rs
@@ -8,6 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+// Test that a local type (with no type parameters) appearing within a
+// *non-fundamental* remote type like `Vec` is not considered local.
+
 // aux-build:coherence_lib.rs
 
 // pretty-expanded FIXME #23616
@@ -17,6 +20,6 @@ use lib::Remote;
 
 struct Local;
 
-impl Remote for Vec<Local> { }
+impl Remote for Vec<Local> { } //~ ERROR E0117
 
 fn main() { }
diff --git a/src/test/compile-fail/coherence_copy_like_err_fundamental_struct.rs b/src/test/compile-fail/coherence_copy_like_err_fundamental_struct.rs
new file mode 100644
index 00000000000..f13175ce8e2
--- /dev/null
+++ b/src/test/compile-fail/coherence_copy_like_err_fundamental_struct.rs
@@ -0,0 +1,36 @@
+// Copyright 2015 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.
+
+// Test that we are able to introduce a negative constraint that
+// `MyType: !MyTrait` along with other "fundamental" wrappers.
+
+// aux-build:coherence_copy_like_lib.rs
+
+#![feature(rustc_attrs)]
+#![allow(dead_code)]
+
+extern crate coherence_copy_like_lib as lib;
+
+use std::marker::MarkerTrait;
+
+struct MyType { x: i32 }
+
+trait MyTrait : MarkerTrait { }
+impl<T: lib::MyCopy> MyTrait for T { }
+
+// `MyFundamentalStruct` is declared fundamental, so we can test that
+//
+//    MyFundamentalStruct<MyTrait>: !MyTrait
+//
+// Huzzah.
+impl MyTrait for lib::MyFundamentalStruct<MyType> { }
+
+#[rustc_error]
+fn main() { } //~ ERROR compilation successful
diff --git a/src/test/compile-fail/coherence_copy_like_err_fundamental_struct_ref.rs b/src/test/compile-fail/coherence_copy_like_err_fundamental_struct_ref.rs
new file mode 100644
index 00000000000..ae3d242af70
--- /dev/null
+++ b/src/test/compile-fail/coherence_copy_like_err_fundamental_struct_ref.rs
@@ -0,0 +1,36 @@
+// Copyright 2015 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.
+
+// Test that we are able to introduce a negative constraint that
+// `MyType: !MyTrait` along with other "fundamental" wrappers.
+
+// aux-build:coherence_copy_like_lib.rs
+
+#![feature(rustc_attrs)]
+#![allow(dead_code)]
+
+extern crate coherence_copy_like_lib as lib;
+
+use std::marker::MarkerTrait;
+
+struct MyType { x: i32 }
+
+trait MyTrait : MarkerTrait { }
+impl<T: lib::MyCopy> MyTrait for T { }
+
+// `MyFundamentalStruct` is declared fundamental, so we can test that
+//
+//    MyFundamentalStruct<&MyTrait>: !MyTrait
+//
+// Huzzah.
+impl<'a> MyTrait for lib::MyFundamentalStruct<&'a MyType> { }
+
+#[rustc_error]
+fn main() { } //~ ERROR compilation successful
diff --git a/src/test/compile-fail/coherence_copy_like_err_fundamental_struct_tuple.rs b/src/test/compile-fail/coherence_copy_like_err_fundamental_struct_tuple.rs
new file mode 100644
index 00000000000..c4e95e77235
--- /dev/null
+++ b/src/test/compile-fail/coherence_copy_like_err_fundamental_struct_tuple.rs
@@ -0,0 +1,32 @@
+// Copyright 2015 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.
+
+// Test that we are able to introduce a negative constraint that
+// `MyType: !MyTrait` along with other "fundamental" wrappers.
+
+// aux-build:coherence_copy_like_lib.rs
+
+#![feature(rustc_attrs)]
+
+extern crate coherence_copy_like_lib as lib;
+
+use std::marker::MarkerTrait;
+
+struct MyType { x: i32 }
+
+trait MyTrait : MarkerTrait { }
+
+impl<T: lib::MyCopy> MyTrait for T { } //~ ERROR E0119
+
+// Tuples are not fundamental.
+impl MyTrait for lib::MyFundamentalStruct<(MyType,)> { }
+
+#[rustc_error]
+fn main() { }
diff --git a/src/test/compile-fail/coherence_copy_like_err_struct.rs b/src/test/compile-fail/coherence_copy_like_err_struct.rs
new file mode 100644
index 00000000000..f768a475ee8
--- /dev/null
+++ b/src/test/compile-fail/coherence_copy_like_err_struct.rs
@@ -0,0 +1,33 @@
+// Copyright 2015 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_copy_like_lib.rs
+
+// Test that we are able to introduce a negative constraint that
+// `MyType: !MyTrait` along with other "fundamental" wrappers.
+
+extern crate coherence_copy_like_lib as lib;
+
+use std::marker::MarkerTrait;
+
+struct MyType { x: i32 }
+
+trait MyTrait : MarkerTrait { }
+impl<T: lib::MyCopy> MyTrait for T { } //~ ERROR E0119
+
+// `MyStruct` is not declared fundamental, therefore this would
+// require that
+//
+//     MyStruct<MyType>: !MyTrait
+//
+// which we cannot approve.
+impl MyTrait for lib::MyStruct<MyType> { }
+
+fn main() { }
diff --git a/src/test/compile-fail/coherence_copy_like_err_tuple.rs b/src/test/compile-fail/coherence_copy_like_err_tuple.rs
new file mode 100644
index 00000000000..0c78fffd2df
--- /dev/null
+++ b/src/test/compile-fail/coherence_copy_like_err_tuple.rs
@@ -0,0 +1,32 @@
+// Copyright 2015 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.
+
+// Test that we are able to introduce a negative constraint that
+// `MyType: !MyTrait` along with other "fundamental" wrappers.
+
+// aux-build:coherence_copy_like_lib.rs
+
+extern crate coherence_copy_like_lib as lib;
+
+use std::marker::MarkerTrait;
+
+struct MyType { x: i32 }
+
+trait MyTrait : MarkerTrait { }
+impl<T: lib::MyCopy> MyTrait for T { } //~ ERROR E0119
+
+// Tuples are not fundamental, therefore this would require that
+//
+//     (MyType,): !MyTrait
+//
+// which we cannot approve.
+impl MyTrait for (MyType,) { }
+
+fn main() { }
diff --git a/src/test/compile-fail/coherence_local.rs b/src/test/compile-fail/coherence_local.rs
new file mode 100644
index 00000000000..551577b6b4e
--- /dev/null
+++ b/src/test/compile-fail/coherence_local.rs
@@ -0,0 +1,33 @@
+// Copyright 2015 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.
+
+// Test that we are able to introduce a negative constraint that
+// `MyType: !MyTrait` along with other "fundamental" wrappers.
+
+// aux-build:coherence_copy_like_lib.rs
+
+#![feature(rustc_attrs)]
+#![allow(dead_code)]
+
+extern crate coherence_copy_like_lib as lib;
+
+struct MyType { x: i32 }
+
+// These are all legal because they are all fundamental types:
+
+impl lib::MyCopy for MyType { }
+impl<'a> lib::MyCopy for &'a MyType { }
+impl<'a> lib::MyCopy for &'a Box<MyType> { }
+impl lib::MyCopy for Box<MyType> { }
+impl lib::MyCopy for lib::MyFundamentalStruct<MyType> { }
+impl lib::MyCopy for lib::MyFundamentalStruct<Box<MyType>> { }
+
+#[rustc_error]
+fn main() { } //~ ERROR compilation successful
diff --git a/src/test/compile-fail/coherence_local_err_struct.rs b/src/test/compile-fail/coherence_local_err_struct.rs
new file mode 100644
index 00000000000..01f4c1cd8a5
--- /dev/null
+++ b/src/test/compile-fail/coherence_local_err_struct.rs
@@ -0,0 +1,29 @@
+// Copyright 2015 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.
+
+// Test that we are able to introduce a negative constraint that
+// `MyType: !MyTrait` along with other "fundamental" wrappers.
+
+// aux-build:coherence_copy_like_lib.rs
+
+#![feature(rustc_attrs)]
+#![allow(dead_code)]
+
+extern crate coherence_copy_like_lib as lib;
+
+struct MyType { x: i32 }
+
+// These are all legal because they are all fundamental types:
+
+// MyStruct is not fundamental.
+impl lib::MyCopy for lib::MyStruct<MyType> { } //~ ERROR E0117
+
+#[rustc_error]
+fn main() { }
diff --git a/src/test/compile-fail/coherence_local_err_tuple.rs b/src/test/compile-fail/coherence_local_err_tuple.rs
new file mode 100644
index 00000000000..590f68cee59
--- /dev/null
+++ b/src/test/compile-fail/coherence_local_err_tuple.rs
@@ -0,0 +1,29 @@
+// Copyright 2015 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.
+
+// Test that we are able to introduce a negative constraint that
+// `MyType: !MyTrait` along with other "fundamental" wrappers.
+
+// aux-build:coherence_copy_like_lib.rs
+
+#![feature(rustc_attrs)]
+#![allow(dead_code)]
+
+extern crate coherence_copy_like_lib as lib;
+
+struct MyType { x: i32 }
+
+// These are all legal because they are all fundamental types:
+
+// Tuples are not fundamental, so this is not a local impl.
+impl lib::MyCopy for (MyType,) { } //~ ERROR E0117
+
+#[rustc_error]
+fn main() { }
diff --git a/src/test/compile-fail/coherence_local_ref.rs b/src/test/compile-fail/coherence_local_ref.rs
new file mode 100644
index 00000000000..f6e1aab5976
--- /dev/null
+++ b/src/test/compile-fail/coherence_local_ref.rs
@@ -0,0 +1,27 @@
+// Copyright 2015 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.
+
+// Test that we are able to introduce a negative constraint that
+// `MyType: !MyTrait` along with other "fundamental" wrappers.
+
+// aux-build:coherence_copy_like_lib.rs
+
+#![feature(rustc_attrs)]
+#![allow(dead_code)]
+
+extern crate coherence_copy_like_lib as lib;
+
+struct MyType { x: i32 }
+
+// naturally, legal
+impl lib::MyCopy for MyType { }
+
+#[rustc_error]
+fn main() { } //~ ERROR compilation successful
diff --git a/src/test/compile-fail/typeck-default-trait-impl-cross-crate-coherence.rs b/src/test/compile-fail/typeck-default-trait-impl-cross-crate-coherence.rs
index 7d25c04882f..b1febae7680 100644
--- a/src/test/compile-fail/typeck-default-trait-impl-cross-crate-coherence.rs
+++ b/src/test/compile-fail/typeck-default-trait-impl-cross-crate-coherence.rs
@@ -20,15 +20,15 @@ extern crate typeck_default_trait_impl_cross_crate_coherence_lib as lib;
 use lib::DefaultedTrait;
 
 struct A;
-impl DefaultedTrait for (A,) { } //~ ERROR E0321
+impl DefaultedTrait for (A,) { } //~ ERROR E0117
 
 struct B;
-impl !DefaultedTrait for (B,) { } //~ ERROR E0321
+impl !DefaultedTrait for (B,) { } //~ ERROR E0117
 
 struct C;
 struct D<T>(T);
 impl DefaultedTrait for Box<C> { } //~ ERROR E0321
-impl DefaultedTrait for lib::Something<C> { } //~ ERROR E0321
+impl DefaultedTrait for lib::Something<C> { } //~ ERROR E0117
 impl DefaultedTrait for D<C> { } // OK
 
 fn main() { }
diff --git a/src/test/run-pass/coherence_copy_like.rs b/src/test/run-pass/coherence_copy_like.rs
new file mode 100644
index 00000000000..db9893613ad
--- /dev/null
+++ b/src/test/run-pass/coherence_copy_like.rs
@@ -0,0 +1,29 @@
+// Copyright 2015 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.
+
+// Test that we are able to introduce a negative constraint that
+// `MyType: !MyTrait` along with other "fundamental" wrappers.
+
+// aux-build:coherence_copy_like_lib.rs
+
+extern crate coherence_copy_like_lib as lib;
+
+use std::marker::MarkerTrait;
+
+struct MyType { x: i32 }
+
+trait MyTrait : MarkerTrait { }
+impl<T: lib::MyCopy> MyTrait for T { }
+impl MyTrait for MyType { }
+impl<'a> MyTrait for &'a MyType { }
+impl MyTrait for Box<MyType> { }
+impl<'a> MyTrait for &'a Box<MyType> { }
+
+fn main() { }
diff --git a/src/test/run-pass/method-two-trait-defer-resolution-2.rs b/src/test/run-pass/method-two-trait-defer-resolution-2.rs
index d87ed03e94e..2ceff22adb9 100644
--- a/src/test/run-pass/method-two-trait-defer-resolution-2.rs
+++ b/src/test/run-pass/method-two-trait-defer-resolution-2.rs
@@ -8,13 +8,16 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// Test that we pick which version of `Foo` to run based on whether
-// the type we (ultimately) inferred for `x` is copyable or not.
-//
-// In this case, the two versions are both impls of same trait, and
-// hence we we can resolve method even without knowing yet which
-// version will run (note that the `push` occurs after the call to
-// `foo()`).
+// Test that when we write `x.foo()`, we do nothave to know the
+// complete type of `x` in order to type-check the method call. In
+// this case, we know that `x: Vec<_1>`, but we don't know what type
+// `_1` is (because the call to `push` comes later). To pick between
+// the impls, we would have to know `_1`, since we have to know
+// whether `_1: MyCopy` or `_1 == Box<i32>`.  However (and this is the
+// point of the test), we don't have to pick between the two impls --
+// it is enough to know that `foo` comes from the `Foo` trait. We can
+// translate the call as `Foo::foo(&x)` and let the specific impl get
+// chosen later.
 
 // pretty-expanded FIXME #23616
 
@@ -25,25 +28,29 @@ trait Foo {
     fn foo(&self) -> isize;
 }
 
-impl<T:Copy> Foo for Vec<T> {
+trait MyCopy { fn foo(&self) { } }
+impl MyCopy for i32 { }
+
+impl<T:MyCopy> Foo for Vec<T> {
     fn foo(&self) -> isize {1}
 }
 
-impl<T> Foo for Vec<Box<T>> {
+impl Foo for Vec<Box<i32>> {
     fn foo(&self) -> isize {2}
 }
 
 fn call_foo_copy() -> isize {
     let mut x = Vec::new();
     let y = x.foo();
-    x.push(0_usize);
+    x.push(0_i32);
     y
 }
 
 fn call_foo_other() -> isize {
-    let mut x: Vec<Box<_>> = Vec::new();
+    let mut x: Vec<_> = Vec::new();
     let y = x.foo();
-    x.push(box 0);
+    let z: Box<i32> = box 0;
+    x.push(z);
     y
 }
 
diff --git a/src/test/run-pass/traits-conditional-dispatch.rs b/src/test/run-pass/traits-conditional-dispatch.rs
index 5edd3dfbc9e..0190b7b7b96 100644
--- a/src/test/run-pass/traits-conditional-dispatch.rs
+++ b/src/test/run-pass/traits-conditional-dispatch.rs
@@ -17,16 +17,24 @@
 #![allow(unknown_features)]
 #![feature(box_syntax)]
 
+use std::marker::MarkerTrait;
+
 trait Get {
     fn get(&self) -> Self;
 }
 
-impl<T:Copy> Get for T {
-    fn get(&self) -> T { *self }
+trait MyCopy : MarkerTrait { fn copy(&self) -> Self; }
+impl MyCopy for u16 { fn copy(&self) -> Self { *self } }
+impl MyCopy for u32 { fn copy(&self) -> Self { *self } }
+impl MyCopy for i32 { fn copy(&self) -> Self { *self } }
+impl<T:Copy> MyCopy for Option<T> { fn copy(&self) -> Self { *self } }
+
+impl<T:MyCopy> Get for T {
+    fn get(&self) -> T { self.copy() }
 }
 
-impl<T:Get> Get for Box<T> {
-    fn get(&self) -> Box<T> { box get_it(&**self) }
+impl Get for Box<i32> {
+    fn get(&self) -> Box<i32> { box get_it(&**self) }
 }
 
 fn get_it<T:Get>(t: &T) -> T {