auto merge of #5141 : nikomatsakis/rust/region-syntax-expl-lifetimes, r=nikomatsakis

Major changes are:
- replace ~[ty_param] with Generics structure, which includes
  both OptVec<TyParam> and OptVec<Lifetime>;
- the use of syntax::opt_vec to avoid allocation for empty lists;

cc #4846

r? @graydon

19 files changed, 802 insertions, 488 deletions

diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index 744cb92fb1c..f97244c477b 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -21,6 +21,8 @@ use core::to_bytes;
 use core::to_str::ToStr;
 use std::serialize::{Encodable, Decodable, Encoder, Decoder};
 
+use opt_vec::OptVec;
+
 /* can't import macros yet, so this is copied from token.rs. See its comment
  * there. */
 macro_rules! interner_key (
@@ -96,6 +98,9 @@ impl to_bytes::IterBytes for ident {
 // Functions may or may not have names.
 pub type fn_ident = Option<ident>;
 
+#[auto_encode]
+#[auto_decode]
+#[deriving_eq]
 pub struct Lifetime {
     id: node_id,
     span: span,
@@ -135,7 +140,7 @@ pub const crate_node_id: node_id = 0;
 // typeck::collect::compute_bounds matches these against
 // the "special" built-in traits (see middle::lang_items) and
 // detects Copy, Send, Owned, and Const.
-pub enum ty_param_bound {
+pub enum TyParamBound {
     TraitTyParamBound(@Ty),
     RegionTyParamBound
 }
@@ -143,10 +148,24 @@ pub enum ty_param_bound {
 #[auto_encode]
 #[auto_decode]
 #[deriving_eq]
-pub struct ty_param {
+pub struct TyParam {
     ident: ident,
     id: node_id,
-    bounds: @~[ty_param_bound]
+    bounds: @OptVec<TyParamBound>
+}
+
+#[auto_encode]
+#[auto_decode]
+#[deriving_eq]
+pub struct Generics {
+    lifetimes: OptVec<Lifetime>,
+    ty_params: OptVec<TyParam>
+}
+
+impl Generics {
+    fn is_empty(&self) -> bool {
+        self.lifetimes.len() + self.ty_params.len() == 0
+    }
 }
 
 #[auto_encode]
@@ -273,8 +292,8 @@ pub enum pat_ {
     // records this pattern's node_id in an auxiliary
     // set (of "pat_idents that refer to nullary enums")
     pat_ident(binding_mode, @path, Option<@pat>),
-    pat_enum(@path, Option<~[@pat]>), // "none" means a * pattern where
-                                  // we don't bind the fields to names
+    pat_enum(@path, Option<~[@pat]>), /* "none" means a * pattern where
+                                       * we don't bind the fields to names */
     pat_rec(~[field_pat], bool),
     pat_struct(@path, ~[field_pat], bool),
     pat_tup(~[@pat]),
@@ -749,7 +768,7 @@ pub struct ty_method {
     attrs: ~[attribute],
     purity: purity,
     decl: fn_decl,
-    tps: ~[ty_param],
+    generics: Generics,
     self_ty: self_ty,
     id: node_id,
     span: span,
@@ -1012,7 +1031,7 @@ pub type self_ty = spanned<self_ty_>;
 pub struct method {
     ident: ident,
     attrs: ~[attribute],
-    tps: ~[ty_param],
+    generics: Generics,
     self_ty: self_ty,
     purity: purity,
     decl: fn_decl,
@@ -1248,14 +1267,14 @@ pub struct item {
 #[deriving_eq]
 pub enum item_ {
     item_const(@Ty, @expr),
-    item_fn(fn_decl, purity, ~[ty_param], blk),
+    item_fn(fn_decl, purity, Generics, blk),
     item_mod(_mod),
     item_foreign_mod(foreign_mod),
-    item_ty(@Ty, ~[ty_param]),
-    item_enum(enum_def, ~[ty_param]),
-    item_struct(@struct_def, ~[ty_param]),
-    item_trait(~[ty_param], ~[@trait_ref], ~[trait_method]),
-    item_impl(~[ty_param],
+    item_ty(@Ty, Generics),
+    item_enum(enum_def, Generics),
+    item_struct(@struct_def, Generics),
+    item_trait(Generics, ~[@trait_ref], ~[trait_method]),
+    item_impl(Generics,
               Option<@trait_ref>, // (optional) trait this impl implements
               @Ty, // self
               ~[@method]),
@@ -1302,7 +1321,7 @@ pub struct foreign_item {
 #[auto_decode]
 #[deriving_eq]
 pub enum foreign_item_ {
-    foreign_item_fn(fn_decl, purity, ~[ty_param]),
+    foreign_item_fn(fn_decl, purity, Generics),
     foreign_item_const(@Ty)
 }
 
@@ -1316,7 +1335,7 @@ pub enum inlined_item {
     ii_item(@item),
     ii_method(def_id /* impl id */, @method),
     ii_foreign(@foreign_item),
-    ii_dtor(struct_dtor, ident, ~[ty_param], def_id /* parent id */)
+    ii_dtor(struct_dtor, ident, Generics, def_id /* parent id */)
 }
 
 #[cfg(test)]
diff --git a/src/libsyntax/ast_map.rs b/src/libsyntax/ast_map.rs
index 959454841a2..abaf7025505 100644
--- a/src/libsyntax/ast_map.rs
+++ b/src/libsyntax/ast_map.rs
@@ -101,7 +101,7 @@ pub enum ast_node {
     node_arg(arg, uint),
     node_local(uint),
     // Destructor for a struct
-    node_dtor(~[ty_param], @struct_dtor, def_id, @path),
+    node_dtor(Generics, @struct_dtor, def_id, @path),
     node_block(blk),
     node_struct_ctor(@struct_def, @item, @path),
 }
diff --git a/src/libsyntax/ast_util.rs b/src/libsyntax/ast_util.rs
index 4c5c4da5142..8a1408ad9c0 100644
--- a/src/libsyntax/ast_util.rs
+++ b/src/libsyntax/ast_util.rs
@@ -16,6 +16,7 @@ use ast_util;
 use codemap::{span, BytePos, dummy_sp};
 use parse::token;
 use visit;
+use opt_vec;
 
 use core::cmp;
 use core::int;
@@ -263,13 +264,13 @@ pub fn public_methods(ms: ~[@method]) -> ~[@method] {
 pub fn trait_method_to_ty_method(method: trait_method) -> ty_method {
     match method {
         required(ref m) => (*m),
-        provided(m) => {
+        provided(ref m) => {
             ty_method {
                 ident: m.ident,
                 attrs: m.attrs,
                 purity: m.purity,
                 decl: m.decl,
-                tps: m.tps,
+                generics: copy m.generics,
                 self_ty: m.self_ty,
                 id: m.id,
                 span: m.span,
@@ -327,8 +328,9 @@ impl inlined_item_utils for inlined_item {
             ii_item(i) => (v.visit_item)(i, e, v),
             ii_foreign(i) => (v.visit_foreign_item)(i, e, v),
             ii_method(_, m) => visit::visit_method_helper(m, e, v),
-            ii_dtor(/*bad*/ copy dtor, _, /*bad*/ copy tps, parent_id) => {
-                visit::visit_struct_dtor_helper(dtor, tps, parent_id, e, v);
+            ii_dtor(/*bad*/ copy dtor, _, ref generics, parent_id) => {
+                visit::visit_struct_dtor_helper(dtor, generics,
+                                                parent_id, e, v);
             }
         }
     }
@@ -375,6 +377,11 @@ pub fn dtor_dec() -> fn_decl {
     }
 }
 
+pub fn empty_generics() -> Generics {
+    Generics {lifetimes: opt_vec::Empty,
+              ty_params: opt_vec::Empty}
+}
+
 // ______________________________________________________________________
 // Enumerating the IDs which appear in an AST
 
@@ -390,6 +397,14 @@ pub fn empty(range: id_range) -> bool {
 }
 
 pub fn id_visitor(vfn: fn@(node_id)) -> visit::vt<()> {
+    let visit_generics = fn@(generics: &Generics) {
+        for generics.ty_params.each |p| {
+            vfn(p.id);
+        }
+        for generics.lifetimes.each |p| {
+            vfn(p.id);
+        }
+    };
     visit::mk_simple_visitor(@visit::SimpleVisitor {
         visit_mod: |_m, _sp, id| vfn(id),
 
@@ -457,29 +472,25 @@ pub fn id_visitor(vfn: fn@(node_id)) -> visit::vt<()> {
             }
         },
 
-        visit_ty_params: fn@(ps: ~[ty_param]) {
-            for vec::each(ps) |p| {
-                vfn(p.id);
-            }
-        },
+        visit_generics: visit_generics,
 
         visit_fn: fn@(fk: visit::fn_kind, d: ast::fn_decl,
                       _b: ast::blk, _sp: span, id: ast::node_id) {
             vfn(id);
 
             match fk {
-                visit::fk_dtor(tps, _, self_id, parent_id) => {
-                    for vec::each(tps) |tp| { vfn(tp.id); }
+                visit::fk_dtor(ref generics, _, self_id, parent_id) => {
+                    visit_generics(generics);
                     vfn(id);
                     vfn(self_id);
                     vfn(parent_id.node);
                 }
-                visit::fk_item_fn(_, tps, _) => {
-                    for vec::each(tps) |tp| { vfn(tp.id); }
+                visit::fk_item_fn(_, ref generics, _) => {
+                    visit_generics(generics);
                 }
-                visit::fk_method(_, tps, m) => {
+                visit::fk_method(_, ref generics, m) => {
                     vfn(m.self_id);
-                    for vec::each(tps) |tp| { vfn(tp.id); }
+                    visit_generics(generics);
                 }
                 visit::fk_anon(_) |
                 visit::fk_fn_block => {
@@ -497,7 +508,9 @@ pub fn id_visitor(vfn: fn@(node_id)) -> visit::vt<()> {
         visit_trait_method: fn@(_ty_m: trait_method) {
         },
 
-        visit_struct_def: fn@(_sd: @struct_def, _id: ident, _tps: ~[ty_param],
+        visit_struct_def: fn@(_sd: @struct_def,
+                              _id: ident,
+                              _generics: &Generics,
                               _id: node_id) {
         },
 
diff --git a/src/libsyntax/ext/auto_encode.rs b/src/libsyntax/ext/auto_encode.rs
index 9e60e215174..aea39502362 100644
--- a/src/libsyntax/ext/auto_encode.rs
+++ b/src/libsyntax/ext/auto_encode.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-/*
+/*!
 
 The compiler code necessary to implement the #[auto_encode] and
 #[auto_decode] extension.  The idea here is that type-defining items may
@@ -96,6 +96,9 @@ use attr;
 use codemap::span;
 use ext::base::*;
 use parse;
+use opt_vec;
+use opt_vec::OptVec;
+use ext::build;
 
 use core::vec;
 use std::oldmap;
@@ -127,24 +130,24 @@ pub fn expand_auto_encode(
     do vec::flat_map(in_items) |item| {
         if item.attrs.any(is_auto_encode) {
             match item.node {
-                ast::item_struct(ref struct_def, ref tps) => {
+                ast::item_struct(ref struct_def, ref generics) => {
                     let ser_impl = mk_struct_ser_impl(
                         cx,
                         item.span,
                         item.ident,
                         struct_def.fields,
-                        *tps
+                        generics
                     );
 
                     ~[filter_attrs(*item), ser_impl]
                 },
-                ast::item_enum(ref enum_def, ref tps) => {
+                ast::item_enum(ref enum_def, ref generics) => {
                     let ser_impl = mk_enum_ser_impl(
                         cx,
                         item.span,
                         item.ident,
                         *enum_def,
-                        *tps
+                        generics
                     );
 
                     ~[filter_attrs(*item), ser_impl]
@@ -182,24 +185,24 @@ pub fn expand_auto_decode(
     do vec::flat_map(in_items) |item| {
         if item.attrs.any(is_auto_decode) {
             match item.node {
-                ast::item_struct(ref struct_def, ref tps) => {
+                ast::item_struct(ref struct_def, ref generics) => {
                     let deser_impl = mk_struct_deser_impl(
                         cx,
                         item.span,
                         item.ident,
                         struct_def.fields,
-                        *tps
+                        generics
                     );
 
                     ~[filter_attrs(*item), deser_impl]
                 },
-                ast::item_enum(ref enum_def, ref tps) => {
+                ast::item_enum(ref enum_def, ref generics) => {
                     let deser_impl = mk_enum_deser_impl(
                         cx,
                         item.span,
                         item.ident,
                         *enum_def,
-                        *tps
+                        generics
                     );
 
                     ~[filter_attrs(*item), deser_impl]
@@ -222,18 +225,18 @@ priv impl ext_ctxt {
         span: span,
         ident: ast::ident,
         path: @ast::path,
-        bounds: @~[ast::ty_param_bound]
-    ) -> ast::ty_param {
+        bounds: @OptVec<ast::TyParamBound>
+    ) -> ast::TyParam {
         let bound = ast::TraitTyParamBound(@ast::Ty {
             id: self.next_id(),
             node: ast::ty_path(path, self.next_id()),
             span: span,
         });
 
-        ast::ty_param {
+        ast::TyParam {
             ident: ident,
             id: self.next_id(),
-            bounds: @vec::append(~[bound], *bounds)
+            bounds: @bounds.prepend(bound)
         }
     }
 
@@ -408,28 +411,45 @@ fn mk_impl(
     cx: ext_ctxt,
     span: span,
     ident: ast::ident,
-    ty_param: ast::ty_param,
+    ty_param: ast::TyParam,
     path: @ast::path,
-    tps: &[ast::ty_param],
+    generics: &ast::Generics,
     f: fn(@ast::Ty) -> @ast::method
 ) -> @ast::item {
+    /*!
+     *
+     * Given that we are deriving auto-encode a type `T<'a, ...,
+     * 'z, A, ..., Z>`, creates an impl like:
+     *
+     *      impl<'a, ..., 'z, A:Tr, ..., Z:Tr> Tr for T<A, ..., Z> { ... }
+     *
+     * where Tr is either Serializable and Deserialize.
+     *
+     * FIXME(#5090): Remove code duplication between this and the code
+     * in deriving.rs
+     */
+
+
+    // Copy the lifetimes
+    let impl_lifetimes = generics.lifetimes.map(|l| {
+        build::mk_lifetime(cx, l.span, l.ident)
+    });
+
     // All the type parameters need to bound to the trait.
-    let mut trait_tps = vec::append(
-        ~[ty_param],
-         do tps.map |tp| {
-            let t_bound = ast::TraitTyParamBound(@ast::Ty {
-                id: cx.next_id(),
-                node: ast::ty_path(path, cx.next_id()),
-                span: span,
-            });
+    let mut impl_tps = opt_vec::with(ty_param);
+    for generics.ty_params.each |tp| {
+        let t_bound = ast::TraitTyParamBound(@ast::Ty {
+            id: cx.next_id(),
+            node: ast::ty_path(path, cx.next_id()),
+            span: span,
+        });
 
-            ast::ty_param {
-                ident: tp.ident,
-                id: cx.next_id(),
-                bounds: @vec::append(~[t_bound], *tp.bounds)
-            }
-        }
-    );
+        impl_tps.push(ast::TyParam {
+            ident: tp.ident,
+            id: cx.next_id(),
+            bounds: @tp.bounds.prepend(t_bound)
+        })
+    }
 
     let opt_trait = Some(@ast::trait_ref {
         path: path,
@@ -439,16 +459,22 @@ fn mk_impl(
     let ty = cx.ty_path(
         span,
         ~[ident],
-        tps.map(|tp| cx.ty_path(span, ~[tp.ident], ~[]))
+        generics.ty_params.map(
+            |tp| cx.ty_path(span, ~[tp.ident], ~[])).to_vec()
     );
 
+    let generics = ast::Generics {
+        lifetimes: impl_lifetimes,
+        ty_params: impl_tps
+    };
+
     @ast::item {
         // This is a new-style impl declaration.
         // XXX: clownshoes
         ident: parse::token::special_idents::clownshoes_extensions,
         attrs: ~[],
         id: cx.next_id(),
-        node: ast::item_impl(trait_tps, opt_trait, ty, ~[f(ty)]),
+        node: ast::item_impl(generics, opt_trait, ty, ~[f(ty)]),
         vis: ast::public,
         span: span,
     }
@@ -458,7 +484,7 @@ fn mk_ser_impl(
     cx: ext_ctxt,
     span: span,
     ident: ast::ident,
-    tps: &[ast::ty_param],
+    generics: &ast::Generics,
     body: @ast::expr
 ) -> @ast::item {
     // Make a path to the std::serialize::Encodable typaram.
@@ -473,7 +499,7 @@ fn mk_ser_impl(
                 cx.ident_of(~"Encoder"),
             ]
         ),
-        @~[]
+        @opt_vec::Empty
     );
 
     // Make a path to the std::serialize::Encodable trait.
@@ -493,7 +519,7 @@ fn mk_ser_impl(
         ident,
         ty_param,
         path,
-        tps,
+        generics,
         |_ty| mk_ser_method(cx, span, cx.expr_blk(body))
     )
 }
@@ -502,7 +528,7 @@ fn mk_deser_impl(
     cx: ext_ctxt,
     span: span,
     ident: ast::ident,
-    tps: ~[ast::ty_param],
+    generics: &ast::Generics,
     body: @ast::expr
 ) -> @ast::item {
     // Make a path to the std::serialize::Decodable typaram.
@@ -517,7 +543,7 @@ fn mk_deser_impl(
                 cx.ident_of(~"Decoder"),
             ]
         ),
-        @~[]
+        @opt_vec::Empty
     );
 
     // Make a path to the std::serialize::Decodable trait.
@@ -537,7 +563,7 @@ fn mk_deser_impl(
         ident,
         ty_param,
         path,
-        tps,
+        generics,
         |ty| mk_deser_method(cx, span, ty, cx.expr_blk(body))
     )
 }
@@ -592,7 +618,7 @@ fn mk_ser_method(
     @ast::method {
         ident: cx.ident_of(~"encode"),
         attrs: ~[],
-        tps: ~[],
+        generics: ast_util::empty_generics(),
         self_ty: codemap::spanned { node: ast::sty_region(ast::m_imm),
                                 span: span },
         purity: ast::impure_fn,
@@ -650,7 +676,7 @@ fn mk_deser_method(
     @ast::method {
         ident: cx.ident_of(~"decode"),
         attrs: ~[],
-        tps: ~[],
+        generics: ast_util::empty_generics(),
         self_ty: codemap::spanned { node: ast::sty_static, span: span },
         purity: ast::impure_fn,
         decl: deser_decl,
@@ -667,7 +693,7 @@ fn mk_struct_ser_impl(
     span: span,
     ident: ast::ident,
     fields: &[@ast::struct_field],
-    tps: &[ast::ty_param]
+    generics: &ast::Generics
 ) -> @ast::item {
     let fields = do mk_struct_fields(fields).mapi |idx, field| {
         // ast for `|| self.$(name).encode(__s)`
@@ -720,7 +746,7 @@ fn mk_struct_ser_impl(
         ]
     );
 
-    mk_ser_impl(cx, span, ident, tps, ser_body)
+    mk_ser_impl(cx, span, ident, generics, ser_body)
 }
 
 fn mk_struct_deser_impl(
@@ -728,7 +754,7 @@ fn mk_struct_deser_impl(
     span: span,
     ident: ast::ident,
     fields: ~[@ast::struct_field],
-    tps: ~[ast::ty_param]
+    generics: &ast::Generics
 ) -> @ast::item {
     let fields = do mk_struct_fields(fields).mapi |idx, field| {
         // ast for `|| std::serialize::decode(__d)`
@@ -796,7 +822,7 @@ fn mk_struct_deser_impl(
         ]
     );
 
-    mk_deser_impl(cx, span, ident, tps, body)
+    mk_deser_impl(cx, span, ident, generics, body)
 }
 
 // Records and structs don't have the same fields types, but they share enough
@@ -832,7 +858,7 @@ fn mk_enum_ser_impl(
     span: span,
     ident: ast::ident,
     enum_def: ast::enum_def,
-    tps: ~[ast::ty_param]
+    generics: &ast::Generics
 ) -> @ast::item {
     let body = mk_enum_ser_body(
         cx,
@@ -841,7 +867,7 @@ fn mk_enum_ser_impl(
         enum_def.variants
     );
 
-    mk_ser_impl(cx, span, ident, tps, body)
+    mk_ser_impl(cx, span, ident, generics, body)
 }
 
 fn mk_enum_deser_impl(
@@ -849,7 +875,7 @@ fn mk_enum_deser_impl(
     span: span,
     ident: ast::ident,
     enum_def: ast::enum_def,
-    tps: ~[ast::ty_param]
+    generics: &ast::Generics
 ) -> @ast::item {
     let body = mk_enum_deser_body(
         cx,
@@ -858,7 +884,7 @@ fn mk_enum_deser_impl(
         enum_def.variants
     );
 
-    mk_deser_impl(cx, span, ident, tps, body)
+    mk_deser_impl(cx, span, ident, generics, body)
 }
 
 fn ser_variant(
diff --git a/src/libsyntax/ext/build.rs b/src/libsyntax/ext/build.rs
index 55e5d5fbe17..fa21243df03 100644
--- a/src/libsyntax/ext/build.rs
+++ b/src/libsyntax/ext/build.rs
@@ -16,6 +16,9 @@ use codemap::span;
 use ext::base::ext_ctxt;
 use ext::build;
 
+use opt_vec;
+use opt_vec::OptVec;
+
 use core::dvec;
 use core::option;
 
@@ -354,8 +357,14 @@ pub fn mk_fn_decl(+inputs: ~[ast::arg], output: @ast::Ty) -> ast::fn_decl {
 }
 pub fn mk_ty_param(cx: ext_ctxt,
                    ident: ast::ident,
-                   bounds: @~[ast::ty_param_bound])
-                -> ast::ty_param {
-    ast::ty_param { ident: ident, id: cx.next_id(), bounds: bounds }
+                   bounds: @OptVec<ast::TyParamBound>)
+                -> ast::TyParam {
+    ast::TyParam { ident: ident, id: cx.next_id(), bounds: bounds }
+}
+pub fn mk_lifetime(cx: ext_ctxt,
+                   span: span,
+                   ident: ast::ident) -> ast::Lifetime
+{
+    ast::Lifetime { id: cx.next_id(), span: span, ident: ident }
 }
 
diff --git a/src/libsyntax/ext/deriving.rs b/src/libsyntax/ext/deriving.rs
index 094eea81fd2..0164f807f4b 100644
--- a/src/libsyntax/ext/deriving.rs
+++ b/src/libsyntax/ext/deriving.rs
@@ -16,15 +16,19 @@ use core::prelude::*;
 use ast;
 use ast::{TraitTyParamBound, Ty, and, bind_by_ref, binop, deref, enum_def};
 use ast::{enum_variant_kind, expr, expr_match, ident, item, item_};
-use ast::{item_enum, item_impl, item_struct, m_imm, meta_item, method};
+use ast::{item_enum, item_impl, item_struct, Generics};
+use ast::{m_imm, meta_item, method};
 use ast::{named_field, or, pat, pat_ident, pat_wild, public, pure_fn};
 use ast::{re_anon, stmt, struct_def, struct_variant_kind};
-use ast::{sty_by_ref, sty_region, tuple_variant_kind, ty_nil, ty_param};
-use ast::{ty_param_bound, ty_path, ty_rptr, unnamed_field, variant};
+use ast::{sty_by_ref, sty_region, tuple_variant_kind, ty_nil, TyParam};
+use ast::{TyParamBound, ty_path, ty_rptr, unnamed_field, variant};
 use ext::base::ext_ctxt;
 use ext::build;
 use codemap::{span, spanned};
 use parse::token::special_idents::clownshoes_extensions;
+use ast_util;
+use opt_vec;
+use opt_vec::OptVec;
 
 use core::dvec;
 use core::uint;
@@ -47,13 +51,13 @@ type ExpandDerivingStructDefFn = &fn(ext_ctxt,
                                      span,
                                      x: &struct_def,
                                      ident,
-                                     +y: ~[ty_param])
+                                     y: &Generics)
                                   -> @item;
 type ExpandDerivingEnumDefFn = &fn(ext_ctxt,
                                    span,
                                    x: &enum_def,
                                    ident,
-                                   +y: ~[ty_param])
+                                   y: &Generics)
                                 -> @item;
 
 pub fn expand_deriving_eq(cx: ext_ctxt,
@@ -90,19 +94,19 @@ fn expand_deriving(cx: ext_ctxt,
     for in_items.each |item| {
         result.push(copy *item);
         match item.node {
-            item_struct(struct_def, copy ty_params) => {
+            item_struct(struct_def, ref generics) => {
                 result.push(expand_deriving_struct_def(cx,
                                                        span,
                                                        struct_def,
                                                        item.ident,
-                                                       ty_params));
+                                                       generics));
             }
-            item_enum(ref enum_definition, copy ty_params) => {
+            item_enum(ref enum_definition, ref generics) => {
                 result.push(expand_deriving_enum_def(cx,
                                                      span,
                                                      enum_definition,
                                                      item.ident,
-                                                     ty_params));
+                                                     generics));
             }
             _ => ()
         }
@@ -127,14 +131,14 @@ fn create_eq_method(cx: ext_ctxt,
                     span: span,
                     method_ident: ident,
                     type_ident: ident,
-                    ty_params: &[ty_param],
+                    generics: &Generics,
                     body: @expr)
                  -> @method {
     // Create the type of the `other` parameter.
     let arg_path_type = create_self_type_with_params(cx,
                                                      span,
                                                      type_ident,
-                                                     ty_params);
+                                                     generics);
     let arg_region = @ast::region { id: cx.next_id(), node: re_anon };
     let arg_type = ty_rptr(
         arg_region,
@@ -171,7 +175,7 @@ fn create_eq_method(cx: ext_ctxt,
     @ast::method {
         ident: method_ident,
         attrs: ~[],
-        tps: ~[],
+        generics: ast_util::empty_generics(),
         self_ty: self_ty,
         purity: pure_fn,
         decl: fn_decl,
@@ -186,11 +190,11 @@ fn create_eq_method(cx: ext_ctxt,
 fn create_self_type_with_params(cx: ext_ctxt,
                                 span: span,
                                 type_ident: ident,
-                                ty_params: &[ty_param])
+                                generics: &Generics)
                              -> @Ty {
     // Create the type parameters on the `self` path.
     let self_ty_params = dvec::DVec();
-    for ty_params.each |ty_param| {
+    for generics.ty_params.each |ty_param| {
         let self_ty_param = build::mk_simple_ty_path(cx,
                                                      span,
                                                      ty_param.ident);
@@ -209,21 +213,34 @@ fn create_self_type_with_params(cx: ext_ctxt,
 fn create_derived_impl(cx: ext_ctxt,
                        span: span,
                        type_ident: ident,
-                       +ty_params: ~[ty_param],
+                       generics: &Generics,
                        methods: &[@method],
                        trait_path: &[ident])
                     -> @item {
+    /*!
+     *
+     * Given that we are deriving a trait `Tr` for a type `T<'a, ...,
+     * 'z, A, ..., Z>`, creates an impl like:
+     *
+     *      impl<'a, ..., 'z, A:Tr, ..., Z: Tr> Tr for T<A, ..., Z> { ... }
+     *
+     * FIXME(#5090): Remove code duplication between this and the
+     * code in auto_encode.rs
+     */
+
+    // Copy the lifetimes
+    let impl_lifetimes = generics.lifetimes.map(|l| {
+        build::mk_lifetime(cx, l.span, l.ident)
+    });
+
     // Create the type parameters.
-    let impl_ty_params = dvec::DVec();
-    for ty_params.each |ty_param| {
+    let impl_ty_params = generics.ty_params.map(|ty_param| {
         let bound = build::mk_ty_path_global(cx,
                                              span,
                                              trait_path.map(|x| *x));
-        let bounds = @~[ TraitTyParamBound(bound) ];
-        let impl_ty_param = build::mk_ty_param(cx, ty_param.ident, bounds);
-        impl_ty_params.push(impl_ty_param);
-    }
-    let impl_ty_params = dvec::unwrap(impl_ty_params);
+        let bounds = @opt_vec::with(TraitTyParamBound(bound));
+        build::mk_ty_param(cx, ty_param.ident, bounds)
+    });
 
     // Create the reference to the trait.
     let trait_path = ast::path {
@@ -244,10 +261,11 @@ fn create_derived_impl(cx: ext_ctxt,
     let self_type = create_self_type_with_params(cx,
                                                  span,
                                                  type_ident,
-                                                 ty_params);
+                                                 generics);
 
     // Create the impl item.
-    let impl_item = item_impl(impl_ty_params,
+    let impl_item = item_impl(Generics {lifetimes: impl_lifetimes,
+                                        ty_params: impl_ty_params},
                               Some(trait_ref),
                               self_type,
                               methods.map(|x| *x));
@@ -257,7 +275,7 @@ fn create_derived_impl(cx: ext_ctxt,
 fn create_derived_eq_impl(cx: ext_ctxt,
                           span: span,
                           type_ident: ident,
-                          +ty_params: ~[ty_param],
+                          generics: &Generics,
                           eq_method: @method,
                           ne_method: @method)
                        -> @item {
@@ -267,13 +285,13 @@ fn create_derived_eq_impl(cx: ext_ctxt,
         cx.ident_of(~"cmp"),
         cx.ident_of(~"Eq")
     ];
-    create_derived_impl(cx, span, type_ident, ty_params, methods, trait_path)
+    create_derived_impl(cx, span, type_ident, generics, methods, trait_path)
 }
 
 fn create_derived_iter_bytes_impl(cx: ext_ctxt,
                                   span: span,
                                   type_ident: ident,
-                                  +ty_params: ~[ty_param],
+                                  generics: &Generics,
                                   method: @method)
                                -> @item {
     let methods = [ method ];
@@ -282,7 +300,7 @@ fn create_derived_iter_bytes_impl(cx: ext_ctxt,
         cx.ident_of(~"to_bytes"),
         cx.ident_of(~"IterBytes")
     ];
-    create_derived_impl(cx, span, type_ident, ty_params, methods, trait_path)
+    create_derived_impl(cx, span, type_ident, generics, methods, trait_path)
 }
 
 // Creates a method from the given set of statements conforming to the
@@ -322,7 +340,7 @@ fn create_iter_bytes_method(cx: ext_ctxt,
     @ast::method {
         ident: method_ident,
         attrs: ~[],
-        tps: ~[],
+        generics: ast_util::empty_generics(),
         self_ty: self_ty,
         purity: pure_fn,
         decl: fn_decl,
@@ -484,7 +502,7 @@ fn expand_deriving_eq_struct_def(cx: ext_ctxt,
                                  span: span,
                                  struct_def: &struct_def,
                                  type_ident: ident,
-                                 +ty_params: ~[ty_param])
+                                 generics: &Generics)
                               -> @item {
     // Create the methods.
     let eq_ident = cx.ident_of(~"eq");
@@ -510,21 +528,21 @@ fn expand_deriving_eq_struct_def(cx: ext_ctxt,
                                      struct_def,
                                      eq_ident,
                                      type_ident,
-                                     ty_params,
+                                     generics,
                                      Conjunction);
     let ne_method = derive_struct_fn(cx,
                                      span,
                                      struct_def,
                                      ne_ident,
                                      type_ident,
-                                     ty_params,
+                                     generics,
                                      Disjunction);
 
     // Create the implementation.
     return create_derived_eq_impl(cx,
                                   span,
                                   type_ident,
-                                  ty_params,
+                                  generics,
                                   eq_method,
                                   ne_method);
 }
@@ -533,7 +551,7 @@ fn expand_deriving_eq_enum_def(cx: ext_ctxt,
                                span: span,
                                enum_definition: &enum_def,
                                type_ident: ident,
-                               +ty_params: ~[ty_param])
+                               generics: &Generics)
                             -> @item {
     // Create the methods.
     let eq_ident = cx.ident_of(~"eq");
@@ -543,21 +561,21 @@ fn expand_deriving_eq_enum_def(cx: ext_ctxt,
                                                    enum_definition,
                                                    eq_ident,
                                                    type_ident,
-                                                   ty_params,
+                                                   generics,
                                                    Conjunction);
     let ne_method = expand_deriving_eq_enum_method(cx,
                                                    span,
                                                    enum_definition,
                                                    ne_ident,
                                                    type_ident,
-                                                   ty_params,
+                                                   generics,
                                                    Disjunction);
 
     // Create the implementation.
     return create_derived_eq_impl(cx,
                                   span,
                                   type_ident,
-                                  ty_params,
+                                  generics,
                                   eq_method,
                                   ne_method);
 }
@@ -566,7 +584,7 @@ fn expand_deriving_iter_bytes_struct_def(cx: ext_ctxt,
                                          span: span,
                                          struct_def: &struct_def,
                                          type_ident: ident,
-                                         +ty_params: ~[ty_param])
+                                         generics: &Generics)
                                       -> @item {
     // Create the method.
     let method = expand_deriving_iter_bytes_struct_method(cx,
@@ -577,7 +595,7 @@ fn expand_deriving_iter_bytes_struct_def(cx: ext_ctxt,
     return create_derived_iter_bytes_impl(cx,
                                           span,
                                           type_ident,
-                                          ty_params,
+                                          generics,
                                           method);
 }
 
@@ -585,7 +603,7 @@ fn expand_deriving_iter_bytes_enum_def(cx: ext_ctxt,
                                        span: span,
                                        enum_definition: &enum_def,
                                        type_ident: ident,
-                                       +ty_params: ~[ty_param])
+                                       generics: &Generics)
                                     -> @item {
     // Create the method.
     let method = expand_deriving_iter_bytes_enum_method(cx,
@@ -596,7 +614,7 @@ fn expand_deriving_iter_bytes_enum_def(cx: ext_ctxt,
     return create_derived_iter_bytes_impl(cx,
                                           span,
                                           type_ident,
-                                          ty_params,
+                                          generics,
                                           method);
 }
 
@@ -605,7 +623,7 @@ fn expand_deriving_eq_struct_method(cx: ext_ctxt,
                                     struct_def: &struct_def,
                                     method_ident: ident,
                                     type_ident: ident,
-                                    ty_params: &[ty_param],
+                                    generics: &Generics,
                                     junction: Junction)
                                  -> @method {
     let self_ident = cx.ident_of(~"self");
@@ -652,7 +670,7 @@ fn expand_deriving_eq_struct_method(cx: ext_ctxt,
                             span,
                             method_ident,
                             type_ident,
-                            ty_params,
+                            generics,
                             body);
 }
 
@@ -696,7 +714,7 @@ fn expand_deriving_eq_enum_method(cx: ext_ctxt,
                                   enum_definition: &enum_def,
                                   method_ident: ident,
                                   type_ident: ident,
-                                  ty_params: &[ty_param],
+                                  generics: &Generics,
                                   junction: Junction)
                                -> @method {
     let self_ident = cx.ident_of(~"self");
@@ -823,7 +841,7 @@ fn expand_deriving_eq_enum_method(cx: ext_ctxt,
                             span,
                             method_ident,
                             type_ident,
-                            ty_params,
+                            generics,
                             self_match_expr);
 }
 
@@ -832,7 +850,7 @@ fn expand_deriving_eq_struct_tuple_method(cx: ext_ctxt,
                                           struct_def: &struct_def,
                                           method_ident: ident,
                                           type_ident: ident,
-                                          ty_params: &[ty_param],
+                                          generics: &Generics,
                                           junction: Junction)
                                         -> @method {
     let self_str = ~"self";
@@ -883,7 +901,7 @@ fn expand_deriving_eq_struct_tuple_method(cx: ext_ctxt,
     let self_match_expr = build::mk_expr(cx, span, self_match_expr);
 
     create_eq_method(cx, span, method_ident,
-        type_ident, ty_params, self_match_expr)
+        type_ident, generics, self_match_expr)
 }
 
 fn expand_deriving_iter_bytes_enum_method(cx: ext_ctxt,
diff --git a/src/libsyntax/ext/pipes/ast_builder.rs b/src/libsyntax/ext/pipes/ast_builder.rs
index 6adea6395a3..a49d3dead0c 100644
--- a/src/libsyntax/ext/pipes/ast_builder.rs
+++ b/src/libsyntax/ext/pipes/ast_builder.rs
@@ -24,6 +24,8 @@ use codemap::{span, respan, dummy_sp};
 use codemap;
 use ext::base::{ext_ctxt, mk_ctxt};
 use ext::quote::rt::*;
+use opt_vec;
+use opt_vec::OptVec;
 
 use core::vec;
 
@@ -67,8 +69,8 @@ impl append_types for @ast::path {
 }
 
 pub trait ext_ctxt_ast_builder {
-    fn ty_param(&self, id: ast::ident, +bounds: ~[ast::ty_param_bound])
-        -> ast::ty_param;
+    fn ty_param(&self, id: ast::ident, bounds: @OptVec<ast::TyParamBound>)
+        -> ast::TyParam;
     fn arg(&self, name: ident, ty: @ast::Ty) -> ast::arg;
     fn expr_block(&self, e: @ast::expr) -> ast::blk;
     fn fn_decl(&self, +inputs: ~[ast::arg], output: @ast::Ty) -> ast::fn_decl;
@@ -76,7 +78,7 @@ pub trait ext_ctxt_ast_builder {
     fn item_fn_poly(&self, name: ident,
                     +inputs: ~[ast::arg],
                     output: @ast::Ty,
-                    +ty_params: ~[ast::ty_param],
+                    +generics: Generics,
                     +body: ast::blk) -> @ast::item;
     fn item_fn(&self, name: ident,
                +inputs: ~[ast::arg],
@@ -85,12 +87,12 @@ pub trait ext_ctxt_ast_builder {
     fn item_enum_poly(&self, name: ident,
                       span: span,
                       +enum_definition: ast::enum_def,
-                      +ty_params: ~[ast::ty_param]) -> @ast::item;
+                      +generics: Generics) -> @ast::item;
     fn item_enum(&self, name: ident, span: span,
                  +enum_definition: ast::enum_def) -> @ast::item;
     fn item_struct_poly(&self, name: ident, span: span,
                         struct_def: ast::struct_def,
-                        ty_params: ~[ast::ty_param]) -> @ast::item;
+                        +generics: Generics) -> @ast::item;
     fn item_struct(&self, name: ident, span: span,
                    struct_def: ast::struct_def) -> @ast::item;
     fn struct_expr(&self, path: @ast::path,
@@ -103,10 +105,10 @@ pub trait ext_ctxt_ast_builder {
     fn item_ty_poly(&self, name: ident,
                     span: span,
                     ty: @ast::Ty,
-                    +params: ~[ast::ty_param]) -> @ast::item;
+                    +generics: Generics) -> @ast::item;
     fn item_ty(&self, name: ident, span: span, ty: @ast::Ty) -> @ast::item;
-    fn ty_vars(&self, +ty_params: ~[ast::ty_param]) -> ~[@ast::Ty];
-    fn ty_vars_global(&self, +ty_params: ~[ast::ty_param]) -> ~[@ast::Ty];
+    fn ty_vars(&self, ty_params: &OptVec<ast::TyParam>) -> ~[@ast::Ty];
+    fn ty_vars_global(&self, ty_params: &OptVec<ast::TyParam>) -> ~[@ast::Ty];
     fn ty_field_imm(&self, name: ident, ty: @ast::Ty) -> ast::ty_field;
     fn field_imm(&self, name: ident, e: @ast::expr) -> ast::field;
     fn block(&self, +stmts: ~[@ast::stmt], e: @ast::expr) -> ast::blk;
@@ -116,7 +118,7 @@ pub trait ext_ctxt_ast_builder {
     fn ty_option(&self, ty: @ast::Ty) -> @ast::Ty;
     fn ty_infer(&self) -> @ast::Ty;
     fn ty_nil_ast_builder(&self) -> @ast::Ty;
-    fn strip_bounds(&self, bounds: &[ast::ty_param]) -> ~[ast::ty_param];
+    fn strip_bounds(&self, bounds: &Generics) -> Generics;
 }
 
 impl ext_ctxt_ast_builder for ext_ctxt {
@@ -172,10 +174,10 @@ impl ext_ctxt_ast_builder for ext_ctxt {
         }
     }
 
-    fn ty_param(&self, id: ast::ident, +bounds: ~[ast::ty_param_bound])
-        -> ast::ty_param
+    fn ty_param(&self, id: ast::ident, bounds: @OptVec<ast::TyParamBound>)
+        -> ast::TyParam
     {
-        ast::ty_param { ident: id, id: self.next_id(), bounds: @bounds }
+        ast::TyParam { ident: id, id: self.next_id(), bounds: bounds }
     }
 
     fn arg(&self, name: ident, ty: @ast::Ty) -> ast::arg {
@@ -247,13 +249,13 @@ impl ext_ctxt_ast_builder for ext_ctxt {
     fn item_fn_poly(&self, name: ident,
                     +inputs: ~[ast::arg],
                     output: @ast::Ty,
-                    +ty_params: ~[ast::ty_param],
+                    +generics: Generics,
                     +body: ast::blk) -> @ast::item {
         self.item(name,
                   dummy_sp(),
                   ast::item_fn(self.fn_decl(inputs, output),
                                ast::impure_fn,
-                               ty_params,
+                               generics,
                                body))
     }
 
@@ -261,29 +263,32 @@ impl ext_ctxt_ast_builder for ext_ctxt {
                +inputs: ~[ast::arg],
                output: @ast::Ty,
                +body: ast::blk) -> @ast::item {
-        self.item_fn_poly(name, inputs, output, ~[], body)
+        self.item_fn_poly(name, inputs, output,
+                          ast_util::empty_generics(), body)
     }
 
     fn item_enum_poly(&self, name: ident, span: span,
                       +enum_definition: ast::enum_def,
-                      +ty_params: ~[ast::ty_param]) -> @ast::item {
-        self.item(name, span, ast::item_enum(enum_definition, ty_params))
+                      +generics: Generics) -> @ast::item {
+        self.item(name, span, ast::item_enum(enum_definition, generics))
     }
 
     fn item_enum(&self, name: ident, span: span,
                  +enum_definition: ast::enum_def) -> @ast::item {
-        self.item_enum_poly(name, span, enum_definition, ~[])
+        self.item_enum_poly(name, span, enum_definition,
+                            ast_util::empty_generics())
     }
 
     fn item_struct(&self, name: ident, span: span,
                    struct_def: ast::struct_def) -> @ast::item {
-        self.item_struct_poly(name, span, struct_def, ~[])
+        self.item_struct_poly(name, span, struct_def,
+                              ast_util::empty_generics())
     }
 
     fn item_struct_poly(&self, name: ident, span: span,
                         struct_def: ast::struct_def,
-                        ty_params: ~[ast::ty_param]) -> @ast::item {
-        self.item(name, span, ast::item_struct(@struct_def, ty_params))
+                        +generics: Generics) -> @ast::item {
+        self.item(name, span, ast::item_struct(@struct_def, generics))
     }
 
     fn struct_expr(&self, path: @ast::path,
@@ -371,28 +376,31 @@ impl ext_ctxt_ast_builder for ext_ctxt {
         }
     }
 
-    fn strip_bounds(&self, bounds: &[ast::ty_param]) -> ~[ast::ty_param] {
-        do bounds.map |ty_param| {
-            ast::ty_param { bounds: @~[], ..copy *ty_param }
-        }
+    fn strip_bounds(&self, generics: &Generics) -> Generics {
+        let no_bounds = @opt_vec::Empty;
+        let new_params = do generics.ty_params.map |ty_param| {
+            ast::TyParam { bounds: no_bounds, ..copy *ty_param }
+        };
+        Generics { ty_params: new_params, ..*generics }
     }
 
     fn item_ty_poly(&self, name: ident, span: span, ty: @ast::Ty,
-                    +params: ~[ast::ty_param]) -> @ast::item {
-        self.item(name, span, ast::item_ty(ty, params))
+                    +generics: Generics) -> @ast::item {
+        self.item(name, span, ast::item_ty(ty, generics))
     }
 
     fn item_ty(&self, name: ident, span: span, ty: @ast::Ty) -> @ast::item {
-        self.item_ty_poly(name, span, ty, ~[])
+        self.item_ty_poly(name, span, ty, ast_util::empty_generics())
     }
 
-    fn ty_vars(&self, +ty_params: ~[ast::ty_param]) -> ~[@ast::Ty] {
+    fn ty_vars(&self, ty_params: &OptVec<ast::TyParam>) -> ~[@ast::Ty] {
         ty_params.map(|p| self.ty_path_ast_builder(
-            path(~[p.ident], dummy_sp())))
+            path(~[p.ident], dummy_sp()))).to_vec()
     }
 
-    fn ty_vars_global(&self, +ty_params: ~[ast::ty_param]) -> ~[@ast::Ty] {
+    fn ty_vars_global(&self,
+                      ty_params: &OptVec<ast::TyParam>) -> ~[@ast::Ty] {
         ty_params.map(|p| self.ty_path_ast_builder(
-            path(~[p.ident], dummy_sp())))
+            path(~[p.ident], dummy_sp()))).to_vec()
     }
 }
diff --git a/src/libsyntax/ext/pipes/check.rs b/src/libsyntax/ext/pipes/check.rs
index f456f7b81ae..b543ef5fdae 100644
--- a/src/libsyntax/ext/pipes/check.rs
+++ b/src/libsyntax/ext/pipes/check.rs
@@ -67,13 +67,13 @@ impl proto::visitor<(), (), ()> for ext_ctxt {
             else {
                 let next = proto.get_state(next_state.state);
 
-                if next.ty_params.len() != next_state.tys.len() {
+                if next.generics.ty_params.len() != next_state.tys.len() {
                     self.span_err(
                         next.span, // use a real span
                         fmt!("message %s target (%s) \
                               needs %u type parameters, but got %u",
                              name, next.name,
-                             next.ty_params.len(),
+                             next.generics.ty_params.len(),
                              next_state.tys.len()));
                 }
             }
diff --git a/src/libsyntax/ext/pipes/parse_proto.rs b/src/libsyntax/ext/pipes/parse_proto.rs
index 9a330db9f18..8caa2c4bba8 100644
--- a/src/libsyntax/ext/pipes/parse_proto.rs
+++ b/src/libsyntax/ext/pipes/parse_proto.rs
@@ -51,13 +51,13 @@ impl proto_parser for parser::Parser {
           _ => fail!()
         };
 
-        let typarms = if *self.token == token::LT {
-            self.parse_ty_params()
+        let generics = if *self.token == token::LT {
+            self.parse_generics()
         } else {
-            ~[]
+            ast_util::empty_generics()
         };
 
-        let state = proto.add_state_poly(name, id, dir, typarms);
+        let state = proto.add_state_poly(name, id, dir, generics);
 
         // parse the messages
         self.parse_unspanned_seq(
diff --git a/src/libsyntax/ext/pipes/pipec.rs b/src/libsyntax/ext/pipes/pipec.rs
index 84d46e318b1..6c124ce16df 100644
--- a/src/libsyntax/ext/pipes/pipec.rs
+++ b/src/libsyntax/ext/pipes/pipec.rs
@@ -19,6 +19,8 @@ use ext::pipes::proto::*;
 use ext::quote::rt::*;
 use parse::*;
 use util::interner;
+use opt_vec;
+use opt_vec::OptVec;
 
 use core::dvec::DVec;
 use core::prelude::*;
@@ -50,20 +52,19 @@ impl gen_send for message {
     fn gen_send(&mut self, cx: ext_ctxt, try: bool) -> @ast::item {
         debug!("pipec: gen_send");
         let name = self.name();
-        let params = self.get_params();
 
         match *self {
           message(ref _id, span, ref tys, this, Some(ref next_state)) => {
             debug!("pipec: next state exists");
             let next = this.proto.get_state(next_state.state);
-            assert next_state.tys.len() == next.ty_params.len();
+            assert next_state.tys.len() == next.generics.ty_params.len();
             let arg_names = tys.mapi(|i, _ty| cx.ident_of(~"x_"+i.to_str()));
 
             let args_ast = (arg_names, *tys).map(|n, t| cx.arg(*n, *t));
 
             let pipe_ty = cx.ty_path_ast_builder(
                 path(~[this.data_name()], span)
-                .add_tys(cx.ty_vars_global(this.ty_params)));
+                .add_tys(cx.ty_vars_global(&this.generics.ty_params)));
             let args_ast = vec::append(
                 ~[cx.arg(cx.ident_of(~"pipe"),
                               pipe_ty)],
@@ -129,7 +130,7 @@ impl gen_send for message {
             cx.item_fn_poly(name,
                             args_ast,
                             rty,
-                            params,
+                            self.get_generics(),
                             cx.expr_block(body))
           }
 
@@ -143,10 +144,10 @@ impl gen_send for message {
 
                 let args_ast = vec::append(
                     ~[cx.arg(cx.ident_of(~"pipe"),
-                                  cx.ty_path_ast_builder(
-                                      path(~[this.data_name()], span)
-                                      .add_tys(cx.ty_vars_global(
-                                        this.ty_params))))],
+                             cx.ty_path_ast_builder(
+                                 path(~[this.data_name()], span)
+                                 .add_tys(cx.ty_vars_global(
+                                     &this.generics.ty_params))))],
                     args_ast);
 
                 let message_args = if arg_names.len() == 0 {
@@ -184,7 +185,7 @@ impl gen_send for message {
                                 } else {
                                     cx.ty_nil_ast_builder()
                                 },
-                                params,
+                                self.get_generics(),
                                 cx.expr_block(body))
             }
           }
@@ -192,7 +193,7 @@ impl gen_send for message {
 
     fn to_ty(&mut self, cx: ext_ctxt) -> @ast::Ty {
         cx.ty_path_ast_builder(path(~[cx.ident_of(self.name())], self.span())
-          .add_tys(cx.ty_vars_global(self.get_params())))
+          .add_tys(cx.ty_vars_global(&self.get_generics().ty_params)))
     }
 }
 
@@ -243,7 +244,7 @@ impl to_type_decls for state {
                 ast::enum_def(enum_def_ {
                     variants: items_msg,
                     common: None }),
-                cx.strip_bounds(self.ty_params)
+                cx.strip_bounds(&self.generics)
             )
         ]
     }
@@ -281,8 +282,9 @@ impl to_type_decls for state {
                             path(~[cx.ident_of(~"super"),
                                    self.data_name()],
                                  dummy_sp())
-                            .add_tys(cx.ty_vars_global(self.ty_params))))),
-                    cx.strip_bounds(self.ty_params)));
+                            .add_tys(cx.ty_vars_global(
+                                &self.generics.ty_params))))),
+                    cx.strip_bounds(&self.generics)));
         }
         else {
             items.push(
@@ -299,9 +301,10 @@ impl to_type_decls for state {
                             path(~[cx.ident_of(~"super"),
                                    self.data_name()],
                                         dummy_sp())
-                            .add_tys(cx.ty_vars_global(self.ty_params))),
+                            .add_tys(cx.ty_vars_global(
+                                &self.generics.ty_params))),
                                    self.proto.buffer_ty_path(cx)])),
-                    cx.strip_bounds(self.ty_params)));
+                    cx.strip_bounds(&self.generics)));
         };
         items
     }
@@ -340,7 +343,7 @@ impl gen_init for protocol {
 
         cx.parse_item(fmt!("pub fn init%s() -> (client::%s, server::%s)\
                             { use core::pipes::HasBuffer; %s }",
-                           start_state.ty_params.to_source(cx),
+                           start_state.generics.to_source(cx),
                            start_state.to_ty(cx).to_source(cx),
                            start_state.to_ty(cx).to_source(cx),
                            body.to_source(cx)))
@@ -385,9 +388,9 @@ impl gen_init for protocol {
     }
 
     fn buffer_ty_path(&self, cx: ext_ctxt) -> @ast::Ty {
-        let mut params: ~[ast::ty_param] = ~[];
+        let mut params: OptVec<ast::TyParam> = opt_vec::Empty;
         for (copy self.states).each |s| {
-            for s.ty_params.each |tp| {
+            for s.generics.ty_params.each |tp| {
                 match params.find(|tpp| tp.ident == tpp.ident) {
                   None => params.push(*tp),
                   _ => ()
@@ -398,19 +401,20 @@ impl gen_init for protocol {
         cx.ty_path_ast_builder(path(~[cx.ident_of(~"super"),
                                       cx.ident_of(~"__Buffer")],
                                     copy self.span)
-                               .add_tys(cx.ty_vars_global(params)))
+                               .add_tys(cx.ty_vars_global(&params)))
     }
 
     fn gen_buffer_type(&self, cx: ext_ctxt) -> @ast::item {
         let ext_cx = cx;
-        let mut params: ~[ast::ty_param] = ~[];
+        let mut params: OptVec<ast::TyParam> = opt_vec::Empty;
         let fields = do (copy self.states).map_to_vec |s| {
-            for s.ty_params.each |tp| {
+            for s.generics.ty_params.each |tp| {
                 match params.find(|tpp| tp.ident == tpp.ident) {
                   None => params.push(*tp),
                   _ => ()
                 }
             }
+
             let ty = s.to_ty(cx);
             let fty = quote_ty!( ::core::pipes::Packet<$ty> );
 
@@ -427,6 +431,11 @@ impl gen_init for protocol {
             }
         };
 
+        let generics = Generics {
+            lifetimes: opt_vec::Empty,
+            ty_params: params
+        };
+
         cx.item_struct_poly(
             cx.ident_of(~"__Buffer"),
             dummy_sp(),
@@ -435,7 +444,7 @@ impl gen_init for protocol {
                 dtor: None,
                 ctor_id: None
             },
-            cx.strip_bounds(params))
+            cx.strip_bounds(&generics))
     }
 
     fn compile(&self, cx: ext_ctxt) -> @ast::item {
diff --git a/src/libsyntax/ext/pipes/proto.rs b/src/libsyntax/ext/pipes/proto.rs
index d22feff9470..6873baf731f 100644
--- a/src/libsyntax/ext/pipes/proto.rs
+++ b/src/libsyntax/ext/pipes/proto.rs
@@ -61,9 +61,9 @@ pub impl message {
     }
 
     /// Return the type parameters actually used by this message
-    fn get_params(&mut self) -> ~[ast::ty_param] {
+    fn get_generics(&self) -> ast::Generics {
         match *self {
-          message(_, _, _, this, _) => this.ty_params
+          message(_, _, _, this, _) => this.generics
         }
     }
 }
@@ -76,7 +76,7 @@ pub struct state_ {
     ident: ast::ident,
     span: span,
     dir: direction,
-    ty_params: ~[ast::ty_param],
+    generics: ast::Generics,
     messages: @mut ~[message],
     proto: protocol
 }
@@ -100,7 +100,7 @@ pub impl state_ {
     fn to_ty(&self, cx: ext_ctxt) -> @ast::Ty {
         cx.ty_path_ast_builder
             (path(~[cx.ident_of(self.name)],self.span).add_tys(
-                cx.ty_vars(self.ty_params)))
+                cx.ty_vars(&self.generics.ty_params)))
     }
 
     /// Iterate over the states that can be reached in one message
@@ -161,7 +161,7 @@ pub impl protocol_ {
 
     fn has_ty_params(&mut self) -> bool {
         for self.states.each |s| {
-            if s.ty_params.len() > 0 {
+            if s.generics.ty_params.len() > 0 {
                 return true;
             }
         }
@@ -175,7 +175,7 @@ pub impl protocol_ {
 
 pub impl protocol {
     fn add_state_poly(&self, name: ~str, ident: ast::ident, dir: direction,
-                      +ty_params: ~[ast::ty_param]) -> state {
+                      +generics: ast::Generics) -> state {
         let messages = @mut ~[];
 
         let state = @state_ {
@@ -184,7 +184,7 @@ pub impl protocol {
             ident: ident,
             span: self.span,
             dir: dir,
-            ty_params: ty_params,
+            generics: generics,
             messages: messages,
             proto: *self
         };
diff --git a/src/libsyntax/ext/quote.rs b/src/libsyntax/ext/quote.rs
index d529ee0c01b..b313d42e812 100644
--- a/src/libsyntax/ext/quote.rs
+++ b/src/libsyntax/ext/quote.rs
@@ -50,12 +50,12 @@ pub mod rt {
     use print::pprust::{item_to_str, ty_to_str};
 
     trait ToTokens {
-        pub fn to_tokens(_cx: ext_ctxt) -> ~[token_tree];
+        pub fn to_tokens(&self, _cx: ext_ctxt) -> ~[token_tree];
     }
 
     impl ToTokens for ~[token_tree] {
-        pub fn to_tokens(_cx: ext_ctxt) -> ~[token_tree] {
-            copy self
+        pub fn to_tokens(&self, _cx: ext_ctxt) -> ~[token_tree] {
+            copy *self
         }
     }
 
@@ -75,91 +75,91 @@ pub mod rt {
 
     trait ToSource {
         // Takes a thing and generates a string containing rust code for it.
-        pub fn to_source(cx: ext_ctxt) -> ~str;
+        pub fn to_source(&self, cx: ext_ctxt) -> ~str;
     }
 
     impl ToSource for ast::ident {
-        fn to_source(cx: ext_ctxt) -> ~str {
-            copy *cx.parse_sess().interner.get(self)
+        fn to_source(&self, cx: ext_ctxt) -> ~str {
+            copy *cx.parse_sess().interner.get(*self)
         }
     }
 
     impl ToSource for @ast::item {
-        fn to_source(cx: ext_ctxt) -> ~str {
-            item_to_str(self, cx.parse_sess().interner)
+        fn to_source(&self, cx: ext_ctxt) -> ~str {
+            item_to_str(*self, cx.parse_sess().interner)
         }
     }
 
     impl ToSource for ~[@ast::item] {
-        fn to_source(cx: ext_ctxt) -> ~str {
+        fn to_source(&self, cx: ext_ctxt) -> ~str {
             str::connect(self.map(|i| i.to_source(cx)), ~"\n\n")
         }
     }
 
     impl ToSource for @ast::Ty {
-        fn to_source(cx: ext_ctxt) -> ~str {
-            ty_to_str(self, cx.parse_sess().interner)
+        fn to_source(&self, cx: ext_ctxt) -> ~str {
+            ty_to_str(*self, cx.parse_sess().interner)
         }
     }
 
     impl ToSource for ~[@ast::Ty] {
-        fn to_source(cx: ext_ctxt) -> ~str {
+        fn to_source(&self, cx: ext_ctxt) -> ~str {
             str::connect(self.map(|i| i.to_source(cx)), ~", ")
         }
     }
 
-    impl ToSource for ~[ast::ty_param] {
-        fn to_source(cx: ext_ctxt) -> ~str {
-            pprust::typarams_to_str(self, cx.parse_sess().interner)
+    impl ToSource for Generics {
+        fn to_source(&self, cx: ext_ctxt) -> ~str {
+            pprust::generics_to_str(self, cx.parse_sess().interner)
         }
     }
 
     impl ToSource for @ast::expr {
-        fn to_source(cx: ext_ctxt) -> ~str {
-            pprust::expr_to_str(self, cx.parse_sess().interner)
+        fn to_source(&self, cx: ext_ctxt) -> ~str {
+            pprust::expr_to_str(*self, cx.parse_sess().interner)
         }
     }
 
     // Alas ... we write these out instead. All redundant.
 
     impl ToTokens for ast::ident {
-        fn to_tokens(cx: ext_ctxt) -> ~[token_tree] {
+        fn to_tokens(&self, cx: ext_ctxt) -> ~[token_tree] {
             cx.parse_tts(self.to_source(cx))
         }
     }
 
     impl ToTokens for @ast::item {
-        fn to_tokens(cx: ext_ctxt) -> ~[token_tree] {
+        fn to_tokens(&self, cx: ext_ctxt) -> ~[token_tree] {
             cx.parse_tts(self.to_source(cx))
         }
     }
 
     impl ToTokens for ~[@ast::item] {
-        fn to_tokens(cx: ext_ctxt) -> ~[token_tree] {
+        fn to_tokens(&self, cx: ext_ctxt) -> ~[token_tree] {
             cx.parse_tts(self.to_source(cx))
         }
     }
 
     impl ToTokens for @ast::Ty {
-        fn to_tokens(cx: ext_ctxt) -> ~[token_tree] {
+        fn to_tokens(&self, cx: ext_ctxt) -> ~[token_tree] {
             cx.parse_tts(self.to_source(cx))
         }
     }
 
     impl ToTokens for ~[@ast::Ty] {
-        fn to_tokens(cx: ext_ctxt) -> ~[token_tree] {
+        fn to_tokens(&self, cx: ext_ctxt) -> ~[token_tree] {
             cx.parse_tts(self.to_source(cx))
         }
     }
 
-    impl ToTokens for ~[ast::ty_param] {
-        fn to_tokens(cx: ext_ctxt) -> ~[token_tree] {
+    impl ToTokens for Generics {
+        fn to_tokens(&self, cx: ext_ctxt) -> ~[token_tree] {
             cx.parse_tts(self.to_source(cx))
         }
     }
 
     impl ToTokens for @ast::expr {
-        fn to_tokens(cx: ext_ctxt) -> ~[token_tree] {
+        fn to_tokens(&self, cx: ext_ctxt) -> ~[token_tree] {
             cx.parse_tts(self.to_source(cx))
         }
     }
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index 2d8b62629ee..8da494b95fd 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -130,21 +130,38 @@ pub fn fold_fn_decl(decl: ast::fn_decl, fld: ast_fold) -> ast::fn_decl {
     }
 }
 
-fn fold_ty_param_bound(tpb: ty_param_bound, fld: ast_fold) -> ty_param_bound {
+fn fold_ty_param_bound(tpb: TyParamBound, fld: ast_fold) -> TyParamBound {
     match tpb {
         TraitTyParamBound(ty) => TraitTyParamBound(fld.fold_ty(ty)),
         RegionTyParamBound => RegionTyParamBound
     }
 }
 
-pub fn fold_ty_param(tp: ty_param, fld: ast_fold) -> ty_param {
-    ast::ty_param { ident: /* FIXME (#2543) */ copy tp.ident,
-                    id: fld.new_id(tp.id),
-                    bounds: @tp.bounds.map(|x| fold_ty_param_bound(*x, fld) )}
+pub fn fold_ty_param(tp: TyParam, fld: ast_fold) -> TyParam {
+    TyParam {ident: tp.ident,
+             id: fld.new_id(tp.id),
+             bounds: @tp.bounds.map(|x| fold_ty_param_bound(*x, fld))}
 }
 
-pub fn fold_ty_params(tps: ~[ty_param], fld: ast_fold) -> ~[ty_param] {
-    tps.map(|x| fold_ty_param(*x, fld))
+pub fn fold_ty_params(tps: &OptVec<TyParam>,
+                      fld: ast_fold) -> OptVec<TyParam> {
+    tps.map(|tp| fold_ty_param(*tp, fld))
+}
+
+pub fn fold_lifetime(l: &Lifetime, fld: ast_fold) -> Lifetime {
+    Lifetime {id: fld.new_id(l.id),
+              span: fld.new_span(l.span),
+              ident: l.ident}
+}
+
+pub fn fold_lifetimes(lts: &OptVec<Lifetime>,
+                      fld: ast_fold) -> OptVec<Lifetime> {
+    lts.map(|l| fold_lifetime(l, fld))
+}
+
+pub fn fold_generics(generics: &Generics, fld: ast_fold) -> Generics {
+    Generics {ty_params: fold_ty_params(&generics.ty_params, fld),
+              lifetimes: fold_lifetimes(&generics.lifetimes, fld)}
 }
 
 pub fn noop_fold_crate(c: crate_, fld: ast_fold) -> crate_ {
@@ -173,7 +190,7 @@ fn noop_fold_foreign_item(&&ni: @foreign_item, fld: ast_fold)
         attrs: vec::map(ni.attrs, |x| fold_attribute(*x)),
         node:
             match ni.node {
-                foreign_item_fn(fdec, purity, typms) => {
+                foreign_item_fn(fdec, purity, ref generics) => {
                     foreign_item_fn(
                         ast::fn_decl {
                             inputs: fdec.inputs.map(|a| fold_arg(*a)),
@@ -181,7 +198,7 @@ fn noop_fold_foreign_item(&&ni: @foreign_item, fld: ast_fold)
                             cf: fdec.cf,
                         },
                         purity,
-                        fold_ty_params(typms, fld))
+                        fold_generics(generics, fld))
                 }
                 foreign_item_const(t) => {
                     foreign_item_const(fld.fold_ty(t))
@@ -218,20 +235,20 @@ pub fn noop_fold_item_underscore(i: item_, fld: ast_fold) -> item_ {
         item_fn(ref decl, purity, ref typms, ref body) => {
             item_fn(fold_fn_decl(/* FIXME (#2543) */ copy *decl, fld),
                     purity,
-                    fold_ty_params(/* FIXME (#2543) */ copy *typms, fld),
+                    fold_generics(typms, fld),
                     fld.fold_block(*body))
         }
         item_mod(m) => item_mod(fld.fold_mod(m)),
         item_foreign_mod(nm) => item_foreign_mod(fld.fold_foreign_mod(nm)),
-        item_ty(t, typms) => item_ty(fld.fold_ty(t),
-                                     fold_ty_params(typms, fld)),
+        item_ty(t, ref typms) => item_ty(fld.fold_ty(t),
+                                     fold_generics(typms, fld)),
         item_enum(ref enum_definition, ref typms) => {
             item_enum(ast::enum_def(ast::enum_def_ {
                 variants: enum_definition.variants.map(
                     |x| fld.fold_variant(*x)),
                 common: enum_definition.common.map(
                     |x| fold_struct_def(*x, fld)),
-            }), fold_ty_params(/* FIXME (#2543) */ copy *typms, fld))
+            }), fold_generics(typms, fld))
         }
         item_struct(ref struct_def, ref typms) => {
             let struct_def = fold_struct_def(
@@ -240,7 +257,7 @@ pub fn noop_fold_item_underscore(i: item_, fld: ast_fold) -> item_ {
             item_struct(struct_def, /* FIXME (#2543) */ copy *typms)
         }
         item_impl(ref tps, ifce, ty, ref methods) => {
-            item_impl(fold_ty_params(/* FIXME (#2543) */ copy *tps, fld),
+            item_impl(fold_generics(tps, fld),
                       ifce.map(|p| fold_trait_ref(*p, fld)),
                       fld.fold_ty(ty),
                       methods.map(|x| fld.fold_method(*x)))
@@ -252,7 +269,7 @@ pub fn noop_fold_item_underscore(i: item_, fld: ast_fold) -> item_ {
                     provided(method) => provided(fld.fold_method(method))
                 }
             };
-            item_trait(fold_ty_params(/* FIXME (#2543) */ copy *tps, fld),
+            item_trait(fold_generics(tps, fld),
                        traits.map(|p| fold_trait_ref(*p, fld)),
                        methods)
         }
@@ -298,7 +315,7 @@ fn noop_fold_method(&&m: @method, fld: ast_fold) -> @method {
     @ast::method {
         ident: fld.fold_ident(m.ident),
         attrs: /* FIXME (#2543) */ copy m.attrs,
-        tps: fold_ty_params(m.tps, fld),
+        generics: fold_generics(&m.generics, fld),
         self_ty: m.self_ty,
         purity: m.purity,
         decl: fold_fn_decl(m.decl, fld),
diff --git a/src/libsyntax/opt_vec.rs b/src/libsyntax/opt_vec.rs
new file mode 100644
index 00000000000..22d69d89e81
--- /dev/null
+++ b/src/libsyntax/opt_vec.rs
@@ -0,0 +1,187 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+/*!
+ *
+ * Defines a type OptVec<T> that can be used in place of ~[T].
+ * OptVec avoids the need for allocation for empty vectors.
+ * OptVec implements the iterable interface as well as
+ * other useful things like `push()` and `len()`.
+ */
+
+use core::prelude::*;
+use core::iter;
+use core::iter::BaseIter;
+
+#[auto_encode]
+#[auto_decode]
+pub enum OptVec<T> {
+    Empty,
+    Vec(~[T])
+}
+
+pub fn with<T>(+t: T) -> OptVec<T> {
+    Vec(~[t])
+}
+
+impl<T> OptVec<T> {
+    fn push(&mut self, +t: T) {
+        match *self {
+            Vec(ref mut v) => {
+                v.push(t);
+                return;
+            }
+            Empty => {}
+        }
+
+        // FIXME(#5074): flow insensitive means we can't move
+        // assignment inside `match`
+        *self = Vec(~[t]);
+    }
+
+    fn map<U>(&self, op: &fn(&T) -> U) -> OptVec<U> {
+        match *self {
+            Empty => Empty,
+            Vec(ref v) => Vec(v.map(op))
+        }
+    }
+
+    pure fn get(&self, i: uint) -> &self/T {
+        match *self {
+            Empty => fail!(fmt!("Invalid index %u", i)),
+            Vec(ref v) => &v[i]
+        }
+    }
+
+    pure fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    pure fn len(&self) -> uint {
+        match *self {
+            Empty => 0,
+            Vec(ref v) => v.len()
+        }
+    }
+
+    pure fn to_vec(self) -> ~[T] {
+        match self {
+            Empty => ~[],
+            Vec(v) => v
+        }
+    }
+}
+
+impl<T:Copy> OptVec<T> {
+    fn prepend(&self, +t: T) -> OptVec<T> {
+        let mut v0 = ~[t];
+        match *self {
+            Empty => {}
+            Vec(v1) => { v0.push_all(v1); }
+        }
+        return Vec(v0);
+    }
+
+    fn push_all<I: BaseIter<T>>(&mut self, from: &I) {
+        for from.each |e| {
+            self.push(copy *e);
+        }
+    }
+}
+
+impl<A:Eq> Eq for OptVec<A> {
+    pure fn eq(&self, other: &OptVec<A>) -> bool {
+        // Note: cannot use #[deriving_eq] here because
+        // (Empty, Vec(~[])) ought to be equal.
+        match (self, other) {
+            (&Empty, &Empty) => true,
+            (&Empty, &Vec(ref v)) => v.is_empty(),
+            (&Vec(ref v), &Empty) => v.is_empty(),
+            (&Vec(ref v1), &Vec(ref v2)) => *v1 == *v2
+        }
+    }
+
+    pure fn ne(&self, other: &OptVec<A>) -> bool {
+        !self.eq(other)
+    }
+}
+
+impl<A> BaseIter<A> for OptVec<A> {
+    pure fn each(&self, blk: fn(v: &A) -> bool) {
+        match *self {
+            Empty => {}
+            Vec(ref v) => v.each(blk)
+        }
+    }
+
+    pure fn size_hint(&self) -> Option<uint> {
+        Some(self.len())
+    }
+}
+
+impl<A> iter::ExtendedIter<A> for OptVec<A> {
+    #[inline(always)]
+    pure fn eachi(&self, blk: fn(+v: uint, v: &A) -> bool) {
+        iter::eachi(self, blk)
+    }
+    #[inline(always)]
+    pure fn all(&self, blk: fn(&A) -> bool) -> bool {
+        iter::all(self, blk)
+    }
+    #[inline(always)]
+    pure fn any(&self, blk: fn(&A) -> bool) -> bool {
+        iter::any(self, blk)
+    }
+    #[inline(always)]
+    pure fn foldl<B>(&self, +b0: B, blk: fn(&B, &A) -> B) -> B {
+        iter::foldl(self, b0, blk)
+    }
+    #[inline(always)]
+    pure fn position(&self, f: fn(&A) -> bool) -> Option<uint> {
+        iter::position(self, f)
+    }
+    #[inline(always)]
+    pure fn map_to_vec<B>(&self, op: fn(&A) -> B) -> ~[B] {
+        iter::map_to_vec(self, op)
+    }
+    #[inline(always)]
+    pure fn flat_map_to_vec<B,IB:BaseIter<B>>(&self, op: fn(&A) -> IB)
+        -> ~[B] {
+        iter::flat_map_to_vec(self, op)
+    }
+
+}
+
+impl<A: Eq> iter::EqIter<A> for OptVec<A> {
+    #[inline(always)]
+    pure fn contains(&self, x: &A) -> bool { iter::contains(self, x) }
+    #[inline(always)]
+    pure fn count(&self, x: &A) -> uint { iter::count(self, x) }
+}
+
+impl<A: Copy> iter::CopyableIter<A> for OptVec<A> {
+    #[inline(always)]
+    pure fn filter_to_vec(&self, pred: fn(&A) -> bool) -> ~[A] {
+        iter::filter_to_vec(self, pred)
+    }
+    #[inline(always)]
+    pure fn to_vec(&self) -> ~[A] { iter::to_vec(self) }
+    #[inline(always)]
+    pure fn find(&self, f: fn(&A) -> bool) -> Option<A> {
+        iter::find(self, f)
+    }
+}
+
+impl<A: Copy+Ord> iter::CopyableOrderedIter<A> for OptVec<A> {
+    #[inline(always)]
+    pure fn min(&self) -> A { iter::min(self) }
+    #[inline(always)]
+    pure fn max(&self) -> A { iter::max(self) }
+}
diff --git a/src/libsyntax/parse/common.rs b/src/libsyntax/parse/common.rs
index 57d62d628dc..a92eb2db42a 100644
--- a/src/libsyntax/parse/common.rs
+++ b/src/libsyntax/parse/common.rs
@@ -20,6 +20,9 @@ use core::option::{None, Option, Some};
 use core::option;
 use std::oldmap::HashMap;
 
+use opt_vec;
+use opt_vec::OptVec;
+
 // SeqSep : a sequence separator (token)
 // and whether a trailing separator is allowed.
 pub struct SeqSep {
@@ -221,10 +224,10 @@ pub impl Parser {
 
     // parse a sequence bracketed by '<' and '>', stopping
     // before the '>'.
-    fn parse_seq_to_before_gt<T:Copy>(sep: Option<token::Token>,
-                                       f: fn(Parser) -> T) -> ~[T] {
+    fn parse_seq_to_before_gt<T: Copy>(sep: Option<token::Token>,
+                                       f: fn(Parser) -> T) -> OptVec<T> {
         let mut first = true;
-        let mut v = ~[];
+        let mut v = opt_vec::Empty;
         while *self.token != token::GT
             && *self.token != token::BINOP(token::SHR) {
             match sep {
@@ -236,29 +239,16 @@ pub impl Parser {
             }
             v.push(f(self));
         }
-
         return v;
     }
 
-    fn parse_seq_to_gt<T:Copy>(sep: Option<token::Token>,
-                                f: fn(Parser) -> T) -> ~[T] {
+    fn parse_seq_to_gt<T: Copy>(sep: Option<token::Token>,
+                                f: fn(Parser) -> T) -> OptVec<T> {
         let v = self.parse_seq_to_before_gt(sep, f);
         self.expect_gt();
-
         return v;
     }
 
-    // parse a sequence bracketed by '<' and '>'
-    fn parse_seq_lt_gt<T:Copy>(sep: Option<token::Token>,
-                                f: fn(Parser) -> T) -> spanned<~[T]> {
-        let lo = self.span.lo;
-        self.expect(token::LT);
-        let result = self.parse_seq_to_before_gt::<T>(sep, f);
-        let hi = self.span.hi;
-        self.expect_gt();
-        return spanned(lo, hi, result);
-    }
-
     // parse a sequence, including the closing delimiter. The function
     // f must consume tokens until reaching the next separator or
     // closing bracket.
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index 59ad35b38e4..6b4f195d076 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -51,7 +51,7 @@ use ast::{token_tree, trait_method, trait_ref, tt_delim, tt_seq, tt_tok};
 use ast::{tt_nonterminal, tuple_variant_kind, Ty, ty_, ty_bot, ty_box};
 use ast::{ty_field, ty_fixed_length_vec, ty_closure, ty_bare_fn};
 use ast::{ty_infer, ty_mac, ty_method};
-use ast::{ty_nil, ty_param, ty_param_bound, ty_path, ty_ptr, ty_rec, ty_rptr};
+use ast::{ty_nil, TyParam, TyParamBound, ty_path, ty_ptr, ty_rec, ty_rptr};
 use ast::{ty_tup, ty_u32, ty_uniq, ty_vec, type_value_ns, uniq};
 use ast::{unnamed_field, unsafe_blk, unsafe_fn, variant, view_item};
 use ast::{view_item_, view_item_extern_mod, view_item_use};
@@ -84,6 +84,8 @@ use parse::token;
 use parse::{new_sub_parser_from_file, next_node_id, ParseSess};
 use print::pprust::expr_to_str;
 use util::interner::Interner;
+use opt_vec;
+use opt_vec::OptVec;
 
 use core::cmp;
 use core::either::{Either, Left, Right};
@@ -439,7 +441,7 @@ pub impl Parser {
             // could change.
             let ident = p.parse_method_name();
 
-            let tps = p.parse_ty_params();
+            let generics = p.parse_generics();
 
             let (self_ty, d) = do self.parse_fn_decl_with_self() |p| {
                 // This is somewhat dubious; We don't want to allow argument
@@ -464,7 +466,7 @@ pub impl Parser {
                     attrs: attrs,
                     purity: pur,
                     decl: d,
-                    tps: tps,
+                    generics: generics,
                     self_ty: self_ty,
                     id: p.get_id(),
                     span: mk_sp(lo, hi)
@@ -478,7 +480,7 @@ pub impl Parser {
                 provided(@ast::method {
                     ident: ident,
                     attrs: attrs,
-                    tps: tps,
+                    generics: generics,
                     self_ty: self_ty,
                     purity: pur,
                     decl: d,
@@ -921,19 +923,7 @@ pub impl Parser {
         };
 
         // Parse any lifetime or type parameters which may appear:
-        let tps = {
-            if !self.eat(token::LT) {
-                ~[]
-            } else {
-                // First consume lifetimes.
-                let _lifetimes = self.parse_lifetimes();
-                let result = self.parse_seq_to_gt(
-                    Some(token::COMMA),
-                    |p| p.parse_ty(false));
-                result
-            }
-        };
-
+        let tps = self.parse_generic_values();
         let hi = self.span.lo;
 
         @ast::path { span: mk_sp(lo, hi),
@@ -979,7 +969,7 @@ pub impl Parser {
         }
     }
 
-    fn parse_lifetimes() -> ~[ast::Lifetime] {
+    fn parse_lifetimes() -> OptVec<ast::Lifetime> {
         /*!
          *
          * Parses zero or more comma separated lifetimes.
@@ -988,7 +978,7 @@ pub impl Parser {
          * lists, where we expect something like `<'a, 'b, T>`.
          */
 
-        let mut res = ~[];
+        let mut res = opt_vec::Empty;
         loop {
             match *self.token {
                 token::LIFETIME(_) => {
@@ -1163,7 +1153,7 @@ pub impl Parser {
                     let remaining_exprs =
                         self.parse_seq_to_end(token::RBRACKET,
                             seq_sep_trailing_allowed(token::COMMA),
-                            |p| p.parse_expr());
+                            |p| p.parse_expr()).to_vec();
                     ex = expr_vec(~[first_expr] + remaining_exprs, mutbl);
                 } else {
                     // Vector with one element.
@@ -1295,8 +1285,7 @@ pub impl Parser {
                     self.bump();
                     let tys = if self.eat(token::MOD_SEP) {
                         self.expect(token::LT);
-                        self.parse_seq_to_gt(Some(token::COMMA),
-                                             |p| p.parse_ty(false))
+                        self.parse_generic_values_after_lt()
                     } else {
                         ~[]
                     };
@@ -1426,7 +1415,7 @@ pub impl Parser {
                 vec::append(
                     self.parse_seq_to_before_end(
                         ket, seq_sep_none(),
-                        |p| p.parse_token_tree()),
+                        |p| p.parse_token_tree()).to_vec(),
                     // the close delimiter:
                     ~[parse_any_tt_tok(self)])))
           }
@@ -2636,81 +2625,105 @@ pub impl Parser {
         if self.eat_keyword(~"once") { ast::Once } else { ast::Many }
     }
 
-    fn parse_optional_ty_param_bounds() -> @~[ty_param_bound] {
-        let mut bounds = ~[];
-        if self.eat(token::COLON) {
-            loop {
-                if self.eat(token::BINOP(token::AND)) {
-                    if self.eat_keyword(~"static") {
-                        bounds.push(RegionTyParamBound);
-                    } else {
-                        self.span_err(*self.span,
-                                      ~"`&static` is the only permissible \
-                                        region bound here");
-                    }
-                } else if is_ident(*self.token) {
-                    let maybe_bound = match *self.token {
-                      token::IDENT(copy sid, _) => {
+    fn parse_optional_ty_param_bounds() -> @OptVec<TyParamBound> {
+        if !self.eat(token::COLON) {
+            return @opt_vec::Empty;
+        }
+
+        let mut result = opt_vec::Empty;
+        loop {
+            if self.eat(token::BINOP(token::AND)) {
+                if self.eat_keyword(~"static") {
+                    result.push(RegionTyParamBound);
+                } else {
+                    self.span_err(*self.span,
+                                  ~"`&static` is the only permissible \
+                                    region bound here");
+                }
+            } else if is_ident(*self.token) {
+                let maybe_bound = match *self.token {
+                    token::IDENT(sid, _) => {
                         match *self.id_to_str(sid) {
+                            ~"send" |
+                            ~"copy" |
+                            ~"const" |
+                            ~"owned" => {
+                                self.obsolete(
+                                    *self.span,
+                                    ObsoleteLowerCaseKindBounds);
+
+                                // Bogus value, but doesn't matter, since
+                                // is an error
+                                Some(TraitTyParamBound(
+                                    self.mk_ty_path(sid)))
+                            }
 
-                          ~"send"
-                          | ~"copy"
-                          | ~"const"
-                          | ~"owned" => {
-                            self.obsolete(*self.span,
-                                          ObsoleteLowerCaseKindBounds);
-                            // Bogus value, but doesn't matter, since
-                            // is an error
-                            Some(TraitTyParamBound(self.mk_ty_path(sid)))
-                          }
-
-                          _ => None
+                            _ => None
                         }
-                      }
-                      _ => self.bug(
-                          ~"is_ident() said this would be an identifier")
-                    };
+                    }
+                    _ => fail!()
+                };
 
-                    match maybe_bound {
-                        Some(bound) => {
-                            self.bump();
-                            bounds.push(bound);
-                        }
-                        None => {
-                            let ty = self.parse_ty(false);
-                            bounds.push(TraitTyParamBound(ty));
-                        }
+                match maybe_bound {
+                    Some(bound) => {
+                        self.bump();
+                        result.push(bound);
+                    }
+                    None => {
+                        let ty = self.parse_ty(false);
+                        result.push(TraitTyParamBound(ty));
                     }
-                } else {
-                    break;
                 }
+            } else {
+                break;
+            }
 
-                if self.eat(token::BINOP(token::PLUS)) {
-                    loop;
-                }
+            if self.eat(token::BINOP(token::PLUS)) {
+                loop;
+            }
 
-                if is_ident_or_path(*self.token) {
-                    self.obsolete(*self.span,
-                                  ObsoleteTraitBoundSeparator);
-                }
+            if is_ident_or_path(*self.token) {
+                self.obsolete(*self.span,
+                              ObsoleteTraitBoundSeparator);
             }
         }
-        return @bounds;
+
+        return @result;
     }
 
-    fn parse_ty_param() -> ty_param {
+    fn parse_ty_param() -> TyParam {
         let ident = self.parse_ident();
         let bounds = self.parse_optional_ty_param_bounds();
-        ast::ty_param { ident: ident, id: self.get_id(), bounds: bounds }
+        ast::TyParam { ident: ident, id: self.get_id(), bounds: bounds }
     }
 
-    fn parse_ty_params() -> ~[ty_param] {
+    fn parse_generics() -> ast::Generics {
         if self.eat(token::LT) {
-            let _lifetimes = self.parse_lifetimes();
-            self.parse_seq_to_gt(
+            let lifetimes = self.parse_lifetimes();
+            let ty_params = self.parse_seq_to_gt(
                 Some(token::COMMA),
-                |p| p.parse_ty_param())
-        } else { ~[] }
+                |p| p.parse_ty_param());
+            return ast::Generics {lifetimes: lifetimes,
+                                  ty_params: ty_params};
+        } else {
+            return ast_util::empty_generics();
+        }
+    }
+
+    fn parse_generic_values() -> ~[@Ty] {
+        if !self.eat(token::LT) {
+            ~[]
+        } else {
+            self.parse_generic_values_after_lt()
+        }
+    }
+
+    fn parse_generic_values_after_lt() -> ~[@Ty] {
+        let _lifetimes = self.parse_lifetimes();
+        let result = self.parse_seq_to_gt(
+            Some(token::COMMA),
+            |p| p.parse_ty(false));
+        result.to_vec()
     }
 
     fn parse_fn_decl(parse_arg_fn: fn(Parser) -> arg_or_capture_item)
@@ -2802,7 +2815,7 @@ pub impl Parser {
                     args_or_capture_items =
                         self.parse_seq_to_before_end(token::RPAREN,
                                                      sep,
-                                                     parse_arg_fn);
+                                                     parse_arg_fn).to_vec();
                 }
                 token::RPAREN => {
                     args_or_capture_items = ~[];
@@ -2818,7 +2831,7 @@ pub impl Parser {
             args_or_capture_items =
                 self.parse_seq_to_before_end(token::RPAREN,
                                              sep,
-                                             parse_arg_fn);
+                                             parse_arg_fn).to_vec();
         }
 
         self.expect(token::RPAREN);
@@ -2861,10 +2874,10 @@ pub impl Parser {
         }
     }
 
-    fn parse_fn_header() -> (ident, ~[ty_param]) {
+    fn parse_fn_header() -> (ident, ast::Generics) {
         let id = self.parse_value_ident();
-        let ty_params = self.parse_ty_params();
-        (id, ty_params)
+        let generics = self.parse_generics();
+        (id, generics)
     }
 
     fn mk_item(+lo: BytePos, +hi: BytePos, +ident: ident,
@@ -2879,10 +2892,10 @@ pub impl Parser {
     }
 
     fn parse_item_fn(purity: purity) -> item_info {
-        let (ident, tps) = self.parse_fn_header();
+        let (ident, generics) = self.parse_fn_header();
         let decl = self.parse_fn_decl(|p| p.parse_arg());
         let (inner_attrs, body) = self.parse_inner_attrs_and_block(true);
-        (ident, item_fn(decl, purity, tps, body), Some(inner_attrs))
+        (ident, item_fn(decl, purity, generics, body), Some(inner_attrs))
     }
 
     fn parse_method_name() -> ident {
@@ -2899,7 +2912,7 @@ pub impl Parser {
         let visa = self.parse_visibility();
         let pur = self.parse_fn_purity();
         let ident = self.parse_method_name();
-        let tps = self.parse_ty_params();
+        let generics = self.parse_generics();
         let (self_ty, decl) = do self.parse_fn_decl_with_self() |p| {
             p.parse_arg()
         };
@@ -2911,7 +2924,7 @@ pub impl Parser {
         @ast::method {
             ident: ident,
             attrs: attrs,
-            tps: tps,
+            generics: generics,
             self_ty: self_ty,
             purity: pur,
             decl: decl,
@@ -2926,7 +2939,7 @@ pub impl Parser {
     fn parse_item_trait() -> item_info {
         let ident = self.parse_ident();
         self.parse_region_param();
-        let tps = self.parse_ty_params();
+        let tps = self.parse_generics();
 
         // Parse traits, if necessary.
         let traits;
@@ -2954,12 +2967,7 @@ pub impl Parser {
         }
 
         // First, parse type parameters if necessary.
-        let mut tps;
-        if *self.token == token::LT {
-            tps = self.parse_ty_params();
-        } else {
-            tps = ~[];
-        }
+        let generics = self.parse_generics();
 
         // This is a new-style impl declaration.
         // XXX: clownshoes
@@ -3007,37 +3015,7 @@ pub impl Parser {
             }
         }
 
-        (ident, item_impl(tps, opt_trait, ty, meths), None)
-    }
-
-    // Instantiates ident <i> with references to <typarams> as arguments.
-    // Used to create a path that refers to a class which will be defined as
-    // the return type of the ctor function.
-    fn ident_to_path_tys(i: ident,
-                         typarams: ~[ty_param]) -> @path {
-        let s = *self.last_span;
-
-        @ast::path {
-             span: s,
-             global: false,
-             idents: ~[i],
-             rp: None,
-             types: do typarams.map |tp| {
-                @Ty {
-                    id: self.get_id(),
-                    node: ty_path(ident_to_path(s, tp.ident), self.get_id()),
-                    span: s
-                }
-            }
-         }
-    }
-
-    fn ident_to_path(i: ident) -> @path {
-        @ast::path { span: *self.last_span,
-                     global: false,
-                     idents: ~[i],
-                     rp: None,
-                     types: ~[] }
+        (ident, item_impl(generics, opt_trait, ty, meths), None)
     }
 
     fn parse_trait_ref() -> @trait_ref {
@@ -3050,13 +3028,13 @@ pub impl Parser {
     fn parse_trait_ref_list(ket: token::Token) -> ~[@trait_ref] {
         self.parse_seq_to_before_end(
             ket, seq_sep_none(),
-            |p| p.parse_trait_ref())
+            |p| p.parse_trait_ref()).to_vec()
     }
 
     fn parse_item_struct() -> item_info {
         let class_name = self.parse_value_ident();
         self.parse_region_param();
-        let ty_params = self.parse_ty_params();
+        let generics = self.parse_generics();
         if self.eat(token::COLON) {
             self.obsolete(*self.span, ObsoleteClassTraits);
             let _ = self.parse_trait_ref_list(token::LBRACE);
@@ -3133,7 +3111,7 @@ pub impl Parser {
              fields: fields,
              dtor: actual_dtor,
              ctor_id: if is_tuple_like { Some(new_id) } else { None }
-         }, ty_params),
+         }, generics),
          None)
     }
 
@@ -3397,13 +3375,13 @@ pub impl Parser {
         let lo = self.span.lo;
         let vis = self.parse_visibility();
         let purity = self.parse_fn_purity();
-        let (ident, tps) = self.parse_fn_header();
+        let (ident, generics) = self.parse_fn_header();
         let decl = self.parse_fn_decl(|p| p.parse_arg());
         let mut hi = self.span.hi;
         self.expect(token::SEMI);
         @ast::foreign_item { ident: ident,
                              attrs: attrs,
-                             node: foreign_item_fn(decl, purity, tps),
+                             node: foreign_item_fn(decl, purity, generics),
                              id: self.get_id(),
                              span: mk_sp(lo, hi),
                              vis: vis }
@@ -3566,7 +3544,7 @@ pub impl Parser {
     fn parse_item_type() -> item_info {
         let (_, ident) = self.parse_type_decl();
         self.parse_region_param();
-        let tps = self.parse_ty_params();
+        let tps = self.parse_generics();
         self.expect(token::EQ);
         let ty = self.parse_ty(false);
         self.expect(token::SEMI);
@@ -3622,8 +3600,7 @@ pub impl Parser {
         };
     }
 
-    fn parse_enum_def(ty_params: ~[ast::ty_param])
-                   -> enum_def {
+    fn parse_enum_def(+generics: ast::Generics) -> enum_def {
         let mut variants: ~[variant] = ~[];
         let mut all_nullary = true, have_disr = false;
         let mut common_fields = None;
@@ -3650,7 +3627,7 @@ pub impl Parser {
             if self.eat_keyword(~"enum") {
                 ident = self.parse_ident();
                 self.expect(token::LBRACE);
-                let nested_enum_def = self.parse_enum_def(ty_params);
+                let nested_enum_def = self.parse_enum_def(generics);
                 kind = enum_variant_kind(nested_enum_def);
                 needs_comma = false;
             } else {
@@ -3706,7 +3683,7 @@ pub impl Parser {
     fn parse_item_enum() -> item_info {
         let id = self.parse_ident();
         self.parse_region_param();
-        let ty_params = self.parse_ty_params();
+        let generics = self.parse_generics();
         // Newtype syntax
         if *self.token == token::EQ {
             self.bump();
@@ -3729,14 +3706,14 @@ pub impl Parser {
                     enum_def(
                         ast::enum_def_ { variants: ~[variant], common: None }
                     ),
-                    ty_params),
+                    generics),
                 None
             );
         }
         self.expect(token::LBRACE);
 
-        let enum_definition = self.parse_enum_def(ty_params);
-        (id, item_enum(enum_definition, ty_params), None)
+        let enum_definition = self.parse_enum_def(generics);
+        (id, item_enum(enum_definition, generics), None)
     }
 
     fn parse_fn_ty_sigil() -> Option<Sigil> {
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index d5a09e087a0..5eb40626437 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -14,6 +14,8 @@ use ast::{RegionTyParamBound, TraitTyParamBound, required, provided};
 use ast;
 use ast_util;
 use ast_util::{operator_prec};
+use opt_vec;
+use opt_vec::OptVec;
 use attr;
 use codemap::{CodeMap, BytePos};
 use codemap;
@@ -164,8 +166,9 @@ pub fn item_to_str(i: @ast::item, intr: @ident_interner) -> ~str {
     to_str(i, print_item, intr)
 }
 
-pub fn typarams_to_str(tps: ~[ast::ty_param], intr: @ident_interner) -> ~str {
-    to_str(tps, print_type_params, intr)
+pub fn generics_to_str(generics: &ast::Generics,
+                       intr: @ident_interner) -> ~str {
+    to_str(generics, print_generics, intr)
 }
 
 pub fn path_to_str(&&p: @ast::path, intr: @ident_interner) -> ~str {
@@ -173,10 +176,10 @@ pub fn path_to_str(&&p: @ast::path, intr: @ident_interner) -> ~str {
 }
 
 pub fn fun_to_str(decl: ast::fn_decl, name: ast::ident,
-                  params: ~[ast::ty_param], intr: @ident_interner) -> ~str {
+                  generics: &ast::Generics, intr: @ident_interner) -> ~str {
     do io::with_str_writer |wr| {
         let s = rust_printer(wr, intr);
-        print_fn(s, decl, None, name, params, None, ast::inherited);
+        print_fn(s, decl, None, name, generics, None, ast::inherited);
         end(s); // Close the head box
         end(s); // Close the outer box
         eof(s.s);
@@ -300,7 +303,7 @@ pub fn synth_comment(s: @ps, text: ~str) {
     word(s.s, ~"*/");
 }
 
-pub fn commasep<IN>(s: @ps, b: breaks, elts: ~[IN], op: fn(@ps, IN)) {
+pub fn commasep<IN>(s: @ps, b: breaks, elts: ~[IN], op: &fn(@ps, IN)) {
     box(s, 0u, b);
     let mut first = true;
     for elts.each |elt| {
@@ -459,8 +462,8 @@ pub fn print_foreign_item(s: @ps, item: @ast::foreign_item) {
     maybe_print_comment(s, item.span.lo);
     print_outer_attributes(s, item.attrs);
     match item.node {
-      ast::foreign_item_fn(decl, purity, typarams) => {
-        print_fn(s, decl, Some(purity), item.ident, typarams, None,
+      ast::foreign_item_fn(decl, purity, ref generics) => {
+        print_fn(s, decl, Some(purity), item.ident, generics, None,
                  ast::inherited);
         end(s); // end head-ibox
         word(s.s, ~";");
@@ -505,7 +508,7 @@ pub fn print_item(s: @ps, &&item: @ast::item) {
             /* FIXME (#2543) */ copy *decl,
             Some(purity),
             item.ident,
-            /* FIXME (#2543) */ copy *typarams,
+            typarams,
             None,
             item.vis
         );
@@ -536,12 +539,12 @@ pub fn print_item(s: @ps, &&item: @ast::item) {
         print_foreign_mod(s, nmod, item.attrs);
         bclose(s, item.span);
       }
-      ast::item_ty(ty, params) => {
+      ast::item_ty(ty, ref params) => {
         ibox(s, indent_unit);
         ibox(s, 0u);
         word_nbsp(s, visibility_qualified(item.vis, ~"type"));
         print_ident(s, item.ident);
-        print_type_params(s, params);
+        print_generics(s, params);
         end(s); // end the inner ibox
 
         space(s.s);
@@ -554,21 +557,21 @@ pub fn print_item(s: @ps, &&item: @ast::item) {
         print_enum_def(
             s,
             *enum_definition,
-            /* FIXME (#2543) */ copy *params,
+            params,
             item.ident,
             item.span,
             item.vis
         );
       }
-      ast::item_struct(struct_def, tps) => {
+      ast::item_struct(struct_def, ref generics) => {
           head(s, visibility_qualified(item.vis, ~"struct"));
-          print_struct(s, struct_def, tps, item.ident, item.span);
+          print_struct(s, struct_def, generics, item.ident, item.span);
       }
 
-      ast::item_impl(tps, opt_trait, ty, methods) => {
+      ast::item_impl(ref generics, opt_trait, ty, methods) => {
         head(s, visibility_qualified(item.vis, ~"impl"));
-        if !tps.is_empty() {
-            print_type_params(s, tps);
+        if !generics.is_empty() {
+            print_generics(s, generics);
             space(s.s);
         }
 
@@ -594,10 +597,10 @@ pub fn print_item(s: @ps, &&item: @ast::item) {
             bclose(s, item.span);
         }
       }
-      ast::item_trait(ref tps, ref traits, ref methods) => {
+      ast::item_trait(ref generics, ref traits, ref methods) => {
         head(s, visibility_qualified(item.vis, ~"trait"));
         print_ident(s, item.ident);
-        print_type_params(s, /* FIXME (#2543) */ copy *tps);
+        print_generics(s, generics);
         if traits.len() != 0u {
             word(s.s, ~":");
             for traits.each |trait_| {
@@ -629,7 +632,7 @@ pub fn print_item(s: @ps, &&item: @ast::item) {
 }
 
 pub fn print_enum_def(s: @ps, enum_definition: ast::enum_def,
-                      params: ~[ast::ty_param], ident: ast::ident,
+                      generics: &ast::Generics, ident: ast::ident,
                       span: codemap::span, visibility: ast::visibility) {
     let mut newtype =
         vec::len(enum_definition.variants) == 1u &&
@@ -648,7 +651,7 @@ pub fn print_enum_def(s: @ps, enum_definition: ast::enum_def,
     }
 
     print_ident(s, ident);
-    print_type_params(s, params);
+    print_generics(s, generics);
     space(s.s);
     if newtype {
         word_space(s, ~"=");
@@ -706,12 +709,12 @@ pub fn print_visibility(s: @ps, vis: ast::visibility) {
 
 pub fn print_struct(s: @ps,
                     struct_def: @ast::struct_def,
-                    tps: ~[ast::ty_param],
+                    generics: &ast::Generics,
                     ident: ast::ident,
                     span: codemap::span) {
     print_ident(s, ident);
     nbsp(s);
-    print_type_params(s, tps);
+    print_generics(s, generics);
     if ast_util::struct_def_is_tuple_like(struct_def) {
         popen(s);
         let mut first = true;
@@ -823,7 +826,8 @@ pub fn print_variant(s: @ps, v: ast::variant) {
         }
         ast::struct_variant_kind(struct_def) => {
             head(s, ~"");
-            print_struct(s, struct_def, ~[], v.node.name, v.span);
+            let generics = ast_util::empty_generics();
+            print_struct(s, struct_def, &generics, v.node.name, v.span);
         }
         ast::enum_variant_kind(ref enum_definition) => {
             print_variants(s, (*enum_definition).variants, v.span);
@@ -844,7 +848,7 @@ pub fn print_ty_method(s: @ps, m: ast::ty_method) {
     maybe_print_comment(s, m.span.lo);
     print_outer_attributes(s, m.attrs);
     print_ty_fn(s, None, None, None, m.purity, ast::Many,
-                m.decl, Some(m.ident), Some(m.tps),
+                m.decl, Some(m.ident), Some(&m.generics),
                 Some(m.self_ty.node));
     word(s.s, ~";");
 }
@@ -861,7 +865,7 @@ pub fn print_method(s: @ps, meth: @ast::method) {
     maybe_print_comment(s, meth.span.lo);
     print_outer_attributes(s, meth.attrs);
     print_fn(s, meth.decl, Some(meth.purity),
-             meth.ident, meth.tps, Some(meth.self_ty.node),
+             meth.ident, &meth.generics, Some(meth.self_ty.node),
              meth.vis);
     word(s.s, ~" ");
     print_block_with_attrs(s, meth.body, meth.attrs);
@@ -1714,14 +1718,14 @@ pub fn print_fn(s: @ps,
                 decl: ast::fn_decl,
                 purity: Option<ast::purity>,
                 name: ast::ident,
-                typarams: ~[ast::ty_param],
+                generics: &ast::Generics,
                 opt_self_ty: Option<ast::self_ty_>,
                 vis: ast::visibility) {
     head(s, ~"");
     print_fn_header_info(s, opt_self_ty, purity, ast::Many, None, vis);
     nbsp(s);
     print_ident(s, name);
-    print_type_params(s, typarams);
+    print_generics(s, generics);
     print_fn_args_and_ret(s, decl, opt_self_ty);
 }
 
@@ -1791,11 +1795,11 @@ pub fn print_arg_mode(s: @ps, m: ast::mode) {
     if ms != ~"" { word(s.s, ms); }
 }
 
-pub fn print_bounds(s: @ps, bounds: @~[ast::ty_param_bound]) {
+pub fn print_bounds(s: @ps, bounds: @OptVec<ast::TyParamBound>) {
     if !bounds.is_empty() {
         word(s.s, ~":");
         let mut first = true;
-        for vec::each(*bounds) |&bound| {
+        for bounds.each |bound| {
             nbsp(s);
             if first {
                 first = false;
@@ -1803,7 +1807,7 @@ pub fn print_bounds(s: @ps, bounds: @~[ast::ty_param_bound]) {
                 word_space(s, ~"+");
             }
 
-            match bound {
+            match *bound {
                 TraitTyParamBound(ty) => print_type(s, ty),
                 RegionTyParamBound => word(s.s, ~"&static"),
             }
@@ -1811,14 +1815,33 @@ pub fn print_bounds(s: @ps, bounds: @~[ast::ty_param_bound]) {
     }
 }
 
-pub fn print_type_params(s: @ps, &&params: ~[ast::ty_param]) {
-    if vec::len(params) > 0u {
+pub fn print_lifetime(s: @ps, lifetime: &ast::Lifetime) {
+    word(s.s, ~"'");
+    print_ident(s, lifetime.ident);
+}
+
+pub fn print_generics(s: @ps, &&generics: &ast::Generics) {
+    let total = generics.lifetimes.len() + generics.ty_params.len();
+    if total > 0 {
         word(s.s, ~"<");
-        fn printParam(s: @ps, param: ast::ty_param) {
-            print_ident(s, param.ident);
-            print_bounds(s, param.bounds);
+        fn print_item(s: @ps, generics: &ast::Generics, idx: uint) {
+            if idx < generics.lifetimes.len() {
+                let lifetime = generics.lifetimes.get(idx);
+                print_lifetime(s, lifetime);
+            } else {
+                let param = generics.ty_params.get(idx);
+                print_ident(s, param.ident);
+                print_bounds(s, param.bounds);
+            }
         }
-        commasep(s, inconsistent, params, printParam);
+
+        let mut ints = ~[];
+        for uint::range(0, total) |i| {
+            ints.push(i);
+        }
+
+        commasep(s, inconsistent, ints,
+                 |s, i| print_item(s, generics, i));
         word(s.s, ~">");
     }
 }
@@ -1954,7 +1977,7 @@ pub fn print_ty_fn(s: @ps,
                    purity: ast::purity,
                    onceness: ast::Onceness,
                    decl: ast::fn_decl, id: Option<ast::ident>,
-                   tps: Option<~[ast::ty_param]>,
+                   generics: Option<&ast::Generics>,
                    opt_self_ty: Option<ast::self_ty_>) {
     ibox(s, indent_unit);
 
@@ -1968,7 +1991,7 @@ pub fn print_ty_fn(s: @ps,
     print_onceness(s, onceness);
     word(s.s, ~"fn");
     match id { Some(id) => { word(s.s, ~" "); print_ident(s, id); } _ => () }
-    match tps { Some(tps) => print_type_params(s, tps), _ => () }
+    match generics { Some(g) => print_generics(s, g), _ => () }
     zerobreak(s.s);
 
     popen(s);
@@ -2301,7 +2324,8 @@ pub mod test {
                               span: codemap::dummy_sp()},
             cf: ast::return_val
         };
-        check_equal (&fun_to_str(decl, abba_ident, ~[],mock_interner),
+        let generics = ast_util::empty_generics();
+        check_equal (&fun_to_str(decl, abba_ident, &generics, mock_interner),
                      &~"fn abba()");
     }
 
diff --git a/src/libsyntax/syntax.rc b/src/libsyntax/syntax.rc
index 05bbe43ee9a..9eb7507f3d0 100644
--- a/src/libsyntax/syntax.rc
+++ b/src/libsyntax/syntax.rc
@@ -35,6 +35,7 @@ pub mod syntax {
     pub use parse;
 }
 
+pub mod opt_vec;
 pub mod attr;
 pub mod diagnostic;
 pub mod codemap;
diff --git a/src/libsyntax/visit.rs b/src/libsyntax/visit.rs
index 3701607ffc1..95a6500955d 100644
--- a/src/libsyntax/visit.rs
+++ b/src/libsyntax/visit.rs
@@ -15,6 +15,7 @@ use ast;
 use ast_util;
 use codemap::span;
 use parse;
+use opt_vec;
 
 use core::option;
 use core::vec;
@@ -30,11 +31,11 @@ use core::vec;
 pub enum vt<E> { mk_vt(visitor<E>), }
 
 pub enum fn_kind {
-    fk_item_fn(ident, ~[ty_param], purity), // fn foo()
-    fk_method(ident, ~[ty_param], @method), // fn foo(&self)
+    fk_item_fn(ident, Generics, purity), // fn foo()
+    fk_method(ident, Generics, @method), // fn foo(&self)
     fk_anon(ast::Sigil),                    // fn@(x, y) { ... }
     fk_fn_block,                            // |x, y| ...
-    fk_dtor(~[ty_param], ~[attribute], node_id /* self id */,
+    fk_dtor(Generics, ~[attribute], node_id /* self id */,
             def_id /* parent class id */) // class destructor
 
 }
@@ -49,13 +50,17 @@ pub fn name_of_fn(fk: fn_kind) -> ident {
     }
 }
 
-pub fn tps_of_fn(fk: fn_kind) -> ~[ty_param] {
+pub fn generics_of_fn(fk: fn_kind) -> Generics {
     match fk {
-        fk_item_fn(_, tps, _) | fk_method(_, tps, _) |
+        fk_item_fn(_, tps, _) |
+        fk_method(_, tps, _) |
         fk_dtor(tps, _, _, _) => {
-            /* FIXME (#2543) */ copy tps
+            copy tps
+        }
+        fk_anon(*) | fk_fn_block(*) => {
+            Generics {lifetimes: opt_vec::Empty,
+                      ty_params: opt_vec::Empty}
         }
-        fk_anon(*) | fk_fn_block(*) => ~[]
     }
 }
 
@@ -73,11 +78,11 @@ pub struct Visitor<E> {
     visit_expr: fn@(@expr, E, vt<E>),
     visit_expr_post: fn@(@expr, E, vt<E>),
     visit_ty: fn@(@Ty, E, vt<E>),
-    visit_ty_params: fn@(~[ty_param], E, vt<E>),
+    visit_generics: fn@(&Generics, E, vt<E>),
     visit_fn: fn@(fn_kind, fn_decl, blk, span, node_id, E, vt<E>),
     visit_ty_method: fn@(ty_method, E, vt<E>),
     visit_trait_method: fn@(trait_method, E, vt<E>),
-    visit_struct_def: fn@(@struct_def, ident, ~[ty_param], node_id, E,
+    visit_struct_def: fn@(@struct_def, ident, &Generics, node_id, E,
                           vt<E>),
     visit_struct_field: fn@(@struct_field, E, vt<E>),
     visit_struct_method: fn@(@method, E, vt<E>)
@@ -100,7 +105,7 @@ pub fn default_visitor<E>() -> visitor<E> {
         visit_expr: |a,b,c|visit_expr::<E>(a, b, c),
         visit_expr_post: |_a,_b,_c| (),
         visit_ty: |a,b,c|skip_ty::<E>(a, b, c),
-        visit_ty_params: |a,b,c|visit_ty_params::<E>(a, b, c),
+        visit_generics: |a,b,c|visit_generics::<E>(a, b, c),
         visit_fn: |a,b,c,d,e,f,g|visit_fn::<E>(a, b, c, d, e, f, g),
         visit_ty_method: |a,b,c|visit_ty_method::<E>(a, b, c),
         visit_trait_method: |a,b,c|visit_trait_method::<E>(a, b, c),
@@ -157,21 +162,21 @@ pub fn visit_item<E>(i: @item, e: E, v: vt<E>) {
         for nm.view_items.each |vi| { (v.visit_view_item)(*vi, e, v); }
         for nm.items.each |ni| { (v.visit_foreign_item)(*ni, e, v); }
       }
-      item_ty(t, tps) => {
+      item_ty(t, ref tps) => {
         (v.visit_ty)(t, e, v);
-        (v.visit_ty_params)(tps, e, v);
+        (v.visit_generics)(tps, e, v);
       }
       item_enum(ref enum_definition, ref tps) => {
-        (v.visit_ty_params)(/* FIXME (#2543) */ copy *tps, e, v);
+        (v.visit_generics)(tps, e, v);
         visit_enum_def(
             *enum_definition,
-            /* FIXME (#2543) */ copy *tps,
+            tps,
             e,
             v
         );
       }
-      item_impl(tps, traits, ty, methods) => {
-        (v.visit_ty_params)(tps, e, v);
+      item_impl(ref tps, traits, ty, methods) => {
+        (v.visit_generics)(tps, e, v);
         for traits.each |p| {
             visit_path(p.path, e, v);
         }
@@ -180,12 +185,12 @@ pub fn visit_item<E>(i: @item, e: E, v: vt<E>) {
             visit_method_helper(*m, e, v)
         }
       }
-      item_struct(struct_def, tps) => {
-        (v.visit_ty_params)(tps, e, v);
+      item_struct(struct_def, ref tps) => {
+        (v.visit_generics)(tps, e, v);
         (v.visit_struct_def)(struct_def, i.ident, tps, i.id, e, v);
       }
       item_trait(ref tps, ref traits, ref methods) => {
-        (v.visit_ty_params)(/* FIXME (#2543) */ copy *tps, e, v);
+        (v.visit_generics)(tps, e, v);
         for traits.each |p| { visit_path(p.path, e, v); }
         for (*methods).each |m| {
             (v.visit_trait_method)(*m, e, v);
@@ -196,7 +201,7 @@ pub fn visit_item<E>(i: @item, e: E, v: vt<E>) {
 }
 
 pub fn visit_enum_def<E>(enum_definition: ast::enum_def,
-                         tps: ~[ast::ty_param],
+                         tps: &Generics,
                          e: E,
                          v: vt<E>) {
     for enum_definition.variants.each |vr| {
@@ -296,9 +301,9 @@ pub fn visit_pat<E>(p: @pat, e: E, v: vt<E>) {
 
 pub fn visit_foreign_item<E>(ni: @foreign_item, e: E, v: vt<E>) {
     match ni.node {
-      foreign_item_fn(fd, _, tps) => {
-        (v.visit_ty_params)(tps, e, v);
+      foreign_item_fn(fd, _, ref generics) => {
         visit_fn_decl(fd, e, v);
+        (v.visit_generics)(generics, e, v);
       }
       foreign_item_const(t) => {
         (v.visit_ty)(t, e, v);
@@ -306,17 +311,18 @@ pub fn visit_foreign_item<E>(ni: @foreign_item, e: E, v: vt<E>) {
     }
 }
 
-pub fn visit_ty_param_bounds<E>(bounds: @~[ty_param_bound], e: E, v: vt<E>) {
-    for bounds.each |&bound| {
-        match bound {
+pub fn visit_ty_param_bounds<E>(bounds: @OptVec<TyParamBound>,
+                                e: E, v: vt<E>) {
+    for bounds.each |bound| {
+        match *bound {
             TraitTyParamBound(ty) => (v.visit_ty)(ty, e, v),
             RegionTyParamBound => ()
         }
     }
 }
 
-pub fn visit_ty_params<E>(tps: ~[ty_param], e: E, v: vt<E>) {
-    for tps.each |tp| {
+pub fn visit_generics<E>(generics: &Generics, e: E, v: vt<E>) {
+    for generics.ty_params.each |tp| {
         visit_ty_param_bounds(tp.bounds, e, v);
     }
 }
@@ -334,29 +340,33 @@ pub fn visit_fn_decl<E>(fd: fn_decl, e: E, v: vt<E>) {
 // because it is not a default impl of any method, though I doubt that really
 // clarifies anything. - Niko
 pub fn visit_method_helper<E>(m: @method, e: E, v: vt<E>) {
-    (v.visit_fn)(fk_method(/* FIXME (#2543) */ copy m.ident,
-                         /* FIXME (#2543) */ copy m.tps, m),
-               m.decl, m.body, m.span, m.id, e, v);
+    (v.visit_fn)(fk_method(m.ident, /* FIXME (#2543) */ copy m.generics, m),
+                 m.decl, m.body, m.span, m.id, e, v);
 }
 
-pub fn visit_struct_dtor_helper<E>(dtor: struct_dtor, tps: ~[ty_param],
+pub fn visit_struct_dtor_helper<E>(dtor: struct_dtor, generics: &Generics,
                                    parent_id: def_id, e: E, v: vt<E>) {
-    (v.visit_fn)(fk_dtor(/* FIXME (#2543) */ copy tps, dtor.node.attrs,
-                       dtor.node.self_id, parent_id), ast_util::dtor_dec(),
-               dtor.node.body, dtor.span, dtor.node.id, e, v)
+    (v.visit_fn)(fk_dtor(copy *generics, dtor.node.attrs,
+                         dtor.node.self_id, parent_id),
+                 ast_util::dtor_dec(),
+                 dtor.node.body,
+                 dtor.span,
+                 dtor.node.id,
+                 e, v)
 
 }
 
 pub fn visit_fn<E>(fk: fn_kind, decl: fn_decl, body: blk, _sp: span,
                    _id: node_id, e: E, v: vt<E>) {
     visit_fn_decl(decl, e, v);
-    (v.visit_ty_params)(tps_of_fn(fk), e, v);
+    let generics = generics_of_fn(fk);
+    (v.visit_generics)(&generics, e, v);
     (v.visit_block)(body, e, v);
 }
 
 pub fn visit_ty_method<E>(m: ty_method, e: E, v: vt<E>) {
     for m.decl.inputs.each |a| { (v.visit_ty)(a.ty, e, v); }
-    (v.visit_ty_params)(m.tps, e, v);
+    (v.visit_generics)(&m.generics, e, v);
     (v.visit_ty)(m.decl.output, e, v);
 }
 
@@ -367,13 +377,16 @@ pub fn visit_trait_method<E>(m: trait_method, e: E, v: vt<E>) {
     }
 }
 
-pub fn visit_struct_def<E>(sd: @struct_def, _nm: ast::ident, tps: ~[ty_param],
-                           id: node_id, e: E, v: vt<E>) {
+pub fn visit_struct_def<E>(sd: @struct_def,
+                           _nm: ast::ident,
+                           generics: &Generics,
+                           id: node_id,
+                           e: E, v: vt<E>) {
     for sd.fields.each |f| {
         (v.visit_struct_field)(*f, e, v);
     }
     do option::iter(&sd.dtor) |dtor| {
-      visit_struct_dtor_helper(*dtor, tps, ast_util::local_def(id), e, v)
+      visit_struct_dtor_helper(*dtor, generics, ast_util::local_def(id), e, v)
     };
 }
 
@@ -552,11 +565,11 @@ pub struct SimpleVisitor {
     visit_expr: fn@(@expr),
     visit_expr_post: fn@(@expr),
     visit_ty: fn@(@Ty),
-    visit_ty_params: fn@(~[ty_param]),
+    visit_generics: fn@(&Generics),
     visit_fn: fn@(fn_kind, fn_decl, blk, span, node_id),
     visit_ty_method: fn@(ty_method),
     visit_trait_method: fn@(trait_method),
-    visit_struct_def: fn@(@struct_def, ident, ~[ty_param], node_id),
+    visit_struct_def: fn@(@struct_def, ident, &Generics, node_id),
     visit_struct_field: fn@(@struct_field),
     visit_struct_method: fn@(@method)
 }
@@ -579,13 +592,13 @@ pub fn default_simple_visitor() -> @SimpleVisitor {
           visit_expr: |_e: @expr| { },
           visit_expr_post: |_e: @expr| { },
           visit_ty: simple_ignore_ty,
-          visit_ty_params: fn@(_ps: ~[ty_param]) {},
+          visit_generics: fn@(_ps: &Generics) {},
           visit_fn: fn@(_fk: fn_kind, _d: fn_decl, _b: blk, _sp: span,
                         _id: node_id) { },
           visit_ty_method: fn@(_m: ty_method) { },
           visit_trait_method: fn@(_m: trait_method) { },
           visit_struct_def: fn@(_sd: @struct_def, _nm: ident,
-                                _tps: ~[ty_param], _id: node_id) { },
+                                _generics: &Generics, _id: node_id) { },
           visit_struct_field: fn@(_f: @struct_field) { },
           visit_struct_method: fn@(_m: @method) { }
          };
@@ -654,17 +667,20 @@ pub fn mk_simple_visitor(v: simple_visitor) -> vt<()> {
         f(m);
         visit_trait_method(m, e, v);
     }
-    fn v_struct_def(f: fn@(@struct_def, ident, ~[ty_param], node_id),
-                    sd: @struct_def, nm: ident, tps: ~[ty_param], id: node_id,
+    fn v_struct_def(f: fn@(@struct_def, ident, &Generics, node_id),
+                    sd: @struct_def,
+                    nm: ident,
+                    generics: &Generics,
+                    id: node_id,
                     &&e: (), v: vt<()>) {
-        f(sd, nm, tps, id);
-        visit_struct_def(sd, nm, tps, id, e, v);
+        f(sd, nm, generics, id);
+        visit_struct_def(sd, nm, generics, id, e, v);
     }
-    fn v_ty_params(f: fn@(~[ty_param]),
-                   ps: ~[ty_param],
-                   &&e: (), v: vt<()>) {
+    fn v_generics(f: fn@(&Generics),
+                  ps: &Generics,
+                  &&e: (), v: vt<()>) {
         f(ps);
-        visit_ty_params(ps, e, v);
+        visit_generics(ps, e, v);
     }
     fn v_fn(f: fn@(fn_kind, fn_decl, blk, span, node_id),
             fk: fn_kind, decl: fn_decl, body: blk, sp: span,
@@ -699,8 +715,8 @@ pub fn mk_simple_visitor(v: simple_visitor) -> vt<()> {
         visit_expr_post: |a,b,c| v_expr_post(v.visit_expr_post,
                                              a, b, c),
         visit_ty: visit_ty,
-        visit_ty_params: |a,b,c|
-            v_ty_params(v.visit_ty_params, a, b, c),
+        visit_generics: |a,b,c|
+            v_generics(v.visit_generics, a, b, c),
         visit_fn: |a,b,c,d,e,f,g|
             v_fn(v.visit_fn, a, b, c, d, e, f, g),
         visit_ty_method: |a,b,c|