auto merge of #8285 : huonw/rust/deriving+++, r=alexcrichton

Some general clean-up relating to deriving:
- `TotalOrd` was too eager, and evaluated the `.cmp` call for every field, even if it could short-circuit earlier.
- the pointer types didn't have impls for `TotalOrd` or `TotalEq`.
- the Makefiles didn't reach deep enough into libsyntax for dependencies.

(Split out from https://github.com/mozilla/rust/pull/8258.)

6 files changed, 142 insertions, 19 deletions

diff --git a/src/libstd/borrow.rs b/src/libstd/borrow.rs
index 9e3a3a28fe8..6c3d4c5f1fb 100644
--- a/src/libstd/borrow.rs
+++ b/src/libstd/borrow.rs
@@ -58,3 +58,15 @@ impl<'self, T: Ord> Ord for &'self T {
         *(*self) > *(*other)
     }
 }
+
+#[cfg(not(test))]
+impl<'self, T: TotalOrd> TotalOrd for &'self T {
+    #[inline]
+    fn cmp(&self, other: & &'self T) -> Ordering { (**self).cmp(*other) }
+}
+
+#[cfg(not(test))]
+impl<'self, T: TotalEq> TotalEq for &'self T {
+    #[inline]
+    fn equals(&self, other: & &'self T) -> bool { (**self).equals(*other) }
+}
diff --git a/src/libstd/cmp.rs b/src/libstd/cmp.rs
index 43a632562b2..b66f89e8341 100644
--- a/src/libstd/cmp.rs
+++ b/src/libstd/cmp.rs
@@ -153,7 +153,6 @@ pub fn cmp2<A:TotalOrd,B:TotalOrd>(
 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]
 pub fn lexical_ordering(o1: Ordering, o2: Ordering) -> Ordering {
     match o1 {
diff --git a/src/libstd/managed.rs b/src/libstd/managed.rs
index bd4dc69537c..57230b2fd24 100644
--- a/src/libstd/managed.rs
+++ b/src/libstd/managed.rs
@@ -12,7 +12,7 @@
 
 use ptr::to_unsafe_ptr;
 
-#[cfg(not(test))] use cmp::{Eq, Ord};
+#[cfg(not(test))] use cmp::*;
 
 pub static RC_MANAGED_UNIQUE : uint = (-2) as uint;
 pub static RC_IMMORTAL : uint = 0x77777777;
@@ -71,6 +71,29 @@ impl<T:Ord> Ord for @mut T {
     fn gt(&self, other: &@mut T) -> bool { *(*self) > *(*other) }
 }
 
+#[cfg(not(test))]
+impl<T: TotalOrd> TotalOrd for @T {
+    #[inline]
+    fn cmp(&self, other: &@T) -> Ordering { (**self).cmp(*other) }
+}
+
+#[cfg(not(test))]
+impl<T: TotalOrd> TotalOrd for @mut T {
+    #[inline]
+    fn cmp(&self, other: &@mut T) -> Ordering { (**self).cmp(*other) }
+}
+
+#[cfg(not(test))]
+impl<T: TotalEq> TotalEq for @T {
+    #[inline]
+    fn equals(&self, other: &@T) -> bool { (**self).equals(*other) }
+}
+
+#[cfg(not(test))]
+impl<T: TotalEq> TotalEq for @mut T {
+    #[inline]
+    fn equals(&self, other: &@mut T) -> bool { (**self).equals(*other) }
+}
 #[test]
 fn test() {
     let x = @3;
diff --git a/src/libstd/owned.rs b/src/libstd/owned.rs
index e7a6e38fdb0..424c4fd6b2f 100644
--- a/src/libstd/owned.rs
+++ b/src/libstd/owned.rs
@@ -10,7 +10,7 @@
 
 //! Operations on unique pointer types
 
-#[cfg(not(test))] use cmp::{Eq, Ord};
+#[cfg(not(test))] use cmp::*;
 
 #[cfg(not(test))]
 impl<T:Eq> Eq for ~T {
@@ -31,3 +31,15 @@ impl<T:Ord> Ord for ~T {
     #[inline]
     fn gt(&self, other: &~T) -> bool { *(*self) > *(*other) }
 }
+
+#[cfg(not(test))]
+impl<T: TotalOrd> TotalOrd for ~T {
+    #[inline]
+    fn cmp(&self, other: &~T) -> Ordering { (**self).cmp(*other) }
+}
+
+#[cfg(not(test))]
+impl<T: TotalEq> TotalEq for ~T {
+    #[inline]
+    fn equals(&self, other: &~T) -> bool { (**self).equals(*other) }
+}
diff --git a/src/libsyntax/ext/deriving/cmp/totalord.rs b/src/libsyntax/ext/deriving/cmp/totalord.rs
index 01dacdfe453..001e9235528 100644
--- a/src/libsyntax/ext/deriving/cmp/totalord.rs
+++ b/src/libsyntax/ext/deriving/cmp/totalord.rs
@@ -8,6 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use ast;
 use ast::{MetaItem, item, expr};
 use codemap::span;
 use ext::base::ExtCtxt;
@@ -40,40 +41,70 @@ pub fn expand_deriving_totalord(cx: @ExtCtxt,
 }
 
 
-pub fn ordering_const(cx: @ExtCtxt, span: span, cnst: Ordering) -> @expr {
+pub fn ordering_const(cx: @ExtCtxt, span: span, cnst: Ordering) -> ast::Path {
     let cnst = match cnst {
         Less => "Less",
         Equal => "Equal",
         Greater => "Greater"
     };
-    cx.expr_path(
-        cx.path_global(span,
-                       ~[cx.ident_of("std"),
-                         cx.ident_of("cmp"),
-                         cx.ident_of(cnst)]))
+    cx.path_global(span,
+                   ~[cx.ident_of("std"),
+                     cx.ident_of("cmp"),
+                     cx.ident_of(cnst)])
 }
 
 pub fn cs_cmp(cx: @ExtCtxt, span: span,
               substr: &Substructure) -> @expr {
+    let test_id = cx.ident_of("__test");
+    let equals_path = ordering_const(cx, span, Equal);
 
+    /*
+    Builds:
+
+    let __test = self_field1.cmp(&other_field2);
+    if other == ::std::cmp::Equal {
+        let __test = self_field2.cmp(&other_field2);
+        if __test == ::std::cmp::Equal {
+            ...
+        } else {
+            __test
+        }
+    } else {
+        __test
+    }
+
+    FIXME #6449: These `if`s could/should be `match`es.
+    */
     cs_same_method_fold(
-        // foldr (possibly) nests the matches in lexical_ordering better
+        // foldr nests the if-elses correctly, leaving the first field
+        // as the outermost one, and the last as the innermost.
         false,
         |cx, span, old, new| {
-            cx.expr_call_global(span,
-                                ~[cx.ident_of("std"),
-                                  cx.ident_of("cmp"),
-                                  cx.ident_of("lexical_ordering")],
-                                ~[old, new])
+            // let __test = new;
+            // if __test == ::std::cmp::Equal {
+            //    old
+            // } else {
+            //    __test
+            // }
+
+            let assign = cx.stmt_let(span, false, test_id, new);
+
+            let cond = cx.expr_binary(span, ast::eq,
+                                      cx.expr_ident(span, test_id),
+                                      cx.expr_path(equals_path.clone()));
+            let if_ = cx.expr_if(span,
+                                 cond,
+                                 old, Some(cx.expr_ident(span, test_id)));
+            cx.expr_block(cx.block(span, ~[assign], Some(if_)))
         },
-        ordering_const(cx, span, Equal),
+        cx.expr_path(equals_path.clone()),
         |cx, span, list, _| {
             match list {
                 // an earlier nonmatching variant is Less than a
-                // later one
+                // later one.
                 [(self_var, _, _),
-                 (other_var, _, _)] => ordering_const(cx, span,
-                                                      self_var.cmp(&other_var)),
+                 (other_var, _, _)] => cx.expr_path(ordering_const(cx, span,
+                                                                   self_var.cmp(&other_var))),
                 _ => cx.span_bug(span, "Not exactly 2 arguments in `deriving(TotalOrd)`")
             }
         },
diff --git a/src/test/run-pass/deriving-cmp-shortcircuit.rs b/src/test/run-pass/deriving-cmp-shortcircuit.rs
new file mode 100644
index 00000000000..7f5c78cf602
--- /dev/null
+++ b/src/test/run-pass/deriving-cmp-shortcircuit.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.
+
+// check that the derived impls for the comparison traits shortcircuit
+// where possible, by having a type that fails when compared as the
+// second element, so this passes iff the instances shortcircuit.
+
+pub struct FailCmp;
+impl Eq for FailCmp {
+    fn eq(&self, _: &FailCmp) -> bool { fail!("eq") }
+}
+
+impl Ord for FailCmp {
+    fn lt(&self, _: &FailCmp) -> bool { fail!("lt") }
+}
+
+impl TotalEq for FailCmp {
+    fn equals(&self, _: &FailCmp) -> bool { fail!("equals") }
+}
+
+impl TotalOrd for FailCmp {
+    fn cmp(&self, _: &FailCmp) -> Ordering { fail!("cmp") }
+}
+
+#[deriving(Eq,Ord,TotalEq,TotalOrd)]
+struct ShortCircuit {
+    x: int,
+    y: FailCmp
+}
+
+fn main() {
+    let a = ShortCircuit { x: 1, y: FailCmp };
+    let b = ShortCircuit { x: 2, y: FailCmp };
+
+    assert!(a != b);
+    assert!(a < b);
+    assert!(!a.equals(&b));
+    assert_eq!(a.cmp(&b), ::std::cmp::Less);
+}