Implement RFC#28: Add PartialOrd::partial_cmp

I ended up altering the semantics of Json's PartialOrd implementation.
It used to be the case that Null < Null, but I can't think of any reason
for an ordering other than the default one so I just switched it over to
using the derived implementation.

This also fixes broken `PartialOrd` implementations for `Vec` and
`TreeMap`.

RFC: 0028-partial-cmp

6 files changed, 155 insertions, 13 deletions

diff --git a/src/libcore/cmp.rs b/src/libcore/cmp.rs
index a29aba6df98..8696d385c44 100644
--- a/src/libcore/cmp.rs
+++ b/src/libcore/cmp.rs
@@ -37,6 +37,10 @@
 //! assert!(SketchyNum {num: 25} != SketchyNum {num: 57});
 //! ```
 
+use option::{Option, Some};
+#[cfg(stage0)]
+use option::None;
+
 /// Trait for values that can be compared for equality and inequality.
 ///
 /// This trait allows for partial equality, for types that do not have an
@@ -127,7 +131,9 @@ impl Ord for Ordering {
 
 impl PartialOrd for Ordering {
     #[inline]
-    fn lt(&self, other: &Ordering) -> bool { (*self as int) < (*other as int) }
+    fn partial_cmp(&self, other: &Ordering) -> Option<Ordering> {
+        (*self as int).partial_cmp(&(*other as int))
+    }
 }
 
 /// Combine orderings, lexically.
@@ -145,7 +151,7 @@ pub fn lexical_ordering(o1: Ordering, o2: Ordering) -> Ordering {
 
 /// Trait for values that can be compared for a sort-order.
 ///
-/// PartialOrd only requires implementation of the `lt` method,
+/// PartialOrd only requires implementation of the `partial_cmp` method,
 /// with the others generated from default implementations.
 ///
 /// However it remains possible to implement the others separately for types
@@ -154,20 +160,57 @@ pub fn lexical_ordering(o1: Ordering, o2: Ordering) -> Ordering {
 /// 5.11).
 #[lang="ord"]
 pub trait PartialOrd: PartialEq {
+    /// This method returns an ordering between `self` and `other` values
+    /// if one exists.
+    #[cfg(stage0)]
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        match (!self.lt(other), !other.lt(self)) {
+            (false, false) => None,
+            (false, true) => Some(Less),
+            (true, false) => Some(Greater),
+            (true, true) => Some(Equal),
+        }
+    }
+
+    /// This method returns an ordering between `self` and `other` values
+    /// if one exists.
+    #[cfg(not(stage0))]
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering>;
+
     /// This method tests less than (for `self` and `other`) and is used by the `<` operator.
-    fn lt(&self, other: &Self) -> bool;
+    fn lt(&self, other: &Self) -> bool {
+        match self.partial_cmp(other) {
+            Some(Less) => true,
+            _ => false,
+        }
+    }
 
     /// This method tests less than or equal to (`<=`).
     #[inline]
-    fn le(&self, other: &Self) -> bool { !other.lt(self) }
+    fn le(&self, other: &Self) -> bool {
+        match self.partial_cmp(other) {
+            Some(Less) | Some(Equal) => true,
+            _ => false,
+        }
+    }
 
     /// This method tests greater than (`>`).
     #[inline]
-    fn gt(&self, other: &Self) -> bool {  other.lt(self) }
+    fn gt(&self, other: &Self) -> bool {
+        match self.partial_cmp(other) {
+            Some(Greater) => true,
+            _ => false,
+        }
+    }
 
     /// This method tests greater than or equal to (`>=`).
     #[inline]
-    fn ge(&self, other: &Self) -> bool { !self.lt(other) }
+    fn ge(&self, other: &Self) -> bool {
+        match self.partial_cmp(other) {
+            Some(Greater) | Some(Equal) => true,
+            _ => false,
+        }
+    }
 }
 
 /// The equivalence relation. Two values may be equivalent even if they are
@@ -195,6 +238,7 @@ pub fn max<T: Ord>(v1: T, v2: T) -> T {
 mod impls {
     use cmp::{PartialOrd, Ord, PartialEq, Eq, Ordering,
               Less, Greater, Equal};
+    use option::{Option, Some, None};
 
     macro_rules! eq_impl(
         ($($t:ty)*) => ($(
@@ -228,6 +272,15 @@ mod impls {
         ($($t:ty)*) => ($(
             impl PartialOrd for $t {
                 #[inline]
+                fn partial_cmp(&self, other: &$t) -> Option<Ordering> {
+                    match (self <= other, self >= other) {
+                        (false, false) => None,
+                        (false, true) => Some(Greater),
+                        (true, false) => Some(Less),
+                        (true, true) => Some(Equal),
+                    }
+                }
+                #[inline]
                 fn lt(&self, other: &$t) -> bool { (*self) < (*other) }
                 #[inline]
                 fn le(&self, other: &$t) -> bool { (*self) <= (*other) }
@@ -241,13 +294,15 @@ mod impls {
 
     impl PartialOrd for () {
         #[inline]
-        fn lt(&self, _other: &()) -> bool { false }
+        fn partial_cmp(&self, _: &()) -> Option<Ordering> {
+            Some(Equal)
+        }
     }
 
     impl PartialOrd for bool {
         #[inline]
-        fn lt(&self, other: &bool) -> bool {
-            (*self as u8) < (*other as u8)
+        fn partial_cmp(&self, other: &bool) -> Option<Ordering> {
+            (*self as u8).partial_cmp(&(*other as u8))
         }
     }
 
@@ -289,6 +344,10 @@ mod impls {
     }
     impl<'a, T: PartialOrd> PartialOrd for &'a T {
         #[inline]
+        fn partial_cmp(&self, other: &&'a T) -> Option<Ordering> {
+            (**self).partial_cmp(*other)
+        }
+        #[inline]
         fn lt(&self, other: & &'a T) -> bool { *(*self) < *(*other) }
         #[inline]
         fn le(&self, other: & &'a T) -> bool { *(*self) <= *(*other) }
@@ -312,6 +371,10 @@ mod impls {
     }
     impl<'a, T: PartialOrd> PartialOrd for &'a mut T {
         #[inline]
+        fn partial_cmp(&self, other: &&'a mut T) -> Option<Ordering> {
+            (**self).partial_cmp(*other)
+        }
+        #[inline]
         fn lt(&self, other: &&'a mut T) -> bool { **self < **other }
         #[inline]
         fn le(&self, other: &&'a mut T) -> bool { **self <= **other }
diff --git a/src/libcore/iter.rs b/src/libcore/iter.rs
index 1445376d7db..5895d871dbe 100644
--- a/src/libcore/iter.rs
+++ b/src/libcore/iter.rs
@@ -2183,7 +2183,7 @@ impl<A: Clone> RandomAccessIterator<A> for Repeat<A> {
 pub mod order {
     use cmp;
     use cmp::{Eq, Ord, PartialOrd, PartialEq};
-    use option::{Some, None};
+    use option::{Option, Some, None};
     use super::Iterator;
 
     /// Compare `a` and `b` for equality using `Eq`
@@ -2212,6 +2212,22 @@ pub mod order {
         }
     }
 
+    /// Order `a` and `b` lexicographically using `PartialOrd`
+    pub fn partial_cmp<A: PartialOrd, T: Iterator<A>, S: Iterator<A>>(mut a: T, mut b: S)
+            -> Option<cmp::Ordering> {
+        loop {
+            match (a.next(), b.next()) {
+                (None, None) => return Some(cmp::Equal),
+                (None, _   ) => return Some(cmp::Less),
+                (_   , None) => return Some(cmp::Greater),
+                (Some(x), Some(y)) => match x.partial_cmp(&y) {
+                    Some(cmp::Equal) => (),
+                    non_eq => return non_eq,
+                },
+            }
+        }
+    }
+
     /// Compare `a` and `b` for equality (Using partial equality, `PartialEq`)
     pub fn eq<A: PartialEq, T: Iterator<A>, S: Iterator<A>>(mut a: T, mut b: S) -> bool {
         loop {
diff --git a/src/libcore/ptr.rs b/src/libcore/ptr.rs
index cecc6bab683..093591cd796 100644
--- a/src/libcore/ptr.rs
+++ b/src/libcore/ptr.rs
@@ -93,7 +93,7 @@ use intrinsics;
 use iter::{range, Iterator};
 use option::{Some, None, Option};
 
-use cmp::{PartialEq, Eq, PartialOrd, Equiv};
+use cmp::{PartialEq, Eq, PartialOrd, Equiv, Ordering, Less, Equal, Greater};
 
 /// Create a null pointer.
 ///
@@ -489,10 +489,50 @@ mod externfnpointers {
 // Comparison for pointers
 impl<T> PartialOrd for *const T {
     #[inline]
+    fn partial_cmp(&self, other: &*const T) -> Option<Ordering> {
+        if self < other {
+            Some(Less)
+        } else if self == other {
+            Some(Equal)
+        } else {
+            Some(Greater)
+        }
+    }
+
+    #[inline]
     fn lt(&self, other: &*const T) -> bool { *self < *other }
+
+    #[inline]
+    fn le(&self, other: &*const T) -> bool { *self <= *other }
+
+    #[inline]
+    fn gt(&self, other: &*const T) -> bool { *self > *other }
+
+    #[inline]
+    fn ge(&self, other: &*const T) -> bool { *self >= *other }
 }
 
 impl<T> PartialOrd for *mut T {
     #[inline]
+    fn partial_cmp(&self, other: &*mut T) -> Option<Ordering> {
+        if self < other {
+            Some(Less)
+        } else if self == other {
+            Some(Equal)
+        } else {
+            Some(Greater)
+        }
+    }
+
+    #[inline]
     fn lt(&self, other: &*mut T) -> bool { *self < *other }
+
+    #[inline]
+    fn le(&self, other: &*mut T) -> bool { *self <= *other }
+
+    #[inline]
+    fn gt(&self, other: &*mut T) -> bool { *self > *other }
+
+    #[inline]
+    fn ge(&self, other: &*mut T) -> bool { *self >= *other }
 }
diff --git a/src/libcore/slice.rs b/src/libcore/slice.rs
index 63406334103..a9e7efdf05a 100644
--- a/src/libcore/slice.rs
+++ b/src/libcore/slice.rs
@@ -253,6 +253,7 @@ pub mod traits {
     use cmp::{PartialEq, PartialOrd, Eq, Ord, Ordering, Equiv};
     use iter::order;
     use collections::Collection;
+    use option::Option;
 
     impl<'a,T:PartialEq> PartialEq for &'a [T] {
         fn eq(&self, other: & &'a [T]) -> bool {
@@ -279,6 +280,11 @@ pub mod traits {
     }
 
     impl<'a, T: PartialOrd> PartialOrd for &'a [T] {
+        #[inline]
+        fn partial_cmp(&self, other: &&'a [T]) -> Option<Ordering> {
+            order::partial_cmp(self.iter(), other.iter())
+        }
+        #[inline]
         fn lt(&self, other: & &'a [T]) -> bool {
             order::lt(self.iter(), other.iter())
         }
diff --git a/src/libcore/str.rs b/src/libcore/str.rs
index 21de4cdf59f..de23e04393b 100644
--- a/src/libcore/str.rs
+++ b/src/libcore/str.rs
@@ -931,7 +931,7 @@ pub mod traits {
     use cmp::{Ord, Ordering, Less, Equal, Greater, PartialEq, PartialOrd, Equiv, Eq};
     use collections::Collection;
     use iter::Iterator;
-    use option::{Some, None};
+    use option::{Option, Some, None};
     use str::{Str, StrSlice, eq_slice};
 
     impl<'a> Ord for &'a str {
@@ -962,7 +962,9 @@ pub mod traits {
 
     impl<'a> PartialOrd for &'a str {
         #[inline]
-        fn lt(&self, other: & &'a str) -> bool { self.cmp(other) == Less }
+        fn partial_cmp(&self, other: &&'a str) -> Option<Ordering> {
+            Some(self.cmp(other))
+        }
     }
 
     impl<'a, S: Str> Equiv<S> for &'a str {
diff --git a/src/libcore/tuple.rs b/src/libcore/tuple.rs
index f44bce33547..0e3722894bc 100644
--- a/src/libcore/tuple.rs
+++ b/src/libcore/tuple.rs
@@ -64,6 +64,7 @@
 use clone::Clone;
 use cmp::*;
 use default::Default;
+use option::{Option, Some};
 
 // macro for implementing n-ary tuple functions and operations
 macro_rules! tuple_impls {
@@ -126,6 +127,10 @@ macro_rules! tuple_impls {
 
             impl<$($T:PartialOrd + PartialEq),+> PartialOrd for ($($T,)+) {
                 #[inline]
+                fn partial_cmp(&self, other: &($($T,)+)) -> Option<Ordering> {
+                    lexical_partial_cmp!($(self.$refN(), other.$refN()),+)
+                }
+                #[inline]
                 fn lt(&self, other: &($($T,)+)) -> bool {
                     lexical_ord!(lt, $(self.$refN(), other.$refN()),+)
                 }
@@ -172,6 +177,16 @@ macro_rules! lexical_ord {
     ($rel: ident, $a:expr, $b:expr) => { (*$a) . $rel ($b) };
 }
 
+macro_rules! lexical_partial_cmp {
+    ($a:expr, $b:expr, $($rest_a:expr, $rest_b:expr),+) => {
+        match ($a).partial_cmp($b) {
+            Some(Equal) => lexical_partial_cmp!($($rest_a, $rest_b),+),
+            ordering   => ordering
+        }
+    };
+    ($a:expr, $b:expr) => { ($a).partial_cmp($b) };
+}
+
 macro_rules! lexical_cmp {
     ($a:expr, $b:expr, $($rest_a:expr, $rest_b:expr),+) => {
         match ($a).cmp($b) {