Merge branch 'master' into copied

9 files changed, 246 insertions, 22 deletions

diff --git a/src/liballoc/tests/arc.rs b/src/liballoc/tests/arc.rs
index d90c22a3b18..ec589710216 100644
--- a/src/liballoc/tests/arc.rs
+++ b/src/liballoc/tests/arc.rs
@@ -10,6 +10,8 @@
 
 use std::any::Any;
 use std::sync::{Arc, Weak};
+use std::cell::RefCell;
+use std::cmp::PartialEq;
 
 #[test]
 fn uninhabited() {
@@ -53,3 +55,43 @@ fn trait_object() {
     b = b.clone();
     assert!(b.upgrade().is_none());
 }
+
+#[test]
+fn float_nan_ne() {
+    let x = Arc::new(std::f32::NAN);
+    assert!(x != x);
+    assert!(!(x == x));
+}
+
+#[test]
+fn partial_eq() {
+    struct TestPEq (RefCell<usize>);
+    impl PartialEq for TestPEq {
+        fn eq(&self, other: &TestPEq) -> bool {
+            *self.0.borrow_mut() += 1;
+            *other.0.borrow_mut() += 1;
+            true
+        }
+    }
+    let x = Arc::new(TestPEq(RefCell::new(0)));
+    assert!(x == x);
+    assert!(!(x != x));
+    assert_eq!(*x.0.borrow(), 4);
+}
+
+#[test]
+fn eq() {
+    #[derive(Eq)]
+    struct TestEq (RefCell<usize>);
+    impl PartialEq for TestEq {
+        fn eq(&self, other: &TestEq) -> bool {
+            *self.0.borrow_mut() += 1;
+            *other.0.borrow_mut() += 1;
+            true
+        }
+    }
+    let x = Arc::new(TestEq(RefCell::new(0)));
+    assert!(x == x);
+    assert!(!(x != x));
+    assert_eq!(*x.0.borrow(), 0);
+}
diff --git a/src/liballoc/tests/binary_heap.rs b/src/liballoc/tests/binary_heap.rs
index 8494463463c..536291de8f0 100644
--- a/src/liballoc/tests/binary_heap.rs
+++ b/src/liballoc/tests/binary_heap.rs
@@ -14,7 +14,7 @@ use std::collections::binary_heap::{Drain, PeekMut};
 use std::panic::{self, AssertUnwindSafe};
 use std::sync::atomic::{AtomicUsize, ATOMIC_USIZE_INIT, Ordering};
 
-use rand::{thread_rng, Rng};
+use rand::{thread_rng, seq::SliceRandom};
 
 #[test]
 fn test_iterator() {
@@ -318,11 +318,11 @@ fn panic_safe() {
     const NTEST: usize = 10;
 
     // don't use 0 in the data -- we want to catch the zeroed-out case.
-    let data = (1..DATASZ + 1).collect::<Vec<_>>();
+    let data = (1..=DATASZ).collect::<Vec<_>>();
 
     // since it's a fuzzy test, run several tries.
     for _ in 0..NTEST {
-        for i in 1..DATASZ + 1 {
+        for i in 1..=DATASZ {
             DROP_COUNTER.store(0, Ordering::SeqCst);
 
             let mut panic_ords: Vec<_> = data.iter()
@@ -332,7 +332,7 @@ fn panic_safe() {
             let panic_item = PanicOrd(i, true);
 
             // heapify the sane items
-            rng.shuffle(&mut panic_ords);
+            panic_ords.shuffle(&mut rng);
             let mut heap = BinaryHeap::from(panic_ords);
             let inner_data;
 
diff --git a/src/liballoc/tests/btree/map.rs b/src/liballoc/tests/btree/map.rs
index 6ebdb86cc4a..33ef13ab811 100644
--- a/src/liballoc/tests/btree/map.rs
+++ b/src/liballoc/tests/btree/map.rs
@@ -302,7 +302,7 @@ fn test_range() {
     for i in 0..size {
         for j in i..size {
             let mut kvs = map.range((Included(&i), Included(&j))).map(|(&k, &v)| (k, v));
-            let mut pairs = (i..j + 1).map(|i| (i, i));
+            let mut pairs = (i..=j).map(|i| (i, i));
 
             for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
                 assert_eq!(kv, pair);
@@ -321,7 +321,7 @@ fn test_range_mut() {
     for i in 0..size {
         for j in i..size {
             let mut kvs = map.range_mut((Included(&i), Included(&j))).map(|(&k, &mut v)| (k, v));
-            let mut pairs = (i..j + 1).map(|i| (i, i));
+            let mut pairs = (i..=j).map(|i| (i, i));
 
             for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
                 assert_eq!(kv, pair);
diff --git a/src/liballoc/tests/lib.rs b/src/liballoc/tests/lib.rs
index e514a8a69c0..146abd1b750 100644
--- a/src/liballoc/tests/lib.rs
+++ b/src/liballoc/tests/lib.rs
@@ -13,11 +13,12 @@
 #![feature(drain_filter)]
 #![feature(exact_size_is_empty)]
 #![feature(pattern)]
+#![feature(repeat_generic_slice)]
 #![feature(slice_sort_by_cached_key)]
 #![feature(str_escape)]
 #![feature(try_reserve)]
 #![feature(unboxed_closures)]
-#![feature(repeat_generic_slice)]
+#![feature(vecdeque_rotate)]
 
 extern crate core;
 extern crate rand;
diff --git a/src/liballoc/tests/rc.rs b/src/liballoc/tests/rc.rs
index 9ec7c831444..02e1dfe13bb 100644
--- a/src/liballoc/tests/rc.rs
+++ b/src/liballoc/tests/rc.rs
@@ -10,6 +10,8 @@
 
 use std::any::Any;
 use std::rc::{Rc, Weak};
+use std::cell::RefCell;
+use std::cmp::PartialEq;
 
 #[test]
 fn uninhabited() {
@@ -53,3 +55,43 @@ fn trait_object() {
     b = b.clone();
     assert!(b.upgrade().is_none());
 }
+
+#[test]
+fn float_nan_ne() {
+    let x = Rc::new(std::f32::NAN);
+    assert!(x != x);
+    assert!(!(x == x));
+}
+
+#[test]
+fn partial_eq() {
+    struct TestPEq (RefCell<usize>);
+    impl PartialEq for TestPEq {
+        fn eq(&self, other: &TestPEq) -> bool {
+            *self.0.borrow_mut() += 1;
+            *other.0.borrow_mut() += 1;
+            true
+        }
+    }
+    let x = Rc::new(TestPEq(RefCell::new(0)));
+    assert!(x == x);
+    assert!(!(x != x));
+    assert_eq!(*x.0.borrow(), 4);
+}
+
+#[test]
+fn eq() {
+    #[derive(Eq)]
+    struct TestEq (RefCell<usize>);
+    impl PartialEq for TestEq {
+        fn eq(&self, other: &TestEq) -> bool {
+            *self.0.borrow_mut() += 1;
+            *other.0.borrow_mut() += 1;
+            true
+        }
+    }
+    let x = Rc::new(TestEq(RefCell::new(0)));
+    assert!(x == x);
+    assert!(!(x != x));
+    assert_eq!(*x.0.borrow(), 0);
+}
diff --git a/src/liballoc/tests/slice.rs b/src/liballoc/tests/slice.rs
index a50f99b0022..6f31e6ca1a1 100644
--- a/src/liballoc/tests/slice.rs
+++ b/src/liballoc/tests/slice.rs
@@ -18,7 +18,7 @@ use std::sync::atomic::Ordering::Relaxed;
 use std::sync::atomic::{ATOMIC_USIZE_INIT, AtomicUsize};
 use std::thread;
 
-use rand::{Rng, RngCore, thread_rng};
+use rand::{Rng, RngCore, thread_rng, seq::SliceRandom};
 use rand::distributions::Standard;
 
 fn square(n: usize) -> usize {
@@ -459,7 +459,7 @@ fn test_sort() {
     for i in 0..v.len() {
         v[i] = i as i32;
     }
-    v.sort_by(|_, _| *rng.choose(&[Less, Equal, Greater]).unwrap());
+    v.sort_by(|_, _| *[Less, Equal, Greater].choose(&mut rng).unwrap());
     v.sort();
     for i in 0..v.len() {
         assert_eq!(v[i], i as i32);
@@ -484,7 +484,7 @@ fn test_sort_stability() {
             // create a vector like [(6, 1), (5, 1), (6, 2), ...],
             // where the first item of each tuple is random, but
             // the second item represents which occurrence of that
-            // number this element is, i.e. the second elements
+            // number this element is, i.e., the second elements
             // will occur in sorted order.
             let mut orig: Vec<_> = (0..len)
                 .map(|_| {
@@ -502,7 +502,7 @@ fn test_sort_stability() {
             // This comparison includes the count (the second item
             // of the tuple), so elements with equal first items
             // will need to be ordered with increasing
-            // counts... i.e. exactly asserting that this sort is
+            // counts... i.e., exactly asserting that this sort is
             // stable.
             assert!(v.windows(2).all(|w| w[0] <= w[1]));
 
@@ -1579,7 +1579,7 @@ macro_rules! test {
             }).join();
 
             // Check that the number of things dropped is exactly
-            // what we expect (i.e. the contents of `v`).
+            // what we expect (i.e., the contents of `v`).
             for (i, c) in DROP_COUNTS.iter().enumerate().take(len) {
                 let count = c.load(Relaxed);
                 assert!(count == 1,
diff --git a/src/liballoc/tests/str.rs b/src/liballoc/tests/str.rs
index a5fa7f0c4d9..9ad8ad1fc07 100644
--- a/src/liballoc/tests/str.rs
+++ b/src/liballoc/tests/str.rs
@@ -1005,7 +1005,7 @@ fn test_escape_debug() {
     // Note that there are subtleties with the number of backslashes
     // on the left- and right-hand sides. In particular, Unicode code points
     // are usually escaped with two backslashes on the right-hand side, as
-    // they are escaped. However, when the character is unescaped (e.g. for
+    // they are escaped. However, when the character is unescaped (e.g., for
     // printable characters), only a single backslash appears (as the character
     // itself appears in the debug string).
     assert_eq!("abc".escape_debug(), "abc");
@@ -1378,7 +1378,7 @@ fn test_bool_from_str() {
 fn check_contains_all_substrings(s: &str) {
     assert!(s.contains(""));
     for i in 0..s.len() {
-        for j in i+1..s.len() + 1 {
+        for j in i+1..=s.len() {
             assert!(s.contains(&s[i..j]));
         }
     }
@@ -1514,9 +1514,9 @@ fn contains_weird_cases() {
 
 #[test]
 fn trim_ws() {
-    assert_eq!(" \t  a \t  ".trim_left_matches(|c: char| c.is_whitespace()),
+    assert_eq!(" \t  a \t  ".trim_start_matches(|c: char| c.is_whitespace()),
                     "a \t  ");
-    assert_eq!(" \t  a \t  ".trim_right_matches(|c: char| c.is_whitespace()),
+    assert_eq!(" \t  a \t  ".trim_end_matches(|c: char| c.is_whitespace()),
                " \t  a");
     assert_eq!(" \t  a \t  ".trim_start_matches(|c: char| c.is_whitespace()),
                     "a \t  ");
@@ -1524,9 +1524,9 @@ fn trim_ws() {
                " \t  a");
     assert_eq!(" \t  a \t  ".trim_matches(|c: char| c.is_whitespace()),
                     "a");
-    assert_eq!(" \t   \t  ".trim_left_matches(|c: char| c.is_whitespace()),
+    assert_eq!(" \t   \t  ".trim_start_matches(|c: char| c.is_whitespace()),
                          "");
-    assert_eq!(" \t   \t  ".trim_right_matches(|c: char| c.is_whitespace()),
+    assert_eq!(" \t   \t  ".trim_end_matches(|c: char| c.is_whitespace()),
                "");
     assert_eq!(" \t   \t  ".trim_start_matches(|c: char| c.is_whitespace()),
                          "");
diff --git a/src/liballoc/tests/vec.rs b/src/liballoc/tests/vec.rs
index e329b45a617..509195cd047 100644
--- a/src/liballoc/tests/vec.rs
+++ b/src/liballoc/tests/vec.rs
@@ -80,6 +80,11 @@ fn test_reserve() {
 }
 
 #[test]
+fn test_zst_capacity() {
+    assert_eq!(Vec::<()>::new().capacity(), usize::max_value());
+}
+
+#[test]
 fn test_extend() {
     let mut v = Vec::new();
     let mut w = Vec::new();
diff --git a/src/liballoc/tests/vec_deque.rs b/src/liballoc/tests/vec_deque.rs
index 3ea6c87a651..c8a6d86413a 100644
--- a/src/liballoc/tests/vec_deque.rs
+++ b/src/liballoc/tests/vec_deque.rs
@@ -861,7 +861,7 @@ fn test_as_slices() {
         ring.push_back(i);
 
         let (left, right) = ring.as_slices();
-        let expected: Vec<_> = (0..i + 1).collect();
+        let expected: Vec<_> = (0..=i).collect();
         assert_eq!(left, &expected[..]);
         assert_eq!(right, []);
     }
@@ -869,7 +869,7 @@ fn test_as_slices() {
     for j in -last..0 {
         ring.push_front(j);
         let (left, right) = ring.as_slices();
-        let expected_left: Vec<_> = (-last..j + 1).rev().collect();
+        let expected_left: Vec<_> = (-last..=j).rev().collect();
         let expected_right: Vec<_> = (0..first).collect();
         assert_eq!(left, &expected_left[..]);
         assert_eq!(right, &expected_right[..]);
@@ -889,7 +889,7 @@ fn test_as_mut_slices() {
         ring.push_back(i);
 
         let (left, right) = ring.as_mut_slices();
-        let expected: Vec<_> = (0..i + 1).collect();
+        let expected: Vec<_> = (0..=i).collect();
         assert_eq!(left, &expected[..]);
         assert_eq!(right, []);
     }
@@ -897,7 +897,7 @@ fn test_as_mut_slices() {
     for j in -last..0 {
         ring.push_front(j);
         let (left, right) = ring.as_mut_slices();
-        let expected_left: Vec<_> = (-last..j + 1).rev().collect();
+        let expected_left: Vec<_> = (-last..=j).rev().collect();
         let expected_right: Vec<_> = (0..first).collect();
         assert_eq!(left, &expected_left[..]);
         assert_eq!(right, &expected_right[..]);
@@ -1309,3 +1309,137 @@ fn test_try_reserve_exact() {
     }
 
 }
+
+#[test]
+fn test_rotate_nop() {
+    let mut v: VecDeque<_> = (0..10).collect();
+    assert_unchanged(&v);
+
+    v.rotate_left(0);
+    assert_unchanged(&v);
+
+    v.rotate_left(10);
+    assert_unchanged(&v);
+
+    v.rotate_right(0);
+    assert_unchanged(&v);
+
+    v.rotate_right(10);
+    assert_unchanged(&v);
+
+    v.rotate_left(3);
+    v.rotate_right(3);
+    assert_unchanged(&v);
+
+    v.rotate_right(3);
+    v.rotate_left(3);
+    assert_unchanged(&v);
+
+    v.rotate_left(6);
+    v.rotate_right(6);
+    assert_unchanged(&v);
+
+    v.rotate_right(6);
+    v.rotate_left(6);
+    assert_unchanged(&v);
+
+    v.rotate_left(3);
+    v.rotate_left(7);
+    assert_unchanged(&v);
+
+    v.rotate_right(4);
+    v.rotate_right(6);
+    assert_unchanged(&v);
+
+    v.rotate_left(1);
+    v.rotate_left(2);
+    v.rotate_left(3);
+    v.rotate_left(4);
+    assert_unchanged(&v);
+
+    v.rotate_right(1);
+    v.rotate_right(2);
+    v.rotate_right(3);
+    v.rotate_right(4);
+    assert_unchanged(&v);
+
+    fn assert_unchanged(v: &VecDeque<i32>) {
+        assert_eq!(v, &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
+    }
+}
+
+#[test]
+fn test_rotate_left_parts() {
+    let mut v: VecDeque<_> = (1..=7).collect();
+    v.rotate_left(2);
+    assert_eq!(v.as_slices(), (&[3, 4, 5, 6, 7, 1][..], &[2][..]));
+    v.rotate_left(2);
+    assert_eq!(v.as_slices(), (&[5, 6, 7, 1][..], &[2, 3, 4][..]));
+    v.rotate_left(2);
+    assert_eq!(v.as_slices(), (&[7, 1][..], &[2, 3, 4, 5, 6][..]));
+    v.rotate_left(2);
+    assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7, 1][..], &[][..]));
+    v.rotate_left(2);
+    assert_eq!(v.as_slices(), (&[4, 5, 6, 7, 1, 2][..], &[3][..]));
+    v.rotate_left(2);
+    assert_eq!(v.as_slices(), (&[6, 7, 1, 2][..], &[3, 4, 5][..]));
+    v.rotate_left(2);
+    assert_eq!(v.as_slices(), (&[1, 2][..], &[3, 4, 5, 6, 7][..]));
+}
+
+#[test]
+fn test_rotate_right_parts() {
+    let mut v: VecDeque<_> = (1..=7).collect();
+    v.rotate_right(2);
+    assert_eq!(v.as_slices(), (&[6, 7][..], &[1, 2, 3, 4, 5][..]));
+    v.rotate_right(2);
+    assert_eq!(v.as_slices(), (&[4, 5, 6, 7][..], &[1, 2, 3][..]));
+    v.rotate_right(2);
+    assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7][..], &[1][..]));
+    v.rotate_right(2);
+    assert_eq!(v.as_slices(), (&[7, 1, 2, 3, 4, 5, 6][..], &[][..]));
+    v.rotate_right(2);
+    assert_eq!(v.as_slices(), (&[5, 6][..], &[7, 1, 2, 3, 4][..]));
+    v.rotate_right(2);
+    assert_eq!(v.as_slices(), (&[3, 4, 5, 6][..], &[7, 1, 2][..]));
+    v.rotate_right(2);
+    assert_eq!(v.as_slices(), (&[1, 2, 3, 4, 5, 6][..], &[7][..]));
+}
+
+#[test]
+fn test_rotate_left_random() {
+    let shifts = [
+        6, 1, 0, 11, 12, 1, 11, 7, 9, 3, 6, 1,
+        4, 0, 5, 1, 3, 1, 12, 8, 3, 1, 11, 11,
+        9, 4, 12, 3, 12, 9, 11, 1, 7, 9, 7, 2,
+    ];
+    let n = 12;
+    let mut v: VecDeque<_> = (0..n).collect();
+    let mut total_shift = 0;
+    for shift in shifts.iter().cloned() {
+        v.rotate_left(shift);
+        total_shift += shift;
+        for i in 0..n {
+            assert_eq!(v[i], (i + total_shift) % n);
+        }
+    }
+}
+
+#[test]
+fn test_rotate_right_random() {
+    let shifts = [
+        6, 1, 0, 11, 12, 1, 11, 7, 9, 3, 6, 1,
+        4, 0, 5, 1, 3, 1, 12, 8, 3, 1, 11, 11,
+        9, 4, 12, 3, 12, 9, 11, 1, 7, 9, 7, 2,
+    ];
+    let n = 12;
+    let mut v: VecDeque<_> = (0..n).collect();
+    let mut total_shift = 0;
+    for shift in shifts.iter().cloned() {
+        v.rotate_right(shift);
+        total_shift += shift;
+        for i in 0..n {
+            assert_eq!(v[(i + total_shift) % n], i);
+        }
+    }
+}