auto merge of #19167 : japaric/rust/rhs-cmp, r=aturon

Comparison traits have gained an `Rhs` input parameter that defaults to `Self`. And now the comparison operators can be overloaded to work between different types. In particular, this PR allows the following operations (and their commutative versions):

- `&str` == `String` == `CowString`
- `&[A]` == `&mut [B]` == `Vec<C>` == `CowVec<D>` == `[E, ..N]` (for `N` up to 32)
- `&mut A` == `&B` (for `Sized` `A` and `B`)

Where `A`, `B`, `C`, `D`, `E` may be different types that implement `PartialEq`. For example, these comparisons are now valid: `string == "foo"`, and `vec_of_strings == ["Hello", "world"]`.

[breaking-change]s

Since the `==` may now work on different types, operations that relied on the old "same type restriction" to drive type inference, will need to be type annotated. These are the most common fallout cases:

- `some_vec == some_iter.collect()`: `collect` needs to be type annotated: `collect::<Vec<_>>()`
- `slice == &[a, b, c]`: RHS doesn't get coerced to an slice, use an array instead `[a, b, c]`
- `lhs == []`: Change expression to `lhs.is_empty()`
- `lhs == some_generic_function()`: Type annotate the RHS as necessary

cc #19148

r? @aturon 

11 files changed, 99 insertions, 44 deletions

diff --git a/src/libcore/array.rs b/src/libcore/array.rs
index 60765e82cb4..ffaf35414ea 100644
--- a/src/libcore/array.rs
+++ b/src/libcore/array.rs
@@ -18,6 +18,7 @@ use clone::Clone;
 use cmp::{PartialEq, Eq, PartialOrd, Ord, Ordering};
 use fmt;
 use kinds::Copy;
+use ops::Deref;
 use option::Option;
 
 // macro for implementing n-ary tuple functions and operations
@@ -39,17 +40,37 @@ macro_rules! array_impls {
             }
 
             #[unstable = "waiting for PartialEq to stabilize"]
