Improve derived implementations for enums with lots of fieldless variants

A number of trait methods like PartialEq::eq or Hash::hash don't
actually need a distinct arm for each variant, because the code within
the arm only depends on the number and types of the fields in the
variants. We can easily exploit this fact to create less and better
code for enums with multiple variants that have no fields at all, the
extreme case being C-like enums.

For nickel.rs and its by now infamous 800 variant enum, this reduces
optimized compile times by 25% and non-optimized compile times by 40%.
Also peak memory usage is down by almost 40% (310MB down to 190MB).

To be fair, most other crates don't benefit nearly as much, because
they don't have as huge enums. The crates in the Rust distribution that
I measured saw basically no change in compile times (I only tried
optimized builds) and only 1-2% reduction in peak memory usage.

13 files changed, 44 insertions, 7 deletions

diff --git a/src/libsyntax_ext/deriving/clone.rs b/src/libsyntax_ext/deriving/clone.rs
index 2c21fd2cd5e..30fe0f2db8a 100644
--- a/src/libsyntax_ext/deriving/clone.rs
+++ b/src/libsyntax_ext/deriving/clone.rs
@@ -39,6 +39,7 @@ pub fn expand_deriving_clone(cx: &mut ExtCtxt,
     //      Clone + Copy, and then there'd be no Clone impl at all if the user fills in something
     //      that is Clone but not Copy. and until specialization we can't write both impls.
     let bounds;
+    let unify_fieldless_variants;
     let substructure;
     match *item {
         Annotatable::Item(ref annitem) => {
@@ -49,6 +50,7 @@ pub fn expand_deriving_clone(cx: &mut ExtCtxt,
                         && attr::contains_name(&annitem.attrs, "derive_Copy") => {
 
                     bounds = vec![Literal(path_std!(cx, core::marker::Copy))];
+                    unify_fieldless_variants = true;
                     substructure = combine_substructure(Box::new(|c, s, sub| {
                         cs_clone("Clone", c, s, sub, Mode::Shallow)
                     }));
@@ -56,6 +58,7 @@ pub fn expand_deriving_clone(cx: &mut ExtCtxt,
 
                 _ => {
                     bounds = vec![];
+                    unify_fieldless_variants = false;
                     substructure = combine_substructure(Box::new(|c, s, sub| {
                         cs_clone("Clone", c, s, sub, Mode::Deep)
                     }));
@@ -84,6 +87,7 @@ pub fn expand_deriving_clone(cx: &mut ExtCtxt,
                 ret_ty: Self_,
                 attributes: attrs,
                 is_unsafe: false,
+                unify_fieldless_variants: unify_fieldless_variants,
                 combine_substructure: substructure,
             }
         ),
diff --git a/src/libsyntax_ext/deriving/cmp/eq.rs b/src/libsyntax_ext/deriving/cmp/eq.rs
index 1b855c56a48..8bd12c39337 100644
--- a/src/libsyntax_ext/deriving/cmp/eq.rs
+++ b/src/libsyntax_ext/deriving/cmp/eq.rs
@@ -62,6 +62,7 @@ pub fn expand_deriving_eq(cx: &mut ExtCtxt,
                 ret_ty: nil_ty(),
                 attributes: attrs,
                 is_unsafe: false,
+                unify_fieldless_variants: true,
                 combine_substructure: combine_substructure(Box::new(|a, b, c| {
                     cs_total_eq_assert(a, b, c)
                 }))
diff --git a/src/libsyntax_ext/deriving/cmp/ord.rs b/src/libsyntax_ext/deriving/cmp/ord.rs
index 74706c47087..6133adb8fc5 100644
--- a/src/libsyntax_ext/deriving/cmp/ord.rs
+++ b/src/libsyntax_ext/deriving/cmp/ord.rs
@@ -42,6 +42,7 @@ pub fn expand_deriving_ord(cx: &mut ExtCtxt,
                 ret_ty: Literal(path_std!(cx, core::cmp::Ordering)),
                 attributes: attrs,
                 is_unsafe: false,
+                unify_fieldless_variants: true,
                 combine_substructure: combine_substructure(Box::new(|a, b, c| {
                     cs_cmp(a, b, c)
                 })),
diff --git a/src/libsyntax_ext/deriving/cmp/partial_eq.rs b/src/libsyntax_ext/deriving/cmp/partial_eq.rs
index 6406ee59a5e..e5890d7213b 100644
--- a/src/libsyntax_ext/deriving/cmp/partial_eq.rs
+++ b/src/libsyntax_ext/deriving/cmp/partial_eq.rs
@@ -73,6 +73,7 @@ pub fn expand_deriving_partial_eq(cx: &mut ExtCtxt,
                 ret_ty: Literal(path_local!(bool)),
                 attributes: attrs,
                 is_unsafe: false,
+                unify_fieldless_variants: true,
                 combine_substructure: combine_substructure(Box::new(|a, b, c| {
                     $f(a, b, c)
                 }))
diff --git a/src/libsyntax_ext/deriving/cmp/partial_ord.rs b/src/libsyntax_ext/deriving/cmp/partial_ord.rs
index e49c77285ab..cfc6dbe5cd0 100644
--- a/src/libsyntax_ext/deriving/cmp/partial_ord.rs
+++ b/src/libsyntax_ext/deriving/cmp/partial_ord.rs
@@ -38,6 +38,7 @@ pub fn expand_deriving_partial_ord(cx: &mut ExtCtxt,
                 ret_ty: Literal(path_local!(bool)),
                 attributes: attrs,
                 is_unsafe: false,
+                unify_fieldless_variants: true,
                 combine_substructure: combine_substructure(Box::new(|cx, span, substr| {
                     cs_op($op, $equal, cx, span, substr)
                 }))
@@ -62,6 +63,7 @@ pub fn expand_deriving_partial_ord(cx: &mut ExtCtxt,
         ret_ty: ret_ty,
         attributes: attrs,
         is_unsafe: false,
+        unify_fieldless_variants: true,
         combine_substructure: combine_substructure(Box::new(|cx, span, substr| {
             cs_partial_cmp(cx, span, substr)
         }))
diff --git a/src/libsyntax_ext/deriving/debug.rs b/src/libsyntax_ext/deriving/debug.rs
index 323c6c388fb..d86eae820a8 100644
--- a/src/libsyntax_ext/deriving/debug.rs
+++ b/src/libsyntax_ext/deriving/debug.rs
@@ -45,6 +45,7 @@ pub fn expand_deriving_debug(cx: &mut ExtCtxt,
                 ret_ty: Literal(path_std!(cx, core::fmt::Result)),
                 attributes: Vec::new(),
                 is_unsafe: false,
+                unify_fieldless_variants: false,
                 combine_substructure: combine_substructure(Box::new(|a, b, c| {
                     show_substructure(a, b, c)
                 }))
diff --git a/src/libsyntax_ext/deriving/decodable.rs b/src/libsyntax_ext/deriving/decodable.rs
index 9387cf05ac7..04888d046ad 100644
--- a/src/libsyntax_ext/deriving/decodable.rs
+++ b/src/libsyntax_ext/deriving/decodable.rs
@@ -85,6 +85,7 @@ fn expand_deriving_decodable_imp(cx: &mut ExtCtxt,
                 )),
                 attributes: Vec::new(),
                 is_unsafe: false,
+                unify_fieldless_variants: false,
                 combine_substructure: combine_substructure(Box::new(|a, b, c| {
                     decodable_substructure(a, b, c, krate)
                 })),
diff --git a/src/libsyntax_ext/deriving/default.rs b/src/libsyntax_ext/deriving/default.rs
index bee63a98c25..a6a4830fab7 100644
--- a/src/libsyntax_ext/deriving/default.rs
+++ b/src/libsyntax_ext/deriving/default.rs
@@ -42,6 +42,7 @@ pub fn expand_deriving_default(cx: &mut ExtCtxt,
                 ret_ty: Self_,
                 attributes: attrs,
                 is_unsafe: false,
+                unify_fieldless_variants: false,
                 combine_substructure: combine_substructure(Box::new(|a, b, c| {
                     default_substructure(a, b, c)
                 }))
diff --git a/src/libsyntax_ext/deriving/encodable.rs b/src/libsyntax_ext/deriving/encodable.rs
index 5b47d8da8b6..66672305829 100644
--- a/src/libsyntax_ext/deriving/encodable.rs
+++ b/src/libsyntax_ext/deriving/encodable.rs
@@ -161,6 +161,7 @@ fn expand_deriving_encodable_imp(cx: &mut ExtCtxt,
                 )),
                 attributes: Vec::new(),
                 is_unsafe: false,
+                unify_fieldless_variants: false,
                 combine_substructure: combine_substructure(Box::new(|a, b, c| {
                     encodable_substructure(a, b, c, krate)
                 })),
diff --git a/src/libsyntax_ext/deriving/generic/mod.rs b/src/libsyntax_ext/deriving/generic/mod.rs
index 1d5fc13c720..45029c8eb94 100644
--- a/src/libsyntax_ext/deriving/generic/mod.rs
+++ b/src/libsyntax_ext/deriving/generic/mod.rs
@@ -257,6 +257,9 @@ pub struct MethodDef<'a> {
     // Is it an `unsafe fn`?
     pub is_unsafe: bool,
 
+    /// Can we combine fieldless variants for enums into a single match arm?
+    pub unify_fieldless_variants: bool,
+
     pub combine_substructure: RefCell<CombineSubstructureFunc<'a>>,
 }
 
@@ -1131,12 +1134,15 @@ impl<'a> MethodDef<'a> {
         let catch_all_substructure = EnumNonMatchingCollapsed(
             self_arg_idents, &variants[..], &vi_idents[..]);
 
+        let first_fieldless = variants.iter().find(|v| v.node.data.fields().is_empty());
+
         // These arms are of the form:
         // (Variant1, Variant1, ...) => Body1
         // (Variant2, Variant2, ...) => Body2
         // ...
         // where each tuple has length = self_args.len()
         let mut match_arms: Vec<ast::Arm> = variants.iter().enumerate()
+            .filter(|&(_, v)| !(self.unify_fieldless_variants && v.node.data.fields().is_empty()))
             .map(|(index, variant)| {
                 let mk_self_pat = |cx: &mut ExtCtxt, self_arg_name: &str| {
                     let (p, idents) = trait_.create_enum_variant_pattern(
@@ -1219,6 +1225,28 @@ impl<'a> MethodDef<'a> {
 
                 cx.arm(sp, vec![single_pat], arm_expr)
             }).collect();
+
+        let default = match first_fieldless {
+            Some(v) if self.unify_fieldless_variants => {
+                // We need a default case that handles the fieldless variants.
+                // The index and actual variant aren't meaningful in this case,
+                // so just use whatever
+                Some(self.call_substructure_method(
+                    cx, trait_, type_ident, &self_args[..], nonself_args,
+                    &EnumMatching(0, v, Vec::new())))
+            }
+            _ if variants.len() > 1 && self_args.len() > 1 => {
+                // Since we know that all the arguments will match if we reach
+                // the match expression we add the unreachable intrinsics as the
+                // result of the catch all which should help llvm in optimizing it
+                Some(deriving::call_intrinsic(cx, sp, "unreachable", vec![]))
+            }
+            _ => None
+        };
+        if let Some(arm) = default {
+            match_arms.push(cx.arm(sp, vec![cx.pat_wild(sp)], arm));
+        }
+
         // We will usually need the catch-all after matching the
         // tuples `(VariantK, VariantK, ...)` for each VariantK of the
         // enum.  But:
@@ -1292,13 +1320,6 @@ impl<'a> MethodDef<'a> {
                 cx, trait_, type_ident, &self_args[..], nonself_args,
                 &catch_all_substructure);
 
-            //Since we know that all the arguments will match if we reach the match expression we
-            //add the unreachable intrinsics as the result of the catch all which should help llvm
-            //in optimizing it
-            match_arms.push(cx.arm(sp,
-                                   vec![cx.pat_wild(sp)],
-                                   deriving::call_intrinsic(cx, sp, "unreachable", vec![])));
-
             // Final wrinkle: the self_args are expressions that deref
             // down to desired l-values, but we cannot actually deref
             // them when they are fed as r-values into a tuple
diff --git a/src/libsyntax_ext/deriving/hash.rs b/src/libsyntax_ext/deriving/hash.rs
index c37ae116d37..fd449372cb3 100644
--- a/src/libsyntax_ext/deriving/hash.rs
+++ b/src/libsyntax_ext/deriving/hash.rs
@@ -51,6 +51,7 @@ pub fn expand_deriving_hash(cx: &mut ExtCtxt,
                 ret_ty: nil_ty(),
                 attributes: vec![],
                 is_unsafe: false,
+                unify_fieldless_variants: true,
                 combine_substructure: combine_substructure(Box::new(|a, b, c| {
                     hash_substructure(a, b, c)
                 }))
diff --git a/src/test/run-pass-fulldeps/auxiliary/custom_derive_plugin.rs b/src/test/run-pass-fulldeps/auxiliary/custom_derive_plugin.rs
index 5f0ef4de491..0132014de0a 100644
--- a/src/test/run-pass-fulldeps/auxiliary/custom_derive_plugin.rs
+++ b/src/test/run-pass-fulldeps/auxiliary/custom_derive_plugin.rs
@@ -58,6 +58,7 @@ fn expand(cx: &mut ExtCtxt,
                 ret_ty: Literal(Path::new_local("isize")),
                 attributes: vec![],
                 is_unsafe: false,
+                unify_fieldless_variants: true,
                 combine_substructure: combine_substructure(box |cx, span, substr| {
                     let zero = cx.expr_isize(span, 0);
                     cs_fold(false,
diff --git a/src/test/run-pass-fulldeps/auxiliary/custom_derive_plugin_attr.rs b/src/test/run-pass-fulldeps/auxiliary/custom_derive_plugin_attr.rs
index 2878674f0ea..6fa78913839 100644
--- a/src/test/run-pass-fulldeps/auxiliary/custom_derive_plugin_attr.rs
+++ b/src/test/run-pass-fulldeps/auxiliary/custom_derive_plugin_attr.rs
@@ -60,6 +60,7 @@ fn expand(cx: &mut ExtCtxt,
                 ret_ty: Literal(Path::new_local("isize")),
                 attributes: vec![],
                 is_unsafe: false,
+                unify_fieldless_variants: true,
                 combine_substructure: combine_substructure(Box::new(totalsum_substructure)),
             },
         ],