Merge remote-tracking branch 'upstream/master'

16 files changed, 136 insertions, 161 deletions

diff --git a/src/liballoc/tests/arc.rs b/src/liballoc/tests/arc.rs
index ec589710216..2759b1b1cac 100644
--- a/src/liballoc/tests/arc.rs
+++ b/src/liballoc/tests/arc.rs
@@ -1,13 +1,3 @@
-// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
 use std::any::Any;
 use std::sync::{Arc, Weak};
 use std::cell::RefCell;
diff --git a/src/liballoc/tests/binary_heap.rs b/src/liballoc/tests/binary_heap.rs
index 536291de8f0..6af1cf40809 100644
--- a/src/liballoc/tests/binary_heap.rs
+++ b/src/liballoc/tests/binary_heap.rs
@@ -1,13 +1,3 @@
-// Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
 use std::cmp;
 use std::collections::BinaryHeap;
 use std::collections::binary_heap::{Drain, PeekMut};
diff --git a/src/liballoc/tests/btree/map.rs b/src/liballoc/tests/btree/map.rs
index 33ef13ab811..05e0bdffaa8 100644
--- a/src/liballoc/tests/btree/map.rs
+++ b/src/liballoc/tests/btree/map.rs
@@ -1,13 +1,3 @@
-// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
 use std::collections::BTreeMap;
 use std::collections::btree_map::Entry::{Occupied, Vacant};
 use std::ops::Bound::{self, Excluded, Included, Unbounded};
diff --git a/src/liballoc/tests/btree/mod.rs b/src/liballoc/tests/btree/mod.rs
index ae8b18d0c9f..4c704d0f8c2 100644
--- a/src/liballoc/tests/btree/mod.rs
+++ b/src/liballoc/tests/btree/mod.rs
@@ -1,13 +1,3 @@
-// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
 mod map;
 mod set;
 
diff --git a/src/liballoc/tests/btree/set.rs b/src/liballoc/tests/btree/set.rs
index 0330bda5e32..e24c04fd8ac 100644
--- a/src/liballoc/tests/btree/set.rs
+++ b/src/liballoc/tests/btree/set.rs
@@ -1,13 +1,3 @@
-// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
 use std::collections::BTreeSet;
 
 use std::iter::FromIterator;
diff --git a/src/liballoc/tests/cow_str.rs b/src/liballoc/tests/cow_str.rs
index 63939686ab7..eb6adb159b0 100644
--- a/src/liballoc/tests/cow_str.rs
+++ b/src/liballoc/tests/cow_str.rs
@@ -1,13 +1,3 @@
-// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
 use std::borrow::Cow;
 
 // check that Cow<'a, str> implements addition
diff --git a/src/liballoc/tests/fmt.rs b/src/liballoc/tests/fmt.rs
index 70e21c65a18..0ad092b4997 100644
--- a/src/liballoc/tests/fmt.rs
+++ b/src/liballoc/tests/fmt.rs
@@ -1,13 +1,3 @@
-// Copyright 2013-2015 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
 use std::fmt;
 
 #[test]
diff --git a/src/liballoc/tests/heap.rs b/src/liballoc/tests/heap.rs
index bf256b23f9a..24eea1d2949 100644
--- a/src/liballoc/tests/heap.rs
+++ b/src/liballoc/tests/heap.rs
@@ -1,13 +1,3 @@
-// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
 use std::alloc::{Global, Alloc, Layout, System};
 
 /// https://github.com/rust-lang/rust/issues/45955
diff --git a/src/liballoc/tests/lib.rs b/src/liballoc/tests/lib.rs
index e514a8a69c0..a76fd87a1a9 100644
--- a/src/liballoc/tests/lib.rs
+++ b/src/liballoc/tests/lib.rs
@@ -1,23 +1,14 @@
-// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
 #![feature(allocator_api)]
 #![feature(box_syntax)]
 #![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/linked_list.rs b/src/liballoc/tests/linked_list.rs
index 4e3e855105e..6e775f9650d 100644
--- a/src/liballoc/tests/linked_list.rs
+++ b/src/liballoc/tests/linked_list.rs
@@ -1,13 +1,3 @@
-// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
 use std::collections::LinkedList;
 
 #[test]
diff --git a/src/liballoc/tests/rc.rs b/src/liballoc/tests/rc.rs
index 02e1dfe13bb..18f82e80410 100644
--- a/src/liballoc/tests/rc.rs
+++ b/src/liballoc/tests/rc.rs
@@ -1,13 +1,3 @@
-// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
 use std::any::Any;
 use std::rc::{Rc, Weak};
 use std::cell::RefCell;
diff --git a/src/liballoc/tests/slice.rs b/src/liballoc/tests/slice.rs
index 6f31e6ca1a1..8ecd17236c0 100644
--- a/src/liballoc/tests/slice.rs
+++ b/src/liballoc/tests/slice.rs
@@ -1,13 +1,3 @@
-// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
 use std::cell::Cell;
 use std::cmp::Ordering::{Equal, Greater, Less};
 use std::cmp::Ordering;
diff --git a/src/liballoc/tests/str.rs b/src/liballoc/tests/str.rs
index 9ad8ad1fc07..66a1b947a7d 100644
--- a/src/liballoc/tests/str.rs
+++ b/src/liballoc/tests/str.rs
@@ -1,13 +1,3 @@
-// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
 use std::borrow::Cow;
 use std::cmp::Ordering::{Equal, Greater, Less};
 use std::str::from_utf8;
diff --git a/src/liballoc/tests/string.rs b/src/liballoc/tests/string.rs
index befb36baeef..8a5bfca8b7d 100644
--- a/src/liballoc/tests/string.rs
+++ b/src/liballoc/tests/string.rs
@@ -1,13 +1,3 @@
-// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
 use std::borrow::Cow;
 use std::collections::CollectionAllocErr::*;
 use std::mem::size_of;
diff --git a/src/liballoc/tests/vec.rs b/src/liballoc/tests/vec.rs
index 509195cd047..0fdcf34c783 100644
--- a/src/liballoc/tests/vec.rs
+++ b/src/liballoc/tests/vec.rs
@@ -1,13 +1,3 @@
-// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
 use std::borrow::Cow;
 use std::mem::size_of;
 use std::{usize, isize};
diff --git a/src/liballoc/tests/vec_deque.rs b/src/liballoc/tests/vec_deque.rs
index 1f2a7211c65..76831ba65e3 100644
--- a/src/liballoc/tests/vec_deque.rs
+++ b/src/liballoc/tests/vec_deque.rs
@@ -1,13 +1,3 @@
-// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
 use std::collections::VecDeque;
 use std::fmt::Debug;
 use std::collections::vec_deque::{Drain};
@@ -1309,3 +1299,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);
+        }
+    }
+}