rustc: use Vec<Kind> in Substs, where Kind is a &TyS | &Region tagged pointer.

57 files changed, 532 insertions, 409 deletions

diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index 48ea953cc1e..1e4b2e9116f 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -27,6 +27,7 @@
 #![feature(box_patterns)]
 #![feature(box_syntax)]
 #![feature(collections)]
+#![feature(conservative_impl_trait)]
 #![feature(const_fn)]
 #![feature(core_intrinsics)]
 #![feature(enumset)]
diff --git a/src/librustc/middle/cstore.rs b/src/librustc/middle/cstore.rs
index 381a86a42d4..b33bc520fe2 100644
--- a/src/librustc/middle/cstore.rs
+++ b/src/librustc/middle/cstore.rs
@@ -149,7 +149,7 @@ pub trait CrateStore<'tcx> {
     fn closure_kind(&self, def_id: DefId) -> ty::ClosureKind;
     fn closure_ty<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId)
                       -> ty::ClosureTy<'tcx>;
-    fn item_variances(&self, def: DefId) -> ty::ItemVariances;
+    fn item_variances(&self, def: DefId) -> Vec<ty::Variance>;
     fn repr_attrs(&self, def: DefId) -> Vec<attr::ReprAttr>;
     fn item_type<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, def: DefId)
                      -> Ty<'tcx>;
@@ -328,7 +328,7 @@ impl<'tcx> CrateStore<'tcx> for DummyCrateStore {
     fn closure_kind(&self, def_id: DefId) -> ty::ClosureKind  { bug!("closure_kind") }
     fn closure_ty<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId)
                       -> ty::ClosureTy<'tcx>  { bug!("closure_ty") }
-    fn item_variances(&self, def: DefId) -> ty::ItemVariances { bug!("item_variances") }
+    fn item_variances(&self, def: DefId) -> Vec<ty::Variance> { bug!("item_variances") }
     fn repr_attrs(&self, def: DefId) -> Vec<attr::ReprAttr> { bug!("repr_attrs") }
     fn item_type<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, def: DefId)
                      -> Ty<'tcx> { bug!("item_type") }
diff --git a/src/librustc/middle/resolve_lifetime.rs b/src/librustc/middle/resolve_lifetime.rs
index 8369a6c39d5..ebe40500221 100644
--- a/src/librustc/middle/resolve_lifetime.rs
+++ b/src/librustc/middle/resolve_lifetime.rs
@@ -89,9 +89,12 @@ struct LifetimeContext<'a, 'tcx: 'a> {
 
 #[derive(PartialEq, Debug)]
 enum ScopeChain<'a> {
-    /// EarlyScope(['a, 'b, ...], s) extends s with early-bound
-    /// lifetimes.
-    EarlyScope(&'a [hir::LifetimeDef], Scope<'a>),
+    /// EarlyScope(['a, 'b, ...], start, s) extends s with early-bound
+    /// lifetimes, with consecutive parameter indices from `start`.
+    /// That is, 'a has index `start`, 'b has index `start + 1`, etc.
+    /// Indices before `start` correspond to other generic parameters
+    /// of a parent item (trait/impl of a method), or `Self` in traits.
+    EarlyScope(&'a [hir::LifetimeDef], u32, Scope<'a>),
     /// LateScope(['a, 'b, ...], s) extends s with late-bound
     /// lifetimes introduced by the declaration binder_id.
     LateScope(&'a [hir::LifetimeDef], Scope<'a>),
