Merge branch 'master' into copied

23 files changed, 756 insertions, 151 deletions

diff --git a/src/liballoc/Cargo.toml b/src/liballoc/Cargo.toml
index 642a43d4d9c..b2eb3566c04 100644
--- a/src/liballoc/Cargo.toml
+++ b/src/liballoc/Cargo.toml
@@ -11,10 +11,10 @@ path = "lib.rs"
 
 [dependencies]
 core = { path = "../libcore" }
-compiler_builtins = { path = "../rustc/compiler_builtins_shim" }
+compiler_builtins = { version = "0.1.0", features = ['rustc-dep-of-std'] }
 
 [dev-dependencies]
-rand = "0.5"
+rand = "0.6"
 
 [[test]]
 name = "collectionstests"
@@ -28,3 +28,6 @@ path = "../liballoc/benches/lib.rs"
 name = "vec_deque_append_bench"
 path = "../liballoc/benches/vec_deque_append.rs"
 harness = false
+
+[features]
+compiler-builtins-mem = ['compiler_builtins/mem']
diff --git a/src/liballoc/boxed.rs b/src/liballoc/boxed.rs
index c3a84bf778d..f1581310b48 100644
--- a/src/liballoc/boxed.rs
+++ b/src/liballoc/boxed.rs
@@ -77,7 +77,9 @@ use core::iter::{Iterator, FromIterator, FusedIterator};
 use core::marker::{Unpin, Unsize};
 use core::mem;
 use core::pin::Pin;
-use core::ops::{CoerceUnsized, DispatchFromDyn, Deref, DerefMut, Generator, GeneratorState};
+use core::ops::{
+    CoerceUnsized, DispatchFromDyn, Deref, DerefMut, Receiver, Generator, GeneratorState
+};
 use core::ptr::{self, NonNull, Unique};
 use core::task::{LocalWaker, Poll};
 
@@ -583,6 +585,9 @@ impl<T: ?Sized> DerefMut for Box<T> {
     }
 }
 
+#[unstable(feature = "receiver_trait", issue = "0")]
+impl<T: ?Sized> Receiver for Box<T> {}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<I: Iterator + ?Sized> Iterator for Box<I> {
     type Item = I::Item;
@@ -801,7 +806,7 @@ impl<T: ?Sized> AsMut<T> for Box<T> {
  *        safe.)
  *      - It is in practice very useful to have Box<T> be unconditionally
  *        Unpin because of trait objects, for which the structural auto
- *        trait functionality does not apply (e.g. Box<dyn Foo> would
+ *        trait functionality does not apply (e.g., Box<dyn Foo> would
  *        otherwise not be Unpin).
  *
  *  Another type with the same semantics as Box but only a conditional
diff --git a/src/liballoc/collections/binary_heap.rs b/src/liballoc/collections/binary_heap.rs
index 8c36962a299..5dd0ea7d431 100644
--- a/src/liballoc/collections/binary_heap.rs
+++ b/src/liballoc/collections/binary_heap.rs
@@ -858,7 +858,7 @@ impl<T: Ord> BinaryHeap<T> {
     }
 }
 
-/// Hole represents a hole in a slice i.e. an index without valid value
+/// Hole represents a hole in a slice i.e., an index without valid value
 /// (because it was moved from or duplicated).
 /// In drop, `Hole` will restore the slice by filling the hole
 /// position with the value that was originally removed.
diff --git a/src/liballoc/collections/btree/node.rs b/src/liballoc/collections/btree/node.rs
index 215689dfc48..a2d2d3c74be 100644
--- a/src/liballoc/collections/btree/node.rs
+++ b/src/liballoc/collections/btree/node.rs
@@ -58,9 +58,34 @@ pub const CAPACITY: usize = 2 * B - 1;
 /// these should always be put behind pointers, and specifically behind `BoxedNode` in the owned
 /// case.
 ///
-/// We put the metadata first so that its position is the same for every `K` and `V`, in order
-/// to statically allocate a single dummy node to avoid allocations. This struct is `repr(C)` to
-/// prevent them from being reordered.
+/// We have a separate type for the header and rely on it matching the prefix of `LeafNode`, in
+/// order to statically allocate a single dummy node to avoid allocations. This struct is
+/// `repr(C)` to prevent them from being reordered.  `LeafNode` does not just contain a
+/// `NodeHeader` because we do not want unnecessary padding between `len` and the keys.
+/// Crucially, `NodeHeader` can be safely transmuted to different K and V.  (This is exploited
+/// by `as_header`.)
+/// See `into_key_slice` for an explanation of K2.  K2 cannot be safely transmuted around
+/// because the size of `NodeHeader` depends on its alignment!
+#[repr(C)]
+struct NodeHeader<K, V, K2 = ()> {
+    /// We use `*const` as opposed to `*mut` so as to be covariant in `K` and `V`.
+    /// This either points to an actual node or is null.
+    parent: *const InternalNode<K, V>,
+
+    /// This node's index into the parent node's `edges` array.
+    /// `*node.parent.edges[node.parent_idx]` should be the same thing as `node`.
+    /// This is only guaranteed to be initialized when `parent` is non-null.
+    parent_idx: MaybeUninit<u16>,
+
+    /// The number of keys and values this node stores.
+    ///
+    /// This next to `parent_idx` to encourage the compiler to join `len` and
+    /// `parent_idx` into the same 32-bit word, reducing space overhead.
+    len: u16,
+
+    /// See `into_key_slice`.
+    keys_start: [K2; 0],
+}
 #[repr(C)]
 struct LeafNode<K, V> {
     /// We use `*const` as opposed to `*mut` so as to be covariant in `K` and `V`.
@@ -98,24 +123,25 @@ impl<K, V> LeafNode<K, V> {
             len: 0
         }
     }
+}
 
+impl<K, V> NodeHeader<K, V> {
     fn is_shared_root(&self) -> bool {
         ptr::eq(self, &EMPTY_ROOT_NODE as *const _ as *const _)
     }
 }
 
 // We need to implement Sync here in order to make a static instance.
-unsafe impl Sync for LeafNode<(), ()> {}
+unsafe impl Sync for NodeHeader<(), ()> {}
 
 // An empty node used as a placeholder for the root node, to avoid allocations.
-// We use () in order to save space, since no operation on an empty tree will
+// We use just a header in order to save space, since no operation on an empty tree will
 // ever take a pointer past the first key.
-static EMPTY_ROOT_NODE: LeafNode<(), ()> = LeafNode {
+static EMPTY_ROOT_NODE: NodeHeader<(), ()> = NodeHeader {
     parent: ptr::null(),
     parent_idx: MaybeUninit::uninitialized(),
     len: 0,
-    keys: MaybeUninit::uninitialized(),
-    vals: MaybeUninit::uninitialized(),
+    keys_start: [],
 };
 
 /// The underlying representation of internal nodes. As with `LeafNode`s, these should be hidden
@@ -281,7 +307,7 @@ impl<K, V> Root<K, V> {
                                     .node)
         };
         self.height -= 1;
