rustc: move trait objects from TraitRef to ExistentialTraitRef.

39 files changed, 682 insertions, 792 deletions

diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index 79eea7314cd..951570679e0 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -1248,9 +1248,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                                      generics: &ty::Generics<'tcx>)
                                      -> &'tcx subst::Substs<'tcx>
     {
-        let type_defs = generics.types.as_full_slice();
-        let region_defs = generics.regions.as_full_slice();
-        let substs = Substs::from_param_defs(region_defs, type_defs, |def| {
+        let substs = Substs::from_generics(generics, |def, _| {
             self.region_var_for_def(span, def)
         }, |def, substs| {
             self.type_var_for_def(span, def, substs)
@@ -1271,9 +1269,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         assert!(generics.types.len(subst::SelfSpace) == 1);
         assert!(generics.types.len(subst::FnSpace) == 0);
 
-        let type_defs = generics.types.as_full_slice();
-        let region_defs = generics.regions.as_full_slice();
-        let substs = Substs::from_param_defs(region_defs, type_defs, |def| {
+        let substs = Substs::from_generics(generics, |def, _| {
             self.region_var_for_def(span, def)
         }, |def, substs| {
             if def.space == subst::SelfSpace {
diff --git a/src/librustc/traits/coherence.rs b/src/librustc/traits/coherence.rs
index b38f5f96de4..f1701d60fd0 100644
--- a/src/librustc/traits/coherence.rs
+++ b/src/librustc/traits/coherence.rs
@@ -231,7 +231,7 @@ fn fundamental_ty(tcx: TyCtxt, ty: Ty) -> bool {
         ty::TyEnum(def, _) | ty::TyStruct(def, _) =>
             def.is_fundamental(),
         ty::TyTrait(ref data) =>
-            tcx.has_attr(data.principal_def_id(), "fundamental"),
+            tcx.has_attr(data.principal.def_id(), "fundamental"),
         _ =>
             false
     }
@@ -275,7 +275,7 @@ fn ty_is_local_constructor(tcx: TyCtxt, ty: Ty, infer_is_local: InferIsLocal)->
         }
 
         ty::TyTrait(ref tt) => {
-            tt.principal_def_id().is_local()
+            tt.principal.def_id().is_local()
         }
 
         ty::TyError => {
diff --git a/src/librustc/traits/project.rs b/src/librustc/traits/project.rs
index d580deed075..ea4fc1c25ab 100644
--- a/src/librustc/traits/project.rs
+++ b/src/librustc/traits/project.rs
@@ -1133,10 +1133,9 @@ fn confirm_object_candidate<'cx, 'gcx, 'tcx>(
                 object_ty)
         }
     };
-    let projection_bounds = data.projection_bounds_with_self_ty(selcx.tcx(), object_ty);
-    let env_predicates = projection_bounds.iter()
-                                          .map(|p| p.to_predicate())
-                                          .collect();
+    let env_predicates = data.projection_bounds.iter().map(|p| {
+        p.with_self_ty(selcx.tcx(), object_ty).to_predicate()
+    }).collect();
     let env_predicate = {
         let env_predicates = elaborate_predicates(selcx.tcx(), env_predicates);
 
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index 9c7dd7ccd70..73108e7d37f 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -1528,7 +1528,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 ty::TyTrait(ref data) => {
                     match this.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) {
+                            if data.builtin_bounds.contains(&bound) {
                                 debug!("assemble_candidates_from_object_ty: matched builtin bound, \
                                         pushing candidate");
                                 candidates.vec.push(BuiltinObjectCandidate);
@@ -1538,7 +1538,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                         _ => {}
                     }
 
-                    data.principal_trait_ref_with_self_ty(this.tcx(), self_ty)
+                    data.principal.with_self_ty(this.tcx(), self_ty)
                 }
                 ty::TyInfer(ty::TyVar(_)) => {
                     debug!("assemble_candidates_from_object_ty: ambiguous");
@@ -1622,7 +1622,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 // We always upcast when we can because of reason
                 // #2 (region bounds).
                 data_a.principal.def_id() == data_a.principal.def_id() &&
-                data_a.bounds.builtin_bounds.is_superset(&data_b.bounds.builtin_bounds)
+                data_a.builtin_bounds.is_superset(&data_b.builtin_bounds)
             }
 
             // T -> Trait.
@@ -2179,10 +2179,9 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         match self_ty.sty {
             ty::TyTrait(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 input_types = data.principal.skip_binder().input_types();
+                let assoc_types = data.projection_bounds.iter()
+                                      .map(|pb| pb.skip_binder().ty);
                 let all_types: Vec<_> = input_types.iter().cloned()
                                                           .chain(assoc_types)
                                                           .collect();
@@ -2315,7 +2314,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
         let poly_trait_ref = match self_ty.sty {
             ty::TyTrait(ref data) => {
-                data.principal_trait_ref_with_self_ty(self.tcx(), self_ty)
+                data.principal.with_self_ty(self.tcx(), self_ty)
             }
             _ => {
                 span_bug!(obligation.cause.span,
@@ -2487,13 +2486,12 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
             (&ty::TyTrait(ref data_a), &ty::TyTrait(ref data_b)) => {
                 // See assemble_candidates_for_unsizing for more info.
-                let bounds = ty::ExistentialBounds {
-                    region_bound: data_b.bounds.region_bound,
-                    builtin_bounds: data_b.bounds.builtin_bounds,
-                    projection_bounds: data_a.bounds.projection_bounds.clone(),
-                };
-
-                let new_trait = tcx.mk_trait(data_a.principal.clone(), bounds);
+                let new_trait = tcx.mk_trait(ty::TraitObject {
+                    principal: data_a.principal,
+                    region_bound: data_b.region_bound,
+                    builtin_bounds: data_b.builtin_bounds,
+                    projection_bounds: data_a.projection_bounds.clone(),
+                });
                 let origin = TypeOrigin::Misc(obligation.cause.span);
                 let InferOk { obligations, .. } =
                     self.infcx.sub_types(false, origin, new_trait, target)
@@ -2504,8 +2502,8 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 let cause = ObligationCause::new(obligation.cause.span,
                                                  obligation.cause.body_id,
                                                  ObjectCastObligation(target));
-                let outlives = ty::OutlivesPredicate(data_a.bounds.region_bound,
-                                                     data_b.bounds.region_bound);
+                let outlives = ty::OutlivesPredicate(data_a.region_bound,
+                                                     data_b.region_bound);
                 nested.push(Obligation::with_depth(cause,
                                                    obligation.recursion_depth + 1,
                                                    ty::Binder(outlives).to_predicate()));
@@ -2513,12 +2511,12 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
 
             // T -> Trait.
             (_, &ty::TyTrait(ref data)) => {
-                let mut object_dids = Some(data.principal_def_id()).into_iter();
+                let mut object_dids = Some(data.principal.def_id()).into_iter();
                 // FIXME(#33243)
-//                    data.bounds.builtin_bounds.iter().flat_map(|bound| {
+//                    data.builtin_bounds.iter().flat_map(|bound| {
 //                        tcx.lang_items.from_builtin_kind(bound).ok()
 //                    })
-//                    .chain(Some(data.principal_def_id()));
+//                    .chain(Some(data.principal.def_id()));
                 if let Some(did) = object_dids.find(|did| {
                     !tcx.is_object_safe(*did)
                 }) {
@@ -2535,10 +2533,10 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 };
 
                 // Create the obligation for casting from T to Trait.
-                push(data.principal_trait_ref_with_self_ty(tcx, source).to_predicate());
+                push(data.principal.with_self_ty(tcx, source).to_predicate());
 
                 // We can only make objects from sized types.
-                let mut builtin_bounds = data.bounds.builtin_bounds;
+                let mut builtin_bounds = data.builtin_bounds;
                 builtin_bounds.insert(ty::BoundSized);
 
                 // Create additional obligations for all the various builtin
@@ -2554,14 +2552,13 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 }
 
                 // Create obligations for the projection predicates.
-                for bound in data.projection_bounds_with_self_ty(tcx, source) {
-                    push(bound.to_predicate());
+                for bound in &data.projection_bounds {
+                    push(bound.with_self_ty(tcx, source).to_predicate());
                 }
 
                 // If the type is `Foo+'a`, ensures that the type
                 // being cast to `Foo+'a` outlives `'a`:
-                let outlives = ty::OutlivesPredicate(source,
-                                                     data.bounds.region_bound);
+                let outlives = ty::OutlivesPredicate(source, data.region_bound);
                 push(ty::Binder(outlives).to_predicate());
             }
 
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index 4056fb01aa2..dfb5482ad87 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -27,9 +27,9 @@ use ty::subst::{self, Substs};
 use traits;
 use ty::{self, TraitRef, Ty, TypeAndMut};
 use ty::{TyS, TypeVariants};
-use ty::{AdtDef, ClosureSubsts, ExistentialBounds, Region};
+use ty::{AdtDef, ClosureSubsts, Region};
 use hir::FreevarMap;
-use ty::{BareFnTy, InferTy, ParamTy, ProjectionTy, TraitTy};
+use ty::{BareFnTy, InferTy, ParamTy, ProjectionTy, TraitObject};
 use ty::{TyVar, TyVid, IntVar, IntVid, FloatVar, FloatVid};
 use ty::TypeVariants::*;
 use ty::layout::{Layout, TargetDataLayout};
@@ -1150,12 +1150,6 @@ impl_interners!('tcx,
     region: mk_region(Region, keep_local) -> Region
 );
 
-fn bound_list_is_sorted(bounds: &[ty::PolyProjectionPredicate]) -> bool {
-    bounds.is_empty() ||
-        bounds[1..].iter().enumerate().all(
-            |(index, bound)| bounds[index].sort_key() <= bound.sort_key())
-}
-
 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
     /// Create an unsafe fn ty based on a safe fn ty.
     pub fn safe_to_unsafe_fn_ty(self, bare_fn: &BareFnTy<'tcx>) -> Ty<'tcx> {
@@ -1288,18 +1282,9 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         self.mk_ty(TyFnPtr(fty))
     }
 
-    pub fn mk_trait(self,
-                    principal: ty::PolyTraitRef<'tcx>,
-                    bounds: ExistentialBounds<'tcx>)
-                    -> Ty<'tcx>
-    {
-        assert!(bound_list_is_sorted(&bounds.projection_bounds));
-
-        let inner = box TraitTy {
-            principal: principal,
-            bounds: bounds
-        };
-        self.mk_ty(TyTrait(inner))
+    pub fn mk_trait(self, mut obj: TraitObject<'tcx>) -> Ty<'tcx> {
+        obj.projection_bounds.sort_by(|a, b| a.sort_key().cmp(&b.sort_key()));
+        self.mk_ty(TyTrait(box obj))
     }
 
     pub fn mk_projection(self,
diff --git a/src/librustc/ty/error.rs b/src/librustc/ty/error.rs
index 42d5788568f..933746ebc2a 100644
--- a/src/librustc/ty/error.rs
+++ b/src/librustc/ty/error.rs
@@ -243,7 +243,7 @@ impl<'a, 'gcx, 'lcx, 'tcx> ty::TyS<'tcx> {
             ty::TyFnDef(..) => format!("fn item"),
             ty::TyFnPtr(_) => "fn pointer".to_string(),
             ty::TyTrait(ref inner) => {
-                format!("trait {}", tcx.item_path_str(inner.principal_def_id()))
+                format!("trait {}", tcx.item_path_str(inner.principal.def_id()))
             }
             ty::TyStruct(def, _) => {
                 format!("struct `{}`", tcx.item_path_str(def.did))
diff --git a/src/librustc/ty/fast_reject.rs b/src/librustc/ty/fast_reject.rs
index 9bf2daeb5f4..f7472d611be 100644
--- a/src/librustc/ty/fast_reject.rs
+++ b/src/librustc/ty/fast_reject.rs
@@ -61,7 +61,7 @@ pub fn simplify_type<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
         ty::TyArray(..) | ty::TySlice(_) => Some(VecSimplifiedType),
         ty::TyRawPtr(_) => Some(PtrSimplifiedType),
         ty::TyTrait(ref trait_info) => {
-            Some(TraitSimplifiedType(trait_info.principal_def_id()))
+            Some(TraitSimplifiedType(trait_info.principal.def_id()))
         }
         ty::TyStruct(def, _) => {
             Some(StructSimplifiedType(def.did))
diff --git a/src/librustc/ty/flags.rs b/src/librustc/ty/flags.rs
index 3a5f3d421ea..6cc759c420d 100644
--- a/src/librustc/ty/flags.rs
+++ b/src/librustc/ty/flags.rs
@@ -116,17 +116,16 @@ impl FlagComputation {
                 self.add_substs(substs);
             }
 
-            &ty::TyTrait(box ty::TraitTy { ref principal, ref bounds }) => {
+            &ty::TyTrait(ref obj) => {
                 let mut computation = FlagComputation::new();
-                computation.add_substs(principal.0.substs);
-                for projection_bound in &bounds.projection_bounds {
+                computation.add_substs(obj.principal.skip_binder().substs);
+                for projection_bound in &obj.projection_bounds {
                     let mut proj_computation = FlagComputation::new();
-                    proj_computation.add_projection_predicate(&projection_bound.0);
+                    proj_computation.add_existential_projection(&projection_bound.0);
                     self.add_bound_computation(&proj_computation);
                 }
                 self.add_bound_computation(&computation);
-
-                self.add_bounds(bounds);
+                self.add_region(obj.region_bound);
             }
 
             &ty::TyBox(tt) | &ty::TyArray(tt, _) | &ty::TySlice(tt) => {
@@ -199,9 +198,9 @@ impl FlagComputation {
         }
     }
 
-    fn add_projection_predicate(&mut self, projection_predicate: &ty::ProjectionPredicate) {
-        self.add_projection_ty(&projection_predicate.projection_ty);
-        self.add_ty(projection_predicate.ty);
+    fn add_existential_projection(&mut self, projection: &ty::ExistentialProjection) {
+        self.add_substs(projection.trait_ref.substs);
+        self.add_ty(projection.ty);
     }
 
     fn add_projection_ty(&mut self, projection_ty: &ty::ProjectionTy) {
@@ -214,8 +213,4 @@ impl FlagComputation {
             self.add_region(r);
         }
     }
-
-    fn add_bounds(&mut self, bounds: &ty::ExistentialBounds) {
-        self.add_region(bounds.region_bound);
-    }
 }
diff --git a/src/librustc/ty/fold.rs b/src/librustc/ty/fold.rs
index 3eeff6ee579..597261cca72 100644
--- a/src/librustc/ty/fold.rs
+++ b/src/librustc/ty/fold.rs
@@ -140,10 +140,6 @@ pub trait TypeFolder<'gcx: 'tcx, 'tcx> : Sized {
         t.super_fold_with(self)
     }
 
-    fn fold_trait_ref(&mut self, t: &ty::TraitRef<'tcx>) -> ty::TraitRef<'tcx> {
-        t.super_fold_with(self)
-    }
-
     fn fold_impl_header(&mut self, imp: &ty::ImplHeader<'tcx>) -> ty::ImplHeader<'tcx> {
         imp.super_fold_with(self)
     }
@@ -177,11 +173,6 @@ pub trait TypeFolder<'gcx: 'tcx, 'tcx> : Sized {
         r.super_fold_with(self)
     }
 
-    fn fold_existential_bounds(&mut self, s: &ty::ExistentialBounds<'tcx>)
-                               -> ty::ExistentialBounds<'tcx> {
-        s.super_fold_with(self)
-    }
-
     fn fold_autoref(&mut self, ar: &adjustment::AutoRef<'tcx>)
                     -> adjustment::AutoRef<'tcx> {
         ar.super_fold_with(self)
diff --git a/src/librustc/ty/item_path.rs b/src/librustc/ty/item_path.rs
index 8ddd8bef36a..1dcc623d365 100644
--- a/src/librustc/ty/item_path.rs
+++ b/src/librustc/ty/item_path.rs
@@ -322,7 +322,7 @@ pub fn characteristic_def_id_of_type(ty: Ty) -> Option<DefId> {
         ty::TyStruct(adt_def, _) |
         ty::TyEnum(adt_def, _) => Some(adt_def.did),
 
-        ty::TyTrait(ref data) => Some(data.principal_def_id()),
+        ty::TyTrait(ref data) => Some(data.principal.def_id()),
 
         ty::TyArray(subty, _) |
         ty::TySlice(subty) |
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 44532fcb4e6..6ac57a877a7 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -54,11 +54,13 @@ use hir::{ItemImpl, ItemTrait, PatKind};
 use hir::intravisit::Visitor;
 
 pub use self::sty::{Binder, DebruijnIndex};
-pub use self::sty::{BuiltinBound, BuiltinBounds, ExistentialBounds};
+pub use self::sty::{BuiltinBound, BuiltinBounds};
 pub use self::sty::{BareFnTy, FnSig, PolyFnSig};
-pub use self::sty::{ClosureTy, InferTy, ParamTy, ProjectionTy, TraitTy};
+pub use self::sty::{ClosureTy, InferTy, ParamTy, ProjectionTy, TraitObject};
 pub use self::sty::{ClosureSubsts, TypeAndMut};
 pub use self::sty::{TraitRef, TypeVariants, PolyTraitRef};
+pub use self::sty::{ExistentialTraitRef, PolyExistentialTraitRef};
+pub use self::sty::{ExistentialProjection, PolyExistentialProjection};
 pub use self::sty::{BoundRegion, EarlyBoundRegion, FreeRegion, Region};
 pub use self::sty::Issue32330;
 pub use self::sty::{TyVid, IntVid, FloatVid, RegionVid, SkolemizedRegionVid};
diff --git a/src/librustc/ty/relate.rs b/src/librustc/ty/relate.rs
index 05a9b811157..aa48474e50c 100644
--- a/src/librustc/ty/relate.rs
+++ b/src/librustc/ty/relate.rs
@@ -326,24 +326,33 @@ impl<'tcx> Relate<'tcx> for ty::ProjectionTy<'tcx> {
     }
 }
 
-impl<'tcx> Relate<'tcx> for ty::ProjectionPredicate<'tcx> {
+impl<'tcx> Relate<'tcx> for ty::ExistentialProjection<'tcx> {
     fn relate<'a, 'gcx, R>(relation: &mut R,
-                           a: &ty::ProjectionPredicate<'tcx>,
-                           b: &ty::ProjectionPredicate<'tcx>)
-                           -> RelateResult<'tcx, ty::ProjectionPredicate<'tcx>>
+                           a: &ty::ExistentialProjection<'tcx>,
+                           b: &ty::ExistentialProjection<'tcx>)
+                           -> RelateResult<'tcx, ty::ExistentialProjection<'tcx>>
         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
     {
-        let projection_ty = relation.relate(&a.projection_ty, &b.projection_ty)?;
-        let ty = relation.relate(&a.ty, &b.ty)?;
-        Ok(ty::ProjectionPredicate { projection_ty: projection_ty, ty: ty })
+        if a.item_name != b.item_name {
+            Err(TypeError::ProjectionNameMismatched(
+                expected_found(relation, &a.item_name, &b.item_name)))
+        } else {
+            let trait_ref = relation.relate(&a.trait_ref, &b.trait_ref)?;
+            let ty = relation.relate(&a.ty, &b.ty)?;
+            Ok(ty::ExistentialProjection {
+                trait_ref: trait_ref,
+                item_name: a.item_name,
+                ty: ty
+            })
+        }
     }
 }
 
-impl<'tcx> Relate<'tcx> for Vec<ty::PolyProjectionPredicate<'tcx>> {
+impl<'tcx> Relate<'tcx> for Vec<ty::PolyExistentialProjection<'tcx>> {
     fn relate<'a, 'gcx, R>(relation: &mut R,
-                           a: &Vec<ty::PolyProjectionPredicate<'tcx>>,
-                           b: &Vec<ty::PolyProjectionPredicate<'tcx>>)
-                           -> RelateResult<'tcx, Vec<ty::PolyProjectionPredicate<'tcx>>>
+                           a: &Vec<ty::PolyExistentialProjection<'tcx>>,
+                           b: &Vec<ty::PolyExistentialProjection<'tcx>>)
+                           -> RelateResult<'tcx, Vec<ty::PolyExistentialProjection<'tcx>>>
         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
     {
         // To be compatible, `a` and `b` must be for precisely the
@@ -361,27 +370,6 @@ impl<'tcx> Relate<'tcx> for Vec<ty::PolyProjectionPredicate<'tcx>> {
     }
 }
 
-impl<'tcx> Relate<'tcx> for ty::ExistentialBounds<'tcx> {
-    fn relate<'a, 'gcx, R>(relation: &mut R,
-                           a: &ty::ExistentialBounds<'tcx>,
-                           b: &ty::ExistentialBounds<'tcx>)
-                           -> RelateResult<'tcx, ty::ExistentialBounds<'tcx>>
-        where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
-    {
-        let r =
-            relation.with_cause(
-                Cause::ExistentialRegionBound,
-                |relation| relation.relate_with_variance(ty::Contravariant,
-                                                         &a.region_bound,
-                                                         &b.region_bound))?;
-        let nb = relation.relate(&a.builtin_bounds, &b.builtin_bounds)?;
-        let pb = relation.relate(&a.projection_bounds, &b.projection_bounds)?;
-        Ok(ty::ExistentialBounds { region_bound: r,
-                                   builtin_bounds: nb,
-                                   projection_bounds: pb })
-    }
-}
-
 impl<'tcx> Relate<'tcx> for ty::BuiltinBounds {
     fn relate<'a, 'gcx, R>(relation: &mut R,
                            a: &ty::BuiltinBounds,
@@ -416,6 +404,23 @@ impl<'tcx> Relate<'tcx> for ty::TraitRef<'tcx> {
     }
 }
 
+impl<'tcx> Relate<'tcx> for ty::ExistentialTraitRef<'tcx> {
+    fn relate<'a, 'gcx, R>(relation: &mut R,
+                           a: &ty::ExistentialTraitRef<'tcx>,
+                           b: &ty::ExistentialTraitRef<'tcx>)
+                           -> RelateResult<'tcx, ty::ExistentialTraitRef<'tcx>>
+        where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
+    {
+        // Different traits cannot be related
+        if a.def_id != b.def_id {
+            Err(TypeError::Traits(expected_found(relation, &a.def_id, &b.def_id)))
+        } else {
+            let substs = relate_item_substs(relation, a.def_id, a.substs, b.substs)?;
+            Ok(ty::ExistentialTraitRef { def_id: a.def_id, substs: substs })
+        }
+    }
+}
+
 impl<'tcx> Relate<'tcx> for Ty<'tcx> {
     fn relate<'a, 'gcx, R>(relation: &mut R,
                            a: &Ty<'tcx>,
@@ -478,11 +483,23 @@ pub fn super_relate_tys<'a, 'gcx, 'tcx, R>(relation: &mut R,
             Ok(tcx.mk_enum(a_def, substs))
         }
 
-        (&ty::TyTrait(ref a_), &ty::TyTrait(ref b_)) =>
+        (&ty::TyTrait(ref a_obj), &ty::TyTrait(ref b_obj)) =>
         {
-            let principal = relation.relate(&a_.principal, &b_.principal)?;
-            let bounds = relation.relate(&a_.bounds, &b_.bounds)?;
-            Ok(tcx.mk_trait(principal, bounds))
+            let principal = relation.relate(&a_obj.principal, &b_obj.principal)?;
+            let r =
+                relation.with_cause(
+                    Cause::ExistentialRegionBound,
+                    |relation| relation.relate_with_variance(ty::Contravariant,
+                                                             &a_obj.region_bound,
+                                                             &b_obj.region_bound))?;
+            let nb = relation.relate(&a_obj.builtin_bounds, &b_obj.builtin_bounds)?;
+            let pb = relation.relate(&a_obj.projection_bounds, &b_obj.projection_bounds)?;
+            Ok(tcx.mk_trait(ty::TraitObject {
+                principal: principal,
+                region_bound: r,
+                builtin_bounds: nb,
+                projection_bounds: pb
+            }))
         }
 
         (&ty::TyStruct(a_def, a_substs), &ty::TyStruct(b_def, b_substs))
diff --git a/src/librustc/ty/structural_impls.rs b/src/librustc/ty/structural_impls.rs
index b0f8e2e13f7..14005c1bd8b 100644
--- a/src/librustc/ty/structural_impls.rs
+++ b/src/librustc/ty/structural_impls.rs
@@ -10,7 +10,7 @@
 
 use infer::type_variable;
 use ty::subst::{self, VecPerParamSpace};
-use ty::{self, Lift, TraitRef, Ty, TyCtxt};
+use ty::{self, Lift, Ty, TyCtxt};
 use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
 
 use std::rc::Rc;
@@ -80,10 +80,20 @@ impl<'tcx> Lift<'tcx> for ty::Region {
     }
 }
 
-impl<'a, 'tcx> Lift<'tcx> for TraitRef<'a> {
-    type Lifted = TraitRef<'tcx>;
-    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<TraitRef<'tcx>> {
-        tcx.lift(&self.substs).map(|substs| TraitRef {
+impl<'a, 'tcx> Lift<'tcx> for ty::TraitRef<'a> {
+    type Lifted = ty::TraitRef<'tcx>;
+    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
+        tcx.lift(&self.substs).map(|substs| ty::TraitRef {
+            def_id: self.def_id,
+            substs: substs
+        })
+    }
+}
+
+impl<'a, 'tcx> Lift<'tcx> for ty::ExistentialTraitRef<'a> {
+    type Lifted = ty::ExistentialTraitRef<'tcx>;
+    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
+        tcx.lift(&self.substs).map(|substs| ty::ExistentialTraitRef {
             def_id: self.def_id,
             substs: substs
         })
@@ -141,6 +151,19 @@ impl<'a, 'tcx> Lift<'tcx> for ty::ProjectionPredicate<'a> {
     }
 }
 
+impl<'a, 'tcx> Lift<'tcx> for ty::ExistentialProjection<'a> {
+    type Lifted = ty::ExistentialProjection<'tcx>;
+    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
+        tcx.lift(&(self.trait_ref, self.ty)).map(|(trait_ref, ty)| {
+            ty::ExistentialProjection {
+                trait_ref: trait_ref,
+                item_name: self.item_name,
+                ty: ty
+            }
+        })
+    }
+}
+
 impl<'a, 'tcx> Lift<'tcx> for ty::Predicate<'a> {
     type Lifted = ty::Predicate<'tcx>;
     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
@@ -437,16 +460,20 @@ impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for VecPerParamSpace<T> {
     }
 }
 
-impl<'tcx> TypeFoldable<'tcx> for ty::TraitTy<'tcx> {
+impl<'tcx> TypeFoldable<'tcx> for ty::TraitObject<'tcx> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
-        ty::TraitTy {
+        ty::TraitObject {
             principal: self.principal.fold_with(folder),
-            bounds: self.bounds.fold_with(folder),
+            region_bound: self.region_bound.fold_with(folder),
+            builtin_bounds: self.builtin_bounds,
+            projection_bounds: self.projection_bounds.fold_with(folder),
         }
     }
 
     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
-        self.principal.visit_with(visitor) || self.bounds.visit_with(visitor)
+        self.principal.visit_with(visitor) ||
+        self.region_bound.visit_with(visitor) ||
+        self.projection_bounds.visit_with(visitor)
     }
 }
 
@@ -599,8 +626,17 @@ impl<'tcx> TypeFoldable<'tcx> for ty::TraitRef<'tcx> {
         }
     }
 
-    fn fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
-        folder.fold_trait_ref(self)
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        self.substs.visit_with(visitor)
+    }
+}
+
+impl<'tcx> TypeFoldable<'tcx> for ty::ExistentialTraitRef<'tcx> {
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        ty::ExistentialTraitRef {
+            def_id: self.def_id,
+            substs: self.substs.fold_with(folder),
+        }
     }
 
     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
@@ -741,24 +777,6 @@ impl<'tcx> TypeFoldable<'tcx> for ty::BuiltinBounds {
     }
 }
 
-impl<'tcx> TypeFoldable<'tcx> for ty::ExistentialBounds<'tcx> {
-    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
-        ty::ExistentialBounds {
-            region_bound: self.region_bound.fold_with(folder),
-            builtin_bounds: self.builtin_bounds,
-            projection_bounds: self.projection_bounds.fold_with(folder),
-        }
-    }
-
-    fn fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
-        folder.fold_existential_bounds(self)
-    }
-
-    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
-        self.region_bound.visit_with(visitor) || self.projection_bounds.visit_with(visitor)
-    }
-}
-
 impl<'tcx> TypeFoldable<'tcx> for ty::TypeParameterDef<'tcx> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
         ty::TypeParameterDef {
@@ -893,6 +911,20 @@ impl<'tcx> TypeFoldable<'tcx> for ty::ProjectionPredicate<'tcx> {
     }
 }
 
+impl<'tcx> TypeFoldable<'tcx> for ty::ExistentialProjection<'tcx> {
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        ty::ExistentialProjection {
+            trait_ref: self.trait_ref.fold_with(folder),
+            item_name: self.item_name,
+            ty: self.ty.fold_with(folder),
+        }
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        self.trait_ref.visit_with(visitor) || self.ty.visit_with(visitor)
+    }
+}
+
 impl<'tcx> TypeFoldable<'tcx> for ty::ProjectionTy<'tcx> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
         ty::ProjectionTy {
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index 098943dfce2..91214873f19 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -152,7 +152,7 @@ pub enum TypeVariants<'tcx> {
     TyFnPtr(&'tcx BareFnTy<'tcx>),
 
     /// A trait, defined with `trait`.
-    TyTrait(Box<TraitTy<'tcx>>),
+    TyTrait(Box<TraitObject<'tcx>>),
 
     /// The anonymous type of a closure. Used to represent the type of
     /// `|a| a`.
@@ -291,57 +291,11 @@ impl<'tcx> Decodable for ClosureSubsts<'tcx> {
 }
 
 #[derive(Clone, PartialEq, Eq, Hash)]
-pub struct TraitTy<'tcx> {
-    pub principal: ty::PolyTraitRef<'tcx>,
-    pub bounds: ExistentialBounds<'tcx>,
-}
-
-impl<'a, 'gcx, 'tcx> TraitTy<'tcx> {
-    pub fn principal_def_id(&self) -> DefId {
-        self.principal.0.def_id
-    }
-
-    /// Object types don't have a self-type specified. Therefore, when
-    /// we convert the principal trait-ref into a normal trait-ref,
-    /// you must give *some* self-type. A common choice is `mk_err()`
-    /// or some skolemized type.
-    pub fn principal_trait_ref_with_self_ty(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
-                                            self_ty: Ty<'tcx>)
-                                            -> ty::PolyTraitRef<'tcx>
-    {
-        // otherwise the escaping regions would be captured by the binder
-        assert!(!self_ty.has_escaping_regions());
-
-        ty::Binder(TraitRef {
-            def_id: self.principal.0.def_id,
-            substs: tcx.mk_substs(self.principal.0.substs.with_self_ty(self_ty)),
-        })
-    }
-
-    pub fn projection_bounds_with_self_ty(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
-                                          self_ty: Ty<'tcx>)
-                                          -> Vec<ty::PolyProjectionPredicate<'tcx>>
-    {
-        // otherwise the escaping regions would be captured by the binders
-        assert!(!self_ty.has_escaping_regions());
-
-        self.bounds.projection_bounds.iter()
-            .map(|in_poly_projection_predicate| {
-                let in_projection_ty = &in_poly_projection_predicate.0.projection_ty;
-                let substs = tcx.mk_substs(in_projection_ty.trait_ref.substs.with_self_ty(self_ty));
-                let trait_ref = ty::TraitRef::new(in_projection_ty.trait_ref.def_id,
-                                              substs);
-                let projection_ty = ty::ProjectionTy {
-                    trait_ref: trait_ref,
-                    item_name: in_projection_ty.item_name
-                };
-                ty::Binder(ty::ProjectionPredicate {
-                    projection_ty: projection_ty,
-                    ty: in_poly_projection_predicate.0.ty
-                })
-            })
-            .collect()
-    }
+pub struct TraitObject<'tcx> {
+    pub principal: PolyExistentialTraitRef<'tcx>,
+    pub region_bound: ty::Region,
+    pub builtin_bounds: BuiltinBounds,
+    pub projection_bounds: Vec<PolyExistentialProjection<'tcx>>,
 }
 
 /// A complete reference to a trait. These take numerous guises in syntax,
@@ -392,6 +346,70 @@ impl<'tcx> PolyTraitRef<'tcx> {
     }
 }
 
+/// An existential reference to a trait, where `Self` is erased.
+/// For example, the trait object `Trait<'a, 'b, X, Y>` is:
+///
+///     exists T. T: Trait<'a, 'b, X, Y>
+///
+/// The substitutions don't include the erased `Self`, only trait
+/// type and lifetime parameters (`[X, Y]` and `['a, 'b]` above).
+#[derive(Copy, Clone, PartialEq, Eq, Hash)]
+pub struct ExistentialTraitRef<'tcx> {
+    pub def_id: DefId,
+    pub substs: &'tcx Substs<'tcx>,
+}
+
+impl<'a, 'gcx, 'tcx> ExistentialTraitRef<'tcx> {
+    pub fn erase_self_ty(tcx: TyCtxt<'a, 'gcx, 'tcx>,
+                         trait_ref: ty::TraitRef<'tcx>)
+                         -> ty::ExistentialTraitRef<'tcx> {
+        let mut substs = trait_ref.substs.clone();
+        substs.types.pop(subst::SelfSpace);
+        ty::ExistentialTraitRef {
+            def_id: trait_ref.def_id,
+            substs: tcx.mk_substs(substs)
+        }
+    }
+
+    pub fn input_types(&self) -> &[Ty<'tcx>] {
+        // Select only the "input types" from a trait-reference. For
+        // now this is all the types that appear in the
+        // trait-reference, but it should eventually exclude
+        // associated types.
+        self.substs.types.as_full_slice()
+    }
+}
+
+pub type PolyExistentialTraitRef<'tcx> = Binder<ExistentialTraitRef<'tcx>>;
+
+impl<'a, 'gcx, 'tcx> PolyExistentialTraitRef<'tcx> {
+    pub fn def_id(&self) -> DefId {
+        self.0.def_id
+    }
+
+    pub fn input_types(&self) -> &[Ty<'tcx>] {
+        // FIXME(#20664) every use of this fn is probably a bug, it should yield Binder<>
+        self.0.input_types()
+    }
+
+    /// Object types don't have a self-type specified. Therefore, when
+    /// we convert the principal trait-ref into a normal trait-ref,
+    /// you must give *some* self-type. A common choice is `mk_err()`
+    /// or some skolemized type.
+    pub fn with_self_ty(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
+                        self_ty: Ty<'tcx>)
+                        -> ty::PolyTraitRef<'tcx>
+    {
+        // otherwise the escaping regions would be captured by the binder
+        assert!(!self_ty.has_escaping_regions());
+
+        self.map_bound(|trait_ref| TraitRef {
+            def_id: trait_ref.def_id,
+            substs: tcx.mk_substs(trait_ref.substs.with_self_ty(self_ty)),
+        })
+    }
+}
+
 /// Binder is a binder for higher-ranked lifetimes. It is part of the
 /// compiler's representation for things like `for<'a> Fn(&'a isize)`
 /// (which would be represented by the type `PolyTraitRef ==
@@ -730,27 +748,40 @@ pub enum InferTy {
     FreshFloatTy(u32)
 }
 
-/// Bounds suitable for an existentially quantified type parameter
-/// such as those that appear in object types or closure types.
-#[derive(PartialEq, Eq, Hash, Clone)]
-pub struct ExistentialBounds<'tcx> {
-    pub region_bound: ty::Region,
-    pub builtin_bounds: BuiltinBounds,
-    pub projection_bounds: Vec<ty::PolyProjectionPredicate<'tcx>>,
+/// A `ProjectionPredicate` for an `ExistentialTraitRef`.
+#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
+pub struct ExistentialProjection<'tcx> {
+    pub trait_ref: ExistentialTraitRef<'tcx>,
+    pub item_name: Name,
+    pub ty: Ty<'tcx>
 }
 
-impl<'tcx> ExistentialBounds<'tcx> {
-    pub fn new(region_bound: ty::Region,
-               builtin_bounds: BuiltinBounds,
-               projection_bounds: Vec<ty::PolyProjectionPredicate<'tcx>>)
-               -> Self {
-        let mut projection_bounds = projection_bounds;
-        projection_bounds.sort_by(|a, b| a.sort_key().cmp(&b.sort_key()));
-        ExistentialBounds {
-            region_bound: region_bound,
-            builtin_bounds: builtin_bounds,
-            projection_bounds: projection_bounds
-        }
+pub type PolyExistentialProjection<'tcx> = Binder<ExistentialProjection<'tcx>>;
+
+impl<'a, 'tcx, 'gcx> PolyExistentialProjection<'tcx> {
+    pub fn item_name(&self) -> Name {
+        self.0.item_name // safe to skip the binder to access a name
+    }
+
+    pub fn sort_key(&self) -> (DefId, Name) {
+        (self.0.trait_ref.def_id, self.0.item_name)
+    }
+
+    pub fn with_self_ty(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
+                        self_ty: Ty<'tcx>)
+                        -> ty::PolyProjectionPredicate<'tcx>
+    {
+        // otherwise the escaping regions would be captured by the binders
+        assert!(!self_ty.has_escaping_regions());
+
+        let trait_ref = self.map_bound(|proj| proj.trait_ref);
+        self.map_bound(|proj| ty::ProjectionPredicate {
+            projection_ty: ty::ProjectionTy {
+                trait_ref: trait_ref.with_self_ty(tcx, self_ty).0,
+                item_name: proj.item_name
+            },
+            ty: proj.ty
+        })
     }
 }
 
@@ -1185,7 +1216,7 @@ impl<'a, 'gcx, 'tcx> TyS<'tcx> {
 
     pub fn ty_to_def_id(&self) -> Option<DefId> {
         match self.sty {
-            TyTrait(ref tt) => Some(tt.principal_def_id()),
+            TyTrait(ref tt) => Some(tt.principal.def_id()),
             TyStruct(def, _) |
             TyEnum(def, _) => Some(def.did),
             TyClosure(id, _) => Some(id),
@@ -1209,9 +1240,8 @@ impl<'a, 'gcx, 'tcx> TyS<'tcx> {
                 vec![*region]
             }
             TyTrait(ref obj) => {
-                let mut v = vec![obj.bounds.region_bound];
-                v.extend_from_slice(obj.principal.skip_binder()
-                                       .substs.regions.as_full_slice());
+                let mut v = vec![obj.region_bound];
+                v.extend_from_slice(obj.principal.skip_binder().substs.regions.as_full_slice());
                 v
             }
             TyEnum(_, substs) |
diff --git a/src/librustc/ty/util.rs b/src/librustc/ty/util.rs
index d7bb8ff2995..3c1f6e91992 100644
--- a/src/librustc/ty/util.rs
+++ b/src/librustc/ty/util.rs
@@ -451,21 +451,21 @@ impl<'a, 'gcx, 'tcx> TypeVisitor<'tcx> for TypeIdHasher<'a, 'gcx, 'tcx> {
                 // to sort them again by the name, in string form.
 
                 // Hash the whole principal trait ref.
-                self.def_id(data.principal_def_id());
+                self.def_id(data.principal.def_id());
                 data.principal.visit_with(self);
 
                 // Hash region and builtin bounds.
-                data.bounds.region_bound.visit_with(self);
-                self.hash(data.bounds.builtin_bounds);
+                data.region_bound.visit_with(self);
+                self.hash(data.builtin_bounds);
 
                 // Only projection bounds are left, sort and hash them.
-                let mut projection_bounds: Vec<_> = data.bounds.projection_bounds
+                let mut projection_bounds: Vec<_> = data.projection_bounds
                                                         .iter()
                                                         .map(|b| (b.item_name().as_str(), b))
                                                         .collect();
                 projection_bounds.sort_by_key(|&(ref name, _)| name.clone());
                 for (name, bound) in projection_bounds {
-                    self.def_id(bound.0.projection_ty.trait_ref.def_id);
+                    self.def_id(bound.0.trait_ref.def_id);
                     self.hash(name);
                     bound.visit_with(self);
                 }
diff --git a/src/librustc/ty/walk.rs b/src/librustc/ty/walk.rs
index 3f87d80e337..3bf53924557 100644
--- a/src/librustc/ty/walk.rs
+++ b/src/librustc/ty/walk.rs
@@ -81,9 +81,9 @@ fn push_subtypes<'tcx>(stack: &mut Vec<Ty<'tcx>>, parent_ty: Ty<'tcx>) {
         ty::TyProjection(ref data) => {
             push_reversed(stack, data.trait_ref.substs.types.as_full_slice());
         }
-        ty::TyTrait(box ty::TraitTy { ref principal, ref bounds }) => {
-            push_reversed(stack, principal.substs().types.as_full_slice());
-            push_reversed(stack, &bounds.projection_bounds.iter().map(|pred| {
+        ty::TyTrait(ref obj) => {
+            push_reversed(stack, obj.principal.input_types());
+            push_reversed(stack, &obj.projection_bounds.iter().map(|pred| {
                 pred.0.ty
             }).collect::<Vec<_>>());
         }
diff --git a/src/librustc/ty/wf.rs b/src/librustc/ty/wf.rs
index 009e3e24334..77d0835bf6b 100644
--- a/src/librustc/ty/wf.rs
+++ b/src/librustc/ty/wf.rs
@@ -406,13 +406,13 @@ impl<'a, 'gcx, 'tcx> WfPredicates<'a, 'gcx, 'tcx> {
                     // FIXME(#33243): remove RFC1592
                     self.out.push(traits::Obligation::new(
                         cause.clone(),
-                        ty::Predicate::ObjectSafe(data.principal_def_id())
+                        ty::Predicate::ObjectSafe(data.principal.def_id())
                     ));
                     let component_traits =
-                        data.bounds.builtin_bounds.iter().flat_map(|bound| {
+                        data.builtin_bounds.iter().flat_map(|bound| {
                             tcx.lang_items.from_builtin_kind(bound).ok()
                         });
-//                        .chain(Some(data.principal_def_id()));
+//                        .chain(Some(data.principal.def_id()));
                     self.out.extend(
                         component_traits.map(|did| { traits::Obligation::new(
                             cause.clone(),
@@ -476,7 +476,7 @@ impl<'a, 'gcx, 'tcx> WfPredicates<'a, 'gcx, 'tcx> {
                   .collect()
     }
 
-    fn from_object_ty(&mut self, ty: Ty<'tcx>, data: &ty::TraitTy<'tcx>) {
+    fn from_object_ty(&mut self, ty: Ty<'tcx>, data: &ty::TraitObject<'tcx>) {
         // Imagine a type like this:
         //
         //     trait Foo { }
@@ -512,10 +512,10 @@ impl<'a, 'gcx, 'tcx> WfPredicates<'a, 'gcx, 'tcx> {
         if !data.has_escaping_regions() {
             let implicit_bounds =
                 object_region_bounds(self.infcx.tcx,
-                                     &data.principal,
-                                     data.bounds.builtin_bounds);
+                                     data.principal,
+                                     data.builtin_bounds);
 
-            let explicit_bound = data.bounds.region_bound;
+            let explicit_bound = data.region_bound;
 
             for implicit_bound in implicit_bounds {
                 let cause = self.cause(traits::ReferenceOutlivesReferent(ty));
@@ -534,7 +534,7 @@ impl<'a, 'gcx, 'tcx> WfPredicates<'a, 'gcx, 'tcx> {
 /// `ty::required_region_bounds`, see that for more information.
 pub fn object_region_bounds<'a, 'gcx, 'tcx>(
     tcx: TyCtxt<'a, 'gcx, 'tcx>,
-    principal: &ty::PolyTraitRef<'tcx>,
+    principal: ty::PolyExistentialTraitRef<'tcx>,
     others: ty::BuiltinBounds)
     -> Vec<ty::Region>
 {
@@ -543,13 +543,8 @@ pub fn object_region_bounds<'a, 'gcx, 'tcx>(
     // a skolemized type.
     let open_ty = tcx.mk_infer(ty::FreshTy(0));
 
-    // Note that we preserve the overall binding levels here.
-    assert!(!open_ty.has_escaping_regions());
-    let substs = tcx.mk_substs(principal.0.substs.with_self_ty(open_ty));
-    let trait_refs = vec!(ty::Binder(ty::TraitRef::new(principal.0.def_id, substs)));
-
     let mut predicates = others.to_predicates(tcx, open_ty);
-    predicates.extend(trait_refs.iter().map(|t| t.to_predicate()));
+    predicates.push(principal.with_self_ty(tcx, open_ty).to_predicate());
 
     tcx.required_region_bounds(open_ty, predicates)
 }
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 37750b568bb..fb0b6413fab 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -288,7 +288,8 @@ fn in_binder<'a, 'gcx, 'tcx, T, U>(f: &mut fmt::Formatter,
 /// projection bounds, so we just stuff them altogether. But in
 /// reality we should eventually sort things out better.
 #[derive(Clone, Debug)]
-struct TraitAndProjections<'tcx>(ty::TraitRef<'tcx>, Vec<ty::ProjectionPredicate<'tcx>>);
+struct TraitAndProjections<'tcx>(ty::ExistentialTraitRef<'tcx>,
+                                 Vec<ty::ProjectionPredicate<'tcx>>);
 
 impl<'tcx> TypeFoldable<'tcx> for TraitAndProjections<'tcx> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
@@ -311,24 +312,24 @@ impl<'tcx> fmt::Display for TraitAndProjections<'tcx> {
     }
 }
 
-impl<'tcx> fmt::Display for ty::TraitTy<'tcx> {
+impl<'tcx> fmt::Display for ty::TraitObject<'tcx> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        let bounds = &self.bounds;
-
         // Generate the main trait ref, including associated types.
         ty::tls::with(|tcx| {
             let principal = tcx.lift(&self.principal.0)
                                .expect("could not lift TraitRef for printing");
-            let projections = tcx.lift(&bounds.projection_bounds[..])
-                                 .expect("could not lift projections for printing");
-            let projections = projections.into_iter().map(|p| p.0).collect();
+            let projections = self.projection_bounds.iter().map(|p| {
+                let projection = tcx.lift(p)
+                                    .expect("could not lift projection for printing");
+                projection.with_self_ty(tcx, tcx.types.err).0
+            }).collect();
 
             let tap = ty::Binder(TraitAndProjections(principal, projections));
             in_binder(f, tcx, &ty::Binder(""), Some(tap))
         })?;
 
         // Builtin bounds.
-        for bound in &bounds.builtin_bounds {
+        for bound in &self.builtin_bounds {
             write!(f, " + {:?}", bound)?;
         }
 
@@ -337,7 +338,7 @@ impl<'tcx> fmt::Display for ty::TraitTy<'tcx> {
         // use thread-local data of some kind? There are also
         // advantages to just showing the region, since it makes
         // people aware that it's there.
-        let bound = bounds.region_bound.to_string();
+        let bound = self.region_bound.to_string();
         if !bound.is_empty() {
             write!(f, " + {}", bound)?;
         }
@@ -397,10 +398,13 @@ impl<'tcx> fmt::Debug for ty::TraitRef<'tcx> {
         // when printing out the debug representation, we don't need
         // to enumerate the `for<...>` etc because the debruijn index
         // tells you everything you need to know.
-        match self.substs.self_ty() {
-            None => write!(f, "{}", *self),
-            Some(self_ty) => write!(f, "<{:?} as {}>", self_ty, *self)
-        }
+        write!(f, "<{:?} as {}>", self.self_ty(), *self)
+    }
+}
+
+impl<'tcx> fmt::Debug for ty::ExistentialTraitRef<'tcx> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{}", *self)
     }
 }
 
@@ -448,11 +452,38 @@ impl<'tcx> fmt::Debug for ty::adjustment::AutoDerefRef<'tcx> {
     }
 }
 
-impl<'tcx> fmt::Debug for ty::TraitTy<'tcx> {
+impl<'tcx> fmt::Debug for ty::TraitObject<'tcx> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "TraitTy({:?},{:?})",
-               self.principal,
-               self.bounds)
+        let mut empty = true;
+        let mut maybe_continue = |f: &mut fmt::Formatter| {
+            if empty {
+                empty = false;
+                Ok(())
+            } else {
+                write!(f, " + ")
+            }
+        };
+
+        maybe_continue(f)?;
+        write!(f, "{:?}", self.principal)?;
+
+        let region_str = format!("{:?}", self.region_bound);
+        if !region_str.is_empty() {
+            maybe_continue(f)?;
+            write!(f, "{}", region_str)?;
+        }
+
+        for bound in &self.builtin_bounds {
+            maybe_continue(f)?;
+            write!(f, "{:?}", bound)?;
+        }
+
+        for projection_bound in &self.projection_bounds {
+            maybe_continue(f)?;
+            write!(f, "{:?}", projection_bound)?;
+        }
+
+        Ok(())
     }
 }
 
@@ -668,38 +699,6 @@ impl<'tcx> fmt::Display for ty::FnSig<'tcx> {
     }
 }
 
-impl<'tcx> fmt::Debug for ty::ExistentialBounds<'tcx> {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        let mut empty = true;
-        let mut maybe_continue = |f: &mut fmt::Formatter| {
-            if empty {
-                empty = false;
-                Ok(())
-            } else {
-                write!(f, " + ")
-            }
-        };
-
-        let region_str = format!("{:?}", self.region_bound);
-        if !region_str.is_empty() {
-            maybe_continue(f)?;
-            write!(f, "{}", region_str)?;
-        }
-
-        for bound in &self.builtin_bounds {
-            maybe_continue(f)?;
-            write!(f, "{:?}", bound)?;
-        }
-
-        for projection_bound in &self.projection_bounds {
-            maybe_continue(f)?;
-            write!(f, "{:?}", projection_bound)?;
-        }
-
-        Ok(())
-    }
-}
-
 impl fmt::Display for ty::BuiltinBounds {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         let mut bounds = self.iter();
@@ -819,6 +818,13 @@ impl<'tcx> fmt::Display for ty::TraitRef<'tcx> {
     }
 }
 
+impl<'tcx> fmt::Display for ty::ExistentialTraitRef<'tcx> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        parameterized(f, self.substs, self.def_id, Ns::Type, &[],
+                      |tcx| Some(tcx.lookup_trait_def(self.def_id).generics.clone()))
+    }
+}
+
 impl<'tcx> fmt::Display for ty::TypeVariants<'tcx> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         match *self {
diff --git a/src/librustc_metadata/astencode.rs b/src/librustc_metadata/astencode.rs
index b8e66530ea1..c552e612504 100644
--- a/src/librustc_metadata/astencode.rs
+++ b/src/librustc_metadata/astencode.rs
@@ -524,16 +524,8 @@ pub fn encode_cast_kind(ebml_w: &mut Encoder, kind: cast::CastKind) {
 trait rbml_writer_helpers<'tcx> {
     fn emit_region(&mut self, ecx: &e::EncodeContext, r: ty::Region);
     fn emit_ty<'a>(&mut self, ecx: &e::EncodeContext<'a, 'tcx>, ty: Ty<'tcx>);
-    fn emit_tys<'a>(&mut self, ecx: &e::EncodeContext<'a, 'tcx>, tys: &[Ty<'tcx>]);
-    fn emit_predicate<'a>(&mut self, ecx: &e::EncodeContext<'a, 'tcx>,
-                          predicate: &ty::Predicate<'tcx>);
-    fn emit_trait_ref<'a>(&mut self, ecx: &e::EncodeContext<'a, 'tcx>,
-                          ty: &ty::TraitRef<'tcx>);
     fn emit_substs<'a>(&mut self, ecx: &e::EncodeContext<'a, 'tcx>,
                        substs: &subst::Substs<'tcx>);
-    fn emit_existential_bounds<'b>(&mut self, ecx: &e::EncodeContext<'b,'tcx>,
-                                   bounds: &ty::ExistentialBounds<'tcx>);
-    fn emit_builtin_bounds(&mut self, ecx: &e::EncodeContext, bounds: &ty::BuiltinBounds);
     fn emit_upvar_capture(&mut self, ecx: &e::EncodeContext, capture: &ty::UpvarCapture);
     fn emit_auto_adjustment<'a>(&mut self, ecx: &e::EncodeContext<'a, 'tcx>,
                                 adj: &adjustment::AutoAdjustment<'tcx>);
@@ -556,39 +548,6 @@ impl<'a, 'tcx> rbml_writer_helpers<'tcx> for Encoder<'a> {
                                                     ty)));
     }
 
-    fn emit_tys<'b>(&mut self, ecx: &e::EncodeContext<'b, 'tcx>, tys: &[Ty<'tcx>]) {
-        self.emit_from_vec(tys, |this, ty| Ok(this.emit_ty(ecx, *ty)));
-    }
-
-    fn emit_trait_ref<'b>(&mut self, ecx: &e::EncodeContext<'b, 'tcx>,
-                          trait_ref: &ty::TraitRef<'tcx>) {
-        self.emit_opaque(|this| Ok(tyencode::enc_trait_ref(&mut this.cursor,
-                                                           &ecx.ty_str_ctxt(),
-                                                           *trait_ref)));
-    }
-
-    fn emit_predicate<'b>(&mut self, ecx: &e::EncodeContext<'b, 'tcx>,
-                          predicate: &ty::Predicate<'tcx>) {
-        self.emit_opaque(|this| {
-            Ok(tyencode::enc_predicate(&mut this.cursor,
-                                       &ecx.ty_str_ctxt(),
-                                       predicate))
-        });
-    }
-
-    fn emit_existential_bounds<'b>(&mut self, ecx: &e::EncodeContext<'b,'tcx>,
-                                   bounds: &ty::ExistentialBounds<'tcx>) {
-        self.emit_opaque(|this| Ok(tyencode::enc_existential_bounds(&mut this.cursor,
-                                                                    &ecx.ty_str_ctxt(),
-                                                                    bounds)));
-    }
-
-    fn emit_builtin_bounds(&mut self, ecx: &e::EncodeContext, bounds: &ty::BuiltinBounds) {
-        self.emit_opaque(|this| Ok(tyencode::enc_builtin_bounds(&mut this.cursor,
-                                                                &ecx.ty_str_ctxt(),
-                                                                bounds)));
-    }
-
     fn emit_upvar_capture(&mut self, ecx: &e::EncodeContext, capture: &ty::UpvarCapture) {
         use rustc_serialize::Encoder;
 
@@ -879,8 +838,6 @@ trait rbml_decoder_decoder_helpers<'tcx> {
                                    -> ty::PolyTraitRef<'tcx>;
     fn read_predicate<'a, 'b>(&mut self, dcx: &DecodeContext<'a, 'b, 'tcx>)
                               -> ty::Predicate<'tcx>;
-    fn read_existential_bounds<'a, 'b>(&mut self, dcx: &DecodeContext<'a, 'b, 'tcx>)
-                                       -> ty::ExistentialBounds<'tcx>;
     fn read_substs<'a, 'b>(&mut self, dcx: &DecodeContext<'a, 'b, 'tcx>)
                            -> subst::Substs<'tcx>;
     fn read_upvar_capture(&mut self, dcx: &DecodeContext)
@@ -988,12 +945,6 @@ impl<'a, 'tcx> rbml_decoder_decoder_helpers<'tcx> for reader::Decoder<'a> {
         self.read_ty_encoded(dcx, |decoder| decoder.parse_predicate())
     }
 
-    fn read_existential_bounds<'b, 'c>(&mut self, dcx: &DecodeContext<'b, 'c, 'tcx>)
-                                       -> ty::ExistentialBounds<'tcx>
-    {
-        self.read_ty_encoded(dcx, |decoder| decoder.parse_existential_bounds())
-    }
-
     fn read_substs<'b, 'c>(&mut self, dcx: &DecodeContext<'b, 'c, 'tcx>)
                            -> subst::Substs<'tcx> {
         self.read_opaque(|_, doc| {
diff --git a/src/librustc_metadata/tydecode.rs b/src/librustc_metadata/tydecode.rs
index 7b4919bb477..11c155cbd5b 100644
--- a/src/librustc_metadata/tydecode.rs
+++ b/src/librustc_metadata/tydecode.rs
@@ -307,6 +307,12 @@ impl<'a,'tcx> TyDecoder<'a,'tcx> {
         ty::TraitRef {def_id: def, substs: substs}
     }
 
+    pub fn parse_existential_trait_ref(&mut self) -> ty::ExistentialTraitRef<'tcx> {
+        let def = self.parse_def();
+        let substs = self.tcx.mk_substs(self.parse_substs());
+        ty::ExistentialTraitRef {def_id: def, substs: substs}
+    }
+
     pub fn parse_ty(&mut self) -> Ty<'tcx> {
         let tcx = self.tcx;
         match self.next() {
@@ -340,10 +346,30 @@ impl<'a,'tcx> TyDecoder<'a,'tcx> {
             }
             'x' => {
                 assert_eq!(self.next(), '[');
-                let trait_ref = ty::Binder(self.parse_trait_ref());
-                let bounds = self.parse_existential_bounds();
+                let trait_ref = ty::Binder(self.parse_existential_trait_ref());
+                let builtin_bounds = self.parse_builtin_bounds();
+                let region_bound = self.parse_region();
+                let mut projection_bounds = Vec::new();
+
+                loop {
+                    match self.next() {
+                        'P' => {
+                            let bound = self.parse_existential_projection();
+                            projection_bounds.push(ty::Binder(bound));
+                        }
+                        '.' => { break; }
+                        c => {
+                            bug!("parse_bounds: bad bounds ('{}')", c)
+                        }
+                    }
+                }
                 assert_eq!(self.next(), ']');
-                return tcx.mk_trait(trait_ref, bounds);
+                return tcx.mk_trait(ty::TraitObject {
+                    principal: trait_ref,
+                    region_bound: region_bound,
+                    builtin_bounds: builtin_bounds,
+                    projection_bounds: projection_bounds
+                });
             }
             'p' => {
                 assert_eq!(self.next(), '[');
@@ -588,6 +614,14 @@ impl<'a,'tcx> TyDecoder<'a,'tcx> {
         }
     }
 
+    fn parse_existential_projection(&mut self) -> ty::ExistentialProjection<'tcx> {
+        ty::ExistentialProjection {
+            trait_ref: self.parse_existential_trait_ref(),
+            item_name: token::intern(&self.parse_str('|')),
+            ty: self.parse_ty(),
+        }
+    }
+
     pub fn parse_type_param_def(&mut self) -> ty::TypeParameterDef<'tcx> {
         let name = self.parse_name(':');
         let def_id = self.parse_def();
@@ -649,27 +683,6 @@ impl<'a,'tcx> TyDecoder<'a,'tcx> {
         }
     }
 
-    pub fn parse_existential_bounds(&mut self) -> ty::ExistentialBounds<'tcx> {
-        let builtin_bounds = self.parse_builtin_bounds();
-        let region_bound = self.parse_region();
-        let mut projection_bounds = Vec::new();
-
-        loop {
-            match self.next() {
-                'P' => {
-                    projection_bounds.push(ty::Binder(self.parse_projection_predicate()));
-                }
-                '.' => { break; }
-                c => {
-                    bug!("parse_bounds: bad bounds ('{}')", c)
-                }
-            }
-        }
-
-        ty::ExistentialBounds::new(
-            region_bound, builtin_bounds, projection_bounds)
-    }
-
     fn parse_builtin_bounds(&mut self) -> ty::BuiltinBounds {
         let mut builtin_bounds = ty::BuiltinBounds::empty();
         loop {
diff --git a/src/librustc_metadata/tyencode.rs b/src/librustc_metadata/tyencode.rs
index 15bafcdd3c9..8deb1eb6ac3 100644
--- a/src/librustc_metadata/tyencode.rs
+++ b/src/librustc_metadata/tyencode.rs
@@ -104,11 +104,26 @@ pub fn enc_ty<'a, 'tcx>(w: &mut Cursor<Vec<u8>>, cx: &ctxt<'a, 'tcx>, t: Ty<'tcx
             enc_substs(w, cx, substs);
             write!(w, "]");
         }
-        ty::TyTrait(box ty::TraitTy { ref principal,
-                                       ref bounds }) => {
+        ty::TyTrait(ref obj) => {
             write!(w, "x[");
-            enc_trait_ref(w, cx, principal.0);
-            enc_existential_bounds(w, cx, bounds);
+            enc_existential_trait_ref(w, cx, obj.principal.0);
+            enc_builtin_bounds(w, cx, &obj.builtin_bounds);
+
+            enc_region(w, cx, obj.region_bound);
+
+            // Encode projection_bounds in a stable order
+            let mut projection_bounds: Vec<_> = obj.projection_bounds
+                                                .iter()
+                                                .map(|b| (b.item_name().as_str(), b))
+                                                .collect();
+            projection_bounds.sort_by_key(|&(ref name, _)| name.clone());
+
+            for tp in projection_bounds.iter().map(|&(_, tp)| tp) {
+                write!(w, "P");
+                enc_existential_projection(w, cx, &tp.0);
+            }
+
+            write!(w, ".");
             write!(w, "]");
         }
         ty::TyTuple(ts) => {
@@ -344,6 +359,12 @@ pub fn enc_trait_ref<'a, 'tcx>(w: &mut Cursor<Vec<u8>>, cx: &ctxt<'a, 'tcx>,
     enc_substs(w, cx, s.substs);
 }
 
+fn enc_existential_trait_ref<'a, 'tcx>(w: &mut Cursor<Vec<u8>>, cx: &ctxt<'a, 'tcx>,
+                                       s: ty::ExistentialTraitRef<'tcx>) {
+    write!(w, "{}|", (cx.ds)(cx.tcx, s.def_id));
+    enc_substs(w, cx, s.substs);
+}
+
 fn enc_unsafety(w: &mut Cursor<Vec<u8>>, p: hir::Unsafety) {
     match p {
         hir::Unsafety::Normal => write!(w, "n"),
@@ -386,7 +407,7 @@ fn enc_fn_sig<'a, 'tcx>(w: &mut Cursor<Vec<u8>>, cx: &ctxt<'a, 'tcx>,
     enc_ty(w, cx, fsig.0.output);
 }
 
-pub fn enc_builtin_bounds(w: &mut Cursor<Vec<u8>>, _cx: &ctxt, bs: &ty::BuiltinBounds) {
+fn enc_builtin_bounds(w: &mut Cursor<Vec<u8>>, _cx: &ctxt, bs: &ty::BuiltinBounds) {
     for bound in bs {
         match bound {
             ty::BoundSend => write!(w, "S"),
@@ -399,28 +420,6 @@ pub fn enc_builtin_bounds(w: &mut Cursor<Vec<u8>>, _cx: &ctxt, bs: &ty::BuiltinB
     write!(w, ".");
 }
 
-pub fn enc_existential_bounds<'a,'tcx>(w: &mut Cursor<Vec<u8>>,
-                                       cx: &ctxt<'a,'tcx>,
-                                       bs: &ty::ExistentialBounds<'tcx>) {
-    enc_builtin_bounds(w, cx, &bs.builtin_bounds);
-
-    enc_region(w, cx, bs.region_bound);
-
-    // Encode projection_bounds in a stable order
-    let mut projection_bounds: Vec<_> = bs.projection_bounds
-                                          .iter()
-                                          .map(|b| (b.item_name().as_str(), b))
-                                          .collect();
-    projection_bounds.sort_by_key(|&(ref name, _)| name.clone());
-
-    for tp in projection_bounds.iter().map(|&(_, tp)| tp) {
-        write!(w, "P");
-        enc_projection_predicate(w, cx, &tp.0);
-    }
-
-    write!(w, ".");
-}
-
 pub fn enc_type_param_def<'a, 'tcx>(w: &mut Cursor<Vec<u8>>, cx: &ctxt<'a, 'tcx>,
                                     v: &ty::TypeParameterDef<'tcx>) {
     write!(w, "{}:{}|{}|{}|{}|",
@@ -489,7 +488,9 @@ pub fn enc_predicate<'a, 'tcx>(w: &mut Cursor<Vec<u8>>,
         }
         ty::Predicate::Projection(ty::Binder(ref data)) => {
             write!(w, "p");
-            enc_projection_predicate(w, cx, data);
+            enc_trait_ref(w, cx, data.projection_ty.trait_ref);
+            write!(w, "{}|", data.projection_ty.item_name);
+            enc_ty(w, cx, data.ty);
         }
         ty::Predicate::WellFormed(data) => {
             write!(w, "w");
@@ -509,10 +510,10 @@ pub fn enc_predicate<'a, 'tcx>(w: &mut Cursor<Vec<u8>>,
     }
 }
 
-fn enc_projection_predicate<'a, 'tcx>(w: &mut Cursor<Vec<u8>>,
-                                      cx: &ctxt<'a, 'tcx>,
-                                      data: &ty::ProjectionPredicate<'tcx>) {
-    enc_trait_ref(w, cx, data.projection_ty.trait_ref);
-    write!(w, "{}|", data.projection_ty.item_name);
+fn enc_existential_projection<'a, 'tcx>(w: &mut Cursor<Vec<u8>>,
+                                        cx: &ctxt<'a, 'tcx>,
+                                        data: &ty::ExistentialProjection<'tcx>) {
+    enc_existential_trait_ref(w, cx, data.trait_ref);
+    write!(w, "{}|", data.item_name);
     enc_ty(w, cx, data.ty);
 }
diff --git a/src/librustc_trans/base.rs b/src/librustc_trans/base.rs
index 0dcac188bb0..749a7495421 100644
--- a/src/librustc_trans/base.rs
+++ b/src/librustc_trans/base.rs
@@ -562,14 +562,9 @@ pub fn unsized_info<'ccx, 'tcx>(ccx: &CrateContext<'ccx, 'tcx>,
             // change to the vtable.
             old_info.expect("unsized_info: missing old info for trait upcast")
         }
-        (_, &ty::TyTrait(box ty::TraitTy { ref principal, .. })) => {
-            // Note that we preserve binding levels here:
-            let substs = principal.0.substs.with_self_ty(source).erase_regions();
-            let substs = ccx.tcx().mk_substs(substs);
-            let trait_ref = ty::Binder(ty::TraitRef {
-                def_id: principal.def_id(),
-                substs: substs,
-            });
+        (_, &ty::TyTrait(ref data)) => {
+            let trait_ref = data.principal.with_self_ty(ccx.tcx(), source);
+            let trait_ref = ccx.tcx().erase_regions(&trait_ref);
             consts::ptrcast(meth::get_vtable(ccx, trait_ref),
                             Type::vtable_ptr(ccx))
         }
diff --git a/src/librustc_trans/collector.rs b/src/librustc_trans/collector.rs
index ffacbae1afd..277110347d0 100644
--- a/src/librustc_trans/collector.rs
+++ b/src/librustc_trans/collector.rs
@@ -1055,8 +1055,7 @@ fn create_trans_items_for_vtable_methods<'a, 'tcx>(scx: &SharedCrateContext<'a,
     assert!(!trait_ty.needs_subst() && !impl_ty.needs_subst());
 
     if let ty::TyTrait(ref trait_ty) = trait_ty.sty {
-        let poly_trait_ref = trait_ty.principal_trait_ref_with_self_ty(scx.tcx(),
-                                                                       impl_ty);
+        let poly_trait_ref = trait_ty.principal.with_self_ty(scx.tcx(), impl_ty);
 
         // Walk all methods of the trait, including those of its supertraits
         for trait_ref in traits::supertraits(scx.tcx(), poly_trait_ref) {
diff --git a/src/librustc_trans/debuginfo/metadata.rs b/src/librustc_trans/debuginfo/metadata.rs
index 3fe8b2b6679..6a99f12b278 100644
--- a/src/librustc_trans/debuginfo/metadata.rs
+++ b/src/librustc_trans/debuginfo/metadata.rs
@@ -627,7 +627,7 @@ fn trait_pointer_metadata<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
     // But it does not describe the trait's methods.
 
     let def_id = match trait_type.sty {
-        ty::TyTrait(ref data) => data.principal_def_id(),
+        ty::TyTrait(ref data) => data.principal.def_id(),
         _ => {
             bug!("debuginfo: Unexpected trait-object type in \
                   trait_pointer_metadata(): {:?}",
diff --git a/src/librustc_trans/trans_item.rs b/src/librustc_trans/trans_item.rs
index c1149279b4d..2dd07cf4405 100644
--- a/src/librustc_trans/trans_item.rs
+++ b/src/librustc_trans/trans_item.rs
@@ -476,10 +476,10 @@ pub fn push_unique_type_name<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
             output.push(']');
         },
         ty::TyTrait(ref trait_data) => {
-            push_item_name(tcx, trait_data.principal.skip_binder().def_id, output);
+            push_item_name(tcx, trait_data.principal.def_id(), output);
             push_type_params(tcx,
                              &trait_data.principal.skip_binder().substs.types,
-                             &trait_data.bounds.projection_bounds,
+                             &trait_data.projection_bounds,
                              output);
         },
         ty::TyFnDef(_, _, &ty::BareFnTy{ unsafety, abi, ref sig } ) |
@@ -562,7 +562,7 @@ fn push_item_name(tcx: TyCtxt,
 
 fn push_type_params<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                               types: &'tcx subst::VecPerParamSpace<Ty<'tcx>>,
-                              projections: &[ty::PolyProjectionPredicate<'tcx>],
+                              projections: &[ty::PolyExistentialProjection<'tcx>],
                               output: &mut String) {
     if types.is_empty() && projections.is_empty() {
         return;
@@ -577,7 +577,7 @@ fn push_type_params<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
     for projection in projections {
         let projection = projection.skip_binder();
-        let name = &projection.projection_ty.item_name.as_str();
+        let name = &projection.item_name.as_str();
         output.push_str(name);
         output.push_str("=");
         push_unique_type_name(tcx, projection.ty, output);
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index ea7b447632c..ed4ea3c937b 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -169,6 +169,11 @@ struct ConvertedBinding<'tcx> {
 
 type TraitAndProjections<'tcx> = (ty::PolyTraitRef<'tcx>, Vec<ty::PolyProjectionPredicate<'tcx>>);
 
+/// Dummy type used for the `Self` of a `TraitRef` created for converting
+/// a trait object, and which gets removed in `ExistentialTraitRef`.
+/// This type must not appear anywhere in other converted types.
+const TRAIT_OBJECT_DUMMY_SELF: ty::TypeVariants<'static> = ty::TyInfer(ty::FreshTy(0));
+
 pub fn ast_region_to_region(tcx: TyCtxt, lifetime: &hir::Lifetime)
                             -> ty::Region {
     let r = match tcx.named_region_map.defs.get(&lifetime.id) {
@@ -478,48 +483,37 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
                 type_substs.len() <= formal_ty_param_count);
 
         let mut substs = region_substs;
-        substs.types.extend(TypeSpace, type_substs.into_iter());
 
-        match self_ty {
-            None => {
-                // If no self-type is provided, it's still possible that
-                // one was declared, because this could be an object type.
-            }
-            Some(ty) => {
-                // If a self-type is provided, one should have been
-                // "declared" (in other words, this should be a
-                // trait-ref).
-                assert!(decl_generics.types.get_self().is_some());
-                substs.types.push(SelfSpace, ty);
-            }
-        }
+        // If a self-type was declared, one should be provided.
+        assert_eq!(decl_generics.types.get_self().is_some(), self_ty.is_some());
+        substs.types.extend(SelfSpace, self_ty.into_iter());
+        substs.types.extend(TypeSpace, type_substs.into_iter());
 
+        let is_object = self_ty.map_or(false, |ty| ty.sty == TRAIT_OBJECT_DUMMY_SELF);
         let actual_supplied_ty_param_count = substs.types.len(TypeSpace);
         for param in &ty_param_defs[actual_supplied_ty_param_count..] {
-            if let Some(default) = param.default {
+            let default = if let Some(default) = param.default {
                 // If we are converting an object type, then the
                 // `Self` parameter is unknown. However, some of the
                 // other type parameters may reference `Self` in their
                 // defaults. This will lead to an ICE if we are not
                 // careful!
-                if self_ty.is_none() && default.has_self_ty() {
+                if is_object && default.has_self_ty() {
                     span_err!(tcx.sess, span, E0393,
                               "the type parameter `{}` must be explicitly specified \
                                in an object type because its default value `{}` references \
                                the type `Self`",
                               param.name,
                               default);
-                    substs.types.push(TypeSpace, tcx.types.err);
+                    tcx.types.err
                 } else {
                     // This is a default type parameter.
-                    let default = default.subst_spanned(tcx,
-                                                        &substs,
-                                                        Some(span));
-                    substs.types.push(TypeSpace, default);
+                    default.subst_spanned(tcx, &substs, Some(span))
                 }
             } else {
                 span_bug!(span, "extra parameter without default");
-            }
+            };
+            substs.types.push(TypeSpace, default);
         }
 
         debug!("create_substs_for_ast_path(decl_generics={:?}, self_ty={:?}) -> {:?}",
@@ -539,11 +533,12 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
                                 self_ty: Option<Ty<'tcx>>)
                                 -> Vec<Ty<'tcx>>
     {
+        let is_object = self_ty.map_or(false, |ty| ty.sty == TRAIT_OBJECT_DUMMY_SELF);
         let use_default = |p: &ty::TypeParameterDef<'tcx>| {
             if let Some(ref default) = p.default {
-                if self_ty.is_none() && default.has_self_ty() {
+                if is_object && default.has_self_ty() {
                     // There is no suitable inference default for a type parameter
-                    // that references self with no self-type provided.
+                    // that references self, in an object type.
                     return false;
                 }
             }
@@ -709,7 +704,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
     pub fn instantiate_poly_trait_ref(&self,
         rscope: &RegionScope,
         ast_trait_ref: &hir::PolyTraitRef,
-        self_ty: Option<Ty<'tcx>>,
+        self_ty: Ty<'tcx>,
         poly_projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
         -> ty::PolyTraitRef<'tcx>
     {
@@ -734,7 +729,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
     pub fn instantiate_mono_trait_ref(&self,
         rscope: &RegionScope,
         trait_ref: &hir::TraitRef,
-        self_ty: Option<Ty<'tcx>>)
+        self_ty: Ty<'tcx>)
         -> ty::TraitRef<'tcx>
     {
         let trait_def_id = self.trait_def_id(trait_ref);
@@ -760,32 +755,12 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
         }
     }
 
-    fn object_path_to_poly_trait_ref(&self,
-        rscope: &RegionScope,
-        span: Span,
-        param_mode: PathParamMode,
-        trait_def_id: DefId,
-        trait_path_ref_id: ast::NodeId,
-        trait_segment: &hir::PathSegment,
-        mut projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
-        -> ty::PolyTraitRef<'tcx>
-    {
-        self.ast_path_to_poly_trait_ref(rscope,
-                                        span,
-                                        param_mode,
-                                        trait_def_id,
-                                        None,
-                                        trait_path_ref_id,
-                                        trait_segment,
-                                        projections)
-    }
-
     fn ast_path_to_poly_trait_ref(&self,
         rscope: &RegionScope,
         span: Span,
         param_mode: PathParamMode,
         trait_def_id: DefId,
-        self_ty: Option<Ty<'tcx>>,
+        self_ty: Ty<'tcx>,
         path_id: ast::NodeId,
         trait_segment: &hir::PathSegment,
         poly_projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
@@ -808,21 +783,14 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
                                                  trait_segment);
         let poly_trait_ref = ty::Binder(ty::TraitRef::new(trait_def_id, substs));
 
-        {
-            let converted_bindings =
-                assoc_bindings
-                .iter()
-                .filter_map(|binding| {
-                    // specify type to assert that error was already reported in Err case:
-                    let predicate: Result<_, ErrorReported> =
-                        self.ast_type_binding_to_poly_projection_predicate(path_id,
-                                                                           poly_trait_ref.clone(),
-                                                                           self_ty,
-                                                                           binding);
-                    predicate.ok() // ok to ignore Err() because ErrorReported (see above)
-                });
-            poly_projections.extend(converted_bindings);
-        }
+        poly_projections.extend(assoc_bindings.iter().filter_map(|binding| {
+            // specify type to assert that error was already reported in Err case:
+            let predicate: Result<_, ErrorReported> =
+                self.ast_type_binding_to_poly_projection_predicate(path_id,
+                                                                   poly_trait_ref,
+                                                                   binding);
+            predicate.ok() // ok to ignore Err() because ErrorReported (see above)
+        }));
 
         debug!("ast_path_to_poly_trait_ref(trait_segment={:?}, projections={:?}) -> {:?}",
                trait_segment, poly_projections, poly_trait_ref);
@@ -834,7 +802,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
                                   span: Span,
                                   param_mode: PathParamMode,
                                   trait_def_id: DefId,
-                                  self_ty: Option<Ty<'tcx>>,
+                                  self_ty: Ty<'tcx>,
                                   trait_segment: &hir::PathSegment)
                                   -> ty::TraitRef<'tcx>
     {
@@ -854,7 +822,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
                                        span: Span,
                                        param_mode: PathParamMode,
                                        trait_def_id: DefId,
-                                       self_ty: Option<Ty<'tcx>>,
+                                       self_ty: Ty<'tcx>,
                                        trait_segment: &hir::PathSegment)
                                        -> (&'tcx Substs<'tcx>, Vec<ConvertedBinding<'tcx>>)
     {
@@ -902,7 +870,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
         let substs = self.create_substs_for_ast_path(span,
                                                      param_mode,
                                                      &trait_def.generics,
-                                                     self_ty,
+                                                     Some(self_ty),
                                                      types,
                                                      regions);
 
@@ -912,8 +880,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
     fn ast_type_binding_to_poly_projection_predicate(
         &self,
         path_id: ast::NodeId,
-        mut trait_ref: ty::PolyTraitRef<'tcx>,
-        self_ty: Option<Ty<'tcx>>,
+        trait_ref: ty::PolyTraitRef<'tcx>,
         binding: &ConvertedBinding<'tcx>)
         -> Result<ty::PolyProjectionPredicate<'tcx>, ErrorReported>
     {
@@ -967,62 +934,39 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
 
         // Simple case: X is defined in the current trait.
         if self.trait_defines_associated_type_named(trait_ref.def_id(), binding.item_name) {
-            return Ok(ty::Binder(ty::ProjectionPredicate {      // <-------------------+
-                projection_ty: ty::ProjectionTy {               //                     |
-                    trait_ref: trait_ref.skip_binder().clone(), // Binder moved here --+
-                    item_name: binding.item_name,
-                },
-                ty: binding.ty,
+            return Ok(trait_ref.map_bound(|trait_ref| {
+                ty::ProjectionPredicate {
+                    projection_ty: ty::ProjectionTy {
+                        trait_ref: trait_ref,
+                        item_name: binding.item_name,
+                    },
+                    ty: binding.ty,
+                }
             }));
         }
 
         // Otherwise, we have to walk through the supertraits to find
-        // those that do.  This is complicated by the fact that, for an
-        // object type, the `Self` type is not present in the
-        // substitutions (after all, it's being constructed right now),
-        // but the `supertraits` iterator really wants one. To handle
-        // this, we currently insert a dummy type and then remove it
-        // later. Yuck.
-
-        let dummy_self_ty = tcx.mk_infer(ty::FreshTy(0));
-        if self_ty.is_none() { // if converting for an object type
-            let mut dummy_substs = trait_ref.skip_binder().substs.clone(); // binder moved here -+
-            assert!(dummy_substs.self_ty().is_none());                     //                    |
-            dummy_substs.types.push(SelfSpace, dummy_self_ty);             //                    |
-            trait_ref = ty::Binder(ty::TraitRef::new(trait_ref.def_id(),   // <------------+
-                                                     tcx.mk_substs(dummy_substs)));
-        }
-
+        // those that do.
         self.ensure_super_predicates(binding.span, trait_ref.def_id())?;
 
-        let mut candidates: Vec<ty::PolyTraitRef> =
+        let candidates: Vec<ty::PolyTraitRef> =
             traits::supertraits(tcx, trait_ref.clone())
             .filter(|r| self.trait_defines_associated_type_named(r.def_id(), binding.item_name))
             .collect();
 
-        // If converting for an object type, then remove the dummy-ty from `Self` now.
-        // Yuckety yuck.
-        if self_ty.is_none() {
-            for candidate in &mut candidates {
-                let mut dummy_substs = candidate.0.substs.clone();
-                assert!(dummy_substs.self_ty() == Some(dummy_self_ty));
-                dummy_substs.types.pop(SelfSpace);
-                *candidate = ty::Binder(ty::TraitRef::new(candidate.def_id(),
-                                                          tcx.mk_substs(dummy_substs)));
-            }
-        }
-
         let candidate = self.one_bound_for_assoc_type(candidates,
                                                       &trait_ref.to_string(),
                                                       &binding.item_name.as_str(),
                                                       binding.span)?;
 
-        Ok(ty::Binder(ty::ProjectionPredicate {             // <-------------------------+
-            projection_ty: ty::ProjectionTy {               //                           |
-                trait_ref: candidate.skip_binder().clone(), // binder is moved up here --+
-                item_name: binding.item_name,
-            },
-            ty: binding.ty,
+        Ok(candidate.map_bound(|trait_ref| {
+            ty::ProjectionPredicate {
+                projection_ty: ty::ProjectionTy {
+                    trait_ref: trait_ref,
+                    item_name: binding.item_name,
+                },
+                ty: binding.ty,
+            }
         }))
     }
 
@@ -1059,11 +1003,12 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
         decl_ty.subst(self.tcx(), &substs)
     }
 
-    fn ast_ty_to_trait_ref(&self,
-                           rscope: &RegionScope,
-                           ty: &hir::Ty,
-                           bounds: &[hir::TyParamBound])
-                           -> Result<TraitAndProjections<'tcx>, ErrorReported>
+    fn ast_ty_to_object_trait_ref(&self,
+                                  rscope: &RegionScope,
+                                  span: Span,
+                                  ty: &hir::Ty,
+                                  bounds: &[hir::TyParamBound])
+                                  -> Ty<'tcx>
     {
         /*!
          * In a type like `Foo + Send`, we want to wait to collect the
@@ -1076,33 +1021,32 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
          * name, and reports an error otherwise.
          */
 
+        let tcx = self.tcx();
         match ty.node {
             hir::TyPath(None, ref path) => {
-                let resolution = self.tcx().expect_resolution(ty.id);
+                let resolution = tcx.expect_resolution(ty.id);
                 match resolution.base_def {
                     Def::Trait(trait_def_id) if resolution.depth == 0 => {
-                        let mut projection_bounds = Vec::new();
-                        let trait_ref =
-                            self.object_path_to_poly_trait_ref(rscope,
-                                                               path.span,
-                                                               PathParamMode::Explicit,
-                                                               trait_def_id,
-                                                               ty.id,
-                                                               path.segments.last().unwrap(),
-                                                               &mut projection_bounds);
-                        Ok((trait_ref, projection_bounds))
+                        self.trait_path_to_object_type(rscope,
+                                                       path.span,
+                                                       PathParamMode::Explicit,
+                                                       trait_def_id,
+                                                       ty.id,
+                                                       path.segments.last().unwrap(),
+                                                       span,
+                                                       partition_bounds(tcx, span, bounds))
                     }
                     _ => {
-                        struct_span_err!(self.tcx().sess, ty.span, E0172,
+                        struct_span_err!(tcx.sess, ty.span, E0172,
                                   "expected a reference to a trait")
                             .span_label(ty.span, &format!("expected a trait"))
                             .emit();
-                        Err(ErrorReported)
+                        tcx.types.err
                     }
                 }
             }
             _ => {
-                let mut err = struct_span_err!(self.tcx().sess, ty.span, E0178,
+                let mut err = struct_span_err!(tcx.sess, ty.span, E0178,
                                                "expected a path on the left-hand side \
                                                 of `+`, not `{}`",
                                                pprust::ty_to_string(ty));
@@ -1141,44 +1085,93 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
                     }
                 }
                 err.emit();
-                Err(ErrorReported)
+                tcx.types.err
             }
         }
     }
 
-    fn trait_ref_to_object_type(&self,
-                                rscope: &RegionScope,
-                                span: Span,
-                                trait_ref: ty::PolyTraitRef<'tcx>,
-                                projection_bounds: Vec<ty::PolyProjectionPredicate<'tcx>>,
-                                bounds: &[hir::TyParamBound])
-                                -> Ty<'tcx>
-    {
-        let existential_bounds = self.conv_existential_bounds(rscope,
-                                                              span,
-                                                              trait_ref.clone(),
-                                                              projection_bounds,
-                                                              bounds);
-
-        let result = self.make_object_type(span, trait_ref, existential_bounds);
-        debug!("trait_ref_to_object_type: result={:?}",
-               result);
-
-        result
+    /// Transform a PolyTraitRef into a PolyExistentialTraitRef by
+    /// removing the dummy Self type (TRAIT_OBJECT_DUMMY_SELF).
+    fn trait_ref_to_existential(&self, trait_ref: ty::TraitRef<'tcx>)
+                                -> ty::ExistentialTraitRef<'tcx> {
+        assert_eq!(trait_ref.self_ty().sty, TRAIT_OBJECT_DUMMY_SELF);
+        ty::ExistentialTraitRef::erase_self_ty(self.tcx(), trait_ref)
     }
 
-    fn make_object_type(&self,
-                        span: Span,
-                        principal: ty::PolyTraitRef<'tcx>,
-                        bounds: ty::ExistentialBounds<'tcx>)
-                        -> Ty<'tcx> {
+    fn trait_path_to_object_type(&self,
+                                 rscope: &RegionScope,
+                                 path_span: Span,
+                                 param_mode: PathParamMode,
+                                 trait_def_id: DefId,
+                                 trait_path_ref_id: ast::NodeId,
+                                 trait_segment: &hir::PathSegment,
+                                 span: Span,
+                                 partitioned_bounds: PartitionedBounds)
+                                 -> Ty<'tcx> {
         let tcx = self.tcx();
-        let object = ty::TraitTy {
-            principal: principal,
-            bounds: bounds
+
+        let mut projection_bounds = vec![];
+        let dummy_self = tcx.mk_ty(TRAIT_OBJECT_DUMMY_SELF);
+        let principal = self.ast_path_to_poly_trait_ref(rscope,
+                                                        path_span,
+                                                        param_mode,
+                                                        trait_def_id,
+                                                        dummy_self,
+                                                        trait_path_ref_id,
+                                                        trait_segment,
+                                                        &mut projection_bounds);
+
+        let PartitionedBounds { builtin_bounds,
+                                trait_bounds,
+                                region_bounds } =
+            partitioned_bounds;
+
+        if !trait_bounds.is_empty() {
+            let b = &trait_bounds[0];
+            let span = b.trait_ref.path.span;
+            struct_span_err!(self.tcx().sess, span, E0225,
+                             "only the builtin traits can be used as closure or object bounds")
+                .span_label(span, &format!("non-builtin trait used as bounds"))
+                .emit();
+        }
+
+        // Erase the dummy_self (TRAIT_OBJECT_DUMMY_SELF) used above.
+        let existential_principal = principal.map_bound(|trait_ref| {
+            self.trait_ref_to_existential(trait_ref)
+        });
+        let existential_projections = projection_bounds.iter().map(|bound| {
+            bound.map_bound(|b| {
+                let p = b.projection_ty;
+                ty::ExistentialProjection {
+                    trait_ref: self.trait_ref_to_existential(p.trait_ref),
+                    item_name: p.item_name,
+                    ty: b.ty
+                }
+            })
+        }).collect();
+
+        let region_bound =
+            self.compute_object_lifetime_bound(span,
+                                               &region_bounds,
+                                               existential_principal,
+                                               builtin_bounds);
+
+        let region_bound = match region_bound {
+            Some(r) => r,
+            None => {
+                match rscope.object_lifetime_default(span) {
+                    Some(r) => r,
+                    None => {
+                        span_err!(self.tcx().sess, span, E0228,
+                                  "the lifetime bound for this object type cannot be deduced \
+                                   from context; please supply an explicit bound");
+                        ty::ReStatic
+                    }
+                }
+            }
         };
-        let object_trait_ref =
-            object.principal_trait_ref_with_self_ty(tcx, tcx.types.err);
+
+        debug!("region_bound: {:?}", region_bound);
 
         // ensure the super predicates and stop if we encountered an error
         if self.ensure_super_predicates(span, principal.def_id()).is_err() {
@@ -1198,7 +1191,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
         }
 
         let mut associated_types: FnvHashSet<(DefId, ast::Name)> =
-            traits::supertraits(tcx, object_trait_ref)
+            traits::supertraits(tcx, principal)
             .flat_map(|tr| {
                 let trait_def = tcx.lookup_trait_def(tr.def_id());
                 trait_def.associated_type_names
@@ -1208,7 +1201,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
             })
             .collect();
 
-        for projection_bound in &object.bounds.projection_bounds {
+        for projection_bound in &projection_bounds {
             let pair = (projection_bound.0.projection_ty.trait_ref.def_id,
                         projection_bound.0.projection_ty.item_name);
             associated_types.remove(&pair);
@@ -1224,7 +1217,14 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
                         .emit();
         }
 
-        tcx.mk_trait(object.principal, object.bounds)
+        let ty = tcx.mk_trait(ty::TraitObject {
+            principal: existential_principal,
+            region_bound: region_bound,
+            builtin_bounds: builtin_bounds,
+            projection_bounds: existential_projections
+        });
+        debug!("trait_object_type: {:?}", ty);
+        ty
     }
 
     fn report_ambiguous_associated_type(&self,
@@ -1458,7 +1458,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
                                                         span,
                                                         param_mode,
                                                         trait_def_id,
-                                                        Some(self_ty),
+                                                        self_ty,
                                                         trait_segment);
 
         debug!("qpath_to_ty: trait_ref={:?}", trait_ref);
@@ -1520,23 +1520,17 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
             Def::Trait(trait_def_id) => {
                 // N.B. this case overlaps somewhat with
                 // TyObjectSum, see that fn for details
-                let mut projection_bounds = Vec::new();
-
-                let trait_ref =
-                    self.object_path_to_poly_trait_ref(rscope,
-                                                       span,
-                                                       param_mode,
-                                                       trait_def_id,
-                                                       base_path_ref_id,
-                                                       base_segments.last().unwrap(),
-                                                       &mut projection_bounds);
 
                 tcx.prohibit_type_params(base_segments.split_last().unwrap().1);
-                self.trait_ref_to_object_type(rscope,
-                                              span,
-                                              trait_ref,
-                                              projection_bounds,
-                                              &[])
+
+                self.trait_path_to_object_type(rscope,
+                                               span,
+                                               param_mode,
+                                               trait_def_id,
+                                               base_path_ref_id,
+                                               base_segments.last().unwrap(),
+                                               span,
+                                               partition_bounds(tcx, span, &[]))
             }
             Def::Enum(did) | Def::TyAlias(did) | Def::Struct(did) => {
                 tcx.prohibit_type_params(base_segments.split_last().unwrap().1);
@@ -1676,18 +1670,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
                 tcx.mk_slice(self.ast_ty_to_ty(rscope, &ty))
             }
             hir::TyObjectSum(ref ty, ref bounds) => {
-                match self.ast_ty_to_trait_ref(rscope, &ty, bounds) {
-                    Ok((trait_ref, projection_bounds)) => {
-                        self.trait_ref_to_object_type(rscope,
-                                                      ast_ty.span,
-                                                      trait_ref,
-                                                      projection_bounds,
-                                                      bounds)
-                    }
-                    Err(ErrorReported) => {
-                        self.tcx().types.err
-                    }
-                }
+                self.ast_ty_to_object_trait_ref(rscope, ast_ty.span, ty, bounds)
             }
             hir::TyPtr(ref mt) => {
                 tcx.mk_ptr(ty::TypeAndMut {
@@ -1764,7 +1747,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
                 tcx.mk_fn_ptr(bare_fn_ty)
             }
             hir::TyPolyTraitRef(ref bounds) => {
-                self.conv_ty_poly_trait_ref(rscope, ast_ty.span, bounds)
+                self.conv_object_ty_poly_trait_ref(rscope, ast_ty.span, bounds)
             }
             hir::TyImplTrait(ref bounds) => {
                 use collect::{compute_bounds, SizedByDefault};
@@ -2091,28 +2074,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
         }
     }
 
-    /// Given an existential type like `Foo+'a+Bar`, this routine converts
-    /// the `'a` and `Bar` intos an `ExistentialBounds` struct.
-    /// The `main_trait_refs` argument specifies the `Foo` -- it is absent
-    /// for closures. Eventually this should all be normalized, I think,
-    /// so that there is no "main trait ref" and instead we just have a flat
-    /// list of bounds as the existential type.
-    fn conv_existential_bounds(&self,
-        rscope: &RegionScope,
-        span: Span,
-        principal_trait_ref: ty::PolyTraitRef<'tcx>,
-        projection_bounds: Vec<ty::PolyProjectionPredicate<'tcx>>,
-        ast_bounds: &[hir::TyParamBound])
-        -> ty::ExistentialBounds<'tcx>
-    {
-        let partitioned_bounds =
-            partition_bounds(self.tcx(), span, ast_bounds);
-
-        self.conv_existential_bounds_from_partitioned_bounds(
-            rscope, span, principal_trait_ref, projection_bounds, partitioned_bounds)
-    }
-
-    fn conv_ty_poly_trait_ref(&self,
+    fn conv_object_ty_poly_trait_ref(&self,
         rscope: &RegionScope,
         span: Span,
         ast_bounds: &[hir::TyParamBound])
@@ -2120,75 +2082,24 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
     {
         let mut partitioned_bounds = partition_bounds(self.tcx(), span, &ast_bounds[..]);
 
-        let mut projection_bounds = Vec::new();
-        let main_trait_bound = if !partitioned_bounds.trait_bounds.is_empty() {
-            let trait_bound = partitioned_bounds.trait_bounds.remove(0);
-            self.instantiate_poly_trait_ref(rscope,
-                                            trait_bound,
-                                            None,
-                                            &mut projection_bounds)
+        let trait_bound = if !partitioned_bounds.trait_bounds.is_empty() {
+            partitioned_bounds.trait_bounds.remove(0)
         } else {
             span_err!(self.tcx().sess, span, E0224,
                       "at least one non-builtin trait is required for an object type");
             return self.tcx().types.err;
         };
 
-        let bounds =
-            self.conv_existential_bounds_from_partitioned_bounds(rscope,
-                                                                 span,
-                                                                 main_trait_bound.clone(),
-                                                                 projection_bounds,
-                                                                 partitioned_bounds);
-
-        self.make_object_type(span, main_trait_bound, bounds)
-    }
-
-    pub fn conv_existential_bounds_from_partitioned_bounds(&self,
-        rscope: &RegionScope,
-        span: Span,
-        principal_trait_ref: ty::PolyTraitRef<'tcx>,
-        projection_bounds: Vec<ty::PolyProjectionPredicate<'tcx>>, // Empty for boxed closures
-        partitioned_bounds: PartitionedBounds)
-        -> ty::ExistentialBounds<'tcx>
-    {
-        let PartitionedBounds { builtin_bounds,
-                                trait_bounds,
-                                region_bounds } =
-            partitioned_bounds;
-
-        if !trait_bounds.is_empty() {
-            let b = &trait_bounds[0];
-            let span = b.trait_ref.path.span;
-            struct_span_err!(self.tcx().sess, span, E0225,
-                             "only the builtin traits can be used as closure or object bounds")
-                .span_label(span, &format!("non-builtin trait used as bounds"))
-                .emit();
-        }
-
-        let region_bound =
-            self.compute_object_lifetime_bound(span,
-                                               &region_bounds,
-                                               principal_trait_ref,
-                                               builtin_bounds);
-
-        let region_bound = match region_bound {
-            Some(r) => r,
-            None => {
-                match rscope.object_lifetime_default(span) {
-                    Some(r) => r,
-                    None => {
-                        span_err!(self.tcx().sess, span, E0228,
-                                  "the lifetime bound for this object type cannot be deduced \
-                                   from context; please supply an explicit bound");
-                        ty::ReStatic
-                    }
-                }
-            }
-        };
-
-        debug!("region_bound: {:?}", region_bound);
-
-        ty::ExistentialBounds::new(region_bound, builtin_bounds, projection_bounds)
+        let trait_ref = &trait_bound.trait_ref;
+        let trait_def_id = self.trait_def_id(trait_ref);
+        self.trait_path_to_object_type(rscope,
+                                       trait_ref.path.span,
+                                       PathParamMode::Explicit,
+                                       trait_def_id,
+                                       trait_ref.ref_id,
+                                       trait_ref.path.segments.last().unwrap(),
+                                       span,
+                                       partitioned_bounds)
     }
 
     /// Given the bounds on an object, determines what single region bound (if any) we can
@@ -2199,7 +2110,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
     fn compute_object_lifetime_bound(&self,
         span: Span,
         explicit_region_bounds: &[&hir::Lifetime],
-        principal_trait_ref: ty::PolyTraitRef<'tcx>,
+        principal_trait_ref: ty::PolyExistentialTraitRef<'tcx>,
         builtin_bounds: ty::BuiltinBounds)
         -> Option<ty::Region> // if None, use the default
     {
@@ -2230,7 +2141,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
         // No explicit region bound specified. Therefore, examine trait
         // bounds and see if we can derive region bounds from those.
         let derived_region_bounds =
-            object_region_bounds(tcx, &principal_trait_ref, builtin_bounds);
+            object_region_bounds(tcx, principal_trait_ref, builtin_bounds);
 
         // If there are no derived region bounds, then report back that we
         // can find no region bound. The caller will use the default.
diff --git a/src/librustc_typeck/check/cast.rs b/src/librustc_typeck/check/cast.rs
index 7a4cc09a7d5..fb78d3a37ca 100644
--- a/src/librustc_typeck/check/cast.rs
+++ b/src/librustc_typeck/check/cast.rs
@@ -78,7 +78,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
     fn unsize_kind(&self, t: Ty<'tcx>) -> Option<UnsizeKind<'tcx>> {
         match t.sty {
             ty::TySlice(_) | ty::TyStr => Some(UnsizeKind::Length),
-            ty::TyTrait(ref tty) => Some(UnsizeKind::Vtable(tty.principal_def_id())),
+            ty::TyTrait(ref tty) => Some(UnsizeKind::Vtable(tty.principal.def_id())),
             ty::TyStruct(def, substs) => {
                 // FIXME(arielb1): do some kind of normalization
                 match def.struct_variant().fields.last() {
diff --git a/src/librustc_typeck/check/closure.rs b/src/librustc_typeck/check/closure.rs
index 3acb8017eec..8a007293e64 100644
--- a/src/librustc_typeck/check/closure.rs
+++ b/src/librustc_typeck/check/closure.rs
@@ -102,12 +102,11 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
 
         match expected_ty.sty {
             ty::TyTrait(ref object_type) => {
-                let proj_bounds = object_type.projection_bounds_with_self_ty(self.tcx,
-                                                                             self.tcx.types.err);
-                let sig = proj_bounds.iter()
-                                     .filter_map(|pb| self.deduce_sig_from_projection(pb))
-                                     .next();
-                let kind = self.tcx.lang_items.fn_trait_kind(object_type.principal_def_id());
+                let sig = object_type.projection_bounds.iter().filter_map(|pb| {
+                    let pb = pb.with_self_ty(self.tcx, self.tcx.types.err);
+                    self.deduce_sig_from_projection(&pb)
+                }).next();
+                let kind = self.tcx.lang_items.fn_trait_kind(object_type.principal.def_id());
                 (sig, kind)
             }
             ty::TyInfer(ty::TyVar(vid)) => {
diff --git a/src/librustc_typeck/check/method/confirm.rs b/src/librustc_typeck/check/method/confirm.rs
index d1d72599555..250bf9265d1 100644
--- a/src/librustc_typeck/check/method/confirm.rs
+++ b/src/librustc_typeck/check/method/confirm.rs
@@ -210,7 +210,7 @@ impl<'a, 'gcx, 'tcx> ConfirmContext<'a, 'gcx, 'tcx> {
 
             probe::ObjectPick => {
                 let trait_def_id = pick.item.container().id();
-                self.extract_trait_ref(self_ty, |this, object_ty, data| {
+                self.extract_existential_trait_ref(self_ty, |this, object_ty, principal| {
                     // The object data has no entry for the Self
                     // Type. For the purposes of this method call, we
                     // substitute the object type itself. This
@@ -222,9 +222,9 @@ impl<'a, 'gcx, 'tcx> ConfirmContext<'a, 'gcx, 'tcx> {
                     // been ruled out when we deemed the trait to be
                     // "object safe".
                     let original_poly_trait_ref =
-                        data.principal_trait_ref_with_self_ty(this.tcx, object_ty);
+                        principal.with_self_ty(this.tcx, object_ty);
                     let upcast_poly_trait_ref =
-                        this.upcast(original_poly_trait_ref.clone(), trait_def_id);
+                        this.upcast(original_poly_trait_ref, trait_def_id);
                     let upcast_trait_ref =
                         this.replace_late_bound_regions_with_fresh_var(&upcast_poly_trait_ref);
                     debug!("original_poly_trait_ref={:?} upcast_trait_ref={:?} target_trait={:?}",
@@ -276,8 +276,12 @@ impl<'a, 'gcx, 'tcx> ConfirmContext<'a, 'gcx, 'tcx> {
         }
     }
 
-    fn extract_trait_ref<R, F>(&mut self, self_ty: Ty<'tcx>, mut closure: F) -> R where
-        F: FnMut(&mut ConfirmContext<'a, 'gcx, 'tcx>, Ty<'tcx>, &ty::TraitTy<'tcx>) -> R,
+    fn extract_existential_trait_ref<R, F>(&mut self,
+                                           self_ty: Ty<'tcx>,
+                                           mut closure: F) -> R
+        where F: FnMut(&mut ConfirmContext<'a, 'gcx, 'tcx>,
+                       Ty<'tcx>,
+                       ty::PolyExistentialTraitRef<'tcx>) -> R,
     {
         // If we specified that this is an object method, then the
         // self-type ought to be something that can be dereferenced to
@@ -288,7 +292,7 @@ impl<'a, 'gcx, 'tcx> ConfirmContext<'a, 'gcx, 'tcx> {
         self.fcx.autoderef(self.span, self_ty)
             .filter_map(|(ty, _)| {
                 match ty.sty {
-                    ty::TyTrait(ref data) => Some(closure(self, ty, &data)),
+                    ty::TyTrait(ref data) => Some(closure(self, ty, data.principal)),
                     _ => None,
                 }
             })
@@ -331,9 +335,7 @@ impl<'a, 'gcx, 'tcx> ConfirmContext<'a, 'gcx, 'tcx> {
         // parameters from the type and those from the method.
         //
         // FIXME -- permit users to manually specify lifetimes
-        let type_defs = method.generics.types.as_full_slice();
-        let region_defs = method.generics.regions.as_full_slice();
-        subst::Substs::from_param_defs(region_defs, type_defs, |def| {
+        subst::Substs::from_generics(&method.generics, |def, _| {
             if def.space != subst::FnSpace {
                 substs.region_for_def(def)
             } else {
diff --git a/src/librustc_typeck/check/method/mod.rs b/src/librustc_typeck/check/method/mod.rs
index 532a5c0de4e..ff34f37bde0 100644
--- a/src/librustc_typeck/check/method/mod.rs
+++ b/src/librustc_typeck/check/method/mod.rs
@@ -189,9 +189,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         assert!(trait_def.generics.regions.is_empty());
 
         // Construct a trait-reference `self_ty : Trait<input_tys>`
-        let type_defs = trait_def.generics.types.as_full_slice();
-        let region_defs = trait_def.generics.regions.as_full_slice();
-        let substs = subst::Substs::from_param_defs(region_defs, type_defs, |def| {
+        let substs = subst::Substs::from_generics(&trait_def.generics, |def, _| {
             self.region_var_for_def(span, def)
         }, |def, substs| {
             if def.space == subst::SelfSpace {
diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs
index 44e371482c5..f6ac3235cf3 100644
--- a/src/librustc_typeck/check/method/probe.rs
+++ b/src/librustc_typeck/check/method/probe.rs
@@ -290,8 +290,8 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
 
         match self_ty.sty {
             ty::TyTrait(box ref data) => {
-                self.assemble_inherent_candidates_from_object(self_ty, data);
-                self.assemble_inherent_impl_candidates_for_type(data.principal_def_id());
+                self.assemble_inherent_candidates_from_object(self_ty, data.principal);
+                self.assemble_inherent_impl_candidates_for_type(data.principal.def_id());
             }
             ty::TyEnum(def, _) |
             ty::TyStruct(def, _) => {
@@ -445,7 +445,7 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
 
     fn assemble_inherent_candidates_from_object(&mut self,
                                                 self_ty: Ty<'tcx>,
-                                                data: &ty::TraitTy<'tcx>) {
+                                                principal: ty::PolyExistentialTraitRef<'tcx>) {
         debug!("assemble_inherent_candidates_from_object(self_ty={:?})",
                self_ty);
 
@@ -456,7 +456,7 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
         // a substitution that replaces `Self` with the object type
         // itself. Hence, a `&self` method will wind up with an
         // argument type like `&Trait`.
-        let trait_ref = data.principal_trait_ref_with_self_ty(self.tcx, self_ty);
+        let trait_ref = principal.with_self_ty(self.tcx, self_ty);
         self.elaborate_bounds(&[trait_ref], |this, new_trait_ref, item| {
             let new_trait_ref = this.erase_late_bound_regions(&new_trait_ref);
 
@@ -1227,15 +1227,16 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
             return impl_ty;
         }
 
-        let placeholder;
-        let mut substs = substs;
-        if
-            !method.generics.types.is_empty_in(subst::FnSpace) ||
-            !method.generics.regions.is_empty_in(subst::FnSpace)
-        {
-            let type_defs = method.generics.types.as_full_slice();
-            let region_defs = method.generics.regions.as_full_slice();
-            placeholder = subst::Substs::from_param_defs(region_defs, type_defs, |def| {
+        // Erase any late-bound regions from the method and substitute
+        // in the values from the substitution.
+        let xform_self_ty = method.fty.sig.input(0);
+        let xform_self_ty = self.erase_late_bound_regions(&xform_self_ty);
+
+        if method.generics.types.is_empty_in(subst::FnSpace) &&
+           method.generics.regions.is_empty_in(subst::FnSpace) {
+            xform_self_ty.subst(self.tcx, substs)
+        } else {
+            let substs = subst::Substs::from_generics(&method.generics, |def, _| {
                 if def.space != subst::FnSpace {
                     substs.region_for_def(def)
                 } else {
@@ -1250,16 +1251,8 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
                     self.type_var_for_def(self.span, def, cur_substs)
                 }
             });
-            substs = &placeholder;
+            xform_self_ty.subst(self.tcx, &substs)
         }
-
-        // Erase any late-bound regions from the method and substitute
-        // in the values from the substitution.
-        let xform_self_ty = method.fty.sig.input(0);
-        let xform_self_ty = self.erase_late_bound_regions(&xform_self_ty);
-        let xform_self_ty = xform_self_ty.subst(self.tcx, substs);
-
-        xform_self_ty
     }
 
     /// Get the type of an impl and generate substitutions with placeholders.
diff --git a/src/librustc_typeck/check/method/suggest.rs b/src/librustc_typeck/check/method/suggest.rs
index 54521782474..dc6fa334b74 100644
--- a/src/librustc_typeck/check/method/suggest.rs
+++ b/src/librustc_typeck/check/method/suggest.rs
@@ -358,7 +358,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
             match ty.sty {
                 ty::TyEnum(def, _) | ty::TyStruct(def, _) => def.did.is_local(),
 
-                ty::TyTrait(ref tr) => tr.principal_def_id().is_local(),
+                ty::TyTrait(ref tr) => tr.principal.def_id().is_local(),
 
                 ty::TyParam(_) => true,
 
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index 6f3d48282e2..8e34b0b8c55 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -824,11 +824,11 @@ impl<'a, 'gcx, 'tcx> RegionCtxt<'a, 'gcx, 'tcx> {
             }
 
             /*From:*/ (_,
-            /*To:  */  &ty::TyTrait(box ty::TraitTy { ref bounds, .. })) => {
+            /*To:  */  &ty::TyTrait(ref obj)) => {
                 // When T is existentially quantified as a trait
                 // `Foo+'to`, it must outlive the region bound `'to`.
                 self.type_must_outlive(infer::RelateObjectBound(cast_expr.span),
-                                       from_ty, bounds.region_bound);
+                                       from_ty, obj.region_bound);
             }
 
             /*From:*/ (&ty::TyBox(from_referent_ty),
diff --git a/src/librustc_typeck/coherence/mod.rs b/src/librustc_typeck/coherence/mod.rs
index 9b26e95f7fa..485e744bf91 100644
--- a/src/librustc_typeck/coherence/mod.rs
+++ b/src/librustc_typeck/coherence/mod.rs
@@ -75,7 +75,7 @@ impl<'a, 'gcx, 'tcx> CoherenceChecker<'a, 'gcx, 'tcx> {
             }
 
             TyTrait(ref t) => {
-                Some(t.principal_def_id())
+                Some(t.principal.def_id())
             }
 
             TyBox(_) => {
diff --git a/src/librustc_typeck/coherence/orphan.rs b/src/librustc_typeck/coherence/orphan.rs
index e426f0cb643..97aed4d5e82 100644
--- a/src/librustc_typeck/coherence/orphan.rs
+++ b/src/librustc_typeck/coherence/orphan.rs
@@ -80,7 +80,7 @@ impl<'cx, 'tcx> OrphanChecker<'cx, 'tcx> {
                         self.check_def_id(item, def.did);
                     }
                     ty::TyTrait(ref data) => {
-                        self.check_def_id(item, data.principal_def_id());
+                        self.check_def_id(item, data.principal.def_id());
                     }
                     ty::TyBox(..) => {
                         match self.tcx.lang_items.require_owned_box() {
diff --git a/src/librustc_typeck/coherence/overlap.rs b/src/librustc_typeck/coherence/overlap.rs
index 46a9ef8d5ba..f60fb9583a6 100644
--- a/src/librustc_typeck/coherence/overlap.rs
+++ b/src/librustc_typeck/coherence/overlap.rs
@@ -168,14 +168,14 @@ impl<'cx, 'tcx,'v> intravisit::Visitor<'v> for OverlapChecker<'cx, 'tcx> {
                     // This is something like impl Trait1 for Trait2. Illegal
                     // if Trait1 is a supertrait of Trait2 or Trait2 is not object safe.
 
-                    if !self.tcx.is_object_safe(data.principal_def_id()) {
+                    if !self.tcx.is_object_safe(data.principal.def_id()) {
                         // This is an error, but it will be
                         // reported by wfcheck.  Ignore it
                         // here. This is tested by
                         // `coherence-impl-trait-for-trait-object-safe.rs`.
                     } else {
                         let mut supertrait_def_ids =
-                            traits::supertrait_def_ids(self.tcx, data.principal_def_id());
+                            traits::supertrait_def_ids(self.tcx, data.principal.def_id());
                         if supertrait_def_ids.any(|d| d == trait_def_id) {
                             span_err!(self.tcx.sess, item.span, E0371,
                                       "the object type `{}` automatically \
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index 0ddc051d4a8..a2a162a7f5f 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -722,7 +722,7 @@ fn convert_item(ccx: &CrateCtxt, it: &hir::Item) {
                 AstConv::instantiate_mono_trait_ref(&ccx.icx(&()),
                                                     &ExplicitRscope,
                                                     ast_trait_ref,
-                                                    None);
+                                                    tcx.mk_self_type());
 
             tcx.record_trait_has_default_impl(trait_ref.def_id);
 
@@ -752,7 +752,7 @@ fn convert_item(ccx: &CrateCtxt, it: &hir::Item) {
                 AstConv::instantiate_mono_trait_ref(&ccx.icx(&ty_predicates),
                                                     &ExplicitRscope,
                                                     ast_trait_ref,
-                                                    Some(selfty))
+                                                    selfty)
             });
             tcx.impl_trait_refs.borrow_mut().insert(def_id, trait_ref);
 
@@ -1815,10 +1815,12 @@ fn ty_generic_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
                             let mut projections = Vec::new();
 
                             let trait_ref =
-                                conv_poly_trait_ref(&ccx.icx(&(base_predicates, ast_generics)),
-                                                    ty,
-                                                    poly_trait_ref,
-                                                    &mut projections);
+                                AstConv::instantiate_poly_trait_ref(&ccx.icx(&(base_predicates,
+                                                                               ast_generics)),
+                                                                    &ExplicitRscope,
+                                                                    poly_trait_ref,
+                                                                    ty,
+                                                                    &mut projections);
 
                             result.predicates.push(trait_ref.to_predicate());
 
@@ -2069,7 +2071,7 @@ pub fn compute_bounds<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, 'tcx>,
     let mut trait_bounds: Vec<_> = trait_bounds.iter().map(|&bound| {
         astconv.instantiate_poly_trait_ref(&rscope,
                                            bound,
-                                           Some(param_ty),
+                                           param_ty,
                                            &mut projection_bounds)
     }).collect();
 
@@ -2100,7 +2102,10 @@ fn predicates_from_bound<'tcx>(astconv: &AstConv<'tcx, 'tcx>,
     match *bound {
         hir::TraitTyParamBound(ref tr, hir::TraitBoundModifier::None) => {
             let mut projections = Vec::new();
-            let pred = conv_poly_trait_ref(astconv, param_ty, tr, &mut projections);
+            let pred = astconv.instantiate_poly_trait_ref(&ExplicitRscope,
+                                                          tr,
+                                                          param_ty,
+                                                          &mut projections);
             projections.into_iter()
                        .map(|p| p.to_predicate())
                        .chain(Some(pred.to_predicate()))
@@ -2117,19 +2122,6 @@ fn predicates_from_bound<'tcx>(astconv: &AstConv<'tcx, 'tcx>,
     }
 }
 
-fn conv_poly_trait_ref<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, 'tcx>,
-                                         param_ty: Ty<'tcx>,
-                                         trait_ref: &hir::PolyTraitRef,
-                                         projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
-                                         -> ty::PolyTraitRef<'tcx>
-{
-    AstConv::instantiate_poly_trait_ref(astconv,
-                                        &ExplicitRscope,
-                                        trait_ref,
-                                        Some(param_ty),
-                                        projections)
-}
-
 fn compute_type_scheme_of_foreign_fn_decl<'a, 'tcx>(
     ccx: &CrateCtxt<'a, 'tcx>,
     id: DefId,
diff --git a/src/librustc_typeck/variance/constraints.rs b/src/librustc_typeck/variance/constraints.rs
index 50c568cfef8..6e6f9ce65c5 100644
--- a/src/librustc_typeck/variance/constraints.rs
+++ b/src/librustc_typeck/variance/constraints.rs
@@ -396,19 +396,16 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
 
             ty::TyTrait(ref data) => {
                 let poly_trait_ref =
-                    data.principal_trait_ref_with_self_ty(self.tcx(),
-                                                          self.tcx().types.err);
+                    data.principal.with_self_ty(self.tcx(), self.tcx().types.err);
 
                 // The type `Foo<T+'a>` is contravariant w/r/t `'a`:
                 let contra = self.contravariant(variance);
-                self.add_constraints_from_region(generics, data.bounds.region_bound, contra);
+                self.add_constraints_from_region(generics, data.region_bound, contra);
 
                 // Ignore the SelfSpace, it is erased.
                 self.add_constraints_from_trait_ref(generics, poly_trait_ref.0, variance);
 
-                let projections = data.projection_bounds_with_self_ty(self.tcx(),
-                                                                      self.tcx().types.err);
-                for projection in &projections {
+                for projection in &data.projection_bounds {
                     self.add_constraints_from_ty(generics, projection.0.ty, self.invariant);
                 }
             }
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index 284e0d4dbdd..ffe5b9aad2f 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -630,26 +630,6 @@ impl Clean<TyParamBound> for hir::TyParamBound {
     }
 }
 
-impl<'tcx> Clean<(Vec<TyParamBound>, Vec<TypeBinding>)> for ty::ExistentialBounds<'tcx> {
-    fn clean(&self, cx: &DocContext) -> (Vec<TyParamBound>, Vec<TypeBinding>) {
-        let mut tp_bounds = vec![];
-        self.region_bound.clean(cx).map(|b| tp_bounds.push(RegionBound(b)));
-        for bb in &self.builtin_bounds {
-            tp_bounds.push(bb.clean(cx));
-        }
-
-        let mut bindings = vec![];
-        for &ty::Binder(ref pb) in &self.projection_bounds {
-            bindings.push(TypeBinding {
-                name: pb.projection_ty.item_name.clean(cx),
-                ty: pb.ty.clean(cx)
-            });
-        }
-
-        (tp_bounds, bindings)
-    }
-}
-
 fn external_path_params(cx: &DocContext, trait_did: Option<DefId>,
                         bindings: Vec<TypeBinding>, substs: &subst::Substs) -> PathParameters {
     let lifetimes = substs.regions.get_slice(subst::TypeSpace)
@@ -1848,12 +1828,26 @@ impl<'tcx> Clean<Type> for ty::Ty<'tcx> {
                     is_generic: false,
                 }
             }
-            ty::TyTrait(box ty::TraitTy { ref principal, ref bounds }) => {
-                let did = principal.def_id();
+            ty::TyTrait(ref obj) => {
+                let did = obj.principal.def_id();
                 inline::record_extern_fqn(cx, did, TypeTrait);
-                let (typarams, bindings) = bounds.clean(cx);
+
+                let mut typarams = vec![];
+                obj.region_bound.clean(cx).map(|b| typarams.push(RegionBound(b)));
+                for bb in &obj.builtin_bounds {
+                    typarams.push(bb.clean(cx));
+                }
+
+                let mut bindings = vec![];
+                for &ty::Binder(ref pb) in &obj.projection_bounds {
+                    bindings.push(TypeBinding {
+                        name: pb.item_name.clean(cx),
+                        ty: pb.ty.clean(cx)
+                    });
+                }
+
                 let path = external_path(cx, &cx.tcx().item_name(did).as_str(),
-                                         Some(did), bindings, principal.substs());
+                                         Some(did), bindings, obj.principal.0.substs);
                 ResolvedPath {
                     path: path,
                     typarams: Some(typarams),