libsyntax: abstract most of the deriving boilerplate into a simpler(r) interface.

Pulls out many of the common patterns from the Eq and Clone deriving code (and
invents a few of its own), so that deriving instances are very easy to write
for a certain class of traits. (Basically, those which don't have parameters
and where all methods only take arguments of type `&Self` and return either
`Self` or types with no parameters.)

7 files changed, 915 insertions, 42 deletions

diff --git a/src/libsyntax/ext/deriving/clone.rs b/src/libsyntax/ext/deriving/clone.rs
index c8ba6b990e4..390b72da331 100644
--- a/src/libsyntax/ext/deriving/clone.rs
+++ b/src/libsyntax/ext/deriving/clone.rs
@@ -55,7 +55,8 @@ fn create_derived_clone_impl(cx: @ext_ctxt,
         cx.ident_of(~"Clone"),
     ];
     let trait_path = build::mk_raw_path_global(span, trait_path);
-    create_derived_impl(cx, span, type_ident, generics, methods, trait_path, opt_vec::Empty)
+    create_derived_impl(cx, span, type_ident, generics, methods, trait_path,
+                        opt_vec::Empty, opt_vec::Empty)
 }
 // Creates a method from the given expression conforming to the signature of
 // the `clone` method.
@@ -219,7 +220,7 @@ fn expand_deriving_clone_tuple_struct_method(cx: @ext_ctxt,
     let mut subcalls = ~[];
     for uint::range(0, struct_def.fields.len()) |i| {
         // Create the expression for this field.
-        let field_ident = cx.ident_of(~"__self" + i.to_str());
+        let field_ident = cx.ident_of(~"__self_" + i.to_str());
         let field = build::mk_path(cx, span, ~[ field_ident ]);
 
         // Call the substructure method.
@@ -262,7 +263,7 @@ fn expand_deriving_clone_enum_method(cx: @ext_ctxt,
         let mut subcalls = ~[];
         for uint::range(0, variant_arg_count(cx, span, variant)) |j| {
             // Create the expression for this field.
-            let field_ident = cx.ident_of(~"__self" + j.to_str());
+            let field_ident = cx.ident_of(~"__self_" + j.to_str());
             let field = build::mk_path(cx, span, ~[ field_ident ]);
 
             // Call the substructure method.
diff --git a/src/libsyntax/ext/deriving/decodable.rs b/src/libsyntax/ext/deriving/decodable.rs
index 11f492316e2..df3536a3cae 100644
--- a/src/libsyntax/ext/deriving/decodable.rs
+++ b/src/libsyntax/ext/deriving/decodable.rs
@@ -81,7 +81,8 @@ fn create_derived_decodable_impl(
         generics,
         methods,
         trait_path,
-        generic_ty_params
+        generic_ty_params,
+        opt_vec::Empty
     )
 }
 
diff --git a/src/libsyntax/ext/deriving/encodable.rs b/src/libsyntax/ext/deriving/encodable.rs
index 81bfb03724f..9776f484818 100644
--- a/src/libsyntax/ext/deriving/encodable.rs
+++ b/src/libsyntax/ext/deriving/encodable.rs
@@ -81,7 +81,8 @@ fn create_derived_encodable_impl(
         generics,
         methods,
         trait_path,
-        generic_ty_params
+        generic_ty_params,
+        opt_vec::Empty
     )
 }
 
@@ -306,7 +307,7 @@ fn expand_deriving_encodable_enum_method(
         let variant_arg_len = variant_arg_count(cx, span, variant);
         for uint::range(0, variant_arg_len) |j| {
             // Create the expression for this field.
-            let field_ident = cx.ident_of(~"__self" + j.to_str());
+            let field_ident = cx.ident_of(~"__self_" + j.to_str());
             let field = build::mk_path(cx, span, ~[ field_ident ]);
 
             // Call the substructure method.
diff --git a/src/libsyntax/ext/deriving/eq.rs b/src/libsyntax/ext/deriving/eq.rs
index c427a206c2e..0afb667c69a 100644
--- a/src/libsyntax/ext/deriving/eq.rs
+++ b/src/libsyntax/ext/deriving/eq.rs
@@ -131,7 +131,7 @@ fn create_derived_eq_impl(cx: @ext_ctxt,
         cx.ident_of(~"Eq")
     ];
     let trait_path = build::mk_raw_path_global(span, trait_path);
-    create_derived_impl(cx, span, type_ident, generics, methods, trait_path, opt_vec::Empty)
+    create_derived_impl(cx, span, type_ident, generics, methods, trait_path, opt_vec::Empty, [])
 }
 
 fn call_substructure_eq_method(cx: @ext_ctxt,
@@ -338,13 +338,13 @@ fn expand_deriving_eq_enum_method(cx: @ext_ctxt,
         let mut matching_body_expr = None;
         for uint::range(0, variant_arg_count(cx, span, self_variant)) |i| {
             // Create the expression for the other field.
-            let other_field_ident = cx.ident_of(~"__other" + i.to_str());
+            let other_field_ident = cx.ident_of(~"__other_" + i.to_str());
             let other_field = build::mk_path(cx,
                                              span,
                                              ~[ other_field_ident ]);
 
             // Create the expression for this field.
-            let self_field_ident = cx.ident_of(~"__self" + i.to_str());
+            let self_field_ident = cx.ident_of(~"__self_" + i.to_str());
             let self_field = build::mk_path(cx, span, ~[ self_field_ident ]);
 
             // Call the substructure method.
@@ -456,10 +456,10 @@ fn expand_deriving_eq_struct_tuple_method(cx: @ext_ctxt,
     // Create comparison expression, comparing each of the fields
     let mut match_body = None;
     for fields.eachi |i, _| {
-        let other_field_ident = cx.ident_of(other_str + i.to_str());
+        let other_field_ident = cx.ident_of(fmt!("%s_%u", other_str, i));
         let other_field = build::mk_path(cx, span, ~[ other_field_ident ]);
 
-        let self_field_ident = cx.ident_of(self_str + i.to_str());
+        let self_field_ident = cx.ident_of(fmt!("%s_%u", self_str, i));
         let self_field = build::mk_path(cx, span, ~[ self_field_ident ]);
 
         call_substructure_eq_method(cx, span, self_field, other_field,
diff --git a/src/libsyntax/ext/deriving/generic.rs b/src/libsyntax/ext/deriving/generic.rs
new file mode 100644
index 00000000000..23a075ef001
--- /dev/null
+++ b/src/libsyntax/ext/deriving/generic.rs
@@ -0,0 +1,826 @@
+// Copyright 2013 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.
+
+/*!
+
+Some code that abstracts away much of the boilerplate of writing
+`deriving` instances for traits. Among other things it manages getting
+access to the fields of the 4 different sorts of structs and enum
+variants, as well as creating the method and impl ast instances.
+
+Supported features (fairly exhaustive):
+- Methods taking any number of parameters of type `&Self`, including
+  none other than `self`. (`MethodDef.nargs`)
+- Methods returning `Self` or a non-parameterised type
+  (e.g. `bool` or `core::cmp::Ordering`). (`MethodDef.output_type`)
+- Generating `impl`s for types with type parameters
+  (e.g. `Option<T>`), the parameters are automatically given the
+  current trait as a bound.
+- Additional bounds on the type parameters, e.g. the `Ord` instance
+  requires an explicit `Eq` bound at the
+  moment. (`TraitDef.additional_bounds`)
+
+(Key unsupported things: methods with arguments of non-`&Self` type,
+traits with parameters, methods returning parameterised types, static
+methods.)
+
+The most important thing for implementers is the `Substructure` and
+`SubstructureFields` objects. The latter groups 3 possibilities of the
+arguments:
+
+- `Struct`, when `Self` is a struct (including tuple structs, e.g
+  `struct T(int, char)`).
+- `EnumMatching`, when `Self` is an enum and all the arguments are the
+  same variant of the enum (e.g. `Some(1)`, `Some(3)` and `Some(4)`)
+- `EnumNonMatching` when `Self` is an enum and the arguments are not
+  the same variant (e.g. `None`, `Some(1)` and `None`)
+
+In the first two cases, the values from the corresponding fields in
+all the arguments are grouped together. In the `EnumNonMatching` case
+this isn't possible (different variants have different fields), so the
+fields are grouped by which argument they come from.
+
+All of the cases have `Option<ident>` in several places associated
+with field `expr`s. This represents the name of the field it is
+associated with. It is only not `None` when the associated field has
+an identifier in the source code. For example, the `x`s in the
+following snippet
+
+    struct A { x : int }
+
+    struct B(int);
+
+    enum C {
+        C0(int),
+        C1 { x: int }
+    }
+
+The `int`s in `B` and `C0` don't have an identifier, so the
+`Option<ident>`s would be `None` for them.
+
+# Examples
+
+The following simplified `Eq` is used for in-code examples:
+
+    trait Eq {
+        fn eq(&self, other: &Self);
+    }
+    impl Eq for int {
+        fn eq(&self, other: &int) -> bool {
+            *self == *other
+        }
+    }
+
+Some examples of the values of `SubstructureFields` follow, using the
+above `Eq`, `A`, `B` and `C`.
+
+## Structs
+
+When generating the `expr` for the `A` impl, the `SubstructureFields` is
+
+    Struct(~[(Some(<ident of x>),
+             <expr for self.x>,
+             ~[<expr for other.x])])
+
+For the `B` impl, called with `B(a)` and `B(b)`,
+
+    Struct(~[(None,
+              <expr for a>
+              ~[<expr for b>])])
+
+## Enums
+
+When generating the `expr` for a call with `self == C0(a)` and `other
+== C0(b)`, the SubstructureFields is
+
+    EnumMatching(0, <ast::variant for C0>,
+                 ~[None,
+                   <expr for a>,
+                   ~[<expr for b>]])
+
+For `C1 {x}` and `C1 {x}`,
+
+    EnumMatching(1, <ast::variant for C1>,
+                 ~[Some(<ident of x>),
+                   <expr for self.x>,
+                   ~[<expr for other.x>]])
+
+For `C0(a)` and `C1 {x}` ,
+
+    EnumNonMatching(~[(0, <ast::variant for B0>,
+                       ~[(None, <expr for a>)]),
+                      (1, <ast::variant for B1>,
+                       ~[(Some(<ident of x>),
+                          <expr for other.x>)])])
+
+(and vice verse, but with the order of the outermost list flipped.)
+
+*/
+
+use core::prelude::*;
+
+use ast;
+
+use ast::{
+    and, binop, deref, enum_def, expr, expr_match, ident, impure_fn,
+    item, Generics, m_imm, meta_item, method, named_field, or, public,
+    struct_def, sty_region, ty_rptr, ty_path, variant};
+
+use ast_util;
+use ext::base::ext_ctxt;
+use ext::build;
+use ext::deriving::*;
+use codemap::{span,respan};
+use opt_vec;
+
+pub fn expand_deriving_generic(cx: @ext_ctxt,
+                               span: span,
+                               _mitem: @meta_item,
+                               in_items: ~[@item],
+                               trait_def: &TraitDef) -> ~[@item] {
+    let expand_enum: ExpandDerivingEnumDefFn =
+        |cx, span, enum_def, type_ident, generics| {
+        trait_def.expand_enum_def(cx, span, enum_def, type_ident, generics)
+    };
+    let expand_struct: ExpandDerivingStructDefFn =
+        |cx, span, struct_def, type_ident, generics| {
+        trait_def.expand_struct_def(cx, span, struct_def, type_ident, generics)
+    };
+
+    expand_deriving(cx, span, in_items,
+                    expand_struct,
+                    expand_enum)
+}
+
+pub struct TraitDef<'self> {
+    /// Path of the trait
+    path: ~[~str],
+    /// Additional bounds required of any type parameters, other than
+    /// the current trait
+    additional_bounds: ~[~[~str]],
+    methods: ~[MethodDef<'self>]
+}
+
+pub struct MethodDef<'self> {
+    /// name of the method
+    name: ~str,
+    /// The path of return type of the method, e.g. `~[~"core",
+    /// ~"cmp", ~"Eq"]`. `None` for `Self`.
+    output_type: Option<~[~str]>,
+    /// Number of arguments other than `self` (all of type `&Self`)
+    nargs: uint,
+
+    combine_substructure: CombineSubstructureFunc<'self>
+}
+
+/// All the data about the data structure/method being derived upon.
+pub struct Substructure<'self> {
+    type_ident: ident,
+    method_ident: ident,
+    fields: &'self SubstructureFields
+}
+
+/// A summary of the possible sets of fields. See above for details
+/// and examples
+pub enum SubstructureFields {
+    /**
+    Vec of `(field ident, self, [others])` where the field ident is
+    the ident of the current field (`None` for all fields in tuple
+    structs)
+    */
+    Struct(~[(Option<ident>, @expr, ~[@expr])]),
+
+    /**
+    Matching variants of the enum: variant index, ast::variant,
+    fields: `(field ident, self, [others])`, where the field ident is
+    only non-`None` in the case of a struct variant.
+    */
+    EnumMatching(uint, variant, ~[(Option<ident>, @expr, ~[@expr])]),
+
+    /**
+    non-matching variants of the enum, [(variant index, ast::variant,
+    [field ident, fields])] (i.e. all fields for self are in the
+    first tuple, for other1 are in the second tuple, etc.)
+    */
+    EnumNonMatching(~[(uint, variant, ~[(Option<ident>, @expr)])])
+}
+
+
+/**
+Combine the values of all the fields together. The last argument is
+all the fields of all the structures, see above for details.
+*/
+pub type CombineSubstructureFunc<'self> =
+    &'self fn(@ext_ctxt, span, &Substructure) -> @expr;
+
+/**
+Deal with non-matching enum variants, the argument is a list
+representing each variant: (variant index, ast::variant instance,
+[variant fields])
+*/
+pub type EnumNonMatchFunc<'self> =
+    &'self fn(@ext_ctxt, span, ~[(uint, variant, ~[(Option<ident>, @expr)])]) -> @expr;
+
+
+
+impl<'self> TraitDef<'self> {
+    fn create_derived_impl(&self, cx: @ext_ctxt, span: span,
+                           type_ident: ident, generics: &Generics,
+                           methods: ~[@method]) -> @item {
+        let trait_path = build::mk_raw_path_global(
+            span,
+            do self.path.map |&s| { cx.ident_of(s) });
+
+        let additional_bounds = opt_vec::from(
+            do self.additional_bounds.map |v| {
+                do v.map |&s| { cx.ident_of(s) }
+            });
+        create_derived_impl(cx, span,
+                            type_ident, generics,
+                            methods, trait_path,
+                            opt_vec::Empty,
+                            additional_bounds)
+    }
+
+    fn expand_struct_def(&self, cx: @ext_ctxt,
+                         span: span,
+                         struct_def: &struct_def,
+                         type_ident: ident,
+                         generics: &Generics)
+    -> @item {
+        let is_tuple = is_struct_tuple(struct_def);
+
+        let methods = do self.methods.map |method_def| {
+            let body = if is_tuple {
+                method_def.expand_struct_tuple_method_body(cx, span,
+                                                           struct_def,
+                                                           type_ident)
+            } else {
+                method_def.expand_struct_method_body(cx, span,
+                                                     struct_def,
+                                                     type_ident)
+            };
+
+            method_def.create_method(cx, span, type_ident, generics, body)
+        };
+
+        self.create_derived_impl(cx, span, type_ident, generics, methods)
+    }
+
+    fn expand_enum_def(&self,
+                       cx: @ext_ctxt, span: span,
+                       enum_def: &enum_def,
+                       type_ident: ident,
+                       generics: &Generics) -> @item {
+        let methods = do self.methods.map |method_def| {
+            let body = method_def.expand_enum_method_body(cx, span,
+                                                          enum_def,
+                                                          type_ident);
+
+            method_def.create_method(cx, span, type_ident, generics, body)
+        };
+
+        self.create_derived_impl(cx, span, type_ident, generics, methods)
+    }
+}
+
+impl<'self> MethodDef<'self> {
+    fn call_substructure_method(&self,
+                                cx: @ext_ctxt,
+                                span: span,
+                                type_ident: ident,
+                                fields: &SubstructureFields)
+        -> @expr {
+        let substructure = Substructure {
+            type_ident: type_ident,
+            method_ident: cx.ident_of(self.name),
+            fields: fields
+        };
+        (self.combine_substructure)(cx, span,
+                                    &substructure)
+    }
+
+    fn get_output_type_path(&self, cx: @ext_ctxt, span: span,
+                              generics: &Generics, type_ident: ident) -> @ast::Path {
+        match self.output_type {
+            None => { // Self, add any type parameters
+                let out_ty_params = do vec::build |push| {
+                    for generics.ty_params.each |ty_param| {
+                        push(build::mk_ty_path(cx, span, ~[ ty_param.ident ]));
+                    }
+                };
+
+                build::mk_raw_path_(span, ~[ type_ident ], out_ty_params)
+            }
+            Some(str_path) => {
+                let p = do str_path.map |&s| { cx.ident_of(s) };
+                build::mk_raw_path(span, p)
+            }
+        }
+    }
+
+    fn create_method(&self, cx: @ext_ctxt, span: span,
+                     type_ident: ident,
+                     generics: &Generics, body: @expr) -> @method {
+        // Create the `Self` type of the `other` parameters.
+        let arg_path_type = create_self_type_with_params(cx,
+                                                         span,
+                                                         type_ident,
+                                                         generics);
+        let arg_type = ty_rptr(
+            None,
+            ast::mt { ty: arg_path_type, mutbl: m_imm }
+        );
+        let arg_type = @ast::Ty {
+            id: cx.next_id(),
+            node: arg_type,
+            span: span,
+        };
+
+        // create the arguments
+        let other_idents = create_other_idents(cx, self.nargs);
+        let args = do other_idents.map |&id| {
+            build::mk_arg(cx, span, id, arg_type)
+        };
+
+        let output_type = self.get_output_type_path(cx, span, generics, type_ident);
+        let output_type = ty_path(output_type, cx.next_id());
+        let output_type = @ast::Ty {
+            id: cx.next_id(),
+            node: output_type,
+            span: span,
+        };
+
+        let method_ident = cx.ident_of(self.name);
+        let fn_decl = build::mk_fn_decl(args, output_type);
+        let body_block = build::mk_simple_block(cx, span, body);
+
+        // Create the method.
+        let self_ty = respan(span, sty_region(None, m_imm));
+        @ast::method {
+            ident: method_ident,
+            attrs: ~[],
+            generics: ast_util::empty_generics(),
+            self_ty: self_ty,
+            purity: impure_fn,
+            decl: fn_decl,
+            body: body_block,
+            id: cx.next_id(),
+            span: span,
+            self_id: cx.next_id(),
+            vis: public
+        }
+    }
+
+    /**
+    ```
+    #[deriving(Eq)]
+    struct A(int, int);
+
+    // equivalent to:
+
+    impl Eq for A {
+        fn eq(&self, __other_1: &A) -> bool {
+            match *self {
+                (ref self_1, ref self_2) => {
+                    match *__other_1 {
+                        (ref __other_1_1, ref __other_1_2) => {
+                            self_1.eq(__other_1_1) && self_2.eq(__other_1_2)
+                        }
+                    }
+                }
+            }
+        }
+    }
+    ```
+    */
+    fn expand_struct_tuple_method_body(&self,
+                                           cx: @ext_ctxt,
+                                               span: span,
+                                               struct_def: &struct_def,
+                                           type_ident: ident) -> @expr {
+        let self_str = ~"self";
+        let other_strs = create_other_strs(self.nargs);
+        let num_fields = struct_def.fields.len();
+
+
+        let fields = do struct_def.fields.mapi |i, _| {
+            let other_fields = do other_strs.map |&other_str| {
+                let other_field_ident = cx.ident_of(fmt!("%s_%u", other_str, i));
+                build::mk_path(cx, span, ~[ other_field_ident ])
+            };
+
+            let self_field_ident = cx.ident_of(fmt!("%s_%u", self_str, i));
+            let self_field = build::mk_path(cx, span, ~[ self_field_ident ]);
+
+            (None, self_field, other_fields)
+        };
+
+        let mut match_body = self.call_substructure_method(cx, span, type_ident, &Struct(fields));
+
+        let type_path = build::mk_raw_path(span, ~[type_ident]);
+
+        // create the matches from inside to out (i.e. other_{self.nargs} to other_1)
+        for other_strs.each_reverse |&other_str| {
+            match_body = create_deref_match(cx, span, type_path,
+                                            other_str, num_fields,
+                                            match_body)
+        }
+
+        // create the match on self
+        return create_deref_match(cx, span, type_path,
+                                  ~"self", num_fields, match_body);
+
+        /**
+        Creates a match expression against a tuple that needs to
+        be dereferenced, but nothing else
+
+        ```
+        match *`to_match` {
+            (`to_match`_1, ..., `to_match`_`num_fields`) => `match_body`
+        }
+        ```
+        */
+        fn create_deref_match(cx: @ext_ctxt,
+                              span: span,
+                              type_path: @ast::Path,
+                              to_match: ~str,
+                              num_fields: uint,
+                              match_body: @expr) -> @expr {
+            let match_subpats = create_subpatterns(cx, span, to_match, num_fields);
+            let match_arm = ast::arm {
+                pats: ~[ build::mk_pat_enum(cx, span, type_path, match_subpats) ],
+                guard: None,
+                body: build::mk_simple_block(cx, span, match_body),
+            };
+
+            let deref_expr = build::mk_unary(cx, span, deref,
+                                             build::mk_path(cx, span,
+                                                            ~[ cx.ident_of(to_match)]));
+            let match_expr = build::mk_expr(cx, span, expr_match(deref_expr, ~[match_arm]));
+
+            match_expr
+        }
+    }
+
+    /**
+    ```
+    #[deriving(Eq)]
+    struct A { x: int, y: int }
+
+    // equivalent to:
+
+    impl Eq for A {
+        fn eq(&self, __other_1: &A) -> bool {
+            self.x.eq(&__other_1.x) &&
+                self.y.eq(&__other_1.y)
+        }
+    }
+    ```
+    */
+    fn expand_struct_method_body(&self,
+                                     cx: @ext_ctxt,
+                                     span: span,
+                                     struct_def: &struct_def,
+                                     type_ident: ident)
+        -> @expr {
+        let self_ident = cx.ident_of(~"self");
+        let other_idents = create_other_idents(cx, self.nargs);
+
+        let fields = do struct_def.fields.map |struct_field| {
+            match struct_field.node.kind {
+                named_field(ident, _, _) => {
+                    // Create the accessor for this field in the other args.
+                    let other_fields = do other_idents.map |&id| {
+                        build::mk_access(cx, span, ~[id], ident)
+                    };
+                    let other_field_refs = do other_fields.map |&other_field| {
+                        build::mk_addr_of(cx, span, other_field)
+                    };
+
+                    // Create the accessor for this field in self.
+                    let self_field =
+                        build::mk_access(
+                            cx, span,
+                            ~[ self_ident ],
+                            ident);
+
+                    (Some(ident), self_field, other_field_refs)
+                }
+                unnamed_field => {
+                    cx.span_unimpl(span, ~"unnamed fields with `deriving_generic`");
+                }
+            }
+        };
+
+        self.call_substructure_method(cx, span, type_ident, &Struct(fields))
+    }
+
+    /**
+    ```
+    #[deriving(Eq)]
+    enum A {
+        A1
+        A2(int)
+    }
+
+    // is equivalent to
+
+    impl Eq for A {
+        fn eq(&self, __other_1: &A) {
+            match *self {
+                A1 => match *__other_1 {
+                    A1 => true,
+                    A2(ref __other_1_1) => false
+                },
+                A2(self_1) => match *__other_1 {
+                    A1 => false,
+                    A2(ref __other_1_1) => self_1.eq(__other_1_1)
+                }
+            }
+        }
+    }
+    ```
+    */
+    fn expand_enum_method_body(&self,
+                               cx: @ext_ctxt,
+                               span: span,
+                               enum_def: &enum_def,
+                               type_ident: ident)
+        -> @expr {
+        self.build_enum_match(cx, span, enum_def, type_ident, ~[])
+    }
+
+
+    /**
+    Creates the nested matches for an enum definition, i.e.
+
+    ```
+    match self {
+       Variant1 => match other { Variant1 => matching, Variant2 => nonmatching, ... },
+       Variant2 => match other { Variant1 => nonmatching, Variant2 => matching, ... },
+       ...
+    }
+    ```
+
+    It acts in the most naive way, so every branch (and subbranch,
+    subsubbranch, etc) exists, not just the ones where all the variants in
+    the tree are the same. Hopefully the optimisers get rid of any
+    repetition, otherwise derived methods with many Self arguments will be
+    exponentially large.
+    */
+    fn build_enum_match(&self,
+                        cx: @ext_ctxt, span: span,
+                        enum_def: &enum_def,
+                        type_ident: ident,
+                        matches_so_far: ~[(uint, variant,
+                                           ~[(Option<ident>, @expr)])]) -> @expr {
+        if matches_so_far.len() == self.nargs + 1 {
+            // we've matched against all arguments, so make the final
+            // expression at the bottom of the match tree
+            match matches_so_far {
+                [] => cx.bug(~"no self match on an enum in `deriving_generic`"),
+                _ => {
+                    // we currently have a vec of vecs, where each
+                    // subvec is the fields of one of the arguments,
+                    // but if the variants all match, we want this as
+                    // vec of tuples, where each tuple represents a
+                    // field.
+
+                    // `ref` inside let matches is buggy. Causes havoc wih rusc.
+                    // let (variant_index, ref self_vec) = matches_so_far[0];
+                    let (variant_index, variant, self_vec) = match matches_so_far[0] {
+                        (i, v, ref s) => (i, v, s)
+                    };
+
+                    let substructure;
+
+                    // most arms don't have matching variants, so do a
+                    // quick check to see if they match (even though
+                    // this means iterating twice) instead of being
+                    // optimistic and doing a pile of allocations etc.
+                    if matches_so_far.all(|&(v_i, _, _)| v_i == variant_index) {
+                        let mut enum_matching_fields = vec::from_elem(self_vec.len(), ~[]);
+
+                        for matches_so_far.tail().each |&(_, _, other_fields)| {
+                            for other_fields.eachi |i, &(_, other_field)| {
+                                enum_matching_fields[i].push(other_field);
+                            }
+                        }
+                        let field_tuples =
+                            do vec::map2(*self_vec,
+                                         enum_matching_fields) |&(id, self_f), &other| {
+                            (id, self_f, other)
+                        };
+                        substructure = EnumMatching(variant_index, variant, field_tuples);
+                    } else {
+                        substructure = EnumNonMatching(matches_so_far);
+                    }
+                    self.call_substructure_method(cx, span, type_ident, &substructure)
+                }
+            }
+
+        } else {  // there are still matches to create
+            let (current_match_ident, current_match_str) = if matches_so_far.is_empty() {
+                (cx.ident_of(~"self"), ~"__self")
+            } else {
+                let s = fmt!("__other_%u", matches_so_far.len() - 1);
+                (cx.ident_of(s), s)
+            };
+
+            let mut arms = ~[];
+
+            // this is used as a stack
+            let mut matches_so_far = matches_so_far;
+
+            // create an arm matching on each variant
+            for enum_def.variants.eachi |index, variant| {
+                let pattern = create_enum_variant_pattern(cx, span,
+                                                          variant,
+                                                          current_match_str);
+
+                let idents = do vec::build |push| {
+                    for each_variant_arg_ident(cx, span, variant) |i, field_id| {
+                        let id = cx.ident_of(fmt!("%s_%u", current_match_str, i));
+                        push((field_id, build::mk_path(cx, span, ~[ id ])));
+                    }
+                };
+
+
+                matches_so_far.push((index, *variant, idents));
+                let arm_expr = self.build_enum_match(cx, span,
+                                                     enum_def,
+                                                     type_ident,
+                                                     matches_so_far);
+                matches_so_far.pop();
+
+                let arm_block = build::mk_simple_block(cx, span, arm_expr);
+                let arm = ast::arm {
+                    pats: ~[ pattern ],
+                    guard: None,
+                    body: arm_block
+                };
+                arms.push(arm);
+            }
+
+            let deref_expr = build::mk_unary(cx, span, deref,
+                                             build::mk_path(cx, span,
+                                                            ~[ current_match_ident ]));
+            let match_expr = build::mk_expr(cx, span,
+                                            expr_match(deref_expr, arms));
+
+            match_expr
+        }
+    }
+}
+
+/// Create variable names (as strings) to refer to the non-self
+/// parameters
+fn create_other_strs(n: uint) -> ~[~str] {
+    do vec::build |push| {
+        for uint::range(0, n) |i| {
+            push(fmt!("__other_%u", i));
+        }
+    }
+}
+/// Like `create_other_strs`, but returns idents for the strings
+fn create_other_idents(cx: @ext_ctxt, n: uint) -> ~[ident] {
+    do create_other_strs(n).map |&s| {
+        cx.ident_of(s)
+    }
+}
+
+
+
+/* helpful premade recipes */
+
+/**
+Fold the fields. `use_foldl` controls whether this is done
+left-to-right (`true`) or right-to-left (`false`).
+*/
+pub fn cs_fold(use_foldl: bool,
+               f: &fn(@ext_ctxt, span,
+                      old: @expr,
+                      self_f: @expr, other_fs: ~[@expr]) -> @expr,
+               base: @expr,
+               enum_nonmatch_f: EnumNonMatchFunc,
+               cx: @ext_ctxt, span: span,
+               substructure: &Substructure) -> @expr {
+    match *substructure.fields {
+        EnumMatching(_, _, all_fields) | Struct(all_fields) => {
+            if use_foldl {
+                do all_fields.foldl(base) |&old, &(_, self_f, other_fs)| {
+                    f(cx, span, old, self_f, other_fs)
+                }
+            } else {
+                do all_fields.foldr(base) |&(_, self_f, other_fs), old| {
+                    f(cx, span, old, self_f, other_fs)
+                }
+            }
+        },
+        EnumNonMatching(all_enums) => enum_nonmatch_f(cx, span, all_enums)
+    }
+}
+
+
+/**
+Call the method that is being derived on all the fields, and then
+process the collected results. i.e.
+
+```
+f(cx, span, ~[self_1.method(__other_1_1, __other_2_1),
+              self_2.method(__other_1_2, __other_2_2)])
+```
+*/
+pub fn cs_same_method(f: &fn(@ext_ctxt, span, ~[@expr]) -> @expr,
+                      enum_nonmatch_f: EnumNonMatchFunc,
+                      cx: @ext_ctxt, span: span,
+                      substructure: &Substructure) -> @expr {
+    match *substructure.fields {
+        EnumMatching(_, _, all_fields) | Struct(all_fields) => {
+            // call self_n.method(other_1_n, other_2_n, ...)
+            let called = do all_fields.map |&(_, self_field, other_fields)| {
+                build::mk_method_call(cx, span,
+                                      self_field,
+                                      substructure.method_ident,
+                                      other_fields)
+            };
+
+            f(cx, span, called)
+        },
+        EnumNonMatching(all_enums) => enum_nonmatch_f(cx, span, all_enums)
+    }
+}
+
+/**
+Fold together the results of calling the derived method on all the
+fields. `use_foldl` controls whether this is done left-to-right
+(`true`) or right-to-left (`false`).
+*/
+pub fn cs_same_method_fold(use_foldl: bool,
+                           f: &fn(@ext_ctxt, span, @expr, @expr) -> @expr,
+                           base: @expr,
+                           enum_nonmatch_f: EnumNonMatchFunc,
+                           cx: @ext_ctxt, span: span,
+                           substructure: &Substructure) -> @expr {
+    cs_same_method(
+        |cx, span, vals| {
+            if use_foldl {
+                do vals.foldl(base) |&old, &new| {
+                    f(cx, span, old, new)
+                }
+            } else {
+                do vals.foldr(base) |&new, old| {
+                    f(cx, span, old, new)
+                }
+            }
+        },
+        enum_nonmatch_f,
+        cx, span, substructure)
+
+}
+
+/**
+Use a given binop to combine the result of calling the derived method
+on all the fields.
+*/
+pub fn cs_binop(binop: binop, base: @expr,
+                enum_nonmatch_f: EnumNonMatchFunc,
+                cx: @ext_ctxt, span: span,
+                substructure: &Substructure) -> @expr {
+    cs_same_method_fold(
+        true, // foldl is good enough
+        |cx, span, old, new| {
+            build::mk_binary(cx, span,
+                             binop,
+                             old, new)
+
+        },
+        base,
+        enum_nonmatch_f,
+        cx, span, substructure)
+}
+
+/// cs_binop with binop == or
+pub fn cs_or(enum_nonmatch_f: EnumNonMatchFunc,
+             cx: @ext_ctxt, span: span,
+             substructure: &Substructure) -> @expr {
+    cs_binop(or, build::mk_bool(cx, span, false),
+             enum_nonmatch_f,
+             cx, span, substructure)
+}
+/// cs_binop with binop == and
+pub fn cs_and(enum_nonmatch_f: EnumNonMatchFunc,
+              cx: @ext_ctxt, span: span,
+              substructure: &Substructure) -> @expr {
+    cs_binop(and, build::mk_bool(cx, span, true),
+             enum_nonmatch_f,
+             cx, span, substructure)
+}
diff --git a/src/libsyntax/ext/deriving/iter_bytes.rs b/src/libsyntax/ext/deriving/iter_bytes.rs
index 4124e6ee6c1..75215b90eb0 100644
--- a/src/libsyntax/ext/deriving/iter_bytes.rs
+++ b/src/libsyntax/ext/deriving/iter_bytes.rs
@@ -56,7 +56,8 @@ fn create_derived_iter_bytes_impl(cx: @ext_ctxt,
         cx.ident_of(~"IterBytes")
     ];
     let trait_path = build::mk_raw_path_global(span, trait_path);
-    create_derived_impl(cx, span, type_ident, generics, methods, trait_path, opt_vec::Empty)
+    create_derived_impl(cx, span, type_ident, generics, methods, trait_path,
+                        opt_vec::Empty, opt_vec::Empty)
 }
 
 // Creates a method from the given set of statements conforming to the
@@ -230,7 +231,7 @@ fn expand_deriving_iter_bytes_enum_method(cx: @ext_ctxt,
         // as well.
         for uint::range(0, variant_arg_count(cx, span, variant)) |j| {
             // Create the expression for this field.
-            let field_ident = cx.ident_of(~"__self" + j.to_str());
+            let field_ident = cx.ident_of(~"__self_" + j.to_str());
             let field = build::mk_path(cx, span, ~[ field_ident ]);
 
             // Call the substructure method.
diff --git a/src/libsyntax/ext/deriving/mod.rs b/src/libsyntax/ext/deriving/mod.rs
index 63106eae48a..1241d4fa711 100644
--- a/src/libsyntax/ext/deriving/mod.rs
+++ b/src/libsyntax/ext/deriving/mod.rs
@@ -24,30 +24,32 @@ use ast::{tuple_variant_kind};
 use ast::{ty_path, unnamed_field, variant};
 use ext::base::ext_ctxt;
 use ext::build;
-use codemap::span;
+use codemap::{span, respan};
 use parse::token::special_idents::clownshoes_extensions;
 use opt_vec;
 
 use core::uint;
 
-pub mod clone;
 pub mod eq;
+pub mod clone;
 pub mod iter_bytes;
 pub mod encodable;
 pub mod decodable;
 
-type ExpandDerivingStructDefFn<'self> = &'self fn(@ext_ctxt,
-                                                  span,
-                                                  x: &struct_def,
-                                                  ident,
-                                                  y: &Generics)
-                                               -> @item;
-type ExpandDerivingEnumDefFn<'self> = &'self fn(@ext_ctxt,
-                                                span,
-                                                x: &enum_def,
-                                                ident,
-                                                y: &Generics)
-                                             -> @item;
+pub mod generic;
+
+pub type ExpandDerivingStructDefFn<'self> = &'self fn(@ext_ctxt,
+                                                       span,
+                                                       x: &struct_def,
+                                                       ident,
+                                                       y: &Generics)
+                                                 -> @item;
+pub type ExpandDerivingEnumDefFn<'self> = &'self fn(@ext_ctxt,
+                                                    span,
+                                                    x: &enum_def,
+                                                    ident,
+                                                    y: &Generics)
+                                                 -> @item;
 
 pub fn expand_meta_deriving(cx: @ext_ctxt,
                             _span: span,
@@ -72,10 +74,10 @@ pub fn expand_meta_deriving(cx: @ext_ctxt,
                     meta_list(tname, _) |
                     meta_word(tname) => {
                         match *tname {
+                            ~"Eq" => eq::expand_deriving_eq(cx, titem.span,
+                                                            titem, in_items),
                             ~"Clone" => clone::expand_deriving_clone(cx,
                                 titem.span, titem, in_items),
-                            ~"Eq" => eq::expand_deriving_eq(cx, titem.span,
-                                titem, in_items),
                             ~"IterBytes" => iter_bytes::expand_deriving_iter_bytes(cx,
                                 titem.span, titem, in_items),
                             ~"Encodable" => encodable::expand_deriving_encodable(cx,
@@ -126,9 +128,19 @@ pub fn expand_deriving(cx: @ext_ctxt,
 }
 
 fn create_impl_item(cx: @ext_ctxt, span: span, +item: item_) -> @item {
+    let doc_attr = respan(span,
+                          ast::lit_str(@~"Automatically derived."));
+    let doc_attr = respan(span, ast::meta_name_value(@~"doc", doc_attr));
+    let doc_attr = ast::attribute_ {
+        style: ast::attr_outer,
+        value: @doc_attr,
+        is_sugared_doc: false
+    };
+    let doc_attr = respan(span, doc_attr);
+
     @ast::item {
         ident: clownshoes_extensions,
-        attrs: ~[],
+        attrs: ~[doc_attr],
         id: cx.next_id(),
         node: item,
         vis: public,
@@ -164,14 +176,17 @@ pub fn create_derived_impl(cx: @ext_ctxt,
                            generics: &Generics,
                            methods: &[@method],
                            trait_path: @ast::Path,
-                           mut impl_ty_params: opt_vec::OptVec<ast::TyParam>)
+                           mut impl_ty_params: opt_vec::OptVec<ast::TyParam>,
+                           bounds_paths: opt_vec::OptVec<~[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> { ... }
+     *      impl<'a, ..., 'z, A:Tr B1 B2, ..., Z: Tr B1 B2> Tr for T<A, ..., Z> { ... }
+     *
+     * where B1, B2, ... are the bounds given by `bounds_paths`.
      *
      * FIXME(#5090): Remove code duplication between this and the
      * code in auto_encode.rs
@@ -182,16 +197,21 @@ pub fn create_derived_impl(cx: @ext_ctxt,
         build::mk_lifetime(cx, l.span, l.ident)
     });
 
-    // Create the reference to the trait.
-    let trait_ref = build::mk_trait_ref_(cx, trait_path);
-
     // Create the type parameters.
     for generics.ty_params.each |ty_param| {
-        let bounds = @opt_vec::with(
-            build::mk_trait_ty_param_bound_(cx, trait_path)
-        );
-        impl_ty_params.push(build::mk_ty_param(cx, ty_param.ident, bounds));
-    };
+        let mut bounds = do bounds_paths.map |&bound_path| {
+            build::mk_trait_ty_param_bound_global(cx, span, bound_path)
+        };
+
+        let this_trait_bound =
+            build::mk_trait_ty_param_bound_(cx, trait_path);
+        bounds.push(this_trait_bound);
+
+        impl_ty_params.push(build::mk_ty_param(cx, ty_param.ident, @bounds));
+    }
+
+    // Create the reference to the trait.
+    let trait_ref = build::mk_trait_ref_(cx, trait_path);
 
     // Create the type of `self`.
     let self_type = create_self_type_with_params(cx,
@@ -216,8 +236,8 @@ pub fn create_subpatterns(cx: @ext_ctxt,
     let mut subpats = ~[];
     for uint::range(0, n) |_i| {
         // Create the subidentifier.
-        let index = subpats.len().to_str();
-        let ident = cx.ident_of(prefix + index);
+        let index = subpats.len();
+        let ident = cx.ident_of(fmt!("%s_%u", prefix, index));
 
         // Create the subpattern.
         let subpath = build::mk_raw_path(span, ~[ ident ]);
@@ -287,6 +307,29 @@ pub fn variant_arg_count(_cx: @ext_ctxt, _span: span, variant: &variant) -> uint
     }
 }
 
+/// Iterate through the idents of the variant arguments. The field is
+/// unnamed (i.e. it's not a struct-like enum), then `None`.
+pub fn each_variant_arg_ident(_cx: @ext_ctxt, _span: span,
+                              variant: &variant, it: &fn(uint, Option<ident>) -> bool) {
+    match variant.node.kind {
+        tuple_variant_kind(ref args) => {
+            for uint::range(0, args.len()) |i| {
+                if !it(i, None) { break }
+            }
+        }
+        struct_variant_kind(ref struct_def) => {
+            for struct_def.fields.eachi |i, f| {
+                let id = match f.node.kind {
+                    named_field(ident, _, _) => Some(ident),
+                    unnamed_field => None
+                };
+                if !it(i, id) { break }
+            }
+        }
+    }
+}
+
+
 pub fn expand_enum_or_struct_match(cx: @ext_ctxt,
                                span: span,
                                arms: ~[ ast::arm ])