Using a type alias of Slice<Kind<'tcx>> to intern Substs<'tcx>.

Fixing now incorrect Hash impl for TransItem.
Using as_ptr() rather than a pointer cast for string formatting.
Fixing Borrow and Lift impls for Substs.
Move usages of tcx.mk_substs to Substs::new iterator-based version.

6 files changed, 68 insertions, 99 deletions

diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index 39fc50666a8..20955dfa432 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -25,7 +25,7 @@ use middle::mem_categorization as mc;
 use middle::mem_categorization::McResult;
 use middle::region::CodeExtent;
 use mir::tcx::LvalueTy;
-use ty::subst::{Subst, Substs};
+use ty::subst::{Kind, Subst, Substs};
 use ty::adjustment;
 use ty::{TyVid, IntVid, FloatVid};
 use ty::{self, Ty, TyCtxt};
@@ -1208,7 +1208,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
     pub fn type_var_for_def(&self,
                             span: Span,
                             def: &ty::TypeParameterDef<'tcx>,
-                            substs: &Substs<'tcx>)
+                            substs: &[Kind<'tcx>])
                             -> Ty<'tcx> {
         let default = def.default.map(|default| {
             type_variable::Default {
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index b1f80455dd9..455a7cefdc5 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -22,7 +22,7 @@ use middle::free_region::FreeRegionMap;
 use middle::region::RegionMaps;
 use middle::resolve_lifetime;
 use middle::stability;
-use ty::subst::Substs;
+use ty::subst::{Kind, Substs};
 use traits;
 use ty::{self, TraitRef, Ty, TypeAndMut};
 use ty::{TyS, TypeVariants, Slice};
@@ -55,7 +55,7 @@ pub struct CtxtArenas<'tcx> {
     // internings
     type_: TypedArena<TyS<'tcx>>,
     type_list: TypedArena<Vec<Ty<'tcx>>>,
-    substs: TypedArena<Substs<'tcx>>,
+    substs: TypedArena<Vec<Kind<'tcx>>>,
     bare_fn: TypedArena<BareFnTy<'tcx>>,
     region: TypedArena<Region>,
     stability: TypedArena<attr::Stability>,
@@ -824,7 +824,7 @@ impl<'a, 'tcx> Lift<'tcx> for Ty<'a> {
 impl<'a, 'tcx> Lift<'tcx> for &'a Substs<'a> {
     type Lifted = &'tcx Substs<'tcx>;
     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<&'tcx Substs<'tcx>> {
-        if let Some(&Interned(substs)) = tcx.interners.substs.borrow().get(*self) {
+        if let Some(&Interned(substs)) = tcx.interners.substs.borrow().get(&self[..]) {
             if *self as *const _ == substs as *const _ {
                 return Some(substs);
             }
@@ -1097,9 +1097,9 @@ impl<'tcx: 'lcx, 'lcx> Borrow<[Ty<'lcx>]> for Interned<'tcx, Slice<Ty<'tcx>>> {
     }
 }
 
-impl<'tcx: 'lcx, 'lcx> Borrow<Substs<'lcx>> for Interned<'tcx, Substs<'tcx>> {
-    fn borrow<'a>(&'a self) -> &'a Substs<'lcx> {
-        self.0
+impl<'tcx: 'lcx, 'lcx> Borrow<[Kind<'lcx>]> for Interned<'tcx, Substs<'tcx>> {
+    fn borrow<'a>(&'a self) -> &'a [Kind<'lcx>] {
+        &self.0[..]
     }
 }
 
@@ -1189,9 +1189,6 @@ fn keep_local<'tcx, T: ty::TypeFoldable<'tcx>>(x: &T) -> bool {
 }
 
 direct_interners!('tcx,
-    substs: mk_substs(|substs: &Substs| {
-        substs.params().iter().any(keep_local)
-    }) -> Substs<'tcx>,
     bare_fn: mk_bare_fn(|fty: &BareFnTy| {
         keep_local(&fty.sig)
     }) -> BareFnTy<'tcx>,
@@ -1209,6 +1206,12 @@ intern_method!('tcx,
     }, keep_local) -> Slice<Ty<'tcx>>
 );
 
+intern_method!('tcx,
+    substs: mk_substs(Vec<Kind<'tcx>>, Deref::deref, |xs: &[Kind]| -> &Slice<Kind> {
+        unsafe { mem::transmute(xs) }
+    }, keep_local) -> Slice<Kind<'tcx>>
+);
+
 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
     /// Create an unsafe fn ty based on a safe fn ty.
     pub fn safe_to_unsafe_fn_ty(self, bare_fn: &BareFnTy<'tcx>) -> Ty<'tcx> {
diff --git a/src/librustc/ty/subst.rs b/src/librustc/ty/subst.rs
index 6911d217426..14deb6820ee 100644
--- a/src/librustc/ty/subst.rs
+++ b/src/librustc/ty/subst.rs
@@ -11,7 +11,7 @@
 // Type substitutions.
 
 use hir::def_id::DefId;
-use ty::{self, Ty, TyCtxt};
+use ty::{self, Slice, Ty, TyCtxt};
 use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
 
 use serialize::{self, Encodable, Encoder, Decodable, Decoder};
@@ -161,26 +161,19 @@ impl<'tcx> Decodable for Kind<'tcx> {
 }
 
 /// A substitution mapping type/region parameters to new values.
-#[derive(Clone, PartialEq, Eq, Debug, Hash, RustcEncodable, RustcDecodable)]
-pub struct Substs<'tcx> {
-    params: Vec<Kind<'tcx>>
-}
+pub type Substs<'tcx> = Slice<Kind<'tcx>>;
 
 impl<'a, 'gcx, 'tcx> Substs<'tcx> {
     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()
-        })
+        tcx.mk_substs(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<_, _>>()?
-        }))
+        Ok(Substs::new(tcx, params.into_iter().collect::<Result<Vec<_>, _>>()?))
     }
 
     pub fn new_trait(tcx: TyCtxt<'a, 'gcx, 'tcx>,
@@ -193,7 +186,7 @@ impl<'a, 'gcx, 'tcx> Substs<'tcx> {
     }
 
     pub fn empty(tcx: TyCtxt<'a, 'gcx, 'tcx>) -> &'tcx Substs<'tcx> {
-        Substs::new(tcx, vec![])
+        Substs::new(tcx, iter::empty())
     }
 
     /// Creates a Substs for generic parameter definitions,
@@ -206,82 +199,81 @@ impl<'a, 'gcx, 'tcx> Substs<'tcx> {
                             mut mk_region: FR,
                             mut mk_type: FT)
                             -> &'tcx Substs<'tcx>
-    where FR: FnMut(&ty::RegionParameterDef, &Substs<'tcx>) -> &'tcx ty::Region,
-          FT: FnMut(&ty::TypeParameterDef<'tcx>, &Substs<'tcx>) -> Ty<'tcx> {
+    where FR: FnMut(&ty::RegionParameterDef, &[Kind<'tcx>]) -> &'tcx ty::Region,
+          FT: FnMut(&ty::TypeParameterDef<'tcx>, &[Kind<'tcx>]) -> Ty<'tcx> {
         let defs = tcx.lookup_generics(def_id);
-        let mut substs = Substs {
-            params: Vec::with_capacity(defs.count())
-        };
+        let mut substs = Vec::with_capacity(defs.count());
 
-        substs.fill_item(tcx, defs, &mut mk_region, &mut mk_type);
+        Substs::fill_item(&mut substs, tcx, defs, &mut mk_region, &mut mk_type);
 
-        tcx.mk_substs(substs)
+        Substs::new(tcx, substs)
     }
 
-    fn fill_item<FR, FT>(&mut self,
+    fn fill_item<FR, FT>(substs: &mut Vec<Kind<'tcx>>,
                          tcx: TyCtxt<'a, 'gcx, 'tcx>,
                          defs: &ty::Generics<'tcx>,
                          mk_region: &mut FR,
                          mk_type: &mut FT)
-    where FR: FnMut(&ty::RegionParameterDef, &Substs<'tcx>) -> &'tcx ty::Region,
-          FT: FnMut(&ty::TypeParameterDef<'tcx>, &Substs<'tcx>) -> Ty<'tcx> {
+    where FR: FnMut(&ty::RegionParameterDef, &[Kind<'tcx>]) -> &'tcx ty::Region,
+          FT: FnMut(&ty::TypeParameterDef<'tcx>, &[Kind<'tcx>]) -> Ty<'tcx> {
+
         if let Some(def_id) = defs.parent {
             let parent_defs = tcx.lookup_generics(def_id);
-            self.fill_item(tcx, parent_defs, mk_region, mk_type);
+            Substs::fill_item(substs, 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));
+            let ty = mk_type(def, substs);
+            assert_eq!(def.index as usize, substs.len());
+            substs.push(Kind::from(ty));
         }
 
         for def in &defs.regions {
-            let region = mk_region(def, self);
-            assert_eq!(def.index as usize, self.params.len());
-            self.params.push(Kind::from(region));
+            let region = mk_region(def, substs);
+            assert_eq!(def.index as usize, substs.len());
+            substs.push(Kind::from(region));
         }
 
         for def in types {
-            let ty = mk_type(def, self);
-            assert_eq!(def.index as usize, self.params.len());
-            self.params.push(Kind::from(ty));
+            let ty = mk_type(def, substs);
+            assert_eq!(def.index as usize, substs.len());
+            substs.push(Kind::from(ty));
         }
     }
 
     pub fn is_noop(&self) -> bool {
-        self.params.is_empty()
+        self.is_empty()
     }
 
     #[inline]
     pub fn params(&self) -> &[Kind<'tcx>] {
-        &self.params
+        &self
     }
 
     #[inline]
     pub fn types(&'a self) -> impl DoubleEndedIterator<Item=Ty<'tcx>> + 'a {
-        self.params.iter().filter_map(|k| k.as_type())
+        self.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())
+        self.iter().filter_map(|k| k.as_region())
     }
 
     #[inline]
     pub fn type_at(&self, i: usize) -> Ty<'tcx> {
-        self.params[i].as_type().unwrap_or_else(|| {
-            bug!("expected type for param #{} in {:?}", i, self.params);
+        self[i].as_type().unwrap_or_else(|| {
+            bug!("expected type for param #{} in {:?}", i, self);
         })
     }
 
     #[inline]
     pub fn region_at(&self, i: usize) -> &'tcx ty::Region {
-        self.params[i].as_region().unwrap_or_else(|| {
-            bug!("expected region for param #{} in {:?}", i, self.params);
+        self[i].as_region().unwrap_or_else(|| {
+            bug!("expected region for param #{} in {:?}", i, self);
         })
     }
 
@@ -305,19 +297,14 @@ impl<'a, 'gcx, 'tcx> Substs<'tcx> {
                        target_substs: &Substs<'tcx>)
                        -> &'tcx Substs<'tcx> {
         let defs = tcx.lookup_generics(source_ancestor);
-        tcx.mk_substs(Substs {
-            params: target_substs.params.iter()
-                .chain(&self.params[defs.own_count()..]).cloned().collect()
-        })
+        Substs::new(tcx, target_substs.iter().chain(&self[defs.own_count()..]).cloned())
     }
 }
 
 impl<'tcx> TypeFoldable<'tcx> for &'tcx Substs<'tcx> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
-        let params = self.params.iter().map(|k| k.fold_with(folder)).collect();
-        folder.tcx().mk_substs(Substs {
-            params: params
-        })
+        let params = self.iter().map(|k| k.fold_with(folder)).collect();
+        folder.tcx().mk_substs(params)
     }
 
     fn fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
@@ -325,7 +312,7 @@ impl<'tcx> TypeFoldable<'tcx> for &'tcx Substs<'tcx> {
     }
 
     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
-        self.params.visit_with(visitor)
+        self.iter().any(|t| t.visit_with(visitor))
     }
 }
 
@@ -340,19 +327,19 @@ impl<'tcx> serialize::UseSpecializedDecodable for &'tcx Substs<'tcx> {}
 
 pub trait Subst<'tcx> : Sized {
     fn subst<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
-                      substs: &Substs<'tcx>) -> Self {
+                      substs: &[Kind<'tcx>]) -> Self {
         self.subst_spanned(tcx, substs, None)
     }
 
     fn subst_spanned<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
-                               substs: &Substs<'tcx>,
+                               substs: &[Kind<'tcx>],
                                span: Option<Span>)
                                -> Self;
 }
 
 impl<'tcx, T:TypeFoldable<'tcx>> Subst<'tcx> for T {
     fn subst_spanned<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
