Auto merge of #49881 - varkor:partialord-opt, r=Manishearth

Fix derive(PartialOrd) and optimise final field operation

```rust
// Before (`lt` on 2-field struct)
self.f1 < other.f1 || (!(other.f1 < self.f1) &&
(self.f2 < other.f2 || (!(other.f2 < self.f2) &&
(false)
))
)

// After
self.f1 < other.f1 || (!(other.f1 < self.f1) &&
self.f2 < other.f2
)

// Before (`le` on 2-field struct)
self.f1 < other.f1 || (!(other.f1 < self.f1) &&
(self.f2 < other.f2 || (!(other.f2 < self.f2) &&
(true)
))
)

// After
self.f1 < other.f1 || (self.f1 == other.f1 &&
self.f2 <= other.f2
)
```

(The big diff is mainly because of a past faulty rustfmt application that I corrected 😒)

Fixes #49650 and fixes #49505.

1 files changed, 99 insertions, 17 deletions

diff --git a/src/libsyntax_ext/deriving/generic/mod.rs b/src/libsyntax_ext/deriving/generic/mod.rs
index 66053e037e1..1f80385cfbd 100644
--- a/src/libsyntax_ext/deriving/generic/mod.rs
+++ b/src/libsyntax_ext/deriving/generic/mod.rs
@@ -1680,12 +1680,55 @@ impl<'a> TraitDef<'a> {
 
 // helpful premade recipes
 
+pub fn cs_fold_fields<'a, F>(use_foldl: bool,
+                             mut f: F,
+                             base: P<Expr>,
+                             cx: &mut ExtCtxt,
+                             all_fields: &[FieldInfo<'a>])
+                             -> P<Expr>
+    where F: FnMut(&mut ExtCtxt, Span, P<Expr>, P<Expr>, &[P<Expr>]) -> P<Expr>
+{
+    if use_foldl {
+        all_fields.iter().fold(base, |old, field| {
+            f(cx, field.span, old, field.self_.clone(), &field.other)
+        })
+    } else {
+        all_fields.iter().rev().fold(base, |old, field| {
+            f(cx, field.span, old, field.self_.clone(), &field.other)
+        })
+    }
+}
+
+pub fn cs_fold_enumnonmatch(mut enum_nonmatch_f: EnumNonMatchCollapsedFunc,
+                            cx: &mut ExtCtxt,
+                            trait_span: Span,
+                            substructure: &Substructure)
+                            -> P<Expr>
+{
+    match *substructure.fields {
+        EnumNonMatchingCollapsed(ref all_args, _, tuple) => {
+            enum_nonmatch_f(cx,
+                            trait_span,
+                            (&all_args[..], tuple),
+                            substructure.nonself_args)
+        }
+        _ => cx.span_bug(trait_span, "cs_fold_enumnonmatch expected an EnumNonMatchingCollapsed")
+    }
+}
+
+pub fn cs_fold_static(cx: &mut ExtCtxt,
+                      trait_span: Span)
+                      -> P<Expr>
+{
+    cx.span_bug(trait_span, "static function in `derive`")
+}
+
 /// Fold the fields. `use_foldl` controls whether this is done
 /// left-to-right (`true`) or right-to-left (`false`).
 pub fn cs_fold<F>(use_foldl: bool,
-                  mut f: F,
+                  f: F,
                   base: P<Expr>,
-                  mut enum_nonmatch_f: EnumNonMatchCollapsedFunc,
+                  enum_nonmatch_f: EnumNonMatchCollapsedFunc,
                   cx: &mut ExtCtxt,
                   trait_span: Span,
                   substructure: &Substructure)
@@ -1695,26 +1738,65 @@ pub fn cs_fold<F>(use_foldl: bool,
     match *substructure.fields {
         EnumMatching(.., ref all_fields) |
         Struct(_, ref all_fields) => {
-            if use_foldl {
-                all_fields.iter().fold(base, |old, field| {
-                    f(cx, field.span, old, field.self_.clone(), &field.other)
-                })
-            } else {
-                all_fields.iter().rev().fold(base, |old, field| {
-                    f(cx, field.span, old, field.self_.clone(), &field.other)
-                })
-            }
+            cs_fold_fields(use_foldl, f, base, cx, all_fields)
         }
-        EnumNonMatchingCollapsed(ref all_args, _, tuple) => {
-            enum_nonmatch_f(cx,
-                            trait_span,
-                            (&all_args[..], tuple),
-                            substructure.nonself_args)
+        EnumNonMatchingCollapsed(..) => {
+            cs_fold_enumnonmatch(enum_nonmatch_f, cx, trait_span, substructure)
+        }
+        StaticEnum(..) | StaticStruct(..) => {
+            cs_fold_static(cx, trait_span)
         }
-        StaticEnum(..) | StaticStruct(..) => cx.span_bug(trait_span, "static function in `derive`"),
     }
 }
 
+/// Function to fold over fields, with three cases, to generate more efficient and concise code.
+/// When the `substructure` has grouped fields, there are two cases:
+/// Zero fields: call the base case function with None (like the usual base case of `cs_fold`).
+/// One or more fields: call the base case function on the first value (which depends on
+/// `use_fold`), and use that as the base case. Then perform `cs_fold` on the remainder of the
+/// fields.
+/// When the `substructure` is a `EnumNonMatchingCollapsed`, the result of `enum_nonmatch_f`
+/// is returned. Statics may not be folded over.
+/// See `cs_op` in `partial_ord.rs` for a model example.
+pub fn cs_fold1<F, B>(use_foldl: bool,
+                      f: F,
+                      mut b: B,
+                      enum_nonmatch_f: EnumNonMatchCollapsedFunc,
+                      cx: &mut ExtCtxt,
+                      trait_span: Span,
+                      substructure: &Substructure)
+                      -> P<Expr>
+    where F: FnMut(&mut ExtCtxt, Span, P<Expr>, P<Expr>, &[P<Expr>]) -> P<Expr>,
+          B: FnMut(&mut ExtCtxt, Option<(Span, P<Expr>, &[P<Expr>])>) -> P<Expr>
+{
+    match *substructure.fields {
+        EnumMatching(.., ref all_fields) |
+        Struct(_, ref all_fields) => {
+            let (base, all_fields) = match (all_fields.is_empty(), use_foldl) {
+                (false, true) => {
+                    let field = &all_fields[0];
+                    let args = (field.span, field.self_.clone(), &field.other[..]);
+                    (b(cx, Some(args)), &all_fields[1..])
+                }
+                (false, false) => {
+                    let idx = all_fields.len() - 1;
+                    let field = &all_fields[idx];
+                    let args = (field.span, field.self_.clone(), &field.other[..]);
+                    (b(cx, Some(args)), &all_fields[..idx])
+                }
+                (true, _) => (b(cx, None), &all_fields[..])
+            };
+
+            cs_fold_fields(use_foldl, f, base, cx, all_fields)
+        }
+        EnumNonMatchingCollapsed(..) => {
+            cs_fold_enumnonmatch(enum_nonmatch_f, cx, trait_span, substructure)
+        }
+        StaticEnum(..) | StaticStruct(..) => {
+            cs_fold_static(cx, trait_span)
+        }
+    }
+}
 
 /// Call the method that is being derived on all the fields, and then
 /// process the collected results. i.e.