@@ -157,7 +160,12 @@ impl<'a, 'tcx, 'v> Visitor<'v> for LifetimeContext<'a, 'tcx> {
                 hir::ItemImpl(_, _, ref generics, _, _, _) => {
                     // These kinds of items have only early bound lifetime parameters.
                     let lifetimes = &generics.lifetimes;
-                    this.with(EarlyScope(lifetimes, &ROOT_SCOPE), |old_scope, this| {
+                    let start = if let hir::ItemTrait(..) = item.node {
+                        1 // Self comes before lifetimes
+                    } else {
+                        0
+                    };
+                    this.with(EarlyScope(lifetimes, start, &ROOT_SCOPE), |old_scope, this| {
                         this.check_lifetime_defs(old_scope, lifetimes);
                         intravisit::walk_item(this, item);
                     });
@@ -461,7 +469,7 @@ fn extract_labels(ctxt: &mut LifetimeContext, b: &hir::Block) {
                 FnScope { s, .. } => { scope = s; }
                 RootScope => { return; }
 
-                EarlyScope(lifetimes, s) |
+                EarlyScope(lifetimes, _, s) |
                 LateScope(lifetimes, s) => {
                     for lifetime_def in lifetimes {
                         // FIXME (#24278): non-hygienic comparison
@@ -566,8 +574,24 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                     .cloned()
                     .partition(|l| self.map.late_bound.contains_key(&l.lifetime.id));
 
+        // Find the start of nested early scopes, e.g. in methods.
+        let mut start = 0;
+        if let EarlyScope(..) = *self.scope {
+            let parent = self.hir_map.expect_item(self.hir_map.get_parent(fn_id));
+            if let hir::ItemTrait(..) = parent.node {
+                start += 1; // Self comes first.
+            }
+            match parent.node {
+                hir::ItemTrait(_, ref generics, _, _) |
+                hir::ItemImpl(_, _, ref generics, _, _, _) => {
+                    start += generics.lifetimes.len() + generics.ty_params.len();
+                }
+                _ => {}
+            }
+        }
+
         let this = self;
-        this.with(EarlyScope(&early, this.scope), move |old_scope, this| {
+        this.with(EarlyScope(&early, start as u32, this.scope), move |old_scope, this| {
             this.with(LateScope(&late, this.scope), move |_, this| {
                 this.check_lifetime_defs(old_scope, &generics.lifetimes);
                 walk(this);
@@ -597,19 +621,11 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                     break;
                 }
 
-                EarlyScope(lifetimes, s) => {
+                EarlyScope(lifetimes, start, s) => {
                     match search_lifetimes(lifetimes, lifetime_ref) {
-                        Some((mut index, lifetime_def)) => {
-                            // Adjust for nested early scopes, e.g. in methods.
-                            let mut parent = s;
-                            while let EarlyScope(lifetimes, s) = *parent {
-                                index += lifetimes.len() as u32;
-                                parent = s;
-                            }
-                            assert_eq!(*parent, RootScope);
-
+                        Some((index, lifetime_def)) => {
                             let decl_id = lifetime_def.id;
-                            let def = DefEarlyBoundRegion(index, decl_id);
+                            let def = DefEarlyBoundRegion(start + index, decl_id);
                             self.insert_lifetime(lifetime_ref, def);
                             return;
                         }
@@ -671,7 +687,7 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                     break;
                 }
 
-                EarlyScope(lifetimes, s) |
+                EarlyScope(lifetimes, _, s) |
                 LateScope(lifetimes, s) => {
                     search_result = search_lifetimes(lifetimes, lifetime_ref);
                     if search_result.is_some() {
@@ -767,7 +783,7 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                     return;
                 }
 
-                EarlyScope(lifetimes, s) |
+                EarlyScope(lifetimes, _, s) |
                 LateScope(lifetimes, s) => {
                     if let Some((_, lifetime_def)) = search_lifetimes(lifetimes, lifetime) {
                         signal_shadowing_problem(
diff --git a/src/librustc/traits/fulfill.rs b/src/librustc/traits/fulfill.rs
index a0e25d54a13..6598aacc1d3 100644
--- a/src/librustc/traits/fulfill.rs
+++ b/src/librustc/traits/fulfill.rs
@@ -162,7 +162,7 @@ impl<'a, 'gcx, 'tcx> DeferredObligation<'tcx> {
                 let concrete_ty = ty_scheme.ty.subst(tcx, substs);
                 let predicate = ty::TraitRef {
                     def_id: self.predicate.def_id(),
-                    substs: Substs::new_trait(tcx, vec![], vec![], concrete_ty)
+                    substs: Substs::new_trait(tcx, concrete_ty, &[])
                 }.to_predicate();
 
                 let original_obligation = Obligation::new(self.cause.clone(),
@@ -440,7 +440,7 @@ fn trait_ref_type_vars<'a, 'gcx, 'tcx>(selcx: &mut SelectionContext<'a, 'gcx, 't
 {
     t.skip_binder() // ok b/c this check doesn't care about regions
      .input_types()
-     .map(|t| selcx.infcx().resolve_type_vars_if_possible(t))
+     .map(|t| selcx.infcx().resolve_type_vars_if_possible(&t))
      .filter(|t| t.has_infer_types())
      .flat_map(|t| t.walk())
      .filter(|t| match t.sty { ty::TyInfer(_) => true, _ => false })
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index 8adf6e19f39..b015de79be5 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -36,7 +36,7 @@ use super::util;
 use hir::def_id::DefId;
 use infer;
 use infer::{InferCtxt, InferOk, TypeFreshener, TypeOrigin};
-use ty::subst::{Subst, Substs};
+use ty::subst::{Kind, Subst, Substs};
 use ty::{self, ToPredicate, ToPolyTraitRef, Ty, TyCtxt, TypeFoldable};
 use traits;
 use ty::fast_reject;
@@ -1933,7 +1933,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
 
             // for `PhantomData<T>`, we pass `T`
             ty::TyStruct(def, substs) if def.is_phantom_data() => {
-                substs.types().cloned().collect()
+                substs.types().collect()
             }
 
             ty::TyStruct(def, substs) | ty::TyEnum(def, substs) => {
@@ -1982,7 +1982,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                                                   trait_def_id,
                                                   recursion_depth,
                                                   normalized_ty,
-                                                  vec![]);
+                                                  &[]);
                 obligations.push(skol_obligation);
                 this.infcx().plug_leaks(skol_map, snapshot, &obligations)
             })
@@ -2180,8 +2180,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 let input_types = data.principal.input_types();
                 let assoc_types = data.projection_bounds.iter()
                                       .map(|pb| pb.skip_binder().ty);
-                let all_types: Vec<_> = input_types.cloned()
-                                                   .chain(assoc_types)
+                let all_types: Vec<_> = input_types.chain(assoc_types)
                                                    .collect();
 
                 // reintroduce the two binding levels we skipped, then flatten into one
@@ -2598,14 +2597,14 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 // TyError and ensure they do not affect any other fields.
                 // This could be checked after type collection for any struct
                 // with a potentially unsized trailing field.
-                let types = substs_a.types().enumerate().map(|(i, ty)| {
+                let params = substs_a.params().iter().enumerate().map(|(i, &k)| {
                     if ty_params.contains(i) {
-                        tcx.types.err
+                        Kind::from(tcx.types.err)
                     } else {
-                        ty
+                        k
                     }
-                }).collect();
-                let substs = Substs::new(tcx, types, substs_a.regions().cloned().collect());
+                });
+                let substs = Substs::new(tcx, params);
                 for &ty in fields.split_last().unwrap().1 {
                     if ty.subst(tcx, substs).references_error() {
                         return Err(Unimplemented);
@@ -2618,15 +2617,14 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
 
                 // Check that the source structure with the target's
                 // type parameters is a subtype of the target.
-                let types = substs_a.types().enumerate().map(|(i, ty)| {
+                let params = substs_a.params().iter().enumerate().map(|(i, &k)| {
                     if ty_params.contains(i) {
-                        substs_b.type_at(i)
+                        Kind::from(substs_b.type_at(i))
                     } else {
-                        ty
+                        k
                     }
-                }).collect();
-                let substs = Substs::new(tcx, types, substs_a.regions().cloned().collect());
-                let new_struct = tcx.mk_struct(def, substs);
+                });
+                let new_struct = tcx.mk_struct(def, Substs::new(tcx, params));
                 let origin = TypeOrigin::Misc(obligation.cause.span);
                 let InferOk { obligations, .. } =
                     self.infcx.sub_types(false, origin, new_struct, target)
@@ -2639,7 +2637,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                     obligation.predicate.def_id(),
                     obligation.recursion_depth + 1,
                     inner_source,
-                    vec![inner_target]));
+                    &[inner_target]));
             }
 
             _ => bug!()
@@ -2753,7 +2751,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
 
         obligation.predicate.skip_binder().input_types()
             .zip(impl_trait_ref.input_types())
-            .any(|(&obligation_ty, &impl_ty)| {
+            .any(|(obligation_ty, impl_ty)| {
                 let simplified_obligation_ty =
                     fast_reject::simplify_type(self.tcx(), obligation_ty, true);
                 let simplified_impl_ty =
diff --git a/src/librustc/traits/util.rs b/src/librustc/traits/util.rs
index 1954ce1993c..038de25312d 100644
--- a/src/librustc/traits/util.rs
+++ b/src/librustc/traits/util.rs
@@ -386,7 +386,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
             Ok(def_id) => {
                 Ok(ty::TraitRef {
                     def_id: def_id,
-                    substs: Substs::new_trait(self, vec![], vec![], param_ty)
+                    substs: Substs::new_trait(self, param_ty, &[])
                 })
             }
             Err(e) => {
@@ -401,12 +401,12 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         trait_def_id: DefId,
         recursion_depth: usize,
         param_ty: Ty<'tcx>,
-        ty_params: Vec<Ty<'tcx>>)
+        ty_params: &[Ty<'tcx>])
         -> PredicateObligation<'tcx>
     {
         let trait_ref = ty::TraitRef {
             def_id: trait_def_id,
-            substs: Substs::new_trait(self, ty_params, vec![], param_ty)
+            substs: Substs::new_trait(self, param_ty, ty_params)
         };
         predicate_for_trait_ref(cause, trait_ref, recursion_depth)
     }
@@ -496,7 +496,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         };
         let trait_ref = ty::TraitRef {
             def_id: fn_trait_def_id,
-            substs: Substs::new_trait(self, vec![arguments_tuple], vec![], self_ty),
+            substs: Substs::new_trait(self, self_ty, &[arguments_tuple]),
         };
         ty::Binder((trait_ref, sig.0.output))
     }
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index e4e69c395a6..e048e618e84 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -1152,7 +1152,7 @@ fn keep_local<'tcx, T: ty::TypeFoldable<'tcx>>(x: &T) -> bool {
 impl_interners!('tcx,
     type_list: mk_type_list(Vec<Ty<'tcx>>, keep_local) -> [Ty<'tcx>],
     substs: mk_substs(Substs<'tcx>, |substs: &Substs| {
-        substs.types().any(keep_local) || substs.regions().any(keep_local)
+        substs.params().iter().any(keep_local)
     }) -> Substs<'tcx>,
     bare_fn: mk_bare_fn(BareFnTy<'tcx>, |fty: &BareFnTy| {
         keep_local(&fty.sig)
diff --git a/src/librustc/ty/flags.rs b/src/librustc/ty/flags.rs
index 20235cf6d79..1afd49ab47f 100644
--- a/src/librustc/ty/flags.rs
+++ b/src/librustc/ty/flags.rs
@@ -208,11 +208,11 @@ impl FlagComputation {
     }
 
     fn add_substs(&mut self, substs: &Substs) {
-        for &ty in substs.types() {
+        for ty in substs.types() {
             self.add_ty(ty);
         }
 
-        for &r in substs.regions() {
+        for r in substs.regions() {
             self.add_region(r);
         }
     }
diff --git a/src/librustc/ty/maps.rs b/src/librustc/ty/maps.rs
index d5686906e6a..0e8bea86178 100644
--- a/src/librustc/ty/maps.rs
+++ b/src/librustc/ty/maps.rs
@@ -38,7 +38,7 @@ dep_map_ty! { TraitItemDefIds: TraitItemDefIds(DefId) -> Rc<Vec<ty::ImplOrTraitI
 dep_map_ty! { ImplTraitRefs: ItemSignature(DefId) -> Option<ty::TraitRef<'tcx>> }
 dep_map_ty! { TraitDefs: ItemSignature(DefId) -> &'tcx ty::TraitDef<'tcx> }
 dep_map_ty! { AdtDefs: ItemSignature(DefId) -> ty::AdtDefMaster<'tcx> }
-dep_map_ty! { ItemVariances: ItemSignature(DefId) -> Rc<ty::ItemVariances> }
+dep_map_ty! { ItemVariances: ItemSignature(DefId) -> Rc<Vec<ty::Variance>> }
 dep_map_ty! { InherentImpls: InherentImpls(DefId) -> Rc<Vec<DefId>> }
 dep_map_ty! { ImplItems: ImplItems(DefId) -> Vec<ty::ImplOrTraitItemId> }
 dep_map_ty! { TraitItems: TraitItems(DefId) -> Rc<Vec<ty::ImplOrTraitItem<'tcx>>> }
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 3079deff1b6..759dc300372 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -417,21 +417,6 @@ pub struct AssociatedType<'tcx> {
     pub container: ImplOrTraitItemContainer,
 }
 
-#[derive(Clone, PartialEq, RustcDecodable, RustcEncodable)]
-pub struct ItemVariances {
-    pub types: Vec<Variance>,
-    pub regions: Vec<Variance>,
-}
-
-impl ItemVariances {
-    pub fn empty() -> ItemVariances {
-        ItemVariances {
-            types: vec![],
-            regions: vec![],
-        }
-    }
-}
-
 #[derive(Clone, PartialEq, RustcDecodable, RustcEncodable, Copy)]
 pub enum Variance {
     Covariant,      // T<A> <: T<B> iff A <: B -- e.g., function return type
@@ -755,6 +740,20 @@ pub struct Generics<'tcx> {
     pub has_self: bool,
 }
 
+impl<'tcx> Generics<'tcx> {
+    pub fn parent_count(&self) -> usize {
+        self.parent_regions as usize + self.parent_types as usize
+    }
+
+    pub fn own_count(&self) -> usize {
+        self.regions.len() + self.types.len()
+    }
+
+    pub fn count(&self) -> usize {
+        self.parent_count() + self.own_count()
+    }
+}
+
 /// Bounds on generics.
 #[derive(Clone)]
 pub struct GenericPredicates<'tcx> {
@@ -963,7 +962,7 @@ impl<'tcx> TraitPredicate<'tcx> {
         DepNode::TraitSelect(self.def_id(), def_ids)
     }
 
-    pub fn input_types(&self) -> slice::Iter<Ty<'tcx>> {
+    pub fn input_types<'a>(&'a self) -> impl DoubleEndedIterator<Item=Ty<'tcx>> + 'a {
         self.trait_ref.input_types()
     }
 
@@ -1107,7 +1106,7 @@ impl<'tcx> Predicate<'tcx> {
     pub fn walk_tys(&self) -> IntoIter<Ty<'tcx>> {
         let vec: Vec<_> = match *self {
             ty::Predicate::Trait(ref data) => {
-                data.skip_binder().input_types().cloned().collect()
+                data.skip_binder().input_types().collect()
             }
             ty::Predicate::Rfc1592(ref data) => {
                 return data.walk_tys()
@@ -1123,9 +1122,7 @@ impl<'tcx> Predicate<'tcx> {
             }
             ty::Predicate::Projection(ref data) => {
                 let trait_inputs = data.0.projection_ty.trait_ref.input_types();
-                trait_inputs.cloned()
-                            .chain(Some(data.0.ty))
-                            .collect()
+                trait_inputs.chain(Some(data.0.ty)).collect()
             }
             ty::Predicate::WellFormed(data) => {
                 vec![data]
@@ -1208,7 +1205,7 @@ impl<'tcx> TraitRef<'tcx> {
         self.substs.type_at(0)
     }
 
-    pub fn input_types(&self) -> slice::Iter<Ty<'tcx>> {
+    pub fn input_types<'a>(&'a self) -> impl DoubleEndedIterator<Item=Ty<'tcx>> + 'a {
         // 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
@@ -1865,7 +1862,7 @@ impl<'a, 'tcx> AdtDefData<'tcx, 'tcx> {
                 };
                 let sized_predicate = Binder(TraitRef {
                     def_id: sized_trait,
-                    substs: Substs::new_trait(tcx, vec![], vec![], ty)
+                    substs: Substs::new_trait(tcx, ty, &[])
                 }).to_predicate();
                 let predicates = tcx.lookup_predicates(self.did).predicates;
                 if predicates.into_iter().any(|p| p == sized_predicate) {
@@ -2592,7 +2589,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
             || self.lookup_repr_hints(did).contains(&attr::ReprSimd)
     }
 
-    pub fn item_variances(self, item_id: DefId) -> Rc<ItemVariances> {
+    pub fn item_variances(self, item_id: DefId) -> Rc<Vec<ty::Variance>> {
         lookup_locally_or_in_crate_store(
             "item_variance_map", item_id, &self.item_variance_map,
             || Rc::new(self.sess.cstore.item_variances(item_id)))
diff --git a/src/librustc/ty/relate.rs b/src/librustc/ty/relate.rs
index 8aa390cdd64..5c157ff32e7 100644
--- a/src/librustc/ty/relate.rs
+++ b/src/librustc/ty/relate.rs
@@ -14,7 +14,7 @@
 //! type equality, etc.
 
 use hir::def_id::DefId;
-use ty::subst::Substs;
+use ty::subst::{Kind, Substs};
 use ty::{self, Ty, TyCtxt, TypeFoldable};
 use ty::error::{ExpectedFound, TypeError};
 use std::rc::Rc;
@@ -139,7 +139,7 @@ fn relate_item_substs<'a, 'gcx, 'tcx, R>(relation: &mut R,
 }
 
 pub fn relate_substs<'a, 'gcx, 'tcx, R>(relation: &mut R,
-                                        variances: Option<&ty::ItemVariances>,
+                                        variances: Option<&Vec<ty::Variance>>,
                                         a_subst: &'tcx Substs<'tcx>,
                                         b_subst: &'tcx Substs<'tcx>)
                                         -> RelateResult<'tcx, &'tcx Substs<'tcx>>
@@ -147,17 +147,18 @@ pub fn relate_substs<'a, 'gcx, 'tcx, R>(relation: &mut R,
 {
     let tcx = relation.tcx();
 
-    let types = a_subst.types().zip(b_subst.types()).enumerate().map(|(i, (a_ty, b_ty))| {
-        let variance = variances.map_or(ty::Invariant, |v| v.types[i]);
-        relation.relate_with_variance(variance, a_ty, b_ty)
-    }).collect::<Result<_, _>>()?;
-
-    let regions = a_subst.regions().zip(b_subst.regions()).enumerate().map(|(i, (a_r, b_r))| {
-        let variance = variances.map_or(ty::Invariant, |v| v.regions[i]);
-        relation.relate_with_variance(variance, a_r, b_r)
-    }).collect::<Result<_, _>>()?;
+    let params = a_subst.params().iter().zip(b_subst.params()).enumerate().map(|(i, (a, b))| {
+        let variance = variances.map_or(ty::Invariant, |v| v[i]);
+        if let (Some(a_ty), Some(b_ty)) = (a.as_type(), b.as_type()) {
+            Ok(Kind::from(relation.relate_with_variance(variance, &a_ty, &b_ty)?))
+        } else if let (Some(a_r), Some(b_r)) = (a.as_region(), b.as_region()) {
+            Ok(Kind::from(relation.relate_with_variance(variance, &a_r, &b_r)?))
+        } else {
+            bug!()
+        }
+    });
 
-    Ok(Substs::new(tcx, types, regions))
+    Substs::maybe_new(tcx, params)
 }
 
 impl<'tcx> Relate<'tcx> for &'tcx ty::BareFnTy<'tcx> {
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index 5e0f3bc5e26..0e3f18c4474 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -21,7 +21,6 @@ use collections::enum_set::{self, EnumSet, CLike};
 use std::fmt;
 use std::mem;
 use std::ops;
-use std::slice;
 use syntax::abi;
 use syntax::ast::{self, Name};
 use syntax::parse::token::keywords;
@@ -336,7 +335,7 @@ impl<'tcx> PolyTraitRef<'tcx> {
         self.0.substs
     }
 
-    pub fn input_types(&self) -> slice::Iter<Ty<'tcx>> {
+    pub fn input_types<'a>(&'a self) -> impl DoubleEndedIterator<Item=Ty<'tcx>> + 'a {
         // FIXME(#20664) every use of this fn is probably a bug, it should yield Binder<>
         self.0.input_types()
     }
@@ -361,7 +360,7 @@ pub struct ExistentialTraitRef<'tcx> {
 }
 
 impl<'tcx> ExistentialTraitRef<'tcx> {
-    pub fn input_types(&self) -> slice::Iter<Ty<'tcx>>{
+    pub fn input_types<'a>(&'a self) -> impl DoubleEndedIterator<Item=Ty<'tcx>> + 'a {
         // 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
@@ -377,7 +376,7 @@ impl<'tcx> PolyExistentialTraitRef<'tcx> {
         self.0.def_id
     }
 
-    pub fn input_types(&self) -> slice::Iter<Ty<'tcx>> {
+    pub fn input_types<'a>(&'a self) -> impl DoubleEndedIterator<Item=Ty<'tcx>> + 'a {
         // FIXME(#20664) every use of this fn is probably a bug, it should yield Binder<>
         self.0.input_types()
     }
@@ -1229,13 +1228,13 @@ impl<'a, 'gcx, 'tcx> TyS<'tcx> {
             TyEnum(_, substs) |
             TyStruct(_, substs) |
             TyAnon(_, substs) => {
-                substs.regions().cloned().collect()
+                substs.regions().collect()
             }
             TyClosure(_, ref substs) => {
-                substs.func_substs.regions().cloned().collect()
+                substs.func_substs.regions().collect()
             }
             TyProjection(ref data) => {
-                data.trait_ref.substs.regions().cloned().collect()
+                data.trait_ref.substs.regions().collect()
             }
             TyFnDef(..) |
             TyFnPtr(_) |
diff --git a/src/librustc/ty/subst.rs b/src/librustc/ty/subst.rs
index b20c17c8a66..0ccfea23309 100644
--- a/src/librustc/ty/subst.rs
+++ b/src/librustc/ty/subst.rs
@@ -18,38 +18,151 @@ use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
 use serialize::{Encodable, Encoder, Decodable, Decoder};
 use syntax_pos::{Span, DUMMY_SP};
 
-use std::slice;
+use core::nonzero::NonZero;
+use std::fmt;
+use std::iter;
+use std::marker::PhantomData;
+use std::mem;
+
+/// An entity in the Rust typesystem, which can be one of
+/// several kinds (only types and lifetimes for now).
+/// To reduce memory usage, a `Kind` is a interned pointer,
+/// with the lowest 2 bits being reserved for a tag to
+/// indicate the type (`Ty` or `Region`) it points to.
+#[derive(Copy, Clone, PartialEq, Eq, Hash)]
+pub struct Kind<'tcx> {
+    ptr: NonZero<usize>,
+    marker: PhantomData<(Ty<'tcx>, &'tcx ty::Region)>
+}
 
-///////////////////////////////////////////////////////////////////////////
+const TAG_MASK: usize = 0b11;
+const TYPE_TAG: usize = 0b00;
+const REGION_TAG: usize = 0b01;
+
+impl<'tcx> From<Ty<'tcx>> for Kind<'tcx> {
+    fn from(ty: Ty<'tcx>) -> Kind<'tcx> {
+        // Ensure we can use the tag bits.
+        assert_eq!(mem::align_of_val(ty) & TAG_MASK, 0);
+
+        let ptr = ty as *const _ as usize;
+        Kind {
+            ptr: unsafe {
+                NonZero::new(ptr | TYPE_TAG)
+            },
+            marker: PhantomData
+        }
+    }
+}
+
+impl<'tcx> From<&'tcx ty::Region> for Kind<'tcx> {
+    fn from(r: &'tcx ty::Region) -> Kind<'tcx> {
+        // Ensure we can use the tag bits.
+        assert_eq!(mem::align_of_val(r) & TAG_MASK, 0);
+
+        let ptr = r as *const _ as usize;
+        Kind {
+            ptr: unsafe {
+                NonZero::new(ptr | REGION_TAG)
+            },
+            marker: PhantomData
+        }
+    }
+}
+
+impl<'tcx> Kind<'tcx> {
+    #[inline]
+    unsafe fn downcast<T>(self, tag: usize) -> Option<&'tcx T> {
+        let ptr = *self.ptr;
+        if ptr & TAG_MASK == tag {
+            Some(&*((ptr & !TAG_MASK) as *const _))
+        } else {
+            None
+        }
+    }
+
+    #[inline]
+    pub fn as_type(self) -> Option<Ty<'tcx>> {
+        unsafe {
+            self.downcast(TYPE_TAG)
+        }
+    }
+
+    #[inline]
+    pub fn as_region(self) -> Option<&'tcx ty::Region> {
+        unsafe {
+            self.downcast(REGION_TAG)
+        }
+    }
+}
+
+impl<'tcx> fmt::Debug for Kind<'tcx> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        if let Some(ty) = self.as_type() {
+            write!(f, "{:?}", ty)
+        } else if let Some(r) = self.as_region() {
+            write!(f, "{:?}", r)
+        } else {
+            write!(f, "<unknwon @ {:p}>", *self.ptr as *const ())
+        }
+    }
+}
+
+impl<'tcx> TypeFoldable<'tcx> for Kind<'tcx> {
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        if let Some(ty) = self.as_type() {
+            Kind::from(ty.fold_with(folder))
+        } else if let Some(r) = self.as_region() {
+            Kind::from(r.fold_with(folder))
+        } else {
+            bug!()
+        }
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        if let Some(ty) = self.as_type() {
+            ty.visit_with(visitor)
+        } else if let Some(r) = self.as_region() {
+            r.visit_with(visitor)
+        } else {
+            bug!()
+        }
+    }
+}
 
 /// A substitution mapping type/region parameters to new values.
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub struct Substs<'tcx> {
-    types: Vec<Ty<'tcx>>,
-    regions: Vec<ty::Region>,
+    params: Vec<Kind<'tcx>>
 }
 
 impl<'a, 'gcx, 'tcx> Substs<'tcx> {
-    pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>,
-               t: Vec<Ty<'tcx>>,
-               r: Vec<ty::Region>)
-               -> &'tcx Substs<'tcx>
-    {
-        tcx.mk_substs(Substs { types: t, regions: r })
+    pub fn new<I>(tcx: TyCtxt<'a, 'gcx, 'tcx>, params: I)
+                  -> &'tcx Substs<'tcx>
+    where I: IntoIterator<Item=Kind<'tcx>> {
+        tcx.mk_substs(Substs {
+            params: params.into_iter().collect()
+        })
+    }
+
+    pub fn maybe_new<I, E>(tcx: TyCtxt<'a, 'gcx, 'tcx>, params: I)
+                           -> Result<&'tcx Substs<'tcx>, E>
+    where I: IntoIterator<Item=Result<Kind<'tcx>, E>> {
+        Ok(tcx.mk_substs(Substs {
+            params: params.into_iter().collect::<Result<_, _>>()?
+        }))
     }
 
     pub fn new_trait(tcx: TyCtxt<'a, 'gcx, 'tcx>,
-                     mut t: Vec<Ty<'tcx>>,
-                     r: Vec<ty::Region>,
-                     s: Ty<'tcx>)
+                     s: Ty<'tcx>,
+                     t: &[Ty<'tcx>])
                     -> &'tcx Substs<'tcx>
     {
-        t.insert(0, s);
-        Substs::new(tcx, t, r)
+        let t = iter::once(s).chain(t.iter().cloned());
+        Substs::new(tcx, t.map(Kind::from))
     }
 
     pub fn empty(tcx: TyCtxt<'a, 'gcx, 'tcx>) -> &'tcx Substs<'tcx> {
-        Substs::new(tcx, vec![], vec![])
+        Substs::new(tcx, vec![])
     }
 
     /// Creates a Substs for generic parameter definitions,
@@ -65,16 +178,13 @@ impl<'a, 'gcx, 'tcx> Substs<'tcx> {
     where FR: FnMut(&ty::RegionParameterDef, &Substs<'tcx>) -> &'tcx ty::Region,
           FT: FnMut(&ty::TypeParameterDef<'tcx>, &Substs<'tcx>) -> Ty<'tcx> {
         let defs = tcx.lookup_generics(def_id);
-        let num_regions = defs.parent_regions as usize + defs.regions.len();
-        let num_types = defs.parent_types as usize + defs.types.len();
         let mut substs = Substs {
-            regions: Vec::with_capacity(num_regions),
-            types: Vec::with_capacity(num_types)
+            params: Vec::with_capacity(defs.count())
         };
 
         substs.fill_item(tcx, defs, &mut mk_region, &mut mk_type);
 
-        Substs::new(tcx, substs.types, substs.regions)
+        tcx.mk_substs(substs)
     }
 
     fn fill_item<FR, FT>(&mut self,
@@ -89,41 +199,59 @@ impl<'a, 'gcx, 'tcx> Substs<'tcx> {
             self.fill_item(tcx, parent_defs, mk_region, mk_type);
         }
 
+        // Handle Self first, before all regions.
+        let mut types = defs.types.iter();
+        if defs.parent.is_none() && defs.has_self {
+            let def = types.next().unwrap();
+            let ty = mk_type(def, self);
+            assert_eq!(def.index as usize, self.params.len());
+            self.params.push(Kind::from(ty));
+        }
+
         for def in &defs.regions {
             let region = mk_region(def, self);
-            assert_eq!(def.index as usize, self.regions.len());
-            self.regions.push(region);
+            assert_eq!(def.index as usize, self.params.len());
+            self.params.push(Kind::from(region));
         }
 
-        for def in &defs.types {
+        for def in types {
             let ty = mk_type(def, self);
-            assert_eq!(def.index as usize, self.types.len());
-            self.types.push(ty);
+            assert_eq!(def.index as usize, self.params.len());
+            self.params.push(Kind::from(ty));
         }
     }
 
     pub fn is_noop(&self) -> bool {
-        self.regions.is_empty() && self.types.is_empty()
+        self.params.is_empty()
     }
 
     #[inline]
-    pub fn types(&self) -> slice::Iter<Ty<'tcx>> {
-        self.types.iter()
+    pub fn params(&self) -> &[Kind<'tcx>] {
+        &self.params
     }
 
     #[inline]
-    pub fn regions(&self) -> slice::Iter<ty::Region> {
-        self.regions.iter()
+    pub fn types(&'a self) -> impl DoubleEndedIterator<Item=Ty<'tcx>> + 'a {
+        self.params.iter().filter_map(|k| k.as_type())
+    }
+
+    #[inline]
+    pub fn regions(&'a self) -> impl DoubleEndedIterator<Item=&'tcx ty::Region> + 'a {
+        self.params.iter().filter_map(|k| k.as_region())
     }
 
     #[inline]
     pub fn type_at(&self, i: usize) -> Ty<'tcx> {
-        self.types[i]
+        self.params[i].as_type().unwrap_or_else(|| {
+            bug!("expected type for param #{} in {:?}", i, self.params);
+        })
     }
 
     #[inline]
     pub fn region_at(&self, i: usize) -> &'tcx ty::Region {
-        self.regions[i]
+        self.params[i].as_region().unwrap_or_else(|| {
+            bug!("expected region for param #{} in {:?}", i, self.params);
+        })
     }
 
     #[inline]
@@ -146,19 +274,19 @@ impl<'a, 'gcx, 'tcx> Substs<'tcx> {
                        target_substs: &Substs<'tcx>)
                        -> &'tcx Substs<'tcx> {
         let defs = tcx.lookup_generics(source_ancestor);
-        let regions = target_substs.regions.iter()
-            .chain(&self.regions[defs.regions.len()..]).cloned().collect();
-        let types = target_substs.types.iter()
-            .chain(&self.types[defs.types.len()..]).cloned().collect();
-        Substs::new(tcx, types, regions)
+        tcx.mk_substs(Substs {
+            params: target_substs.params.iter()
+                .chain(&self.params[defs.own_count()..]).cloned().collect()
+        })
     }
 }
 
 impl<'tcx> TypeFoldable<'tcx> for &'tcx Substs<'tcx> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
-        let types = self.types.fold_with(folder);
-        let regions = self.regions.fold_with(folder);
-        Substs::new(folder.tcx(), types, regions)
+        let params = self.params.iter().map(|k| k.fold_with(folder)).collect();
+        folder.tcx().mk_substs(Substs {
+            params: params
+        })
     }
 
     fn fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
@@ -166,7 +294,7 @@ impl<'tcx> TypeFoldable<'tcx> for &'tcx Substs<'tcx> {
     }
 
     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
-        self.types.visit_with(visitor) || self.regions.visit_with(visitor)
+        self.params.visit_with(visitor)
     }
 }
 
@@ -263,8 +391,10 @@ impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for SubstFolder<'a, 'gcx, 'tcx> {
         // the specialized routine `ty::replace_late_regions()`.
         match *r {
             ty::ReEarlyBound(data) => {
-                match self.substs.regions.get(data.index as usize) {
-                    Some(&r) => {
+                let r = self.substs.params.get(data.index as usize)
+                            .and_then(|k| k.as_region());
+                match r {
+                    Some(r) => {
                         self.shift_region_through_binders(r)
                     }
                     None => {
@@ -318,9 +448,10 @@ impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for SubstFolder<'a, 'gcx, 'tcx> {
 impl<'a, 'gcx, 'tcx> SubstFolder<'a, 'gcx, 'tcx> {
     fn ty_for_param(&self, p: ty::ParamTy, source_ty: Ty<'tcx>) -> Ty<'tcx> {
         // Look up the type in the substitutions. It really should be in there.
-        let opt_ty = self.substs.types.get(p.idx as usize);
+        let opt_ty = self.substs.params.get(p.idx as usize)
+                         .and_then(|k| k.as_type());
         let ty = match opt_ty {
-            Some(t) => *t,
+            Some(t) => t,
             None => {
                 let span = self.span.unwrap_or(DUMMY_SP);
                 span_bug!(
@@ -331,7 +462,7 @@ impl<'a, 'gcx, 'tcx> SubstFolder<'a, 'gcx, 'tcx> {
                     source_ty,
                     p.idx,
                     self.root_ty,
-                    self.substs);
+                    self.substs.params);
             }
         };
 
@@ -407,12 +538,11 @@ impl<'a, 'gcx, 'tcx> ty::TraitRef<'tcx> {
                        substs: &Substs<'tcx>)
                        -> ty::TraitRef<'tcx> {
         let defs = tcx.lookup_generics(trait_id);
-        let regions = substs.regions[..defs.regions.len()].to_vec();
-        let types = substs.types[..defs.types.len()].to_vec();
 
+        let params = substs.params[..defs.own_count()].iter().cloned();
         ty::TraitRef {
             def_id: trait_id,
-            substs: Substs::new(tcx, types, regions)
+            substs: Substs::new(tcx, params)
         }
     }
 }
@@ -421,13 +551,13 @@ impl<'a, 'gcx, 'tcx> ty::ExistentialTraitRef<'tcx> {
     pub fn erase_self_ty(tcx: TyCtxt<'a, 'gcx, 'tcx>,
                          trait_ref: ty::TraitRef<'tcx>)
                          -> ty::ExistentialTraitRef<'tcx> {
-        let Substs { mut types, regions } = trait_ref.substs.clone();
-
-        types.remove(0);
+        // Assert there is a Self.
+        trait_ref.substs.type_at(0);
 
+        let params = trait_ref.substs.params[1..].iter().cloned();
         ty::ExistentialTraitRef {
             def_id: trait_ref.def_id,
-            substs: Substs::new(tcx, types, regions)
+            substs: Substs::new(tcx, params)
         }
     }
 }
@@ -444,13 +574,11 @@ impl<'a, 'gcx, 'tcx> ty::PolyExistentialTraitRef<'tcx> {
         assert!(!self_ty.has_escaping_regions());
 
         self.map_bound(|trait_ref| {
-            let Substs { mut types, regions } = trait_ref.substs.clone();
-
-            types.insert(0, self_ty);
-
+            let params = trait_ref.substs.params.iter().cloned();
+            let params = iter::once(Kind::from(self_ty)).chain(params);
             ty::TraitRef {
                 def_id: trait_ref.def_id,
-                substs: Substs::new(tcx, types, regions)
+                substs: Substs::new(tcx, params)
             }
         })
     }
diff --git a/src/librustc/ty/util.rs b/src/librustc/ty/util.rs
index 96f432587b1..dd5c6a9758a 100644
--- a/src/librustc/ty/util.rs
+++ b/src/librustc/ty/util.rs
@@ -693,7 +693,7 @@ impl<'a, 'tcx> ty::TyS<'tcx> {
                         return false;
                     }
 
-                    substs_a.types().zip(substs_b.types()).all(|(&a, &b)| same_type(a, b))
+                    substs_a.types().zip(substs_b.types()).all(|(a, b)| same_type(a, b))
                 }
                 _ => {
                     a == b
diff --git a/src/librustc/ty/walk.rs b/src/librustc/ty/walk.rs
index 5a94ba3cf6c..409f5a85997 100644
--- a/src/librustc/ty/walk.rs
+++ b/src/librustc/ty/walk.rs
@@ -67,6 +67,12 @@ pub fn walk_shallow<'tcx>(ty: Ty<'tcx>) -> IntoIter<Ty<'tcx>> {
     stack.into_iter()
 }
 
+// We push types on the stack in reverse order so as to
+// maintain a pre-order traversal. As of the time of this
+// writing, the fact that the traversal is pre-order is not
+// known to be significant to any code, but it seems like the
+// natural order one would expect (basically, the order of the
+// types as they are written).
 fn push_subtypes<'tcx>(stack: &mut Vec<Ty<'tcx>>, parent_ty: Ty<'tcx>) {
     match parent_ty.sty {
         ty::TyBool | ty::TyChar | ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) |
@@ -79,28 +85,28 @@ fn push_subtypes<'tcx>(stack: &mut Vec<Ty<'tcx>>, parent_ty: Ty<'tcx>) {
             stack.push(mt.ty);
         }
         ty::TyProjection(ref data) => {
-            push_reversed(stack, data.trait_ref.substs.types());
+            stack.extend(data.trait_ref.substs.types().rev());
         }
         ty::TyTrait(ref obj) => {
-            push_reversed(stack, obj.principal.input_types());
-            push_reversed(stack, &obj.projection_bounds.iter().map(|pred| {
+            stack.extend(obj.principal.input_types().rev());
+            stack.extend(obj.projection_bounds.iter().map(|pred| {
                 pred.0.ty
-            }).collect::<Vec<_>>());
+            }).rev());
         }
         ty::TyEnum(_, ref substs) |
         ty::TyStruct(_, ref substs) |
         ty::TyAnon(_, ref substs) => {
-            push_reversed(stack, substs.types());
+            stack.extend(substs.types().rev());
         }
         ty::TyClosure(_, ref substs) => {
-            push_reversed(stack, substs.func_substs.types());
-            push_reversed(stack, substs.upvar_tys);
+            stack.extend(substs.func_substs.types().rev());
+            stack.extend(substs.upvar_tys.iter().cloned().rev());
         }
         ty::TyTuple(ts) => {
-            push_reversed(stack, ts);
+            stack.extend(ts.iter().cloned().rev());
         }
         ty::TyFnDef(_, substs, ref ft) => {
-            push_reversed(stack, substs.types());
+            stack.extend(substs.types().rev());
             push_sig_subtypes(stack, &ft.sig);
         }
         ty::TyFnPtr(ref ft) => {
@@ -111,20 +117,5 @@ fn push_subtypes<'tcx>(stack: &mut Vec<Ty<'tcx>>, parent_ty: Ty<'tcx>) {
 
 fn push_sig_subtypes<'tcx>(stack: &mut Vec<Ty<'tcx>>, sig: &ty::PolyFnSig<'tcx>) {
     stack.push(sig.0.output);
-    push_reversed(stack, &sig.0.inputs);
-}
-
-fn push_reversed<'a, 'tcx: 'a, I>(stack: &mut Vec<Ty<'tcx>>, tys: I)
-    where I: IntoIterator<Item=&'a Ty<'tcx>>,
-          I::IntoIter: DoubleEndedIterator
-{
-    // We push slices on the stack in reverse order so as to
-    // maintain a pre-order traversal. As of the time of this
-    // writing, the fact that the traversal is pre-order is not
-    // known to be significant to any code, but it seems like the
-    // natural order one would expect (basically, the order of the
-    // types as they are written).
-    for &ty in tys.into_iter().rev() {
-        stack.push(ty);
-    }
+    stack.extend(sig.0.inputs.iter().cloned().rev());
 }
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 4b6234e8815..24b68c66e46 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -143,14 +143,14 @@ pub fn parameterized(f: &mut fmt::Formatter,
         }
     };
 
-    let print_regions = |f: &mut fmt::Formatter, start: &str, regions| {
+    let print_regions = |f: &mut fmt::Formatter, start: &str, skip, count| {
         // Don't print any regions if they're all erased.
-        if Iterator::all(&mut Clone::clone(&regions),
-                         |r: &ty::Region| *r == ty::ReErased) {
+        let regions = || substs.regions().skip(skip).take(count);
+        if regions().all(|r: &ty::Region| *r == ty::ReErased) {
             return Ok(());
         }
 
-        for region in regions {
+        for region in regions() {
             let region: &ty::Region = region;
             start_or_continue(f, start, ", ")?;
             if verbose {
@@ -173,12 +173,12 @@ pub fn parameterized(f: &mut fmt::Formatter,
         Ok(())
     };
 
-    print_regions(f, "<", substs.regions().take(num_regions).skip(0))?;
+    print_regions(f, "<", 0, num_regions)?;
 
     let tps = substs.types().take(num_types - num_supplied_defaults)
                             .skip(has_self as usize);
 
-    for &ty in tps {
+    for ty in tps {
         start_or_continue(f, "<", ", ")?;
         write!(f, "{}", ty)?;
     }
@@ -204,7 +204,7 @@ pub fn parameterized(f: &mut fmt::Formatter,
             write!(f, "::{}", item_name)?;
         }
 
-        print_regions(f, "::<", substs.regions().take(usize::MAX).skip(num_regions))?;
+        print_regions(f, "::<", num_regions, usize::MAX)?;
 
         // FIXME: consider being smart with defaults here too
         for ty in substs.types().skip(num_types) {
@@ -655,13 +655,6 @@ impl fmt::Debug for ty::Variance {
     }
 }
 
-impl fmt::Debug for ty::ItemVariances {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "ItemVariances(types={:?}, regions={:?})",
-               self.types, self.regions)
-    }
-}
-
 impl<'tcx> fmt::Debug for ty::GenericPredicates<'tcx> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         write!(f, "GenericPredicates({:?})", self.predicates)
diff --git a/src/librustc_borrowck/borrowck/mir/elaborate_drops.rs b/src/librustc_borrowck/borrowck/mir/elaborate_drops.rs
index 111646912ad..3ff2fb8e2e5 100644
--- a/src/librustc_borrowck/borrowck/mir/elaborate_drops.rs
+++ b/src/librustc_borrowck/borrowck/mir/elaborate_drops.rs
@@ -16,7 +16,7 @@ use super::{drop_flag_effects_for_location, on_all_children_bits};
 use super::{DropFlagState, MoveDataParamEnv};
 use super::patch::MirPatch;
 use rustc::ty::{self, Ty, TyCtxt};
-use rustc::ty::subst::{Subst, Substs};
+use rustc::ty::subst::{Kind, Subst, Substs};
 use rustc::mir::repr::*;
 use rustc::mir::transform::{Pass, MirPass, MirSource};
 use rustc::middle::const_val::ConstVal;
@@ -26,6 +26,7 @@ use rustc_data_structures::indexed_vec::Idx;
 use syntax_pos::Span;
 
 use std::fmt;
+use std::iter;
 use std::u32;
 
 pub struct ElaborateDrops;
@@ -859,7 +860,7 @@ impl<'b, 'tcx> ElaborateDropsCtxt<'b, 'tcx> {
         let unit_temp = Lvalue::Temp(self.patch.new_temp(tcx.mk_nil()));
         let free_func = tcx.lang_items.require(lang_items::BoxFreeFnLangItem)
             .unwrap_or_else(|e| tcx.sess.fatal(&e));
-        let substs = Substs::new(tcx, vec![ty], vec![]);
+        let substs = Substs::new(tcx, iter::once(Kind::from(ty)));
         let fty = tcx.lookup_item_type(free_func).ty.subst(tcx, substs);
 
         self.patch.new_block(BasicBlockData {
diff --git a/src/librustc_driver/test.rs b/src/librustc_driver/test.rs
index a99262d30ee..460a6e68a5c 100644
--- a/src/librustc_driver/test.rs
+++ b/src/librustc_driver/test.rs
@@ -20,13 +20,14 @@ use rustc::middle::region::{self, CodeExtent};
 use rustc::middle::region::CodeExtentData;
 use rustc::middle::resolve_lifetime;
 use rustc::middle::stability;
-use rustc::ty::subst::{Subst, Substs};
+use rustc::ty::subst::{Kind, Subst, Substs};
 use rustc::traits::Reveal;
 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
 use rustc::infer::{self, InferOk, InferResult, TypeOrigin};
 use rustc_metadata::cstore::CStore;
 use rustc::hir::map as hir_map;
 use rustc::session::{self, config};
+use std::iter;
 use std::rc::Rc;
 use syntax::ast;
 use syntax::abi::Abi;
@@ -676,7 +677,7 @@ fn subst_ty_renumber_bound() {
             env.t_fn(&[t_param], env.t_nil())
         };
 
-        let substs = Substs::new(env.infcx.tcx, vec![t_rptr_bound1], vec![]);
+        let substs = Substs::new(env.infcx.tcx, iter::once(Kind::from(t_rptr_bound1)));
         let t_substituted = t_source.subst(env.infcx.tcx, substs);
 
         // t_expected = fn(&'a isize)
@@ -711,7 +712,7 @@ fn subst_ty_renumber_some_bounds() {
             env.t_pair(t_param, env.t_fn(&[t_param], env.t_nil()))
         };
 
-        let substs = Substs::new(env.infcx.tcx, vec![t_rptr_bound1], vec![]);
+        let substs = Substs::new(env.infcx.tcx, iter::once(Kind::from(t_rptr_bound1)));
         let t_substituted = t_source.subst(env.infcx.tcx, substs);
 
         // t_expected = (&'a isize, fn(&'a isize))
@@ -773,7 +774,7 @@ fn subst_region_renumber_region() {
             env.t_fn(&[env.t_rptr(re_early)], env.t_nil())
         };
 
-        let substs = Substs::new(env.infcx.tcx, vec![], vec![re_bound1]);
+        let substs = Substs::new(env.infcx.tcx, iter::once(Kind::from(re_bound1)));
         let t_substituted = t_source.subst(env.infcx.tcx, substs);
 
         // t_expected = fn(&'a isize)
diff --git a/src/librustc_metadata/csearch.rs b/src/librustc_metadata/csearch.rs
index d5c3a4a6bb0..0fd7b683067 100644
--- a/src/librustc_metadata/csearch.rs
+++ b/src/librustc_metadata/csearch.rs
@@ -73,7 +73,7 @@ impl<'tcx> CrateStore<'tcx> for cstore::CStore {
         decoder::closure_ty(&cdata, def_id.index, tcx)
     }
 
-    fn item_variances(&self, def: DefId) -> ty::ItemVariances {
+    fn item_variances(&self, def: DefId) -> Vec<ty::Variance> {
         self.dep_graph.read(DepNode::MetaData(def));
         let cdata = self.get_crate_data(def.krate);
         decoder::get_item_variances(&cdata, def.index)
diff --git a/src/librustc_metadata/decoder.rs b/src/librustc_metadata/decoder.rs
index ccd8bb70f65..bbda089b1c2 100644
--- a/src/librustc_metadata/decoder.rs
+++ b/src/librustc_metadata/decoder.rs
@@ -991,7 +991,7 @@ pub fn get_trait_item_def_ids(cdata: Cmd, id: DefIndex)
     }).collect()
 }
 
-pub fn get_item_variances(cdata: Cmd, id: DefIndex) -> ty::ItemVariances {
+pub fn get_item_variances(cdata: Cmd, id: DefIndex) -> Vec<ty::Variance> {
     let item_doc = cdata.lookup_item(id);
     let variance_doc = reader::get_doc(item_doc, tag_item_variances);
     let mut decoder = reader::Decoder::new(variance_doc);
diff --git a/src/librustc_metadata/tydecode.rs b/src/librustc_metadata/tydecode.rs
index 3b022448efa..f51299226fe 100644
--- a/src/librustc_metadata/tydecode.rs
+++ b/src/librustc_metadata/tydecode.rs
@@ -20,7 +20,7 @@ use rustc::hir;
 
 use rustc::hir::def_id::{DefId, DefIndex};
 use middle::region;
-use rustc::ty::subst::Substs;
+use rustc::ty::subst::{Kind, Substs};
 use rustc::ty::{self, ToPredicate, Ty, TyCtxt, TypeFoldable};
 
 use rbml;
@@ -129,19 +129,19 @@ impl<'a,'tcx> TyDecoder<'a,'tcx> {
     }
 
     pub fn parse_substs(&mut self) -> &'tcx Substs<'tcx> {
-        let mut regions = vec![];
-        let mut types = vec![];
+        let mut params = vec![];
         assert_eq!(self.next(), '[');
-        while self.peek() != '|' {
-            regions.push(self.parse_region());
-        }
-        assert_eq!(self.next(), '|');
         while self.peek() != ']' {
-            types.push(self.parse_ty());
+            let k = match self.next() {
+                'r' => Kind::from(self.parse_region()),
+                't' => Kind::from(self.parse_ty()),
+                _ => bug!()
+            };
+            params.push(k);
         }
         assert_eq!(self.next(), ']');
 
-        Substs::new(self.tcx, types, regions)
+        Substs::new(self.tcx, params)
     }
 
     pub fn parse_generics(&mut self) -> &'tcx ty::Generics<'tcx> {
diff --git a/src/librustc_metadata/tyencode.rs b/src/librustc_metadata/tyencode.rs
index f502ec45543..7255eae61d4 100644
--- a/src/librustc_metadata/tyencode.rs
+++ b/src/librustc_metadata/tyencode.rs
@@ -251,12 +251,16 @@ fn enc_opt<T, F>(w: &mut Cursor<Vec<u8>>, t: Option<T>, enc_f: F) where
 pub fn enc_substs<'a, 'tcx>(w: &mut Cursor<Vec<u8>>, cx: &ctxt<'a, 'tcx>,
                             substs: &Substs<'tcx>) {
     write!(w, "[");
-    for &r in substs.regions() {
-        enc_region(w, cx, r);
-    }
-    write!(w, "|");
-    for &ty in substs.types() {
-        enc_ty(w, cx, ty);
+    for &k in substs.params() {
+        if let Some(ty) = k.as_type() {
+            write!(w, "t");
+            enc_ty(w, cx, ty);
+        } else if let Some(r) = k.as_region() {
+            write!(w, "r");
+            enc_region(w, cx, r);
+        } else {
+            bug!()
+        }
     }
     write!(w, "]");
 }
diff --git a/src/librustc_mir/build/matches/test.rs b/src/librustc_mir/build/matches/test.rs
index 8c9ed53c8ab..bf43bfb326a 100644
--- a/src/librustc_mir/build/matches/test.rs
+++ b/src/librustc_mir/build/matches/test.rs
@@ -293,7 +293,7 @@ impl<'a, 'gcx, 'tcx> Builder<'a, 'gcx, 'tcx> {
                     assert!(ty.is_slice());
                     let eq_def_id = self.hir.tcx().lang_items.eq_trait().unwrap();
                     let ty = mt.ty;
-                    let (mty, method) = self.hir.trait_method(eq_def_id, "eq", ty, vec![ty]);
+                    let (mty, method) = self.hir.trait_method(eq_def_id, "eq", ty, &[ty]);
 
                     let bool_ty = self.hir.bool_ty();
                     let eq_result = self.temp(bool_ty);
diff --git a/src/librustc_mir/build/scope.rs b/src/librustc_mir/build/scope.rs
index 2f83c0ef1be..0b33e5a1450 100644
--- a/src/librustc_mir/build/scope.rs
+++ b/src/librustc_mir/build/scope.rs
@@ -89,13 +89,15 @@ should go to.
 use build::{BlockAnd, BlockAndExtension, Builder, CFG, ScopeAuxiliary, ScopeId};
 use rustc::middle::region::{CodeExtent, CodeExtentData};
 use rustc::middle::lang_items;
-use rustc::ty::subst::{Substs, Subst};
+use rustc::ty::subst::{Kind, Substs, Subst};
 use rustc::ty::{Ty, TyCtxt};
 use rustc::mir::repr::*;
 use syntax_pos::Span;
 use rustc_data_structures::indexed_vec::Idx;
 use rustc_data_structures::fnv::FnvHashMap;
 
+use std::iter;
+
 pub struct Scope<'tcx> {
     /// the scope-id within the scope_auxiliary
     id: ScopeId,
@@ -789,7 +791,7 @@ fn build_free<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
                               -> TerminatorKind<'tcx> {
     let free_func = tcx.lang_items.require(lang_items::BoxFreeFnLangItem)
                        .unwrap_or_else(|e| tcx.sess.fatal(&e));
-    let substs = Substs::new(tcx, vec![data.item_ty], vec![]);
+    let substs = Substs::new(tcx, iter::once(Kind::from(data.item_ty)));
     TerminatorKind::Call {
         func: Operand::Constant(Constant {
             span: data.span,
diff --git a/src/librustc_mir/hair/cx/mod.rs b/src/librustc_mir/hair/cx/mod.rs
index 972e7f5be70..a38b429333b 100644
--- a/src/librustc_mir/hair/cx/mod.rs
+++ b/src/librustc_mir/hair/cx/mod.rs
@@ -144,10 +144,10 @@ impl<'a, 'gcx, 'tcx> Cx<'a, 'gcx, 'tcx> {
                         trait_def_id: DefId,
                         method_name: &str,
                         self_ty: Ty<'tcx>,
-                        params: Vec<Ty<'tcx>>)
+                        params: &[Ty<'tcx>])
                         -> (Ty<'tcx>, Literal<'tcx>) {
         let method_name = token::intern(method_name);
-        let substs = Substs::new_trait(self.tcx, params, vec![], self_ty);
+        let substs = Substs::new_trait(self.tcx, self_ty, params);
         for trait_item in self.tcx.trait_items(trait_def_id).iter() {
             match *trait_item {
                 ty::ImplOrTraitItem::MethodTraitItem(ref method) => {
diff --git a/src/librustc_trans/base.rs b/src/librustc_trans/base.rs
index 165884c8f55..5e431193a2c 100644
--- a/src/librustc_trans/base.rs
+++ b/src/librustc_trans/base.rs
@@ -514,7 +514,7 @@ pub fn custom_coerce_unsize_info<'scx, 'tcx>(scx: &SharedCrateContext<'scx, 'tcx
                                              -> CustomCoerceUnsized {
     let trait_ref = ty::Binder(ty::TraitRef {
         def_id: scx.tcx().lang_items.coerce_unsized_trait().unwrap(),
-        substs: Substs::new_trait(scx.tcx(), vec![target_ty], vec![], source_ty)
+        substs: Substs::new_trait(scx.tcx(), source_ty, &[target_ty])
     });
 
     match fulfill_obligation(scx, DUMMY_SP, trait_ref) {
diff --git a/src/librustc_trans/collector.rs b/src/librustc_trans/collector.rs
index b0afc147e6f..8dd76535cf8 100644
--- a/src/librustc_trans/collector.rs
+++ b/src/librustc_trans/collector.rs
@@ -753,7 +753,7 @@ fn find_drop_glue_neighbors<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
                                    .drop_trait()
                                    .unwrap();
 
-        let self_type_substs = Substs::new_trait(scx.tcx(), vec![], vec![], ty);
+        let self_type_substs = Substs::new_trait(scx.tcx(), ty, &[]);
 
         let trait_ref = ty::TraitRef {
             def_id: drop_trait_def_id,
diff --git a/src/librustc_trans/debuginfo/metadata.rs b/src/librustc_trans/debuginfo/metadata.rs
index 49aa1955730..67d4a0e044c 100644
--- a/src/librustc_trans/debuginfo/metadata.rs
+++ b/src/librustc_trans/debuginfo/metadata.rs
@@ -345,7 +345,7 @@ impl<'tcx> TypeMap<'tcx> {
             if substs.types().next().is_some() {
                 output.push('<');
 
-                for &type_parameter in substs.types() {
+                for type_parameter in substs.types() {
                     let param_type_id =
                         type_map.get_unique_type_id_of_type(cx, type_parameter);
                     let param_type_id =
diff --git a/src/librustc_trans/debuginfo/mod.rs b/src/librustc_trans/debuginfo/mod.rs
index 72a91f50be3..4d8a9a2ac40 100644
--- a/src/librustc_trans/debuginfo/mod.rs
+++ b/src/librustc_trans/debuginfo/mod.rs
@@ -354,7 +354,7 @@ pub fn create_function_debug_context<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
         }
 
         name_to_append_suffix_to.push('<');
-        for (i, &actual_type) in substs.types().enumerate() {
+        for (i, actual_type) in substs.types().enumerate() {
             if i != 0 {
                 name_to_append_suffix_to.push_str(",");
             }
@@ -372,7 +372,7 @@ pub fn create_function_debug_context<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
         let template_params: Vec<_> = if cx.sess().opts.debuginfo == FullDebugInfo {
             let names = get_type_parameter_names(cx, generics);
             substs.types().zip(names).map(|(ty, name)| {
-                let actual_type = cx.tcx().normalize_associated_type(ty);
+                let actual_type = cx.tcx().normalize_associated_type(&ty);
                 let actual_type_metadata = type_metadata(cx, actual_type, syntax_pos::DUMMY_SP);
                 let name = CString::new(name.as_str().as_bytes()).unwrap();
                 unsafe {
diff --git a/src/librustc_trans/debuginfo/type_names.rs b/src/librustc_trans/debuginfo/type_names.rs
index 9337f7e58ff..f757578e695 100644
--- a/src/librustc_trans/debuginfo/type_names.rs
+++ b/src/librustc_trans/debuginfo/type_names.rs
@@ -181,7 +181,7 @@ pub fn push_debuginfo_type_name<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 
         output.push('<');
 
-        for &type_parameter in substs.types() {
+        for type_parameter in substs.types() {
             push_debuginfo_type_name(cx, type_parameter, true, output);
             output.push_str(", ");
         }
diff --git a/src/librustc_trans/glue.rs b/src/librustc_trans/glue.rs
index 6a072c84dd9..f29d85f3b52 100644
--- a/src/librustc_trans/glue.rs
+++ b/src/librustc_trans/glue.rs
@@ -302,7 +302,7 @@ fn trans_struct_drop<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 
     let trait_ref = ty::Binder(ty::TraitRef {
         def_id: tcx.lang_items.drop_trait().unwrap(),
-        substs: Substs::new_trait(tcx, vec![], vec![], t)
+        substs: Substs::new_trait(tcx, t, &[])
     });
     let vtbl = match fulfill_obligation(bcx.ccx().shared(), DUMMY_SP, trait_ref) {
         traits::VtableImpl(data) => data,
diff --git a/src/librustc_trans/trans_item.rs b/src/librustc_trans/trans_item.rs
index 93302ab3b3b..2c91c408487 100644
--- a/src/librustc_trans/trans_item.rs
+++ b/src/librustc_trans/trans_item.rs
@@ -541,7 +541,7 @@ fn push_type_params<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
     output.push('<');
 
-    for &type_parameter in substs.types() {
+    for type_parameter in substs.types() {
         push_unique_type_name(tcx, type_parameter, output);
         output.push_str(", ");
     }
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index 79c4a9af829..f24a7cf2121 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -473,7 +473,8 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
 
         let mut output_assoc_binding = None;
         let substs = Substs::for_item(tcx, def_id, |def, _| {
-            tcx.mk_region(regions[def.index as usize])
+            let i = def.index as usize - self_ty.is_some() as usize;
+            tcx.mk_region(regions[i])
         }, |def, substs| {
             let i = def.index as usize;
 
@@ -482,7 +483,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
                 return ty;
             }
 
-            let i = i - self_ty.is_some() as usize;
+            let i = i - self_ty.is_some() as usize - decl_generics.regions.len();
             if num_types_provided.map_or(false, |n| i < n) {
                 // A provided type parameter.
                 match *parameters {
diff --git a/src/librustc_typeck/check/autoderef.rs b/src/librustc_typeck/check/autoderef.rs
index 9a3cbabe553..19261a2447f 100644
--- a/src/librustc_typeck/check/autoderef.rs
+++ b/src/librustc_typeck/check/autoderef.rs
@@ -101,7 +101,7 @@ impl<'a, 'gcx, 'tcx> Autoderef<'a, 'gcx, 'tcx> {
                 Some(f) => f,
                 None => return None
             },
-            substs: Substs::new_trait(tcx, vec![], vec![], self.cur_ty)
+            substs: Substs::new_trait(tcx, self.cur_ty, &[])
         };
 
         let cause = traits::ObligationCause::misc(self.span, self.fcx.body_id);
diff --git a/src/librustc_typeck/check/coercion.rs b/src/librustc_typeck/check/coercion.rs
index 7126478f2c4..26a47055289 100644
--- a/src/librustc_typeck/check/coercion.rs
+++ b/src/librustc_typeck/check/coercion.rs
@@ -458,7 +458,7 @@ impl<'f, 'gcx, 'tcx> Coerce<'f, 'gcx, 'tcx> {
                                                          coerce_unsized_did,
                                                          0,
                                                          source,
-                                                         vec![target]));
+                                                         &[target]));
 
         // Keep resolving `CoerceUnsized` and `Unsize` predicates to avoid
         // emitting a coercion in cases like `Foo<$1>` -> `Foo<$2>`, where
diff --git a/src/librustc_typeck/check/method/confirm.rs b/src/librustc_typeck/check/method/confirm.rs
index 9197bdaa030..be77ca435a1 100644
--- a/src/librustc_typeck/check/method/confirm.rs
+++ b/src/librustc_typeck/check/method/confirm.rs
@@ -327,21 +327,22 @@ 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 supplied_start = substs.params().len() + method.generics.regions.len();
         Substs::for_item(self.tcx, method.def_id, |def, _| {
             let i = def.index as usize;
-            if i < substs.regions().count() {
+            if i < substs.params().len() {
                 substs.region_at(i)
             } else {
                 self.region_var_for_def(self.span, def)
             }
         }, |def, cur_substs| {
             let i = def.index as usize;
-            if i < substs.types().count() {
+            if i < substs.params().len() {
                 substs.type_at(i)
             } else if supplied_method_types.is_empty() {
                 self.type_var_for_def(self.span, def, cur_substs)
             } else {
-                supplied_method_types[i - substs.types().count()]
+                supplied_method_types[i - supplied_start]
             }
         })
     }
diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs
index e38d6aa7a00..a64982cd1bf 100644
--- a/src/librustc_typeck/check/method/probe.rs
+++ b/src/librustc_typeck/check/method/probe.rs
@@ -1237,7 +1237,7 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
         } else {
             let substs = Substs::for_item(self.tcx, method.def_id, |def, _| {
                 let i = def.index as usize;
-                if i < substs.regions().count() {
+                if i < substs.params().len() {
                     substs.region_at(i)
                 } else {
                     // In general, during probe we erase regions. See
@@ -1246,7 +1246,7 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
                 }
             }, |def, cur_substs| {
                 let i = def.index as usize;
-                if i < substs.types().count() {
+                if i < substs.params().len() {
                     substs.type_at(i)
                 } else {
                     self.type_var_for_def(self.span, def, cur_substs)
diff --git a/src/librustc_typeck/check/method/suggest.rs b/src/librustc_typeck/check/method/suggest.rs
index 573dae46456..f9699a55f50 100644
--- a/src/librustc_typeck/check/method/suggest.rs
+++ b/src/librustc_typeck/check/method/suggest.rs
@@ -54,7 +54,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
 
                 self.autoderef(span, ty).any(|(ty, _)| self.probe(|_| {
                     let fn_once_substs =
-                        Substs::new_trait(tcx, vec![self.next_ty_var()], vec![], ty);
+                        Substs::new_trait(tcx, ty, &[self.next_ty_var()]);
                     let trait_ref = ty::TraitRef::new(fn_once, fn_once_substs);
                     let poly_trait_ref = trait_ref.to_poly_trait_ref();
                     let obligation = Obligation::misc(span,
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index cc7eadefeb0..e972a5ca7fb 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -770,7 +770,7 @@ pub fn check_item_type<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>, it: &'tcx hir::Item) {
       }
       hir::ItemTy(_, ref generics) => {
         let pty_ty = ccx.tcx.node_id_to_type(it.id);
-        check_bounds_are_used(ccx, &generics.ty_params, pty_ty);
+        check_bounds_are_used(ccx, generics, pty_ty);
       }
       hir::ItemForeignMod(ref m) => {
         if m.abi == Abi::RustIntrinsic {
@@ -1899,7 +1899,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
     /// Registers obligations that all types appearing in `substs` are well-formed.
     pub fn add_wf_bounds(&self, substs: &Substs<'tcx>, expr: &hir::Expr)
     {
-        for &ty in substs.types() {
+        for ty in substs.types() {
             self.register_wf_obligation(ty, expr.span, traits::MiscObligation);
         }
     }
@@ -4242,18 +4242,23 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         self.check_path_parameter_count(span, !require_type_space, &mut type_segment);
         self.check_path_parameter_count(span, true, &mut fn_segment);
 
+        let (fn_start, has_self) = match (type_segment, fn_segment) {
+            (_, Some((_, generics))) => {
+                (generics.parent_count(), generics.has_self)
+            }
+            (Some((_, generics)), None) => {
+                (generics.own_count(), generics.has_self)
+            }
+            (None, None) => (0, false)
+        };
         let substs = Substs::for_item(self.tcx, def.def_id(), |def, _| {
             let mut i = def.index as usize;
-            let type_regions = match (type_segment, fn_segment) {
-                (_, Some((_, generics))) => generics.parent_regions as usize,
-                (Some((_, generics)), None) => generics.regions.len(),
-                (None, None) => 0
-            };
 
-            let segment = if i < type_regions {
+            let segment = if i < fn_start {
+                i -= has_self as usize;
                 type_segment
             } else {
-                i -= type_regions;
+                i -= fn_start;
                 fn_segment
             };
             let lifetimes = match segment.map(|(s, _)| &s.parameters) {
@@ -4269,18 +4274,9 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
             }
         }, |def, substs| {
             let mut i = def.index as usize;
-            let (type_types, has_self) = match (type_segment, fn_segment) {
-                (_, Some((_, generics))) => {
-                    (generics.parent_types as usize, generics.has_self)
-                }
-                (Some((_, generics)), None) => {
-                    (generics.types.len(), generics.has_self)
-                }
-                (None, None) => (0, false)
-            };
 
-            let can_omit = i >= type_types || !require_type_space;
-            let segment = if i < type_types {
+            let can_omit = i >= fn_start || !require_type_space;
+            let segment = if i < fn_start {
                 // Handle Self first, so we can adjust the index to match the AST.
                 if has_self && i == 0 {
                     return opt_self_ty.unwrap_or_else(|| {
@@ -4290,7 +4286,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
                 i -= has_self as usize;
                 type_segment
             } else {
-                i -= type_types;
+                i -= fn_start;
                 fn_segment
             };
             let types = match segment.map(|(s, _)| &s.parameters) {
@@ -4299,6 +4295,11 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
                 None => &[]
             };
 
+            // Skip over the lifetimes in the same segment.
+            if let Some((_, generics)) = segment {
+                i -= generics.regions.len();
+            }
+
             let omitted = can_omit && types.is_empty();
             if let Some(ast_ty) = types.get(i) {
                 // A provided type parameter.
@@ -4502,28 +4503,28 @@ pub fn may_break(tcx: TyCtxt, id: ast::NodeId, b: &hir::Block) -> bool {
 }
 
 pub fn check_bounds_are_used<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
-                                       tps: &[hir::TyParam],
+                                       generics: &hir::Generics,
                                        ty: Ty<'tcx>) {
     debug!("check_bounds_are_used(n_tps={}, ty={:?})",
-           tps.len(),  ty);
+           generics.ty_params.len(),  ty);
 
     // make a vector of booleans initially false, set to true when used
-    if tps.is_empty() { return; }
-    let mut tps_used = vec![false; tps.len()];
+    if generics.ty_params.is_empty() { return; }
+    let mut tps_used = vec![false; generics.ty_params.len()];
 
     for leaf_ty in ty.walk() {
         if let ty::TyParam(ParamTy {idx, ..}) = leaf_ty.sty {
             debug!("Found use of ty param num {}", idx);
-            tps_used[idx as usize] = true;
+            tps_used[idx as usize - generics.lifetimes.len()] = true;
         }
     }
 
-    for (i, b) in tps_used.iter().enumerate() {
-        if !*b {
-            struct_span_err!(ccx.tcx.sess, tps[i].span, E0091,
+    for (&used, param) in tps_used.iter().zip(&generics.ty_params) {
+        if !used {
+            struct_span_err!(ccx.tcx.sess, param.span, E0091,
                 "type parameter `{}` is unused",
-                tps[i].name)
-                .span_label(tps[i].span, &format!("unused type parameter"))
+                param.name)
+                .span_label(param.span, &format!("unused type parameter"))
                 .emit();
         }
     }
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index 5f5cda358ff..cef2bb07e35 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -1447,11 +1447,11 @@ impl<'a, 'gcx, 'tcx> RegionCtxt<'a, 'gcx, 'tcx> {
 
         let origin = infer::ParameterInScope(origin, expr_span);
 
-        for &region in substs.regions() {
+        for region in substs.regions() {
             self.sub_regions(origin.clone(), expr_region, region);
         }
 
-        for &ty in substs.types() {
+        for ty in substs.types() {
             let ty = self.resolve_type(ty);
             self.type_must_outlive(origin.clone(), ty, expr_region);
         }
@@ -1577,11 +1577,11 @@ impl<'a, 'gcx, 'tcx> RegionCtxt<'a, 'gcx, 'tcx> {
         if env_bounds.is_empty() && needs_infer {
             debug!("projection_must_outlive: no declared bounds");
 
-            for &component_ty in projection_ty.trait_ref.substs.types() {
+            for component_ty in projection_ty.trait_ref.substs.types() {
                 self.type_must_outlive(origin.clone(), component_ty, region);
             }
 
-            for &r in projection_ty.trait_ref.substs.regions() {
+            for r in projection_ty.trait_ref.substs.regions() {
                 self.sub_regions(origin.clone(), region, r);
             }
 
diff --git a/src/librustc_typeck/check/wfcheck.rs b/src/librustc_typeck/check/wfcheck.rs
index b3f26c6c838..38ec7ba686f 100644
--- a/src/librustc_typeck/check/wfcheck.rs
+++ b/src/librustc_typeck/check/wfcheck.rs
@@ -457,7 +457,7 @@ impl<'ccx, 'gcx> CheckTypeWellFormedVisitor<'ccx, 'gcx> {
         let variances = self.tcx().item_variances(item_def_id);
 
         let mut constrained_parameters: HashSet<_> =
-            variances.types
+            variances[ast_generics.lifetimes.len()..]
                      .iter().enumerate()
                      .filter(|&(_, &variance)| variance != ty::Bivariant)
                      .map(|(index, _)| self.param_ty(ast_generics, index))
@@ -468,22 +468,22 @@ impl<'ccx, 'gcx> CheckTypeWellFormedVisitor<'ccx, 'gcx> {
                                          None,
                                          &mut constrained_parameters);
 
-        for (index, _) in variances.types.iter().enumerate() {
-            let param_ty = self.param_ty(ast_generics, index);
-            if constrained_parameters.contains(&Parameter::Type(param_ty)) {
-                continue;
-            }
-            let span = ast_generics.ty_params[index].span;
-            self.report_bivariance(span, param_ty.name);
-        }
-
-        for (index, &variance) in variances.regions.iter().enumerate() {
-            if variance != ty::Bivariant {
-                continue;
-            }
+        for (index, &variance) in variances.iter().enumerate() {
+            let (span, name) = if index < ast_generics.lifetimes.len() {
+                if variance != ty::Bivariant {
+                    continue;
+                }
 
-            let span = ast_generics.lifetimes[index].lifetime.span;
-            let name = ast_generics.lifetimes[index].lifetime.name;
+                (ast_generics.lifetimes[index].lifetime.span,
+                 ast_generics.lifetimes[index].lifetime.name)
+            } else {
+                let index = index - ast_generics.lifetimes.len();
+                let param_ty = self.param_ty(ast_generics, index);
+                if constrained_parameters.contains(&Parameter::Type(param_ty)) {
+                    continue;
+                }
+                (ast_generics.ty_params[index].span, param_ty.name)
+            };
             self.report_bivariance(span, name);
         }
     }
@@ -597,7 +597,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
                 // Trait impl: take implied bounds from all types that
                 // appear in the trait reference.
                 let trait_ref = self.instantiate_type_scheme(span, free_substs, trait_ref);
-                trait_ref.substs.types().cloned().collect()
+                trait_ref.substs.types().collect()
             }
 
             None => {
diff --git a/src/librustc_typeck/check/writeback.rs b/src/librustc_typeck/check/writeback.rs
index 6a738032adf..3bd0e890bb8 100644
--- a/src/librustc_typeck/check/writeback.rs
+++ b/src/librustc_typeck/check/writeback.rs
@@ -104,7 +104,12 @@ impl<'cx, 'gcx, 'tcx> WritebackCx<'cx, 'gcx, 'tcx> {
 
         let gcx = fcx.tcx.global_tcx();
         let free_substs = fcx.parameter_environment.free_substs;
-        for (i, r) in free_substs.regions().enumerate() {
+        for (i, k) in free_substs.params().iter().enumerate() {
+            let r = if let Some(r) = k.as_region() {
+                r
+            } else {
+                continue;
+            };
             match *r {
                 ty::ReFree(ty::FreeRegion {
                     bound_region: ty::BoundRegion::BrNamed(def_id, name, _), ..
diff --git a/src/librustc_typeck/coherence/mod.rs b/src/librustc_typeck/coherence/mod.rs
index c522d9fce0e..7d6cee7b3ba 100644
--- a/src/librustc_typeck/coherence/mod.rs
+++ b/src/librustc_typeck/coherence/mod.rs
@@ -498,7 +498,7 @@ impl<'a, 'gcx, 'tcx> CoherenceChecker<'a, 'gcx, 'tcx> {
                 // Register an obligation for `A: Trait<B>`.
                 let cause = traits::ObligationCause::misc(span, impl_node_id);
                 let predicate = tcx.predicate_for_trait_def(cause, trait_def_id, 0,
-                                                            source, vec![target]);
+                                                            source, &[target]);
                 fulfill_cx.register_predicate_obligation(&infcx, predicate);
 
                 // Check that all transitive obligations are satisfied.
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index 2b2b1d3154f..0074d3930e2 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -1486,6 +1486,7 @@ fn generics_of_def_id<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 
         let has_self = opt_self.is_some();
         let mut parent_has_self = false;
+        let mut own_start = has_self as u32;
         let (parent_regions, parent_types) = parent_def_id.map_or((0, 0), |def_id| {
             let generics = generics_of_def_id(ccx, def_id);
             assert_eq!(generics.parent, None);
@@ -1493,6 +1494,7 @@ fn generics_of_def_id<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
             assert_eq!(generics.parent_types, 0);
             assert_eq!(has_self, false);
             parent_has_self = generics.has_self;
+            own_start = generics.count() as u32;
             (generics.regions.len() as u32, generics.types.len() as u32)
         });
 
@@ -1500,17 +1502,18 @@ fn generics_of_def_id<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
         let regions = early_lifetimes.iter().enumerate().map(|(i, l)| {
             ty::RegionParameterDef {
                 name: l.lifetime.name,
-                index: parent_regions + i as u32,
+                index: own_start + i as u32,
                 def_id: tcx.map.local_def_id(l.lifetime.id),
                 bounds: l.bounds.iter().map(|l| {
                     ast_region_to_region(tcx, l)
                 }).collect()
             }
-        }).collect();
+        }).collect::<Vec<_>>();
 
         // Now create the real type parameters.
+        let type_start = own_start + regions.len() as u32;
         let types = ast_generics.ty_params.iter().enumerate().map(|(i, p)| {
-            let i = parent_types + has_self as u32 + i as u32;
+            let i = type_start + i as u32;
             get_or_create_type_parameter_def(ccx, ast_generics, i, p, allow_defaults)
         });
         let types: Vec<_> = opt_self.into_iter().chain(types).collect();
@@ -1529,8 +1532,8 @@ fn generics_of_def_id<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 
         tcx.alloc_generics(ty::Generics {
             parent: parent_def_id,
-            parent_regions: parent_regions as u32,
-            parent_types: parent_types as u32,
+            parent_regions: parent_regions,
+            parent_types: parent_types,
             regions: regions,
             types: types,
             has_self: has_self || parent_has_self
@@ -1741,12 +1744,12 @@ fn ty_generic_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
                                   -> ty::GenericPredicates<'tcx>
 {
     let tcx = ccx.tcx;
-    let (parent_regions, parent_types) = parent.map_or((0, 0), |def_id| {
+    let parent_count = parent.map_or(0, |def_id| {
         let generics = generics_of_def_id(ccx, def_id);
         assert_eq!(generics.parent, None);
         assert_eq!(generics.parent_regions, 0);
         assert_eq!(generics.parent_types, 0);
-        (generics.regions.len() as u32, generics.types.len() as u32)
+        generics.count() as u32
     });
     let ref base_predicates = match parent {
         Some(def_id) => {
@@ -1762,10 +1765,29 @@ fn ty_generic_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
     };
     let mut predicates = super_predicates;
 
+    // Collect the region predicates that were declared inline as
+    // well. In the case of parameters declared on a fn or method, we
+    // have to be careful to only iterate over early-bound regions.
+    let own_start = parent_count + has_self as u32;
+    let early_lifetimes = early_bound_lifetimes_from_generics(ccx, ast_generics);
+    for (index, param) in early_lifetimes.iter().enumerate() {
+        let index = own_start + index as u32;
+        let region = ccx.tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
+            index: index,
+            name: param.lifetime.name
+        }));
+        for bound in &param.bounds {
+            let bound_region = ast_region_to_region(ccx.tcx, bound);
+            let outlives = ty::Binder(ty::OutlivesPredicate(region, bound_region));
+            predicates.push(outlives.to_predicate());
+        }
+    }
+
     // Collect the predicates that were written inline by the user on each
     // type parameter (e.g., `<T:Foo>`).
+    let type_start = own_start + early_lifetimes.len() as u32;
     for (index, param) in ast_generics.ty_params.iter().enumerate() {
-        let index = parent_types + has_self as u32 + index as u32;
+        let index = type_start + index as u32;
         let param_ty = ty::ParamTy::new(index, param.name).to_ty(ccx.tcx);
         let bounds = compute_bounds(&ccx.icx(&(base_predicates, ast_generics)),
                                     param_ty,
@@ -1776,24 +1798,6 @@ fn ty_generic_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
         predicates.extend(bounds.predicates(ccx.tcx, param_ty));
     }
 
-    // Collect the region predicates that were declared inline as
-    // well. In the case of parameters declared on a fn or method, we
-    // have to be careful to only iterate over early-bound regions.
-    let early_lifetimes = early_bound_lifetimes_from_generics(ccx, ast_generics);
-    for (index, param) in early_lifetimes.iter().enumerate() {
-        let index = parent_regions + index as u32;
-        let region =
-            ty::ReEarlyBound(ty::EarlyBoundRegion {
-                index: index,
-                name: param.lifetime.name
-            });
-        for bound in &param.bounds {
-            let bound_region = ast_region_to_region(ccx.tcx, bound);
-            let outlives = ty::Binder(ty::OutlivesPredicate(region, bound_region));
-            predicates.push(outlives.to_predicate());
-        }
-    }
-
     // Add in the bounds that appear in the where-clause
     let where_clause = &ast_generics.where_clause;
     for predicate in &where_clause.predicates {
diff --git a/src/librustc_typeck/variance/constraints.rs b/src/librustc_typeck/variance/constraints.rs
index 5fd03cbd054..2cf84b5745a 100644
--- a/src/librustc_typeck/variance/constraints.rs
+++ b/src/librustc_typeck/variance/constraints.rs
@@ -26,7 +26,6 @@ use rustc::hir::intravisit::Visitor;
 
 use super::terms::*;
 use super::terms::VarianceTerm::*;
-use super::terms::ParamKind::*;
 use super::xform::*;
 
 pub struct ConstraintContext<'a, 'tcx: 'a> {
@@ -209,7 +208,6 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
     fn declared_variance(&self,
                          param_def_id: DefId,
                          item_def_id: DefId,
-                         kind: ParamKind,
                          index: usize)
                          -> VarianceTermPtr<'a> {
         assert_eq!(param_def_id.krate, item_def_id.krate);
@@ -224,11 +222,7 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
             // Parameter on an item defined within another crate:
             // variance already inferred, just look it up.
             let variances = self.tcx().item_variances(item_def_id);
-            let variance = match kind {
-                TypeParam => variances.types[index],
-                RegionParam => variances.regions[index],
-            };
-            self.constant_term(variance)
+            self.constant_term(variances[index])
         }
     }
 
@@ -330,7 +324,7 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
 
             ty::TyRef(region, ref mt) => {
                 let contra = self.contravariant(variance);
-                self.add_constraints_from_region(generics, *region, contra);
+                self.add_constraints_from_region(generics, region, contra);
                 self.add_constraints_from_mt(generics, mt, variance);
             }
 
@@ -401,8 +395,11 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
 
             ty::TyParam(ref data) => {
                 assert_eq!(generics.parent, None);
-                assert!((data.idx as usize) < generics.types.len());
-                let def_id = generics.types[data.idx as usize].def_id;
+                let mut i = data.idx as usize;
+                if !generics.has_self || i > 0 {
+                    i -= generics.regions.len();
+                }
+                let def_id = generics.types[i].def_id;
                 let node_id = self.tcx().map.as_local_node_id(def_id).unwrap();
                 match self.terms_cx.inferred_map.get(&node_id) {
                     Some(&index) => {
@@ -449,7 +446,7 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
 
         for p in type_param_defs {
             let variance_decl =
-                self.declared_variance(p.def_id, def_id, TypeParam, p.index as usize);
+                self.declared_variance(p.def_id, def_id, p.index as usize);
             let variance_i = self.xform(variance, variance_decl);
             let substs_ty = substs.type_for_def(p);
             debug!("add_constraints_from_substs: variance_decl={:?} variance_i={:?}",
@@ -459,7 +456,7 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
 
         for p in region_param_defs {
             let variance_decl =
-                self.declared_variance(p.def_id, def_id, RegionParam, p.index as usize);
+                self.declared_variance(p.def_id, def_id, p.index as usize);
             let variance_i = self.xform(variance, variance_decl);
             let substs_r = substs.region_for_def(p);
             self.add_constraints_from_region(generics, substs_r, variance_i);
@@ -488,8 +485,8 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
         match *region {
             ty::ReEarlyBound(ref data) => {
                 assert_eq!(generics.parent, None);
-                assert!((data.index as usize) < generics.regions.len());
-                let def_id = generics.regions[data.index as usize].def_id;
+                let i = data.index as usize - generics.has_self as usize;
+                let def_id = generics.regions[i].def_id;
                 let node_id = self.tcx().map.as_local_node_id(def_id).unwrap();
                 if self.is_to_be_inferred(node_id) {
                     let index = self.inferred_index(node_id);
diff --git a/src/librustc_typeck/variance/solve.rs b/src/librustc_typeck/variance/solve.rs
index d3b63119bcb..82b63d0cc09 100644
--- a/src/librustc_typeck/variance/solve.rs
+++ b/src/librustc_typeck/variance/solve.rs
@@ -21,7 +21,6 @@ use std::rc::Rc;
 use super::constraints::*;
 use super::terms::*;
 use super::terms::VarianceTerm::*;
-use super::terms::ParamKind::*;
 use super::xform::*;
 
 struct SolveContext<'a, 'tcx: 'a> {
@@ -109,24 +108,16 @@ impl<'a, 'tcx> SolveContext<'a, 'tcx> {
         while index < num_inferred {
             let item_id = inferred_infos[index].item_id;
 
-            let mut item_variances = ty::ItemVariances::empty();
+            let mut item_variances = vec![];
 
             while index < num_inferred && inferred_infos[index].item_id == item_id {
                 let info = &inferred_infos[index];
                 let variance = solutions[index];
-                debug!("Index {} Info {} / {:?} Variance {:?}",
-                       index, info.index, info.kind, variance);
-                match info.kind {
-                    TypeParam => {
-                        assert_eq!(item_variances.types.len(), info.index);
-                        item_variances.types.push(variance);
-                    }
-                    RegionParam => {
-                        assert_eq!(item_variances.regions.len(), info.index);
-                        item_variances.regions.push(variance);
-                    }
-                }
+                debug!("Index {} Info {} Variance {:?}",
+                       index, info.index, variance);
 
+                assert_eq!(item_variances.len(), info.index);
+                item_variances.push(variance);
                 index += 1;
             }
 
diff --git a/src/librustc_typeck/variance/terms.rs b/src/librustc_typeck/variance/terms.rs
index d30cbc8f117..c0b53787177 100644
--- a/src/librustc_typeck/variance/terms.rs
+++ b/src/librustc_typeck/variance/terms.rs
@@ -31,7 +31,6 @@ use rustc::hir::intravisit::Visitor;
 use util::nodemap::NodeMap;
 
 use self::VarianceTerm::*;
-use self::ParamKind::*;
 
 pub type VarianceTermPtr<'a> = &'a VarianceTerm<'a>;
 
@@ -61,7 +60,7 @@ pub struct TermsContext<'a, 'tcx: 'a> {
     pub tcx: TyCtxt<'a, 'tcx, 'tcx>,
     pub arena: &'a TypedArena<VarianceTerm<'a>>,
 
-    pub empty_variances: Rc<ty::ItemVariances>,
+    pub empty_variances: Rc<Vec<ty::Variance>>,
 
     // For marker types, UnsafeCell, and other lang items where
     // variance is hardcoded, records the item-id and the hardcoded
@@ -76,15 +75,8 @@ pub struct TermsContext<'a, 'tcx: 'a> {
     pub inferred_infos: Vec<InferredInfo<'a>> ,
 }
 
-#[derive(Copy, Clone, Debug, PartialEq)]
-pub enum ParamKind {
-    TypeParam,
-    RegionParam,
-}
-
 pub struct InferredInfo<'a> {
     pub item_id: ast::NodeId,
-    pub kind: ParamKind,
     pub index: usize,
     pub param_id: ast::NodeId,
     pub term: VarianceTermPtr<'a>,
@@ -110,7 +102,7 @@ pub fn determine_parameters_to_be_inferred<'a, 'tcx>(
 
         // cache and share the variance struct used for items with
         // no type/region parameters
-        empty_variances: Rc::new(ty::ItemVariances::empty())
+        empty_variances: Rc::new(vec![])
     };
 
     // See README.md for a discussion on dep-graph management.
@@ -162,17 +154,19 @@ impl<'a, 'tcx> TermsContext<'a, 'tcx> {
 
         let inferreds_on_entry = self.num_inferred();
 
+        if has_self {
+            self.add_inferred(item_id, 0, item_id);
+        }
+
         for (i, p) in generics.lifetimes.iter().enumerate() {
             let id = p.lifetime.id;
-            self.add_inferred(item_id, RegionParam, i, id);
+            let i = has_self as usize + i;
+            self.add_inferred(item_id, i, id);
         }
 
-        if has_self {
-            self.add_inferred(item_id, TypeParam, 0, item_id);
-        }
         for (i, p) in generics.ty_params.iter().enumerate() {
-            let i = has_self as usize + i;
-            self.add_inferred(item_id, TypeParam, i, p.id);
+            let i = has_self as usize + generics.lifetimes.len() + i;
+            self.add_inferred(item_id, i, p.id);
         }
 
         // If this item has no type or lifetime parameters,
@@ -194,14 +188,12 @@ impl<'a, 'tcx> TermsContext<'a, 'tcx> {
 
     fn add_inferred(&mut self,
                     item_id: ast::NodeId,
-                    kind: ParamKind,
                     index: usize,
                     param_id: ast::NodeId) {
         let inf_index = InferredIndex(self.inferred_infos.len());
         let term = self.arena.alloc(InferredTerm(inf_index));
         let initial_variance = self.pick_initial_variance(item_id, index);
         self.inferred_infos.push(InferredInfo { item_id: item_id,
-                                                kind: kind,
                                                 index: index,
                                                 param_id: param_id,
                                                 term: term,
@@ -211,13 +203,12 @@ impl<'a, 'tcx> TermsContext<'a, 'tcx> {
 
         debug!("add_inferred(item_path={}, \
                 item_id={}, \
-                kind={:?}, \
                 index={}, \
                 param_id={}, \
                 inf_index={:?}, \
                 initial_variance={:?})",
                self.tcx.item_path_str(self.tcx.map.local_def_id(item_id)),
-               item_id, kind, index, param_id, inf_index,
+               item_id, index, param_id, inf_index,
                initial_variance);
     }
 
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index e0a6f40c860..c8620254b6f 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -643,7 +643,7 @@ impl Clean<TyParamBound> for hir::TyParamBound {
 fn external_path_params(cx: &DocContext, trait_did: Option<DefId>, has_self: bool,
                         bindings: Vec<TypeBinding>, substs: &Substs) -> PathParameters {
     let lifetimes = substs.regions().filter_map(|v| v.clean(cx)).collect();
-    let types = substs.types().skip(has_self as usize).cloned().collect::<Vec<_>>();
+    let types = substs.types().skip(has_self as usize).collect::<Vec<_>>();
 
     match (trait_did, cx.tcx_opt()) {
         // Attempt to sugar an external path like Fn<(A, B,), C> to Fn(A, B) -> C
@@ -741,7 +741,7 @@ impl<'tcx> Clean<TyParamBound> for ty::TraitRef<'tcx> {
 
         // collect any late bound regions
         let mut late_bounds = vec![];
-        for &ty_s in self.input_types().skip(1) {
+        for ty_s in self.input_types().skip(1) {
             if let ty::TyTuple(ts) = ty_s.sty {
                 for &ty_s in ts {
                     if let ty::TyRef(ref reg, _) = ty_s.sty {
diff --git a/src/test/compile-fail/variance-associated-types.rs b/src/test/compile-fail/variance-associated-types.rs
index 5539a26d2a1..7dbfc6ac125 100644
--- a/src/test/compile-fail/variance-associated-types.rs
+++ b/src/test/compile-fail/variance-associated-types.rs
@@ -20,12 +20,12 @@ trait Trait<'a> {
 }
 
 #[rustc_variance]
-struct Foo<'a, T : Trait<'a>> { //~ ERROR ItemVariances(types=[+], regions=[-])
+struct Foo<'a, T : Trait<'a>> { //~ ERROR [-, +]
     field: (T, &'a ())
 }
 
 #[rustc_variance]
-struct Bar<'a, T : Trait<'a>> { //~ ERROR ItemVariances(types=[o], regions=[o])
+struct Bar<'a, T : Trait<'a>> { //~ ERROR [o, o]
     field: <T as Trait<'a>>::Type
 }
 
diff --git a/src/test/compile-fail/variance-object-types.rs b/src/test/compile-fail/variance-object-types.rs
index 2f422bfd38c..1f54771e367 100644
--- a/src/test/compile-fail/variance-object-types.rs
+++ b/src/test/compile-fail/variance-object-types.rs
@@ -18,7 +18,7 @@ use std::cell::Cell;
 // For better or worse, associated types are invariant, and hence we
 // get an invariant result for `'a`.
 #[rustc_variance]
-struct Foo<'a> { //~ ERROR regions=[o]
+struct Foo<'a> { //~ ERROR [o]
     x: Box<Fn(i32) -> &'a i32 + 'static>
 }
 
diff --git a/src/test/compile-fail/variance-region-bounds.rs b/src/test/compile-fail/variance-region-bounds.rs
index 99416057b25..41d204a541b 100644
--- a/src/test/compile-fail/variance-region-bounds.rs
+++ b/src/test/compile-fail/variance-region-bounds.rs
@@ -13,11 +13,11 @@
 #![feature(rustc_attrs)]
 
 #[rustc_variance]
-trait Foo: 'static { //~ ERROR types=[o]
+trait Foo: 'static { //~ ERROR [o]
 }
 
 #[rustc_variance]
-trait Bar<T> { //~ ERROR types=[o, o]
+trait Bar<T> { //~ ERROR [o, o]
     fn do_it(&self)
         where T: 'static;
 }
diff --git a/src/test/compile-fail/variance-regions-direct.rs b/src/test/compile-fail/variance-regions-direct.rs
index 78591063de8..bf46edcfab8 100644
--- a/src/test/compile-fail/variance-regions-direct.rs
+++ b/src/test/compile-fail/variance-regions-direct.rs
@@ -16,7 +16,7 @@
 // Regions that just appear in normal spots are contravariant:
 
 #[rustc_variance]
-struct Test2<'a, 'b, 'c> { //~ ERROR regions=[-, -, -]
+struct Test2<'a, 'b, 'c> { //~ ERROR [-, -, -]
     x: &'a isize,
     y: &'b [isize],
     c: &'c str
@@ -25,7 +25,7 @@ struct Test2<'a, 'b, 'c> { //~ ERROR regions=[-, -, -]
 // Those same annotations in function arguments become covariant:
 
 #[rustc_variance]
-struct Test3<'a, 'b, 'c> { //~ ERROR regions=[+, +, +]
+struct Test3<'a, 'b, 'c> { //~ ERROR [+, +, +]
     x: extern "Rust" fn(&'a isize),
     y: extern "Rust" fn(&'b [isize]),
     c: extern "Rust" fn(&'c str),
@@ -34,7 +34,7 @@ struct Test3<'a, 'b, 'c> { //~ ERROR regions=[+, +, +]
 // Mutability induces invariance:
 
 #[rustc_variance]
-struct Test4<'a, 'b:'a> { //~ ERROR regions=[-, o]
+struct Test4<'a, 'b:'a> { //~ ERROR [-, o]
     x: &'a mut &'b isize,
 }
 
@@ -42,7 +42,7 @@ struct Test4<'a, 'b:'a> { //~ ERROR regions=[-, o]
 // contravariant context:
 
 #[rustc_variance]
-struct Test5<'a, 'b:'a> { //~ ERROR regions=[+, o]
+struct Test5<'a, 'b:'a> { //~ ERROR [+, o]
     x: extern "Rust" fn(&'a mut &'b isize),
 }
 
@@ -52,14 +52,14 @@ struct Test5<'a, 'b:'a> { //~ ERROR regions=[+, o]
 // argument list occurs in an invariant context.
 
 #[rustc_variance]
-struct Test6<'a, 'b:'a> { //~ ERROR regions=[-, o]
+struct Test6<'a, 'b:'a> { //~ ERROR [-, o]
     x: &'a mut extern "Rust" fn(&'b isize),
 }
 
 // No uses at all is bivariant:
 
 #[rustc_variance]
-struct Test7<'a> { //~ ERROR regions=[*]
+struct Test7<'a> { //~ ERROR [*]
     //~^ ERROR parameter `'a` is never used
     x: isize
 }
@@ -67,7 +67,7 @@ struct Test7<'a> { //~ ERROR regions=[*]
 // Try enums too.
 
 #[rustc_variance]
-enum Test8<'a, 'b, 'c:'b> { //~ ERROR regions=[+, -, o]
+enum Test8<'a, 'b, 'c:'b> { //~ ERROR [+, -, o]
     Test8A(extern "Rust" fn(&'a isize)),
     Test8B(&'b [isize]),
     Test8C(&'b mut &'c str),
diff --git a/src/test/compile-fail/variance-regions-indirect.rs b/src/test/compile-fail/variance-regions-indirect.rs
index d8af30da163..e28828f62e5 100644
--- a/src/test/compile-fail/variance-regions-indirect.rs
+++ b/src/test/compile-fail/variance-regions-indirect.rs
@@ -15,7 +15,7 @@
 #![feature(rustc_attrs)]
 
 #[rustc_variance]
-enum Base<'a, 'b, 'c:'b, 'd> { //~ ERROR regions=[+, -, o, *]
+enum Base<'a, 'b, 'c:'b, 'd> { //~ ERROR [+, -, o, *]
     //~^ ERROR parameter `'d` is never used
     Test8A(extern "Rust" fn(&'a isize)),
     Test8B(&'b [isize]),
@@ -23,25 +23,25 @@ enum Base<'a, 'b, 'c:'b, 'd> { //~ ERROR regions=[+, -, o, *]
 }
 
 #[rustc_variance]
-struct Derived1<'w, 'x:'y, 'y, 'z> { //~ ERROR regions=[*, o, -, +]
+struct Derived1<'w, 'x:'y, 'y, 'z> { //~ ERROR [*, o, -, +]
     //~^ ERROR parameter `'w` is never used
     f: Base<'z, 'y, 'x, 'w>
 }
 
 #[rustc_variance] // Combine - and + to yield o
-struct Derived2<'a, 'b:'a, 'c> { //~ ERROR regions=[o, o, *]
+struct Derived2<'a, 'b:'a, 'c> { //~ ERROR [o, o, *]
     //~^ ERROR parameter `'c` is never used
     f: Base<'a, 'a, 'b, 'c>
 }
 
 #[rustc_variance] // Combine + and o to yield o (just pay attention to 'a here)
-struct Derived3<'a:'b, 'b, 'c> { //~ ERROR regions=[o, -, *]
+struct Derived3<'a:'b, 'b, 'c> { //~ ERROR [o, -, *]
     //~^ ERROR parameter `'c` is never used
     f: Base<'a, 'b, 'a, 'c>
 }
 
 #[rustc_variance] // Combine + and * to yield + (just pay attention to 'a here)
-struct Derived4<'a, 'b, 'c:'b> { //~ ERROR regions=[+, -, o]
+struct Derived4<'a, 'b, 'c:'b> { //~ ERROR [+, -, o]
     f: Base<'a, 'b, 'c, 'a>
 }
 
diff --git a/src/test/compile-fail/variance-trait-bounds.rs b/src/test/compile-fail/variance-trait-bounds.rs
index 150a1aa56fe..4c737a7594d 100644
--- a/src/test/compile-fail/variance-trait-bounds.rs
+++ b/src/test/compile-fail/variance-trait-bounds.rs
@@ -15,48 +15,48 @@
 // influence variance.
 
 #[rustc_variance]
-trait Getter<T> { //~ ERROR types=[o, o]
+trait Getter<T> { //~ ERROR [o, o]
     fn get(&self) -> T;
 }
 
 #[rustc_variance]
-trait Setter<T> { //~ ERROR types=[o, o]
+trait Setter<T> { //~ ERROR [o, o]
     fn get(&self, T);
 }
 
 #[rustc_variance]
-struct TestStruct<U,T:Setter<U>> { //~ ERROR types=[+, +]
+struct TestStruct<U,T:Setter<U>> { //~ ERROR [+, +]
     t: T, u: U
 }
 
 #[rustc_variance]
-enum TestEnum<U,T:Setter<U>> {//~ ERROR types=[*, +]
+enum TestEnum<U,T:Setter<U>> {//~ ERROR [*, +]
     //~^ ERROR parameter `U` is never used
     Foo(T)
 }
 
 #[rustc_variance]
-trait TestTrait<U,T:Setter<U>> { //~ ERROR types=[o, o, o]
+trait TestTrait<U,T:Setter<U>> { //~ ERROR [o, o, o]
     fn getter(&self, u: U) -> T;
 }
 
 #[rustc_variance]
-trait TestTrait2<U> : Getter<U> { //~ ERROR types=[o, o]
+trait TestTrait2<U> : Getter<U> { //~ ERROR [o, o]
 }
 
 #[rustc_variance]
-trait TestTrait3<U> { //~ ERROR types=[o, o]
+trait TestTrait3<U> { //~ ERROR [o, o]
     fn getter<T:Getter<U>>(&self);
 }
 
 #[rustc_variance]
-struct TestContraStruct<U,T:Setter<U>> { //~ ERROR types=[*, +]
+struct TestContraStruct<U,T:Setter<U>> { //~ ERROR [*, +]
     //~^ ERROR parameter `U` is never used
     t: T
 }
 
 #[rustc_variance]
-struct TestBox<U,T:Getter<U>+Setter<U>> { //~ ERROR types=[*, +]
+struct TestBox<U,T:Getter<U>+Setter<U>> { //~ ERROR [*, +]
     //~^ ERROR parameter `U` is never used
     t: T
 }
diff --git a/src/test/compile-fail/variance-trait-object-bound.rs b/src/test/compile-fail/variance-trait-object-bound.rs
index 4244b0e1d8b..b120588ecab 100644
--- a/src/test/compile-fail/variance-trait-object-bound.rs
+++ b/src/test/compile-fail/variance-trait-object-bound.rs
@@ -21,7 +21,7 @@ use std::mem;
 trait T { fn foo(&self); }
 
 #[rustc_variance]
-struct TOption<'a> { //~ ERROR regions=[-]
+struct TOption<'a> { //~ ERROR [-]
     v: Option<Box<T + 'a>>,
 }
 
diff --git a/src/test/compile-fail/variance-types-bounds.rs b/src/test/compile-fail/variance-types-bounds.rs
index c47710d6d37..2df94cc907a 100644
--- a/src/test/compile-fail/variance-types-bounds.rs
+++ b/src/test/compile-fail/variance-types-bounds.rs
@@ -14,46 +14,46 @@
 #![feature(rustc_attrs)]
 
 #[rustc_variance]
-struct TestImm<A, B> { //~ ERROR types=[+, +]
+struct TestImm<A, B> { //~ ERROR [+, +]
     x: A,
     y: B,
 }
 
 #[rustc_variance]
-struct TestMut<A, B:'static> { //~ ERROR types=[+, o]
+struct TestMut<A, B:'static> { //~ ERROR [+, o]
     x: A,
     y: &'static mut B,
 }
 
 #[rustc_variance]
-struct TestIndirect<A:'static, B:'static> { //~ ERROR types=[+, o]
+struct TestIndirect<A:'static, B:'static> { //~ ERROR [+, o]
     m: TestMut<A, B>
 }
 
 #[rustc_variance]
-struct TestIndirect2<A:'static, B:'static> { //~ ERROR types=[o, o]
+struct TestIndirect2<A:'static, B:'static> { //~ ERROR [o, o]
     n: TestMut<A, B>,
     m: TestMut<B, A>
 }
 
 #[rustc_variance]
-trait Getter<A> { //~ ERROR types=[o, o]
+trait Getter<A> { //~ ERROR [o, o]
     fn get(&self) -> A;
 }
 
 #[rustc_variance]
-trait Setter<A> { //~ ERROR types=[o, o]
+trait Setter<A> { //~ ERROR [o, o]
     fn set(&mut self, a: A);
 }
 
 #[rustc_variance]
-trait GetterSetter<A> { //~ ERROR types=[o, o]
+trait GetterSetter<A> { //~ ERROR [o, o]
     fn get(&self) -> A;
     fn set(&mut self, a: A);
 }
 
 #[rustc_variance]
-trait GetterInTypeBound<A> { //~ ERROR types=[o, o]
+trait GetterInTypeBound<A> { //~ ERROR [o, o]
     // Here, the use of `A` in the method bound *does* affect
     // variance.  Think of it as if the method requested a dictionary
     // for `T:Getter<A>`.  Since this dictionary is an input, it is
@@ -63,12 +63,12 @@ trait GetterInTypeBound<A> { //~ ERROR types=[o, o]
 }
 
 #[rustc_variance]
-trait SetterInTypeBound<A> { //~ ERROR types=[o, o]
+trait SetterInTypeBound<A> { //~ ERROR [o, o]
     fn do_it<T:Setter<A>>(&self);
 }
 
 #[rustc_variance]
-struct TestObject<A, R> { //~ ERROR types=[o, o]
+struct TestObject<A, R> { //~ ERROR [o, o]
     n: Box<Setter<A>+Send>,
     m: Box<Getter<R>+Send>,
 }
diff --git a/src/test/compile-fail/variance-types.rs b/src/test/compile-fail/variance-types.rs
index d5164412358..7667972c9d2 100644
--- a/src/test/compile-fail/variance-types.rs
+++ b/src/test/compile-fail/variance-types.rs
@@ -17,32 +17,32 @@ use std::cell::Cell;
 // not considered bivariant.
 
 #[rustc_variance]
-struct InvariantMut<'a,A:'a,B:'a> { //~ ERROR types=[o, o], regions=[-]
+struct InvariantMut<'a,A:'a,B:'a> { //~ ERROR [-, o, o]
     t: &'a mut (A,B)
 }
 
 #[rustc_variance]
-struct InvariantCell<A> { //~ ERROR types=[o]
+struct InvariantCell<A> { //~ ERROR [o]
     t: Cell<A>
 }
 
 #[rustc_variance]
-struct InvariantIndirect<A> { //~ ERROR types=[o]
+struct InvariantIndirect<A> { //~ ERROR [o]
     t: InvariantCell<A>
 }
 
 #[rustc_variance]
-struct Covariant<A> { //~ ERROR types=[+]
+struct Covariant<A> { //~ ERROR [+]
     t: A, u: fn() -> A
 }
 
 #[rustc_variance]
-struct Contravariant<A> { //~ ERROR types=[-]
+struct Contravariant<A> { //~ ERROR [-]
     t: fn(A)
 }
 
 #[rustc_variance]
-enum Enum<A,B,C> { //~ ERROR types=[+, -, o]
+enum Enum<A,B,C> { //~ ERROR [+, -, o]
     Foo(Covariant<A>),
     Bar(Contravariant<B>),
     Zed(Covariant<C>,Contravariant<C>)