-                               substs: &Substs<'tcx>,
+                               substs: &[Kind<'tcx>],
                                span: Option<Span>)
                                -> T
     {
@@ -371,7 +358,7 @@ impl<'tcx, T:TypeFoldable<'tcx>> Subst<'tcx> for T {
 
 struct SubstFolder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     tcx: TyCtxt<'a, 'gcx, 'tcx>,
-    substs: &'a Substs<'tcx>,
+    substs: &'a [Kind<'tcx>],
 
     // The location for which the substitution is performed, if available.
     span: Option<Span>,
@@ -404,7 +391,7 @@ impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for SubstFolder<'a, 'gcx, 'tcx> {
         // the specialized routine `ty::replace_late_regions()`.
         match *r {
             ty::ReEarlyBound(data) => {
-                let r = self.substs.params.get(data.index as usize)
+                let r = self.substs.get(data.index as usize)
                             .and_then(|k| k.as_region());
                 match r {
                     Some(r) => {
@@ -461,7 +448,7 @@ 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.params.get(p.idx as usize)
+        let opt_ty = self.substs.get(p.idx as usize)
                          .and_then(|k| k.as_type());
         let ty = match opt_ty {
             Some(t) => t,
@@ -475,7 +462,7 @@ impl<'a, 'gcx, 'tcx> SubstFolder<'a, 'gcx, 'tcx> {
                     source_ty,
                     p.idx,
                     self.root_ty,
-                    self.substs.params);
+                    self.substs);
             }
         };
 
@@ -552,7 +539,7 @@ impl<'a, 'gcx, 'tcx> ty::TraitRef<'tcx> {
                        -> ty::TraitRef<'tcx> {
         let defs = tcx.lookup_generics(trait_id);
 
-        let params = substs.params[..defs.own_count()].iter().cloned();
+        let params = substs[..defs.own_count()].iter().cloned();
         ty::TraitRef {
             def_id: trait_id,
             substs: Substs::new(tcx, params)
@@ -567,7 +554,7 @@ impl<'a, 'gcx, 'tcx> ty::ExistentialTraitRef<'tcx> {
         // Assert there is a Self.
         trait_ref.substs.type_at(0);
 
-        let params = trait_ref.substs.params[1..].iter().cloned();
+        let params = trait_ref.substs[1..].iter().cloned();
         ty::ExistentialTraitRef {
             def_id: trait_ref.def_id,
             substs: Substs::new(tcx, params)
@@ -587,7 +574,7 @@ impl<'a, 'gcx, 'tcx> ty::PolyExistentialTraitRef<'tcx> {
         assert!(!self_ty.has_escaping_regions());
 
         self.map_bound(|trait_ref| {
-            let params = trait_ref.substs.params.iter().cloned();
+            let params = trait_ref.substs.iter().cloned();
             let params = iter::once(Kind::from(self_ty)).chain(params);
             ty::TraitRef {
                 def_id: trait_ref.def_id,
diff --git a/src/librustc_trans/trans_item.rs b/src/librustc_trans/trans_item.rs
index 5c7cbbbd88d..3f3268bb569 100644
--- a/src/librustc_trans/trans_item.rs
+++ b/src/librustc_trans/trans_item.rs
@@ -28,7 +28,6 @@ use rustc::hir::def_id::DefId;
 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
 use rustc::ty::subst::Substs;
 use rustc_const_eval::fatal_const_eval_err;
-use std::hash::{Hash, Hasher};
 use syntax::ast::{self, NodeId};
 use syntax::attr;
 use type_of;
@@ -36,33 +35,13 @@ use glue;
 use abi::{Abi, FnType};
 use back::symbol_names;
 
-#[derive(PartialEq, Eq, Clone, Copy, Debug)]
+#[derive(PartialEq, Eq, Clone, Copy, Debug, Hash)]
 pub enum TransItem<'tcx> {
     DropGlue(DropGlueKind<'tcx>),
     Fn(Instance<'tcx>),
     Static(NodeId)
 }
 
-impl<'tcx> Hash for TransItem<'tcx> {
-    fn hash<H: Hasher>(&self, s: &mut H) {
-        match *self {
-            TransItem::DropGlue(t) => {
-                0u8.hash(s);
-                t.hash(s);
-            },
-            TransItem::Fn(instance) => {
-                1u8.hash(s);
-                instance.def.hash(s);
-                (instance.substs as *const _ as usize).hash(s);
-            }
-            TransItem::Static(node_id) => {
-                2u8.hash(s);
-                node_id.hash(s);
-            }
-        };
-    }
-}
-
 impl<'a, 'tcx> TransItem<'tcx> {
 
     pub fn define(&self, ccx: &CrateContext<'a, 'tcx>) {
@@ -359,7 +338,7 @@ impl<'a, 'tcx> TransItem<'tcx> {
             TransItem::Fn(instance) => {
                 format!("Fn({:?}, {})",
                          instance.def,
-                         instance.substs as *const _ as usize)
+                         instance.substs.as_ptr() as usize)
             }
             TransItem::Static(id) => {
                 format!("Static({:?})", id)
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index 568e44a9519..4e780537706 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -55,7 +55,7 @@ use hir::def_id::DefId;
 use hir::print as pprust;
 use middle::resolve_lifetime as rl;
 use rustc::lint;
-use rustc::ty::subst::{Subst, Substs};
+use rustc::ty::subst::{Kind, Subst, Substs};
 use rustc::traits;
 use rustc::ty::{self, Ty, TyCtxt, ToPredicate, TypeFoldable};
 use rustc::ty::wf::object_region_bounds;
@@ -124,7 +124,7 @@ pub trait AstConv<'gcx, 'tcx> {
     /// Same as ty_infer, but with a known type parameter definition.
     fn ty_infer_for_def(&self,
                         _def: &ty::TypeParameterDef<'tcx>,
-                        _substs: &Substs<'tcx>,
+                        _substs: &[Kind<'tcx>],
                         span: Span) -> Ty<'tcx> {
         self.ty_infer(span)
     }
@@ -620,7 +620,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
 
     fn convert_parenthesized_parameters(&self,
                                         rscope: &RegionScope,
-                                        region_substs: &Substs<'tcx>,
+                                        region_substs: &[Kind<'tcx>],
                                         data: &hir::ParenthesizedParameterData)
                                         -> (Ty<'tcx>, ConvertedBinding<'tcx>)
     {
@@ -1431,7 +1431,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
     fn ast_ty_arg_to_ty(&self,
                         rscope: &RegionScope,
                         def: Option<&ty::TypeParameterDef<'tcx>>,
-                        region_substs: &Substs<'tcx>,
+                        region_substs: &[Kind<'tcx>],
                         ast_ty: &hir::Ty)
                         -> Ty<'tcx>
     {
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 79c1c5fb5e2..0a810f59991 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -87,7 +87,7 @@ use hir::def::{Def, CtorKind, PathResolution};
 use hir::def_id::{DefId, LOCAL_CRATE};
 use hir::pat_util;
 use rustc::infer::{self, InferCtxt, InferOk, TypeOrigin, TypeTrace, type_variable};
-use rustc::ty::subst::{Subst, Substs};
+use rustc::ty::subst::{Kind, Subst, Substs};
 use rustc::traits::{self, Reveal};
 use rustc::ty::{ParamTy, ParameterEnvironment};
 use rustc::ty::{LvaluePreference, NoPreference, PreferMutLvalue};
@@ -1361,7 +1361,7 @@ impl<'a, 'gcx, 'tcx> AstConv<'gcx, 'tcx> for FnCtxt<'a, 'gcx, 'tcx> {
 
     fn ty_infer_for_def(&self,
                         ty_param_def: &ty::TypeParameterDef<'tcx>,
-                        substs: &Substs<'tcx>,
+                        substs: &[Kind<'tcx>],
                         span: Span) -> Ty<'tcx> {
         self.type_var_for_def(span, ty_param_def, substs)
     }