`O(n*k)` code-size deriving on enums (better than previous `O(n^k)`).

In the above formulas, `n` is the number of variants, and `k` is the
number of self-args fed into deriving.  In the particular case of
interest (namely `PartialOrd` and `Ord`), `k` is always 2, so we are
basically comparing `O(n)` versus `O(n^2)`.

Also, the stage is set for having *all* enum deriving codes go through
`build_enum_match_tuple` and getting rid of `build_enum_match`.

Also, seriously attempted to clean up the code itself.  Added a bunch
of comments attempting to document what I learned as I worked through
the original code and adapted it to this new strategy.

4 files changed, 59 insertions, 5 deletions

diff --git a/src/libsyntax/ext/deriving/cmp/eq.rs b/src/libsyntax/ext/deriving/cmp/eq.rs
index 2eaeb0df7fb..3c7f82a315a 100644
--- a/src/libsyntax/ext/deriving/cmp/eq.rs
+++ b/src/libsyntax/ext/deriving/cmp/eq.rs
@@ -27,10 +27,12 @@ pub fn expand_deriving_eq(cx: &mut ExtCtxt,
     // any fields are not equal or if the enum variants are different
     fn cs_eq(cx: &mut ExtCtxt, span: Span, substr: &Substructure) -> Gc<Expr> {
         cs_and(|cx, span, _, _| cx.expr_bool(span, false),
-                                 cx, span, substr)
+               |cx, span, _, _| cx.expr_bool(span, false),
+               cx, span, substr)
     }
     fn cs_ne(cx: &mut ExtCtxt, span: Span, substr: &Substructure) -> Gc<Expr> {
         cs_or(|cx, span, _, _| cx.expr_bool(span, true),
+              |cx, span, _, _| cx.expr_bool(span, true),
               cx, span, substr)
     }
 
diff --git a/src/libsyntax/ext/deriving/cmp/ord.rs b/src/libsyntax/ext/deriving/cmp/ord.rs
index c8edf5c4157..52a180deffb 100644
--- a/src/libsyntax/ext/deriving/cmp/ord.rs
+++ b/src/libsyntax/ext/deriving/cmp/ord.rs
@@ -35,7 +35,7 @@ pub fn expand_deriving_ord(cx: &mut ExtCtxt,
                 args: vec!(borrowed_self()),
                 ret_ty: Literal(Path::new(vec!("bool"))),
                 attributes: attrs,
-                on_nonmatching: NonMatchesExplode,
+                on_nonmatching: NonMatchesCollapseWithTags,
                 combine_substructure: combine_substructure(|cx, span, substr| {
                     cs_op($op, $equal, cx, span, substr)
                 })
@@ -59,7 +59,7 @@ pub fn expand_deriving_ord(cx: &mut ExtCtxt,
         args: vec![borrowed_self()],
         ret_ty: ret_ty,
         attributes: attrs,
-        on_nonmatching: NonMatchesExplode,
+        on_nonmatching: NonMatchesCollapseWithTags,
         combine_substructure: combine_substructure(|cx, span, substr| {
             cs_partial_cmp(cx, span, substr)
         })
@@ -96,6 +96,24 @@ pub fn some_ordering_const(cx: &mut ExtCtxt, span: Span, cnst: Ordering) -> Gc<a
     cx.expr_some(span, ordering)
 }
 
+pub enum OrderingOp {
+    PartialCmpOp, LtOp, LeOp, GtOp, GeOp,
+}
+
+pub fn some_ordering_collapsed(cx: &mut ExtCtxt,
+                               span: Span,
+                               op: OrderingOp,
+                               self_arg_tags: &[ast::Ident]) -> Gc<ast::Expr> {
+    let lft = cx.expr_ident(span, self_arg_tags[0]);
+    let rgt = cx.expr_addr_of(span, cx.expr_ident(span, self_arg_tags[1]));
+    let op_str = match op {
+        PartialCmpOp => "partial_cmp",
+        LtOp => "lt", LeOp => "le",
+        GtOp => "gt", GeOp => "ge",
+    };
+    cx.expr_method_call(span, lft, cx.ident_of(op_str), vec![rgt])
+}
+
 pub fn cs_partial_cmp(cx: &mut ExtCtxt, span: Span,
               substr: &Substructure) -> Gc<Expr> {
     let test_id = cx.ident_of("__test");
@@ -147,7 +165,14 @@ pub fn cs_partial_cmp(cx: &mut ExtCtxt, span: Span,
                 // later one.
                 [(self_var, _, _), (other_var, _, _)] =>
                      some_ordering_const(cx, span, self_var.cmp(&other_var)),
-                _ => cx.span_bug(span, "not exactly 2 arguments in `deriving(Ord)`")
+                _ => cx.span_bug(span, "not exactly 2 arguments in `deriving(Ord)`"),
+            }
+        },
+        |cx, span, (self_args, tag_tuple), _non_self_args| {
+            if self_args.len() != 2 {
+                cx.span_bug(span, "not exactly 2 arguments in `deriving(Ord)`")
+            } else {
+                some_ordering_collapsed(cx, span, PartialCmpOp, tag_tuple)
             }
         },
         cx, span, substr)
