create a sensible comparison trait hierarchy

* `Ord` inherits from `Eq`
* `TotalOrd` inherits from `TotalEq`
* `TotalOrd` inherits from `Ord`
* `TotalEq` inherits from `Eq`

This is a partial implementation of #12517.

5 files changed, 33 insertions, 18 deletions

diff --git a/src/libstd/cmp.rs b/src/libstd/cmp.rs
index 291f1dd04d3..6975c9da3f0 100644
--- a/src/libstd/cmp.rs
+++ b/src/libstd/cmp.rs
@@ -42,8 +42,12 @@ pub trait Eq {
 }
 
 /// Trait for equality comparisons where `a == b` and `a != b` are strict inverses.
-pub trait TotalEq {
-    fn equals(&self, other: &Self) -> bool;
+pub trait TotalEq: Eq {
+    /// This method must return the same value as `eq`. It exists to prevent
+    /// deriving `TotalEq` from fields not implementing the `TotalEq` trait.
+    fn equals(&self, other: &Self) -> bool {
+        self.eq(other)
+    }
 }
 
 macro_rules! totaleq_impl(
@@ -76,7 +80,7 @@ totaleq_impl!(char)
 pub enum Ordering { Less = -1, Equal = 0, Greater = 1 }
 
 /// Trait for types that form a total order
-pub trait TotalOrd: TotalEq {
+pub trait TotalOrd: TotalEq + Ord {
     fn cmp(&self, other: &Self) -> Ordering;
 }
 
@@ -161,7 +165,7 @@ pub fn lexical_ordering(o1: Ordering, o2: Ordering) -> Ordering {
 * (cf. IEEE 754-2008 section 5.11).
 */
 #[lang="ord"]
-pub trait Ord {
+pub trait Ord: Eq {
     fn lt(&self, other: &Self) -> bool;
     #[inline]
     fn le(&self, other: &Self) -> bool { !other.lt(self) }
@@ -169,8 +173,6 @@ pub trait Ord {
     fn gt(&self, other: &Self) -> bool {  other.lt(self) }
     #[inline]
     fn ge(&self, other: &Self) -> bool { !self.lt(other) }
-
-    // FIXME (#12068): Add min/max/clamp default methods
 }
 
 /// The equivalence relation. Two values may be equivalent even if they are
diff --git a/src/libstd/iter.rs b/src/libstd/iter.rs
index a01a4bf3d62..6bf3cdf52ab 100644
--- a/src/libstd/iter.rs
+++ b/src/libstd/iter.rs
@@ -2033,7 +2033,7 @@ pub fn range_inclusive<A: Add<A, A> + Ord + Clone + One + ToPrimitive>(start: A,
     RangeInclusive{range: range(start, stop), done: false}
 }
 
-impl<A: Add<A, A> + Eq + Ord + Clone + ToPrimitive> Iterator<A> for RangeInclusive<A> {
+impl<A: Add<A, A> + Ord + Clone + ToPrimitive> Iterator<A> for RangeInclusive<A> {
     #[inline]
     fn next(&mut self) -> Option<A> {
         match self.range.next() {
@@ -2244,7 +2244,7 @@ pub mod order {
     }
 
     /// Return `a` < `b` lexicographically (Using partial order, `Ord`)
-    pub fn lt<A: Eq + Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
+    pub fn lt<A: Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
         loop {
             match (a.next(), b.next()) {
                 (None, None) => return false,
@@ -2256,7 +2256,7 @@ pub mod order {
     }
 
     /// Return `a` <= `b` lexicographically (Using partial order, `Ord`)
-    pub fn le<A: Eq + Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
+    pub fn le<A: Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
         loop {
             match (a.next(), b.next()) {
                 (None, None) => return true,
@@ -2268,7 +2268,7 @@ pub mod order {
     }
 
     /// Return `a` > `b` lexicographically (Using partial order, `Ord`)
-    pub fn gt<A: Eq + Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
+    pub fn gt<A: Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
         loop {
             match (a.next(), b.next()) {
                 (None, None) => return false,
@@ -2280,7 +2280,7 @@ pub mod order {
     }
 
     /// Return `a` >= `b` lexicographically (Using partial order, `Ord`)
-    pub fn ge<A: Eq + Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
+    pub fn ge<A: Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
         loop {
             match (a.next(), b.next()) {
                 (None, None) => return true,
@@ -2978,6 +2978,12 @@ mod tests {
             }
         }
 
+        impl Eq for Foo {
+            fn eq(&self, _: &Foo) -> bool {
+                true
+            }
+        }
+
         impl Ord for Foo {
             fn lt(&self, _: &Foo) -> bool {
                 false
diff --git a/src/libstd/option.rs b/src/libstd/option.rs
index 633d6e92c70..7997c5747b4 100644
--- a/src/libstd/option.rs
+++ b/src/libstd/option.rs
@@ -40,7 +40,7 @@
 use any::Any;
 use clone::Clone;
 use clone::DeepClone;
-use cmp::{Eq, TotalEq, TotalOrd};
+use cmp::{Eq, TotalOrd};
 use default::Default;
 use iter::{Iterator, DoubleEndedIterator, FromIterator, ExactSize};
 use kinds::Send;
diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index 59136c99ec9..69bf5f5d0fc 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -682,7 +682,7 @@ pub mod traits {
         fn cmp(&self, other: &~[T]) -> Ordering { self.as_slice().cmp(&other.as_slice()) }
     }
 
-    impl<'a, T: Eq + Ord> Ord for &'a [T] {
+    impl<'a, T: Ord> Ord for &'a [T] {
         fn lt(&self, other: & &'a [T]) -> bool {
             order::lt(self.iter(), other.iter())
         }
@@ -700,7 +700,7 @@ pub mod traits {
         }
     }
 
-    impl<T: Eq + Ord> Ord for ~[T] {
+    impl<T: Ord> Ord for ~[T] {
         #[inline]
         fn lt(&self, other: &~[T]) -> bool { self.as_slice() < other.as_slice() }
         #[inline]
diff --git a/src/libstd/vec_ng.rs b/src/libstd/vec_ng.rs
index 0a5a7c2da47..ae918bfa98b 100644
--- a/src/libstd/vec_ng.rs
+++ b/src/libstd/vec_ng.rs
@@ -13,7 +13,7 @@
 
 use cast::{forget, transmute};
 use clone::Clone;
-use cmp::{Eq, Ordering, TotalEq, TotalOrd};
+use cmp::{Ord, Eq, Ordering, TotalEq, TotalOrd};
 use container::Container;
 use default::Default;
 use fmt;
@@ -136,21 +136,28 @@ impl<T> Extendable<T> for Vec<T> {
     }
 }
 
-impl<T:Eq> Eq for Vec<T> {
+impl<T: Eq> Eq for Vec<T> {
     #[inline]
     fn eq(&self, other: &Vec<T>) -> bool {
         self.as_slice() == other.as_slice()
     }
 }
 
-impl<T:TotalEq> TotalEq for Vec<T> {
+impl<T: Ord> Ord for Vec<T> {
+    #[inline]
+    fn lt(&self, other: &Vec<T>) -> bool {
+        self.as_slice() < other.as_slice()
+    }
+}
+
+impl<T: TotalEq> TotalEq for Vec<T> {
     #[inline]
     fn equals(&self, other: &Vec<T>) -> bool {
         self.as_slice().equals(&other.as_slice())
     }
 }
 
-impl<T:TotalOrd> TotalOrd for Vec<T> {
+impl<T: TotalOrd> TotalOrd for Vec<T> {
     #[inline]
     fn cmp(&self, other: &Vec<T>) -> Ordering {
         self.as_slice().cmp(&other.as_slice())