Auto merge of #32794 - Manishearth:rollup, r=Manishearth

Rollup of 7 pull requests

- Successful merges: #32674, #32699, #32711, #32745, #32748, #32757, #32789
- Failed merges:

4 files changed, 155 insertions, 50 deletions

diff --git a/src/libcore/lib.rs b/src/libcore/lib.rs
index 648b652772a..fa5e90562d8 100644
--- a/src/libcore/lib.rs
+++ b/src/libcore/lib.rs
@@ -75,6 +75,7 @@
 #![feature(unwind_attributes)]
 #![feature(repr_simd, platform_intrinsics)]
 #![feature(rustc_attrs)]
+#![feature(specialization)]
 #![feature(staged_api)]
 #![feature(unboxed_closures)]
 #![feature(question_mark)]
diff --git a/src/libcore/slice.rs b/src/libcore/slice.rs
index aa555b44e89..25082eed2fe 100644
--- a/src/libcore/slice.rs
+++ b/src/libcore/slice.rs
@@ -1630,12 +1630,60 @@ pub unsafe fn from_raw_parts_mut<'a, T>(p: *mut T, len: usize) -> &'a mut [T] {
 }
 
 //
-// Boilerplate traits
+// Comparison traits
 //
 
+extern {
+    /// Call implementation provided memcmp
+    ///
+    /// Interprets the data as u8.
+    ///
+    /// Return 0 for equal, < 0 for less than and > 0 for greater
+    /// than.
+    // FIXME(#32610): Return type should be c_int
+    fn memcmp(s1: *const u8, s2: *const u8, n: usize) -> i32;
+}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
     fn eq(&self, other: &[B]) -> bool {
+        SlicePartialEq::equal(self, other)
+    }
+
+    fn ne(&self, other: &[B]) -> bool {
+        SlicePartialEq::not_equal(self, other)
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T: Eq> Eq for [T] {}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T: Ord> Ord for [T] {
+    fn cmp(&self, other: &[T]) -> Ordering {
+        SliceOrd::compare(self, other)
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T: PartialOrd> PartialOrd for [T] {
+    fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
+        SlicePartialOrd::partial_compare(self, other)
+    }
+}
+
+#[doc(hidden)]
+// intermediate trait for specialization of slice's PartialEq
+trait SlicePartialEq<B> {
+    fn equal(&self, other: &[B]) -> bool;
+    fn not_equal(&self, other: &[B]) -> bool;
+}
+
+// Generic slice equality
+impl<A, B> SlicePartialEq<B> for [A]
+    where A: PartialEq<B>
+{
+    default fn equal(&self, other: &[B]) -> bool {
         if self.len() != other.len() {
             return false;
         }
@@ -1648,7 +1696,8 @@ impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
 
         true
     }
-    fn ne(&self, other: &[B]) -> bool {
+
+    default fn not_equal(&self, other: &[B]) -> bool {
         if self.len() != other.len() {
             return true;
         }
@@ -1663,12 +1712,36 @@ impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
     }
 }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<T: Eq> Eq for [T] {}
+// Use memcmp for bytewise equality when the types allow
+impl<A> SlicePartialEq<A> for [A]
+    where A: PartialEq<A> + BytewiseEquality
+{
+    fn equal(&self, other: &[A]) -> bool {
+        if self.len() != other.len() {
+            return false;
+        }
+        unsafe {
+            let size = mem::size_of_val(self);
+            memcmp(self.as_ptr() as *const u8,
+                   other.as_ptr() as *const u8, size) == 0
+        }
+    }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<T: Ord> Ord for [T] {
-    fn cmp(&self, other: &[T]) -> Ordering {
+    fn not_equal(&self, other: &[A]) -> bool {
+        !self.equal(other)
+    }
+}
+
+#[doc(hidden)]
+// intermediate trait for specialization of slice's PartialOrd
+trait SlicePartialOrd<B> {
+    fn partial_compare(&self, other: &[B]) -> Option<Ordering>;
+}
+
+impl<A> SlicePartialOrd<A> for [A]
+    where A: PartialOrd
+{
+    default fn partial_compare(&self, other: &[A]) -> Option<Ordering> {
         let l = cmp::min(self.len(), other.len());
 
         // Slice to the loop iteration range to enable bound check
@@ -1677,19 +1750,33 @@ impl<T: Ord> Ord for [T] {
         let rhs = &other[..l];
 
         for i in 0..l {
-            match lhs[i].cmp(&rhs[i]) {
-                Ordering::Equal => (),
+            match lhs[i].partial_cmp(&rhs[i]) {
+                Some(Ordering::Equal) => (),
                 non_eq => return non_eq,
             }
         }
 
-        self.len().cmp(&other.len())
+        self.len().partial_cmp(&other.len())
     }
 }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<T: PartialOrd> PartialOrd for [T] {
-    fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
+impl SlicePartialOrd<u8> for [u8] {
+    #[inline]
+    fn partial_compare(&self, other: &[u8]) -> Option<Ordering> {
+        Some(SliceOrd::compare(self, other))
+    }
+}
+
+#[doc(hidden)]
+// intermediate trait for specialization of slice's Ord
+trait SliceOrd<B> {
+    fn compare(&self, other: &[B]) -> Ordering;
+}
+
+impl<A> SliceOrd<A> for [A]
+    where A: Ord
+{
+    default fn compare(&self, other: &[A]) -> Ordering {
         let l = cmp::min(self.len(), other.len());
 
         // Slice to the loop iteration range to enable bound check
@@ -1698,12 +1785,48 @@ impl<T: PartialOrd> PartialOrd for [T] {
         let rhs = &other[..l];
 
         for i in 0..l {
-            match lhs[i].partial_cmp(&rhs[i]) {
-                Some(Ordering::Equal) => (),
+            match lhs[i].cmp(&rhs[i]) {
+                Ordering::Equal => (),
                 non_eq => return non_eq,
             }
         }
 
-        self.len().partial_cmp(&other.len())
+        self.len().cmp(&other.len())
     }
 }
+
+// memcmp compares a sequence of unsigned bytes lexicographically.
+// this matches the order we want for [u8], but no others (not even [i8]).
+impl SliceOrd<u8> for [u8] {
+    #[inline]
+    fn compare(&self, other: &[u8]) -> Ordering {
+        let order = unsafe {
+            memcmp(self.as_ptr(), other.as_ptr(),
+                   cmp::min(self.len(), other.len()))
+        };
+        if order == 0 {
+            self.len().cmp(&other.len())
+        } else if order < 0 {
+            Less
+        } else {
+            Greater
+        }
+    }
+}
+
+#[doc(hidden)]
+/// Trait implemented for types that can be compared for equality using
+/// their bytewise representation
+trait BytewiseEquality { }
+
+macro_rules! impl_marker_for {
+    ($traitname:ident, $($ty:ty)*) => {
+        $(
+            impl $traitname for $ty { }
+        )*
+    }
+}
+
+impl_marker_for!(BytewiseEquality,
+                 u8 i8 u16 i16 u32 i32 u64 i64 usize isize char bool);
+
diff --git a/src/libcore/str/mod.rs b/src/libcore/str/mod.rs
index d5a5e2b4741..305546df5be 100644
--- a/src/libcore/str/mod.rs
+++ b/src/libcore/str/mod.rs
@@ -1150,16 +1150,7 @@ Section: Comparing strings
 #[lang = "str_eq"]
 #[inline]
 fn eq_slice(a: &str, b: &str) -> bool {
-    a.len() == b.len() && unsafe { cmp_slice(a, b, a.len()) == 0 }
-}
-
-/// Bytewise slice comparison.
-/// NOTE: This uses the system's memcmp, which is currently dramatically
-/// faster than comparing each byte in a loop.
-#[inline]
-unsafe fn cmp_slice(a: &str, b: &str, len: usize) -> i32 {
-    extern { fn memcmp(s1: *const i8, s2: *const i8, n: usize) -> i32; }
-    memcmp(a.as_ptr() as *const i8, b.as_ptr() as *const i8, len)
+    a.as_bytes() == b.as_bytes()
 }
 
 /*
@@ -1328,8 +1319,7 @@ Section: Trait implementations
 */
 
 mod traits {
-    use cmp::{self, Ordering, Ord, PartialEq, PartialOrd, Eq};
-    use cmp::Ordering::{Less, Greater};
+    use cmp::{Ord, Ordering, PartialEq, PartialOrd, Eq};
     use iter::Iterator;
     use option::Option;
     use option::Option::Some;
@@ -1340,16 +1330,7 @@ mod traits {
     impl Ord for str {
         #[inline]
         fn cmp(&self, other: &str) -> Ordering {
-            let cmp = unsafe {
-                super::cmp_slice(self, other, cmp::min(self.len(), other.len()))
-            };
-            if cmp == 0 {
-                self.len().cmp(&other.len())
-            } else if cmp < 0 {
-                Less
-            } else {
-                Greater
-            }
+            self.as_bytes().cmp(other.as_bytes())
         }
     }
 
diff --git a/src/libcore/sync/atomic.rs b/src/libcore/sync/atomic.rs
index d2e98a795d9..483c3822df6 100644
--- a/src/libcore/sync/atomic.rs
+++ b/src/libcore/sync/atomic.rs
@@ -327,7 +327,7 @@ impl AtomicBool {
     /// `compare_exchange` takes two `Ordering` arguments to describe the memory ordering of this
     /// operation. The first describes the required ordering if the operation succeeds while the
     /// second describes the required ordering when the operation fails. The failure ordering can't
-    /// be `Acquire` or `AcqRel` and must be equivalent or weaker than the success ordering.
+    /// be `Release` or `AcqRel` and must be equivalent or weaker than the success ordering.
     ///
     /// # Examples
     ///
@@ -376,7 +376,7 @@ impl AtomicBool {
     /// `compare_exchange_weak` takes two `Ordering` arguments to describe the memory
     /// ordering of this operation. The first describes the required ordering if the operation
     /// succeeds while the second describes the required ordering when the operation fails. The
-    /// failure ordering can't be `Acquire` or `AcqRel` and must be equivalent or weaker than the
+    /// failure ordering can't be `Release` or `AcqRel` and must be equivalent or weaker than the
     /// success ordering.
     ///
     /// # Examples
@@ -663,7 +663,7 @@ impl AtomicIsize {
     /// `compare_exchange` takes two `Ordering` arguments to describe the memory ordering of this
     /// operation. The first describes the required ordering if the operation succeeds while the
     /// second describes the required ordering when the operation fails. The failure ordering can't
-    /// be `Acquire` or `AcqRel` and must be equivalent or weaker than the success ordering.
+    /// be `Release` or `AcqRel` and must be equivalent or weaker than the success ordering.
     ///
     /// # Examples
     ///
@@ -705,7 +705,7 @@ impl AtomicIsize {
     /// `compare_exchange_weak` takes two `Ordering` arguments to describe the memory
     /// ordering of this operation. The first describes the required ordering if the operation
     /// succeeds while the second describes the required ordering when the operation fails. The
-    /// failure ordering can't be `Acquire` or `AcqRel` and must be equivalent or weaker than the
+    /// failure ordering can't be `Release` or `AcqRel` and must be equivalent or weaker than the
     /// success ordering.
     ///
     /// # Examples
@@ -939,7 +939,7 @@ impl AtomicUsize {
     /// `compare_exchange` takes two `Ordering` arguments to describe the memory ordering of this
     /// operation. The first describes the required ordering if the operation succeeds while the
     /// second describes the required ordering when the operation fails. The failure ordering can't
-    /// be `Acquire` or `AcqRel` and must be equivalent or weaker than the success ordering.
+    /// be `Release` or `AcqRel` and must be equivalent or weaker than the success ordering.
     ///
     /// # Examples
     ///
@@ -981,7 +981,7 @@ impl AtomicUsize {
     /// `compare_exchange_weak` takes two `Ordering` arguments to describe the memory
     /// ordering of this operation. The first describes the required ordering if the operation
     /// succeeds while the second describes the required ordering when the operation fails. The
-    /// failure ordering can't be `Acquire` or `AcqRel` and must be equivalent or weaker than the
+    /// failure ordering can't be `Release` or `AcqRel` and must be equivalent or weaker than the
     /// success ordering.
     ///
     /// # Examples
@@ -1223,7 +1223,7 @@ impl<T> AtomicPtr<T> {
     /// `compare_exchange` takes two `Ordering` arguments to describe the memory ordering of this
     /// operation. The first describes the required ordering if the operation succeeds while the
     /// second describes the required ordering when the operation fails. The failure ordering can't
-    /// be `Acquire` or `AcqRel` and must be equivalent or weaker than the success ordering.
+    /// be `Release` or `AcqRel` and must be equivalent or weaker than the success ordering.
     ///
     /// # Examples
     ///
@@ -1270,7 +1270,7 @@ impl<T> AtomicPtr<T> {
     /// `compare_exchange_weak` takes two `Ordering` arguments to describe the memory
     /// ordering of this operation. The first describes the required ordering if the operation
     /// succeeds while the second describes the required ordering when the operation fails. The
-    /// failure ordering can't be `Acquire` or `AcqRel` and must be equivalent or weaker than the
+    /// failure ordering can't be `Release` or `AcqRel` and must be equivalent or weaker than the
     /// success ordering.
     ///
     /// # Examples
@@ -1396,8 +1396,8 @@ unsafe fn atomic_compare_exchange<T>(dst: *mut T,
         (AcqRel, Relaxed)  => intrinsics::atomic_cxchg_acqrel_failrelaxed(dst, old, new),
         (SeqCst, Relaxed)  => intrinsics::atomic_cxchg_failrelaxed(dst, old, new),
         (SeqCst, Acquire)  => intrinsics::atomic_cxchg_failacq(dst, old, new),
-        (_, Release) => panic!("there is no such thing as an acquire/release failure ordering"),
-        (_, AcqRel) => panic!("there is no such thing as a release failure ordering"),
+        (_, AcqRel) => panic!("there is no such thing as an acquire/release failure ordering"),
+        (_, Release) => panic!("there is no such thing as a release failure ordering"),
         _ => panic!("a failure ordering can't be stronger than a success ordering"),
     };
     if ok {
@@ -1446,8 +1446,8 @@ unsafe fn atomic_compare_exchange_weak<T>(dst: *mut T,
         (AcqRel, Relaxed)  => intrinsics::atomic_cxchgweak_acqrel_failrelaxed(dst, old, new),
         (SeqCst, Relaxed)  => intrinsics::atomic_cxchgweak_failrelaxed(dst, old, new),
         (SeqCst, Acquire)  => intrinsics::atomic_cxchgweak_failacq(dst, old, new),
-        (_, Release) => panic!("there is no such thing as an acquire/release failure ordering"),
-        (_, AcqRel) => panic!("there is no such thing as a release failure ordering"),
+        (_, AcqRel) => panic!("there is no such thing as an acquire/release failure ordering"),
+        (_, Release) => panic!("there is no such thing as a release failure ordering"),
         _ => panic!("a failure ordering can't be stronger than a success ordering"),
     };
     if ok {