@@ -206,5 +231,16 @@ fn cs_op(less: bool, equal: bool, cx: &mut ExtCtxt, span: Span,
                 _ => cx.span_bug(span, "not exactly 2 arguments in `deriving(Ord)`")
             }
         },
+        |cx, span, (self_args, tag_tuple), _non_self_args| {
+            if self_args.len() != 2 {
+                cx.span_bug(span, "not exactly 2 arguments in `deriving(Ord)`")
+            } else {
+                let op = match (less, equal) {
+                    (true,  true) => LeOp, (true,  false) => LtOp,
+                    (false, true) => GeOp, (false, false) => GtOp,
+                };
+                some_ordering_collapsed(cx, span, op, tag_tuple)
+            }
+        },
         cx, span, substr)
 }
diff --git a/src/libsyntax/ext/deriving/cmp/totaleq.rs b/src/libsyntax/ext/deriving/cmp/totaleq.rs
index 09aa24f9bfb..3a6b1fa218a 100644
--- a/src/libsyntax/ext/deriving/cmp/totaleq.rs
+++ b/src/libsyntax/ext/deriving/cmp/totaleq.rs
@@ -33,6 +33,7 @@ pub fn expand_deriving_totaleq(cx: &mut ExtCtxt,
             cx.expr_block(block)
         },
                        |cx, sp, _, _| cx.span_bug(sp, "non matching enums in deriving(Eq)?"),
+                       |cx, sp, _, _| cx.span_bug(sp, "non matching enums in deriving(Eq)?"),
                        cx,
                        span,
                        substr)
diff --git a/src/libsyntax/ext/deriving/cmp/totalord.rs b/src/libsyntax/ext/deriving/cmp/totalord.rs
index 24785a026d1..0e4b786857b 100644
--- a/src/libsyntax/ext/deriving/cmp/totalord.rs
+++ b/src/libsyntax/ext/deriving/cmp/totalord.rs
@@ -41,7 +41,7 @@ pub fn expand_deriving_totalord(cx: &mut ExtCtxt,
                 args: vec!(borrowed_self()),
                 ret_ty: Literal(Path::new(vec!("std", "cmp", "Ordering"))),
                 attributes: attrs,
-                on_nonmatching: NonMatchesExplode,
+                on_nonmatching: NonMatchesCollapseWithTags,
                 combine_substructure: combine_substructure(|a, b, c| {
                     cs_cmp(a, b, c)
                 }),
@@ -65,6 +65,14 @@ pub fn ordering_const(cx: &mut ExtCtxt, span: Span, cnst: Ordering) -> ast::Path
                      cx.ident_of(cnst)))
 }
 
+pub fn ordering_collapsed(cx: &mut ExtCtxt,
+                          span: Span,
+                          self_arg_tags: &[ast::Ident]) -> Gc<ast::Expr> {
+    let lft = cx.expr_ident(span, self_arg_tags[0]);
+    let rgt = cx.expr_addr_of(span, cx.expr_ident(span, self_arg_tags[1]));
+    cx.expr_method_call(span, lft, cx.ident_of("cmp"), vec![rgt])
+}
+
 pub fn cs_cmp(cx: &mut ExtCtxt, span: Span,
               substr: &Substructure) -> Gc<Expr> {
     let test_id = cx.ident_of("__test");
@@ -122,5 +130,12 @@ pub fn cs_cmp(cx: &mut ExtCtxt, span: Span,
                 _ => cx.span_bug(span, "not exactly 2 arguments in `deriving(Ord)`")
             }
         },
+        |cx, span, (self_args, tag_tuple), _non_self_args| {
+            if self_args.len() != 2 {
+                cx.span_bug(span, "not exactly 2 arguments in `deriving(TotalOrd)`")
+            } else {
+                ordering_collapsed(cx, span, tag_tuple)
+            }
+        },
         cx, span, substr)
 }