Merge remote-tracking branch 'origin/master' into proc_macro_api

11 files changed, 113 insertions, 64 deletions

diff --git a/src/liballoc/allocator.rs b/src/liballoc/allocator.rs
index 9bddce29957..bf38629ed38 100644
--- a/src/liballoc/allocator.rs
+++ b/src/liballoc/allocator.rs
@@ -873,7 +873,7 @@ pub unsafe trait Alloc {
     {
         let k = Layout::new::<T>();
         if k.size() > 0 {
-            unsafe { self.alloc(k).map(|p|Unique::new(*p as *mut T)) }
+            unsafe { self.alloc(k).map(|p| Unique::new(p as *mut T)) }
         } else {
             Err(AllocErr::invalid_input("zero-sized type invalid for alloc_one"))
         }
diff --git a/src/liballoc/benches/lib.rs b/src/liballoc/benches/lib.rs
index 958020d0b0e..174628ccd07 100644
--- a/src/liballoc/benches/lib.rs
+++ b/src/liballoc/benches/lib.rs
@@ -14,9 +14,9 @@
 #![feature(rand)]
 #![feature(repr_simd)]
 #![feature(slice_rotate)]
-#![feature(sort_unstable)]
 #![feature(test)]
 
+extern crate rand;
 extern crate test;
 
 mod btree;
diff --git a/src/liballoc/benches/slice.rs b/src/liballoc/benches/slice.rs
index aa5a438b35e..d99270e7f31 100644
--- a/src/liballoc/benches/slice.rs
+++ b/src/liballoc/benches/slice.rs
@@ -8,9 +8,11 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::{mem, ptr};
-use std::__rand::{Rng, thread_rng};
+use std::__rand::{thread_rng};
+use std::mem;
+use std::ptr;
 
+use rand::{Rng, SeedableRng, XorShiftRng};
 use test::{Bencher, black_box};
 
 #[bench]
@@ -191,17 +193,17 @@ fn gen_descending(len: usize) -> Vec<u64> {
 }
 
 fn gen_random(len: usize) -> Vec<u64> {
-    let mut rng = thread_rng();
+    let mut rng = XorShiftRng::from_seed([0, 1, 2, 3]);
     rng.gen_iter::<u64>().take(len).collect()
 }
 
 fn gen_random_bytes(len: usize) -> Vec<u8> {
-    let mut rng = thread_rng();
+    let mut rng = XorShiftRng::from_seed([0, 1, 2, 3]);
     rng.gen_iter::<u8>().take(len).collect()
 }
 
 fn gen_mostly_ascending(len: usize) -> Vec<u64> {
-    let mut rng = thread_rng();
+    let mut rng = XorShiftRng::from_seed([0, 1, 2, 3]);
     let mut v = gen_ascending(len);
     for _ in (0usize..).take_while(|x| x * x <= len) {
         let x = rng.gen::<usize>() % len;
@@ -212,7 +214,7 @@ fn gen_mostly_ascending(len: usize) -> Vec<u64> {
 }
 
 fn gen_mostly_descending(len: usize) -> Vec<u64> {
-    let mut rng = thread_rng();
+    let mut rng = XorShiftRng::from_seed([0, 1, 2, 3]);
     let mut v = gen_descending(len);
     for _ in (0usize..).take_while(|x| x * x <= len) {
         let x = rng.gen::<usize>() % len;
@@ -223,7 +225,7 @@ fn gen_mostly_descending(len: usize) -> Vec<u64> {
 }
 
 fn gen_strings(len: usize) -> Vec<String> {
-    let mut rng = thread_rng();
+    let mut rng = XorShiftRng::from_seed([0, 1, 2, 3]);
     let mut v = vec![];
     for _ in 0..len {
         let n = rng.gen::<usize>() % 20 + 1;
@@ -233,7 +235,7 @@ fn gen_strings(len: usize) -> Vec<String> {
 }
 
 fn gen_big_random(len: usize) -> Vec<[u64; 16]> {
-    let mut rng = thread_rng();
+    let mut rng = XorShiftRng::from_seed([0, 1, 2, 3]);
     rng.gen_iter().map(|x| [x; 16]).take(len).collect()
 }
 
@@ -241,18 +243,32 @@ macro_rules! sort {
     ($f:ident, $name:ident, $gen:expr, $len:expr) => {
         #[bench]
         fn $name(b: &mut Bencher) {
-            b.iter(|| $gen($len).$f());
+            let v = $gen($len);
+            b.iter(|| v.clone().$f());
             b.bytes = $len * mem::size_of_val(&$gen(1)[0]) as u64;
         }
     }
 }
 
+macro_rules! sort_strings {
+    ($f:ident, $name:ident, $gen:expr, $len:expr) => {
+        #[bench]
+        fn $name(b: &mut Bencher) {
+            let v = $gen($len);
+            let v = v.iter().map(|s| &**s).collect::<Vec<&str>>();
+            b.iter(|| v.clone().$f());
+            b.bytes = $len * mem::size_of::<&str>() as u64;
+        }
+    }
+}
+
 macro_rules! sort_expensive {
     ($f:ident, $name:ident, $gen:expr, $len:expr) => {
         #[bench]
         fn $name(b: &mut Bencher) {
+            let v = $gen($len);
             b.iter(|| {
-                let mut v = $gen($len);
+                let mut v = v.clone();
                 let mut count = 0;
                 v.$f(|a: &u64, b: &u64| {
                     count += 1;
@@ -263,7 +279,7 @@ macro_rules! sort_expensive {
                 });
                 black_box(count);
             });
-            b.bytes = $len as u64 * mem::size_of::<u64>() as u64;
+            b.bytes = $len * mem::size_of_val(&$gen(1)[0]) as u64;
         }
     }
 }
@@ -271,30 +287,30 @@ macro_rules! sort_expensive {
 sort!(sort, sort_small_ascending, gen_ascending, 10);
 sort!(sort, sort_small_descending, gen_descending, 10);
 sort!(sort, sort_small_random, gen_random, 10);
-sort!(sort, sort_small_big_random, gen_big_random, 10);
+sort!(sort, sort_small_big, gen_big_random, 10);
 sort!(sort, sort_medium_random, gen_random, 100);
 sort!(sort, sort_large_ascending, gen_ascending, 10000);
 sort!(sort, sort_large_descending, gen_descending, 10000);
 sort!(sort, sort_large_mostly_ascending, gen_mostly_ascending, 10000);
 sort!(sort, sort_large_mostly_descending, gen_mostly_descending, 10000);
 sort!(sort, sort_large_random, gen_random, 10000);
-sort!(sort, sort_large_big_random, gen_big_random, 10000);
-sort!(sort, sort_large_strings, gen_strings, 10000);
-sort_expensive!(sort_by, sort_large_random_expensive, gen_random, 10000);
+sort!(sort, sort_large_big, gen_big_random, 10000);
+sort_strings!(sort, sort_large_strings, gen_strings, 10000);
+sort_expensive!(sort_by, sort_large_expensive, gen_random, 10000);
 
 sort!(sort_unstable, sort_unstable_small_ascending, gen_ascending, 10);
 sort!(sort_unstable, sort_unstable_small_descending, gen_descending, 10);
 sort!(sort_unstable, sort_unstable_small_random, gen_random, 10);
-sort!(sort_unstable, sort_unstable_small_big_random, gen_big_random, 10);
+sort!(sort_unstable, sort_unstable_small_big, gen_big_random, 10);
 sort!(sort_unstable, sort_unstable_medium_random, gen_random, 100);
 sort!(sort_unstable, sort_unstable_large_ascending, gen_ascending, 10000);
 sort!(sort_unstable, sort_unstable_large_descending, gen_descending, 10000);
 sort!(sort_unstable, sort_unstable_large_mostly_ascending, gen_mostly_ascending, 10000);
 sort!(sort_unstable, sort_unstable_large_mostly_descending, gen_mostly_descending, 10000);
 sort!(sort_unstable, sort_unstable_large_random, gen_random, 10000);
-sort!(sort_unstable, sort_unstable_large_big_random, gen_big_random, 10000);
-sort!(sort_unstable, sort_unstable_large_strings, gen_strings, 10000);
-sort_expensive!(sort_unstable_by, sort_unstable_large_random_expensive, gen_random, 10000);
+sort!(sort_unstable, sort_unstable_large_big, gen_big_random, 10000);
+sort_strings!(sort_unstable, sort_unstable_large_strings, gen_strings, 10000);
+sort_expensive!(sort_unstable_by, sort_unstable_large_expensive, gen_random, 10000);
 
 macro_rules! reverse {
     ($name:ident, $ty:ty, $f:expr) => {
diff --git a/src/liballoc/fmt.rs b/src/liballoc/fmt.rs
index 1bd95fb82aa..4847b21c0b3 100644
--- a/src/liballoc/fmt.rs
+++ b/src/liballoc/fmt.rs
@@ -498,12 +498,10 @@ pub use core::fmt::{DebugList, DebugMap, DebugSet, DebugStruct, DebugTuple};
 
 use string;
 
-/// The format function takes a precompiled format string and a list of
-/// arguments, to return the resulting formatted string.
+/// The `format` function takes an `Arguments` struct and returns the resulting
+/// formatted string.
 ///
-/// # Arguments
-///
-///   * args - a structure of arguments generated via the `format_args!` macro.
+/// The `Arguments` instance can be created with the `format_args!` macro.
 ///
 /// # Examples
 ///
diff --git a/src/liballoc/lib.rs b/src/liballoc/lib.rs
index ca52943ea97..23da2913136 100644
--- a/src/liballoc/lib.rs
+++ b/src/liballoc/lib.rs
@@ -83,7 +83,6 @@
 #![cfg_attr(not(test), feature(core_float))]
 #![cfg_attr(not(test), feature(exact_size_is_empty))]
 #![cfg_attr(not(test), feature(slice_rotate))]
-#![cfg_attr(not(test), feature(sort_unstable))]
 #![cfg_attr(not(test), feature(str_checked_slicing))]
 #![cfg_attr(test, feature(rand, test))]
 #![feature(allocator)]
diff --git a/src/liballoc/slice.rs b/src/liballoc/slice.rs
index 88876999d76..f4c2b9d054b 100644
--- a/src/liballoc/slice.rs
+++ b/src/liballoc/slice.rs
@@ -1144,6 +1144,10 @@ impl<T> [T] {
     ///
     /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
     ///
+    /// When applicable, unstable sorting is preferred because it is generally faster than stable
+    /// sorting and it doesn't allocate auxiliary memory.
+    /// See [`sort_unstable`](#method.sort_unstable).
+    ///
     /// # Current implementation
     ///
     /// The current algorithm is an adaptive, iterative merge sort inspired by
@@ -1174,6 +1178,10 @@ impl<T> [T] {
     ///
     /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
     ///
+    /// When applicable, unstable sorting is preferred because it is generally faster than stable
+    /// sorting and it doesn't allocate auxiliary memory.
+    /// See [`sort_unstable_by`](#method.sort_unstable_by).
+    ///
     /// # Current implementation
     ///
     /// The current algorithm is an adaptive, iterative merge sort inspired by
@@ -1207,6 +1215,10 @@ impl<T> [T] {
     ///
     /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
     ///
+    /// When applicable, unstable sorting is preferred because it is generally faster than stable
+    /// sorting and it doesn't allocate auxiliary memory.
+    /// See [`sort_unstable_by_key`](#method.sort_unstable_by_key).
+    ///
     /// # Current implementation
     ///
     /// The current algorithm is an adaptive, iterative merge sort inspired by
@@ -1251,8 +1263,6 @@ impl<T> [T] {
     /// # Examples
     ///
     /// ```
-    /// #![feature(sort_unstable)]
-    ///
     /// let mut v = [-5, 4, 1, -3, 2];
     ///
     /// v.sort_unstable();
@@ -1260,8 +1270,7 @@ impl<T> [T] {
     /// ```
     ///
     /// [pdqsort]: https://github.com/orlp/pdqsort
-    // FIXME #40585: Mention `sort_unstable` in the documentation for `sort`.
-    #[unstable(feature = "sort_unstable", issue = "40585")]
+    #[stable(feature = "sort_unstable", since = "1.20.0")]
     #[inline]
     pub fn sort_unstable(&mut self)
         where T: Ord
@@ -1288,8 +1297,6 @@ impl<T> [T] {
     /// # Examples
     ///
     /// ```
-    /// #![feature(sort_unstable)]
-    ///
     /// let mut v = [5, 4, 1, 3, 2];
     /// v.sort_unstable_by(|a, b| a.cmp(b));
     /// assert!(v == [1, 2, 3, 4, 5]);
@@ -1300,8 +1307,7 @@ impl<T> [T] {
     /// ```
     ///
     /// [pdqsort]: https://github.com/orlp/pdqsort
-    // FIXME #40585: Mention `sort_unstable_by` in the documentation for `sort_by`.
-    #[unstable(feature = "sort_unstable", issue = "40585")]
+    #[stable(feature = "sort_unstable", since = "1.20.0")]
     #[inline]
     pub fn sort_unstable_by<F>(&mut self, compare: F)
         where F: FnMut(&T, &T) -> Ordering
@@ -1328,8 +1334,6 @@ impl<T> [T] {
     /// # Examples
     ///
     /// ```
-    /// #![feature(sort_unstable)]
-    ///
     /// let mut v = [-5i32, 4, 1, -3, 2];
     ///
     /// v.sort_unstable_by_key(|k| k.abs());
@@ -1337,8 +1341,7 @@ impl<T> [T] {
     /// ```
     ///
     /// [pdqsort]: https://github.com/orlp/pdqsort
-    // FIXME #40585: Mention `sort_unstable_by_key` in the documentation for `sort_by_key`.
-    #[unstable(feature = "sort_unstable", issue = "40585")]
+    #[stable(feature = "sort_unstable", since = "1.20.0")]
     #[inline]
     pub fn sort_unstable_by_key<B, F>(&mut self, f: F)
         where F: FnMut(&T) -> B,
@@ -1794,7 +1797,7 @@ unsafe fn merge<T, F>(v: &mut [T], mid: usize, buf: *mut T, is_less: &mut F)
 
     impl<T> Drop for MergeHole<T> {
         fn drop(&mut self) {
-            // `T` is not a zero-sized type, so it's okay to divide by it's size.
+            // `T` is not a zero-sized type, so it's okay to divide by its size.
             let len = (self.end as usize - self.start as usize) / mem::size_of::<T>();
             unsafe { ptr::copy_nonoverlapping(self.start, self.dest, len); }
         }
@@ -1908,7 +1911,7 @@ fn merge_sort<T, F>(v: &mut [T], mut is_less: F)
     // if `Some(r)` is returned, that means `runs[r]` and `runs[r + 1]` must be merged next. If the
     // algorithm should continue building a new run instead, `None` is returned.
     //
-    // TimSort is infamous for it's buggy implementations, as described here:
+    // TimSort is infamous for its buggy implementations, as described here:
     // http://envisage-project.eu/timsort-specification-and-verification/
     //
     // The gist of the story is: we must enforce the invariants on the top four runs on the stack.
diff --git a/src/liballoc/string.rs b/src/liballoc/string.rs
index 79d1ccf637d..622cc68964b 100644
--- a/src/liballoc/string.rs
+++ b/src/liballoc/string.rs
@@ -2008,10 +2008,10 @@ impl From<Box<str>> for String {
     }
 }
 
-#[stable(feature = "box_from_str", since = "1.18.0")]
-impl Into<Box<str>> for String {
-    fn into(self) -> Box<str> {
-        self.into_boxed_str()
+#[stable(feature = "box_from_str", since = "1.20.0")]
+impl From<String> for Box<str> {
+    fn from(s: String) -> Box<str> {
+        s.into_boxed_str()
     }
 }
 
diff --git a/src/liballoc/tests/slice.rs b/src/liballoc/tests/slice.rs
index 7fa65a2144e..c53bf15f1bf 100644
--- a/src/liballoc/tests/slice.rs
+++ b/src/liballoc/tests/slice.rs
@@ -396,18 +396,44 @@ fn test_sort() {
     let mut rng = thread_rng();
 
     for len in (2..25).chain(500..510) {
-        for _ in 0..100 {
-            let mut v: Vec<_> = rng.gen_iter::<i32>().take(len).collect();
-            let mut v1 = v.clone();
-
-            v.sort();
-            assert!(v.windows(2).all(|w| w[0] <= w[1]));
-
-            v1.sort_by(|a, b| a.cmp(b));
-            assert!(v1.windows(2).all(|w| w[0] <= w[1]));
-
-            v1.sort_by(|a, b| b.cmp(a));
-            assert!(v1.windows(2).all(|w| w[0] >= w[1]));
+        for &modulus in &[5, 10, 100, 1000] {
+            for _ in 0..10 {
+                let orig: Vec<_> = rng.gen_iter::<i32>()
+                    .map(|x| x % modulus)
+                    .take(len)
+                    .collect();
+
+                // Sort in default order.
+                let mut v = orig.clone();
+                v.sort();
+                assert!(v.windows(2).all(|w| w[0] <= w[1]));
+
+                // Sort in ascending order.
+                let mut v = orig.clone();
+                v.sort_by(|a, b| a.cmp(b));
+                assert!(v.windows(2).all(|w| w[0] <= w[1]));
+
+                // Sort in descending order.
+                let mut v = orig.clone();
+                v.sort_by(|a, b| b.cmp(a));
+                assert!(v.windows(2).all(|w| w[0] >= w[1]));
+
+                // Sort with many pre-sorted runs.
+                let mut v = orig.clone();
+                v.sort();
+                v.reverse();
+                for _ in 0..5 {
+                    let a = rng.gen::<usize>() % len;
+                    let b = rng.gen::<usize>() % len;
+                    if a < b {
+                        v[a..b].reverse();
+                    } else {
+                        v.swap(a, b);
+                    }
+                }
+                v.sort();
+                assert!(v.windows(2).all(|w| w[0] <= w[1]));
+            }
         }
     }
 
diff --git a/src/liballoc/tests/vec.rs b/src/liballoc/tests/vec.rs
index fdf453b39cf..17f1229c206 100644
--- a/src/liballoc/tests/vec.rs
+++ b/src/liballoc/tests/vec.rs
@@ -274,6 +274,11 @@ fn test_dedup_by() {
     vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
 
     assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
+
+    let mut vec = vec![("foo", 1), ("foo", 2), ("bar", 3), ("bar", 4), ("bar", 5)];
+    vec.dedup_by(|a, b| a.0 == b.0 && { b.1 += a.1; true });
+
+    assert_eq!(vec, [("foo", 3), ("bar", 12)]);
 }
 
 #[test]
diff --git a/src/liballoc/tests/vec_deque.rs b/src/liballoc/tests/vec_deque.rs
index a992351653d..f2935c05d4f 100644
--- a/src/liballoc/tests/vec_deque.rs
+++ b/src/liballoc/tests/vec_deque.rs
@@ -510,8 +510,7 @@ fn test_from_iter() {
     let u: Vec<_> = deq.iter().cloned().collect();
     assert_eq!(u, v);
 
-    // FIXME #27741: Remove `.skip(0)` when Range::step_by is fully removed
-    let seq = (0..).skip(0).step_by(2).take(256);
+    let seq = (0..).step_by(2).take(256);
     let deq: VecDeque<_> = seq.collect();
     for (i, &x) in deq.iter().enumerate() {
         assert_eq!(2 * i, x);
diff --git a/src/liballoc/vec.rs b/src/liballoc/vec.rs
index 5d1999a4262..780a51aec3b 100644
--- a/src/liballoc/vec.rs
+++ b/src/liballoc/vec.rs
@@ -222,7 +222,7 @@ use Bound::{Excluded, Included, Unbounded};
 /// on an empty Vec, it will not allocate memory. Similarly, if you store zero-sized
 /// types inside a `Vec`, it will not allocate space for them. *Note that in this case
 /// the `Vec` may not report a [`capacity`] of 0*. `Vec` will allocate if and only
-/// if [`mem::size_of::<T>`]` * capacity() > 0`. In general, `Vec`'s allocation
+/// if [`mem::size_of::<T>`]`() * capacity() > 0`. In general, `Vec`'s allocation
 /// details are subtle enough that it is strongly recommended that you only
 /// free memory allocated by a `Vec` by creating a new `Vec` and dropping it.
 ///
@@ -823,7 +823,8 @@ impl<T> Vec<T> {
         }
     }
 
-    /// Removes consecutive elements in the vector that resolve to the same key.
+    /// Removes all but the first of consecutive elements in the vector that resolve to the same
+    /// key.
     ///
     /// If the vector is sorted, this removes all duplicates.
     ///
@@ -842,11 +843,13 @@ impl<T> Vec<T> {
         self.dedup_by(|a, b| key(a) == key(b))
     }
 
-    /// Removes consecutive elements in the vector according to a predicate.
+    /// Removes all but the first of consecutive elements in the vector satisfying a given equality
+    /// relation.
     ///
     /// The `same_bucket` function is passed references to two elements from the vector, and
-    /// returns `true` if the elements compare equal, or `false` if they do not. Only the first
-    /// of adjacent equal items is kept.
+    /// returns `true` if the elements compare equal, or `false` if they do not. The elements are
+    /// passed in opposite order from their order in the vector, so if `same_bucket(a, b)` returns
+    /// `true`, `a` is removed.
     ///
     /// If the vector is sorted, this removes all duplicates.
     ///