auto merge of #5640 : dbaupp/rust/syntax-generalise-deriving, r=thestinger

This refactors much of the ast generation required for `deriving` instances into a common interface, so that new instances only need to specify what they do with the actual data, rather than worry about naming function arguments and extracting fields from structs and enum. (This all happens in `generic.rs`. I've tried to make sure it was well commented and explained, since it's a little abstract at points, but I'm sure it's still a little confusing.)

It makes instances like the comparison traits and `Clone` short and easy to write.

Caveats:
- Not surprisingly, this slows the expansion pass (in some cases, dramatically, specifically deriving Ord or TotalOrd on enums with many variants).   However, this shouldn't be too concerning, since in a more realistic case (compiling `core.rc`) the time increased by 0.01s, which isn't worth mentioning. And, it possibly slows type checking very slightly (about 2% worst case), but I'm having trouble measuring it (and I don't understand why this would happen). I think this could be resolved by using traits and encoding it all in the type system so that monomorphisation handles everything, but that would probably be a little tricky to arrange nicely, reduce flexibility and make compiling rustc take longer. (Maybe some judicious use of `#[inline(always)]` would help too; I'll have a bit of a play with it.)
- The abstraction is not currently powerful enough for:
  - `IterBytes`: doesn't support arguments of type other than `&Self`.
  - `Encodable`/`Decodable` (#5090): doesn't support traits with parameters.
  - `Rand` & `FromStr`; doesn't support static functions and arguments of type other than `&Self`.
   - `ToStr`: I don't think it supports returning `~str` yet, but I haven't actually tried.

  (The last 3 are traits that might be nice to have: the derived `ToStr`/`FromStr` could just read/write the same format as `fmt!("%?", x)`, like `Show` and `Read` in Haskell.)
 
  I have ideas to resolve all of these, but I feel like it would essentially be a simpler version of the `mt` & `ty_` parts of `ast.rs`, and I'm not sure if the simplification is worth having 2 copies of similar code.

Also, makes Ord, TotalOrd and TotalEq derivable (closes #4269, #5588 and #5589), although a snapshot is required before they can be used in the rust repo.

If there is anything that is unclear (or incorrect) either here or in the code, I'd like to get it pointed out now, so I can explain/fix it while I'm still intimately familiar with the code.

16 files changed, 1608 insertions, 791 deletions

diff --git a/src/libcore/cmp.rs b/src/libcore/cmp.rs
index f96575aaf41..2c2b7f40f31 100644
--- a/src/libcore/cmp.rs
+++ b/src/libcore/cmp.rs
@@ -117,6 +117,19 @@ totalord_impl!(int)
 totalord_impl!(uint)
 
 /**
+Return `o1` if it is not `Equal`, otherwise `o2`. Simulates the
+lexical ordering on a type `(int, int)`.
+*/
+// used in deriving code in libsyntax
+#[inline(always)]
+pub fn lexical_ordering(o1: Ordering, o2: Ordering) -> Ordering {
+    match o1 {
+        Equal => o2,
+        _ => o1
+    }
+}
+
+/**
 * Trait for values that can be compared for a sort-order.
 *
 * Eventually this may be simplified to only require
@@ -184,6 +197,8 @@ pub fn max<T:Ord>(v1: T, v2: T) -> T {
 
 #[cfg(test)]
 mod test {
+    use super::lexical_ordering;
+
     #[test]
     fn test_int_totalord() {
         assert_eq!(5.cmp(&10), Less);
@@ -204,4 +219,16 @@ mod test {
         assert!(Less < Equal);
         assert_eq!(Greater.cmp(&Less), Greater);
     }
+
+    #[test]
+    fn test_lexical_ordering() {
+        fn t(o1: Ordering, o2: Ordering, e: Ordering) {
+            assert_eq!(lexical_ordering(o1, o2), e);
+        }
+        for [Less, Equal, Greater].each |&o| {
+            t(Less, o, Less);
+            t(Equal, o, o);
+            t(Greater, o, Greater);
+         }
+    }
 }
diff --git a/src/libsyntax/ext/deriving/clone.rs b/src/libsyntax/ext/deriving/clone.rs
index c8ba6b990e4..d996bca60a3 100644
--- a/src/libsyntax/ext/deriving/clone.rs
+++ b/src/libsyntax/ext/deriving/clone.rs
@@ -8,29 +8,36 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use core::prelude::*;
-
-use ast;
-use ast::*;
+use ast::{meta_item, item, expr};
+use codemap::span;
 use ext::base::ext_ctxt;
 use ext::build;
-use ext::deriving::*;
-use codemap::{span, spanned};
-use ast_util;
-use opt_vec;
+use ext::deriving::generic::*;
+use core::option::{None,Some};
 
-use core::uint;
 
 pub fn expand_deriving_clone(cx: @ext_ctxt,
                              span: span,
-                             _: @meta_item,
+                             mitem: @meta_item,
                              in_items: ~[@item])
                           -> ~[@item] {
-    expand_deriving(cx,
-                    span,
-                    in_items,
-                    expand_deriving_clone_struct_def,
-                    expand_deriving_clone_enum_def)
+    let trait_def = TraitDef {
+        path: ~[~"core", ~"clone", ~"Clone"],
+        additional_bounds: ~[],
+        methods: ~[
+            MethodDef {
+                name: ~"clone",
+                nargs: 0,
+                output_type: None, // return Self
+                const_nonmatching: false,
+                combine_substructure: cs_clone
+            }
+        ]
+    };
+
+    expand_deriving_generic(cx, span,
+                            mitem, in_items,
+                            &trait_def)
 }
 
 pub fn expand_deriving_obsolete(cx: @ext_ctxt,
@@ -42,251 +49,52 @@ pub fn expand_deriving_obsolete(cx: @ext_ctxt,
     in_items
 }
 
-fn create_derived_clone_impl(cx: @ext_ctxt,
-                             span: span,
-                             type_ident: ident,
-                             generics: &Generics,
-                             method: @method)
-                          -> @item {
-    let methods = [ method ];
-    let trait_path = ~[
-        cx.ident_of(~"core"),
-        cx.ident_of(~"clone"),
-        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)
-}
-// Creates a method from the given expression conforming to the signature of
-// the `clone` method.
-fn create_clone_method(cx: @ext_ctxt,
-                       span: span,
-                       +type_ident: ast::ident,
-                       generics: &Generics,
-                       expr: @ast::expr)
-                    -> @method {
-    // Create the type parameters of the return value.
-    let mut output_ty_params = ~[];
-    for generics.ty_params.each |ty_param| {
-        let path = build::mk_ty_path(cx, span, ~[ ty_param.ident ]);
-        output_ty_params.push(path);
-    }
-
-    // Create the type of the return value.
-    let output_type_path = build::mk_raw_path_(span,
-                                               ~[ type_ident ],
-                                               output_ty_params);
-    let output_type = ast::ty_path(output_type_path, cx.next_id());
-    let output_type = @ast::Ty {
-        id: cx.next_id(),
-        node: output_type,
-        span: span
-    };
-
-    // Create the function declaration.
-    let fn_decl = build::mk_fn_decl(~[], output_type);
-
-    // Create the body block.
-    let body_block = build::mk_simple_block(cx, span, expr);
-
-    // Create the self type and method identifier.
-    let self_ty = spanned { node: sty_region(None, m_imm), span: span };
-    let method_ident = cx.ident_of(~"clone");
-
-    // Create the method.
-    @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,
+fn cs_clone(cx: @ext_ctxt, span: span,
+            substr: &Substructure) -> @expr {
+    let clone_ident = substr.method_ident;
+    let ctor_ident;
+    let all_fields;
+    let subcall = |field|
+        build::mk_method_call(cx, span, field, clone_ident, ~[]);
+
+    match *substr.fields {
+        Struct(af) => {
+            ctor_ident = ~[ substr.type_ident ];
+            all_fields = af;
+        }
+        EnumMatching(_, variant, af) => {
+            ctor_ident = ~[ variant.node.name ];
+            all_fields = af;
+        },
+        EnumNonMatching(*) => cx.bug("Non-matching enum variants in `deriving(Clone)`")
     }
-}
-
-fn call_substructure_clone_method(cx: @ext_ctxt,
-                                  span: span,
-                                  self_field: @expr)
-                               -> @expr {
-    // Call the substructure method.
-    let clone_ident = cx.ident_of(~"clone");
-    build::mk_method_call(cx, span,
-                          self_field, clone_ident,
-                          ~[])
-}
-
-fn expand_deriving_clone_struct_def(cx: @ext_ctxt,
-                                    span: span,
-                                    struct_def: &struct_def,
-                                    type_ident: ident,
-                                    generics: &Generics)
-                                 -> @item {
-    // Create the method.
-    let method = if !is_struct_tuple(struct_def) {
-        expand_deriving_clone_struct_method(cx,
-                                            span,
-                                            struct_def,
-                                            type_ident,
-                                            generics)
-    } else {
-        expand_deriving_clone_tuple_struct_method(cx,
-                                                  span,
-                                                  struct_def,
-                                                  type_ident,
-                                                  generics)
-    };
-
-    // Create the implementation.
-    create_derived_clone_impl(cx, span, type_ident, generics, method)
-}
-
-fn expand_deriving_clone_enum_def(cx: @ext_ctxt,
-                                  span: span,
-                                  enum_definition: &enum_def,
-                                  type_ident: ident,
-                                  generics: &Generics)
-                               -> @item {
-    // Create the method.
-    let method = expand_deriving_clone_enum_method(cx,
-                                                   span,
-                                                   enum_definition,
-                                                   type_ident,
-                                                   generics);
-
-    // Create the implementation.
-    create_derived_clone_impl(cx, span, type_ident, generics, method)
-}
-
-fn expand_deriving_clone_struct_method(cx: @ext_ctxt,
-                                       span: span,
-                                       struct_def: &struct_def,
-                                       type_ident: ident,
-                                       generics: &Generics)
-                                    -> @method {
-    let self_ident = cx.ident_of(~"self");
-
-    // Create the new fields.
-    let mut fields = ~[];
-    for struct_def.fields.each |struct_field| {
-        match struct_field.node.kind {
-            named_field(ident, _, _) => {
-                // Create the accessor for this field.
-                let self_field = build::mk_access(cx,
-                                                  span,
-                                                  ~[ self_ident ],
-                                                  ident);
 
-                // Call the substructure method.
-                let call = call_substructure_clone_method(cx,
-                                                          span,
-                                                          self_field);
-
-                let field = build::Field { ident: ident, ex: call };
-                fields.push(field);
-            }
-            unnamed_field => {
-                cx.span_bug(span, ~"unnamed fields in `deriving(Clone)`");
+    match all_fields {
+        [(None, _, _), .. _] => {
+            // enum-like
+            let subcalls = all_fields.map(|&(_, self_f, _)| subcall(self_f));
+            build::mk_call(cx, span, ctor_ident, subcalls)
+        },
+        _ => {
+            // struct-like
+            let fields = do all_fields.map |&(o_id, self_f, _)| {
+                let ident = match o_id {
+                    Some(i) => i,
+                    None => cx.span_bug(span,
+                                        ~"unnamed field in normal struct \
+                                          in `deriving(Clone)`")
+                };
+                build::Field { ident: ident, ex: subcall(self_f) }
+            };
+
+            if fields.is_empty() {
+                // no fields, so construct like `None`
+                build::mk_path(cx, span, ctor_ident)
+            } else {
+                build::mk_struct_e(cx, span,
+                                   ctor_ident,
+                                   fields)
             }
         }
     }
-
-    // Create the struct literal.
-    let struct_literal = build::mk_struct_e(cx,
-                                            span,
-                                            ~[ type_ident ],
-                                            fields);
-    create_clone_method(cx, span, type_ident, generics, struct_literal)
-}
-
-fn expand_deriving_clone_tuple_struct_method(cx: @ext_ctxt,
-                                             span: span,
-                                             struct_def: &struct_def,
-                                             type_ident: ident,
-                                             generics: &Generics)
-                                          -> @method {
-    // Create the pattern for the match.
-    let matching_path = build::mk_raw_path(span, ~[ type_ident ]);
-    let field_count = struct_def.fields.len();
-    let subpats = create_subpatterns(cx, span, ~"__self", field_count);
-    let pat = build::mk_pat_enum(cx, span, matching_path, subpats);
-
-    // Create the new fields.
-    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 = build::mk_path(cx, span, ~[ field_ident ]);
-
-        // Call the substructure method.
-        let subcall = call_substructure_clone_method(cx, span, field);
-        subcalls.push(subcall);
-    }
-
-    // Create the call to the struct constructor.
-    let call = build::mk_call(cx, span, ~[ type_ident ], subcalls);
-
-    // Create the pattern body.
-    let match_body_block = build::mk_simple_block(cx, span, call);
-
-    // Create the arm.
-    let arm = ast::arm {
-        pats: ~[ pat ],
-        guard: None,
-        body: match_body_block
-    };
-
-    // Create the method body.
-    let self_match_expr = expand_enum_or_struct_match(cx, span, ~[ arm ]);
-
-    // Create the method.
-    create_clone_method(cx, span, type_ident, generics, self_match_expr)
-}
-
-fn expand_deriving_clone_enum_method(cx: @ext_ctxt,
-                                     span: span,
-                                     enum_definition: &enum_def,
-                                     type_ident: ident,
-                                     generics: &Generics)
-                                  -> @method {
-    // Create the arms of the match in the method body.
-    let arms = do enum_definition.variants.map |variant| {
-        // Create the matching pattern.
-        let pat = create_enum_variant_pattern(cx, span, variant, ~"__self");
-
-        // Iterate over the variant arguments, creating the subcalls.
-        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 = build::mk_path(cx, span, ~[ field_ident ]);
-
-            // Call the substructure method.
-            let subcall = call_substructure_clone_method(cx, span, field);
-            subcalls.push(subcall);
-        }
-
-        // Create the call to the enum variant (if necessary).
-        let call = if subcalls.len() > 0 {
-            build::mk_call(cx, span, ~[ variant.node.name ], subcalls)
-        } else {
-            build::mk_path(cx, span, ~[ variant.node.name ])
-        };
-
-        // Create the pattern body.
-        let match_body_block = build::mk_simple_block(cx, span, call);
-
-        // Create the arm.
-        ast::arm { pats: ~[ pat ], guard: None, body: match_body_block }
-    };
-
-    // Create the method body.
-    let self_match_expr = expand_enum_or_struct_match(cx, span, arms);
-
-    // Create the method.
-    create_clone_method(cx, span, type_ident, generics, self_match_expr)
 }
diff --git a/src/libsyntax/ext/deriving/cmp/eq.rs b/src/libsyntax/ext/deriving/cmp/eq.rs
new file mode 100644
index 00000000000..c0060cc67dc
--- /dev/null
+++ b/src/libsyntax/ext/deriving/cmp/eq.rs
@@ -0,0 +1,65 @@
+// 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.
+
+
+use ast::{meta_item, item, expr};
+use codemap::span;
+use ext::base::ext_ctxt;
+use ext::build;
+use ext::deriving::generic::*;
+
+use core::option::Some;
+
+pub fn expand_deriving_eq(cx: @ext_ctxt,
+                          span: span,
+                          mitem: @meta_item,
+                          in_items: ~[@item]) -> ~[@item] {
+    // structures are equal if all fields are equal, and non equal, if
+    // any fields are not equal or if the enum variants are different
+    fn cs_eq(cx: @ext_ctxt, span: span, substr: &Substructure) -> @expr {
+        cs_and(|cx, span, _| build::mk_bool(cx, span, false),
+                                 cx, span, substr)
+    }
+    fn cs_ne(cx: @ext_ctxt, span: span, substr: &Substructure) -> @expr {
+        cs_or(|cx, span, _| build::mk_bool(cx, span, true),
+              cx, span, substr)
+    }
+    macro_rules! md (
+        ($name:expr, $f:ident) => {
+            MethodDef {
+                name: $name,
+                output_type: Some(~[~"bool"]),
+                nargs: 1,
+                const_nonmatching: true,
+                combine_substructure: $f
+            },
+        }
+    )
+
+    let trait_def = TraitDef {
+        path: ~[~"core", ~"cmp", ~"Eq"],
+        additional_bounds: ~[],
+        methods: ~[
+            md!(~"eq", cs_eq),
+            md!(~"ne", cs_ne)
+        ]
+    };
+
+    expand_deriving_generic(cx, span, mitem, in_items,
+                            &trait_def)
+}
+
+pub fn expand_deriving_obsolete(cx: @ext_ctxt,
+                                span: span,
+                                _mitem: @meta_item,
+                                in_items: ~[@item]) -> ~[@item] {
+    cx.span_err(span, ~"`#[deriving_eq]` is obsolete; use `#[deriving(Eq)]` instead");
+    in_items
+}
diff --git a/src/libsyntax/ext/deriving/cmp/ord.rs b/src/libsyntax/ext/deriving/cmp/ord.rs
new file mode 100644
index 00000000000..398e27eb3e3
--- /dev/null
+++ b/src/libsyntax/ext/deriving/cmp/ord.rs
@@ -0,0 +1,128 @@
+// 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.
+
+
+use ast::{meta_item, item, expr_if, expr};
+use codemap::span;
+use ext::base::ext_ctxt;
+use ext::build;
+use ext::deriving::generic::*;
+use core::option::Some;
+
+macro_rules! md {
+    ($name:expr, $less:expr, $equal:expr) => {
+        MethodDef {
+            name: $name,
+            output_type: Some(~[~"bool"]),
+            nargs: 1,
+            const_nonmatching: false,
+            combine_substructure: |cx, span, substr|
+                    cs_ord($less, $equal, cx, span, substr)
+        }
+    }
+}
+
+pub fn expand_deriving_ord(cx: @ext_ctxt,
+                           span: span,
+                           mitem: @meta_item,
+                           in_items: ~[@item]) -> ~[@item] {
+    let trait_def = TraitDef {
+        path: ~[~"core", ~"cmp", ~"Ord"],
+        // XXX: Ord doesn't imply Eq yet
+        additional_bounds: ~[~[~"core", ~"cmp", ~"Eq"]],
+        methods: ~[
+            md!(~"lt", true,  false),
+            md!(~"le", true,  true),
+            md!(~"gt", false, false),
+            md!(~"ge", false, true)
+        ]
+    };
+
+    expand_deriving_generic(cx, span, mitem, in_items,
+                            &trait_def)
+}
+
+/// `less`: is this `lt` or `le`? `equal`: is this `le` or `ge`?
+fn cs_ord(less: bool, equal: bool,
+          cx: @ext_ctxt, span: span,
+          substr: &Substructure) -> @expr {
+    let binop = if less {
+        cx.ident_of(~"lt")
+    } else {
+        cx.ident_of(~"gt")
+    };
+    let false_blk_expr = build::mk_block(cx, span,
+                                         ~[], ~[],
+                                         Some(build::mk_bool(cx, span, false)));
+    let true_blk = build::mk_simple_block(cx, span,
+                                          build::mk_bool(cx, span, true));
+    let base = build::mk_bool(cx, span, equal);
+
+    cs_fold(
+        false, // need foldr,
+        |cx, span, subexpr, self_f, other_fs| {
+            /*
+
+            build up a series of nested ifs from the inside out to get
+            lexical ordering (hence foldr), i.e.
+
+            ```
+            if self.f1 `binop` other.f1 {
+                true
+            } else if self.f1 == other.f1 {
+                if self.f2 `binop` other.f2 {
+                    true
+                } else if self.f2 == other.f2 {
+                    `equal`
+                } else {
+                    false
+                }
+            } else {
+                false
+            }
+            ```
+
+            The inner "`equal`" case is only reached if the two
+            items have all fields equal.
+            */
+            if other_fs.len() != 1 {
+                cx.span_bug(span, "Not exactly 2 arguments in `deriving(Ord)`");
+            }
+
+            let cmp = build::mk_method_call(cx, span,
+                                            self_f, cx.ident_of(~"eq"), other_fs);
+            let subexpr = build::mk_simple_block(cx, span, subexpr);
+            let elseif = expr_if(cmp, subexpr, Some(false_blk_expr));
+            let elseif = build::mk_expr(cx, span, elseif);
+
+            let cmp = build::mk_method_call(cx, span,
+                                            self_f, binop, other_fs);
+            let if_ = expr_if(cmp, true_blk, Some(elseif));
+
+            build::mk_expr(cx, span, if_)
+        },
+        base,
+        |cx, span, args| {
+            // nonmatching enums, order by the order the variants are
+            // written
+            match args {
+                [(self_var, _, _),
+                 (other_var, _, _)] =>
+                    build::mk_bool(cx, span,
+                                   if less {
+                                       self_var < other_var
+                                   } else {
+                                       self_var > other_var
+                                   }),
+                _ => cx.span_bug(span, "Not exactly 2 arguments in `deriving(Ord)`")
+            }
+        },
+        cx, span, substr)
+}
diff --git a/src/libsyntax/ext/deriving/cmp/totaleq.rs b/src/libsyntax/ext/deriving/cmp/totaleq.rs
new file mode 100644
index 00000000000..fc8ec103a60
--- /dev/null
+++ b/src/libsyntax/ext/deriving/cmp/totaleq.rs
@@ -0,0 +1,46 @@
+// 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.
+
+
+use ast::{meta_item, item, expr};
+use codemap::span;
+use ext::base::ext_ctxt;
+use ext::build;
+use ext::deriving::generic::*;
+
+use core::option::Some;
+
+pub fn expand_deriving_totaleq(cx: @ext_ctxt,
+                          span: span,
+                          mitem: @meta_item,
+                          in_items: ~[@item]) -> ~[@item] {
+
+    fn cs_equals(cx: @ext_ctxt, span: span, substr: &Substructure) -> @expr {
+        cs_and(|cx, span, _| build::mk_bool(cx, span, false),
+               cx, span, substr)
+    }
+
+    let trait_def = TraitDef {
+        path: ~[~"core", ~"cmp", ~"TotalEq"],
+        additional_bounds: ~[],
+        methods: ~[
+            MethodDef {
+                name: ~"equals",
+                output_type: Some(~[~"bool"]),
+                nargs: 1,
+                const_nonmatching: true,
+                combine_substructure: cs_equals
+            }
+        ]
+    };
+
+    expand_deriving_generic(cx, span, mitem, in_items,
+                            &trait_def)
+}
diff --git a/src/libsyntax/ext/deriving/cmp/totalord.rs b/src/libsyntax/ext/deriving/cmp/totalord.rs
new file mode 100644
index 00000000000..a098a7463d3
--- /dev/null
+++ b/src/libsyntax/ext/deriving/cmp/totalord.rs
@@ -0,0 +1,78 @@
+// 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.
+
+use ast::{meta_item, item, expr};
+use codemap::span;
+use ext::base::ext_ctxt;
+use ext::build;
+use ext::deriving::generic::*;
+use core::cmp::{Ordering, Equal, Less, Greater};
+use core::option::Some;
+
+pub fn expand_deriving_totalord(cx: @ext_ctxt,
+                                span: span,
+                                mitem: @meta_item,
+                                in_items: ~[@item]) -> ~[@item] {
+    let trait_def = TraitDef {
+        path: ~[~"core", ~"cmp", ~"TotalOrd"],
+        additional_bounds: ~[],
+        methods: ~[
+            MethodDef {
+                name: ~"cmp",
+                output_type: Some(~[~"core", ~"cmp", ~"Ordering"]),
+                nargs: 1,
+                const_nonmatching: false,
+                combine_substructure: cs_cmp
+            }
+        ]
+    };
+
+    expand_deriving_generic(cx, span, mitem, in_items,
+                            &trait_def)
+}
+
+
+pub fn ordering_const(cx: @ext_ctxt, span: span, cnst: Ordering) -> @expr {
+    let cnst = match cnst {
+        Less => ~"Less",
+        Equal => ~"Equal",
+        Greater => ~"Greater"
+    };
+    build::mk_path_global(cx, span,
+                          ~[cx.ident_of(~"core"),
+                            cx.ident_of(~"cmp"),
+                            cx.ident_of(cnst)])
+}
+
+pub fn cs_cmp(cx: @ext_ctxt, span: span,
+              substr: &Substructure) -> @expr {
+    let lexical_ord = ~[cx.ident_of(~"core"),
+                        cx.ident_of(~"cmp"),
+                        cx.ident_of(~"lexical_ordering")];
+
+    cs_same_method_fold(
+        // foldr (possibly) nests the matches in lexical_ordering better
+        false,
+        |cx, span, old, new| {
+            build::mk_call_global(cx, span, lexical_ord, ~[old, new])
+        },
+        ordering_const(cx, span, Equal),
+        |cx, span, list| {
+            match list {
+                // an earlier nonmatching variant is Less than a
+                // later one
+                [(self_var, _, _),
+                 (other_var, _, _)] => ordering_const(cx, span,
+                                                      self_var.cmp(&other_var)),
+                _ => cx.span_bug(span, "Not exactly 2 arguments in `deriving(TotalOrd)`")
+            }
+        },
+        cx, span, substr)
+}
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
deleted file mode 100644
index c427a206c2e..00000000000
--- a/src/libsyntax/ext/deriving/eq.rs
+++ /dev/null
@@ -1,500 +0,0 @@
-// Copyright 2012-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.
-
-use core::prelude::*;
-
-use ast;
-use ast::*;
-use ext::base::ext_ctxt;
-use ext::build;
-use ext::deriving::*;
-use codemap::{span, spanned};
-use ast_util;
-use opt_vec;
-
-use core::uint;
-
-enum Junction {
-    Conjunction,
-    Disjunction,
-}
-
-pub impl Junction {
-    fn to_binop(self) -> binop {
-        match self {
-            Conjunction => and,
-            Disjunction => or,
-        }
-    }
-}
-
-pub fn expand_deriving_eq(cx: @ext_ctxt,
-                          span: span,
-                          _mitem: @meta_item,
-                          in_items: ~[@item])
-                       -> ~[@item] {
-    expand_deriving(cx,
-                    span,
-                    in_items,
-                    expand_deriving_eq_struct_def,
-                    expand_deriving_eq_enum_def)
-}
-
-pub fn expand_deriving_obsolete(cx: @ext_ctxt,
-                                span: span,
-                                _mitem: @meta_item,
-                                in_items: ~[@item])
-                             -> ~[@item] {
-    cx.span_err(span, ~"`#[deriving_eq]` is obsolete; use `#[deriving(Eq)]` instead");
-    in_items
-}
-
-/// Creates a method from the given expression, the signature of which
-/// conforms to the `eq` or `ne` method.
-fn create_eq_method(cx: @ext_ctxt,
-                    span: span,
-                    method_ident: ident,
-                    type_ident: ident,
-                    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,
-                                                     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 `other` parameter.
-    let other_ident = cx.ident_of(~"__other");
-    let arg = build::mk_arg(cx, span, other_ident, arg_type);
-
-    // Create the type of the return value.
-    let bool_ident = cx.ident_of(~"bool");
-    let output_type = build::mk_raw_path(span, ~[ bool_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,
-    };
-
-    // Create the function declaration.
-    let fn_decl = build::mk_fn_decl(~[ arg ], output_type);
-
-    // Create the body block.
-    let body_block = build::mk_simple_block(cx, span, body);
-
-    // Create the method.
-    let self_ty = spanned { node: sty_region(None, m_imm), span: span };
-    @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
-    }
-}
-
-fn create_derived_eq_impl(cx: @ext_ctxt,
-                          span: span,
-                          type_ident: ident,
-                          generics: &Generics,
-                          eq_method: @method,
-                          ne_method: @method)
-                       -> @item {
-    let methods = [ eq_method, ne_method ];
-    let trait_path = ~[
-        cx.ident_of(~"core"),
-        cx.ident_of(~"cmp"),
-        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)
-}
-
-fn call_substructure_eq_method(cx: @ext_ctxt,
-                               span: span,
-                               self_field: @expr,
-                               other_field_ref: @expr,
-                               method_ident: ident,
-                               junction: Junction,
-                               chain_expr: &mut Option<@expr>) {
-    // Call the substructure method.
-    let self_call = build::mk_method_call(cx, span,
-                                          self_field, method_ident,
-                                          ~[ other_field_ref ]);
-
-    // Connect to the outer expression if necessary.
-    *chain_expr = match *chain_expr {
-        None => Some(self_call),
-        Some(copy old_outer_expr) => {
-            let binop = junction.to_binop();
-            let chain_expr = build::mk_binary(cx,
-                                              span,
-                                              binop,
-                                              old_outer_expr,
-                                              self_call);
-            Some(chain_expr)
-        }
-    };
-}
-
-fn finish_eq_chain_expr(cx: @ext_ctxt,
-                        span: span,
-                        chain_expr: Option<@expr>,
-                        junction: Junction)
-                     -> @expr {
-    match chain_expr {
-        None => {
-            match junction {
-                Conjunction => build::mk_bool(cx, span, true),
-                Disjunction => build::mk_bool(cx, span, false),
-            }
-        }
-        Some(ref outer_expr) => *outer_expr,
-    }
-}
-
-fn expand_deriving_eq_struct_def(cx: @ext_ctxt,
-                                 span: span,
-                                 struct_def: &struct_def,
-                                 type_ident: ident,
-                                 generics: &Generics)
-                              -> @item {
-    // Create the methods.
-    let eq_ident = cx.ident_of(~"eq");
-    let ne_ident = cx.ident_of(~"ne");
-
-    let derive_struct_fn = if is_struct_tuple(struct_def) {
-        expand_deriving_eq_struct_tuple_method
-    } else {
-        expand_deriving_eq_struct_method
-    };
-
-    let eq_method = derive_struct_fn(cx,
-                                     span,
-                                     struct_def,
-                                     eq_ident,
-                                     type_ident,
-                                     generics,
-                                     Conjunction);
-    let ne_method = derive_struct_fn(cx,
-                                     span,
-                                     struct_def,
-                                     ne_ident,
-                                     type_ident,
-                                     generics,
-                                     Disjunction);
-
-    // Create the implementation.
-    return create_derived_eq_impl(cx,
-                                  span,
-                                  type_ident,
-                                  generics,
-                                  eq_method,
-                                  ne_method);
-}
-
-fn expand_deriving_eq_enum_def(cx: @ext_ctxt,
-                               span: span,
-                               enum_definition: &enum_def,
-                               type_ident: ident,
-                               generics: &Generics)
-                            -> @item {
-    // Create the methods.
-    let eq_ident = cx.ident_of(~"eq");
-    let ne_ident = cx.ident_of(~"ne");
-    let eq_method = expand_deriving_eq_enum_method(cx,
-                                                   span,
-                                                   enum_definition,
-                                                   eq_ident,
-                                                   type_ident,
-                                                   generics,
-                                                   Conjunction);
-    let ne_method = expand_deriving_eq_enum_method(cx,
-                                                   span,
-                                                   enum_definition,
-                                                   ne_ident,
-                                                   type_ident,
-                                                   generics,
-                                                   Disjunction);
-
-    // Create the implementation.
-    return create_derived_eq_impl(cx,
-                                  span,
-                                  type_ident,
-                                  generics,
-                                  eq_method,
-                                  ne_method);
-}
-
-fn expand_deriving_eq_struct_method(cx: @ext_ctxt,
-                                    span: span,
-                                    struct_def: &struct_def,
-                                    method_ident: ident,
-                                    type_ident: ident,
-                                    generics: &Generics,
-                                    junction: Junction)
-                                 -> @method {
-    let self_ident = cx.ident_of(~"self");
-    let other_ident = cx.ident_of(~"__other");
-
-    // Create the body of the method.
-    let mut outer_expr = None;
-    for struct_def.fields.each |struct_field| {
-        match struct_field.node.kind {
-            named_field(ident, _, _) => {
-                // Create the accessor for the other field.
-                let other_field = build::mk_access(cx,
-                                                   span,
-                                                   ~[ other_ident ],
-                                                   ident);
-                let other_field_ref = build::mk_addr_of(cx,
-                                                        span,
-                                                        other_field);
-
-                // Create the accessor for this field.
-                let self_field = build::mk_access(cx,
-                                                  span,
-                                                  ~[ self_ident ],
-                                                  ident);
-
-                // Call the substructure method.
-                call_substructure_eq_method(cx,
-                                            span,
-                                            self_field,
-                                            other_field_ref,
-                                            method_ident,
-                                            junction,
-                                            &mut outer_expr);
-            }
-            unnamed_field => {
-                cx.span_unimpl(span, ~"unnamed fields with `deriving(Eq)`");
-            }
-        }
-    }
-
-    // Create the method itself.
-    let body = finish_eq_chain_expr(cx, span, outer_expr, junction);
-    return create_eq_method(cx,
-                            span,
-                            method_ident,
-                            type_ident,
-                            generics,
-                            body);
-}
-
-fn expand_deriving_eq_enum_method(cx: @ext_ctxt,
-                                  span: span,
-                                  enum_definition: &enum_def,
-                                  method_ident: ident,
-                                  type_ident: ident,
-                                  generics: &Generics,
-                                  junction: Junction)
-                               -> @method {
-    let self_ident = cx.ident_of(~"self");
-    let other_ident = cx.ident_of(~"__other");
-
-    let is_eq;
-    match junction {
-        Conjunction => is_eq = true,
-        Disjunction => is_eq = false,
-    }
-
-    // Create the arms of the self match in the method body.
-    let mut self_arms = ~[];
-    for enum_definition.variants.each |self_variant| {
-        let mut other_arms = ~[];
-
-        // Create the matching pattern.
-        let matching_pat = create_enum_variant_pattern(cx,
-                                                       span,
-                                                       self_variant,
-                                                       ~"__other");
-
-        // Create the matching pattern body.
-        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 = 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 = build::mk_path(cx, span, ~[ self_field_ident ]);
-
-            // Call the substructure method.
-            call_substructure_eq_method(cx,
-                                        span,
-                                        self_field,
-                                        other_field,
-                                        method_ident,
-                                        junction,
-                                        &mut matching_body_expr);
-        }
-
-        let matching_body_expr = finish_eq_chain_expr(cx,
-                                                      span,
-                                                      matching_body_expr,
-                                                      junction);
-        let matching_body_block = build::mk_simple_block(cx,
-                                                         span,
-                                                         matching_body_expr);
-
-        // Create the matching arm.
-        let matching_arm = ast::arm {
-            pats: ~[ matching_pat ],
-            guard: None,
-            body: matching_body_block
-        };
-        other_arms.push(matching_arm);
-
-        // Maybe generate a non-matching case. If there is only one
-        // variant then there will always be a match.
-        if enum_definition.variants.len() > 1 {
-            // Create the nonmatching pattern.
-            let nonmatching_pat = @ast::pat {
-                id: cx.next_id(),
-                node: pat_wild,
-                span: span
-            };
-
-            // Create the nonmatching pattern body.
-            let nonmatching_expr = build::mk_bool(cx, span, !is_eq);
-            let nonmatching_body_block =
-                build::mk_simple_block(cx,
-                                       span,
-                                       nonmatching_expr);
-
-            // Create the nonmatching arm.
-            let nonmatching_arm = ast::arm {
-                pats: ~[ nonmatching_pat ],
-                guard: None,
-                body: nonmatching_body_block,
-            };
-            other_arms.push(nonmatching_arm);
-        }
-
-        // Create the self pattern.
-        let self_pat = create_enum_variant_pattern(cx,
-                                                   span,
-                                                   self_variant,
-                                                   ~"__self");
-
-        // Create the self pattern body.
-        let other_expr = build::mk_path(cx, span, ~[ other_ident ]);
-        let other_expr = build::mk_unary(cx, span, deref, other_expr);
-        let other_match_expr = expr_match(other_expr, other_arms);
-        let other_match_expr = build::mk_expr(cx,
-                                              span,
-                                              other_match_expr);
-        let other_match_body_block = build::mk_simple_block(cx,
-                                                            span,
-                                                            other_match_expr);
-
-        // Create the self arm.
-        let self_arm = ast::arm {
-            pats: ~[ self_pat ],
-            guard: None,
-            body: other_match_body_block,
-        };
-        self_arms.push(self_arm);
-    }
-
-    // Create the method body.
-    let self_expr = build::mk_path(cx, span, ~[ self_ident ]);
-    let self_expr = build::mk_unary(cx, span, deref, self_expr);
-    let self_match_expr = expr_match(self_expr, self_arms);
-    let self_match_expr = build::mk_expr(cx, span, self_match_expr);
-
-    // Create the method.
-    return create_eq_method(cx,
-                            span,
-                            method_ident,
-                            type_ident,
-                            generics,
-                            self_match_expr);
-}
-
-fn expand_deriving_eq_struct_tuple_method(cx: @ext_ctxt,
-                                          span: span,
-                                          struct_def: &struct_def,
-                                          method_ident: ident,
-                                          type_ident: ident,
-                                          generics: &Generics,
-                                          junction: Junction)
-                                        -> @method {
-    let self_str = ~"self";
-    let other_str = ~"__other";
-    let type_path = build::mk_raw_path(span, ~[type_ident]);
-    let fields = copy struct_def.fields;
-
-    // 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 = build::mk_path(cx, span, ~[ other_field_ident ]);
-
-        let self_field_ident = cx.ident_of(self_str + i.to_str());
-        let self_field = build::mk_path(cx, span, ~[ self_field_ident ]);
-
-        call_substructure_eq_method(cx, span, self_field, other_field,
-            method_ident, junction, &mut match_body);
-    }
-    let match_body = finish_eq_chain_expr(cx, span, match_body, junction);
-
-    // Create arm for the '__other' match, containing the comparison expr
-    let other_subpats = create_subpatterns(cx, span, other_str, fields.len());
-    let other_arm = ast::arm {
-        pats: ~[ build::mk_pat_enum(cx, span, type_path, other_subpats) ],
-        guard: None,
-        body: build::mk_simple_block(cx, span, match_body),
-    };
-
-    // Create the match on '__other'
-    let other_expr = build::mk_path(cx, span, ~[ cx.ident_of(other_str) ]);
-    let other_expr = build::mk_unary(cx, span, deref, other_expr);
-    let other_match_expr = expr_match(other_expr, ~[other_arm]);
-    let other_match_expr = build::mk_expr(cx, span, other_match_expr);
-
-    // Create arm for the 'self' match, which contains the '__other' match
-    let self_subpats = create_subpatterns(cx, span, self_str, fields.len());
-    let self_arm = ast::arm {
-        pats: ~[build::mk_pat_enum(cx, span, type_path, self_subpats)],
-        guard: None,
-        body: build::mk_simple_block(cx, span, other_match_expr),
-    };
-
-    // Create the match on 'self'
-    let self_expr = build::mk_path(cx, span, ~[ cx.ident_of(self_str) ]);
-    let self_expr = build::mk_unary(cx, span, deref, self_expr);
-    let self_match_expr = expr_match(self_expr, ~[self_arm]);
-    let self_match_expr = build::mk_expr(cx, span, self_match_expr);
-
-    create_eq_method(cx, span, method_ident,
-        type_ident, generics, self_match_expr)
-}
diff --git a/src/libsyntax/ext/deriving/generic.rs b/src/libsyntax/ext/deriving/generic.rs
new file mode 100644
index 00000000000..dfbb98fa233
--- /dev/null
+++ b/src/libsyntax/ext/deriving/generic.rs
@@ -0,0 +1,906 @@
+// 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`). If
+  `const_nonmatching` is true, this will contain an empty list.
+
+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,
+    pat_wild, 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,
+
+    /// if the value of the nonmatching enums is independent of the
+    /// actual enums, i.e. can use _ => .. match.
+    const_nonmatching: bool,
+
+    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_global(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,
+                              None, ~[], 0)
+    }
+
+
+    /**
+    Creates the nested matches for an enum definition recursively, 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.
+
+    `matching` is Some(n) if all branches in the tree above the
+    current position are variant `n`, `None` otherwise (including on
+    the first call).
+    */
+    fn build_enum_match(&self,
+                        cx: @ext_ctxt, span: span,
+                        enum_def: &enum_def,
+                        type_ident: ident,
+                        matching: Option<uint>,
+                        matches_so_far: ~[(uint, variant,
+                                           ~[(Option<ident>, @expr)])],
+                        match_count: uint) -> @expr {
+        if match_count == 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.
+
+                    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.
+                    match matching {
+                        Some(variant_index) => {
+                            // `ref` inside let matches is buggy. Causes havoc wih rusc.
+                            // let (variant_index, ref self_vec) = matches_so_far[0];
+                            let (variant, self_vec) = match matches_so_far[0] {
+                                (_, v, ref s) => (v, s)
+                            };
+
+                            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);
+                        }
+                        None => {
+                            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 match_count == 0 {
+                (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;
+
+            macro_rules! mk_arm(
+                ($pat:expr, $expr:expr) => {
+                    {
+                        let blk = build::mk_simple_block(cx, span, $expr);
+                        let arm = ast::arm {
+                            pats: ~[$ pat ],
+                            guard: None,
+                            body: blk
+                        };
+                        arm
+                    }
+                }
+            )
+
+            // the code for nonmatching variants only matters when
+            // we've seen at least one other variant already
+            if self.const_nonmatching && match_count > 0 {
+                // make a matching-variant match, and a _ match.
+                let index = match matching {
+                    Some(i) => i,
+                    None => cx.span_bug(span, ~"Non-matching variants when required to\
+                                                be matching in `deriving_generic`")
+                };
+
+                // matching-variant match
+                let variant = &enum_def.variants[index];
+                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,
+                                                     matching,
+                                                     matches_so_far,
+                                                     match_count + 1);
+                matches_so_far.pop();
+                let arm = mk_arm!(pattern, arm_expr);
+                arms.push(arm);
+
+                if enum_def.variants.len() > 1 {
+                    // _ match, if necessary
+                    let wild_pat = @ast::pat {
+                        id: cx.next_id(),
+                        node: pat_wild,
+                        span: span
+                    };
+
+                    let wild_expr = self.call_substructure_method(cx, span, type_ident,
+                                                                  &EnumNonMatching(~[]));
+                    let wild_arm = mk_arm!(wild_pat, wild_expr);
+                    arms.push(wild_arm);
+                }
+            } else {
+                // 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 new_matching =
+                        match matching {
+                            _ if match_count == 0 => Some(index),
+                            Some(i) if index == i => Some(i),
+                            _ => None
+                        };
+                    let arm_expr = self.build_enum_match(cx, span,
+                                                         enum_def,
+                                                         type_ident,
+                                                         new_matching,
+                                                         matches_so_far,
+                                                         match_count + 1);
+                    matches_so_far.pop();
+
+                    let arm = mk_arm!(pattern, arm_expr);
+                    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..78faf5556b2 100644
--- a/src/libsyntax/ext/deriving/mod.rs
+++ b/src/libsyntax/ext/deriving/mod.rs
@@ -24,30 +24,41 @@ 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 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;
+#[path="cmp/eq.rs"]
+pub mod eq;
+#[path="cmp/totaleq.rs"]
+pub mod totaleq;
+#[path="cmp/ord.rs"]
+pub mod ord;
+#[path="cmp/totalord.rs"]
+pub mod totalord;
+
+
+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,
@@ -74,14 +85,20 @@ pub fn expand_meta_deriving(cx: @ext_ctxt,
                         match *tname {
                             ~"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,
                                 titem.span, titem, in_items),
                             ~"Decodable" => decodable::expand_deriving_decodable(cx,
                                 titem.span, titem, in_items),
+                            ~"Eq" => eq::expand_deriving_eq(cx, titem.span,
+                                                             titem, in_items),
+                            ~"TotalEq" => totaleq::expand_deriving_totaleq(cx, titem.span,
+                                                                           titem, in_items),
+                            ~"Ord" => ord::expand_deriving_ord(cx, titem.span,
+                                                               titem, in_items),
+                            ~"TotalOrd" => totalord::expand_deriving_totalord(cx, titem.span,
+                                                                              titem, in_items),
                             tname => {
                                 cx.span_err(titem.span, fmt!("unknown \
                                     `deriving` trait: `%s`", tname));
@@ -126,9 +143,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 +191,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 +212,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 +251,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 +322,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 ])
diff --git a/src/test/run-pass/deriving-cmp-generic-enum.rs b/src/test/run-pass/deriving-cmp-generic-enum.rs
new file mode 100644
index 00000000000..a2651ddac3d
--- /dev/null
+++ b/src/test/run-pass/deriving-cmp-generic-enum.rs
@@ -0,0 +1,50 @@
+// 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.
+
+#[deriving(Eq, TotalEq, Ord, TotalOrd)]
+enum E<T> {
+    E0,
+    E1(T),
+    E2(T,T)
+}
+
+pub fn main() {
+    let e0 = E0, e11 = E1(1), e12 = E1(2), e21 = E2(1,1), e22 = E2(1, 2);
+
+    // in order for both Ord and TotalOrd
+    let es = [e0, e11, e12, e21, e22];
+
+    for es.eachi |i, e1| {
+        for es.eachi |j, e2| {
+            let ord = i.cmp(&j);
+
+            let eq = i == j;
+            let lt = i < j, le = i <= j;
+            let gt = i > j, ge = i >= j;
+
+            // Eq
+            assert_eq!(*e1 == *e2, eq);
+            assert_eq!(*e1 != *e2, !eq);
+
+            // TotalEq
+            assert_eq!(e1.equals(e2), eq);
+
+            // Ord
+            assert_eq!(*e1 < *e2, lt);
+            assert_eq!(*e1 > *e2, gt);
+
+            assert_eq!(*e1 <= *e2, le);
+            assert_eq!(*e1 >= *e2, ge);
+
+            // TotalOrd
+            assert_eq!(e1.cmp(e2), ord);
+        }
+    }
+}
diff --git a/src/test/run-pass/deriving-cmp-generic-struct-enum.rs b/src/test/run-pass/deriving-cmp-generic-struct-enum.rs
new file mode 100644
index 00000000000..6f6e8d79d8b
--- /dev/null
+++ b/src/test/run-pass/deriving-cmp-generic-struct-enum.rs
@@ -0,0 +1,52 @@
+// xfail-test #5530
+
+// 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.
+
+#[deriving(Eq, TotalEq, Ord, TotalOrd)]
+enum ES<T> {
+    ES1 { x: T },
+    ES2 { x: T, y: T }
+}
+
+
+pub fn main() {
+    let es11 = ES1 {x: 1}, es12 = ES1 {x: 2}, es21 = ES2 {x: 1, y: 1}, es22 = ES2 {x: 1, y: 2};
+
+    // in order for both Ord and TotalOrd
+    let ess = [es11, es12, es21, es22];
+
+    for ess.eachi |i, es1| {
+        for ess.eachi |j, es2| {
+            let ord = i.cmp(&j);
+
+            let eq = i == j;
+            let lt = i < j, le = i <= j;
+            let gt = i > j, ge = i >= j;
+
+            // Eq
+            assert_eq!(*es1 == *es2, eq);
+            assert_eq!(*es1 != *es2, !eq);
+
+            // TotalEq
+            assert_eq!(es1.equals(es2), eq);
+
+            // Ord
+            assert_eq!(*es1 < *es2, lt);
+            assert_eq!(*es1 > *es2, gt);
+
+            assert_eq!(*es1 <= *es2, le);
+            assert_eq!(*es1 >= *es2, ge);
+
+            // TotalOrd
+            assert_eq!(es1.cmp(es2), ord);
+        }
+    }
+}
\ No newline at end of file
diff --git a/src/test/run-pass/deriving-cmp-generic-struct.rs b/src/test/run-pass/deriving-cmp-generic-struct.rs
new file mode 100644
index 00000000000..bd3e02ba29b
--- /dev/null
+++ b/src/test/run-pass/deriving-cmp-generic-struct.rs
@@ -0,0 +1,49 @@
+// 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.
+
+#[deriving(Eq, TotalEq, Ord, TotalOrd)]
+struct S<T> {
+    x: T,
+    y: T
+}
+
+pub fn main() {
+    let s1 = S {x: 1, y: 1}, s2 = S {x: 1, y: 2};
+
+    // in order for both Ord and TotalOrd
+    let ss = [s1, s2];
+
+    for ss.eachi |i, s1| {
+        for ss.eachi |j, s2| {
+            let ord = i.cmp(&j);
+
+            let eq = i == j;
+            let lt = i < j, le = i <= j;
+            let gt = i > j, ge = i >= j;
+
+            // Eq
+            assert_eq!(*s1 == *s2, eq);
+            assert_eq!(*s1 != *s2, !eq);
+
+            // TotalEq
+            assert_eq!(s1.equals(s2), eq);
+
+            // Ord
+            assert_eq!(*s1 < *s2, lt);
+            assert_eq!(*s1 > *s2, gt);
+
+            assert_eq!(*s1 <= *s2, le);
+            assert_eq!(*s1 >= *s2, ge);
+
+            // TotalOrd
+            assert_eq!(s1.cmp(s2), ord);
+        }
+    }
+}
\ No newline at end of file
diff --git a/src/test/run-pass/deriving-cmp-generic-tuple-struct.rs b/src/test/run-pass/deriving-cmp-generic-tuple-struct.rs
new file mode 100644
index 00000000000..733b19a9ae2
--- /dev/null
+++ b/src/test/run-pass/deriving-cmp-generic-tuple-struct.rs
@@ -0,0 +1,47 @@
+// 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.
+
+#[deriving(Eq, TotalEq, Ord, TotalOrd)]
+struct TS<T>(T,T);
+
+
+pub fn main() {
+    let ts1 = TS(1, 1), ts2 = TS(1,2);
+
+    // in order for both Ord and TotalOrd
+    let tss = [ts1, ts2];
+
+    for tss.eachi |i, ts1| {
+        for tss.eachi |j, ts2| {
+            let ord = i.cmp(&j);
+
+            let eq = i == j;
+            let lt = i < j, le = i <= j;
+            let gt = i > j, ge = i >= j;
+
+            // Eq
+            assert_eq!(*ts1 == *ts2, eq);
+            assert_eq!(*ts1 != *ts2, !eq);
+
+            // TotalEq
+            assert_eq!(ts1.equals(ts2), eq);
+
+            // Ord
+            assert_eq!(*ts1 < *ts2, lt);
+            assert_eq!(*ts1 > *ts2, gt);
+
+            assert_eq!(*ts1 <= *ts2, le);
+            assert_eq!(*ts1 >= *ts2, ge);
+
+            // TotalOrd
+            assert_eq!(ts1.cmp(ts2), ord);
+        }
+    }
+}
\ No newline at end of file