4 files changed, 33 insertions, 5 deletions
diff --git a/src/librustc/traits/project.rs b/src/librustc/traits/project.rs
index 355216f8c1a..f3a4c25f7c5 100644
--- a/src/librustc/traits/project.rs
+++ b/src/librustc/traits/project.rs
@@ -101,7 +101,7 @@ pub struct MismatchedProjectionTypes<'tcx> {
     pub err: ty::error::TypeError<'tcx>
 }
 
-#[derive(PartialEq, Eq, Debug)]
+#[derive(PartialEq, Eq, PartialOrd, Ord, Debug)]
 enum ProjectionTyCandidate<'tcx> {
     // from a where-clause in the env or object type
     ParamEnv(ty::PolyProjectionPredicate<'tcx>),
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 2b4d2c80c6f..4ce8c09a600 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -39,6 +39,7 @@ use util::nodemap::{NodeSet, DefIdMap, FxHashMap, FxHashSet};
 use serialize::{self, Encodable, Encoder};
 use std::collections::BTreeMap;
 use std::cmp;
+use std::cmp::Ordering;
 use std::fmt;
 use std::hash::{Hash, Hasher};
 use std::iter::FromIterator;
@@ -497,6 +498,20 @@ impl<'tcx> Hash for TyS<'tcx> {
     }
 }
 
+impl<'tcx> Ord for TyS<'tcx> {
+    #[inline]
+    fn cmp(&self, other: &TyS<'tcx>) -> Ordering {
+        // (self as *const _).cmp(other as *const _)
+        (self as *const TyS<'tcx>).cmp(&(other as *const TyS<'tcx>))
+    }
+}
+impl<'tcx> PartialOrd for TyS<'tcx> {
+    #[inline]
+    fn partial_cmp(&self, other: &TyS<'tcx>) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
 impl<'tcx> TyS<'tcx> {
     pub fn is_primitive_ty(&self) -> bool {
         match self.sty {
@@ -566,6 +581,19 @@ impl<T> PartialEq for Slice<T> {
 }
 impl<T> Eq for Slice<T> {}
 
+impl<T> Ord for Slice<T> {
+    #[inline]
+    fn cmp(&self, other: &Slice<T>) -> Ordering {
+        (&self.0 as *const [T]).cmp(&(&other.0 as *const [T]))
+    }
+}
+impl<T> PartialOrd for Slice<T> {
+    #[inline]
+    fn partial_cmp(&self, other: &Slice<T>) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
 impl<T> Hash for Slice<T> {
     fn hash<H: Hasher>(&self, s: &mut H) {
         (self.as_ptr(), self.len()).hash(s)
@@ -1101,7 +1129,7 @@ pub type PolySubtypePredicate<'tcx> = ty::Binder<SubtypePredicate<'tcx>>;
 /// equality between arbitrary types. Processing an instance of
 /// Form #2 eventually yields one of these `ProjectionPredicate`
 /// instances to normalize the LHS.
-#[derive(Copy, Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
+#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable)]
 pub struct ProjectionPredicate<'tcx> {
     pub projection_ty: ProjectionTy<'tcx>,
     pub ty: Ty<'tcx>,
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index 0889efdc142..55caffa2caf 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -646,7 +646,7 @@ impl<'tcx> PolyExistentialTraitRef<'tcx> {
 /// erase, or otherwise "discharge" these bound regions, we change the
 /// type from `Binder<T>` to just `T` (see
 /// e.g. `liberate_late_bound_regions`).
-#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, RustcEncodable, RustcDecodable)]
+#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, RustcEncodable, RustcDecodable)]
 pub struct Binder<T>(pub T);
 
 impl<T> Binder<T> {
@@ -746,7 +746,7 @@ impl<T> Binder<T> {
 
 /// Represents the projection of an associated type. In explicit UFCS
 /// form this would be written `<T as Trait<..>>::N`.
-#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, RustcEncodable, RustcDecodable)]
+#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, RustcEncodable, RustcDecodable)]
 pub struct ProjectionTy<'tcx> {
     /// The parameters of the associated item.
     pub substs: &'tcx Substs<'tcx>,
diff --git a/src/librustc/ty/subst.rs b/src/librustc/ty/subst.rs
index 80b113dfdf5..7c167f69ebd 100644
--- a/src/librustc/ty/subst.rs
+++ b/src/librustc/ty/subst.rs
@@ -29,7 +29,7 @@ use std::mem;
 /// To reduce memory usage, a `Kind` is a interned pointer,
 /// with the lowest 2 bits being reserved for a tag to
 /// indicate the type (`Ty` or `Region`) it points to.
-#[derive(Copy, Clone, PartialEq, Eq, Hash)]
+#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub struct Kind<'tcx> {
     ptr: NonZero<usize>,
     marker: PhantomData<(Ty<'tcx>, ty::Region<'tcx>)>