rollup merge of #23712: nikomatsakis/reflect-trait

This PR introduces a `Reflect` marker trait which is a supertrait of `Any`. The idea is that `Reflect` is defined for all concrete types, but is not defined for type parameters unless there is a `T:Reflect` bound. This is intended to preserve the parametricity property. This allows the `Any` interface to be stabilized without committing us to unbounded reflection that is not easily detectable by the caller.

The implementation of `Reflect` relies on an experimental variant of OIBIT. This variant behaves differently for objects, since it requires that all types exposed as part of the object's *interface* are `Reflect`, but isn't concerned about other types that may be closed over. In other words, you don't have to write `Foo+Reflect` in order for `Foo: Reflect` to hold (where `Foo` is a trait).

Given that `Any` is slated to stabilization and hence that we are committed to some form of reflection, the goal of this PR is to leave our options open with respect to parametricity. I see the options for full stabilization as follows (I think an RFC would be an appropriate way to confirm whichever of these three routes we take):

1. We make `Reflect` a lang-item.
2. We stabilize some version of the OIBIT variation I implemented as a general mechanism that may be appropriate for other use cases.
3. We give up on preserving parametricity here and just have `impl<T> Reflect for T` instead. In that case, `Reflect` is a harmless but not especially useful trait going forward.

cc @aturon
cc @alexcrichton
cc @glaebhoerl (this is more-or-less your proposal, as I understood it)
cc @reem (this is more-or-less what we discussed on IRC at some point)
cc @FlaPer87 (vaguely pertains to OIBIT)

21 files changed, 568 insertions, 173 deletions