-        self.as_mut().as_leaf_mut().parent = ptr::null();
+        unsafe { (*self.as_mut().as_leaf_mut()).parent = ptr::null(); }
 
         unsafe {
             Global.dealloc(NonNull::from(top).cast(), Layout::new::<InternalNode<K, V>>());
@@ -306,6 +332,11 @@ impl<K, V> Root<K, V> {
 ///   `Leaf`, the `NodeRef` points to a leaf node, when this is `Internal` the
 ///   `NodeRef` points to an internal node, and when this is `LeafOrInternal` the
 ///   `NodeRef` could be pointing to either type of node.
+///   Note that in case of a leaf node, this might still be the shared root!  Only turn
+///   this into a `LeafNode` reference if you know it is not a root!  Shared references
+///   must be dereferencable *for the entire size of their pointee*, so `&InternalNode`
+///   pointing to the shared root is UB.
+///   Turning this into a `NodeHeader` is always safe.
 pub struct NodeRef<BorrowType, K, V, Type> {
     height: usize,
     node: NonNull<LeafNode<K, V>>,
@@ -352,7 +383,7 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
     /// Finds the length of the node. This is the number of keys or values. In an
     /// internal node, the number of edges is `len() + 1`.
     pub fn len(&self) -> usize {
-        self.as_leaf().len as usize
+        self.as_header().len as usize
     }
 
     /// Returns the height of this node in the whole tree. Zero height denotes the
@@ -382,14 +413,19 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
         }
     }
 
-    fn as_leaf(&self) -> &LeafNode<K, V> {
+    /// Assert that this is indeed a proper leaf node, and not the shared root.
+    unsafe fn as_leaf(&self) -> &LeafNode<K, V> {
+        self.node.as_ref()
+    }
+
+    fn as_header(&self) -> &NodeHeader<K, V> {
         unsafe {
-            self.node.as_ref()
+            &*(self.node.as_ptr() as *const NodeHeader<K, V>)
         }
     }
 
     pub fn is_shared_root(&self) -> bool {
-        self.as_leaf().is_shared_root()
+        self.as_header().is_shared_root()
     }
 
     pub fn keys(&self) -> &[K] {
@@ -418,7 +454,7 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
         >,
         Self
     > {
-        let parent_as_leaf = self.as_leaf().parent as *const LeafNode<K, V>;
+        let parent_as_leaf = self.as_header().parent as *const LeafNode<K, V>;
         if let Some(non_zero) = NonNull::new(parent_as_leaf as *mut _) {
             Ok(Handle {
                 node: NodeRef {
@@ -427,7 +463,7 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
                     root: self.root,
                     _marker: PhantomData
                 },
-                idx: unsafe { usize::from(*self.as_leaf().parent_idx.get_ref()) },
+                idx: unsafe { usize::from(*self.as_header().parent_idx.get_ref()) },
                 _marker: PhantomData
             })
         } else {
@@ -534,10 +570,10 @@ impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
         }
     }
 
-    fn as_leaf_mut(&mut self) -> &mut LeafNode<K, V> {
-        unsafe {
-            self.node.as_mut()
-        }
+    /// Returns a raw ptr to avoid asserting exclusive access to the entire node.
+    fn as_leaf_mut(&mut self) -> *mut LeafNode<K, V> {
+        // We are mutable, so we cannot be the root, so accessing this as a leaf is okay.
+        self.node.as_ptr()
     }
 
     fn keys_mut(&mut self) -> &mut [K] {
@@ -551,28 +587,50 @@ impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
 
 impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
     fn into_key_slice(self) -> &'a [K] {
-        // When taking a pointer to the keys, if our key has a stricter
-        // alignment requirement than the shared root does, then the pointer
-        // would be out of bounds, which LLVM assumes will not happen. If the
-        // alignment is more strict, we need to make an empty slice that doesn't
-        // use an out of bounds pointer.
+        // We have to be careful here because we might be pointing to the shared root.
+        // In that case, we must not create an `&LeafNode`.  We could just return
+        // an empty slice whenever the length is 0 (this includes the shared root),
+        // but we want to avoid that run-time check.
+        // Instead, we create a slice pointing into the node whenever possible.
+        // We can sometimes do this even for the shared root, as the slice will be
+        // empty.  We cannot *always* do this because if the type is too highly
+        // aligned, the offset of `keys` in a "full node" might be outside the bounds
+        // of the header!  So we do an alignment check first, that will be
+        // evaluated at compile-time, and only do any run-time check in the rare case
+        // that the alignment is very big.
         if mem::align_of::<K>() > mem::align_of::<LeafNode<(), ()>>() && self.is_shared_root() {
             &[]
         } else {
-            // Here either it's not the root, or the alignment is less strict,
-            // in which case the keys pointer will point "one-past-the-end" of
-            // the node, which is allowed by LLVM.
+            // Thanks to the alignment check above, we know that `keys` will be
+            // in-bounds of some allocation even if this is the shared root!
+            // (We might be one-past-the-end, but that is allowed by LLVM.)
+            // Getting the pointer is tricky though.  `NodeHeader` does not have a `keys`
+            // field because we want its size to not depend on the alignment of `K`
+            // (needed becuase `as_header` should be safe).  We cannot call `as_leaf`
+            // because we might be the shared root.
+            // For this reason, `NodeHeader` has this `K2` parameter (that's usually `()`
+            // and hence just adds a size-0-align-1 field, not affecting layout).
+            // We know that we can transmute `NodeHeader<K, V, ()>` to `NodeHeader<K, V, K>`
+            // because we did the alignment check above, and hence `NodeHeader<K, V, K>`
+            // is not bigger than `NodeHeader<K, V, ()>`!  Then we can use `NodeHeader<K, V, K>`
+            // to compute the pointer where the keys start.
+            // This entire hack will become unnecessary once
+            // <https://github.com/rust-lang/rfcs/pull/2582> lands, then we can just take a raw
+            // pointer to the `keys` field of `*const InternalNode<K, V>`.
+
+            // This is a non-debug-assert because it can be completely compile-time evaluated.
+            assert!(mem::size_of::<NodeHeader<K, V>>() == mem::size_of::<NodeHeader<K, V, K>>());
+            let header = self.as_header() as *const _ as *const NodeHeader<K, V, K>;
+            let keys = unsafe { &(*header).keys_start as *const _ as *const K };
             unsafe {
-                slice::from_raw_parts(
-                    self.as_leaf().keys.as_ptr() as *const K,
-                    self.len()
-                )
+                slice::from_raw_parts(keys, self.len())
             }
         }
     }
 
     fn into_val_slice(self) -> &'a [V] {
         debug_assert!(!self.is_shared_root());
+        // We cannot be the root, so `as_leaf` is okay
         unsafe {
             slice::from_raw_parts(
                 self.as_leaf().vals.as_ptr() as *const V,
@@ -602,7 +660,7 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
         } else {
             unsafe {
                 slice::from_raw_parts_mut(
-                    self.as_leaf_mut().keys.as_mut_ptr() as *mut K,
+                    (*self.as_leaf_mut()).keys.as_mut_ptr() as *mut K,
                     self.len()
                 )
             }
@@ -613,7 +671,7 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
         debug_assert!(!self.is_shared_root());
         unsafe {
             slice::from_raw_parts_mut(
-                self.as_leaf_mut().vals.as_mut_ptr() as *mut V,
+                (*self.as_leaf_mut()).vals.as_mut_ptr() as *mut V,
                 self.len()
             )
         }
@@ -637,9 +695,9 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
         unsafe {
             ptr::write(self.keys_mut().get_unchecked_mut(idx), key);
             ptr::write(self.vals_mut().get_unchecked_mut(idx), val);
-        }
 
-        self.as_leaf_mut().len += 1;
+            (*self.as_leaf_mut()).len += 1;
+        }
     }
 
     /// Adds a key/value pair to the beginning of the node.
@@ -651,9 +709,9 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
         unsafe {
             slice_insert(self.keys_mut(), 0, key);
             slice_insert(self.vals_mut(), 0, val);
-        }
 
-        self.as_leaf_mut().len += 1;
+            (*self.as_leaf_mut()).len += 1;
+        }
     }
 }
 
@@ -672,7 +730,7 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
             ptr::write(self.vals_mut().get_unchecked_mut(idx), val);
             ptr::write(self.as_internal_mut().edges.get_unchecked_mut(idx + 1), edge.node);
 
-            self.as_leaf_mut().len += 1;
+            (*self.as_leaf_mut()).len += 1;
 
             Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link();
         }
