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

28 files changed, 346 insertions, 164 deletions

diff --git a/src/liballoc/owned.rs b/src/liballoc/owned.rs
index 33afa806f4e..addec396bbe 100644
--- a/src/liballoc/owned.rs
+++ b/src/liballoc/owned.rs
@@ -18,6 +18,7 @@ use core::fmt;
 use core::intrinsics;
 use core::kinds::Send;
 use core::mem;
+use core::option::Option;
 use core::raw::TraitObject;
 use core::result::{Ok, Err, Result};
 
@@ -65,6 +66,10 @@ impl<T:PartialEq> PartialEq for Box<T> {
 }
 impl<T:PartialOrd> PartialOrd for Box<T> {
     #[inline]
+    fn partial_cmp(&self, other: &Box<T>) -> Option<Ordering> {
+        (**self).partial_cmp(*other)
+    }
+    #[inline]
     fn lt(&self, other: &Box<T>) -> bool { *(*self) < *(*other) }
     #[inline]
     fn le(&self, other: &Box<T>) -> bool { *(*self) <= *(*other) }
diff --git a/src/liballoc/rc.rs b/src/liballoc/rc.rs
index a3ca72f1547..0746f0a0f04 100644
--- a/src/liballoc/rc.rs
+++ b/src/liballoc/rc.rs
@@ -163,6 +163,11 @@ impl<T: Eq> Eq for Rc<T> {}
 
 impl<T: PartialOrd> PartialOrd for Rc<T> {
     #[inline(always)]
+    fn partial_cmp(&self, other: &Rc<T>) -> Option<Ordering> {
+        (**self).partial_cmp(&**other)
+    }
+
+    #[inline(always)]
     fn lt(&self, other: &Rc<T>) -> bool { **self < **other }
 
     #[inline(always)]
diff --git a/src/libcollections/btree.rs b/src/libcollections/btree.rs
index 64bee05a379..92abfaad348 100644
--- a/src/libcollections/btree.rs
+++ b/src/libcollections/btree.rs
@@ -107,8 +107,8 @@ impl<K: Ord, V: Eq> PartialEq for BTree<K, V> {
 impl<K: Ord, V: Eq> Eq for BTree<K, V> {}
 
 impl<K: Ord, V: Eq> PartialOrd for BTree<K, V> {
-    fn lt(&self, other: &BTree<K, V>) -> bool {
-        self.cmp(other) == Less
+    fn partial_cmp(&self, other: &BTree<K, V>) -> Option<Ordering> {
+        Some(self.cmp(other))
     }
 }
 
@@ -229,8 +229,8 @@ impl<K: Ord, V: Eq> PartialEq for Node<K, V> {
 impl<K: Ord, V: Eq> Eq for Node<K, V> {}
 
 impl<K: Ord, V: Eq> PartialOrd for Node<K, V> {
-    fn lt(&self, other: &Node<K, V>) -> bool {
-        self.cmp(other) == Less
+    fn partial_cmp(&self, other: &Node<K, V>) -> Option<Ordering> {
+        Some(self.cmp(other))
     }
 }
 
@@ -408,8 +408,8 @@ impl<K: Ord, V: Eq> PartialEq for Leaf<K, V> {
 impl<K: Ord, V: Eq> Eq for Leaf<K, V> {}
 
 impl<K: Ord, V: Eq> PartialOrd for Leaf<K, V> {
-    fn lt(&self, other: &Leaf<K, V>) -> bool {
-        self.cmp(other) == Less
+    fn partial_cmp(&self, other: &Leaf<K, V>) -> Option<Ordering> {
+        Some(self.cmp(other))
     }
 }
 
@@ -638,8 +638,8 @@ impl<K: Ord, V: Eq> PartialEq for Branch<K, V> {
 impl<K: Ord, V: Eq> Eq for Branch<K, V> {}
 
 impl<K: Ord, V: Eq> PartialOrd for Branch<K, V> {
-    fn lt(&self, other: &Branch<K, V>) -> bool {
-        self.cmp(other) == Less
+    fn partial_cmp(&self, other: &Branch<K, V>) -> Option<Ordering> {
+        Some(self.cmp(other))
     }
 }
 
@@ -706,8 +706,8 @@ impl<K: Ord, V: Eq> PartialEq for LeafElt<K, V> {
 impl<K: Ord, V: Eq> Eq for LeafElt<K, V> {}
 
 impl<K: Ord, V: Eq> PartialOrd for LeafElt<K, V> {
-    fn lt(&self, other: &LeafElt<K, V>) -> bool {
-        self.cmp(other) == Less
+    fn partial_cmp(&self, other: &LeafElt<K, V>) -> Option<Ordering> {
+        Some(self.cmp(other))
     }
 }
 
@@ -755,8 +755,8 @@ impl<K: Ord, V: Eq> PartialEq for BranchElt<K, V>{
 impl<K: Ord, V: Eq> Eq for BranchElt<K, V>{}
 
 impl<K: Ord, V: Eq> PartialOrd for BranchElt<K, V> {
-    fn lt(&self, other: &BranchElt<K, V>) -> bool {
-        self.cmp(other) == Less
+    fn partial_cmp(&self, other: &BranchElt<K, V>) -> Option<Ordering> {
+        Some(self.cmp(other))
     }
 }
 
diff --git a/src/libcollections/dlist.rs b/src/libcollections/dlist.rs
index 7ea5c482e61..4114c8cb1c4 100644
--- a/src/libcollections/dlist.rs
+++ b/src/libcollections/dlist.rs
@@ -595,17 +595,8 @@ impl<A: PartialEq> PartialEq for DList<A> {
 }
 
 impl<A: PartialOrd> PartialOrd for DList<A> {
-    fn lt(&self, other: &DList<A>) -> bool {
-        iter::order::lt(self.iter(), other.iter())
-    }
-    fn le(&self, other: &DList<A>) -> bool {
-        iter::order::le(self.iter(), other.iter())
-    }
-    fn gt(&self, other: &DList<A>) -> bool {
-        iter::order::gt(self.iter(), other.iter())
-    }
-    fn ge(&self, other: &DList<A>) -> bool {
-        iter::order::ge(self.iter(), other.iter())
+    fn partial_cmp(&self, other: &DList<A>) -> Option<Ordering> {
+        iter::order::partial_cmp(self.iter(), other.iter())
     }
 }
 
diff --git a/src/libcollections/str.rs b/src/libcollections/str.rs
index 2d84c733b09..b5424d1683f 100644
--- a/src/libcollections/str.rs
+++ b/src/libcollections/str.rs
@@ -572,8 +572,8 @@ impl<'a> Eq for MaybeOwned<'a> {}
 
 impl<'a> PartialOrd for MaybeOwned<'a> {
     #[inline]
-    fn lt(&self, other: &MaybeOwned) -> bool {
-        self.as_slice().lt(&other.as_slice())
+    fn partial_cmp(&self, other: &MaybeOwned) -> Option<Ordering> {
+        Some(self.cmp(other))
     }
 }
 
diff --git a/src/libcollections/treemap.rs b/src/libcollections/treemap.rs
index 568baa6fc40..becceffe6d0 100644
--- a/src/libcollections/treemap.rs
+++ b/src/libcollections/treemap.rs
@@ -56,23 +56,11 @@ impl<K: PartialEq + Ord, V: PartialEq> PartialEq for TreeMap<K, V> {
     }
 }
 
-// Lexicographical comparison
-fn lt<K: PartialOrd + Ord, V: PartialOrd>(a: &TreeMap<K, V>,
-                                 b: &TreeMap<K, V>) -> bool {
-    // the Zip iterator is as long as the shortest of a and b.
-    for ((key_a, value_a), (key_b, value_b)) in a.iter().zip(b.iter()) {
-        if *key_a < *key_b { return true; }
-        if *key_a > *key_b { return false; }
-        if *value_a < *value_b { return true; }
-        if *value_a > *value_b { return false; }
-    }
-
-    a.len() < b.len()
-}
-
-impl<K: PartialOrd + Ord, V: PartialOrd> PartialOrd for TreeMap<K, V> {
+impl<K: Ord, V: PartialOrd> PartialOrd for TreeMap<K, V> {
     #[inline]
-    fn lt(&self, other: &TreeMap<K, V>) -> bool { lt(self, other) }
+    fn partial_cmp(&self, other: &TreeMap<K, V>) -> Option<Ordering> {
+        iter::order::partial_cmp(self.iter(), other.iter())
+    }
 }
 
 impl<K: Ord + Show, V: Show> Show for TreeMap<K, V> {
@@ -568,9 +556,11 @@ impl<T: PartialEq + Ord> PartialEq for TreeSet<T> {
     fn eq(&self, other: &TreeSet<T>) -> bool { self.map == other.map }
 }
 
-impl<T: PartialOrd + Ord> PartialOrd for TreeSet<T> {
+impl<T: Ord> PartialOrd for TreeSet<T> {
     #[inline]
-    fn lt(&self, other: &TreeSet<T>) -> bool { self.map < other.map }
+    fn partial_cmp(&self, other: &TreeSet<T>) -> Option<Ordering> {
+        self.map.partial_cmp(&other.map)
+    }
 }
 
 impl<T: Ord + Show> Show for TreeSet<T> {
diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs
index 8e6e86ce36e..2ffc168f82c 100644
--- a/src/libcollections/vec.rs
+++ b/src/libcollections/vec.rs
@@ -389,8 +389,8 @@ impl<T: PartialEq> PartialEq for Vec<T> {
 
 impl<T: PartialOrd> PartialOrd for Vec<T> {
     #[inline]
-    fn lt(&self, other: &Vec<T>) -> bool {
-        self.as_slice() < other.as_slice()
+    fn partial_cmp(&self, other: &Vec<T>) -> Option<Ordering> {
+        self.as_slice().partial_cmp(&other.as_slice())
     }
 }
 
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) {
diff --git a/src/libcoretest/iter.rs b/src/libcoretest/iter.rs
index bc55b17b346..86b5ffece41 100644
--- a/src/libcoretest/iter.rs
+++ b/src/libcoretest/iter.rs
@@ -707,8 +707,8 @@ fn test_range() {
     }
 
     impl PartialOrd for Foo {
-        fn lt(&self, _: &Foo) -> bool {
-            false
+        fn partial_cmp(&self, _: &Foo) -> Option<Ordering> {
+            None
         }
     }
 
diff --git a/src/libgraphviz/maybe_owned_vec.rs b/src/libgraphviz/maybe_owned_vec.rs
index 026db9d96f6..bd19f19cec6 100644
--- a/src/libgraphviz/maybe_owned_vec.rs
+++ b/src/libgraphviz/maybe_owned_vec.rs
@@ -73,8 +73,8 @@ impl<'a, T: PartialEq> PartialEq for MaybeOwnedVector<'a, T> {
 impl<'a, T: Eq> Eq for MaybeOwnedVector<'a, T> {}
 
 impl<'a, T: PartialOrd> PartialOrd for MaybeOwnedVector<'a, T> {
-    fn lt(&self, other: &MaybeOwnedVector<T>) -> bool {
-        self.as_slice().lt(&other.as_slice())
+    fn partial_cmp(&self, other: &MaybeOwnedVector<T>) -> Option<Ordering> {
+        self.as_slice().partial_cmp(&other.as_slice())
     }
 }
 
diff --git a/src/libnum/bigint.rs b/src/libnum/bigint.rs
index 9011aafc009..cc3753def59 100644
--- a/src/libnum/bigint.rs
+++ b/src/libnum/bigint.rs
@@ -91,8 +91,8 @@ impl Eq for BigUint {}
 
 impl PartialOrd for BigUint {
     #[inline]
-    fn lt(&self, other: &BigUint) -> bool {
-        self.cmp(other) == Less
+    fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
+        Some(self.cmp(other))
     }
 }
 
@@ -816,8 +816,8 @@ impl Eq for BigInt {}
 
 impl PartialOrd for BigInt {
     #[inline]
-    fn lt(&self, other: &BigInt) -> bool {
-        self.cmp(other) == Less
+    fn partial_cmp(&self, other: &BigInt) -> Option<Ordering> {
+        Some(self.cmp(other))
     }
 }
 
diff --git a/src/libnum/rational.rs b/src/libnum/rational.rs
index 971b6b1b51b..9a455edf2c0 100644
--- a/src/libnum/rational.rs
+++ b/src/libnum/rational.rs
@@ -193,7 +193,8 @@ macro_rules! cmp_impl {
     };
 }
 cmp_impl!(impl PartialEq, eq, ne)
-cmp_impl!(impl PartialOrd, lt, gt, le, ge)
+cmp_impl!(impl PartialOrd, lt -> bool, gt -> bool, le -> bool, ge -> bool,
+          partial_cmp -> Option<cmp::Ordering>)
 cmp_impl!(impl Eq, )
 cmp_impl!(impl Ord, cmp -> cmp::Ordering)
 
diff --git a/src/libsemver/lib.rs b/src/libsemver/lib.rs
index 054a97315ad..675b2e507b3 100644
--- a/src/libsemver/lib.rs
+++ b/src/libsemver/lib.rs
@@ -55,12 +55,12 @@ pub enum Identifier {
 
 impl cmp::PartialOrd for Identifier {
     #[inline]
-    fn lt(&self, other: &Identifier) -> bool {
+    fn partial_cmp(&self, other: &Identifier) -> Option<Ordering> {
         match (self, other) {
-            (&Numeric(a), &Numeric(b)) => a < b,
-            (&Numeric(_), _) => true,
-            (&AlphaNumeric(ref a), &AlphaNumeric(ref b)) => *a < *b,
-            (&AlphaNumeric(_), _) => false
+            (&Numeric(a), &Numeric(ref b)) => a.partial_cmp(b),
+            (&Numeric(_), _) => Some(Less),
+            (&AlphaNumeric(ref a), &AlphaNumeric(ref b)) => a.partial_cmp(b),
+            (&AlphaNumeric(_), _) => Some(Greater)
         }
     }
 }
@@ -130,30 +130,31 @@ impl cmp::PartialEq for Version {
 
 impl cmp::PartialOrd for Version {
     #[inline]
-    fn lt(&self, other: &Version) -> bool {
-
-        self.major < other.major ||
-
-            (self.major == other.major &&
-             self.minor < other.minor) ||
-
-            (self.major == other.major &&
-             self.minor == other.minor &&
-             self.patch < other.patch) ||
-
-            (self.major == other.major &&
-             self.minor == other.minor &&
-             self.patch == other.patch &&
-             // NB: semver spec says 0.0.0-pre < 0.0.0
-             // but the version of ord defined for vec
-             // says that [] < [pre], so we alter it
-             // here.
-             (match (self.pre.len(), other.pre.len()) {
-                 (0, 0) => false,
-                 (0, _) => false,
-                 (_, 0) => true,
-                 (_, _) => self.pre < other.pre
-             }))
+    fn partial_cmp(&self, other: &Version) -> Option<Ordering> {
+        match self.major.partial_cmp(&other.major) {
+            Some(Equal) => {}
+            r => return r,
+        }
+
+        match self.minor.partial_cmp(&other.minor) {
+            Some(Equal) => {}
+            r => return r,
+        }
+
+        match self.patch.partial_cmp(&other.patch) {
+            Some(Equal) => {}
+            r => return r,
+        }
+
+        // NB: semver spec says 0.0.0-pre < 0.0.0
+        // but the version of ord defined for vec
+        // says that [] < [pre] so we alter it here
+        match (self.pre.len(), other.pre.len()) {
+            (0, 0) => Some(Equal),
+            (0, _) => Some(Greater),
+            (_, 0) => Some(Less),
+            (_, _) => self.pre.partial_cmp(&other.pre)
+        }
     }
 }
 
diff --git a/src/libserialize/json.rs b/src/libserialize/json.rs
index d8dd2938b34..9f5f020152f 100644
--- a/src/libserialize/json.rs
+++ b/src/libserialize/json.rs
@@ -244,7 +244,7 @@ use std::vec::Vec;
 use Encodable;
 
 /// Represents a json value
-#[deriving(Clone, PartialEq)]
+#[deriving(Clone, PartialEq, PartialOrd)]
 pub enum Json {
     Number(f64),
     String(String),
@@ -2087,62 +2087,6 @@ impl ::Decoder<DecoderError> for Decoder {
     }
 }
 
-/// Test if two json values are less than one another
-impl PartialOrd for Json {
-    fn lt(&self, other: &Json) -> bool {
-        match *self {
-            Number(f0) => {
-                match *other {
-                    Number(f1) => f0 < f1,
-                    String(_) | Boolean(_) | List(_) | Object(_) |
-                    Null => true
-                }
-            }
-
-            String(ref s0) => {
-                match *other {
-                    Number(_) => false,
-                    String(ref s1) => s0 < s1,
-                    Boolean(_) | List(_) | Object(_) | Null => true
-                }
-            }
-
-            Boolean(b0) => {
-                match *other {
-                    Number(_) | String(_) => false,
-                    Boolean(b1) => b0 < b1,
-                    List(_) | Object(_) | Null => true
-                }
-            }
-
-            List(ref l0) => {
-                match *other {
-                    Number(_) | String(_) | Boolean(_) => false,
-                    List(ref l1) => (*l0) < (*l1),
-                    Object(_) | Null => true
-                }
-            }
-
-            Object(ref d0) => {
-                match *other {
-                    Number(_) | String(_) | Boolean(_) | List(_) => false,
-                    Object(ref d1) => d0 < d1,
-                    Null => true
-                }
-            }
-
-            Null => {
-                match *other {
-                    Number(_) | String(_) | Boolean(_) | List(_) |
-                    Object(_) =>
-                        false,
-                    Null => true
-                }
-            }
-        }
-    }
-}
-
 /// A trait for converting values to JSON
 pub trait ToJson {
     /// Converts the value of `self` to an instance of JSON
diff --git a/src/libstd/gc.rs b/src/libstd/gc.rs
index 44988a23070..80f1cbe6cb2 100644
--- a/src/libstd/gc.rs
+++ b/src/libstd/gc.rs
@@ -24,6 +24,7 @@ use default::Default;
 use fmt;
 use hash;
 use kinds::marker;
+use option::Option;
 use ops::Deref;
 use raw;
 
@@ -59,6 +60,10 @@ impl<T: PartialEq + 'static> PartialEq for Gc<T> {
 }
 impl<T: PartialOrd + 'static> PartialOrd for Gc<T> {
     #[inline]
+    fn partial_cmp(&self, other: &Gc<T>) -> Option<Ordering> {
+        (**self).partial_cmp(&**other)
+    }
+    #[inline]
     fn lt(&self, other: &Gc<T>) -> bool { *(*self) < *(*other) }
     #[inline]
     fn le(&self, other: &Gc<T>) -> bool { *(*self) <= *(*other) }
diff --git a/src/libsyntax/ext/deriving/cmp/ord.rs b/src/libsyntax/ext/deriving/cmp/ord.rs
index 88ebe8a60fa..59cdec1ea88 100644
--- a/src/libsyntax/ext/deriving/cmp/ord.rs
+++ b/src/libsyntax/ext/deriving/cmp/ord.rs
@@ -43,22 +43,116 @@ pub fn expand_deriving_ord(cx: &mut ExtCtxt,
         } }
     );
 
+    let ordering_ty = Literal(Path::new(vec!["std", "cmp", "Ordering"]));
+    let ret_ty = Literal(Path::new_(vec!["std", "option", "Option"],
+                                    None,
+                                    vec![box ordering_ty],
+                                    true));
+
+    let inline = cx.meta_word(span, InternedString::new("inline"));
+    let attrs = vec!(cx.attribute(span, inline));
+
+    let partial_cmp_def = MethodDef {
+        name: "partial_cmp",
+        generics: LifetimeBounds::empty(),
+        explicit_self: borrowed_explicit_self(),
+        args: vec![borrowed_self()],
+        ret_ty: ret_ty,
+        attributes: attrs,
+        const_nonmatching: false,
+        combine_substructure: combine_substructure(|cx, span, substr| {
+            cs_partial_cmp(cx, span, substr)
+        })
+    };
+
     let trait_def = TraitDef {
         span: span,
-        attributes: Vec::new(),
-        path: Path::new(vec!("std", "cmp", "PartialOrd")),
-        additional_bounds: Vec::new(),
+        attributes: vec![],
+        path: Path::new(vec!["std", "cmp", "PartialOrd"]),
+        additional_bounds: vec![],
         generics: LifetimeBounds::empty(),
-        methods: vec!(
+        methods: vec![
+            partial_cmp_def,
             md!("lt", true, false),
             md!("le", true, true),
             md!("gt", false, false),
             md!("ge", false, true)
-        )
+        ]
     };
     trait_def.expand(cx, mitem, item, push)
 }
 
+pub fn some_ordering_const(cx: &mut ExtCtxt, span: Span, cnst: Ordering) -> Gc<ast::Expr> {
+    let cnst = match cnst {
+        Less => "Less",
+        Equal => "Equal",
+        Greater => "Greater"
+    };
+    let ordering = cx.path_global(span,
+                                  vec!(cx.ident_of("std"),
+                                       cx.ident_of("cmp"),
+                                       cx.ident_of(cnst)));
+    let ordering = cx.expr_path(ordering);
+    cx.expr_some(span, ordering)
+}
+
+pub fn cs_partial_cmp(cx: &mut ExtCtxt, span: Span,
+              substr: &Substructure) -> Gc<Expr> {
+    let test_id = cx.ident_of("__test");
+    let equals_expr = some_ordering_const(cx, span, Equal);
+
+    /*
+    Builds:
+
+    let __test = self_field1.partial_cmp(&other_field2);
+    if __test == ::std::option::Some(::std::cmp::Equal) {
+        let __test = self_field2.partial_cmp(&other_field2);
+        if __test == ::std::option::Some(::std::cmp::Equal) {
+            ...
+        } else {
+            __test
+        }
+    } else {
+        __test
+    }
+
+    FIXME #6449: These `if`s could/should be `match`es.
+    */
+    cs_same_method_fold(
+        // 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| {
+            // let __test = new;
+            // if __test == Some(::std::cmp::Equal) {
+            //    old
+            // } else {
+            //    __test
+            // }
+
+            let assign = cx.stmt_let(span, false, test_id, new);
+
+            let cond = cx.expr_binary(span, ast::BiEq,
+                                      cx.expr_ident(span, test_id),
+                                      equals_expr.clone());
+            let if_ = cx.expr_if(span,
+                                 cond,
+                                 old, Some(cx.expr_ident(span, test_id)));
+            cx.expr_block(cx.block(span, vec!(assign), Some(if_)))
+        },
+        equals_expr.clone(),
+        |cx, span, list, _| {
+            match list {
+                // an earlier nonmatching variant is Less than a
+                // later one.
+                [(self_var, _, _), (other_var, _, _)] =>
+                     some_ordering_const(cx, span, self_var.cmp(&other_var)),
+                _ => cx.span_bug(span, "not exactly 2 arguments in `deriving(Ord)`")
+            }
+        },
+        cx, span, substr)
+}
+
 /// Strict inequality.
 fn cs_op(less: bool, equal: bool, cx: &mut ExtCtxt, span: Span,
          substr: &Substructure) -> Gc<Expr> {
diff --git a/src/test/compile-fail/deriving-span-PartialOrd-enum-struct-variant.rs b/src/test/compile-fail/deriving-span-PartialOrd-enum-struct-variant.rs
index 077286eef49..dd6c11d2b39 100644
--- a/src/test/compile-fail/deriving-span-PartialOrd-enum-struct-variant.rs
+++ b/src/test/compile-fail/deriving-span-PartialOrd-enum-struct-variant.rs
@@ -27,6 +27,7 @@ enum Enum {
 //~^^^^^ ERROR
 //~^^^^^^ ERROR
 //~^^^^^^^ ERROR
+//~^^^^^^^^ ERROR
    }
 }
 
diff --git a/src/test/compile-fail/deriving-span-PartialOrd-enum.rs b/src/test/compile-fail/deriving-span-PartialOrd-enum.rs
index 8fd4ba6053e..1b3d73a6f8b 100644
--- a/src/test/compile-fail/deriving-span-PartialOrd-enum.rs
+++ b/src/test/compile-fail/deriving-span-PartialOrd-enum.rs
@@ -27,6 +27,7 @@ enum Enum {
 //~^^^^^ ERROR
 //~^^^^^^ ERROR
 //~^^^^^^^ ERROR
+//~^^^^^^^^ ERROR
      )
 }
 
diff --git a/src/test/compile-fail/deriving-span-PartialOrd-struct.rs b/src/test/compile-fail/deriving-span-PartialOrd-struct.rs
index 3a198a542e4..2ef3b4dfe8a 100644
--- a/src/test/compile-fail/deriving-span-PartialOrd-struct.rs
+++ b/src/test/compile-fail/deriving-span-PartialOrd-struct.rs
@@ -26,6 +26,7 @@ struct Struct {
 //~^^^^^ ERROR
 //~^^^^^^ ERROR
 //~^^^^^^^ ERROR
+//~^^^^^^^^ ERROR
 }
 
 fn main() {}
diff --git a/src/test/compile-fail/deriving-span-PartialOrd-tuple-struct.rs b/src/test/compile-fail/deriving-span-PartialOrd-tuple-struct.rs
index 2de3c18425b..303896737dc 100644
--- a/src/test/compile-fail/deriving-span-PartialOrd-tuple-struct.rs
+++ b/src/test/compile-fail/deriving-span-PartialOrd-tuple-struct.rs
@@ -26,6 +26,7 @@ struct Struct(
 //~^^^^^ ERROR
 //~^^^^^^ ERROR
 //~^^^^^^^ ERROR
+//~^^^^^^^^ ERROR
 );
 
 fn main() {}
diff --git a/src/test/compile-fail/issue-3344.rs b/src/test/compile-fail/issue-3344.rs
index d6fe83a7703..293f372866d 100644
--- a/src/test/compile-fail/issue-3344.rs
+++ b/src/test/compile-fail/issue-3344.rs
@@ -10,7 +10,7 @@
 
 #[deriving(PartialEq)]
 struct thing(uint);
-impl PartialOrd for thing { //~ ERROR not all trait methods implemented, missing: `lt`
+impl PartialOrd for thing { //~ ERROR not all trait methods implemented, missing: `partial_cmp`
     fn le(&self, other: &thing) -> bool { true }
     fn ge(&self, other: &thing) -> bool { true }
 }
diff --git a/src/test/run-pass/cmp-default.rs b/src/test/run-pass/cmp-default.rs
index 7805a2bb49e..cfba87c3f69 100644
--- a/src/test/run-pass/cmp-default.rs
+++ b/src/test/run-pass/cmp-default.rs
@@ -31,10 +31,10 @@ impl PartialEq for Int {
 }
 
 impl PartialOrd for Int {
-    fn lt(&self, other: &Int) -> bool {
+    fn partial_cmp(&self, other: &Int) -> Option<Ordering> {
         let Int(this) = *self;
         let Int(other) = *other;
-        this < other
+        this.partial_cmp(&other)
     }
 }
 
@@ -49,10 +49,10 @@ impl PartialEq for RevInt {
 }
 
 impl PartialOrd for RevInt {
-    fn lt(&self, other: &RevInt) -> bool {
+    fn partial_cmp(&self, other: &RevInt) -> Option<Ordering> {
         let RevInt(this) = *self;
         let RevInt(other) = *other;
-        this > other
+        other.partial_cmp(&this)
     }
 }
 
diff --git a/src/test/run-pass/deriving-cmp-shortcircuit.rs b/src/test/run-pass/deriving-cmp-shortcircuit.rs
index 69ee47fd1d9..df5c58ff04b 100644
--- a/src/test/run-pass/deriving-cmp-shortcircuit.rs
+++ b/src/test/run-pass/deriving-cmp-shortcircuit.rs
@@ -18,7 +18,7 @@ impl PartialEq for FailCmp {
 }
 
 impl PartialOrd for FailCmp {
-    fn lt(&self, _: &FailCmp) -> bool { fail!("lt") }
+    fn partial_cmp(&self, _: &FailCmp) -> Option<Ordering> { fail!("partial_cmp") }
 }
 
 impl Eq for FailCmp {}