diff --git a/src/liballoc/boxed.rs b/src/liballoc/boxed.rs
index 8b18fbf554a..f9bd0ab2f1e 100644
--- a/src/liballoc/boxed.rs
+++ b/src/liballoc/boxed.rs
@@ -244,13 +244,13 @@ pub trait BoxAny {
     /// Returns the boxed value if it is of type `T`, or
     /// `Err(Self)` if it isn't.
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn downcast<T: 'static>(self) -> Result<Box<T>, Box<Any>>;
+    fn downcast<T: Any>(self) -> Result<Box<T>, Box<Any>>;
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl BoxAny for Box<Any> {
     #[inline]
-    fn downcast<T: 'static>(self) -> Result<Box<T>, Box<Any>> {
+    fn downcast<T: Any>(self) -> Result<Box<T>, Box<Any>> {
         if self.is::<T>() {
             unsafe {
                 // Get the raw representation of the trait object
@@ -270,7 +270,7 @@ impl BoxAny for Box<Any> {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl BoxAny for Box<Any+Send> {
     #[inline]
-    fn downcast<T: 'static>(self) -> Result<Box<T>, Box<Any>> {
+    fn downcast<T: Any>(self) -> Result<Box<T>, Box<Any>> {
         <Box<Any>>::downcast(self)
     }
 }
diff --git a/src/libcore/any.rs b/src/libcore/any.rs
index c94d8e2ed0c..d3bc07b173a 100644
--- a/src/libcore/any.rs
+++ b/src/libcore/any.rs
@@ -55,7 +55,7 @@
 //! }
 //!
 //! // This function wants to log its parameter out prior to doing work with it.
-//! fn do_work<T: Debug + 'static>(value: &T) {
+//! fn do_work<T: Any + Debug>(value: &T) {
 //!     log(value);
 //!     // ...do some other work
 //! }
@@ -76,7 +76,7 @@ use mem::transmute;
 use option::Option::{self, Some, None};
 use raw::TraitObject;
 use intrinsics;
-use marker::Sized;
+use marker::{Reflect, Sized};
 
 ///////////////////////////////////////////////////////////////////////////////
 // Any trait
@@ -88,14 +88,16 @@ use marker::Sized;
 ///
 /// [mod]: ../index.html
 #[stable(feature = "rust1", since = "1.0.0")]
-pub trait Any: 'static {
+pub trait Any: Reflect + 'static {
     /// Get the `TypeId` of `self`
     #[unstable(feature = "core",
                reason = "this method will likely be replaced by an associated static")]
     fn get_type_id(&self) -> TypeId;
 }
 
-impl<T: 'static> Any for T {
+impl<T> Any for T
+    where T: Reflect + 'static
+{
     fn get_type_id(&self) -> TypeId { TypeId::of::<T>() }
 }
 
@@ -107,7 +109,7 @@ impl Any {
     /// Returns true if the boxed type is the same as `T`
     #[stable(feature = "rust1", since = "1.0.0")]
     #[inline]
-    pub fn is<T: 'static>(&self) -> bool {
+    pub fn is<T: Any>(&self) -> bool {
         // Get TypeId of the type this function is instantiated with
         let t = TypeId::of::<T>();
 
@@ -122,7 +124,7 @@ impl Any {
     /// `None` if it isn't.
     #[stable(feature = "rust1", since = "1.0.0")]
     #[inline]
-    pub fn downcast_ref<T: 'static>(&self) -> Option<&T> {
+    pub fn downcast_ref<T: Any>(&self) -> Option<&T> {
         if self.is::<T>() {
             unsafe {
                 // Get the raw representation of the trait object
@@ -140,7 +142,7 @@ impl Any {
     /// `None` if it isn't.
     #[stable(feature = "rust1", since = "1.0.0")]
     #[inline]
-    pub fn downcast_mut<T: 'static>(&mut self) -> Option<&mut T> {
+    pub fn downcast_mut<T: Any>(&mut self) -> Option<&mut T> {
         if self.is::<T>() {
             unsafe {
                 // Get the raw representation of the trait object
@@ -159,21 +161,21 @@ impl Any+Send {
     /// Forwards to the method defined on the type `Any`.
     #[stable(feature = "rust1", since = "1.0.0")]
     #[inline]
-    pub fn is<T: 'static>(&self) -> bool {
+    pub fn is<T: Any>(&self) -> bool {
         Any::is::<T>(self)
     }
 
     /// Forwards to the method defined on the type `Any`.
     #[stable(feature = "rust1", since = "1.0.0")]
     #[inline]
-    pub fn downcast_ref<T: 'static>(&self) -> Option<&T> {
+    pub fn downcast_ref<T: Any>(&self) -> Option<&T> {
         Any::downcast_ref::<T>(self)
     }
 
     /// Forwards to the method defined on the type `Any`.
     #[stable(feature = "rust1", since = "1.0.0")]
     #[inline]
-    pub fn downcast_mut<T: 'static>(&mut self) -> Option<&mut T> {
+    pub fn downcast_mut<T: Any>(&mut self) -> Option<&mut T> {
         Any::downcast_mut::<T>(self)
     }
 }
@@ -202,7 +204,7 @@ impl TypeId {
     /// instantiated with
     #[unstable(feature = "core",
                reason = "may grow a `Reflect` bound soon via marker traits")]
-    pub fn of<T: ?Sized + 'static>() -> TypeId {
+    pub fn of<T: ?Sized + Any>() -> TypeId {
         TypeId {
             t: unsafe { intrinsics::type_id::<T>() },
         }
diff --git a/src/libcore/lib.rs b/src/libcore/lib.rs
index a2b13584270..7225b016e6b 100644
--- a/src/libcore/lib.rs
+++ b/src/libcore/lib.rs
@@ -72,6 +72,7 @@
 #![feature(rustc_attrs)]
 #![feature(optin_builtin_traits)]
 #![feature(concat_idents)]
+#![feature(reflect)]
 
 #[macro_use]
 mod macros;
diff --git a/src/libcore/marker.rs b/src/libcore/marker.rs
index 88c10e3661e..35fde2cb64a 100644
--- a/src/libcore/marker.rs
+++ b/src/libcore/marker.rs
@@ -450,3 +450,46 @@ pub struct CovariantType<T>;
 #[deprecated(since = "1.0.0", reason = "Replace with `PhantomData<Cell<T>>`")]
 #[lang="invariant_type"]
 pub struct InvariantType<T>;
+
+/// A marker trait indicates a type that can be reflected over. This
+/// trait is implemented for all types. Its purpose is to ensure that
+/// when you write a generic function that will employ reflection,
+/// that must be reflected (no pun intended) in the generic bounds of
+/// that function. Here is an example:
+///
+/// ```
+/// #![feature(core)]
+/// use std::marker::Reflect;
+/// use std::any::Any;
+/// fn foo<T:Reflect+'static>(x: &T) {
+///     let any: &Any = x;
+///     if any.is::<u32>() { println!("u32"); }
+/// }
+/// ```
+///
+/// Without the declaration `T:Reflect`, `foo` would not type check
+/// (note: as a matter of style, it would be preferable to to write
+/// `T:Any`, because `T:Any` implies `T:Reflect` and `T:'static`, but
+/// we use `Reflect` here to show how it works). The `Reflect` bound
+/// thus serves to alert `foo`'s caller to the fact that `foo` may
+/// behave differently depending on whether `T=u32` or not. In
+/// particular, thanks to the `Reflect` bound, callers know that a
+/// function declared like `fn bar<T>(...)` will always act in
+/// precisely the same way no matter what type `T` is supplied,
+/// beacuse there are no bounds declared on `T`. (The ability for a
+/// caller to reason about what a function may do based solely on what
+/// generic bounds are declared is often called the ["parametricity
+/// property"][1].)
+///
+/// [1]: http://en.wikipedia.org/wiki/Parametricity
+#[rustc_reflect_like]
+#[unstable(feature = "core", reason = "requires RFC and more experience")]
+pub trait Reflect : MarkerTrait {
+}
+
+#[cfg(stage0)]
+impl<T> Reflect for T { }
+
+#[cfg(not(stage0))]
+impl Reflect for .. { }
+
diff --git a/src/librustc/middle/traits/fulfill.rs b/src/librustc/middle/traits/fulfill.rs
index 3d46f93914a..2eaa536dabe 100644
--- a/src/librustc/middle/traits/fulfill.rs
+++ b/src/librustc/middle/traits/fulfill.rs
@@ -163,6 +163,8 @@ impl<'tcx> FulfillmentContext<'tcx> {
         // debug output much nicer to read and so on.
         let obligation = infcx.resolve_type_vars_if_possible(&obligation);
 
+        assert!(!obligation.has_escaping_regions());
+
         if !self.duplicate_set.insert(obligation.predicate.clone()) {
             debug!("register_predicate({}) -- already seen, skip", obligation.repr(infcx.tcx));
             return;
diff --git a/src/librustc/middle/traits/mod.rs b/src/librustc/middle/traits/mod.rs
index 24b201c960f..ffc11efe7c7 100644
--- a/src/librustc/middle/traits/mod.rs
+++ b/src/librustc/middle/traits/mod.rs
@@ -48,6 +48,8 @@ pub use self::util::get_vtable_index_of_object_method;
 pub use self::util::trait_ref_for_builtin_bound;
 pub use self::util::supertraits;
 pub use self::util::Supertraits;
+pub use self::util::supertrait_def_ids;
+pub use self::util::SupertraitDefIds;
 pub use self::util::transitive_bounds;
 pub use self::util::upcast;
 
@@ -640,7 +642,7 @@ impl<'tcx> FulfillmentError<'tcx> {
 }
 
 impl<'tcx> TraitObligation<'tcx> {
-    fn self_ty(&self) -> Ty<'tcx> {
-        self.predicate.0.self_ty()
+    fn self_ty(&self) -> ty::Binder<Ty<'tcx>> {
+        ty::Binder(self.predicate.skip_binder().self_ty())
     }
 }
diff --git a/src/librustc/middle/traits/object_safety.rs b/src/librustc/middle/traits/object_safety.rs
index 881487a2dad..9dccadc932b 100644
--- a/src/librustc/middle/traits/object_safety.rs
+++ b/src/librustc/middle/traits/object_safety.rs
@@ -53,36 +53,36 @@ pub enum MethodViolationCode {
 }
 
 pub fn is_object_safe<'tcx>(tcx: &ty::ctxt<'tcx>,
-                            trait_ref: ty::PolyTraitRef<'tcx>)
+                            trait_def_id: ast::DefId)
                             -> bool
 {
     // Because we query yes/no results frequently, we keep a cache:
     let cached_result =
-        tcx.object_safety_cache.borrow().get(&trait_ref.def_id()).cloned();
+        tcx.object_safety_cache.borrow().get(&trait_def_id).cloned();
 
     let result =
         cached_result.unwrap_or_else(|| {
-            let result = object_safety_violations(tcx, trait_ref.clone()).is_empty();
+            let result = object_safety_violations(tcx, trait_def_id).is_empty();
 
             // Record just a yes/no result in the cache; this is what is
             // queried most frequently. Note that this may overwrite a
             // previous result, but always with the same thing.
-            tcx.object_safety_cache.borrow_mut().insert(trait_ref.def_id(), result);
+            tcx.object_safety_cache.borrow_mut().insert(trait_def_id, result);
 
             result
         });
 
-    debug!("is_object_safe({}) = {}", trait_ref.repr(tcx), result);
+    debug!("is_object_safe({}) = {}", trait_def_id.repr(tcx), result);
 
     result
 }
 
 pub fn object_safety_violations<'tcx>(tcx: &ty::ctxt<'tcx>,
-                                      sub_trait_ref: ty::PolyTraitRef<'tcx>)
+                                      trait_def_id: ast::DefId)
                                       -> Vec<ObjectSafetyViolation<'tcx>>
 {
-    supertraits(tcx, sub_trait_ref)
-        .flat_map(|tr| object_safety_violations_for_trait(tcx, tr.def_id()).into_iter())
+    traits::supertrait_def_ids(tcx, trait_def_id)
+        .flat_map(|def_id| object_safety_violations_for_trait(tcx, def_id).into_iter())
         .collect()
 }
 
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index 0d6a1f7df5e..7e89534026f 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -138,6 +138,7 @@ enum SelectionCandidate<'tcx> {
     ParamCandidate(ty::PolyTraitRef<'tcx>),
     ImplCandidate(ast::DefId),
     DefaultImplCandidate(ast::DefId),
+    DefaultImplObjectCandidate(ast::DefId),
 
     /// This is a trait matching with a projected type as `Self`, and
     /// we found an applicable bound in the trait definition.
@@ -171,7 +172,7 @@ struct SelectionCandidateSet<'tcx> {
 }
 
 enum BuiltinBoundConditions<'tcx> {
-    If(Vec<Ty<'tcx>>),
+    If(ty::Binder<Vec<Ty<'tcx>>>),
     ParameterBuiltin,
     AmbiguousBuiltin
 }
@@ -292,7 +293,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         // because if it is a closure type, it must be a closure type from
         // within this current fn, and hence none of the higher-ranked
         // lifetimes can appear inside the self-type.
-        let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
+        let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
         let (closure_def_id, substs) = match self_ty.sty {
             ty::ty_closure(id, ref substs) => (id, substs.clone()),
             _ => { return; }
@@ -1050,7 +1051,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             None => { return Ok(()); }
         };
 
-        let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
+        // ok to skip binder because the substs on closure types never
+        // touch bound regions, they just capture the in-scope
+        // type/region parameters
+        let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
         let (closure_def_id, substs) = match self_ty.sty {
             ty::ty_closure(id, ref substs) => (id, substs.clone()),
             ty::ty_infer(ty::TyVar(_)) => {
@@ -1093,7 +1097,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             return Ok(());
         }
 
-        let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
+        // ok to skip binder because what we are inspecting doesn't involve bound regions
+        let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
         match self_ty.sty {
             ty::ty_infer(ty::TyVar(_)) => {
                 debug!("assemble_fn_pointer_candidates: ambiguous self-type");
@@ -1125,8 +1130,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                       candidates: &mut SelectionCandidateSet<'tcx>)
                                       -> Result<(), SelectionError<'tcx>>
     {
-        let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
-        debug!("assemble_candidates_from_impls(self_ty={})", self_ty.repr(self.tcx()));
+        debug!("assemble_candidates_from_impls(obligation={})", obligation.repr(self.tcx()));
 
         let def_id = obligation.predicate.def_id();
         let all_impls = self.all_impls(def_id);
@@ -1152,15 +1156,28 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                               candidates: &mut SelectionCandidateSet<'tcx>)
                                               -> Result<(), SelectionError<'tcx>>
     {
-
-        let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
+        // OK to skip binder here because the tests we do below do not involve bound regions
+        let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
         debug!("assemble_candidates_from_default_impls(self_ty={})", self_ty.repr(self.tcx()));
 
         let def_id = obligation.predicate.def_id();
 
         if ty::trait_has_default_impl(self.tcx(), def_id) {
             match self_ty.sty {
-                ty::ty_trait(..) |
+                ty::ty_trait(..) => {
+                    // For object types, we don't know what the closed
+                    // over types are. For most traits, this means we
+                    // conservatively say nothing; a candidate may be
+                    // added by `assemble_candidates_from_object_ty`.
+                    // However, for the kind of magic reflect trait,
+                    // we consider it to be implemented even for
+                    // object types, because it just lets you reflect
+                    // onto the object type, not into the object's
+                    // interior.
+                    if ty::has_attr(self.tcx(), def_id, "rustc_reflect_like") {
+                        candidates.vec.push(DefaultImplObjectCandidate(def_id));
+                    }
+                }
                 ty::ty_param(..) |
                 ty::ty_projection(..) => {
                     // In these cases, we don't know what the actual
@@ -1210,10 +1227,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                           obligation: &TraitObligation<'tcx>,
                                           candidates: &mut SelectionCandidateSet<'tcx>)
     {
-        let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
-
         debug!("assemble_candidates_from_object_ty(self_ty={})",
-               self_ty.repr(self.tcx()));
+               self.infcx.shallow_resolve(*obligation.self_ty().skip_binder()).repr(self.tcx()));
 
         // Object-safety candidates are only applicable to object-safe
         // traits. Including this check is useful because it helps
@@ -1222,47 +1237,56 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         // self-type from one of the other inputs. Without this check,
         // these cases wind up being considered ambiguous due to a
         // (spurious) ambiguity introduced here.
-        if !object_safety::is_object_safe(self.tcx(), obligation.predicate.to_poly_trait_ref()) {
+        let predicate_trait_ref = obligation.predicate.to_poly_trait_ref();
+        if !object_safety::is_object_safe(self.tcx(), predicate_trait_ref.def_id()) {
             return;
         }
 
-        let poly_trait_ref = match self_ty.sty {
-            ty::ty_trait(ref data) => {
-                match self.tcx().lang_items.to_builtin_kind(obligation.predicate.def_id()) {
-                    Some(bound @ ty::BoundSend) | Some(bound @ ty::BoundSync) => {
-                        if data.bounds.builtin_bounds.contains(&bound) {
-                            debug!("assemble_candidates_from_object_ty: matched builtin bound, \
-                            pushing candidate");
-                            candidates.vec.push(BuiltinObjectCandidate);
-                            return;
+        self.infcx.try(|snapshot| {
+            let bound_self_ty =
+                self.infcx.resolve_type_vars_if_possible(&obligation.self_ty());
+            let (self_ty, _) =
+                self.infcx().skolemize_late_bound_regions(&bound_self_ty, snapshot);
+            let poly_trait_ref = match self_ty.sty {
+                ty::ty_trait(ref data) => {
+                    match self.tcx().lang_items.to_builtin_kind(obligation.predicate.def_id()) {
+                        Some(bound @ ty::BoundSend) | Some(bound @ ty::BoundSync) => {
+                            if data.bounds.builtin_bounds.contains(&bound) {
+                                debug!("assemble_candidates_from_object_ty: matched builtin bound, \
+                                        pushing candidate");
+                                candidates.vec.push(BuiltinObjectCandidate);
+                                return Ok(());
+                            }
                         }
+                        _ => {}
                     }
-                    _ => {}
+
+                    data.principal_trait_ref_with_self_ty(self.tcx(), self_ty)
+                }
+                ty::ty_infer(ty::TyVar(_)) => {
+                    debug!("assemble_candidates_from_object_ty: ambiguous");
+                    candidates.ambiguous = true; // could wind up being an object type
+                    return Ok(());
+                }
+                _ => {
+                    return Ok(());
                 }
+            };
 
-                data.principal_trait_ref_with_self_ty(self.tcx(), self_ty)
-            }
-            ty::ty_infer(ty::TyVar(_)) => {
-                debug!("assemble_candidates_from_object_ty: ambiguous");
-                candidates.ambiguous = true; // could wind up being an object type
-                return;
-            }
-            _ => {
-                return;
-            }
-        };
+            debug!("assemble_candidates_from_object_ty: poly_trait_ref={}",
+                   poly_trait_ref.repr(self.tcx()));
 
-        debug!("assemble_candidates_from_object_ty: poly_trait_ref={}",
-               poly_trait_ref.repr(self.tcx()));
+            // see whether the object trait can be upcast to the trait we are looking for
+            let upcast_trait_refs = self.upcast(poly_trait_ref, obligation);
+            if upcast_trait_refs.len() > 1 {
+                // can be upcast in many ways; need more type information
+                candidates.ambiguous = true;
+            } else if upcast_trait_refs.len() == 1 {
+                candidates.vec.push(ObjectCandidate);
+            }
 
-        // see whether the object trait can be upcast to the trait we are looking for
-        let upcast_trait_refs = self.upcast(poly_trait_ref, obligation);
-        if upcast_trait_refs.len() > 1 {
-            // can be upcast in many ways; need more type information
-            candidates.ambiguous = true;
-        } else if upcast_trait_refs.len() == 1 {
-            candidates.vec.push(ObjectCandidate);
-        }
+            Ok::<(),()>(())
+        }).unwrap();
     }
 
     ///////////////////////////////////////////////////////////////////////////
@@ -1397,23 +1421,23 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
         let self_ty = self.infcx.shallow_resolve(obligation.predicate.0.self_ty());
         return match self_ty.sty {
-            ty::ty_infer(ty::IntVar(_))
-            | ty::ty_infer(ty::FloatVar(_))
-            | ty::ty_uint(_)
-            | ty::ty_int(_)
-            | ty::ty_bool
-            | ty::ty_float(_)
-            | ty::ty_bare_fn(..)
-            | ty::ty_char => {
+            ty::ty_infer(ty::IntVar(_)) |
+            ty::ty_infer(ty::FloatVar(_)) |
+            ty::ty_uint(_) |
+            ty::ty_int(_) |
+            ty::ty_bool |
+            ty::ty_float(_) |
+            ty::ty_bare_fn(..) |
+            ty::ty_char => {
                 // safe for everything
-                Ok(If(Vec::new()))
+                ok_if(Vec::new())
             }
 
             ty::ty_uniq(_) => {  // Box<T>
                 match bound {
                     ty::BoundCopy => Err(Unimplemented),
 
-                    ty::BoundSized => Ok(If(Vec::new())),
+                    ty::BoundSized => ok_if(Vec::new()),
 
                     ty::BoundSync | ty::BoundSend => {
                         self.tcx().sess.bug("Send/Sync shouldn't occur in builtin_bounds()");
@@ -1423,7 +1447,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
             ty::ty_ptr(..) => {     // *const T, *mut T
                 match bound {
-                    ty::BoundCopy | ty::BoundSized => Ok(If(Vec::new())),
+                    ty::BoundCopy | ty::BoundSized => ok_if(Vec::new()),
 
                     ty::BoundSync | ty::BoundSend => {
                         self.tcx().sess.bug("Send/Sync shouldn't occur in builtin_bounds()");
@@ -1436,7 +1460,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     ty::BoundSized => Err(Unimplemented),
                     ty::BoundCopy => {
                         if data.bounds.builtin_bounds.contains(&bound) {
-                            Ok(If(Vec::new()))
+                            ok_if(Vec::new())
                         } else {
                             // Recursively check all supertraits to find out if any further
                             // bounds are required and thus we must fulfill.
@@ -1446,7 +1470,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                             let desired_def_id = obligation.predicate.def_id();
                             for tr in util::supertraits(self.tcx(), principal) {
                                 if tr.def_id() == desired_def_id {
-                                    return Ok(If(Vec::new()))
+                                    return ok_if(Vec::new())
                                 }
                             }
 
@@ -1468,11 +1492,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                             ast::MutMutable => Err(Unimplemented),
 
                             // &T is always copyable
-                            ast::MutImmutable => Ok(If(Vec::new())),
+                            ast::MutImmutable => ok_if(Vec::new()),
                         }
                     }
 
-                    ty::BoundSized => Ok(If(Vec::new())),
+                    ty::BoundSized => ok_if(Vec::new()),
 
                     ty::BoundSync | ty::BoundSend => {
                         self.tcx().sess.bug("Send/Sync shouldn't occur in builtin_bounds()");
@@ -1486,7 +1510,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     ty::BoundCopy => {
                         match *len {
                             // [T, ..n] is copy iff T is copy
-                            Some(_) => Ok(If(vec![element_ty])),
+                            Some(_) => ok_if(vec![element_ty]),
 
                             // [T] is unsized and hence affine
                             None => Err(Unimplemented),
@@ -1495,7 +1519,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
                     ty::BoundSized => {
                         if len.is_some() {
-                            Ok(If(Vec::new()))
+                            ok_if(Vec::new())
                         } else {
                             Err(Unimplemented)
                         }
@@ -1519,7 +1543,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             }
 
             // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
-            ty::ty_tup(ref tys) => Ok(If(tys.clone())),
+            ty::ty_tup(ref tys) => ok_if(tys.clone()),
 
             ty::ty_closure(def_id, substs) => {
                 // FIXME -- This case is tricky. In the case of by-ref
@@ -1544,11 +1568,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 // unsized, so the closure struct as a whole must be
                 // Sized.
                 if bound == ty::BoundSized {
-                    return Ok(If(Vec::new()));
+                    return ok_if(Vec::new());
                 }
 
                 match self.closure_typer.closure_upvars(def_id, substs) {
-                    Some(upvars) => Ok(If(upvars.iter().map(|c| c.ty).collect())),
+                    Some(upvars) => ok_if(upvars.iter().map(|c| c.ty).collect()),
                     None => {
                         debug!("assemble_builtin_bound_candidates: no upvar types available yet");
                         Ok(AmbiguousBuiltin)
@@ -1590,7 +1614,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 Ok(AmbiguousBuiltin)
             }
 
-            ty::ty_err => Ok(If(Vec::new())),
+            ty::ty_err => ok_if(Vec::new()),
 
             ty::ty_infer(ty::FreshTy(_))
             | ty::ty_infer(ty::FreshIntTy(_)) => {
@@ -1601,6 +1625,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             }
         };
 
+        fn ok_if<'tcx>(v: Vec<Ty<'tcx>>)
+                       -> Result<BuiltinBoundConditions<'tcx>, SelectionError<'tcx>> {
+            Ok(If(ty::Binder(v)))
+        }
+
         fn nominal<'cx, 'tcx>(bound: ty::BuiltinBound,
                               types: Vec<Ty<'tcx>>)
                               -> Result<BuiltinBoundConditions<'tcx>, SelectionError<'tcx>>
@@ -1611,7 +1640,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 ty::BoundCopy => Ok(ParameterBuiltin),
 
                 // Sized if all the component types are sized.
-                ty::BoundSized => Ok(If(types)),
+                ty::BoundSized => ok_if(types),
 
                 // Shouldn't be coming through here.
                 ty::BoundSend | ty::BoundSync => unreachable!(),
@@ -1714,8 +1743,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     fn collect_predicates_for_types(&mut self,
                                     obligation: &TraitObligation<'tcx>,
                                     trait_def_id: ast::DefId,
-                                    types: Vec<Ty<'tcx>>) -> Vec<PredicateObligation<'tcx>> {
-
+                                    types: ty::Binder<Vec<Ty<'tcx>>>)
+                                    -> Vec<PredicateObligation<'tcx>>
+    {
         let derived_cause = match self.tcx().lang_items.to_builtin_kind(trait_def_id) {
             Some(_) => {
                 self.derived_cause(obligation, BuiltinDerivedObligation)
@@ -1725,43 +1755,52 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             }
         };
 
-        let normalized = project::normalize_with_depth(self, obligation.cause.clone(),
-                                                       obligation.recursion_depth + 1,
-                                                       &types);
-
-        let obligations = normalized.value.iter().map(|&nested_ty| {
-            // the obligation might be higher-ranked, e.g. for<'a> &'a
-            // int : Copy. In that case, we will wind up with
-            // late-bound regions in the `nested` vector. So for each
-            // one we instantiate to a skolemized region, do our work
-            // to produce something like `&'0 int : Copy`, and then
-            // re-bind it. This is a bit of busy-work but preserves
-            // the invariant that we only manipulate free regions, not
-            // bound ones.
+        // Because the types were potentially derived from
+        // higher-ranked obligations they may reference late-bound
+        // regions. For example, `for<'a> Foo<&'a int> : Copy` would
+        // yield a type like `for<'a> &'a int`. In general, we
+        // maintain the invariant that we never manipulate bound
+        // regions, so we have to process these bound regions somehow.
+        //
+        // The strategy is to:
+        //
+        // 1. Instantiate those regions to skolemized regions (e.g.,
+        //    `for<'a> &'a int` becomes `&0 int`.
+        // 2. Produce something like `&'0 int : Copy`
+        // 3. Re-bind the regions back to `for<'a> &'a int : Copy`
+
+        // Move the binder into the individual types
+        let bound_types: Vec<ty::Binder<Ty<'tcx>>> =
+            types.skip_binder()
+                 .iter()
+                 .map(|&nested_ty| ty::Binder(nested_ty))
+                 .collect();
+
+        // For each type, produce a vector of resulting obligations
+        let obligations: Result<Vec<Vec<_>>, _> = bound_types.iter().map(|nested_ty| {
             self.infcx.try(|snapshot| {
                 let (skol_ty, skol_map) =
-                    self.infcx().skolemize_late_bound_regions(&ty::Binder(nested_ty), snapshot);
-                let skol_predicate =
-                    util::predicate_for_trait_def(
-                        self.tcx(),
-                        derived_cause.clone(),
-                        trait_def_id,
-                        obligation.recursion_depth + 1,
-                        skol_ty);
-                match skol_predicate {
-                    Ok(skol_predicate) => Ok(self.infcx().plug_leaks(skol_map, snapshot,
-                                                                     &skol_predicate)),
-                    Err(ErrorReported) => Err(ErrorReported)
-                }
+                    self.infcx().skolemize_late_bound_regions(nested_ty, snapshot);
+                let Normalized { value: normalized_ty, mut obligations } =
+                    project::normalize_with_depth(self,
+                                                  obligation.cause.clone(),
+                                                  obligation.recursion_depth + 1,
+                                                  &skol_ty);
+                let skol_obligation =
+                    try!(util::predicate_for_trait_def(self.tcx(),
+                                                       derived_cause.clone(),
+                                                       trait_def_id,
+                                                       obligation.recursion_depth + 1,
+                                                       normalized_ty));
+                obligations.push(skol_obligation);
+                Ok(self.infcx().plug_leaks(skol_map, snapshot, &obligations))
             })
-        }).collect::<Result<Vec<PredicateObligation<'tcx>>, _>>();
+        }).collect();
 
+        // Flatten those vectors (couldn't do it above due `collect`)
         match obligations {
-            Ok(mut obls) => {
-                obls.push_all(&normalized.obligations);
-                obls
-            },
-            Err(ErrorReported) => Vec::new()
+            Ok(obligations) => obligations.into_iter().flat_map(|o| o.into_iter()).collect(),
+            Err(ErrorReported) => Vec::new(),
         }
     }
 
@@ -1798,7 +1837,12 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             }
 
             DefaultImplCandidate(trait_def_id) => {
-                let data = try!(self.confirm_default_impl_candidate(obligation, trait_def_id));
+                let data = self.confirm_default_impl_candidate(obligation, trait_def_id);
+                Ok(VtableDefaultImpl(data))
+            }
+
+            DefaultImplObjectCandidate(trait_def_id) => {
+                let data = self.confirm_default_impl_object_candidate(obligation, trait_def_id);
                 Ok(VtableDefaultImpl(data))
             }
 
@@ -1900,7 +1944,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     fn vtable_builtin_data(&mut self,
                            obligation: &TraitObligation<'tcx>,
                            bound: ty::BuiltinBound,
-                           nested: Vec<Ty<'tcx>>)
+                           nested: ty::Binder<Vec<Ty<'tcx>>>)
                            -> VtableBuiltinData<PredicateObligation<'tcx>>
     {
         let trait_def = match self.tcx().lang_items.from_builtin_kind(bound) {
@@ -1927,17 +1971,17 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     /// 2. For each where-clause `C` declared on `Foo`, `[Self => X] C` holds.
     fn confirm_default_impl_candidate(&mut self,
                                       obligation: &TraitObligation<'tcx>,
-                                      impl_def_id: ast::DefId)
-                              -> Result<VtableDefaultImplData<PredicateObligation<'tcx>>,
-                                        SelectionError<'tcx>>
+                                      trait_def_id: ast::DefId)
+                                      -> VtableDefaultImplData<PredicateObligation<'tcx>>
     {
         debug!("confirm_default_impl_candidate({}, {})",
                obligation.repr(self.tcx()),
-               impl_def_id.repr(self.tcx()));
+               trait_def_id.repr(self.tcx()));
 
-        let self_ty = self.infcx.shallow_resolve(obligation.predicate.0.self_ty());
+        // binder is moved below
+        let self_ty = self.infcx.shallow_resolve(obligation.predicate.skip_binder().self_ty());
         match self.constituent_types_for_ty(self_ty) {
-            Some(types) => Ok(self.vtable_default_impl(obligation, impl_def_id, types)),
+            Some(types) => self.vtable_default_impl(obligation, trait_def_id, ty::Binder(types)),
             None => {
                 self.tcx().sess.bug(
                     &format!(
@@ -1947,33 +1991,72 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         }
     }
 
+    fn confirm_default_impl_object_candidate(&mut self,
+                                             obligation: &TraitObligation<'tcx>,
+                                             trait_def_id: ast::DefId)
+                                             -> VtableDefaultImplData<PredicateObligation<'tcx>>
+    {
+        debug!("confirm_default_impl_object_candidate({}, {})",
+               obligation.repr(self.tcx()),
+               trait_def_id.repr(self.tcx()));
+
+        assert!(ty::has_attr(self.tcx(), trait_def_id, "rustc_reflect_like"));
+
+        // OK to skip binder, it is reintroduced below
+        let self_ty = self.infcx.shallow_resolve(obligation.predicate.skip_binder().self_ty());
+        match self_ty.sty {
+            ty::ty_trait(ref data) => {
+                // OK to skip the binder, it is reintroduced below
+                let input_types = data.principal.skip_binder().substs.types.get_slice(TypeSpace);
+                let assoc_types = data.bounds.projection_bounds
+                                             .iter()
+                                             .map(|pb| pb.skip_binder().ty);
+                let all_types: Vec<_> = input_types.iter().cloned()
+                                                          .chain(assoc_types)
+                                                          .collect();
+
+                // reintroduce the two binding levels we skipped, then flatten into one
+                let all_types = ty::Binder(ty::Binder(all_types));
+                let all_types = ty::flatten_late_bound_regions(self.tcx(), &all_types);
+
+                self.vtable_default_impl(obligation, trait_def_id, all_types)
+            }
+            _ => {
+                self.tcx().sess.bug(
+                    &format!(
+                        "asked to confirm default object implementation for non-object type: {}",
+                        self_ty.repr(self.tcx())));
+            }
+        }
+    }
+
     /// See `confirm_default_impl_candidate`
     fn vtable_default_impl(&mut self,
                            obligation: &TraitObligation<'tcx>,
                            trait_def_id: ast::DefId,
-                           nested: Vec<Ty<'tcx>>)
+                           nested: ty::Binder<Vec<Ty<'tcx>>>)
                            -> VtableDefaultImplData<PredicateObligation<'tcx>>
     {
+        debug!("vtable_default_impl_data: nested={}", nested.repr(self.tcx()));
 
         let mut obligations = self.collect_predicates_for_types(obligation,
                                                                 trait_def_id,
                                                                 nested);
 
-        let _: Result<(),()> = self.infcx.try(|snapshot| {
-            let (_, skol_map) =
-                self.infcx().skolemize_late_bound_regions(&obligation.predicate, snapshot);
-
-            let substs = obligation.predicate.to_poly_trait_ref().substs();
-            let trait_obligations = self.impl_or_trait_obligations(obligation.cause.clone(),
-                                                                   obligation.recursion_depth + 1,
-                                                                   trait_def_id,
-                                                                   substs,
-                                                                   skol_map,
-                                                                   snapshot);
-            obligations.push_all(trait_obligations.as_slice());
-            Ok(())
+        let trait_obligations: Result<VecPerParamSpace<_>,()> = self.infcx.try(|snapshot| {
+            let poly_trait_ref = obligation.predicate.to_poly_trait_ref();
+            let (trait_ref, skol_map) =
+                self.infcx().skolemize_late_bound_regions(&poly_trait_ref, snapshot);
+            Ok(self.impl_or_trait_obligations(obligation.cause.clone(),
+                                              obligation.recursion_depth + 1,
+                                              trait_def_id,
+                                              &trait_ref.substs,
+                                              skol_map,
+                                              snapshot))
         });
 
+        obligations.extend(trait_obligations.unwrap().into_iter()); // no Errors in that code above
+
         debug!("vtable_default_impl_data: obligations={}", obligations.repr(self.tcx()));
 
         VtableDefaultImplData {
@@ -2047,7 +2130,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         debug!("confirm_object_candidate({})",
                obligation.repr(self.tcx()));
 
-        let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
+        // FIXME skipping binder here seems wrong -- we should
+        // probably flatten the binder from the obligation and the
+        // binder from the object. Have to try to make a broken test
+        // case that results. -nmatsakis
+        let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
         let poly_trait_ref = match self_ty.sty {
             ty::ty_trait(ref data) => {
                 data.principal_trait_ref_with_self_ty(self.tcx(), self_ty)
@@ -2085,15 +2172,16 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         debug!("confirm_fn_pointer_candidate({})",
                obligation.repr(self.tcx()));
 
-        let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
+        // ok to skip binder; it is reintroduced below
+        let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
         let sig = ty::ty_fn_sig(self_ty);
-        let ty::Binder((trait_ref, _)) =
+        let trait_ref =
             util::closure_trait_ref_and_return_type(self.tcx(),
                                                     obligation.predicate.def_id(),
                                                     self_ty,
                                                     sig,
-                                                    util::TupleArgumentsFlag::Yes);
-        let trait_ref = ty::Binder(trait_ref);
+                                                    util::TupleArgumentsFlag::Yes)
+            .map_bound(|(trait_ref, _)| trait_ref);
 
         try!(self.confirm_poly_trait_refs(obligation.cause.clone(),
                                           obligation.predicate.to_poly_trait_ref(),
@@ -2448,6 +2536,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                  snapshot: &infer::CombinedSnapshot)
                                  -> VecPerParamSpace<PredicateObligation<'tcx>>
     {
+        debug!("impl_or_trait_obligations(def_id={})", def_id.repr(self.tcx()));
+
         let predicates = ty::lookup_predicates(self.tcx(), def_id);
         let predicates = predicates.instantiate(self.tcx(), substs);
         let predicates = normalize_with_depth(self, cause.clone(), recursion_depth, &predicates);
@@ -2530,6 +2620,7 @@ impl<'tcx> Repr<'tcx> for SelectionCandidate<'tcx> {
             ParamCandidate(ref a) => format!("ParamCandidate({})", a.repr(tcx)),
             ImplCandidate(a) => format!("ImplCandidate({})", a.repr(tcx)),
             DefaultImplCandidate(t) => format!("DefaultImplCandidate({:?})", t),
+            DefaultImplObjectCandidate(t) => format!("DefaultImplObjectCandidate({:?})", t),
             ProjectionCandidate => format!("ProjectionCandidate"),
             FnPointerCandidate => format!("FnPointerCandidate"),
             ObjectCandidate => format!("ObjectCandidate"),
diff --git a/src/librustc/middle/traits/util.rs b/src/librustc/middle/traits/util.rs
index 965aaf12044..06b687bd92b 100644
--- a/src/librustc/middle/traits/util.rs
+++ b/src/librustc/middle/traits/util.rs
@@ -210,6 +210,47 @@ pub fn transitive_bounds<'cx, 'tcx>(tcx: &'cx ty::ctxt<'tcx>,
 }
 
 ///////////////////////////////////////////////////////////////////////////
+// Iterator over def-ids of supertraits
+
+pub struct SupertraitDefIds<'cx, 'tcx:'cx> {
+    tcx: &'cx ty::ctxt<'tcx>,
+    stack: Vec<ast::DefId>,
+    visited: FnvHashSet<ast::DefId>,
+}
+
+pub fn supertrait_def_ids<'cx, 'tcx>(tcx: &'cx ty::ctxt<'tcx>,
+                                     trait_def_id: ast::DefId)
+                                     -> SupertraitDefIds<'cx, 'tcx>
+{
+    SupertraitDefIds {
+        tcx: tcx,
+        stack: vec![trait_def_id],
+        visited: Some(trait_def_id).into_iter().collect(),
+    }
+}
+
+impl<'cx, 'tcx> Iterator for SupertraitDefIds<'cx, 'tcx> {
+    type Item = ast::DefId;
+
+    fn next(&mut self) -> Option<ast::DefId> {
+        let def_id = match self.stack.pop() {
+            Some(def_id) => def_id,
+            None => { return None; }
+        };
+
+        let predicates = ty::lookup_super_predicates(self.tcx, def_id);
+        let visited = &mut self.visited;
+        self.stack.extend(
+            predicates.predicates
+                      .iter()
+                      .filter_map(|p| p.to_opt_poly_trait_ref())
+                      .map(|t| t.def_id())
+                      .filter(|&super_def_id| visited.insert(super_def_id)));
+        Some(def_id)
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////
 // Other
 ///////////////////////////////////////////////////////////////////////////
 
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 23fba5ead22..01e13887462 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -1108,16 +1108,16 @@ pub type PolyFnSig<'tcx> = Binder<FnSig<'tcx>>;
 
 impl<'tcx> PolyFnSig<'tcx> {
     pub fn inputs(&self) -> ty::Binder<Vec<Ty<'tcx>>> {
-        ty::Binder(self.0.inputs.clone())
+        self.map_bound_ref(|fn_sig| fn_sig.inputs.clone())
     }
     pub fn input(&self, index: uint) -> ty::Binder<Ty<'tcx>> {
-        ty::Binder(self.0.inputs[index])
+        self.map_bound_ref(|fn_sig| fn_sig.inputs[index])
     }
     pub fn output(&self) -> ty::Binder<FnOutput<'tcx>> {
-        ty::Binder(self.0.output.clone())
+        self.map_bound_ref(|fn_sig| fn_sig.output.clone())
     }
     pub fn variadic(&self) -> bool {
-        self.0.variadic
+        self.skip_binder().variadic
     }
 }
 
@@ -1519,6 +1519,22 @@ impl<T> Binder<T> {
     pub fn skip_binder(&self) -> &T {
         &self.0
     }
+
+    pub fn as_ref(&self) -> Binder<&T> {
+        ty::Binder(&self.0)
+    }
+
+    pub fn map_bound_ref<F,U>(&self, f: F) -> Binder<U>
+        where F: FnOnce(&T) -> U
+    {
+        self.as_ref().map_bound(f)
+    }
+
+    pub fn map_bound<F,U>(self, f: F) -> Binder<U>
+        where F: FnOnce(T) -> U
+    {
+        ty::Binder(f(self.0))
+    }
 }
 
 #[derive(Clone, Copy, PartialEq)]
@@ -2062,8 +2078,7 @@ impl<'tcx> ToPolyTraitRef<'tcx> for Rc<TraitRef<'tcx>> {
 
 impl<'tcx> ToPolyTraitRef<'tcx> for PolyTraitPredicate<'tcx> {
     fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx> {
-        // We are just preserving the binder levels here
-        ty::Binder(self.0.trait_ref.clone())
+        self.map_bound_ref(|trait_pred| trait_pred.trait_ref.clone())
     }
 }
 
@@ -6753,6 +6768,30 @@ pub fn binds_late_bound_regions<'tcx, T>(
     count_late_bound_regions(tcx, value) > 0
 }
 
+/// Flattens two binding levels into one. So `for<'a> for<'b> Foo`
+/// becomes `for<'a,'b> Foo`.
+pub fn flatten_late_bound_regions<'tcx, T>(
+    tcx: &ty::ctxt<'tcx>,
+    bound2_value: &Binder<Binder<T>>)
+    -> Binder<T>
+    where T: TypeFoldable<'tcx> + Repr<'tcx>
+{
+    let bound0_value = bound2_value.skip_binder().skip_binder();
+    let value = ty_fold::fold_regions(tcx, bound0_value, |region, current_depth| {
+        match region {
+            ty::ReLateBound(debruijn, br) if debruijn.depth >= current_depth => {
+                // should be true if no escaping regions from bound2_value
+                assert!(debruijn.depth - current_depth <= 1);
+                ty::ReLateBound(DebruijnIndex::new(current_depth), br)
+            }
+            _ => {
+                region
+            }
+        }
+    });
+    Binder(value)
+}
+
 pub fn no_late_bound_regions<'tcx, T>(
     tcx: &ty::ctxt<'tcx>,
     value: &Binder<T>)
@@ -7089,6 +7128,12 @@ impl<'tcx> RegionEscape for Predicate<'tcx> {
     }
 }
 
+impl<'tcx,P:RegionEscape> RegionEscape for traits::Obligation<'tcx,P> {
+    fn has_regions_escaping_depth(&self, depth: u32) -> bool {
+        self.predicate.has_regions_escaping_depth(depth)
+    }
+}
+
 impl<'tcx> RegionEscape for TraitRef<'tcx> {
     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
         self.substs.types.iter().any(|t| t.has_regions_escaping_depth(depth)) ||
diff --git a/src/librustc_typeck/check/vtable.rs b/src/librustc_typeck/check/vtable.rs
index 2858dc9b569..67461ff561b 100644
--- a/src/librustc_typeck/check/vtable.rs
+++ b/src/librustc_typeck/check/vtable.rs
@@ -28,18 +28,17 @@ pub fn check_object_safety<'tcx>(tcx: &ty::ctxt<'tcx>,
                                  object_trait: &ty::TyTrait<'tcx>,
                                  span: Span)
 {
-    let object_trait_ref =
-        object_trait.principal_trait_ref_with_self_ty(tcx, tcx.types.err);
+    let trait_def_id = object_trait.principal_def_id();
 
-    if traits::is_object_safe(tcx, object_trait_ref.clone()) {
+    if traits::is_object_safe(tcx, trait_def_id) {
         return;
     }
 
     span_err!(tcx.sess, span, E0038,
               "cannot convert to a trait object because trait `{}` is not object-safe",
-              ty::item_path_str(tcx, object_trait_ref.def_id()));
+              ty::item_path_str(tcx, trait_def_id));
 
-    let violations = traits::object_safety_violations(tcx, object_trait_ref.clone());
+    let violations = traits::object_safety_violations(tcx, trait_def_id);
     for violation in violations {
         match violation {
             ObjectSafetyViolation::SizedSelf => {
diff --git a/src/librustc_typeck/variance.rs b/src/librustc_typeck/variance.rs
index ac1ff29e7f5..3a716b28e73 100644
--- a/src/librustc_typeck/variance.rs
+++ b/src/librustc_typeck/variance.rs
@@ -1059,14 +1059,29 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
                 }
 
                 ty::Predicate::Equate(ty::Binder(ref data)) => {
-                    self.add_constraints_from_ty(generics, data.0, variance);
-                    self.add_constraints_from_ty(generics, data.1, variance);
+                    // A == B is only true if A and B are the same
+                    // types, not subtypes of one another, so this is
+                    // an invariant position:
+                    self.add_constraints_from_ty(generics, data.0, self.invariant);
+                    self.add_constraints_from_ty(generics, data.1, self.invariant);
                 }
 
                 ty::Predicate::TypeOutlives(ty::Binder(ref data)) => {
-                    self.add_constraints_from_ty(generics, data.0, variance);
+                    // Why contravariant on both? Let's consider:
+                    //
+                    // Under what conditions is `(T:'t) <: (U:'u)`,
+                    // meaning that `(T:'t) => (U:'u)`. The answer is
+                    // if `U <: T` or `'u <= 't`. Let's see some examples:
+                    //
+                    //   (T: 'big) => (T: 'small)
+                    //   where 'small <= 'big
+                    //
+                    //   (&'small Foo: 't) => (&'big Foo: 't)
+                    //   where 'small <= 'big
+                    //   note that &'big Foo <: &'small Foo
 
                     let variance_r = self.xform(variance, self.contravariant);
+                    self.add_constraints_from_ty(generics, data.0, variance_r);
                     self.add_constraints_from_region(generics, data.1, variance_r);
                 }
 
@@ -1084,6 +1099,9 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
                                                         &*data.projection_ty.trait_ref,
                                                         variance);
 
+                    // as the equality predicate above, a binder is a
+                    // type equality relation, not a subtyping
+                    // relation
                     self.add_constraints_from_ty(generics, data.ty, self.invariant);
                 }
             }
diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs
index 60f81dac1e9..46115ae468f 100644
--- a/src/libsyntax/feature_gate.rs
+++ b/src/libsyntax/feature_gate.rs
@@ -74,6 +74,7 @@ const KNOWN_FEATURES: &'static [(&'static str, &'static str, Status)] = &[
 
     ("rustc_diagnostic_macros", "1.0.0", Active),
     ("unboxed_closures", "1.0.0", Active),
+    ("reflect", "1.0.0", Active),
     ("import_shadowing", "1.0.0", Removed),
     ("advanced_slice_patterns", "1.0.0", Active),
     ("tuple_indexing", "1.0.0", Accepted),
@@ -281,7 +282,11 @@ pub const KNOWN_ATTRIBUTES: &'static [(&'static str, AttributeType)] = &[
     // FIXME: #19470 this shouldn't be needed forever
     ("old_orphan_check", Whitelisted),
     ("old_impl_check", Whitelisted),
-    ("rustc_paren_sugar", Whitelisted), // FIXME: #18101 temporary unboxed closure hack
+
+    ("rustc_paren_sugar", Gated("unboxed_closures",
+                                "unboxed_closures are still evolving")),
+    ("rustc_reflect_like", Gated("reflect",
+                                 "defining reflective traits is still evolving")),
 
     // Crate level attributes
     ("crate_name", CrateLevel),
diff --git a/src/test/auxiliary/typeid-intrinsic.rs b/src/test/auxiliary/typeid-intrinsic.rs
index 82d07a9df4e..bd47054f093 100644
--- a/src/test/auxiliary/typeid-intrinsic.rs
+++ b/src/test/auxiliary/typeid-intrinsic.rs
@@ -10,7 +10,7 @@
 
 #![feature(core)]
 
-use std::any::TypeId;
+use std::any::{Any, TypeId};
 
 pub struct A;
 pub struct B(Option<A>);
@@ -31,4 +31,4 @@ pub unsafe fn id_F() -> TypeId { TypeId::of::<F>() }
 pub unsafe fn id_G() -> TypeId { TypeId::of::<G>() }
 pub unsafe fn id_H() -> TypeId { TypeId::of::<H>() }
 
-pub unsafe fn foo<T: 'static>() -> TypeId { TypeId::of::<T>() }
+pub unsafe fn foo<T: Any>() -> TypeId { TypeId::of::<T>() }
diff --git a/src/test/auxiliary/typeid-intrinsic2.rs b/src/test/auxiliary/typeid-intrinsic2.rs
index 82d07a9df4e..5e81bf50ae4 100644
--- a/src/test/auxiliary/typeid-intrinsic2.rs
+++ b/src/test/auxiliary/typeid-intrinsic2.rs
@@ -10,7 +10,7 @@
 
 #![feature(core)]
 
-use std::any::TypeId;
+use std::any::{Any, TypeId};
 
 pub struct A;
 pub struct B(Option<A>);
@@ -31,4 +31,4 @@ pub unsafe fn id_F() -> TypeId { TypeId::of::<F>() }
 pub unsafe fn id_G() -> TypeId { TypeId::of::<G>() }
 pub unsafe fn id_H() -> TypeId { TypeId::of::<H>() }
 
-pub unsafe fn foo<T: 'static>() -> TypeId { TypeId::of::<T>() }
+pub unsafe fn foo<T:Any>() -> TypeId { TypeId::of::<T>() }
diff --git a/src/test/compile-fail/reflect-assoc.rs b/src/test/compile-fail/reflect-assoc.rs
new file mode 100644
index 00000000000..9cf0d252c2d
--- /dev/null
+++ b/src/test/compile-fail/reflect-assoc.rs
@@ -0,0 +1,35 @@
+// 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 types that appear in assoc bindings in an object
+// type are subject to the reflect check.
+
+use std::marker::Reflect;
+use std::io::Write;
+
+trait Get {
+    type Output;
+    fn get(self) -> Self::Output;
+}
+
+struct Struct<T>(T);
+
+fn is_reflect<T:Reflect>() { }
+
+fn a<T>() {
+    is_reflect::<Box<Get<Output=T>>>(); //~ ERROR not implemented
+}
+
+fn ok_a<T: Reflect>() {
+    is_reflect::<Box<Get<Output=T>>>(); // OK
+}
+
+fn main() {
+}
diff --git a/src/test/compile-fail/reflect-object-param.rs b/src/test/compile-fail/reflect-object-param.rs
new file mode 100644
index 00000000000..9f074667feb
--- /dev/null
+++ b/src/test/compile-fail/reflect-object-param.rs
@@ -0,0 +1,47 @@
+// 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 types that appear in input types in an object type are
+// subject to the reflect check.
+
+use std::marker::Reflect;
+use std::io::Write;
+
+trait Get<T> {
+    fn get(self) -> T;
+}
+
+struct Struct<T>(T);
+
+fn is_reflect<T:Reflect>() { }
+
+fn a<T>() {
+    is_reflect::<T>(); //~ ERROR not implemented
+}
+
+fn ok_a<T: Reflect>() {
+    is_reflect::<T>(); // OK
+}
+
+fn b<T>() {
+    is_reflect::<Box<Get<T>>>(); //~ ERROR not implemented
+}
+
+fn ok_b<T: Reflect>() {
+    is_reflect::<Box<Get<T>>>(); // OK
+}
+
+fn c<T>() {
+    is_reflect::<Box<Get<Struct<T>>>>(); //~ ERROR not implemented
+}
+
+fn main() {
+    is_reflect::<Box<Get<Struct<()>>>>(); // OK
+}
diff --git a/src/test/compile-fail/reflect.rs b/src/test/compile-fail/reflect.rs
new file mode 100644
index 00000000000..701aa5b40bc
--- /dev/null
+++ b/src/test/compile-fail/reflect.rs
@@ -0,0 +1,39 @@
+// 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 there is no way to get a generic type `T` to be
+// considered as `Reflect` (or accessible via something that is
+// considered `Reflect`) without a reflect bound, but that any
+// concrete type works fine. Note that object types are tested
+// separately.
+
+use std::marker::Reflect;
+use std::io::Write;
+
+struct Struct<T>(T);
+
+fn is_reflect<T:Reflect>() { }
+
+fn c<T>() {
+    is_reflect::<Struct<T>>(); //~ ERROR not implemented
+}
+
+fn ok_c<T: Reflect>() {
+    is_reflect::<Struct<T>>(); // OK
+}
+
+fn d<T>() {
+    is_reflect::<(i32, T)>(); //~ ERROR not implemented
+}
+
+fn main() {
+    is_reflect::<&i32>(); // OK
+    is_reflect::<Box<Write>>(); // OK
+}
diff --git a/src/test/compile-fail/variance-region-bounds.rs b/src/test/compile-fail/variance-region-bounds.rs
new file mode 100644
index 00000000000..96ae201f6ae
--- /dev/null
+++ b/src/test/compile-fail/variance-region-bounds.rs
@@ -0,0 +1,25 @@
+// 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.
+
+// Check that `T:'a` is contravariant in T.
+
+#![feature(rustc_attrs)]
+
+#[rustc_variance]
+trait Foo: 'static { //~ ERROR types=[[];[-];[]]
+}
+
+#[rustc_variance]
+trait Bar<T> { //~ ERROR types=[[+];[-];[]]
+    fn do_it(&self)
+        where T: 'static;
+}
+
+fn main() { }
diff --git a/src/test/run-pass/object-one-type-two-traits.rs b/src/test/run-pass/object-one-type-two-traits.rs
index baf8c6e4c97..f4e056b3f21 100644
--- a/src/test/run-pass/object-one-type-two-traits.rs
+++ b/src/test/run-pass/object-one-type-two-traits.rs
@@ -30,7 +30,7 @@ impl Wrap for int {
     }
 }
 
-fn is<T:'static>(x: &Any) -> bool {
+fn is<T:Any>(x: &Any) -> bool {
     x.is::<T>()
 }
 
diff --git a/src/test/run-pass/type-id-higher-rank.rs b/src/test/run-pass/type-id-higher-rank.rs
index 5670c45b68a..a40989d4e37 100644
--- a/src/test/run-pass/type-id-higher-rank.rs
+++ b/src/test/run-pass/type-id-higher-rank.rs
@@ -15,7 +15,7 @@
 
 #![feature(unboxed_closures, core)]
 
-use std::any::TypeId;
+use std::any::{Any, TypeId};
 
 fn main() {
     // Bare fns
@@ -63,7 +63,7 @@ fn main() {
         assert!(a != b);
     }
 
-    fn id<T:'static>(_: T) -> TypeId {
+    fn id<T:Any>(_: T) -> TypeId {
         TypeId::of::<T>()
     }
 }