Introduce lifetime declarations into the lists of type parameters.

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

34 files changed, 1067 insertions, 719 deletions

diff --git a/src/librustc/front/test.rs b/src/librustc/front/test.rs
index f19b52661f2..22333f236ed 100644
--- a/src/librustc/front/test.rs
+++ b/src/librustc/front/test.rs
@@ -200,14 +200,14 @@ fn is_bench_fn(i: @ast::item) -> bool {
         vec::len(attr::find_attrs_by_name(i.attrs, ~"bench")) > 0u;
 
     fn has_test_signature(i: @ast::item) -> bool {
-        match /*bad*/copy i.node {
-            ast::item_fn(decl, _, tps, _) => {
+        match i.node {
+            ast::item_fn(ref decl, _, ref generics, _) => {
                 let input_cnt = vec::len(decl.inputs);
                 let no_output = match decl.output.node {
                     ast::ty_nil => true,
                     _ => false
                 };
-                let tparm_cnt = vec::len(tps);
+                let tparm_cnt = generics.ty_params.len();
                 // NB: inadequate check, but we're running
                 // well before resolve, can't get too deep.
                 input_cnt == 1u
diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index 86b07abffc2..95973aaaf90 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -49,6 +49,8 @@ use syntax::diagnostic::span_handler;
 use syntax::parse::token::special_idents;
 use syntax::print::pprust;
 use syntax::{ast_util, visit};
+use syntax::opt_vec::OptVec;
+use syntax::opt_vec;
 use syntax;
 use writer = std::ebml::writer;
 
@@ -187,10 +189,11 @@ fn encode_ty_type_param_bounds(ebml_w: writer::Encoder, ecx: @EncodeContext,
     }
 }
 
-fn encode_type_param_bounds(ebml_w: writer::Encoder, ecx: @EncodeContext,
-                            params: &[ty_param]) {
+fn encode_type_param_bounds(ebml_w: writer::Encoder,
+                            ecx: @EncodeContext,
+                            params: &OptVec<TyParam>) {
     let ty_param_bounds =
-        @params.map(|param| ecx.tcx.ty_param_bounds.get(&param.id));
+        @params.map_to_vec(|param| ecx.tcx.ty_param_bounds.get(&param.id));
     encode_ty_type_param_bounds(ebml_w, ecx, ty_param_bounds);
 }
 
@@ -265,7 +268,7 @@ fn encode_enum_variant_info(ecx: @EncodeContext, ebml_w: writer::Encoder,
                             id: node_id, variants: &[variant],
                             path: &[ast_map::path_elt],
                             index: @mut ~[entry<int>],
-                            ty_params: &[ty_param]) {
+                            generics: &ast::Generics) {
     let mut disr_val = 0;
     let mut i = 0;
     let vi = ty::enum_variants(ecx.tcx,
@@ -281,7 +284,7 @@ fn encode_enum_variant_info(ecx: @EncodeContext, ebml_w: writer::Encoder,
                     node_id_to_type(ecx.tcx, variant.node.id));
         match variant.node.kind {
             ast::tuple_variant_kind(ref args)
-                    if args.len() > 0 && ty_params.len() == 0 => {
+                    if args.len() > 0 && generics.ty_params.len() == 0 => {
                 encode_symbol(ecx, ebml_w, variant.node.id);
             }
             ast::tuple_variant_kind(_) | ast::struct_variant_kind(_) |
@@ -292,7 +295,7 @@ fn encode_enum_variant_info(ecx: @EncodeContext, ebml_w: writer::Encoder,
             encode_disr_val(ecx, ebml_w, vi[i].disr_val);
             disr_val = vi[i].disr_val;
         }
-        encode_type_param_bounds(ebml_w, ecx, ty_params);
+        encode_type_param_bounds(ebml_w, ecx, &generics.ty_params);
         encode_path(ecx, ebml_w, path,
                     ast_map::path_name(variant.node.name));
         ebml_w.end_tag();
@@ -465,14 +468,18 @@ fn encode_info_for_struct(ecx: @EncodeContext, ebml_w: writer::Encoder,
 }
 
 // This is for encoding info for ctors and dtors
-fn encode_info_for_ctor(ecx: @EncodeContext, ebml_w: writer::Encoder,
-                        id: node_id, ident: ident, path: &[ast_map::path_elt],
-                        item: Option<inlined_item>, tps: &[ty_param]) {
+fn encode_info_for_ctor(ecx: @EncodeContext,
+                        ebml_w: writer::Encoder,
+                        id: node_id,
+                        ident: ident,
+                        path: &[ast_map::path_elt],
+                        item: Option<inlined_item>,
+                        generics: &ast::Generics) {
         ebml_w.start_tag(tag_items_data_item);
         encode_name(ecx, ebml_w, ident);
         encode_def_id(ebml_w, local_def(id));
         encode_family(ebml_w, purity_fn_family(ast::impure_fn));
-        encode_type_param_bounds(ebml_w, ecx, tps);
+        encode_type_param_bounds(ebml_w, ecx, &generics.ty_params);
         let its_ty = node_id_to_type(ecx.tcx, id);
         debug!("fn name = %s ty = %s its node id = %d",
                *ecx.tcx.sess.str_of(ident),
@@ -518,9 +525,12 @@ fn encode_info_for_method(ecx: @EncodeContext,
                           should_inline: bool,
                           parent_id: node_id,
                           m: @method,
-                          +all_tps: ~[ty_param]) {
-    debug!("encode_info_for_method: %d %s %u", m.id,
-           *ecx.tcx.sess.str_of(m.ident), all_tps.len());
+                          owner_generics: &ast::Generics,
+                          method_generics: &ast::Generics) {
+    debug!("encode_info_for_method: %d %s %u %u", m.id,
+           *ecx.tcx.sess.str_of(m.ident),
+           owner_generics.ty_params.len(),
+           method_generics.ty_params.len());
     ebml_w.start_tag(tag_items_data_item);
     encode_def_id(ebml_w, local_def(m.id));
     match m.self_ty.node {
@@ -529,8 +539,13 @@ fn encode_info_for_method(ecx: @EncodeContext,
         }
         _ => encode_family(ebml_w, purity_fn_family(m.purity))
     }
-    let len = all_tps.len();
-    encode_type_param_bounds(ebml_w, ecx, all_tps);
+
+    let mut combined_ty_params = opt_vec::Empty;
+    combined_ty_params.push_all(&owner_generics.ty_params);
+    combined_ty_params.push_all(&method_generics.ty_params);
+    let len = combined_ty_params.len();
+    encode_type_param_bounds(ebml_w, ecx, &combined_ty_params);
+
     encode_type(ecx, ebml_w, node_id_to_type(ecx.tcx, m.id));
     encode_name(ecx, ebml_w, m.ident);
     encode_path(ecx, ebml_w, impl_path, ast_map::path_name(m.ident));
@@ -604,13 +619,13 @@ fn encode_info_for_item(ecx: @EncodeContext, ebml_w: writer::Encoder,
         encode_path(ecx, ebml_w, path, ast_map::path_name(item.ident));
         ebml_w.end_tag();
       }
-      item_fn(_, purity, tps, _) => {
+      item_fn(_, purity, ref generics, _) => {
         add_to_index();
         ebml_w.start_tag(tag_items_data_item);
         encode_def_id(ebml_w, local_def(item.id));
         encode_family(ebml_w, purity_fn_family(purity));
-        let tps_len = tps.len();
-        encode_type_param_bounds(ebml_w, ecx, tps);
+        let tps_len = generics.ty_params.len();
+        encode_type_param_bounds(ebml_w, ecx, &generics.ty_params);
         encode_type(ecx, ebml_w, node_id_to_type(tcx, item.id));
         encode_path(ecx, ebml_w, path, ast_map::path_name(item.ident));
         encode_attributes(ebml_w, item.attrs);
@@ -634,24 +649,24 @@ fn encode_info_for_item(ecx: @EncodeContext, ebml_w: writer::Encoder,
         encode_path(ecx, ebml_w, path, ast_map::path_name(item.ident));
         ebml_w.end_tag();
       }
-      item_ty(_, tps) => {
+      item_ty(_, ref generics) => {
         add_to_index();
         ebml_w.start_tag(tag_items_data_item);
         encode_def_id(ebml_w, local_def(item.id));
         encode_family(ebml_w, 'y');
-        encode_type_param_bounds(ebml_w, ecx, tps);
+        encode_type_param_bounds(ebml_w, ecx, &generics.ty_params);
         encode_type(ecx, ebml_w, node_id_to_type(tcx, item.id));
         encode_name(ecx, ebml_w, item.ident);
         encode_path(ecx, ebml_w, path, ast_map::path_name(item.ident));
         encode_region_param(ecx, ebml_w, item);
         ebml_w.end_tag();
       }
-      item_enum(ref enum_definition, ref tps) => {
+      item_enum(ref enum_definition, ref generics) => {
         add_to_index();
         do ebml_w.wr_tag(tag_items_data_item) {
             encode_def_id(ebml_w, local_def(item.id));
             encode_family(ebml_w, 't');
-            encode_type_param_bounds(ebml_w, ecx, *tps);
+            encode_type_param_bounds(ebml_w, ecx, &generics.ty_params);
             encode_type(ecx, ebml_w, node_id_to_type(tcx, item.id));
             encode_name(ecx, ebml_w, item.ident);
             for (*enum_definition).variants.each |v| {
@@ -667,9 +682,9 @@ fn encode_info_for_item(ecx: @EncodeContext, ebml_w: writer::Encoder,
                                  (*enum_definition).variants,
                                  path,
                                  index,
-                                 *tps);
+                                 generics);
       }
-      item_struct(struct_def, tps) => {
+      item_struct(struct_def, ref generics) => {
         /* First, encode the fields
            These come first because we need to write them to make
            the index, and the index needs to be in the item for the
@@ -686,24 +701,25 @@ fn encode_info_for_item(ecx: @EncodeContext, ebml_w: writer::Encoder,
                                    *ecx.tcx.sess.str_of(item.ident) +
                                    ~"_dtor"),
                                path,
-                               if tps.len() > 0u {
+                               if generics.ty_params.len() > 0u {
                                    Some(ii_dtor(copy *dtor,
                                                 item.ident,
-                                                copy tps,
+                                                copy *generics,
                                                 local_def(item.id))) }
                                else {
                                    None
                                },
-                               tps);
+                               generics);
         }
 
         /* Index the class*/
         add_to_index();
+
         /* Now, make an item for the class itself */
         ebml_w.start_tag(tag_items_data_item);
         encode_def_id(ebml_w, local_def(item.id));
         encode_family(ebml_w, 'S');
-        encode_type_param_bounds(ebml_w, ecx, tps);
+        encode_type_param_bounds(ebml_w, ecx, &generics.ty_params);
         encode_type(ecx, ebml_w, node_id_to_type(tcx, item.id));
 
         // If this is a tuple- or enum-like struct, encode the type of the
@@ -759,13 +775,13 @@ fn encode_info_for_item(ecx: @EncodeContext, ebml_w: writer::Encoder,
         encode_index(ebml_w, bkts, write_int);
         ebml_w.end_tag();
       }
-      item_impl(tps, opt_trait, ty, methods) => {
+      item_impl(ref generics, opt_trait, ty, ref methods) => {
         add_to_index();
         ebml_w.start_tag(tag_items_data_item);
         encode_def_id(ebml_w, local_def(item.id));
         encode_family(ebml_w, 'i');
         encode_region_param(ecx, ebml_w, item);
-        encode_type_param_bounds(ebml_w, ecx, tps);
+        encode_type_param_bounds(ebml_w, ecx, &generics.ty_params);
         encode_type(ecx, ebml_w, node_id_to_type(tcx, item.id));
         encode_name(ecx, ebml_w, item.ident);
         encode_attributes(ebml_w, item.attrs);
@@ -797,10 +813,10 @@ fn encode_info_for_item(ecx: @EncodeContext, ebml_w: writer::Encoder,
             encode_info_for_method(ecx, ebml_w, impl_path,
                                    should_inline(m.attrs),
                                    item.id, *m,
-                                   vec::append(/*bad*/copy tps, m.tps));
+                                   generics, &m.generics);
         }
       }
-      item_trait(ref tps, ref traits, ref ms) => {
+      item_trait(ref generics, ref traits, ref ms) => {
         let provided_methods = dvec::DVec();
 
         add_to_index();
@@ -808,7 +824,7 @@ fn encode_info_for_item(ecx: @EncodeContext, ebml_w: writer::Encoder,
         encode_def_id(ebml_w, local_def(item.id));
         encode_family(ebml_w, 'I');
         encode_region_param(ecx, ebml_w, item);
-        encode_type_param_bounds(ebml_w, ecx, *tps);
+        encode_type_param_bounds(ebml_w, ecx, &generics.ty_params);
         encode_type(ecx, ebml_w, node_id_to_type(tcx, item.id));
         encode_name(ecx, ebml_w, item.ident);
         encode_attributes(ebml_w, item.attrs);
@@ -820,7 +836,7 @@ fn encode_info_for_item(ecx: @EncodeContext, ebml_w: writer::Encoder,
                 encode_def_id(ebml_w, local_def((*ty_m).id));
                 encode_name(ecx, ebml_w, mty.ident);
                 encode_type_param_bounds(ebml_w, ecx,
-                                         (*ty_m).tps);
+                                         &ty_m.generics.ty_params);
                 encode_type(ecx, ebml_w,
                             ty::mk_bare_fn(tcx, copy mty.fty));
                 encode_family(ebml_w, purity_fn_family(mty.fty.purity));
@@ -834,7 +850,8 @@ fn encode_info_for_item(ecx: @EncodeContext, ebml_w: writer::Encoder,
                 ebml_w.start_tag(tag_item_trait_method);
                 encode_def_id(ebml_w, local_def(m.id));
                 encode_name(ecx, ebml_w, mty.ident);
-                encode_type_param_bounds(ebml_w, ecx, m.tps);
+                encode_type_param_bounds(ebml_w, ecx,
+                                         &m.generics.ty_params);
                 encode_type(ecx, ebml_w,
                             ty::mk_bare_fn(tcx, copy mty.fty));
                 encode_family(ebml_w, purity_fn_family(mty.fty.purity));
@@ -880,8 +897,14 @@ fn encode_info_for_item(ecx: @EncodeContext, ebml_w: writer::Encoder,
         // Finally, output all the provided methods as items.
         for provided_methods.each |m| {
             index.push(entry { val: m.id, pos: ebml_w.writer.tell() });
+
+            // We do not concatenate the generics of the owning impl and that
+            // of provided methods.  I am not sure why this is. -ndm
+            let owner_generics = ast_util::empty_generics();
+
             encode_info_for_method(ecx, ebml_w, /*bad*/copy path,
-                                   true, item.id, *m, /*bad*/copy m.tps);
+                                   true, item.id, *m,
+                                   &owner_generics, &m.generics);
         }
       }
       item_mac(*) => fail!(~"item macros unimplemented")
@@ -898,11 +921,11 @@ fn encode_info_for_foreign_item(ecx: @EncodeContext,
     index.push(entry { val: nitem.id, pos: ebml_w.writer.tell() });
 
     ebml_w.start_tag(tag_items_data_item);
-    match /*bad*/copy nitem.node {
-      foreign_item_fn(_, purity, tps) => {
+    match nitem.node {
+      foreign_item_fn(_, purity, ref generics) => {
         encode_def_id(ebml_w, local_def(nitem.id));
         encode_family(ebml_w, purity_fn_family(purity));
-        encode_type_param_bounds(ebml_w, ecx, tps);
+        encode_type_param_bounds(ebml_w, ecx, &generics.ty_params);
         encode_type(ecx, ebml_w, node_id_to_type(ecx.tcx, nitem.id));
         if abi == foreign_abi_rust_intrinsic {
             (ecx.encode_inlined_item)(ecx, ebml_w, path, ii_foreign(nitem));
diff --git a/src/librustc/middle/astencode.rs b/src/librustc/middle/astencode.rs
index 02cd5afc920..58433cec272 100644
--- a/src/librustc/middle/astencode.rs
+++ b/src/librustc/middle/astencode.rs
@@ -371,10 +371,10 @@ fn renumber_ast(xcx: @ExtendedDecodeContext, ii: ast::inlined_item)
       ast::ii_foreign(i) => {
         ast::ii_foreign(fld.fold_foreign_item(i))
       }
-      ast::ii_dtor(ref dtor, nm, ref tps, parent_id) => {
+      ast::ii_dtor(ref dtor, nm, ref generics, parent_id) => {
         let dtor_body = fld.fold_block((*dtor).node.body);
-        let dtor_attrs = fld.fold_attributes(/*bad*/copy (*dtor).node.attrs);
-        let new_params = fold::fold_ty_params(/*bad*/copy *tps, fld);
+        let dtor_attrs = fld.fold_attributes(copy dtor.node.attrs);
+        let new_generics = fold::fold_generics(generics, fld);
         let dtor_id = fld.new_id((*dtor).node.id);
         let new_parent = xcx.tr_def_id(parent_id);
         let new_self = fld.new_id((*dtor).node.self_id);
@@ -386,7 +386,7 @@ fn renumber_ast(xcx: @ExtendedDecodeContext, ii: ast::inlined_item)
                                           body: dtor_body },
                 .. (/*bad*/copy *dtor)
             },
-            nm, new_params, new_parent)
+            nm, new_generics, new_parent)
       }
      }
 }
diff --git a/src/librustc/middle/lint.rs b/src/librustc/middle/lint.rs
index f4c3a1e8d12..eb418d0cd5a 100644
--- a/src/librustc/middle/lint.rs
+++ b/src/librustc/middle/lint.rs
@@ -753,7 +753,7 @@ fn check_item_structural_records(cx: ty::ctxt, it: @ast::item) {
 fn check_item_ctypes(cx: ty::ctxt, it: @ast::item) {
 
     fn check_foreign_fn(cx: ty::ctxt, fn_id: ast::node_id,
-                       decl: ast::fn_decl) {
+                        decl: ast::fn_decl) {
         let tys = vec::map(decl.inputs, |a| a.ty );
         for vec::each(vec::append_one(tys, decl.output)) |ty| {
             match ty.node {
@@ -786,9 +786,9 @@ fn check_item_ctypes(cx: ty::ctxt, it: @ast::item) {
       if attr::foreign_abi(it.attrs) !=
             either::Right(ast::foreign_abi_rust_intrinsic) => {
         for nmod.items.each |ni| {
-            match /*bad*/copy ni.node {
-              ast::foreign_item_fn(decl, _, _) => {
-                check_foreign_fn(cx, it.id, decl);
+            match ni.node {
+              ast::foreign_item_fn(ref decl, _, _) => {
+                check_foreign_fn(cx, it.id, *decl);
               }
               // FIXME #4622: Not implemented.
               ast::foreign_item_const(*) => {}
diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index 5b2d3c9bb96..19accd25c12 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -621,7 +621,8 @@ pub fn determine_rp_in_fn(fk: visit::fn_kind,
             }
         }
         (visitor.visit_ty)(decl.output, cx, visitor);
-        (visitor.visit_ty_params)(visit::tps_of_fn(fk), cx, visitor);
+        let generics = visit::generics_of_fn(fk);
+        (visitor.visit_generics)(&generics, cx, visitor);
         (visitor.visit_block)(body, cx, visitor);
     }
 }
diff --git a/src/librustc/middle/resolve.rs b/src/librustc/middle/resolve.rs
index e75a73650b4..2b0263a4736 100644
--- a/src/librustc/middle/resolve.rs
+++ b/src/librustc/middle/resolve.rs
@@ -42,6 +42,7 @@ use syntax::ast::{enum_variant_kind, expr, expr_again, expr_assign_op};
 use syntax::ast::{expr_fn_block, expr_index, expr_loop};
 use syntax::ast::{expr_path, expr_struct, expr_unary, fn_decl};
 use syntax::ast::{foreign_item, foreign_item_const, foreign_item_fn, ge};
+use syntax::ast::{Generics};
 use syntax::ast::{gt, ident, impure_fn, inherited, item, item_struct};
 use syntax::ast::{item_const, item_enum, item_fn, item_foreign_mod};
 use syntax::ast::{item_impl, item_mac, item_mod, item_trait, item_ty, le};
@@ -53,9 +54,9 @@ use syntax::ast::{public, required, rem, self_ty_, shl, shr, stmt_decl};
 use syntax::ast::{struct_dtor, struct_field, struct_variant_kind, sty_by_ref};
 use syntax::ast::{sty_static, subtract, trait_ref, tuple_variant_kind, Ty};
 use syntax::ast::{ty_bool, ty_char, ty_f, ty_f32, ty_f64, ty_float, ty_i};
-use syntax::ast::{ty_i16, ty_i32, ty_i64, ty_i8, ty_int, ty_param, ty_path};
+use syntax::ast::{ty_i16, ty_i32, ty_i64, ty_i8, ty_int, TyParam, ty_path};
 use syntax::ast::{ty_str, ty_u, ty_u16, ty_u32, ty_u64, ty_u8, ty_uint};
-use syntax::ast::{type_value_ns, ty_param_bound, unnamed_field};
+use syntax::ast::{type_value_ns, unnamed_field};
 use syntax::ast::{variant, view_item, view_item_extern_mod};
 use syntax::ast::{view_item_use, view_path_glob, view_path_list};
 use syntax::ast::{view_path_simple, visibility, anonymous, named, not};
@@ -73,6 +74,8 @@ use syntax::visit::{default_visitor, fk_method, mk_vt, Visitor, visit_block};
 use syntax::visit::{visit_crate, visit_expr, visit_expr_opt, visit_fn};
 use syntax::visit::{visit_foreign_item, visit_item, visit_method_helper};
 use syntax::visit::{visit_mod, visit_ty, vt};
+use syntax::opt_vec;
+use syntax::opt_vec::OptVec;
 
 use managed::ptr_eq;
 use dvec::DVec;
@@ -216,9 +219,9 @@ pub impl<T> ResolveResult<T> {
 }
 
 pub enum TypeParameters/& {
-    NoTypeParameters,               //< No type parameters.
-    HasTypeParameters(&~[ty_param], //< Type parameters.
-                      node_id,      //< ID of the enclosing item
+    NoTypeParameters,              //< No type parameters.
+    HasTypeParameters(&Generics,   //< Type parameters.
+                      node_id,     //< ID of the enclosing item
 
                       // The index to start numbering the type parameters at.
                       // This is zero if this is the outermost set of type
@@ -231,7 +234,6 @@ pub enum TypeParameters/& {
                       //
                       // The index at the method site will be 1, because the
                       // outer T had index 0.
-
                       uint,
 
                       // The kind of the rib used for type parameters.
@@ -1500,14 +1502,15 @@ pub impl Resolver {
             self.add_child(name, parent, ForbidDuplicateValues,
                            foreign_item.span);
 
-        match /*bad*/copy foreign_item.node {
-            foreign_item_fn(_, _, type_parameters) => {
+        match foreign_item.node {
+            foreign_item_fn(_, _, ref generics) => {
                 let def = def_fn(local_def(foreign_item.id), unsafe_fn);
                 name_bindings.define_value(Public, def, foreign_item.span);
 
-                do self.with_type_parameter_rib
-                        (HasTypeParameters(&type_parameters, foreign_item.id,
-                                           0, NormalRibKind)) {
+                do self.with_type_parameter_rib(
+                    HasTypeParameters(
+                        generics, foreign_item.id, 0, NormalRibKind))
+                {
                     visit_foreign_item(foreign_item, new_parent, visitor);
                 }
             }
@@ -3582,8 +3585,7 @@ pub impl Resolver {
 
             // enum item: resolve all the variants' discrs,
             // then resolve the ty params
-            item_enum(ref enum_def, ref type_parameters) => {
-
+            item_enum(ref enum_def, ref generics) => {
                 for (*enum_def).variants.each() |variant| {
                     do variant.node.disr_expr.iter() |dis_expr| {
                         // resolve the discriminator expr
@@ -3599,14 +3601,14 @@ pub impl Resolver {
                 // error if there is one? -- tjc
                 do self.with_type_parameter_rib(
                     HasTypeParameters(
-                        type_parameters, item.id, 0, NormalRibKind)) {
+                        generics, item.id, 0, NormalRibKind)) {
                     visit_item(item, (), visitor);
                 }
             }
 
-            item_ty(_, type_parameters) => {
+            item_ty(_, ref generics) => {
                 do self.with_type_parameter_rib
-                        (HasTypeParameters(&type_parameters, item.id, 0,
+                        (HasTypeParameters(generics, item.id, 0,
                                            NormalRibKind))
                         || {
 
@@ -3614,20 +3616,20 @@ pub impl Resolver {
                 }
             }
 
-            item_impl(type_parameters,
+            item_impl(ref generics,
                       implemented_traits,
                       self_type,
-                      methods) => {
+                      ref methods) => {
                 self.resolve_implementation(item.id,
                                             item.span,
-                                            type_parameters,
+                                            generics,
                                             implemented_traits,
                                             self_type,
-                                            methods,
+                                            *methods,
                                             visitor);
             }
 
-            item_trait(ref type_parameters, ref traits, ref methods) => {
+            item_trait(ref generics, ref traits, ref methods) => {
                 // Create a new rib for the self type.
                 let self_type_rib = @Rib(NormalRibKind);
                 (*self.type_ribs).push(self_type_rib);
@@ -3636,10 +3638,10 @@ pub impl Resolver {
 
                 // Create a new rib for the trait-wide type parameters.
                 do self.with_type_parameter_rib
-                        (HasTypeParameters(type_parameters, item.id, 0,
+                        (HasTypeParameters(generics, item.id, 0,
                                            NormalRibKind)) {
 
-                    self.resolve_type_parameters(/*bad*/copy *type_parameters,
+                    self.resolve_type_parameters(&generics.ty_params,
                                                  visitor);
 
                     // Resolve derived traits.
@@ -3672,18 +3674,18 @@ pub impl Resolver {
                         match *method {
                           required(ref ty_m) => {
                             do self.with_type_parameter_rib
-                                (HasTypeParameters(&(*ty_m).tps,
+                                (HasTypeParameters(&ty_m.generics,
                                                    item.id,
-                                                   type_parameters.len(),
+                                                   generics.ty_params.len(),
                                         MethodRibKind(item.id, Required))) {
 
                                 // Resolve the method-specific type
                                 // parameters.
                                 self.resolve_type_parameters(
-                                    /*bad*/copy (*ty_m).tps,
+                                    &ty_m.generics.ty_params,
                                     visitor);
 
-                                for (*ty_m).decl.inputs.each |argument| {
+                                for ty_m.decl.inputs.each |argument| {
                                     self.resolve_type(argument.ty, visitor);
                                 }
 
@@ -3694,7 +3696,7 @@ pub impl Resolver {
                               self.resolve_method(MethodRibKind(item.id,
                                                      Provided(m.id)),
                                                   m,
-                                                  type_parameters.len(),
+                                                  generics.ty_params.len(),
                                                   visitor)
                           }
                         }
@@ -3704,12 +3706,12 @@ pub impl Resolver {
                 (*self.type_ribs).pop();
             }
 
-            item_struct(struct_def, ty_params) => {
+            item_struct(struct_def, ref generics) => {
                 self.resolve_struct(item.id,
-                                   @copy ty_params,
-                                   /*bad*/copy struct_def.fields,
-                                   struct_def.dtor,
-                                   visitor);
+                                    generics,
+                                    struct_def.fields,
+                                    struct_def.dtor,
+                                    visitor);
             }
 
             item_mod(module_) => {
@@ -3722,18 +3724,14 @@ pub impl Resolver {
             item_foreign_mod(foreign_module) => {
                 do self.with_scope(Some(item.ident)) {
                     for foreign_module.items.each |foreign_item| {
-                        match /*bad*/copy foreign_item.node {
-                            foreign_item_fn(_, _, type_parameters) => {
-                                do self.with_type_parameter_rib
-                                    (HasTypeParameters(&type_parameters,
-                                                       foreign_item.id,
-                                                       0,
-                                                       OpaqueFunctionRibKind))
-                                        || {
-
-                                    visit_foreign_item(*foreign_item, (),
-                                                       visitor);
-                                }
+                        match foreign_item.node {
+                            foreign_item_fn(_, _, ref generics) => {
+                                self.with_type_parameter_rib(
+                                    HasTypeParameters(
+                                        generics, foreign_item.id, 0,
+                                        NormalRibKind),
+                                    || visit_foreign_item(*foreign_item, (),
+                                                          visitor));
                             }
                             foreign_item_const(_) => {
                                 visit_foreign_item(*foreign_item, (),
@@ -3744,7 +3742,7 @@ pub impl Resolver {
                 }
             }
 
-            item_fn(ref fn_decl, _, ref ty_params, ref block) => {
+            item_fn(ref fn_decl, _, ref generics, ref block) => {
                 // If this is the main function, we must record it in the
                 // session.
                 // FIXME #4404 android JNI hacks
@@ -3771,7 +3769,7 @@ pub impl Resolver {
                 self.resolve_function(OpaqueFunctionRibKind,
                                       Some(@/*bad*/copy *fn_decl),
                                       HasTypeParameters
-                                        (ty_params,
+                                        (generics,
                                          item.id,
                                          0,
                                          OpaqueFunctionRibKind),
@@ -3798,13 +3796,13 @@ pub impl Resolver {
                                type_parameters: TypeParameters,
                                f: fn()) {
         match type_parameters {
-            HasTypeParameters(type_parameters, node_id, initial_index,
+            HasTypeParameters(generics, node_id, initial_index,
                               rib_kind) => {
 
                 let function_type_rib = @Rib(rib_kind);
-                (*self.type_ribs).push(function_type_rib);
+                self.type_ribs.push(function_type_rib);
 
-                for (*type_parameters).eachi |index, type_parameter| {
+                for generics.ty_params.eachi |index, type_parameter| {
                     let name = type_parameter.ident;
                     debug!("with_type_parameter_rib: %d %d", node_id,
                            type_parameter.id);
@@ -3815,7 +3813,7 @@ pub impl Resolver {
                     // the item that bound it
                     self.record_def(type_parameter.id,
                                     def_typaram_binder(node_id));
-                    (*function_type_rib).bindings.insert(name, def_like);
+                    function_type_rib.bindings.insert(name, def_like);
                 }
             }
 
@@ -3828,7 +3826,7 @@ pub impl Resolver {
 
         match type_parameters {
             HasTypeParameters(*) => {
-                (*self.type_ribs).pop();
+                self.type_ribs.pop();
             }
 
             NoTypeParameters => {
@@ -3871,8 +3869,8 @@ pub impl Resolver {
                 NoTypeParameters => {
                     // Continue.
                 }
-                HasTypeParameters(type_parameters, _, _, _) => {
-                    self.resolve_type_parameters(/*bad*/copy *type_parameters,
+                HasTypeParameters(ref generics, _, _, _) => {
+                    self.resolve_type_parameters(&generics.ty_params,
                                                  visitor);
                 }
             }
@@ -3927,7 +3925,7 @@ pub impl Resolver {
     }
 
     fn resolve_type_parameters(@mut self,
-                               type_parameters: ~[ty_param],
+                               type_parameters: &OptVec<TyParam>,
                                visitor: ResolveVisitor) {
         for type_parameters.each |type_parameter| {
             for type_parameter.bounds.each |&bound| {
@@ -3941,19 +3939,17 @@ pub impl Resolver {
 
     fn resolve_struct(@mut self,
                       id: node_id,
-                      type_parameters: @~[ty_param],
-                      fields: ~[@struct_field],
+                      generics: &Generics,
+                      fields: &[@struct_field],
                       optional_destructor: Option<struct_dtor>,
                       visitor: ResolveVisitor) {
         // If applicable, create a rib for the type parameters.
-        let borrowed_type_parameters: &~[ty_param] = &*type_parameters;
         do self.with_type_parameter_rib(HasTypeParameters
-                                        (borrowed_type_parameters, id, 0,
+                                        (generics, id, 0,
                                          OpaqueFunctionRibKind)) {
 
             // Resolve the type parameters.
-            self.resolve_type_parameters(/*bad*/copy *type_parameters,
-                                         visitor);
+            self.resolve_type_parameters(&generics.ty_params, visitor);
 
             // Resolve fields.
             for fields.each |field| {
@@ -3986,9 +3982,9 @@ pub impl Resolver {
                       method: @method,
                       outer_type_parameter_count: uint,
                       visitor: ResolveVisitor) {
-        let borrowed_method_type_parameters = &method.tps;
+        let method_generics = &method.generics;
         let type_parameters =
-            HasTypeParameters(borrowed_method_type_parameters,
+            HasTypeParameters(method_generics,
                               method.id,
                               outer_type_parameter_count,
                               rib_kind);
@@ -4010,19 +4006,18 @@ pub impl Resolver {
     fn resolve_implementation(@mut self,
                               id: node_id,
                               span: span,
-                              type_parameters: ~[ty_param],
+                              generics: &Generics,
                               opt_trait_reference: Option<@trait_ref>,
                               self_type: @Ty,
                               methods: ~[@method],
                               visitor: ResolveVisitor) {
         // If applicable, create a rib for the type parameters.
-        let outer_type_parameter_count = type_parameters.len();
-        let borrowed_type_parameters: &~[ty_param] = &type_parameters;
+        let outer_type_parameter_count = generics.ty_params.len();
         do self.with_type_parameter_rib(HasTypeParameters
-                                        (borrowed_type_parameters, id, 0,
+                                        (generics, id, 0,
                                          NormalRibKind)) {
             // Resolve the type parameters.
-            self.resolve_type_parameters(/*bad*/copy type_parameters,
+            self.resolve_type_parameters(&generics.ty_params,
                                          visitor);
 
             // Resolve the trait reference, if necessary.
diff --git a/src/librustc/middle/trans/base.rs b/src/librustc/middle/trans/base.rs
index 53555dc9ff8..142c3278556 100644
--- a/src/librustc/middle/trans/base.rs
+++ b/src/librustc/middle/trans/base.rs
@@ -2103,9 +2103,9 @@ pub fn trans_item(ccx: @CrateContext, item: ast::item) {
             }
         }
       }
-      ast::item_impl(tps, _, _, ms) => {
-        meth::trans_impl(ccx, /*bad*/copy *path, item.ident, ms, tps, None,
-                         item.id);
+      ast::item_impl(ref generics, _, _, ref ms) => {
+        meth::trans_impl(ccx, /*bad*/copy *path, item.ident, *ms,
+                         generics, None, item.id);
       }
       ast::item_mod(m) => {
         trans_mod(ccx, m);
diff --git a/src/librustc/middle/trans/inline.rs b/src/librustc/middle/trans/inline.rs
index 43369aa9d75..b352b078a47 100644
--- a/src/librustc/middle/trans/inline.rs
+++ b/src/librustc/middle/trans/inline.rs
@@ -91,7 +91,9 @@ pub fn maybe_instantiate_inline(ccx: @CrateContext, fn_id: ast::def_id,
                 region_param: _,
                 ty: _
             } = ty::lookup_item_type(ccx.tcx, impl_did);
-            if translate && (*impl_bnds).len() + mth.tps.len() == 0u {
+            if translate &&
+                impl_bnds.len() + mth.generics.ty_params.len() == 0u
+            {
                 let llfn = get_item_val(ccx, mth.id);
                 let path = vec::append(
                     ty::item_path(ccx.tcx, impl_did),
diff --git a/src/librustc/middle/trans/meth.rs b/src/librustc/middle/trans/meth.rs
index 07b6556df6a..777711889c7 100644
--- a/src/librustc/middle/trans/meth.rs
+++ b/src/librustc/middle/trans/meth.rs
@@ -46,13 +46,13 @@ be generated once they are invoked with specific type parameters,
 see `trans::base::lval_static_fn()` or `trans::base::monomorphic_fn()`.
 */
 pub fn trans_impl(ccx: @CrateContext, +path: path, name: ast::ident,
-                  methods: ~[@ast::method], tps: ~[ast::ty_param],
+                  methods: ~[@ast::method], generics: &ast::Generics,
                   self_ty: Option<ty::t>, id: ast::node_id) {
     let _icx = ccx.insn_ctxt("impl::trans_impl");
-    if tps.len() > 0u { return; }
+    if !generics.ty_params.is_empty() { return; }
     let sub_path = vec::append_one(path, path_name(name));
     for vec::each(methods) |method| {
-        if method.tps.len() == 0u {
+        if method.generics.ty_params.len() == 0u {
             let llfn = get_item_val(ccx, method.id);
             let path = vec::append_one(/*bad*/copy sub_path,
                                        path_name(method.ident));
@@ -410,7 +410,7 @@ pub fn method_ty_param_count(ccx: @CrateContext, m_id: ast::def_id,
     debug!("method_ty_param_count: m_id: %?, i_id: %?", m_id, i_id);
     if m_id.crate == ast::local_crate {
         match ccx.tcx.items.find(&m_id.node) {
-            Some(ast_map::node_method(m, _, _)) => m.tps.len(),
+            Some(ast_map::node_method(m, _, _)) => m.generics.ty_params.len(),
             None => {
                 match ccx.tcx.provided_method_sources.find(&m_id) {
                     Some(source) => {
@@ -420,9 +420,9 @@ pub fn method_ty_param_count(ccx: @CrateContext, m_id: ast::def_id,
                     None => fail!()
                 }
             }
-            Some(ast_map::node_trait_method(@ast::provided(@ref m), _, _))
-                => {
-                m.tps.len()
+            Some(ast_map::node_trait_method(@ast::provided(@ref m),
+                                            _, _)) => {
+                m.generics.ty_params.len()
             }
             copy e => fail!(fmt!("method_ty_param_count %?", e))
         }
diff --git a/src/librustc/middle/trans/reachable.rs b/src/librustc/middle/trans/reachable.rs
index d56d28c982d..a235322532b 100644
--- a/src/librustc/middle/trans/reachable.rs
+++ b/src/librustc/middle/trans/reachable.rs
@@ -97,38 +97,41 @@ fn traverse_public_mod(cx: ctx, mod_id: node_id, m: _mod) {
 fn traverse_public_item(cx: ctx, item: @item) {
     if cx.rmap.contains_key(&item.id) { return; }
     cx.rmap.insert(item.id, ());
-    match /*bad*/copy item.node {
-      item_mod(m) => traverse_public_mod(cx, item.id, m),
-      item_foreign_mod(nm) => {
+    match item.node {
+      item_mod(ref m) => traverse_public_mod(cx, item.id, *m),
+      item_foreign_mod(ref nm) => {
           if !traverse_exports(cx, item.id) {
               for vec::each(nm.items) |item| {
                   cx.rmap.insert(item.id, ());
               }
           }
       }
-      item_fn(_, _, ref tps, ref blk) => {
-        if tps.len() > 0u ||
+      item_fn(_, _, ref generics, ref blk) => {
+        if generics.ty_params.len() > 0u ||
            attr::find_inline_attr(item.attrs) != attr::ia_none {
             traverse_inline_body(cx, (*blk));
         }
       }
-      item_impl(tps, _, _, ms) => {
-        for vec::each(ms) |m| {
-            if tps.len() > 0u || m.tps.len() > 0u ||
-               attr::find_inline_attr(m.attrs) != attr::ia_none {
+      item_impl(ref generics, _, _, ref ms) => {
+        for ms.each |m| {
+            if generics.ty_params.len() > 0u ||
+                m.generics.ty_params.len() > 0u ||
+                attr::find_inline_attr(m.attrs) != attr::ia_none
+            {
                 cx.rmap.insert(m.id, ());
                 traverse_inline_body(cx, m.body);
             }
         }
       }
-      item_struct(struct_def, tps) => {
+      item_struct(ref struct_def, ref generics) => {
         for struct_def.ctor_id.each |&ctor_id| {
             cx.rmap.insert(ctor_id, ());
         }
         do option::iter(&struct_def.dtor) |dtor| {
             cx.rmap.insert(dtor.node.id, ());
-            if tps.len() > 0u || attr::find_inline_attr(dtor.node.attrs)
-                     != attr::ia_none {
+            if generics.ty_params.len() > 0u ||
+                attr::find_inline_attr(dtor.node.attrs) != attr::ia_none
+            {
                 traverse_inline_body(cx, dtor.node.body);
             }
         }
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 182ab11b917..792d1fb4dfb 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -4143,10 +4143,11 @@ pub fn is_binopable(_cx: ctxt, ty: t, op: ast::binop) -> bool {
     return tbl[tycat(ty)][opcat(op)];
 }
 
-pub fn ty_params_to_tys(tcx: ty::ctxt, tps: ~[ast::ty_param]) -> ~[t] {
-    vec::from_fn(tps.len(), |i| {
-                ty::mk_param(tcx, i, ast_util::local_def(tps[i].id))
-        })
+pub fn ty_params_to_tys(tcx: ty::ctxt, generics: &ast::Generics) -> ~[t] {
+    vec::from_fn(generics.ty_params.len(), |i| {
+        let id = generics.ty_params.get(i).id;
+        ty::mk_param(tcx, i, ast_util::local_def(id))
+    })
 }
 
 /// Returns an equivalent type with all the typedefs and self regions removed.
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index e63e46ace3d..fe956162786 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -127,6 +127,8 @@ use syntax::codemap;
 use syntax::parse::token::special_idents;
 use syntax::print::pprust;
 use syntax::visit;
+use syntax::opt_vec::OptVec;
+use syntax::opt_vec;
 use syntax;
 
 pub mod _match;
@@ -592,9 +594,9 @@ pub fn check_item(ccx: @mut CrateCtxt, it: @ast::item) {
       ast::item_struct(struct_def, _) => {
         check_struct(ccx, struct_def, it.id, it.span);
       }
-      ast::item_ty(t, tps) => {
+      ast::item_ty(t, ref generics) => {
         let tpt_ty = ty::node_id_to_type(ccx.tcx, it.id);
-        check_bounds_are_used(ccx, t.span, tps, tpt_ty);
+        check_bounds_are_used(ccx, t.span, &generics.ty_params, tpt_ty);
         // If this is a record ty, check for duplicate fields
         match t.node {
             ast::ty_rec(ref fields) => {
@@ -1062,8 +1064,9 @@ pub fn impl_self_ty(vcx: &VtableContext,
                   node: ast::item_impl(ref ts, _, st, _),
                   _
               }, _)) => {
-            (ts.len(), region_param,
-                vcx.ccx.to_ty(rscope::type_rscope(region_param), st))
+            (ts.ty_params.len(),
+             region_param,
+             vcx.ccx.to_ty(rscope::type_rscope(region_param), st))
           }
           Some(ast_map::node_item(@ast::item {
                   node: ast::item_struct(_, ref ts),
@@ -1074,12 +1077,13 @@ pub fn impl_self_ty(vcx: &VtableContext,
                  (doing a no-op subst for the ty params; in the next step,
                  we substitute in fresh vars for them)
                */
-              (ts.len(), region_param,
-                  ty::mk_struct(tcx, local_def(class_id),
+              (ts.ty_params.len(),
+               region_param,
+               ty::mk_struct(tcx, local_def(class_id),
                       substs {
                         self_r: rscope::bound_self_region(region_param),
                         self_ty: None,
-                        tps: ty::ty_params_to_tys(tcx, /*bad*/copy *ts)
+                        tps: ty::ty_params_to_tys(tcx, ts)
                       }))
           }
           _ => { tcx.sess.bug(~"impl_self_ty: unbound item or item that \
@@ -1862,11 +1866,11 @@ pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
                 tcx.region_paramd_items.find(&class_id.node);
             match tcx.items.find(&class_id.node) {
                 Some(ast_map::node_item(@ast::item {
-                        node: ast::item_struct(_, ref type_parameters),
+                        node: ast::item_struct(_, ref generics),
                         _
                     }, _)) => {
 
-                    type_parameter_count = type_parameters.len();
+                    type_parameter_count = generics.ty_params.len();
 
                     let self_region =
                         bound_self_region(region_parameterized);
@@ -1876,7 +1880,7 @@ pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
                         self_ty: None,
                         tps: ty::ty_params_to_tys(
                             tcx,
-                            /*bad*/copy *type_parameters)
+                            generics)
                     });
                 }
                 _ => {
@@ -1946,11 +1950,11 @@ pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
                 tcx.region_paramd_items.find(&enum_id.node);
             match tcx.items.find(&enum_id.node) {
                 Some(ast_map::node_item(@ast::item {
-                        node: ast::item_enum(_, ref type_parameters),
+                        node: ast::item_enum(_, ref generics),
                         _
                     }, _)) => {
 
-                    type_parameter_count = type_parameters.len();
+                    type_parameter_count = generics.ty_params.len();
 
                     let self_region =
                         bound_self_region(region_parameterized);
@@ -1960,7 +1964,7 @@ pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
                         self_ty: None,
                         tps: ty::ty_params_to_tys(
                             tcx,
-                            /*bad*/copy *type_parameters)
+                            generics)
                     });
                 }
                 _ => {
@@ -3126,7 +3130,7 @@ pub fn may_break(cx: ty::ctxt, id: ast::node_id, b: ast::blk) -> bool {
 
 pub fn check_bounds_are_used(ccx: @mut CrateCtxt,
                              span: span,
-                             tps: ~[ast::ty_param],
+                             tps: &OptVec<ast::TyParam>,
                              ty: ty::t) {
     debug!("check_bounds_are_used(n_tps=%u, ty=%s)",
            tps.len(), ppaux::ty_to_str(ccx.tcx, ty));
@@ -3153,7 +3157,7 @@ pub fn check_bounds_are_used(ccx: @mut CrateCtxt,
         if !*b {
             ccx.tcx.sess.span_err(
                 span, fmt!("type parameter `%s` is unused",
-                           *ccx.tcx.sess.str_of(tps[i].ident)));
+                           *ccx.tcx.sess.str_of(tps.get(i).ident)));
         }
     }
 }
diff --git a/src/librustc/middle/typeck/coherence.rs b/src/librustc/middle/typeck/coherence.rs
index 29738f28266..5ab2bcd8519 100644
--- a/src/librustc/middle/typeck/coherence.rs
+++ b/src/librustc/middle/typeck/coherence.rs
@@ -147,7 +147,7 @@ pub fn get_base_type_def_id(inference_context: @mut InferCtxt,
 pub fn method_to_MethodInfo(ast_method: @method) -> @MethodInfo {
     @MethodInfo {
         did: local_def(ast_method.id),
-        n_tps: ast_method.tps.len(),
+        n_tps: ast_method.generics.ty_params.len(),
         ident: ast_method.ident,
         self_type: ast_method.self_ty.node
     }
diff --git a/src/librustc/middle/typeck/collect.rs b/src/librustc/middle/typeck/collect.rs
index 96c76b52181..630ff46ccfb 100644
--- a/src/librustc/middle/typeck/collect.rs
+++ b/src/librustc/middle/typeck/collect.rs
@@ -60,6 +60,8 @@ use syntax::codemap::span;
 use syntax::codemap;
 use syntax::print::pprust::path_to_str;
 use syntax::visit;
+use syntax::opt_vec;
+use syntax::opt_vec::OptVec;
 
 pub fn collect_item_types(ccx: @mut CrateCtxt, crate: @ast::crate) {
 
@@ -70,8 +72,8 @@ pub fn collect_item_types(ccx: @mut CrateCtxt, crate: @ast::crate) {
         if crate_item.ident
             == ::syntax::parse::token::special_idents::intrinsic {
 
-            match /*bad*/copy crate_item.node {
-              ast::item_mod(m) => {
+            match crate_item.node {
+              ast::item_mod(ref m) => {
                 for m.items.each |intrinsic_item| {
                     let def_id = ast::def_id { crate: ast::local_crate,
                                                node: intrinsic_item.id };
@@ -153,7 +155,7 @@ pub impl AstConv for CrateCtxt {
 pub fn get_enum_variant_types(ccx: @mut CrateCtxt,
                               enum_ty: ty::t,
                               variants: &[ast::variant],
-                              +ty_params: ~[ast::ty_param],
+                              generics: &ast::Generics,
                               rp: Option<ty::region_variance>) {
     let tcx = ccx.tcx;
 
@@ -175,7 +177,7 @@ pub fn get_enum_variant_types(ccx: @mut CrateCtxt,
 
             ast::struct_variant_kind(struct_def) => {
                 let tpt = ty_param_bounds_and_ty {
-                    bounds: ty_param_bounds(ccx, ty_params),
+                    bounds: ty_param_bounds(ccx, generics),
                     region_param: rp,
                     ty: enum_ty
                 };
@@ -183,7 +185,7 @@ pub fn get_enum_variant_types(ccx: @mut CrateCtxt,
                 convert_struct(ccx,
                                rp,
                                struct_def,
-                               ty_params.to_vec(),
+                               generics,
                                tpt,
                                variant.node.id);
 
@@ -196,7 +198,7 @@ pub fn get_enum_variant_types(ccx: @mut CrateCtxt,
                 get_enum_variant_types(ccx,
                                        enum_ty,
                                        enum_definition.variants,
-                                       copy ty_params,
+                                       generics,
                                        rp);
                 result_ty = None;
             }
@@ -206,7 +208,7 @@ pub fn get_enum_variant_types(ccx: @mut CrateCtxt,
             None => {}
             Some(result_ty) => {
                 let tpt = ty_param_bounds_and_ty {
-                    bounds: ty_param_bounds(ccx, ty_params),
+                    bounds: ty_param_bounds(ccx, generics),
                     region_param: rp,
                     ty: result_ty
                 };
@@ -276,7 +278,7 @@ pub fn ensure_trait_methods(ccx: @mut CrateCtxt,
     let region_paramd = tcx.region_paramd_items.find(&id);
     match tcx.items.get(&id) {
       ast_map::node_item(@ast::item {
-                node: ast::item_trait(ref params, _, ref ms),
+                node: ast::item_trait(ref generics, _, ref ms),
                 _
             }, _) => {
         store_methods::<ast::trait_method>(ccx, id, (/*bad*/copy *ms), |m| {
@@ -288,7 +290,7 @@ pub fn ensure_trait_methods(ccx: @mut CrateCtxt,
                 ast::provided(method) => def_id = local_def(method.id)
             }
 
-            let trait_bounds = ty_param_bounds(ccx, *params);
+            let trait_bounds = ty_param_bounds(ccx, generics);
             let ty_m = trait_method_to_ty_method(*m);
             let method_ty = ty_of_ty_method(ccx, ty_m, region_paramd, def_id);
             if ty_m.self_ty.node == ast::sty_static {
@@ -488,7 +490,7 @@ pub fn compare_impl_method(tcx: ty::ctxt,
 }
 
 pub fn check_methods_against_trait(ccx: @mut CrateCtxt,
-                                   tps: ~[ast::ty_param],
+                                   generics: &ast::Generics,
                                    rp: Option<ty::region_variance>,
                                    selfty: ty::t,
                                    a_trait_ty: @ast::trait_ref,
@@ -522,8 +524,9 @@ pub fn check_methods_against_trait(ccx: @mut CrateCtxt,
     for impl_ms.each |impl_m| {
         match trait_ms.find(|trait_m| trait_m.ident == impl_m.mty.ident) {
             Some(ref trait_m) => {
+                let num_impl_tps = generics.ty_params.len();
                 compare_impl_method(
-                    ccx.tcx, tps.len(), impl_m, trait_m,
+                    ccx.tcx, num_impl_tps, impl_m, trait_m,
                     &tpt.substs, selfty);
             }
             None => {
@@ -568,7 +571,7 @@ pub fn convert_methods(ccx: @mut CrateCtxt,
 
     let tcx = ccx.tcx;
     do vec::map(ms) |m| {
-        let bounds = ty_param_bounds(ccx, m.tps);
+        let bounds = ty_param_bounds(ccx, &m.generics);
         let mty = ty_of_method(ccx, *m, rp);
         let fty = ty::mk_bare_fn(tcx, copy mty.fty);
         tcx.tcache.insert(
@@ -589,9 +592,9 @@ pub fn convert_methods(ccx: @mut CrateCtxt,
 
 pub fn ensure_no_ty_param_bounds(ccx: @mut CrateCtxt,
                                  span: span,
-                                 ty_params: &[ast::ty_param],
+                                 generics: &ast::Generics,
                                  thing: &static/str) {
-    for ty_params.each |ty_param| {
+    for generics.ty_params.each |ty_param| {
         if ty_param.bounds.len() > 0 {
             ccx.tcx.sess.span_err(
                 span,
@@ -606,21 +609,21 @@ pub fn convert(ccx: @mut CrateCtxt, it: @ast::item) {
     let rp = tcx.region_paramd_items.find(&it.id);
     debug!("convert: item %s with id %d rp %?",
            *tcx.sess.str_of(it.ident), it.id, rp);
-    match /*bad*/copy it.node {
+    match it.node {
       // These don't define types.
       ast::item_foreign_mod(_) | ast::item_mod(_) => {}
-      ast::item_enum(ref enum_definition, ref ty_params) => {
-        ensure_no_ty_param_bounds(ccx, it.span, *ty_params, "enumeration");
+      ast::item_enum(ref enum_definition, ref generics) => {
+        ensure_no_ty_param_bounds(ccx, it.span, generics, "enumeration");
         let tpt = ty_of_item(ccx, it);
         write_ty_to_tcx(tcx, it.id, tpt.ty);
         get_enum_variant_types(ccx,
                                tpt.ty,
                                enum_definition.variants,
-                               copy *ty_params,
+                               generics,
                                rp);
       }
-      ast::item_impl(ref tps, trait_ref, selfty, ref ms) => {
-        let i_bounds = ty_param_bounds(ccx, *tps);
+      ast::item_impl(ref generics, trait_ref, selfty, ref ms) => {
+        let i_bounds = ty_param_bounds(ccx, generics);
         let selfty = ccx.to_ty(type_rscope(rp), selfty);
         write_ty_to_tcx(tcx, it.id, selfty);
         tcx.tcache.insert(local_def(it.id),
@@ -632,11 +635,11 @@ pub fn convert(ccx: @mut CrateCtxt, it: @ast::item) {
         // XXX: Bad copy of `ms` below.
         let cms = convert_methods(ccx, /*bad*/copy *ms, rp, i_bounds);
         for trait_ref.each |t| {
-            check_methods_against_trait(ccx, /*bad*/copy *tps, rp, selfty,
+            check_methods_against_trait(ccx, generics, rp, selfty,
                                         *t, /*bad*/copy cms);
         }
       }
-      ast::item_trait(ref tps, ref supertraits, ref trait_methods) => {
+      ast::item_trait(ref generics, ref supertraits, ref trait_methods) => {
         let tpt = ty_of_item(ccx, it);
         debug!("item_trait(it.id=%d, tpt.ty=%s)",
                it.id, ppaux::ty_to_str(tcx, tpt.ty));
@@ -646,21 +649,21 @@ pub fn convert(ccx: @mut CrateCtxt, it: @ast::item) {
 
         let (_, provided_methods) =
             split_trait_methods(/*bad*/copy *trait_methods);
-        let (bounds, _) = mk_substs(ccx, /*bad*/copy *tps, rp);
+        let (bounds, _) = mk_substs(ccx, generics, rp);
         let _ = convert_methods(ccx, provided_methods, rp, bounds);
       }
-      ast::item_struct(struct_def, tps) => {
-        ensure_no_ty_param_bounds(ccx, it.span, tps, "structure");
+      ast::item_struct(struct_def, ref generics) => {
+        ensure_no_ty_param_bounds(ccx, it.span, generics, "structure");
 
         // Write the class type
         let tpt = ty_of_item(ccx, it);
         write_ty_to_tcx(tcx, it.id, tpt.ty);
         tcx.tcache.insert(local_def(it.id), tpt);
 
-        convert_struct(ccx, rp, struct_def, tps, tpt, it.id);
+        convert_struct(ccx, rp, struct_def, generics, tpt, it.id);
       }
-      ast::item_ty(_, ref ty_params) => {
-        ensure_no_ty_param_bounds(ccx, it.span, *ty_params, "type");
+      ast::item_ty(_, ref generics) => {
+        ensure_no_ty_param_bounds(ccx, it.span, generics, "type");
         let tpt = ty_of_item(ccx, it);
         write_ty_to_tcx(tcx, it.id, tpt.ty);
       }
@@ -677,7 +680,7 @@ pub fn convert(ccx: @mut CrateCtxt, it: @ast::item) {
 pub fn convert_struct(ccx: @mut CrateCtxt,
                       rp: Option<ty::region_variance>,
                       struct_def: @ast::struct_def,
-                      +tps: ~[ast::ty_param],
+                      generics: &ast::Generics,
                       tpt: ty::ty_param_bounds_and_ty,
                       id: ast::node_id) {
     let tcx = ccx.tcx;
@@ -702,7 +705,7 @@ pub fn convert_struct(ccx: @mut CrateCtxt,
     for struct_def.fields.each |f| {
        convert_field(ccx, rp, tpt.bounds, *f);
     }
-    let (_, substs) = mk_substs(ccx, tps, rp);
+    let (_, substs) = mk_substs(ccx, generics, rp);
     let selfty = ty::mk_struct(tcx, local_def(id), substs);
 
     // If this struct is enum-like or tuple-like, create the type of its
@@ -746,7 +749,7 @@ pub fn ty_of_method(ccx: @mut CrateCtxt,
                     rp: Option<ty::region_variance>) -> ty::method {
     ty::method {
         ident: m.ident,
-        tps: ty_param_bounds(ccx, m.tps),
+        tps: ty_param_bounds(ccx, &m.generics),
         fty: astconv::ty_of_bare_fn(ccx, type_rscope(rp), m.purity,
                                     ast::RustAbi, m.decl),
         self_ty: m.self_ty.node,
@@ -761,7 +764,7 @@ pub fn ty_of_ty_method(self: @mut CrateCtxt,
                        id: ast::def_id) -> ty::method {
     ty::method {
         ident: m.ident,
-        tps: ty_param_bounds(self, m.tps),
+        tps: ty_param_bounds(self, &m.generics),
         fty: astconv::ty_of_bare_fn(self, type_rscope(rp), m.purity,
                                     ast::RustAbi, m.decl),
         // assume public, because this is only invoked on trait methods
@@ -809,17 +812,17 @@ pub fn ty_of_item(ccx: @mut CrateCtxt, it: @ast::item)
       _ => {}
     }
     let rp = tcx.region_paramd_items.find(&it.id);
-    match /*bad*/copy it.node {
+    match it.node {
       ast::item_const(t, _) => {
         let typ = ccx.to_ty(empty_rscope, t);
         let tpt = no_params(typ);
         tcx.tcache.insert(local_def(it.id), tpt);
         return tpt;
       }
-      ast::item_fn(decl, purity, tps, _) => {
-        let bounds = ty_param_bounds(ccx, tps);
+      ast::item_fn(ref decl, purity, ref generics, _) => {
+        let bounds = ty_param_bounds(ccx, generics);
         let tofd = astconv::ty_of_bare_fn(ccx, empty_rscope, purity,
-                                          ast::RustAbi, decl);
+                                          ast::RustAbi, *decl);
         let tpt = ty_param_bounds_and_ty {
             bounds: bounds,
             region_param: None,
@@ -832,7 +835,7 @@ pub fn ty_of_item(ccx: @mut CrateCtxt, it: @ast::item)
         ccx.tcx.tcache.insert(local_def(it.id), tpt);
         return tpt;
       }
-      ast::item_ty(t, tps) => {
+      ast::item_ty(t, ref generics) => {
         match tcx.tcache.find(&local_def(it.id)) {
           Some(tpt) => return tpt,
           None => { }
@@ -846,12 +849,12 @@ pub fn ty_of_item(ccx: @mut CrateCtxt, it: @ast::item)
                 // like "foo<X>".  This is because otherwise ty_to_str will
                 // print the name as merely "foo", as it has no way to
                 // reconstruct the value of X.
-                if !vec::is_empty(tps) { t0 } else {
+                if !generics.is_empty() { t0 } else {
                     ty::mk_with_id(tcx, t0, def_id)
                 }
             };
             ty_param_bounds_and_ty {
-                bounds: ty_param_bounds(ccx, tps),
+                bounds: ty_param_bounds(ccx, generics),
                 region_param: rp,
                 ty: ty
             }
@@ -860,9 +863,9 @@ pub fn ty_of_item(ccx: @mut CrateCtxt, it: @ast::item)
         tcx.tcache.insert(local_def(it.id), tpt);
         return tpt;
       }
-      ast::item_enum(_, tps) => {
+      ast::item_enum(_, ref generics) => {
         // Create a new generic polytype.
-        let (bounds, substs) = mk_substs(ccx, tps, rp);
+        let (bounds, substs) = mk_substs(ccx, generics, rp);
         let t = ty::mk_enum(tcx, local_def(it.id), substs);
         let tpt = ty_param_bounds_and_ty {
             bounds: bounds,
@@ -872,8 +875,8 @@ pub fn ty_of_item(ccx: @mut CrateCtxt, it: @ast::item)
         tcx.tcache.insert(local_def(it.id), tpt);
         return tpt;
       }
-      ast::item_trait(tps, _, _) => {
-        let (bounds, substs) = mk_substs(ccx, tps, rp);
+      ast::item_trait(ref generics, _, _) => {
+        let (bounds, substs) = mk_substs(ccx, generics, rp);
         let t = ty::mk_trait(tcx, local_def(it.id), substs, ty::vstore_box);
         let tpt = ty_param_bounds_and_ty {
             bounds: bounds,
@@ -883,8 +886,8 @@ pub fn ty_of_item(ccx: @mut CrateCtxt, it: @ast::item)
         tcx.tcache.insert(local_def(it.id), tpt);
         return tpt;
       }
-      ast::item_struct(_, tps) => {
-          let (bounds, substs) = mk_substs(ccx, tps, rp);
+      ast::item_struct(_, ref generics) => {
+          let (bounds, substs) = mk_substs(ccx, generics, rp);
           let t = ty::mk_struct(tcx, local_def(it.id), substs);
           let tpt = ty_param_bounds_and_ty {
             bounds: bounds,
@@ -902,9 +905,10 @@ pub fn ty_of_item(ccx: @mut CrateCtxt, it: @ast::item)
 
 pub fn ty_of_foreign_item(ccx: @mut CrateCtxt, it: @ast::foreign_item)
     -> ty::ty_param_bounds_and_ty {
-    match /*bad*/copy it.node {
-      ast::foreign_item_fn(fn_decl, _, params) => {
-        return ty_of_foreign_fn_decl(ccx, fn_decl, params, local_def(it.id));
+    match it.node {
+      ast::foreign_item_fn(ref fn_decl, _, ref generics) => {
+        return ty_of_foreign_fn_decl(ccx, *fn_decl, local_def(it.id),
+                                     generics);
       }
       ast::foreign_item_const(t) => {
         let rb = in_binding_rscope(empty_rscope);
@@ -922,9 +926,9 @@ pub fn ty_of_foreign_item(ccx: @mut CrateCtxt, it: @ast::foreign_item)
 // either be user-defined traits, or one of the four built-in traits (formerly
 // known as kinds): Const, Copy, Durable, and Send.
 pub fn compute_bounds(ccx: @mut CrateCtxt,
-                      ast_bounds: @~[ast::ty_param_bound])
+                      ast_bounds: @OptVec<ast::TyParamBound>)
                    -> ty::param_bounds {
-    @do vec::flat_map(*ast_bounds) |b| {
+    @ast_bounds.flat_map_to_vec(|b| {
         match b {
             &TraitTyParamBound(b) => {
                 let li = &ccx.tcx.lang_items;
@@ -954,13 +958,13 @@ pub fn compute_bounds(ccx: @mut CrateCtxt,
             }
             &RegionTyParamBound => ~[ty::bound_durable]
         }
-    }
+    })
 }
 
 pub fn ty_param_bounds(ccx: @mut CrateCtxt,
-                       params: ~[ast::ty_param])
+                       generics: &ast::Generics)
                     -> @~[ty::param_bounds] {
-    @do params.map |param| {
+    @do generics.ty_params.map_to_vec |param| {
         match ccx.tcx.ty_param_bounds.find(&param.id) {
           Some(bs) => bs,
           None => {
@@ -974,10 +978,10 @@ pub fn ty_param_bounds(ccx: @mut CrateCtxt,
 
 pub fn ty_of_foreign_fn_decl(ccx: @mut CrateCtxt,
                              decl: ast::fn_decl,
-                             +ty_params: ~[ast::ty_param],
-                             def_id: ast::def_id)
+                             def_id: ast::def_id,
+                             generics: &ast::Generics)
                           -> ty::ty_param_bounds_and_ty {
-    let bounds = ty_param_bounds(ccx, ty_params);
+    let bounds = ty_param_bounds(ccx, generics);
     let rb = in_binding_rscope(empty_rscope);
     let input_tys = decl.inputs.map(|a| ty_of_arg(ccx, rb, *a, None) );
     let output_ty = ast_ty_to_ty(ccx, rb, decl.output);
@@ -998,13 +1002,13 @@ pub fn ty_of_foreign_fn_decl(ccx: @mut CrateCtxt,
     return tpt;
 }
 
-pub fn mk_ty_params(ccx: @mut CrateCtxt, atps: ~[ast::ty_param])
-    -> (@~[ty::param_bounds], ~[ty::t]) {
-
+pub fn mk_generics(ccx: @mut CrateCtxt, generics: &ast::Generics)
+    -> (@~[ty::param_bounds], ~[ty::t])
+{
     let mut i = 0u;
-    let bounds = ty_param_bounds(ccx, atps);
+    let bounds = ty_param_bounds(ccx, generics);
     (bounds,
-     vec::map(atps, |atp| {
+     generics.ty_params.map_to_vec(|atp| {
          let t = ty::mk_param(ccx.tcx, i, local_def(atp.id));
          i += 1u;
          t
@@ -1012,10 +1016,11 @@ pub fn mk_ty_params(ccx: @mut CrateCtxt, atps: ~[ast::ty_param])
 }
 
 pub fn mk_substs(ccx: @mut CrateCtxt,
-                 +atps: ~[ast::ty_param],
+                 generics: &ast::Generics,
                  rp: Option<ty::region_variance>)
-              -> (@~[ty::param_bounds], ty::substs) {
-    let (bounds, params) = mk_ty_params(ccx, atps);
+              -> (@~[ty::param_bounds], ty::substs)
+{
+    let (bounds, params) = mk_generics(ccx, generics);
     let self_r = rscope::bound_self_region(rp);
     (bounds, substs { self_r: self_r, self_ty: None, tps: params })
 }
diff --git a/src/librustdoc/tystr_pass.rs b/src/librustdoc/tystr_pass.rs
index b39cee87525..bdfc2be7bd6 100644
--- a/src/librustdoc/tystr_pass.rs
+++ b/src/librustdoc/tystr_pass.rs
@@ -77,7 +77,7 @@ fn get_fn_sig(srv: astsrv::Srv, fn_id: doc::AstId) -> Option<~str> {
             ident: ident,
             node: ast::foreign_item_fn(ref decl, _, ref tys), _
           }, _, _) => {
-            Some(pprust::fun_to_str(*decl, ident, copy *tys,
+            Some(pprust::fun_to_str(*decl, ident, tys,
                                     extract::interner()))
           }
           _ => fail!(~"get_fn_sig: fn_id not bound to a fn item")
@@ -215,7 +215,7 @@ fn get_method_sig(
                       Some(pprust::fun_to_str(
                           ty_m.decl,
                           ty_m.ident,
-                          copy ty_m.tps,
+                          &ty_m.generics,
                           extract::interner()
                       ))
                     }
@@ -223,7 +223,7 @@ fn get_method_sig(
                       Some(pprust::fun_to_str(
                           m.decl,
                           m.ident,
-                          copy m.tps,
+                          &m.generics,
                           extract::interner()
                       ))
                     }
@@ -242,7 +242,7 @@ fn get_method_sig(
                     Some(pprust::fun_to_str(
                         method.decl,
                         method.ident,
-                        copy method.tps,
+                        &method.generics,
                         extract::interner()
                     ))
                 }
@@ -339,7 +339,7 @@ fn fold_type(
                         Some(fmt!(
                             "type %s%s = %s",
                             to_str(ident),
-                            pprust::typarams_to_str(*params,
+                            pprust::generics_to_str(params,
                                                     extract::interner()),
                             pprust::ty_to_str(ty,
                                               extract::interner())
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index 5af67aa0e3b..5460584763e 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 @@ pub 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 74f67808a5e..ea34d5a2779 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 fec3a961a52..95f52fbea99 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 @@ pub 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 0019acc1291..6417707d8bb 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 49f7fe5853e..6324379fc9a 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 @@ pub 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;
 }
 
 pub impl ext_ctxt_ast_builder for ext_ctxt {
@@ -172,10 +174,10 @@ pub 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 @@ pub 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 @@ pub 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 @@ pub 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 cc42a0992cb..1d49b8c1be8 100644
--- a/src/libsyntax/ext/pipes/check.rs
+++ b/src/libsyntax/ext/pipes/check.rs
@@ -67,13 +67,13 @@ pub 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 66feb7cc753..ef705652929 100644
--- a/src/libsyntax/ext/pipes/parse_proto.rs
+++ b/src/libsyntax/ext/pipes/parse_proto.rs
@@ -51,13 +51,13 @@ pub 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 444b09d9ae4..6bb25e31f69 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 @@ pub 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 @@ pub 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 @@ pub 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 @@ pub impl gen_send for message {
                                 } else {
                                     cx.ty_nil_ast_builder()
                                 },
-                                params,
+                                self.get_generics(),
                                 cx.expr_block(body))
             }
           }
@@ -192,7 +193,7 @@ pub 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 @@ pub 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 @@ pub 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 @@ pub 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 @@ pub 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 @@ pub 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 @@ pub 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 @@ pub 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 @@ pub 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 7c6dc1f937d..6052e20e6e9 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 dacb6f60e37..acc1054aa71 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 af25a4f6e58..d4b7f2ae5b4 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};
@@ -83,6 +83,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};
@@ -438,7 +440,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
@@ -463,7 +465,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)
@@ -477,7 +479,7 @@ pub impl Parser {
                 provided(@ast::method {
                     ident: ident,
                     attrs: attrs,
-                    tps: tps,
+                    generics: generics,
                     self_ty: self_ty,
                     purity: pur,
                     decl: d,
@@ -917,19 +919,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),
@@ -975,7 +965,7 @@ pub impl Parser {
         }
     }
 
-    fn parse_lifetimes() -> ~[ast::Lifetime] {
+    fn parse_lifetimes() -> OptVec<ast::Lifetime> {
         /*!
          *
          * Parses zero or more comma separated lifetimes.
@@ -984,7 +974,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(_) => {
@@ -1155,7 +1145,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.
@@ -1287,8 +1277,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 {
                         ~[]
                     };
@@ -1418,7 +1407,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)])))
           }
@@ -2624,81 +2613,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)
@@ -2790,7 +2803,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 = ~[];
@@ -2806,7 +2819,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);
@@ -2849,10 +2862,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,
@@ -2867,10 +2880,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 {
@@ -2887,7 +2900,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()
         };
@@ -2899,7 +2912,7 @@ pub impl Parser {
         @ast::method {
             ident: ident,
             attrs: attrs,
-            tps: tps,
+            generics: generics,
             self_ty: self_ty,
             purity: pur,
             decl: decl,
@@ -2914,7 +2927,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;
@@ -2942,12 +2955,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
@@ -2989,37 +2997,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 {
@@ -3032,13 +3010,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);
@@ -3115,7 +3093,7 @@ pub impl Parser {
              fields: fields,
              dtor: actual_dtor,
              ctor_id: if is_tuple_like { Some(new_id) } else { None }
-         }, ty_params),
+         }, generics),
          None)
     }
 
@@ -3379,13 +3357,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 }
@@ -3548,7 +3526,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);
@@ -3604,8 +3582,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;
@@ -3632,7 +3609,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 {
@@ -3688,7 +3665,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();
@@ -3711,14 +3688,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|