-            impl<T:PartialEq> PartialEq for [T, ..$N] {
+            impl<A, B> PartialEq<[B, ..$N]> for [A, ..$N] where A: PartialEq<B> {
                 #[inline]
-                fn eq(&self, other: &[T, ..$N]) -> bool {
+                fn eq(&self, other: &[B, ..$N]) -> bool {
                     self[] == other[]
                 }
                 #[inline]
-                fn ne(&self, other: &[T, ..$N]) -> bool {
+                fn ne(&self, other: &[B, ..$N]) -> bool {
                     self[] != other[]
                 }
             }
 
+            impl<'a, A, B, Rhs> PartialEq<Rhs> for [A, ..$N] where
+                A: PartialEq<B>,
+                Rhs: Deref<[B]>,
+            {
+                #[inline(always)]
+                fn eq(&self, other: &Rhs) -> bool { PartialEq::eq(self[], &**other) }
+                #[inline(always)]
+                fn ne(&self, other: &Rhs) -> bool { PartialEq::ne(self[], &**other) }
+            }
+
+            impl<'a, A, B, Lhs> PartialEq<[B, ..$N]> for Lhs where
+                A: PartialEq<B>,
+                Lhs: Deref<[A]>
+            {
+                #[inline(always)]
+                fn eq(&self, other: &[B, ..$N]) -> bool { PartialEq::eq(&**self, other[]) }
+                #[inline(always)]
+                fn ne(&self, other: &[B, ..$N]) -> bool { PartialEq::ne(&**self, other[]) }
+            }
+
             #[unstable = "waiting for Eq to stabilize"]
             impl<T:Eq> Eq for [T, ..$N] { }
 
diff --git a/src/libcore/borrow.rs b/src/libcore/borrow.rs
index 06fda8d6092..b88fb914dd8 100644
--- a/src/libcore/borrow.rs
+++ b/src/libcore/borrow.rs
@@ -196,9 +196,12 @@ impl<'a, T, Sized? B> Ord for Cow<'a, T, B> where B: Ord + ToOwned<T> {
     }
 }
 
-impl<'a, T, Sized? B> PartialEq for Cow<'a, T, B> where B: PartialEq + ToOwned<T> {
+impl<'a, 'b, T, U, Sized? B, Sized? C> PartialEq<Cow<'b, U, C>> for Cow<'a, T, B> where
+    B: PartialEq<C> + ToOwned<T>,
+    C: ToOwned<U>,
+{
     #[inline]
-    fn eq(&self, other: &Cow<'a, T, B>) -> bool {
+    fn eq(&self, other: &Cow<'b, U, C>) -> bool {
         PartialEq::eq(&**self, &**other)
     }
 }
diff --git a/src/libcore/cmp.rs b/src/libcore/cmp.rs
index 51122d0a170..df19256471e 100644
--- a/src/libcore/cmp.rs
+++ b/src/libcore/cmp.rs
@@ -61,13 +61,13 @@ use option::{Option, Some, None};
 /// `Eq`.
 #[lang="eq"]
 #[unstable = "Definition may change slightly after trait reform"]
-pub trait PartialEq for Sized? {
+pub trait PartialEq<Sized? Rhs = Self> for Sized? {
     /// This method tests for `self` and `other` values to be equal, and is used by `==`.
-    fn eq(&self, other: &Self) -> bool;
+    fn eq(&self, other: &Rhs) -> bool;
 
     /// This method tests for `!=`.
     #[inline]
-    fn ne(&self, other: &Self) -> bool { !self.eq(other) }
+    fn ne(&self, other: &Rhs) -> bool { !self.eq(other) }
 }
 
 /// Trait for equality comparisons which are [equivalence relations](
@@ -80,7 +80,7 @@ pub trait PartialEq for Sized? {
 /// - symmetric: `a == b` implies `b == a`; and
 /// - transitive: `a == b` and `b == c` implies `a == c`.
 #[unstable = "Definition may change slightly after trait reform"]
-pub trait Eq for Sized?: PartialEq {
+pub trait Eq<Sized? Rhs = Self> for Sized?: PartialEq<Rhs> {
     // FIXME #13101: this method is used solely by #[deriving] to
     // assert that every component of a type implements #[deriving]
     // itself, the current deriving infrastructure means doing this
@@ -150,7 +150,7 @@ impl Ordering {
 /// - transitive, `a < b` and `b < c` implies `a < c`. The same must hold for
 ///   both `==` and `>`.
 #[unstable = "Definition may change slightly after trait reform"]
-pub trait Ord for Sized?: Eq + PartialOrd {
+pub trait Ord<Sized? Rhs = Self> for Sized?: Eq<Rhs> + PartialOrd<Rhs> {
     /// This method returns an ordering between `self` and `other` values.
     ///
     /// By convention, `self.cmp(&other)` returns the ordering matching
@@ -161,7 +161,7 @@ pub trait Ord for Sized?: Eq + PartialOrd {
     /// assert_eq!(10u.cmp(&5),  Greater);  // because 10 > 5
     /// assert_eq!( 5u.cmp(&5),  Equal);    // because 5 == 5
     /// ```
-    fn cmp(&self, other: &Self) -> Ordering;
+    fn cmp(&self, other: &Rhs) -> Ordering;
 }
 
 #[unstable = "Trait is unstable."]
@@ -194,14 +194,14 @@ impl PartialOrd for Ordering {
 /// 5.11).
 #[lang="ord"]
 #[unstable = "Definition may change slightly after trait reform"]
-pub trait PartialOrd for Sized?: PartialEq {
+pub trait PartialOrd<Sized? Rhs = Self> for Sized?: PartialEq<Rhs> {
     /// This method returns an ordering between `self` and `other` values
     /// if one exists.
-    fn partial_cmp(&self, other: &Self) -> Option<Ordering>;
+    fn partial_cmp(&self, other: &Rhs) -> Option<Ordering>;
 
     /// This method tests less than (for `self` and `other`) and is used by the `<` operator.
     #[inline]
-    fn lt(&self, other: &Self) -> bool {
+    fn lt(&self, other: &Rhs) -> bool {
         match self.partial_cmp(other) {
             Some(Less) => true,
             _ => false,
@@ -210,7 +210,7 @@ pub trait PartialOrd for Sized?: PartialEq {
 
     /// This method tests less than or equal to (`<=`).
     #[inline]
-    fn le(&self, other: &Self) -> bool {
+    fn le(&self, other: &Rhs) -> bool {
         match self.partial_cmp(other) {
             Some(Less) | Some(Equal) => true,
             _ => false,
@@ -219,7 +219,7 @@ pub trait PartialOrd for Sized?: PartialEq {
 
     /// This method tests greater than (`>`).
     #[inline]
-    fn gt(&self, other: &Self) -> bool {
+    fn gt(&self, other: &Rhs) -> bool {
         match self.partial_cmp(other) {
             Some(Greater) => true,
             _ => false,
@@ -228,7 +228,7 @@ pub trait PartialOrd for Sized?: PartialEq {
 
     /// This method tests greater than or equal to (`>=`).
     #[inline]
-    fn ge(&self, other: &Self) -> bool {
+    fn ge(&self, other: &Rhs) -> bool {
         match self.partial_cmp(other) {
             Some(Greater) | Some(Equal) => true,
             _ => false,
@@ -240,7 +240,7 @@ pub trait PartialOrd for Sized?: PartialEq {
 /// of different types. The most common use case for this relation is
 /// container types; e.g. it is often desirable to be able to use `&str`
 /// values to look up entries in a container with `String` keys.
-#[experimental = "Better solutions may be discovered."]
+#[deprecated = "Use overloaded core::cmp::PartialEq"]
 pub trait Equiv<Sized? T> for Sized? {
     /// Implement this function to decide equivalent values.
     fn equiv(&self, other: &T) -> bool;
@@ -400,11 +400,11 @@ mod impls {
     // & pointers
 
     #[unstable = "Trait is unstable."]
-    impl<'a, Sized? T: PartialEq> PartialEq for &'a T {
+    impl<'a, 'b, Sized? A, Sized? B> PartialEq<&'b B> for &'a A where A: PartialEq<B> {
         #[inline]
-        fn eq(&self, other: & &'a T) -> bool { PartialEq::eq(*self, *other) }
+        fn eq(&self, other: & &'b B) -> bool { PartialEq::eq(*self, *other) }
         #[inline]
-        fn ne(&self, other: & &'a T) -> bool { PartialEq::ne(*self, *other) }
+        fn ne(&self, other: & &'b B) -> bool { PartialEq::ne(*self, *other) }
     }
     #[unstable = "Trait is unstable."]
     impl<'a, Sized? T: PartialOrd> PartialOrd for &'a T {
@@ -432,11 +432,11 @@ mod impls {
     // &mut pointers
 
     #[unstable = "Trait is unstable."]
-    impl<'a, Sized? T: PartialEq> PartialEq for &'a mut T {
+    impl<'a, 'b, Sized? A, Sized? B> PartialEq<&'b mut B> for &'a mut A where A: PartialEq<B> {
         #[inline]
-        fn eq(&self, other: &&'a mut T) -> bool { PartialEq::eq(*self, *other) }
+        fn eq(&self, other: &&'b mut B) -> bool { PartialEq::eq(*self, *other) }
         #[inline]
-        fn ne(&self, other: &&'a mut T) -> bool { PartialEq::ne(*self, *other) }
+        fn ne(&self, other: &&'b mut B) -> bool { PartialEq::ne(*self, *other) }
     }
     #[unstable = "Trait is unstable."]
     impl<'a, Sized? T: PartialOrd> PartialOrd for &'a mut T {
@@ -460,4 +460,18 @@ mod impls {
     }
     #[unstable = "Trait is unstable."]
     impl<'a, Sized? T: Eq> Eq for &'a mut T {}
+
+    impl<'a, 'b, Sized? A, Sized? B> PartialEq<&'b mut B> for &'a A where A: PartialEq<B> {
+        #[inline]
+        fn eq(&self, other: &&'b mut B) -> bool { PartialEq::eq(*self, *other) }
+        #[inline]
+        fn ne(&self, other: &&'b mut B) -> bool { PartialEq::ne(*self, *other) }
+    }
+
+    impl<'a, 'b, Sized? A, Sized? B> PartialEq<&'b B> for &'a mut A where A: PartialEq<B> {
+        #[inline]
+        fn eq(&self, other: &&'b B) -> bool { PartialEq::eq(*self, *other) }
+        #[inline]
+        fn ne(&self, other: &&'b B) -> bool { PartialEq::ne(*self, *other) }
+    }
 }
diff --git a/src/libcore/intrinsics.rs b/src/libcore/intrinsics.rs
index 78c74075d48..347777b587a 100644
--- a/src/libcore/intrinsics.rs
+++ b/src/libcore/intrinsics.rs
@@ -226,7 +226,7 @@ extern "rust-intrinsic" {
     /// use std::mem;
     ///
     /// let v: &[u8] = unsafe { mem::transmute("L") };
-    /// assert!(v == &[76u8]);
+    /// assert!(v == [76u8]);
     /// ```
     pub fn transmute<T,U>(e: T) -> U;
 
diff --git a/src/libcore/iter.rs b/src/libcore/iter.rs
index 2d488a4b155..f9595f0663d 100644
--- a/src/libcore/iter.rs
+++ b/src/libcore/iter.rs
@@ -2473,7 +2473,11 @@ pub mod order {
     }
 
     /// 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 {
+    pub fn eq<A, B, L, R>(mut a: L, mut b: R) -> bool where
+        A: PartialEq<B>,
+        L: Iterator<A>,
+        R: Iterator<B>,
+    {
         loop {
             match (a.next(), b.next()) {
                 (None, None) => return true,
@@ -2484,7 +2488,11 @@ pub mod order {
     }
 
     /// Compare `a` and `b` for nonequality (Using partial equality, `PartialEq`)
-    pub fn ne<A: PartialEq, T: Iterator<A>, S: Iterator<A>>(mut a: T, mut b: S) -> bool {
+    pub fn ne<A, B, L, R>(mut a: L, mut b: R) -> bool where
+        A: PartialEq<B>,
+        L: Iterator<A>,
+        R: Iterator<B>,
+    {
         loop {
             match (a.next(), b.next()) {
                 (None, None) => return false,
diff --git a/src/libcore/lib.rs b/src/libcore/lib.rs
index 56a86773060..5ad9462daf2 100644
--- a/src/libcore/lib.rs
+++ b/src/libcore/lib.rs
@@ -59,6 +59,7 @@
 #![allow(unknown_features)]
 #![feature(globs, intrinsics, lang_items, macro_rules, phase)]
 #![feature(simd, unsafe_destructor, slicing_syntax)]
+#![feature(default_type_params)]
 #![deny(missing_docs)]
 
 mod macros;
diff --git a/src/libcore/option.rs b/src/libcore/option.rs
index 7d7b41bf7bf..ef895a1d7fb 100644
--- a/src/libcore/option.rs
+++ b/src/libcore/option.rs
@@ -274,9 +274,9 @@ impl<T> Option<T> {
     /// let mut x = Some("Diamonds");
     /// {
     ///     let v = x.as_mut_slice();
-    ///     assert!(v == &mut ["Diamonds"]);
+    ///     assert!(v == ["Diamonds"]);
     ///     v[0] = "Dirt";
-    ///     assert!(v == &mut ["Dirt"]);
+    ///     assert!(v == ["Dirt"]);
     /// }
     /// assert_eq!(x, Some("Dirt"));
     /// ```
@@ -554,7 +554,7 @@ impl<T> Option<T> {
     ///
     /// let x = None;
     /// let v: Vec<&str> = x.into_iter().collect();
-    /// assert_eq!(v, vec![]);
+    /// assert!(v.is_empty());
     /// ```
     #[inline]
     #[unstable = "waiting for iterator conventions"]
diff --git a/src/libcore/ptr.rs b/src/libcore/ptr.rs
index 5e2f5529e8d..416bc4588b4 100644
--- a/src/libcore/ptr.rs
+++ b/src/libcore/ptr.rs
@@ -321,12 +321,16 @@ impl<T> PartialEq for *mut T {
 impl<T> Eq for *mut T {}
 
 // Equivalence for pointers
+#[allow(deprecated)]
+#[deprecated = "Use overloaded `core::cmp::PartialEq`"]
 impl<T> Equiv<*mut T> for *const T {
     fn equiv(&self, other: &*mut T) -> bool {
         self.to_uint() == other.to_uint()
     }
 }
 
+#[allow(deprecated)]
+#[deprecated = "Use overloaded `core::cmp::PartialEq`"]
 impl<T> Equiv<*const T> for *mut T {
     fn equiv(&self, other: &*const T) -> bool {
         self.to_uint() == other.to_uint()
diff --git a/src/libcore/result.rs b/src/libcore/result.rs
index 202ac464497..07bb6f15c94 100644
--- a/src/libcore/result.rs
+++ b/src/libcore/result.rs
@@ -407,14 +407,14 @@ impl<T, E> Result<T, E> {
     /// let mut x: Result<&str, uint> = Ok("Gold");
     /// {
     ///     let v = x.as_mut_slice();
-    ///     assert!(v == &mut ["Gold"]);
+    ///     assert!(v == ["Gold"]);
     ///     v[0] = "Silver";
-    ///     assert!(v == &mut ["Silver"]);
+    ///     assert!(v == ["Silver"]);
     /// }
     /// assert_eq!(x, Ok("Silver"));
     ///
     /// let mut x: Result<&str, uint> = Err(45);
-    /// assert!(x.as_mut_slice() == &mut []);
+    /// assert!(x.as_mut_slice().is_empty());
     /// ```
     #[inline]
     #[unstable = "waiting for mut conventions"]
diff --git a/src/libcore/slice.rs b/src/libcore/slice.rs
index 950f04a5d97..85bd6adf8b8 100644
--- a/src/libcore/slice.rs
+++ b/src/libcore/slice.rs
@@ -374,20 +374,20 @@ pub trait SlicePrelude<T> for Sized? {
     /// // scoped to restrict the lifetime of the borrows
     /// {
     ///    let (left, right) = v.split_at_mut(0);
-    ///    assert!(left == &mut []);
-    ///    assert!(right == &mut [1i, 2, 3, 4, 5, 6]);
+    ///    assert!(left == []);
+    ///    assert!(right == [1i, 2, 3, 4, 5, 6]);
     /// }
     ///
     /// {
     ///     let (left, right) = v.split_at_mut(2);
-    ///     assert!(left == &mut [1i, 2]);
-    ///     assert!(right == &mut [3i, 4, 5, 6]);
+    ///     assert!(left == [1i, 2]);
+    ///     assert!(right == [3i, 4, 5, 6]);
     /// }
     ///
     /// {
     ///     let (left, right) = v.split_at_mut(6);
-    ///     assert!(left == &mut [1i, 2, 3, 4, 5, 6]);
-    ///     assert!(right == &mut []);
+    ///     assert!(left == [1i, 2, 3, 4, 5, 6]);
+    ///     assert!(right == []);
     /// }
     /// ```
     #[unstable = "waiting on final error conventions"]
@@ -1802,12 +1802,12 @@ pub mod bytes {
 //
 
 #[unstable = "waiting for DST"]
-impl<T: PartialEq> PartialEq for [T] {
-    fn eq(&self, other: &[T]) -> bool {
+impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
+    fn eq(&self, other: &[B]) -> bool {
         self.len() == other.len() &&
             order::eq(self.iter(), other.iter())
     }
-    fn ne(&self, other: &[T]) -> bool {
+    fn ne(&self, other: &[B]) -> bool {
         self.len() != other.len() ||
             order::ne(self.iter(), other.iter())
     }
@@ -1816,13 +1816,15 @@ impl<T: PartialEq> PartialEq for [T] {
 #[unstable = "waiting for DST"]
 impl<T: Eq> Eq for [T] {}
 
-#[unstable = "waiting for DST"]
+#[allow(deprecated)]
+#[deprecated = "Use overloaded `core::cmp::PartialEq`"]
 impl<T: PartialEq, Sized? V: AsSlice<T>> Equiv<V> for [T] {
     #[inline]
     fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
 }
 
-#[unstable = "waiting for DST"]
+#[allow(deprecated)]
+#[deprecated = "Use overloaded `core::cmp::PartialEq`"]
 impl<'a,T:PartialEq, Sized? V: AsSlice<T>> Equiv<V> for &'a mut [T] {
     #[inline]
     fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
diff --git a/src/libcore/str.rs b/src/libcore/str.rs
index b9586399aec..4be628f0ac3 100644
--- a/src/libcore/str.rs
+++ b/src/libcore/str.rs
@@ -1248,6 +1248,8 @@ pub mod traits {
         }
     }
 
+    #[allow(deprecated)]
+    #[deprecated = "Use overloaded `core::cmp::PartialEq`"]
     impl<S: Str> Equiv<S> for str {
         #[inline]
         fn equiv(&self, other: &S) -> bool { eq_slice(self, other.as_slice()) }