@@ -708,7 +766,7 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
                 edge.node
             );
 
-            self.as_leaf_mut().len += 1;
+            (*self.as_leaf_mut()).len += 1;
 
             self.correct_all_childrens_parent_links();
         }
@@ -732,12 +790,12 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
                 ForceResult::Internal(internal) => {
                     let edge = ptr::read(internal.as_internal().edges.get_unchecked(idx + 1));
                     let mut new_root = Root { node: edge, height: internal.height - 1 };
-                    new_root.as_mut().as_leaf_mut().parent = ptr::null();
+                    (*new_root.as_mut().as_leaf_mut()).parent = ptr::null();
                     Some(new_root)
                 }
             };
 
-            self.as_leaf_mut().len -= 1;
+            (*self.as_leaf_mut()).len -= 1;
             (key, val, edge)
         }
     }
@@ -765,7 +823,7 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
                     );
 
                     let mut new_root = Root { node: edge, height: internal.height - 1 };
-                    new_root.as_mut().as_leaf_mut().parent = ptr::null();
+                    (*new_root.as_mut().as_leaf_mut()).parent = ptr::null();
 
                     for i in 0..old_len {
                         Handle::new_edge(internal.reborrow_mut(), i).correct_parent_link();
@@ -775,7 +833,7 @@ impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
                 }
             };
 
-            self.as_leaf_mut().len -= 1;
+            (*self.as_leaf_mut()).len -= 1;
 
             (key, val, edge)
         }
@@ -966,7 +1024,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge
             slice_insert(self.node.keys_mut(), self.idx, key);
             slice_insert(self.node.vals_mut(), self.idx, val);
 
-            self.node.as_leaf_mut().len += 1;
+            (*self.node.as_leaf_mut()).len += 1;
 
             self.node.vals_mut().get_unchecked_mut(self.idx)
         }
@@ -1009,8 +1067,10 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
         let idx = self.idx as u16;
         let ptr = self.node.as_internal_mut() as *mut _;
         let mut child = self.descend();
-        child.as_leaf_mut().parent = ptr;
-        child.as_leaf_mut().parent_idx.set(idx);
+        unsafe {
+            (*child.as_leaf_mut()).parent = ptr;
+            (*child.as_leaf_mut()).parent_idx.set(idx);
+        }
     }
 
     /// Unsafely asserts to the compiler some static information about whether the underlying
@@ -1158,7 +1218,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV>
                 new_len
             );
 
-            self.node.as_leaf_mut().len = self.idx as u16;
+            (*self.node.as_leaf_mut()).len = self.idx as u16;
             new_node.len = new_len as u16;
 
             (
@@ -1180,7 +1240,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV>
         unsafe {
             let k = slice_remove(self.node.keys_mut(), self.idx);
             let v = slice_remove(self.node.vals_mut(), self.idx);
-            self.node.as_leaf_mut().len -= 1;
+            (*self.node.as_leaf_mut()).len -= 1;
             (self.left_edge(), k, v)
         }
     }
@@ -1221,7 +1281,7 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
                 new_len + 1
             );
 
