syntax: rewrite deriving(Ord) to not require Eq.

lt and gt are implement directly in terms of the corresponding
method on their elements, and le and ge are the negations of these.

1 files changed, 59 insertions, 57 deletions

diff --git a/src/libsyntax/ext/deriving/cmp/ord.rs b/src/libsyntax/ext/deriving/cmp/ord.rs
index e07215a905a..759576814d5 100644
--- a/src/libsyntax/ext/deriving/cmp/ord.rs
+++ b/src/libsyntax/ext/deriving/cmp/ord.rs
@@ -10,6 +10,7 @@
 
 use core::prelude::*;
 
+use ast;
 use ast::{meta_item, item, expr};
 use codemap::span;
 use ext::base::ExtCtxt;
@@ -21,7 +22,7 @@ pub fn expand_deriving_ord(cx: @ExtCtxt,
                            mitem: @meta_item,
                            in_items: ~[@item]) -> ~[@item] {
     macro_rules! md (
-        ($name:expr, $less:expr, $equal:expr) => {
+        ($name:expr, $func:expr, $op:expr) => {
             MethodDef {
                 name: $name,
                 generics: LifetimeBounds::empty(),
@@ -29,82 +30,67 @@ pub fn expand_deriving_ord(cx: @ExtCtxt,
                 args: ~[borrowed_self()],
                 ret_ty: Literal(Path::new(~["bool"])),
                 const_nonmatching: false,
-                combine_substructure: |cx, span, substr|
-                    cs_ord($less, $equal, cx, span, substr)
+                combine_substructure: |cx, span, substr| $func($op, cx, span, substr)
             }
         }
     );
 
-
-
     let trait_def = TraitDef {
         path: Path::new(~["std", "cmp", "Ord"]),
-        // XXX: Ord doesn't imply Eq yet
-        additional_bounds: ~[Literal(Path::new(~["std", "cmp", "Eq"]))],
+        additional_bounds: ~[],
         generics: LifetimeBounds::empty(),
         methods: ~[
-            md!("lt", true,  false),
-            md!("le", true,  true),
-            md!("gt", false, false),
-            md!("ge", false, true)
+            md!("lt", cs_strict, true),
+            md!("le", cs_nonstrict, true), // inverse operation
+            md!("gt", cs_strict, false),
+            md!("ge", cs_nonstrict, false)
         ]
     };
     trait_def.expand(cx, span, mitem, in_items)
 }
 
-/// `less`: is this `lt` or `le`? `equal`: is this `le` or `ge`?
-fn cs_ord(less: bool, equal: bool,
-          cx: @ExtCtxt, span: span,
-          substr: &Substructure) -> @expr {
-    let binop = if less {
-        cx.ident_of("lt")
-    } else {
-        cx.ident_of("gt")
-    };
-    let base = cx.expr_bool(span, equal);
-
+/// Strict inequality.
+fn cs_strict(less: bool, cx: @ExtCtxt, span: span, substr: &Substructure) -> @expr {
+    let op = if less {ast::lt} else {ast::gt};
     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.
+            build up a series of chain ||'s and &&'s from the inside
+            out (hence foldr) to get lexical ordering, i.e. for op ==
+            `ast::lt`
 
             ```
-            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
-            }
+            self.f1 < other.f1 || (!(other.f1 < self.f1) &&
+                (self.f2 < other.f2 || (!(other.f2 < self.f2) &&
+                    (false)
+                ))
+            )
             ```
 
-            The inner "`equal`" case is only reached if the two
-            items have all fields equal.
+            The optimiser should remove the redundancy. We explicitly
+            get use the binops to avoid auto-deref derefencing too many
+            layers of pointers, if the type includes pointers.
             */
-            if other_fs.len() != 1 {
-                cx.span_bug(span, "Not exactly 2 arguments in `deriving(Ord)`");
-            }
+            let other_f = match other_fs {
+                [o_f] => o_f,
+                _ => cx.span_bug(span, "Not exactly 2 arguments in `deriving(Ord)`")
+            };
+
+            let cmp = cx.expr_binary(span, op,
+                                     cx.expr_deref(span, self_f),
+                                     cx.expr_deref(span, other_f));
 
-            let cmp = cx.expr_method_call(span,
-                                          self_f, cx.ident_of("eq"), other_fs.to_owned());
-            let elseif = cx.expr_if(span, cmp,
-                                    subexpr, Some(cx.expr_bool(span, false)));
+            let not_cmp = cx.expr_binary(span, op,
+                                         cx.expr_deref(span, other_f),
+                                         cx.expr_deref(span, self_f));
+            let not_cmp = cx.expr_unary(span, ast::not, not_cmp);
 
-            let cmp = cx.expr_method_call(span,
-                                          self_f, binop, other_fs.to_owned());
-            cx.expr_if(span, cmp,
-                        cx.expr_bool(span, true), Some(elseif))
+            let and = cx.expr_binary(span, ast::and,
+                                     not_cmp, subexpr);
+            cx.expr_binary(span, ast::or, cmp, and)
         },
-        base,
+        cx.expr_bool(span, false),
         |cx, span, args, _| {
             // nonmatching enums, order by the order the variants are
             // written
@@ -112,13 +98,29 @@ fn cs_ord(less: bool, equal: bool,
                 [(self_var, _, _),
                  (other_var, _, _)] =>
                     cx.expr_bool(span,
-                                   if less {
-                                       self_var < other_var
-                                   } else {
-                                       self_var > other_var
-                                   }),
+                                 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)
 }
+
+fn cs_nonstrict(less: bool, cx: @ExtCtxt, span: span, substr: &Substructure) -> @expr {
+    // Example: ge becomes !(*self < *other), le becomes !(*self > *other)
+
+    let inverse_op = if less {ast::gt} else {ast::lt};
+    match substr.self_args {
+        [self_, other] => {
+            let inverse_cmp = cx.expr_binary(span, inverse_op,
+                                             cx.expr_deref(span, self_),
+                                             cx.expr_deref(span, other));
+
+            cx.expr_unary(span, ast::not, inverse_cmp)
+        }
+        _ => cx.span_bug(span, "Not exactly 2 arguments in `deriving(Ord)`")
+    }
+}