-            self.node.as_leaf_mut().len = self.idx as u16;
+            (*self.node.as_leaf_mut()).len = self.idx as u16;
             new_node.data.len = new_len as u16;
 
             let mut new_root = Root {
@@ -1295,9 +1355,9 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
             for i in self.idx+1..self.node.len() {
                 Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link();
             }
-            self.node.as_leaf_mut().len -= 1;
+            (*self.node.as_leaf_mut()).len -= 1;
 
-            left_node.as_leaf_mut().len += right_len as u16 + 1;
+            (*left_node.as_leaf_mut()).len += right_len as u16 + 1;
 
             if self.node.height > 1 {
                 ptr::copy_nonoverlapping(
@@ -1407,8 +1467,8 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
                 move_kv(left_kv, new_left_len, parent_kv, 0, 1);
             }
 
-            left_node.reborrow_mut().as_leaf_mut().len -= count as u16;
-            right_node.reborrow_mut().as_leaf_mut().len += count as u16;
+            (*left_node.reborrow_mut().as_leaf_mut()).len -= count as u16;
+            (*right_node.reborrow_mut().as_leaf_mut()).len += count as u16;
 
             match (left_node.force(), right_node.force()) {
                 (ForceResult::Internal(left), ForceResult::Internal(mut right)) => {
@@ -1468,8 +1528,8 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::
                           new_right_len);
             }
 
-            left_node.reborrow_mut().as_leaf_mut().len += count as u16;
-            right_node.reborrow_mut().as_leaf_mut().len -= count as u16;
+            (*left_node.reborrow_mut().as_leaf_mut()).len += count as u16;
+            (*right_node.reborrow_mut().as_leaf_mut()).len -= count as u16;
 
             match (left_node.force(), right_node.force()) {
                 (ForceResult::Internal(left), ForceResult::Internal(mut right)) => {
@@ -1560,8 +1620,8 @@ impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, ma
 
             move_kv(left_kv, left_new_len, right_kv, 0, right_new_len);
 
-            left_node.reborrow_mut().as_leaf_mut().len = left_new_len as u16;
-            right_node.reborrow_mut().as_leaf_mut().len = right_new_len as u16;
+            (*left_node.reborrow_mut().as_leaf_mut()).len = left_new_len as u16;
+            (*right_node.reborrow_mut().as_leaf_mut()).len = right_new_len as u16;
 
             match (left_node.force(), right_node.force()) {
                 (ForceResult::Internal(left), ForceResult::Internal(right)) => {
diff --git a/src/liballoc/collections/btree/set.rs b/src/liballoc/collections/btree/set.rs
index af9a7074e4a..fa74dce2f1f 100644
--- a/src/liballoc/collections/btree/set.rs
+++ b/src/liballoc/collections/btree/set.rs
@@ -258,7 +258,7 @@ impl<T: Ord> BTreeSet<T> {
     }
 
     /// Visits the values representing the difference,
-    /// i.e. the values that are in `self` but not in `other`,
+    /// i.e., the values that are in `self` but not in `other`,
     /// in ascending order.
     ///
     /// # Examples
@@ -286,7 +286,7 @@ impl<T: Ord> BTreeSet<T> {
     }
 
     /// Visits the values representing the symmetric difference,
-    /// i.e. the values that are in `self` or in `other` but not in both,
+    /// i.e., the values that are in `self` or in `other` but not in both,
     /// in ascending order.
     ///
     /// # Examples
@@ -316,7 +316,7 @@ impl<T: Ord> BTreeSet<T> {
     }
 
     /// Visits the values representing the intersection,
-    /// i.e. the values that are both in `self` and `other`,
+    /// i.e., the values that are both in `self` and `other`,
     /// in ascending order.
     ///
     /// # Examples
@@ -344,7 +344,7 @@ impl<T: Ord> BTreeSet<T> {
     }
 
     /// Visits the values representing the union,
-    /// i.e. all the values in `self` or `other`, without duplicates,
+    /// i.e., all the values in `self` or `other`, without duplicates,
     /// in ascending order.
     ///
     /// # Examples
@@ -455,7 +455,7 @@ impl<T: Ord> BTreeSet<T> {
     }
 
     /// Returns `true` if the set is a subset of another,
-    /// i.e. `other` contains at least all the values in `self`.
+    /// i.e., `other` contains at least all the values in `self`.
     ///
     /// # Examples
     ///
@@ -498,7 +498,7 @@ impl<T: Ord> BTreeSet<T> {
     }
 
     /// Returns `true` if the set is a superset of another,
-    /// i.e. `self` contains at least all the values in `other`.
+    /// i.e., `self` contains at least all the values in `other`.
     ///
     /// # Examples
     ///
diff --git a/src/liballoc/collections/linked_list.rs b/src/liballoc/collections/linked_list.rs
index 2ef84dbade0..ba46fafaf16 100644
--- a/src/liballoc/collections/linked_list.rs
+++ b/src/liballoc/collections/linked_list.rs
@@ -627,7 +627,9 @@ impl<T> LinkedList<T> {
         self.pop_front_node().map(Node::into_element)
     }
 
-    /// Appends an element to the back of a list
+    /// Appends an element to the back of a list.
+    ///
+    /// This operation should compute in O(1) time.
     ///
     /// # Examples
     ///
@@ -647,6 +649,8 @@ impl<T> LinkedList<T> {
     /// Removes the last element from a list and returns it, or `None` if
     /// it is empty.
     ///
+    /// This operation should compute in O(1) time.
+    ///
     /// # Examples
     ///
     /// ```
diff --git a/src/liballoc/collections/vec_deque.rs b/src/liballoc/collections/vec_deque.rs
index c8ee40f3d27..553c6d7291a 100644
--- a/src/liballoc/collections/vec_deque.rs
+++ b/src/liballoc/collections/vec_deque.rs
@@ -1026,7 +1026,10 @@ impl<T> VecDeque<T> {
             iter: Iter {
                 tail: drain_tail,
                 head: drain_head,
-                ring: unsafe { self.buffer_as_mut_slice() },
+                // Crucially, we only create shared references from `self` here and read from
+                // it.  We do not write to `self` nor reborrow to a mutable reference.
+                // Hence the raw pointer we created above, for `deque`, remains valid.
+                ring: unsafe { self.buffer_as_slice() },
             },
         }
     }
@@ -1894,8 +1897,6 @@ impl<T> VecDeque<T> {
     /// # Examples
     ///
     /// ```
-    /// #![feature(vec_resize_with)]
-    ///
     /// use std::collections::VecDeque;
     ///
     /// let mut buf = VecDeque::new();
@@ -1914,7 +1915,7 @@ impl<T> VecDeque<T> {
     /// buf.resize_with(5, || { state += 1; state });
     /// assert_eq!(buf, [5, 10, 101, 102, 103]);
     /// ```
-    #[unstable(feature = "vec_resize_with", issue = "41758")]
+    #[stable(feature = "vec_resize_with", since = "1.33.0")]
     pub fn resize_with(&mut self, new_len: usize, generator: impl FnMut()->T) {
         let len = self.len();
 
@@ -1924,6 +1925,118 @@ impl<T> VecDeque<T> {
             self.truncate(new_len);
         }
     }
+
+    /// Rotates the double-ended queue `mid` places to the left.
+    ///
+    /// Equivalently,
+    /// - Rotates item `mid` into the first position.
+    /// - Pops the first `mid` items and pushes them to the end.
+    /// - Rotates `len() - mid` places to the right.
+    ///
+    /// # Panics
+    ///
+    /// If `mid` is greater than `len()`.  Note that `mid == len()`
+    /// does _not_ panic and is a no-op rotation.
+    ///
+    /// # Complexity
+    ///
+    /// Takes `O(min(mid, len() - mid))` time and no extra space.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(vecdeque_rotate)]
+    ///
+    /// use std::collections::VecDeque;
+    ///
+    /// let mut buf: VecDeque<_> = (0..10).collect();
+    ///
+    /// buf.rotate_left(3);
+    /// assert_eq!(buf, [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]);
+    ///
+    /// for i in 1..10 {
+    ///     assert_eq!(i * 3 % 10, buf[0]);
+    ///     buf.rotate_left(3);
+    /// }
+    /// assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
+    /// ```
+    #[unstable(feature = "vecdeque_rotate", issue = "56686")]
+    pub fn rotate_left(&mut self, mid: usize) {
+        assert!(mid <= self.len());
+        let k = self.len() - mid;
+        if mid <= k {
+            unsafe { self.rotate_left_inner(mid) }
+        } else {
+            unsafe { self.rotate_right_inner(k) }
+        }
+    }
+
+    /// Rotates the double-ended queue `k` places to the right.
+    ///
+    /// Equivalently,
+    /// - Rotates the first item into position `k`.
+    /// - Pops the last `k` items and pushes them to the front.
+    /// - Rotates `len() - k` places to the left.
+    ///
+    /// # Panics
+    ///
+    /// If `k` is greater than `len()`.  Note that `k == len()`
+    /// does _not_ panic and is a no-op rotation.
+    ///
+    /// # Complexity
+    ///
+    /// Takes `O(min(k, len() - k))` time and no extra space.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(vecdeque_rotate)]
+    ///
+    /// use std::collections::VecDeque;
+    ///
+    /// let mut buf: VecDeque<_> = (0..10).collect();
+    ///
+    /// buf.rotate_right(3);
+    /// assert_eq!(buf, [7, 8, 9, 0, 1, 2, 3, 4, 5, 6]);
+    ///
+    /// for i in 1..10 {
+    ///     assert_eq!(0, buf[i * 3 % 10]);
+    ///     buf.rotate_right(3);
+    /// }
+    /// assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
+    /// ```
+    #[unstable(feature = "vecdeque_rotate", issue = "56686")]
+    pub fn rotate_right(&mut self, k: usize) {
+        assert!(k <= self.len());
+        let mid = self.len() - k;
+        if k <= mid {
+            unsafe { self.rotate_right_inner(k) }
+        } else {
+            unsafe { self.rotate_left_inner(mid) }
+        }
+    }
+
+    // Safety: the following two methods require that the rotation amount
+    // be less than half the length of the deque.
+    //
+    // `wrap_copy` requres that `min(x, cap() - x) + copy_len <= cap()`,
+    // but than `min` is never more than half the capacity, regardless of x,
+    // so it's sound to call here because we're calling with something
+    // less than half the length, which is never above half the capacity.
+
+    unsafe fn rotate_left_inner(&mut self, mid: usize) {
+        debug_assert!(mid * 2 <= self.len());
+        self.wrap_copy(self.head, self.tail, mid);
+        self.head = self.wrap_add(self.head, mid);
+        self.tail = self.wrap_add(self.tail, mid);
+    }
+
+    unsafe fn rotate_right_inner(&mut self, k: usize) {
+        debug_assert!(k * 2 <= self.len());
+        self.head = self.wrap_sub(self.head, k);
+        self.tail = self.wrap_sub(self.tail, k);
+        self.wrap_copy(self.tail, self.head, k);
+    }
 }
 
 impl<T: Clone> VecDeque<T> {
@@ -2795,7 +2908,7 @@ mod tests {
             // 0, 1, 2, .., len - 1
             let expected = (0..).take(len).collect::<VecDeque<_>>();
             for tail_pos in 0..cap {
-                for to_remove in 0..len + 1 {
+                for to_remove in 0..=len {
                     tester.tail = tail_pos;
                     tester.head = tail_pos;
                     for i in 0..len {
@@ -2821,10 +2934,10 @@ mod tests {
         let mut tester: VecDeque<usize> = VecDeque::with_capacity(7);
 
         let cap = tester.capacity();
-        for len in 0..cap + 1 {
-            for tail in 0..cap + 1 {
-                for drain_start in 0..len + 1 {
-                    for drain_end in drain_start..len + 1 {
+        for len in 0..=cap {
+            for tail in 0..=cap {
+                for drain_start in 0..=len {
+                    for drain_end in drain_start..=len {
                         tester.tail = tail;
                         tester.head = tail;
                         for i in 0..len {
@@ -2866,10 +2979,10 @@ mod tests {
         tester.reserve(63);
         let max_cap = tester.capacity();
 
-        for len in 0..cap + 1 {
+        for len in 0..=cap {
             // 0, 1, 2, .., len - 1
             let expected = (0..).take(len).collect::<VecDeque<_>>();
-            for tail_pos in 0..max_cap + 1 {
+            for tail_pos in 0..=max_cap {
                 tester.tail = tail_pos;
                 tester.head = tail_pos;
                 tester.reserve(63);
@@ -2899,7 +3012,7 @@ mod tests {
         // len is the length *before* splitting
         for len in 0..cap {
             // index to split at
-            for at in 0..len + 1 {
+            for at in 0..=len {
                 // 0, 1, 2, .., at - 1 (may be empty)
                 let expected_self = (0..).take(at).collect::<VecDeque<_>>();
                 // at, at + 1, .., len - 1 (may be empty)
@@ -2927,7 +3040,7 @@ mod tests {
     fn test_from_vec() {
         use vec::Vec;
         for cap in 0..35 {
-            for len in 0..cap + 1 {
+            for len in 0..=cap {
                 let mut vec = Vec::with_capacity(cap);
                 vec.extend(0..len);
 
diff --git a/src/liballoc/lib.rs b/src/liballoc/lib.rs
index abacc62c856..afa7a6f919d 100644
--- a/src/liballoc/lib.rs
+++ b/src/liballoc/lib.rs
@@ -72,6 +72,8 @@
        test(no_crate_inject, attr(allow(unused_variables), deny(warnings))))]
 #![no_std]
 #![needs_allocator]
+
+#![deny(intra_doc_link_resolution_failure)]
 #![deny(missing_debug_implementations)]
 
 #![cfg_attr(not(test), feature(fn_traits))]
@@ -104,6 +106,7 @@
 #![feature(ptr_internals)]
 #![feature(ptr_offset_from)]
 #![feature(rustc_attrs)]
+#![feature(receiver_trait)]
 #![feature(specialization)]
 #![feature(split_ascii_whitespace)]
 #![feature(staged_api)]
diff --git a/src/liballoc/raw_vec.rs b/src/liballoc/raw_vec.rs
index e87bf78561c..f4674b32769 100644
--- a/src/liballoc/raw_vec.rs
+++ b/src/liballoc/raw_vec.rs
@@ -739,7 +739,7 @@ unsafe impl<#[may_dangle] T, A: Alloc> Drop for RawVec<T, A> {
 // On 64-bit we just need to check for overflow since trying to allocate
 // `> isize::MAX` bytes will surely fail. On 32-bit and 16-bit we need to add
 // an extra guard for this in case we're running on a platform which can use
-// all 4GB in user-space. e.g. PAE or x32
+// all 4GB in user-space. e.g., PAE or x32
 
 #[inline]
 fn alloc_guard(alloc_size: usize) -> Result<(), CollectionAllocErr> {
diff --git a/src/liballoc/rc.rs b/src/liballoc/rc.rs
index 3ca6de191de..65a610b9d1e 100644
--- a/src/liballoc/rc.rs
+++ b/src/liballoc/rc.rs
@@ -253,7 +253,7 @@ use core::intrinsics::abort;
 use core::marker;
 use core::marker::{Unpin, Unsize, PhantomData};
 use core::mem::{self, align_of_val, forget, size_of_val};
-use core::ops::Deref;
+use core::ops::{Deref, Receiver};
 use core::ops::{CoerceUnsized, DispatchFromDyn};
 use core::pin::Pin;
 use core::ptr::{self, NonNull};
@@ -276,7 +276,7 @@ struct RcBox<T: ?Sized> {
 /// See the [module-level documentation](./index.html) for more details.
 ///
 /// The inherent methods of `Rc` are all associated functions, which means
-/// that you have to call them as e.g. [`Rc::get_mut(&mut value)`][get_mut] instead of
+/// that you have to call them as e.g., [`Rc::get_mut(&mut value)`][get_mut] instead of
 /// `value.get_mut()`. This avoids conflicts with methods of the inner
 /// type `T`.
 ///
@@ -813,6 +813,9 @@ impl<T: ?Sized> Deref for Rc<T> {
     }
 }
 
+#[unstable(feature = "receiver_trait", issue = "0")]
+impl<T: ?Sized> Receiver for Rc<T> {}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 unsafe impl<#[may_dangle] T: ?Sized> Drop for Rc<T> {
     /// Drops the `Rc`.
@@ -840,6 +843,8 @@ unsafe impl<#[may_dangle] T: ?Sized> Drop for Rc<T> {
     /// drop(foo);    // Doesn't print anything
     /// drop(foo2);   // Prints "dropped!"
     /// ```
+    ///
+    /// [`Weak`]: ../../std/rc/struct.Weak.html
     fn drop(&mut self) {
         unsafe {
             self.dec_strong();
@@ -901,11 +906,46 @@ impl<T: Default> Default for Rc<T> {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
+trait RcEqIdent<T: ?Sized + PartialEq> {
+    fn eq(&self, other: &Rc<T>) -> bool;
+    fn ne(&self, other: &Rc<T>) -> bool;
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T: ?Sized + PartialEq> RcEqIdent<T> for Rc<T> {
+    #[inline]
+    default fn eq(&self, other: &Rc<T>) -> bool {
+        **self == **other
+    }
+
+    #[inline]
+    default fn ne(&self, other: &Rc<T>) -> bool {
+        **self != **other
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T: ?Sized + Eq> RcEqIdent<T> for Rc<T> {
+    #[inline]
+    fn eq(&self, other: &Rc<T>) -> bool {
+        Rc::ptr_eq(self, other) || **self == **other
+    }
+
+    #[inline]
+    fn ne(&self, other: &Rc<T>) -> bool {
+        !Rc::ptr_eq(self, other) && **self != **other
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
 impl<T: ?Sized + PartialEq> PartialEq for Rc<T> {
     /// Equality for two `Rc`s.
     ///
     /// Two `Rc`s are equal if their inner values are equal.
     ///
+    /// If `T` also implements `Eq`, two `Rc`s that point to the same value are
+    /// always equal.
+    ///
     /// # Examples
     ///
     /// ```
@@ -915,15 +955,18 @@ impl<T: ?Sized + PartialEq> PartialEq for Rc<T> {
     ///
     /// assert!(five == Rc::new(5));
     /// ```
-    #[inline(always)]
+    #[inline]
     fn eq(&self, other: &Rc<T>) -> bool {
-        **self == **other
+        RcEqIdent::eq(self, other)
     }
 
     /// Inequality for two `Rc`s.
     ///
     /// Two `Rc`s are unequal if their inner values are unequal.
     ///
+    /// If `T` also implements `Eq`, two `Rc`s that point to the same value are
+    /// never unequal.
+    ///
     /// # Examples
     ///
     /// ```
@@ -933,9 +976,9 @@ impl<T: ?Sized + PartialEq> PartialEq for Rc<T> {
     ///
     /// assert!(five != Rc::new(6));
     /// ```
-    #[inline(always)]
+    #[inline]
     fn ne(&self, other: &Rc<T>) -> bool {
-        **self != **other
+        RcEqIdent::ne(self, other)
     }
 }
 
@@ -1187,8 +1230,9 @@ impl<T: ?Sized + Unsize<U>, U: ?Sized> DispatchFromDyn<Weak<U>> for Weak<T> {}
 
 impl<T> Weak<T> {
     /// Constructs a new `Weak<T>`, without allocating any memory.
-    /// Calling [`upgrade`][Weak::upgrade] on the return value always gives [`None`].
+    /// Calling [`upgrade`] on the return value always gives [`None`].
     ///
+    /// [`upgrade`]: #method.upgrade
     /// [`None`]: ../../std/option/enum.Option.html
     ///
     /// # Examples
@@ -1251,7 +1295,7 @@ impl<T: ?Sized> Weak<T> {
     }
 
     /// Return `None` when the pointer is dangling and there is no allocated `RcBox`,
-    /// i.e. this `Weak` was created by `Weak::new`
+    /// i.e., this `Weak` was created by `Weak::new`
     #[inline]
     fn inner(&self) -> Option<&RcBox<T>> {
         if is_dangling(self.ptr) {
@@ -1260,6 +1304,52 @@ impl<T: ?Sized> Weak<T> {
             Some(unsafe { self.ptr.as_ref() })
         }
     }
+
+    /// Returns true if the two `Weak`s point to the same value (not just values
+    /// that compare as equal).
+    ///
+    /// # Notes
+    ///
+    /// Since this compares pointers it means that `Weak::new()` will equal each
+    /// other, even though they don't point to any value.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(weak_ptr_eq)]
+    /// use std::rc::{Rc, Weak};
+    ///
+    /// let first_rc = Rc::new(5);
+    /// let first = Rc::downgrade(&first_rc);
+    /// let second = Rc::downgrade(&first_rc);
+    ///
+    /// assert!(Weak::ptr_eq(&first, &second));
+    ///
+    /// let third_rc = Rc::new(5);
+    /// let third = Rc::downgrade(&third_rc);
+    ///
+    /// assert!(!Weak::ptr_eq(&first, &third));
+    /// ```
+    ///
+    /// Comparing `Weak::new`.
+    ///
+    /// ```
+    /// #![feature(weak_ptr_eq)]
+    /// use std::rc::{Rc, Weak};
+    ///
+    /// let first = Weak::new();
+    /// let second = Weak::new();
+    /// assert!(Weak::ptr_eq(&first, &second));
+    ///
+    /// let third_rc = Rc::new(());
+    /// let third = Rc::downgrade(&third_rc);
+    /// assert!(!Weak::ptr_eq(&first, &third));
+    /// ```
+    #[inline]
+    #[unstable(feature = "weak_ptr_eq", issue = "55981")]
+    pub fn ptr_eq(this: &Self, other: &Self) -> bool {
+        this.ptr.as_ptr() == other.ptr.as_ptr()
+    }
 }
 
 #[stable(feature = "rc_weak", since = "1.4.0")]
@@ -1334,9 +1424,10 @@ impl<T: ?Sized + fmt::Debug> fmt::Debug for Weak<T> {
 #[stable(feature = "downgraded_weak", since = "1.10.0")]
 impl<T> Default for Weak<T> {
     /// Constructs a new `Weak<T>`, allocating memory for `T` without initializing
-    /// it. Calling [`upgrade`][Weak::upgrade] on the return value always gives [`None`].
+    /// it. Calling [`upgrade`] on the return value always gives [`None`].
     ///
     /// [`None`]: ../../std/option/enum.Option.html
+    /// [`upgrade`]: ../../std/rc/struct.Weak.html#method.upgrade
     ///
     /// # Examples
     ///
diff --git a/src/liballoc/slice.rs b/src/liballoc/slice.rs
index 22da9dd6e96..510b4b06e40 100644
--- a/src/liballoc/slice.rs
+++ b/src/liballoc/slice.rs
@@ -177,7 +177,7 @@ mod hack {
 impl<T> [T] {
     /// Sorts the slice.
     ///
-    /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
+    /// 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.
@@ -211,7 +211,7 @@ impl<T> [T] {
 
     /// Sorts the slice with a comparator function.
     ///
-    /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
+    /// This sort is stable (i.e., does not reorder equal elements) and `O(n log n)` worst-case.
     ///
     /// The comparator function must define a total ordering for the elements in the slice. If
     /// the ordering is not total, the order of the elements is unspecified. An order is a
@@ -264,7 +264,7 @@ impl<T> [T] {
 
     /// Sorts the slice with a key extraction function.
     ///
-    /// This sort is stable (i.e. does not reorder equal elements) and `O(m n log(m n))`
+    /// This sort is stable (i.e., does not reorder equal elements) and `O(m n log(m n))`
     /// worst-case, where the key function is `O(m)`.
     ///
     /// When applicable, unstable sorting is preferred because it is generally faster than stable
@@ -301,10 +301,10 @@ impl<T> [T] {
     ///
     /// During sorting, the key function is called only once per element.
     ///
-    /// This sort is stable (i.e. does not reorder equal elements) and `O(m n + n log n)`
+    /// This sort is stable (i.e., does not reorder equal elements) and `O(m n + n log n)`
     /// worst-case, where the key function is `O(m)`.
     ///
-    /// For simple key functions (e.g. functions that are property accesses or
+    /// For simple key functions (e.g., functions that are property accesses or
     /// basic operations), [`sort_by_key`](#method.sort_by_key) is likely to be
     /// faster.
     ///
@@ -589,7 +589,7 @@ impl<T: Clone, V: Borrow<[T]>> SliceConcatExt<T> for [V] {
     type Output = Vec<T>;
 
     fn concat(&self) -> Vec<T> {
-        let size = self.iter().fold(0, |acc, v| acc + v.borrow().len());
+        let size = self.iter().map(|slice| slice.borrow().len()).sum();
         let mut result = Vec::with_capacity(size);
         for v in self {
             result.extend_from_slice(v.borrow())
@@ -603,8 +603,8 @@ impl<T: Clone, V: Borrow<[T]>> SliceConcatExt<T> for [V] {
             Some(first) => first,
             None => return vec![],
         };
-        let size = self.iter().fold(0, |acc, v| acc + v.borrow().len());
-        let mut result = Vec::with_capacity(size + self.len());
+        let size = self.iter().map(|slice| slice.borrow().len()).sum::<usize>() + self.len() - 1;
+        let mut result = Vec::with_capacity(size);
         result.extend_from_slice(first.borrow());
 
         for v in iter {
diff --git a/src/liballoc/string.rs b/src/liballoc/string.rs
index 662f8ae614f..4652c0e7efa 100644
--- a/src/liballoc/string.rs
+++ b/src/liballoc/string.rs
@@ -577,7 +577,7 @@ impl String {
             return Cow::Borrowed("");
         };
 
-        const REPLACEMENT: &'static str = "\u{FFFD}";
+        const REPLACEMENT: &str = "\u{FFFD}";
 
         let mut res = String::with_capacity(v.len());
         res.push_str(first_valid);
@@ -1732,18 +1732,37 @@ impl<'a> FromIterator<&'a str> for String {
 #[stable(feature = "extend_string", since = "1.4.0")]
 impl FromIterator<String> for String {
     fn from_iter<I: IntoIterator<Item = String>>(iter: I) -> String {
-        let mut buf = String::new();
-        buf.extend(iter);
-        buf
+        let mut iterator = iter.into_iter();
+
+        // Because we're iterating over `String`s, we can avoid at least
+        // one allocation by getting the first string from the iterator
+        // and appending to it all the subsequent strings.
+        match iterator.next() {
+            None => String::new(),
+            Some(mut buf) => {
+                buf.extend(iterator);
+                buf
+            }
+        }
     }
 }
 
 #[stable(feature = "herd_cows", since = "1.19.0")]
 impl<'a> FromIterator<Cow<'a, str>> for String {
     fn from_iter<I: IntoIterator<Item = Cow<'a, str>>>(iter: I) -> String {
-        let mut buf = String::new();
-        buf.extend(iter);
-        buf
+        let mut iterator = iter.into_iter();
+
+        // Because we're iterating over CoWs, we can (potentially) avoid at least
+        // one allocation by getting the first item and appending to it all the
+        // subsequent items.
+        match iterator.next() {
+            None => String::new(),
+            Some(cow) => {
+                let mut buf = cow.into_owned();
+                buf.extend(iterator);
+                buf
+            }
+        }
     }
 }
 
@@ -1753,9 +1772,7 @@ impl Extend<char> for String {
         let iterator = iter.into_iter();
         let (lower_bound, _) = iterator.size_hint();
         self.reserve(lower_bound);
-        for ch in iterator {
-            self.push(ch)
-        }
+        iterator.for_each(move |c| self.push(c));
     }
 }
 
@@ -1769,27 +1786,21 @@ impl<'a> Extend<&'a char> for String {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a> Extend<&'a str> for String {
     fn extend<I: IntoIterator<Item = &'a str>>(&mut self, iter: I) {
-        for s in iter {
-            self.push_str(s)
-        }
+        iter.into_iter().for_each(move |s| self.push_str(s));
     }
 }
 
 #[stable(feature = "extend_string", since = "1.4.0")]
 impl Extend<String> for String {
     fn extend<I: IntoIterator<Item = String>>(&mut self, iter: I) {
-        for s in iter {
-            self.push_str(&s)
-        }
+        iter.into_iter().for_each(move |s| self.push_str(&s));
     }
 }
 
 #[stable(feature = "herd_cows", since = "1.19.0")]
 impl<'a> Extend<Cow<'a, str>> for String {
     fn extend<I: IntoIterator<Item = Cow<'a, str>>>(&mut self, iter: I) {
-        for s in iter {
-            self.push_str(&s)
-        }
+        iter.into_iter().for_each(move |s| self.push_str(&s));
     }
 }
 
@@ -2158,7 +2169,7 @@ impl<T: fmt::Display + ?Sized> ToString for T {
         use core::fmt::Write;
         let mut buf = String::new();
         buf.write_fmt(format_args!("{}", self))
-           .expect("a Display implementation return an error unexpectedly");
+           .expect("a Display implementation returned an error unexpectedly");
         buf.shrink_to_fit();
         buf
     }
diff --git a/src/liballoc/sync.rs b/src/liballoc/sync.rs
index 4f4031e3c4e..948c36117a3 100644
--- a/src/liballoc/sync.rs
+++ b/src/liballoc/sync.rs
@@ -24,7 +24,7 @@ use core::fmt;
 use core::cmp::Ordering;
 use core::intrinsics::abort;
 use core::mem::{self, align_of_val, size_of_val};
-use core::ops::Deref;
+use core::ops::{Deref, Receiver};
 use core::ops::{CoerceUnsized, DispatchFromDyn};
 use core::pin::Pin;
 use core::ptr::{self, NonNull};
@@ -767,6 +767,9 @@ impl<T: ?Sized> Deref for Arc<T> {
     }
 }
 
+#[unstable(feature = "receiver_trait", issue = "0")]
+impl<T: ?Sized> Receiver for Arc<T> {}
+
 impl<T: Clone> Arc<T> {
     /// Makes a mutable reference into the given `Arc`.
     ///
@@ -952,6 +955,8 @@ unsafe impl<#[may_dangle] T: ?Sized> Drop for Arc<T> {
     /// drop(foo);    // Doesn't print anything
     /// drop(foo2);   // Prints "dropped!"
     /// ```
+    ///
+    /// [`Weak`]: ../../std/sync/struct.Weak.html
     #[inline]
     fn drop(&mut self) {
         // Because `fetch_sub` is already atomic, we do not need to synchronize
@@ -1121,7 +1126,7 @@ impl<T: ?Sized> Weak<T> {
     }
 
     /// Return `None` when the pointer is dangling and there is no allocated `ArcInner`,
-    /// i.e. this `Weak` was created by `Weak::new`
+    /// i.e., this `Weak` was created by `Weak::new`
     #[inline]
     fn inner(&self) -> Option<&ArcInner<T>> {
         if is_dangling(self.ptr) {
@@ -1130,6 +1135,53 @@ impl<T: ?Sized> Weak<T> {
             Some(unsafe { self.ptr.as_ref() })
         }
     }
+
+    /// Returns true if the two `Weak`s point to the same value (not just values
+    /// that compare as equal).
+    ///
+    /// # Notes
+    ///
+    /// Since this compares pointers it means that `Weak::new()` will equal each
+    /// other, even though they don't point to any value.
+    ///
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(weak_ptr_eq)]
+    /// use std::sync::{Arc, Weak};
+    ///
+    /// let first_rc = Arc::new(5);
+    /// let first = Arc::downgrade(&first_rc);
+    /// let second = Arc::downgrade(&first_rc);
+    ///
+    /// assert!(Weak::ptr_eq(&first, &second));
+    ///
+    /// let third_rc = Arc::new(5);
+    /// let third = Arc::downgrade(&third_rc);
+    ///
+    /// assert!(!Weak::ptr_eq(&first, &third));
+    /// ```
+    ///
+    /// Comparing `Weak::new`.
+    ///
+    /// ```
+    /// #![feature(weak_ptr_eq)]
+    /// use std::sync::{Arc, Weak};
+    ///
+    /// let first = Weak::new();
+    /// let second = Weak::new();
+    /// assert!(Weak::ptr_eq(&first, &second));
+    ///
+    /// let third_rc = Arc::new(());
+    /// let third = Arc::downgrade(&third_rc);
+    /// assert!(!Weak::ptr_eq(&first, &third));
+    /// ```
+    #[inline]
+    #[unstable(feature = "weak_ptr_eq", issue = "55981")]
+    pub fn ptr_eq(this: &Self, other: &Self) -> bool {
+        this.ptr.as_ptr() == other.ptr.as_ptr()
+    }
 }
 
 #[stable(feature = "arc_weak", since = "1.4.0")]
@@ -1172,10 +1224,11 @@ impl<T: ?Sized> Clone for Weak<T> {
 #[stable(feature = "downgraded_weak", since = "1.10.0")]
 impl<T> Default for Weak<T> {
     /// Constructs a new `Weak<T>`, without allocating memory.
-    /// Calling [`upgrade`][Weak::upgrade] on the return value always
+    /// Calling [`upgrade`] on the return value always
     /// gives [`None`].
     ///
     /// [`None`]: ../../std/option/enum.Option.html#variant.None
+    /// [`upgrade`]: ../../std/sync/struct.Weak.html#method.upgrade
     ///
     /// # Examples
     ///
@@ -1241,11 +1294,45 @@ impl<T: ?Sized> Drop for Weak<T> {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
+trait ArcEqIdent<T: ?Sized + PartialEq> {
+    fn eq(&self, other: &Arc<T>) -> bool;
+    fn ne(&self, other: &Arc<T>) -> bool;
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T: ?Sized + PartialEq> ArcEqIdent<T> for Arc<T> {
+    #[inline]
+    default fn eq(&self, other: &Arc<T>) -> bool {
+        **self == **other
+    }
+    #[inline]
+    default fn ne(&self, other: &Arc<T>) -> bool {
+        **self != **other
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T: ?Sized + Eq> ArcEqIdent<T> for Arc<T> {
+    #[inline]
+    fn eq(&self, other: &Arc<T>) -> bool {
+        Arc::ptr_eq(self, other) || **self == **other
+    }
+
+    #[inline]
+    fn ne(&self, other: &Arc<T>) -> bool {
+        !Arc::ptr_eq(self, other) && **self != **other
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
 impl<T: ?Sized + PartialEq> PartialEq for Arc<T> {
     /// Equality for two `Arc`s.
     ///
     /// Two `Arc`s are equal if their inner values are equal.
     ///
+    /// If `T` also implements `Eq`, two `Arc`s that point to the same value are
+    /// always equal.
+    ///
     /// # Examples
     ///
     /// ```
@@ -1255,14 +1342,18 @@ impl<T: ?Sized + PartialEq> PartialEq for Arc<T> {
     ///
     /// assert!(five == Arc::new(5));
     /// ```
+    #[inline]
     fn eq(&self, other: &Arc<T>) -> bool {
-        *(*self) == *(*other)
+        ArcEqIdent::eq(self, other)
     }
 
     /// Inequality for two `Arc`s.
     ///
     /// Two `Arc`s are unequal if their inner values are unequal.
     ///
+    /// If `T` also implements `Eq`, two `Arc`s that point to the same value are
+    /// never unequal.
+    ///
     /// # Examples
     ///
     /// ```
@@ -1272,10 +1363,12 @@ impl<T: ?Sized + PartialEq> PartialEq for Arc<T> {
     ///
     /// assert!(five != Arc::new(6));
     /// ```
+    #[inline]
     fn ne(&self, other: &Arc<T>) -> bool {
-        *(*self) != *(*other)
+        ArcEqIdent::ne(self, other)
     }
 }
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T: ?Sized + PartialOrd> PartialOrd for Arc<T> {
     /// Partial comparison for two `Arc`s.
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);
+        }
+    }
+}
diff --git a/src/liballoc/vec.rs b/src/liballoc/vec.rs
index ca7c766e413..b78e71331a9 100644
--- a/src/liballoc/vec.rs
+++ b/src/liballoc/vec.rs
@@ -213,7 +213,7 @@ use raw_vec::RawVec;
 /// about its design. This ensures that it's as low-overhead as possible in
 /// the general case, and can be correctly manipulated in primitive ways
 /// by unsafe code. Note that these guarantees refer to an unqualified `Vec<T>`.
-/// If additional type parameters are added (e.g. to support custom allocators),
+/// If additional type parameters are added (e.g., to support custom allocators),
 /// overriding their defaults may change the behavior.
 ///
 /// Most fundamentally, `Vec` is and always will be a (pointer, capacity, length)
@@ -1241,8 +1241,6 @@ impl<T> Vec<T> {
     /// # Examples
     ///
     /// ```
-    /// #![feature(vec_resize_with)]
-    ///
     /// let mut vec = vec![1, 2, 3];
     /// vec.resize_with(5, Default::default);
     /// assert_eq!(vec, [1, 2, 3, 0, 0]);
@@ -1255,7 +1253,7 @@ impl<T> Vec<T> {
     ///
     /// [`resize`]: #method.resize
     /// [`Clone`]: ../../std/clone/trait.Clone.html
-    #[unstable(feature = "vec_resize_with", issue = "41758")]
+    #[stable(feature = "vec_resize_with", since = "1.33.0")]
     pub fn resize_with<F>(&mut self, new_len: usize, f: F)
         where F: FnMut() -> T
     {