Merge branch 'master' into format-temporaries

23 files changed, 1412 insertions, 613 deletions

diff --git a/src/liballoc/borrow.rs b/src/liballoc/borrow.rs
index a9c5bce4c25..d2bdda83fa9 100644
--- a/src/liballoc/borrow.rs
+++ b/src/liballoc/borrow.rs
@@ -207,6 +207,47 @@ impl<B: ?Sized + ToOwned> Clone for Cow<'_, B> {
 }
 
 impl<B: ?Sized + ToOwned> Cow<'_, B> {
+    /// Returns true if the data is borrowed, i.e. if `to_mut` would require additional work.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(cow_is_borrowed)]
+    /// use std::borrow::Cow;
+    ///
+    /// let cow = Cow::Borrowed("moo");
+    /// assert!(cow.is_borrowed());
+    ///
+    /// let bull: Cow<'_, str> = Cow::Owned("...moo?".to_string());
+    /// assert!(!bull.is_borrowed());
+    /// ```
+    #[unstable(feature = "cow_is_borrowed", issue = "65143")]
+    pub fn is_borrowed(&self) -> bool {
+        match *self {
+            Borrowed(_) => true,
+            Owned(_) => false,
+        }
+    }
+
+    /// Returns true if the data is owned, i.e. if `to_mut` would be a no-op.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(cow_is_borrowed)]
+    /// use std::borrow::Cow;
+    ///
+    /// let cow: Cow<'_, str> = Cow::Owned("moo".to_string());
+    /// assert!(cow.is_owned());
+    ///
+    /// let bull = Cow::Borrowed("...moo?");
+    /// assert!(!bull.is_owned());
+    /// ```
+    #[unstable(feature = "cow_is_borrowed", issue = "65143")]
+    pub fn is_owned(&self) -> bool {
+        !self.is_borrowed()
+    }
+
     /// Acquires a mutable reference to the owned form of the data.
     ///
     /// Clones the data if it is not already owned.
diff --git a/src/liballoc/boxed.rs b/src/liballoc/boxed.rs
index c61e3183409..567b8ea7224 100644
--- a/src/liballoc/boxed.rs
+++ b/src/liballoc/boxed.rs
@@ -29,10 +29,8 @@
 //!     Nil,
 //! }
 //!
-//! fn main() {
-//!     let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil))));
-//!     println!("{:?}", list);
-//! }
+//! let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil))));
+//! println!("{:?}", list);
 //! ```
 //!
 //! This will print `Cons(1, Cons(2, Nil))`.
@@ -144,6 +142,9 @@ impl<T> Box<T> {
     #[unstable(feature = "new_uninit", issue = "63291")]
     pub fn new_uninit() -> Box<mem::MaybeUninit<T>> {
         let layout = alloc::Layout::new::<mem::MaybeUninit<T>>();
+        if layout.size() == 0 {
+            return Box(NonNull::dangling().into())
+        }
         let ptr = unsafe {
             Global.alloc(layout)
                 .unwrap_or_else(|_| alloc::handle_alloc_error(layout))
@@ -184,9 +185,16 @@ impl<T> Box<[T]> {
     #[unstable(feature = "new_uninit", issue = "63291")]
     pub fn new_uninit_slice(len: usize) -> Box<[mem::MaybeUninit<T>]> {
         let layout = alloc::Layout::array::<mem::MaybeUninit<T>>(len).unwrap();
-        let ptr = unsafe { alloc::alloc(layout) };
-        let unique = Unique::new(ptr).unwrap_or_else(|| alloc::handle_alloc_error(layout));
-        let slice = unsafe { slice::from_raw_parts_mut(unique.cast().as_ptr(), len) };
+        let ptr = if layout.size() == 0 {
+            NonNull::dangling()
+        } else {
+            unsafe {
+                Global.alloc(layout)
+                    .unwrap_or_else(|_| alloc::handle_alloc_error(layout))
+                    .cast()
+            }
+        };
+        let slice = unsafe { slice::from_raw_parts_mut(ptr.as_ptr(), len) };
         Box(Unique::from(slice))
     }
 }
@@ -375,14 +383,12 @@ impl<T: ?Sized> Box<T> {
     /// ```
     /// #![feature(box_into_raw_non_null)]
     ///
-    /// fn main() {
-    ///     let x = Box::new(5);
-    ///     let ptr = Box::into_raw_non_null(x);
+    /// let x = Box::new(5);
+    /// let ptr = Box::into_raw_non_null(x);
     ///
-    ///     // Clean up the memory by converting the NonNull pointer back
-    ///     // into a Box and letting the Box be dropped.
-    ///     let x = unsafe { Box::from_raw(ptr.as_ptr()) };
-    /// }
+    /// // Clean up the memory by converting the NonNull pointer back
+    /// // into a Box and letting the Box be dropped.
+    /// let x = unsafe { Box::from_raw(ptr.as_ptr()) };
     /// ```
     #[unstable(feature = "box_into_raw_non_null", issue = "47336")]
     #[inline]
@@ -428,23 +434,19 @@ impl<T: ?Sized> Box<T> {
     /// Simple usage:
     ///
     /// ```
-    /// fn main() {
-    ///     let x = Box::new(41);
-    ///     let static_ref: &'static mut usize = Box::leak(x);
-    ///     *static_ref += 1;
-    ///     assert_eq!(*static_ref, 42);
-    /// }
+    /// let x = Box::new(41);
+    /// let static_ref: &'static mut usize = Box::leak(x);
+    /// *static_ref += 1;
+    /// assert_eq!(*static_ref, 42);
     /// ```
     ///
     /// Unsized data:
     ///
     /// ```
-    /// fn main() {
-    ///     let x = vec![1, 2, 3].into_boxed_slice();
-    ///     let static_ref = Box::leak(x);
-    ///     static_ref[0] = 4;
-    ///     assert_eq!(*static_ref, [4, 2, 3]);
-    /// }
+    /// let x = vec![1, 2, 3].into_boxed_slice();
+    /// let static_ref = Box::leak(x);
+    /// static_ref[0] = 4;
+    /// assert_eq!(*static_ref, [4, 2, 3]);
     /// ```
     #[stable(feature = "box_leak", since = "1.26.0")]
     #[inline]
@@ -780,11 +782,9 @@ impl Box<dyn Any> {
     ///     }
     /// }
     ///
-    /// fn main() {
-    ///     let my_string = "Hello World".to_string();
-    ///     print_if_string(Box::new(my_string));
-    ///     print_if_string(Box::new(0i8));
-    /// }
+    /// let my_string = "Hello World".to_string();
+    /// print_if_string(Box::new(my_string));
+    /// print_if_string(Box::new(0i8));
     /// ```
     pub fn downcast<T: Any>(self) -> Result<Box<T>, Box<dyn Any>> {
         if self.is::<T>() {
@@ -814,11 +814,9 @@ impl Box<dyn Any + Send> {
     ///     }
     /// }
     ///
-    /// fn main() {
-    ///     let my_string = "Hello World".to_string();
-    ///     print_if_string(Box::new(my_string));
-    ///     print_if_string(Box::new(0i8));
-    /// }
+    /// let my_string = "Hello World".to_string();
+    /// print_if_string(Box::new(my_string));
+    /// print_if_string(Box::new(0i8));
     /// ```
     pub fn downcast<T: Any>(self) -> Result<Box<T>, Box<dyn Any + Send>> {
         <Box<dyn Any>>::downcast(self).map_err(|s| unsafe {
@@ -883,11 +881,33 @@ impl<I: Iterator + ?Sized> Iterator for Box<I> {
     fn nth(&mut self, n: usize) -> Option<I::Item> {
         (**self).nth(n)
     }
+    fn last(self) -> Option<I::Item> {
+        BoxIter::last(self)
+    }
+}
+
+trait BoxIter {
+    type Item;
+    fn last(self) -> Option<Self::Item>;
+}
+
+impl<I: Iterator + ?Sized> BoxIter for Box<I> {
+    type Item = I::Item;
+    default fn last(self) -> Option<I::Item> {
+        #[inline]
+        fn some<T>(_: Option<T>, x: T) -> Option<T> {
+            Some(x)
+        }
+
+        self.fold(None, some)
+    }
 }
 
+/// Specialization for sized `I`s that uses `I`s implementation of `last()`
+/// instead of the default.
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<I: Iterator + Sized> Iterator for Box<I> {
-    fn last(self) -> Option<I::Item> where I: Sized {
+impl<I: Iterator> BoxIter for Box<I> {
+    fn last(self) -> Option<I::Item> {
         (*self).last()
     }
 }
diff --git a/src/liballoc/collections/binary_heap.rs b/src/liballoc/collections/binary_heap.rs
index 3d04f30e7bd..fda6f090fd7 100644
--- a/src/liballoc/collections/binary_heap.rs
+++ b/src/liballoc/collections/binary_heap.rs
@@ -146,7 +146,7 @@
 #![stable(feature = "rust1", since = "1.0.0")]
 
 use core::ops::{Deref, DerefMut};
-use core::iter::{FromIterator, FusedIterator};
+use core::iter::{FromIterator, FusedIterator, TrustedLen};
 use core::mem::{swap, size_of, ManuallyDrop};
 use core::ptr;
 use core::fmt;
@@ -648,6 +648,36 @@ impl<T: Ord> BinaryHeap<T> {
             self.extend(other.drain());
         }
     }
+
+    /// Returns an iterator which retrieves elements in heap order.
+    /// The retrieved elements are removed from the original heap.
+    /// The remaining elements will be removed on drop in heap order.
+    ///
+    /// Note:
+    /// * `.drain_sorted()` is O(n lg n); much slower than `.drain()`.
+    ///   You should use the latter for most cases.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// #![feature(binary_heap_drain_sorted)]
+    /// use std::collections::BinaryHeap;
+    ///
+    /// let mut heap = BinaryHeap::from(vec![1, 2, 3, 4, 5]);
+    /// assert_eq!(heap.len(), 5);
+    ///
+    /// drop(heap.drain_sorted()); // removes all elements in heap order
+    /// assert_eq!(heap.len(), 0);
+    /// ```
+    #[inline]
+    #[unstable(feature = "binary_heap_drain_sorted", issue = "59278")]
+    pub fn drain_sorted(&mut self) -> DrainSorted<'_, T> {
+        DrainSorted {
+            inner: self,
+        }
+    }
 }
 
 impl<T> BinaryHeap<T> {
@@ -672,6 +702,27 @@ impl<T> BinaryHeap<T> {
         Iter { iter: self.data.iter() }
     }
 
+    /// Returns an iterator which retrieves elements in heap order.
+    /// This method consumes the original heap.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// #![feature(binary_heap_into_iter_sorted)]
+    /// use std::collections::BinaryHeap;
+    /// let heap = BinaryHeap::from(vec![1, 2, 3, 4, 5]);
+    ///
+    /// assert_eq!(heap.into_iter_sorted().take(2).collect::<Vec<_>>(), vec![5, 4]);
+    /// ```
+    #[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")]
+    pub fn into_iter_sorted(self) -> IntoIterSorted<T> {
+        IntoIterSorted {
+            inner: self,
+        }
+    }
+
     /// Returns the greatest item in the binary heap, or `None` if it is empty.
     ///
     /// # Examples
@@ -1115,6 +1166,37 @@ impl<T> ExactSizeIterator for IntoIter<T> {
 #[stable(feature = "fused", since = "1.26.0")]
 impl<T> FusedIterator for IntoIter<T> {}
 
+#[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")]
+#[derive(Clone, Debug)]
+pub struct IntoIterSorted<T> {
+    inner: BinaryHeap<T>,
+}
+
+#[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")]
+impl<T: Ord> Iterator for IntoIterSorted<T> {
+    type Item = T;
+
+    #[inline]
+    fn next(&mut self) -> Option<T> {
+        self.inner.pop()
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let exact = self.inner.len();
+        (exact, Some(exact))
+    }
+}
+
+#[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")]
+impl<T: Ord> ExactSizeIterator for IntoIterSorted<T> {}
+
+#[unstable(feature = "binary_heap_into_iter_sorted", issue = "59278")]
+impl<T: Ord> FusedIterator for IntoIterSorted<T> {}
+
+#[unstable(feature = "trusted_len", issue = "37572")]
+unsafe impl<T: Ord> TrustedLen for IntoIterSorted<T> {}
+
 /// A draining iterator over the elements of a `BinaryHeap`.
 ///
 /// This `struct` is created by the [`drain`] method on [`BinaryHeap`]. See its
@@ -1161,6 +1243,52 @@ impl<T> ExactSizeIterator for Drain<'_, T> {
 #[stable(feature = "fused", since = "1.26.0")]
 impl<T> FusedIterator for Drain<'_, T> {}
 
+/// A draining iterator over the elements of a `BinaryHeap`.
+///
+/// This `struct` is created by the [`drain_sorted`] method on [`BinaryHeap`]. See its
+/// documentation for more.
+///
+/// [`drain_sorted`]: struct.BinaryHeap.html#method.drain_sorted
+/// [`BinaryHeap`]: struct.BinaryHeap.html
+#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")]
+#[derive(Debug)]
+pub struct DrainSorted<'a, T: Ord> {
+    inner: &'a mut BinaryHeap<T>,
+}
+
+#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")]
+impl<'a, T: Ord> Drop for DrainSorted<'a, T> {
+    /// Removes heap elements in heap order.
+    fn drop(&mut self) {
+        while let Some(_) = self.inner.pop() {}
+    }
+}
+
+#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")]
+impl<T: Ord> Iterator for DrainSorted<'_, T> {
+    type Item = T;
+
+    #[inline]
+    fn next(&mut self) -> Option<T> {
+        self.inner.pop()
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let exact = self.inner.len();
+        (exact, Some(exact))
+    }
+}
+
+#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")]
+impl<T: Ord> ExactSizeIterator for DrainSorted<'_, T> { }
+
+#[unstable(feature = "binary_heap_drain_sorted", issue = "59278")]
+impl<T: Ord> FusedIterator for DrainSorted<'_, T> {}
+
+#[unstable(feature = "trusted_len", issue = "37572")]
+unsafe impl<T: Ord> TrustedLen for DrainSorted<'_, T> {}
+
 #[stable(feature = "binary_heap_extras_15", since = "1.5.0")]
 impl<T: Ord> From<Vec<T>> for BinaryHeap<T> {
     /// Converts a `Vec<T>` into a `BinaryHeap<T>`.
diff --git a/src/liballoc/collections/btree/map.rs b/src/liballoc/collections/btree/map.rs
index ddf012d1502..83fd4485f73 100644
--- a/src/liballoc/collections/btree/map.rs
+++ b/src/liballoc/collections/btree/map.rs
@@ -2226,14 +2226,12 @@ impl<'a, K: Ord, V: Default> Entry<'a, K, V> {
     /// # Examples
     ///
     /// ```
-    /// # fn main() {
     /// use std::collections::BTreeMap;
     ///
     /// let mut map: BTreeMap<&str, Option<usize>> = BTreeMap::new();
     /// map.entry("poneyland").or_default();
     ///
     /// assert_eq!(map["poneyland"], None);
-    /// # }
     /// ```
     pub fn or_default(self) -> &'a mut V {
         match self {
diff --git a/src/liballoc/collections/btree/set.rs b/src/liballoc/collections/btree/set.rs
index 0cb91ba4c81..f0796354e00 100644
--- a/src/liballoc/collections/btree/set.rs
+++ b/src/liballoc/collections/btree/set.rs
@@ -2,7 +2,7 @@
 // to TreeMap
 
 use core::borrow::Borrow;
-use core::cmp::Ordering::{self, Less, Greater, Equal};
+use core::cmp::Ordering::{Less, Greater, Equal};
 use core::cmp::{max, min};
 use core::fmt::{self, Debug};
 use core::iter::{Peekable, FromIterator, FusedIterator};
@@ -109,6 +109,77 @@ pub struct Range<'a, T: 'a> {
     iter: btree_map::Range<'a, T, ()>,
 }
 
+/// Core of SymmetricDifference and Union.
+/// More efficient than btree.map.MergeIter,
+/// and crucially for SymmetricDifference, nexts() reports on both sides.
+#[derive(Clone)]
+struct MergeIterInner<I>
+    where I: Iterator,
+          I::Item: Copy,
+{
+    a: I,
+    b: I,
+    peeked: Option<MergeIterPeeked<I>>,
+}
+
+#[derive(Copy, Clone, Debug)]
+enum MergeIterPeeked<I: Iterator> {
+    A(I::Item),
+    B(I::Item),
+}
+
+impl<I> MergeIterInner<I>
+    where I: ExactSizeIterator + FusedIterator,
+          I::Item: Copy + Ord,
+{
+    fn new(a: I, b: I) -> Self {
+        MergeIterInner { a, b, peeked: None }
+    }
+
+    fn nexts(&mut self) -> (Option<I::Item>, Option<I::Item>) {
+        let mut a_next = match self.peeked {
+            Some(MergeIterPeeked::A(next)) => Some(next),
+            _ => self.a.next(),
+        };
+        let mut b_next = match self.peeked {
+            Some(MergeIterPeeked::B(next)) => Some(next),
+            _ => self.b.next(),
+        };
+        let ord = match (a_next, b_next) {
+            (None, None) => Equal,
+            (_, None) => Less,
+            (None, _) => Greater,
+            (Some(a1), Some(b1)) => a1.cmp(&b1),
+        };
+        self.peeked = match ord {
+            Less => b_next.take().map(MergeIterPeeked::B),
+            Equal => None,
+            Greater => a_next.take().map(MergeIterPeeked::A),
+        };
+        (a_next, b_next)
+    }
+
+    fn lens(&self) -> (usize, usize) {
+        match self.peeked {
+            Some(MergeIterPeeked::A(_)) => (1 + self.a.len(), self.b.len()),
+            Some(MergeIterPeeked::B(_)) => (self.a.len(), 1 + self.b.len()),
+            _ => (self.a.len(), self.b.len()),
+        }
+    }
+}
+
+impl<I> Debug for MergeIterInner<I>
+    where I: Iterator + Debug,
+          I::Item: Copy + Debug,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_tuple("MergeIterInner")
+            .field(&self.a)
+            .field(&self.b)
+            .finish()
+    }
+}
+
 /// A lazy iterator producing elements in the difference of `BTreeSet`s.
 ///
 /// This `struct` is created by the [`difference`] method on [`BTreeSet`].
@@ -120,34 +191,25 @@ pub struct Range<'a, T: 'a> {
 pub struct Difference<'a, T: 'a> {
     inner: DifferenceInner<'a, T>,
 }
+#[derive(Debug)]
 enum DifferenceInner<'a, T: 'a> {
     Stitch {
+        // iterate all of self and some of other, spotting matches along the way
         self_iter: Iter<'a, T>,
         other_iter: Peekable<Iter<'a, T>>,
     },
     Search {
+        // iterate a small set, look up in the large set
         self_iter: Iter<'a, T>,
         other_set: &'a BTreeSet<T>,
     },
+    Iterate(Iter<'a, T>), // simply stream self's elements
 }
 
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<T: fmt::Debug> fmt::Debug for Difference<'_, T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        match &self.inner {
-            DifferenceInner::Stitch {
-                self_iter,
-                other_iter,
-            } => f
-                .debug_tuple("Difference")
-                .field(&self_iter)
-                .field(&other_iter)
-                .finish(),
-            DifferenceInner::Search {
-                self_iter,
-                other_set: _,
-            } => f.debug_tuple("Difference").field(&self_iter).finish(),
-        }
+        f.debug_tuple("Difference").field(&self.inner).finish()
     }
 }
 
@@ -159,18 +221,12 @@ impl<T: fmt::Debug> fmt::Debug for Difference<'_, T> {
 /// [`BTreeSet`]: struct.BTreeSet.html
 /// [`symmetric_difference`]: struct.BTreeSet.html#method.symmetric_difference
 #[stable(feature = "rust1", since = "1.0.0")]
-pub struct SymmetricDifference<'a, T: 'a> {
-    a: Peekable<Iter<'a, T>>,
-    b: Peekable<Iter<'a, T>>,
-}
+pub struct SymmetricDifference<'a, T: 'a>(MergeIterInner<Iter<'a, T>>);
 
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<T: fmt::Debug> fmt::Debug for SymmetricDifference<'_, T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_tuple("SymmetricDifference")
-         .field(&self.a)
-         .field(&self.b)
-         .finish()
+        f.debug_tuple("SymmetricDifference").field(&self.0).finish()
     }
 }
 
@@ -185,34 +241,25 @@ impl<T: fmt::Debug> fmt::Debug for SymmetricDifference<'_, T> {
 pub struct Intersection<'a, T: 'a> {
     inner: IntersectionInner<'a, T>,
 }
+#[derive(Debug)]
 enum IntersectionInner<'a, T: 'a> {
     Stitch {
+        // iterate similarly sized sets jointly, spotting matches along the way
         a: Iter<'a, T>,
         b: Iter<'a, T>,
     },
     Search {
+        // iterate a small set, look up in the large set
         small_iter: Iter<'a, T>,
         large_set: &'a BTreeSet<T>,
     },
+    Answer(Option<&'a T>), // return a specific value or emptiness
 }
 
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<T: fmt::Debug> fmt::Debug for Intersection<'_, T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        match &self.inner {
-            IntersectionInner::Stitch {
-                a,
-                b,
-            } => f
-                .debug_tuple("Intersection")
-                .field(&a)
-                .field(&b)
-                .finish(),
-            IntersectionInner::Search {
-                small_iter,
-                large_set: _,
-            } => f.debug_tuple("Intersection").field(&small_iter).finish(),
-        }
+        f.debug_tuple("Intersection").field(&self.inner).finish()
     }
 }
 
@@ -224,18 +271,12 @@ impl<T: fmt::Debug> fmt::Debug for Intersection<'_, T> {
 /// [`BTreeSet`]: struct.BTreeSet.html
 /// [`union`]: struct.BTreeSet.html#method.union
 #[stable(feature = "rust1", since = "1.0.0")]
-pub struct Union<'a, T: 'a> {
-    a: Peekable<Iter<'a, T>>,
-    b: Peekable<Iter<'a, T>>,
-}
+pub struct Union<'a, T: 'a>(MergeIterInner<Iter<'a, T>>);
 
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<T: fmt::Debug> fmt::Debug for Union<'_, T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_tuple("Union")
-         .field(&self.a)
-         .field(&self.b)
-         .finish()
+        f.debug_tuple("Union").field(&self.0).finish()
     }
 }
 
@@ -314,24 +355,48 @@ impl<T: Ord> BTreeSet<T> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn difference<'a>(&'a self, other: &'a BTreeSet<T>) -> Difference<'a, T> {
-        if self.len() > other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF {
-            // Self is bigger than or not much smaller than other set.
-            // Iterate both sets jointly, spotting matches along the way.
-            Difference {
-                inner: DifferenceInner::Stitch {
-                    self_iter: self.iter(),
-                    other_iter: other.iter().peekable(),
-                },
-            }
+        let (self_min, self_max) = if let (Some(self_min), Some(self_max)) =
+            (self.iter().next(), self.iter().next_back())
+        {
+            (self_min, self_max)
+        } else {
+            return Difference {
+                inner: DifferenceInner::Iterate(self.iter()),
+            };
+        };
+        let (other_min, other_max) = if let (Some(other_min), Some(other_max)) =
+            (other.iter().next(), other.iter().next_back())
+        {
+            (other_min, other_max)
         } else {
-            // Self is much smaller than other set, or both sets are empty.
-            // Iterate the small set, searching for matches in the large set.
-            Difference {
-                inner: DifferenceInner::Search {
+            return Difference {
+                inner: DifferenceInner::Iterate(self.iter()),
+            };
+        };
+        Difference {
+            inner: match (self_min.cmp(other_max), self_max.cmp(other_min)) {
+                (Greater, _) | (_, Less) => DifferenceInner::Iterate(self.iter()),
+                (Equal, _) => {
+                    let mut self_iter = self.iter();
+                    self_iter.next();
+                    DifferenceInner::Iterate(self_iter)
+                }
+                (_, Equal) => {
+                    let mut self_iter = self.iter();
+                    self_iter.next_back();
+                    DifferenceInner::Iterate(self_iter)
+                }
+                _ if self.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
+                    DifferenceInner::Search {
+                        self_iter: self.iter(),
+                        other_set: other,
+                    }
+                }
+                _ => DifferenceInner::Stitch {
                     self_iter: self.iter(),
-                    other_set: other,
+                    other_iter: other.iter().peekable(),
                 },
-            }
+            },
         }
     }
 
@@ -359,10 +424,7 @@ impl<T: Ord> BTreeSet<T> {
     pub fn symmetric_difference<'a>(&'a self,
                                     other: &'a BTreeSet<T>)
                                     -> SymmetricDifference<'a, T> {
-        SymmetricDifference {
-            a: self.iter().peekable(),
-            b: other.iter().peekable(),
-        }
+        SymmetricDifference(MergeIterInner::new(self.iter(), other.iter()))
     }
 
     /// Visits the values representing the intersection,
@@ -387,29 +449,46 @@ impl<T: Ord> BTreeSet<T> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn intersection<'a>(&'a self, other: &'a BTreeSet<T>) -> Intersection<'a, T> {
-        let (small, other) = if self.len() <= other.len() {
-            (self, other)
+        let (self_min, self_max) = if let (Some(self_min), Some(self_max)) =
+            (self.iter().next(), self.iter().next_back())
+        {
+            (self_min, self_max)
         } else {
-            (other, self)
+            return Intersection {
+                inner: IntersectionInner::Answer(None),
+            };
         };
-        if small.len() > other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF {
-            // Small set is not much smaller than other set.
-            // Iterate both sets jointly, spotting matches along the way.
-            Intersection {
-                inner: IntersectionInner::Stitch {
-                    a: small.iter(),
-                    b: other.iter(),
-                },
-            }
+        let (other_min, other_max) = if let (Some(other_min), Some(other_max)) =
+            (other.iter().next(), other.iter().next_back())
+        {
+            (other_min, other_max)
         } else {
-            // Big difference in number of elements, or both sets are empty.
-            // Iterate the small set, searching for matches in the large set.
-            Intersection {
-                inner: IntersectionInner::Search {
-                    small_iter: small.iter(),
-                    large_set: other,
+            return Intersection {
+                inner: IntersectionInner::Answer(None),
+            };
+        };
+        Intersection {
+            inner: match (self_min.cmp(other_max), self_max.cmp(other_min)) {
+                (Greater, _) | (_, Less) => IntersectionInner::Answer(None),
+                (Equal, _) => IntersectionInner::Answer(Some(self_min)),
+                (_, Equal) => IntersectionInner::Answer(Some(self_max)),
+                _ if self.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
+                    IntersectionInner::Search {
+                        small_iter: self.iter(),
+                        large_set: other,
+                    }
+                }
+                _ if other.len() <= self.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
+                    IntersectionInner::Search {
+                        small_iter: other.iter(),
+                        large_set: self,
+                    }
+                }
+                _ => IntersectionInner::Stitch {
+                    a: self.iter(),
+                    b: other.iter(),
                 },
-            }
+            },
         }
     }
 
@@ -433,10 +512,7 @@ impl<T: Ord> BTreeSet<T> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn union<'a>(&'a self, other: &'a BTreeSet<T>) -> Union<'a, T> {
-        Union {
-            a: self.iter().peekable(),
-            b: other.iter().peekable(),
-        }
+        Union(MergeIterInner::new(self.iter(), other.iter()))
     }
 
     /// Clears the set, removing all values.
@@ -544,43 +620,61 @@ impl<T: Ord> BTreeSet<T> {
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn is_subset(&self, other: &BTreeSet<T>) -> bool {
         // Same result as self.difference(other).next().is_none()
-        // but the 3 paths below are faster (in order: hugely, 20%, 5%).
+        // but the code below is faster (hugely in some cases).
         if self.len() > other.len() {
-            false
-        } else if self.len() > other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF {
-            // Self is not much smaller than other set.
-            // Stolen from TreeMap
-            let mut x = self.iter();
-            let mut y = other.iter();
-            let mut a = x.next();
-            let mut b = y.next();
-            while a.is_some() {
-                if b.is_none() {
+            return false;
+        }
+        let (self_min, self_max) = if let (Some(self_min), Some(self_max)) =
+            (self.iter().next(), self.iter().next_back())
+        {
+            (self_min, self_max)
+        } else {
+            return true; // self is empty
+        };
+        let (other_min, other_max) = if let (Some(other_min), Some(other_max)) =
+            (other.iter().next(), other.iter().next_back())
+        {
+            (other_min, other_max)
+        } else {
+            return false; // other is empty
+        };
+        let mut self_iter = self.iter();
+        match self_min.cmp(other_min) {
+            Less => return false,
+            Equal => {
+                self_iter.next();
+            }
+            Greater => (),
+        }
+        match self_max.cmp(other_max) {
+            Greater => return false,
+            Equal => {
+                self_iter.next_back();
+            }
+            Less => (),
+        }
+        if self_iter.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF {
+            // Big difference in number of elements.
+            for next in self_iter {
+                if !other.contains(next) {
                     return false;
                 }
-
-                let a1 = a.unwrap();
-                let b1 = b.unwrap();
-
-                match b1.cmp(a1) {
-                    Less => (),
-                    Greater => return false,
-                    Equal => a = x.next(),
-                }
-
-                b = y.next();
             }
-            true
         } else {
-            // Big difference in number of elements, or both sets are empty.
-            // Iterate the small set, searching for matches in the large set.
-            for next in self {
-                if !other.contains(next) {
-                    return false;
+            // Self is not much smaller than other set.
+            let mut other_iter = other.iter();
+            other_iter.next();
+            other_iter.next_back();
+            let mut self_next = self_iter.next();
+            while let Some(self1) = self_next {
+                match other_iter.next().map_or(Less, |other1| self1.cmp(other1)) {
+                    Less => return false,
+                    Equal => self_next = self_iter.next(),
+                    Greater => (),
                 }
             }
-            true
         }
+        true
     }
 
     /// Returns `true` if the set is a superset of another,
@@ -1092,15 +1186,6 @@ impl<'a, T> DoubleEndedIterator for Range<'a, T> {
 #[stable(feature = "fused", since = "1.26.0")]
 impl<T> FusedIterator for Range<'_, T> {}
 
-/// Compares `x` and `y`, but return `short` if x is None and `long` if y is None
-fn cmp_opt<T: Ord>(x: Option<&T>, y: Option<&T>, short: Ordering, long: Ordering) -> Ordering {
-    match (x, y) {
-        (None, _) => short,
-        (_, None) => long,
-        (Some(x1), Some(y1)) => x1.cmp(y1),
-    }
-}
-
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> Clone for Difference<'_, T> {
     fn clone(&self) -> Self {
@@ -1120,6 +1205,7 @@ impl<T> Clone for Difference<'_, T> {
                     self_iter: self_iter.clone(),
                     other_set,
                 },
+                DifferenceInner::Iterate(iter) => DifferenceInner::Iterate(iter.clone()),
             },
         }
     }
@@ -1138,7 +1224,7 @@ impl<'a, T: Ord> Iterator for Difference<'a, T> {
                 loop {
                     match other_iter
                         .peek()
-                        .map_or(Less, |other_next| Ord::cmp(self_next, other_next))
+                        .map_or(Less, |other_next| self_next.cmp(other_next))
                     {
                         Less => return Some(self_next),
                         Equal => {
@@ -1160,6 +1246,7 @@ impl<'a, T: Ord> Iterator for Difference<'a, T> {
                     return Some(self_next);
                 }
             },
+            DifferenceInner::Iterate(iter) => iter.next(),
         }
     }
 
@@ -1167,12 +1254,13 @@ impl<'a, T: Ord> Iterator for Difference<'a, T> {
         let (self_len, other_len) = match &self.inner {
             DifferenceInner::Stitch {
                 self_iter,
-                other_iter
+                other_iter,
             } => (self_iter.len(), other_iter.len()),
             DifferenceInner::Search {
                 self_iter,
-                other_set
+                other_set,
             } => (self_iter.len(), other_set.len()),
+            DifferenceInner::Iterate(iter) => (iter.len(), 0),
         };
         (self_len.saturating_sub(other_len), Some(self_len))
     }
@@ -1184,10 +1272,7 @@ impl<T: Ord> FusedIterator for Difference<'_, T> {}
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> Clone for SymmetricDifference<'_, T> {
     fn clone(&self) -> Self {
-        SymmetricDifference {
-            a: self.a.clone(),
-            b: self.b.clone(),
-        }
+        SymmetricDifference(self.0.clone())
     }
 }
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -1196,19 +1281,19 @@ impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> {
 
     fn next(&mut self) -> Option<&'a T> {
         loop {
-            match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
-                Less => return self.a.next(),
-                Equal => {
-                    self.a.next();
-                    self.b.next();
-                }
-                Greater => return self.b.next(),
+            let (a_next, b_next) = self.0.nexts();
+            if a_next.and(b_next).is_none() {
+                return a_next.or(b_next);
             }
         }
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
-        (0, Some(self.a.len() + self.b.len()))
+        let (a_len, b_len) = self.0.lens();
+        // No checked_add, because even if a and b refer to the same set,
+        // and T is an empty type, the storage overhead of sets limits
+        // the number of elements to less than half the range of usize.
+        (0, Some(a_len + b_len))
     }
 }
 
@@ -1234,6 +1319,7 @@ impl<T> Clone for Intersection<'_, T> {
                     small_iter: small_iter.clone(),
                     large_set,
                 },
+                IntersectionInner::Answer(answer) => IntersectionInner::Answer(*answer),
             },
         }
     }
@@ -1251,7 +1337,7 @@ impl<'a, T: Ord> Iterator for Intersection<'a, T> {
                 let mut a_next = a.next()?;
                 let mut b_next = b.next()?;
                 loop {
-                    match Ord::cmp(a_next, b_next) {
+                    match a_next.cmp(b_next) {
                         Less => a_next = a.next()?,
                         Greater => b_next = b.next()?,
                         Equal => return Some(a_next),
@@ -1267,15 +1353,17 @@ impl<'a, T: Ord> Iterator for Intersection<'a, T> {
                     return Some(small_next);
                 }
             },
+            IntersectionInner::Answer(answer) => answer.take(),
         }
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
-        let min_len = match &self.inner {
-            IntersectionInner::Stitch { a, b } => min(a.len(), b.len()),
-            IntersectionInner::Search { small_iter, .. } => small_iter.len(),
-        };
-        (0, Some(min_len))
+        match &self.inner {
+            IntersectionInner::Stitch { a, b } => (0, Some(min(a.len(), b.len()))),
+            IntersectionInner::Search { small_iter, .. } => (0, Some(small_iter.len())),
+            IntersectionInner::Answer(None) => (0, Some(0)),
+            IntersectionInner::Answer(Some(_)) => (1, Some(1)),
+        }
     }
 }
 
@@ -1285,10 +1373,7 @@ impl<T: Ord> FusedIterator for Intersection<'_, T> {}
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> Clone for Union<'_, T> {
     fn clone(&self) -> Self {
-        Union {
-            a: self.a.clone(),
-            b: self.b.clone(),
-        }
+        Union(self.0.clone())
     }
 }
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -1296,19 +1381,13 @@ impl<'a, T: Ord> Iterator for Union<'a, T> {
     type Item = &'a T;
 
     fn next(&mut self) -> Option<&'a T> {
-        match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
-            Less => self.a.next(),
-            Equal => {
-                self.b.next();
-                self.a.next()
-            }
-            Greater => self.b.next(),
-        }
+        let (a_next, b_next) = self.0.nexts();
+        a_next.or(b_next)
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
-        let a_len = self.a.len();
-        let b_len = self.b.len();
+        let (a_len, b_len) = self.0.lens();
+        // No checked_add - see SymmetricDifference::size_hint.
         (max(a_len, b_len), Some(a_len + b_len))
     }
 }
diff --git a/src/liballoc/collections/linked_list.rs b/src/liballoc/collections/linked_list.rs
index 816a71f2557..702df250999 100644
--- a/src/liballoc/collections/linked_list.rs
+++ b/src/liballoc/collections/linked_list.rs
@@ -1197,6 +1197,19 @@ impl<T: Clone> Clone for LinkedList<T> {
     fn clone(&self) -> Self {
         self.iter().cloned().collect()
     }
+
+    fn clone_from(&mut self, other: &Self) {
+        let mut iter_other = other.iter();
+        if self.len() > other.len() {
+            self.split_off(other.len());
+        }
+        for (elem, elem_other) in self.iter_mut().zip(&mut iter_other) {
+            elem.clone_from(elem_other);
+        }
+        if !iter_other.is_empty() {
+            self.extend(iter_other.cloned());
+        }
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
diff --git a/src/liballoc/collections/linked_list/tests.rs b/src/liballoc/collections/linked_list/tests.rs
index ecb5948f11b..1001f6bba3b 100644
--- a/src/liballoc/collections/linked_list/tests.rs
+++ b/src/liballoc/collections/linked_list/tests.rs
@@ -111,6 +111,49 @@ fn test_append() {
 }
 
 #[test]
+fn test_clone_from() {
+    // Short cloned from long
+    {
+        let v = vec![1, 2, 3, 4, 5];
+        let u = vec![8, 7, 6, 2, 3, 4, 5];
+        let mut m = list_from(&v);
+        let n = list_from(&u);
+        m.clone_from(&n);
+        check_links(&m);
+        assert_eq!(m, n);
+        for elt in u {
+            assert_eq!(m.pop_front(), Some(elt))
+        }
+    }
+    // Long cloned from short
+    {
+        let v = vec![1, 2, 3, 4, 5];
+        let u = vec![6, 7, 8];
+        let mut m = list_from(&v);
+        let n = list_from(&u);
+        m.clone_from(&n);
+        check_links(&m);
+        assert_eq!(m, n);
+        for elt in u {
+            assert_eq!(m.pop_front(), Some(elt))
+        }
+    }
+    // Two equal length lists
+    {
+        let v = vec![1, 2, 3, 4, 5];
+        let u = vec![9, 8, 1, 2, 3];
+        let mut m = list_from(&v);
+        let n = list_from(&u);
+        m.clone_from(&n);
+        check_links(&m);
+        assert_eq!(m, n);
+        for elt in u {
+            assert_eq!(m.pop_front(), Some(elt))
+        }
+    }
+}
+
+#[test]
 fn test_insert_prev() {
     let mut m = list_from(&[0, 2, 4, 6, 8]);
     let len = m.len();
diff --git a/src/liballoc/collections/vec_deque.rs b/src/liballoc/collections/vec_deque.rs
index a4a0fbb194d..8f3dfabd888 100644
--- a/src/liballoc/collections/vec_deque.rs
+++ b/src/liballoc/collections/vec_deque.rs
@@ -10,8 +10,8 @@
 use core::array::LengthAtMost32;
 use core::cmp::{self, Ordering};
 use core::fmt;
-use core::iter::{repeat_with, FromIterator, FusedIterator};
-use core::mem;
+use core::iter::{once, repeat_with, FromIterator, FusedIterator};
+use core::mem::{self, replace};
 use core::ops::Bound::{Excluded, Included, Unbounded};
 use core::ops::{Index, IndexMut, RangeBounds, Try};
 use core::ptr::{self, NonNull};
@@ -57,11 +57,88 @@ pub struct VecDeque<T> {
     buf: RawVec<T>,
 }
 
+/// PairSlices pairs up equal length slice parts of two deques
+///
+/// For example, given deques "A" and "B" with the following division into slices:
+///
+/// A: [0 1 2] [3 4 5]
+/// B: [a b] [c d e]
+///
+/// It produces the following sequence of matching slices:
+///
+/// ([0 1], [a b])
+/// ([2], [c])
+/// ([3 4], [d e])
+///
+/// and the uneven remainder of either A or B is skipped.
+struct PairSlices<'a, 'b, T> {
+    a0: &'a mut [T],
+    a1: &'a mut [T],
+    b0: &'b [T],
+    b1: &'b [T],
+}
+
+impl<'a, 'b, T> PairSlices<'a, 'b, T> {
+    fn from(to: &'a mut VecDeque<T>, from: &'b VecDeque<T>) -> Self {
+        let (a0, a1) = to.as_mut_slices();
+        let (b0, b1) = from.as_slices();
+        PairSlices { a0, a1, b0, b1 }
+    }
+
+    fn has_remainder(&self) -> bool {
+        !self.b0.is_empty()
+    }
+
+    fn remainder(self) -> impl Iterator<Item=&'b [T]> {
+        once(self.b0).chain(once(self.b1))
+    }
+}
+
+impl<'a, 'b, T> Iterator for PairSlices<'a, 'b, T>
+{
+    type Item = (&'a mut [T], &'b [T]);
+    fn next(&mut self) -> Option<Self::Item> {
+        // Get next part length
+        let part = cmp::min(self.a0.len(), self.b0.len());
+        if part == 0 {
+            return None;
+        }
+        let (p0, p1) = replace(&mut self.a0, &mut []).split_at_mut(part);
+        let (q0, q1) = self.b0.split_at(part);
+
+        // Move a1 into a0, if it's empty (and b1, b0 the same way).
+        self.a0 = p1;
+        self.b0 = q1;
+        if self.a0.is_empty() {
+            self.a0 = replace(&mut self.a1, &mut []);
+        }
+        if self.b0.is_empty() {
+            self.b0 = replace(&mut self.b1, &[]);
+        }
+        Some((p0, q0))
+    }
+}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T: Clone> Clone for VecDeque<T> {
     fn clone(&self) -> VecDeque<T> {
         self.iter().cloned().collect()
     }
+
+    fn clone_from(&mut self, other: &Self) {
+        self.truncate(other.len());
+
+        let mut iter = PairSlices::from(self, other);
+        while let Some((dst, src)) = iter.next() {
+            dst.clone_from_slice(&src);
+        }
+
+        if iter.has_remainder() {
+            for remainder in iter.remainder() {
+                self.extend(remainder.iter().cloned());
+            }
+        }
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -1740,7 +1817,7 @@ impl<T> VecDeque<T> {
             }
         }
 
-        return elem;
+        elem
     }
 
     /// Splits the `VecDeque` into two at the given index.
@@ -2209,6 +2286,16 @@ impl<'a, T> Iterator for Iter<'a, T> {
         final_res
     }
 
+    fn nth(&mut self, n: usize) -> Option<Self::Item> {
+        if n >= count(self.tail, self.head, self.ring.len()) {
+            self.tail = self.head;
+            None
+        } else {
+            self.tail = wrap_index(self.tail.wrapping_add(n), self.ring.len());
+            self.next()
+        }
+    }
+
     #[inline]
     fn last(mut self) -> Option<&'a T> {
         self.next_back()
@@ -2327,6 +2414,16 @@ impl<'a, T> Iterator for IterMut<'a, T> {
         back.iter_mut().fold(accum, &mut f)
     }
 
+    fn nth(&mut self, n: usize) -> Option<Self::Item> {
+        if n >= count(self.tail, self.head, self.ring.len()) {
+            self.tail = self.head;
+            None
+        } else {
+            self.tail = wrap_index(self.tail.wrapping_add(n), self.ring.len());
+            self.next()
+        }
+    }
+
     #[inline]
     fn last(mut self) -> Option<&'a mut T> {
         self.next_back()
diff --git a/src/liballoc/collections/vec_deque/tests.rs b/src/liballoc/collections/vec_deque/tests.rs
index d2535239979..d578ee0dac4 100644
--- a/src/liballoc/collections/vec_deque/tests.rs
+++ b/src/liballoc/collections/vec_deque/tests.rs
@@ -362,6 +362,29 @@ fn test_vec_from_vecdeque() {
 }
 
 #[test]
+fn test_clone_from() {
+    let m = vec![1; 8];
+    let n = vec![2; 12];
+    for pfv in 0..8 {
+        for pfu in 0..8 {
+            for longer in 0..2 {
+                let (vr, ur) = if longer == 0 { (&m, &n) } else { (&n, &m) };
+                let mut v = VecDeque::from(vr.clone());
+                for _ in 0..pfv {
+                    v.push_front(1);
+                }
+                let mut u = VecDeque::from(ur.clone());
+                for _ in 0..pfu {
+                    u.push_front(2);
+                }
+                v.clone_from(&u);
+                assert_eq!(&v, &u);
+            }
+        }
+    }
+}
+
+#[test]
 fn issue_53529() {
     use crate::boxed::Box;
 
diff --git a/src/liballoc/fmt.rs b/src/liballoc/fmt.rs
index 68cbc366d7b..cbfc55233a1 100644
--- a/src/liballoc/fmt.rs
+++ b/src/liballoc/fmt.rs
@@ -80,24 +80,210 @@
 //! arguments which have names. Like with positional parameters, it is not
 //! valid to provide named parameters that are unused by the format string.
 //!
-//! ## Argument types
+//! # Formatting Parameters
+//!
+//! Each argument being formatted can be transformed by a number of formatting
+//! parameters (corresponding to `format_spec` in the syntax above). These
+//! parameters affect the string representation of what's being formatted.
+//!
+//! ## Width
+//!
+//! ```
+//! // All of these print "Hello x    !"
+//! println!("Hello {:5}!", "x");
+//! println!("Hello {:1$}!", "x", 5);
+//! println!("Hello {1:0$}!", 5, "x");
+//! println!("Hello {:width$}!", "x", width = 5);
+//! ```
+//!
+//! This is a parameter for the "minimum width" that the format should take up.
+//! If the value's string does not fill up this many characters, then the
+//! padding specified by fill/alignment will be used to take up the required
+//! space (see below).
+//!
+//! The value for the width can also be provided as a [`usize`] in the list of
+//! parameters by adding a postfix `$`, indicating that the second argument is
+//! a [`usize`] specifying the width.
+//!
+//! Referring to an argument with the dollar syntax does not affect the "next
+//! argument" counter, so it's usually a good idea to refer to arguments by
+//! position, or use named arguments.
+//!
+//! ## Fill/Alignment
+//!
+//! ```
+//! assert_eq!(format!("Hello {:<5}!", "x"),  "Hello x    !");
+//! assert_eq!(format!("Hello {:-<5}!", "x"), "Hello x----!");
+//! assert_eq!(format!("Hello {:^5}!", "x"),  "Hello   x  !");
+//! assert_eq!(format!("Hello {:>5}!", "x"),  "Hello     x!");
+//! ```
+//!
+//! The optional fill character and alignment is provided normally in conjunction with the
+//! [`width`](#width) parameter. It must be defined before `width`, right after the `:`.
+//! This indicates that if the value being formatted is smaller than
+//! `width` some extra characters will be printed around it.
+//! Filling comes in the following variants for different alignments:
+//!
+//! * `[fill]<` - the argument is left-aligned in `width` columns
+//! * `[fill]^` - the argument is center-aligned in `width` columns
+//! * `[fill]>` - the argument is right-aligned in `width` columns
+//!
+//! The default [fill/alignment](#fillalignment) for non-numerics is a space and
+//! left-aligned. The
+//! defaults for numeric formatters is also a space but with right-alignment. If
+//! the `0` flag (see below) is specified for numerics, then the implicit fill character is
+//! `0`.
+//!
+//! Note that alignment may not be implemented by some types. In particular, it
+//! is not generally implemented for the `Debug` trait.  A good way to ensure
+//! padding is applied is to format your input, then pad this resulting string
+//! to obtain your output:
+//!
+//! ```
+//! println!("Hello {:^15}!", format!("{:?}", Some("hi"))); // => "Hello   Some("hi")   !"
+//! ```
+//!
+//! ## Sign/`#`/`0`
+//!
+//! ```
+//! assert_eq!(format!("Hello {:+}!", 5), "Hello +5!");
+//! assert_eq!(format!("{:#x}!", 27), "0x1b!");
+//! assert_eq!(format!("Hello {:05}!", 5),  "Hello 00005!");
+//! assert_eq!(format!("Hello {:05}!", -5), "Hello -0005!");
+//! assert_eq!(format!("{:#010x}!", 27), "0x0000001b!");
+//! ```
+//!
+//! These are all flags altering the behavior of the formatter.
+//!
+//! * `+` - This is intended for numeric types and indicates that the sign
+//!         should always be printed. Positive signs are never printed by
+//!         default, and the negative sign is only printed by default for the
+//!         `Signed` trait. This flag indicates that the correct sign (`+` or `-`)
+//!         should always be printed.
+//! * `-` - Currently not used
+//! * `#` - This flag is indicates that the "alternate" form of printing should
+//!         be used. The alternate forms are:
+//!     * `#?` - pretty-print the [`Debug`] formatting
+//!     * `#x` - precedes the argument with a `0x`
+//!     * `#X` - precedes the argument with a `0x`
+//!     * `#b` - precedes the argument with a `0b`
+//!     * `#o` - precedes the argument with a `0o`
+//! * `0` - This is used to indicate for integer formats that the padding to `width` should
+//!         both be done with a `0` character as well as be sign-aware. A format
+//!         like `{:08}` would yield `00000001` for the integer `1`, while the
+//!         same format would yield `-0000001` for the integer `-1`. Notice that
+//!         the negative version has one fewer zero than the positive version.
+//!         Note that padding zeroes are always placed after the sign (if any)
+//!         and before the digits. When used together with the `#` flag, a similar
+//!         rule applies: padding zeroes are inserted after the prefix but before
+//!         the digits. The prefix is included in the total width.
+//!
+//! ## Precision
+//!
+//! For non-numeric types, this can be considered a "maximum width". If the resulting string is
+//! longer than this width, then it is truncated down to this many characters and that truncated
+//! value is emitted with proper `fill`, `alignment` and `width` if those parameters are set.
+//!
+//! For integral types, this is ignored.
+//!
+//! For floating-point types, this indicates how many digits after the decimal point should be
+//! printed.
+//!
+//! There are three possible ways to specify the desired `precision`:
+//!
+//! 1. An integer `.N`:
+//!
+//!    the integer `N` itself is the precision.
+//!
+//! 2. An integer or name followed by dollar sign `.N$`:
+//!
+//!    use format *argument* `N` (which must be a `usize`) as the precision.
+//!
+//! 3. An asterisk `.*`:
+//!
+//!    `.*` means that this `{...}` is associated with *two* format inputs rather than one: the
+//!    first input holds the `usize` precision, and the second holds the value to print. Note that
+//!    in this case, if one uses the format string `{<arg>:<spec>.*}`, then the `<arg>` part refers
+//!    to the *value* to print, and the `precision` must come in the input preceding `<arg>`.
+//!
+//! For example, the following calls all print the same thing `Hello x is 0.01000`:
+//!
+//! ```
+//! // Hello {arg 0 ("x")} is {arg 1 (0.01) with precision specified inline (5)}
+//! println!("Hello {0} is {1:.5}", "x", 0.01);
+//!
+//! // Hello {arg 1 ("x")} is {arg 2 (0.01) with precision specified in arg 0 (5)}
+//! println!("Hello {1} is {2:.0$}", 5, "x", 0.01);
+//!
+//! // Hello {arg 0 ("x")} is {arg 2 (0.01) with precision specified in arg 1 (5)}
+//! println!("Hello {0} is {2:.1$}", "x", 5, 0.01);
+//!
+//! // Hello {next arg ("x")} is {second of next two args (0.01) with precision
+//! //                          specified in first of next two args (5)}
+//! println!("Hello {} is {:.*}",    "x", 5, 0.01);
+//!
+//! // Hello {next arg ("x")} is {arg 2 (0.01) with precision
+//! //                          specified in its predecessor (5)}
+//! println!("Hello {} is {2:.*}",   "x", 5, 0.01);
+//!
+//! // Hello {next arg ("x")} is {arg "number" (0.01) with precision specified
+//! //                          in arg "prec" (5)}
+//! println!("Hello {} is {number:.prec$}", "x", prec = 5, number = 0.01);
+//! ```
 //!
-//! Each argument's type is dictated by the format string.
-//! There are various parameters which require a particular type, however.
-//! An example is the `{:.*}` syntax, which sets the number of decimal places
-//! in floating-point types:
+//! While these:
 //!
 //! ```
-//! let formatted_number = format!("{:.*}", 2, 1.234567);
+//! println!("{}, `{name:.*}` has 3 fractional digits", "Hello", 3, name=1234.56);
+//! println!("{}, `{name:.*}` has 3 characters", "Hello", 3, name="1234.56");
+//! println!("{}, `{name:>8.*}` has 3 right-aligned characters", "Hello", 3, name="1234.56");
+//! ```
 //!
-//! assert_eq!("1.23", formatted_number)
+//! print two significantly different things:
+//!
+//! ```text
+//! Hello, `1234.560` has 3 fractional digits
+//! Hello, `123` has 3 characters
+//! Hello, `     123` has 3 right-aligned characters
 //! ```
 //!
-//! If this syntax is used, then the number of characters to print precedes the
-//! actual object being formatted, and the number of characters must have the
-//! type [`usize`].
+//! # Escaping
+//!
+//! The literal characters `{` and `}` may be included in a string by preceding
+//! them with the same character. For example, the `{` character is escaped with
+//! `{{` and the `}` character is escaped with `}}`.
 //!
-//! ## Formatting traits
+//! ```
+//! assert_eq!(format!("Hello {{}}"), "Hello {}");
+//! assert_eq!(format!("{{ Hello"), "{ Hello");
+//! ```
+//!
+//! # Syntax
+//!
+//! To summarize, here you can find the full grammar of format strings.
+//! The syntax for the formatting language used is drawn from other languages,
+//! so it should not be too alien. Arguments are formatted with Python-like
+//! syntax, meaning that arguments are surrounded by `{}` instead of the C-like
+//! `%`. The actual grammar for the formatting syntax is:
+//!
+//! ```text
+//! format_string := <text> [ maybe-format <text> ] *
+//! maybe-format := '{' '{' | '}' '}' | <format>
+//! format := '{' [ argument ] [ ':' format_spec ] '}'
+//! argument := integer | identifier
+//!
+//! format_spec := [[fill]align][sign]['#']['0'][width]['.' precision][type]
+//! fill := character
+//! align := '<' | '^' | '>'
+//! sign := '+' | '-'
+//! width := count
+//! precision := count | '*'
+//! type := identifier | '?' | ''
+//! count := parameter | integer
+//! parameter := argument '$'
+//! ```
+//!
+//! # Formatting traits
 //!
 //! When requesting that an argument be formatted with a particular type, you
 //! are actually requesting that an argument ascribes to a particular trait.
@@ -220,7 +406,7 @@
 //! assert_eq!(format!("{} {:?}", "foo\n", "bar\n"), "foo\n \"bar\\n\"");
 //! ```
 //!
-//! ## Related macros
+//! # Related macros
 //!
 //! There are a number of related macros in the [`format!`] family. The ones that
 //! are currently implemented are:
@@ -300,185 +486,6 @@
 //! it would internally pass around this structure until it has been determined
 //! where output should go to.
 //!
-//! # Syntax
-//!
-//! The syntax for the formatting language used is drawn from other languages,
-//! so it should not be too alien. Arguments are formatted with Python-like
-//! syntax, meaning that arguments are surrounded by `{}` instead of the C-like
-//! `%`. The actual grammar for the formatting syntax is:
-//!
-//! ```text
-//! format_string := <text> [ maybe-format <text> ] *
-//! maybe-format := '{' '{' | '}' '}' | <format>
-//! format := '{' [ argument ] [ ':' format_spec ] '}'
-//! argument := integer | identifier
-//!
-//! format_spec := [[fill]align][sign]['#']['0'][width]['.' precision][type]
-//! fill := character
-//! align := '<' | '^' | '>'
-//! sign := '+' | '-'
-//! width := count
-//! precision := count | '*'
-//! type := identifier | '?' | ''
-//! count := parameter | integer
-//! parameter := argument '$'
-//! ```
-//!
-//! # Formatting Parameters
-//!
-//! Each argument being formatted can be transformed by a number of formatting
-//! parameters (corresponding to `format_spec` in the syntax above). These
-//! parameters affect the string representation of what's being formatted.
-//!
-//! ## Fill/Alignment
-//!
-//! The fill character is provided normally in conjunction with the
-//! [`width`](#width)
-//! parameter. This indicates that if the value being formatted is smaller than
-//! `width` some extra characters will be printed around it. The extra
-//! characters are specified by `fill`, and the alignment can be one of the
-//! following options:
-//!
-//! * `<` - the argument is left-aligned in `width` columns
-//! * `^` - the argument is center-aligned in `width` columns
-//! * `>` - the argument is right-aligned in `width` columns
-//!
-//! Note that alignment may not be implemented by some types. In particular, it
-//! is not generally implemented for the `Debug` trait.  A good way to ensure
-//! padding is applied is to format your input, then use this resulting string
-//! to pad your output.
-//!
-//! ## Sign/`#`/`0`
-//!
-//! These can all be interpreted as flags for a particular formatter.
-//!
-//! * `+` - This is intended for numeric types and indicates that the sign
-//!         should always be printed. Positive signs are never printed by
-//!         default, and the negative sign is only printed by default for the
-//!         `Signed` trait. This flag indicates that the correct sign (`+` or `-`)
-//!         should always be printed.
-//! * `-` - Currently not used
-//! * `#` - This flag is indicates that the "alternate" form of printing should
-//!         be used. The alternate forms are:
-//!     * `#?` - pretty-print the [`Debug`] formatting
-//!     * `#x` - precedes the argument with a `0x`
-//!     * `#X` - precedes the argument with a `0x`
-//!     * `#b` - precedes the argument with a `0b`
-//!     * `#o` - precedes the argument with a `0o`
-//! * `0` - This is used to indicate for integer formats that the padding should
-//!         both be done with a `0` character as well as be sign-aware. A format
-//!         like `{:08}` would yield `00000001` for the integer `1`, while the
-//!         same format would yield `-0000001` for the integer `-1`. Notice that
-//!         the negative version has one fewer zero than the positive version.
-//!         Note that padding zeroes are always placed after the sign (if any)
-//!         and before the digits. When used together with the `#` flag, a similar
-//!         rule applies: padding zeroes are inserted after the prefix but before
-//!         the digits.
-//!
-//! ## Width
-//!
-//! This is a parameter for the "minimum width" that the format should take up.
-//! If the value's string does not fill up this many characters, then the
-//! padding specified by fill/alignment will be used to take up the required
-//! space.
-//!
-//! The default [fill/alignment](#fillalignment) for non-numerics is a space and
-//! left-aligned. The
-//! defaults for numeric formatters is also a space but with right-alignment. If
-//! the `0` flag is specified for numerics, then the implicit fill character is
-//! `0`.
-//!
-//! The value for the width can also be provided as a [`usize`] in the list of
-//! parameters by using the dollar syntax indicating that the second argument is
-//! a [`usize`] specifying the width, for example:
-//!
-//! ```
-//! // All of these print "Hello x    !"
-//! println!("Hello {:5}!", "x");
-//! println!("Hello {:1$}!", "x", 5);
-//! println!("Hello {1:0$}!", 5, "x");
-//! println!("Hello {:width$}!", "x", width = 5);
-//! ```
-//!
-//! Referring to an argument with the dollar syntax does not affect the "next
-//! argument" counter, so it's usually a good idea to refer to arguments by
-//! position, or use named arguments.
-//!
-//! ## Precision
-//!
-//! For non-numeric types, this can be considered a "maximum width". If the resulting string is
-//! longer than this width, then it is truncated down to this many characters and that truncated
-//! value is emitted with proper `fill`, `alignment` and `width` if those parameters are set.
-//!
-//! For integral types, this is ignored.
-//!
-//! For floating-point types, this indicates how many digits after the decimal point should be
-//! printed.
-//!
-//! There are three possible ways to specify the desired `precision`:
-//!
-//! 1. An integer `.N`:
-//!
-//!    the integer `N` itself is the precision.
-//!
-//! 2. An integer or name followed by dollar sign `.N$`:
-//!
-//!    use format *argument* `N` (which must be a `usize`) as the precision.
-//!
-//! 3. An asterisk `.*`:
-//!
-//!    `.*` means that this `{...}` is associated with *two* format inputs rather than one: the
-//!    first input holds the `usize` precision, and the second holds the value to print. Note that
-//!    in this case, if one uses the format string `{<arg>:<spec>.*}`, then the `<arg>` part refers
-//!    to the *value* to print, and the `precision` must come in the input preceding `<arg>`.
-//!
-//! For example, the following calls all print the same thing `Hello x is 0.01000`:
-//!
-//! ```
-//! // Hello {arg 0 ("x")} is {arg 1 (0.01) with precision specified inline (5)}
-//! println!("Hello {0} is {1:.5}", "x", 0.01);
-//!
-//! // Hello {arg 1 ("x")} is {arg 2 (0.01) with precision specified in arg 0 (5)}
-//! println!("Hello {1} is {2:.0$}", 5, "x", 0.01);
-//!
-//! // Hello {arg 0 ("x")} is {arg 2 (0.01) with precision specified in arg 1 (5)}
-//! println!("Hello {0} is {2:.1$}", "x", 5, 0.01);
-//!
-//! // Hello {next arg ("x")} is {second of next two args (0.01) with precision
-//! //                          specified in first of next two args (5)}
-//! println!("Hello {} is {:.*}",    "x", 5, 0.01);
-//!
-//! // Hello {next arg ("x")} is {arg 2 (0.01) with precision
-//! //                          specified in its predecessor (5)}
-//! println!("Hello {} is {2:.*}",   "x", 5, 0.01);
-//!
-//! // Hello {next arg ("x")} is {arg "number" (0.01) with precision specified
-//! //                          in arg "prec" (5)}
-//! println!("Hello {} is {number:.prec$}", "x", prec = 5, number = 0.01);
-//! ```
-//!
-//! While these:
-//!
-//! ```
-//! println!("{}, `{name:.*}` has 3 fractional digits", "Hello", 3, name=1234.56);
-//! println!("{}, `{name:.*}` has 3 characters", "Hello", 3, name="1234.56");
-//! println!("{}, `{name:>8.*}` has 3 right-aligned characters", "Hello", 3, name="1234.56");
-//! ```
-//!
-//! print two significantly different things:
-//!
-//! ```text
-//! Hello, `1234.560` has 3 fractional digits
-//! Hello, `123` has 3 characters
-//! Hello, `     123` has 3 right-aligned characters
-//! ```
-//!
-//! # Escaping
-//!
-//! The literal characters `{` and `}` may be included in a string by preceding
-//! them with the same character. For example, the `{` character is escaped with
-//! `{{` and the `}` character is escaped with `}}`.
-//!
 //! [`usize`]: ../../std/primitive.usize.html
 //! [`isize`]: ../../std/primitive.isize.html
 //! [`i8`]: ../../std/primitive.i8.html
diff --git a/src/liballoc/lib.rs b/src/liballoc/lib.rs
index 247cd9a0201..94379afc2bd 100644
--- a/src/liballoc/lib.rs
+++ b/src/liballoc/lib.rs
@@ -85,6 +85,7 @@
 #![feature(const_generic_impls_guard)]
 #![feature(const_generics)]
 #![feature(const_in_array_repeat_expressions)]
+#![feature(cow_is_borrowed)]
 #![feature(dispatch_from_dyn)]
 #![feature(core_intrinsics)]
 #![feature(container_error_extra)]
@@ -121,7 +122,6 @@
 #![feature(maybe_uninit_extra, maybe_uninit_slice)]
 #![feature(alloc_layout_extra)]
 #![feature(try_trait)]
-#![feature(mem_take)]
 #![feature(associated_type_bounds)]
 
 // Allow testing this library
@@ -154,7 +154,7 @@ mod boxed {
 #[cfg(test)]
 mod tests;
 pub mod collections;
-#[cfg(all(target_has_atomic = "ptr", target_has_atomic = "cas"))]
+#[cfg(target_has_atomic = "ptr")]
 pub mod sync;
 pub mod rc;
 pub mod raw_vec;
diff --git a/src/liballoc/rc.rs b/src/liballoc/rc.rs
index f234ac5ebe5..f1c4c32e116 100644
--- a/src/liballoc/rc.rs
+++ b/src/liballoc/rc.rs
@@ -3,8 +3,9 @@
 //!
 //! The type [`Rc<T>`][`Rc`] provides shared ownership of a value of type `T`,
 //! allocated in the heap. Invoking [`clone`][clone] on [`Rc`] produces a new
-//! pointer to the same value in the heap. When the last [`Rc`] pointer to a
-//! given value is destroyed, the pointed-to value is also destroyed.
+//! pointer to the same allocation in the heap. When the last [`Rc`] pointer to a
+//! given allocation is destroyed, the value stored in that allocation (often
+//! referred to as "inner value") is also dropped.
 //!
 //! Shared references in Rust disallow mutation by default, and [`Rc`]
 //! is no exception: you cannot generally obtain a mutable reference to
@@ -21,8 +22,10 @@
 //!
 //! The [`downgrade`][downgrade] method can be used to create a non-owning
 //! [`Weak`] pointer. A [`Weak`] pointer can be [`upgrade`][upgrade]d
-//! to an [`Rc`], but this will return [`None`] if the value has
-//! already been dropped.
+//! to an [`Rc`], but this will return [`None`] if the value stored in the allocation has
+//! already been dropped. In other words, `Weak` pointers do not keep the value
+//! inside the allocation alive; however, they *do* keep the allocation
+//! (the backing store for the inner value) alive.
 //!
 //! A cycle between [`Rc`] pointers will never be deallocated. For this reason,
 //! [`Weak`] is used to break cycles. For example, a tree could have strong
@@ -41,13 +44,13 @@
 //! Rc::downgrade(&my_rc);
 //! ```
 //!
-//! [`Weak<T>`][`Weak`] does not auto-dereference to `T`, because the value may have
-//! already been destroyed.
+//! [`Weak<T>`][`Weak`] does not auto-dereference to `T`, because the inner value may have
+//! already been dropped.
 //!
 //! # Cloning references
 //!
-//! Creating a new reference from an existing reference counted pointer is done using the
-//! `Clone` trait implemented for [`Rc<T>`][`Rc`] and [`Weak<T>`][`Weak`].
+//! Creating a new reference to the same allocation as an existing reference counted pointer
+//! is done using the `Clone` trait implemented for [`Rc<T>`][`Rc`] and [`Weak<T>`][`Weak`].
 //!
 //! ```
 //! use std::rc::Rc;
@@ -93,7 +96,7 @@
 //!     );
 //!
 //!     // Create `Gadget`s belonging to `gadget_owner`. Cloning the `Rc<Owner>`
-//!     // value gives us a new pointer to the same `Owner` value, incrementing
+//!     // gives us a new pointer to the same `Owner` allocation, incrementing
 //!     // the reference count in the process.
 //!     let gadget1 = Gadget {
 //!         id: 1,
@@ -110,8 +113,8 @@
 //!     // Despite dropping `gadget_owner`, we're still able to print out the name
 //!     // of the `Owner` of the `Gadget`s. This is because we've only dropped a
 //!     // single `Rc<Owner>`, not the `Owner` it points to. As long as there are
-//!     // other `Rc<Owner>` values pointing at the same `Owner`, it will remain
-//!     // allocated. The field projection `gadget1.owner.name` works because
+//!     // other `Rc<Owner>` pointing at the same `Owner` allocation, it will remain
+//!     // live. The field projection `gadget1.owner.name` works because
 //!     // `Rc<Owner>` automatically dereferences to `Owner`.
 //!     println!("Gadget {} owned by {}", gadget1.id, gadget1.owner.name);
 //!     println!("Gadget {} owned by {}", gadget2.id, gadget2.owner.name);
@@ -124,9 +127,9 @@
 //!
 //! If our requirements change, and we also need to be able to traverse from
 //! `Owner` to `Gadget`, we will run into problems. An [`Rc`] pointer from `Owner`
-//! to `Gadget` introduces a cycle between the values. This means that their
-//! reference counts can never reach 0, and the values will remain allocated
-//! forever: a memory leak. In order to get around this, we can use [`Weak`]
+//! to `Gadget` introduces a cycle. This means that their
+//! reference counts can never reach 0, and the allocation will never be destroyed:
+//! a memory leak. In order to get around this, we can use [`Weak`]
 //! pointers.
 //!
 //! Rust actually makes it somewhat difficult to produce this loop in the first
@@ -193,10 +196,10 @@
 //!     for gadget_weak in gadget_owner.gadgets.borrow().iter() {
 //!
 //!         // `gadget_weak` is a `Weak<Gadget>`. Since `Weak` pointers can't
-//!         // guarantee the value is still allocated, we need to call
+//!         // guarantee the allocation still exists, we need to call
 //!         // `upgrade`, which returns an `Option<Rc<Gadget>>`.
 //!         //
-//!         // In this case we know the value still exists, so we simply
+//!         // In this case we know the allocation still exists, so we simply
 //!         // `unwrap` the `Option`. In a more complicated program, you might
 //!         // need graceful error handling for a `None` result.
 //!
@@ -365,7 +368,7 @@ impl<T> Rc<T> {
         unsafe { Pin::new_unchecked(Rc::new(value)) }
     }
 
-    /// Returns the contained value, if the `Rc` has exactly one strong reference.
+    /// Returns the inner value, if the `Rc` has exactly one strong reference.
     ///
     /// Otherwise, an [`Err`][result] is returned with the same `Rc` that was
     /// passed in.
@@ -446,7 +449,7 @@ impl<T> Rc<mem::MaybeUninit<T>> {
     /// # Safety
     ///
     /// As with [`MaybeUninit::assume_init`],
-    /// it is up to the caller to guarantee that the value
+    /// it is up to the caller to guarantee that the inner value
     /// really is in an initialized state.
     /// Calling this when the content is not yet fully initialized
     /// causes immediate undefined behavior.
@@ -485,7 +488,7 @@ impl<T> Rc<[mem::MaybeUninit<T>]> {
     /// # Safety
     ///
     /// As with [`MaybeUninit::assume_init`],
-    /// it is up to the caller to guarantee that the value
+    /// it is up to the caller to guarantee that the inner value
     /// really is in an initialized state.
     /// Calling this when the content is not yet fully initialized
     /// causes immediate undefined behavior.
@@ -604,7 +607,7 @@ impl<T: ?Sized> Rc<T> {
         unsafe { NonNull::new_unchecked(Rc::into_raw(this) as *mut _) }
     }
 
-    /// Creates a new [`Weak`][weak] pointer to this value.
+    /// Creates a new [`Weak`][weak] pointer to this allocation.
     ///
     /// [weak]: struct.Weak.html
     ///
@@ -625,7 +628,7 @@ impl<T: ?Sized> Rc<T> {
         Weak { ptr: this.ptr }
     }
 
-    /// Gets the number of [`Weak`][weak] pointers to this value.
+    /// Gets the number of [`Weak`][weak] pointers to this allocation.
     ///
     /// [weak]: struct.Weak.html
     ///
@@ -645,7 +648,7 @@ impl<T: ?Sized> Rc<T> {
         this.weak() - 1
     }
 
-    /// Gets the number of strong (`Rc`) pointers to this value.
+    /// Gets the number of strong (`Rc`) pointers to this allocation.
     ///
     /// # Examples
     ///
@@ -664,7 +667,7 @@ impl<T: ?Sized> Rc<T> {
     }
 
     /// Returns `true` if there are no other `Rc` or [`Weak`][weak] pointers to
-    /// this inner value.
+    /// this allocation.
     ///
     /// [weak]: struct.Weak.html
     #[inline]
@@ -672,14 +675,14 @@ impl<T: ?Sized> Rc<T> {
         Rc::weak_count(this) == 0 && Rc::strong_count(this) == 1
     }
 
-    /// Returns a mutable reference to the inner value, if there are
-    /// no other `Rc` or [`Weak`][weak] pointers to the same value.
+    /// Returns a mutable reference into the given `Rc`, if there are
+    /// no other `Rc` or [`Weak`][weak] pointers to the same allocation.
     ///
     /// Returns [`None`] otherwise, because it is not safe to
     /// mutate a shared value.
     ///
     /// See also [`make_mut`][make_mut], which will [`clone`][clone]
-    /// the inner value when it's shared.
+    /// the inner value when there are other pointers.
     ///
     /// [weak]: struct.Weak.html
     /// [`None`]: ../../std/option/enum.Option.html#variant.None
@@ -710,7 +713,7 @@ impl<T: ?Sized> Rc<T> {
         }
     }
 
-    /// Returns a mutable reference to the inner value,
+    /// Returns a mutable reference into the given `Rc`,
     /// without any check.
     ///
     /// See also [`get_mut`], which is safe and does appropriate checks.
@@ -719,7 +722,7 @@ impl<T: ?Sized> Rc<T> {
     ///
     /// # Safety
     ///
-    /// Any other `Rc` or [`Weak`] pointers to the same value must not be dereferenced
+    /// Any other `Rc` or [`Weak`] pointers to the same allocation must not be dereferenced
     /// for the duration of the returned borrow.
     /// This is trivially the case if no such pointers exist,
     /// for example immediately after `Rc::new`.
@@ -745,8 +748,8 @@ impl<T: ?Sized> Rc<T> {
 
     #[inline]
     #[stable(feature = "ptr_eq", since = "1.17.0")]
-    /// Returns `true` if the two `Rc`s point to the same value (not
-    /// just values that compare as equal).
+    /// Returns `true` if the two `Rc`s point to the same allocation
+    /// (in a vein similar to [`ptr::eq`]).
     ///
     /// # Examples
     ///
@@ -760,6 +763,8 @@ impl<T: ?Sized> Rc<T> {
     /// assert!(Rc::ptr_eq(&five, &same_five));
     /// assert!(!Rc::ptr_eq(&five, &other_five));
     /// ```
+    ///
+    /// [`ptr::eq`]: ../../std/ptr/fn.eq.html
     pub fn ptr_eq(this: &Self, other: &Self) -> bool {
         this.ptr.as_ptr() == other.ptr.as_ptr()
     }
@@ -768,12 +773,12 @@ impl<T: ?Sized> Rc<T> {
 impl<T: Clone> Rc<T> {
     /// Makes a mutable reference into the given `Rc`.
     ///
-    /// If there are other `Rc` pointers to the same value, then `make_mut` will
-    /// [`clone`] the inner value to ensure unique ownership.  This is also
+    /// If there are other `Rc` pointers to the same allocation, then `make_mut` will
+    /// [`clone`] the inner value to a new allocation to ensure unique ownership.  This is also
     /// referred to as clone-on-write.
     ///
-    /// If there are no other `Rc` pointers to this value, then [`Weak`]
-    /// pointers to this value will be dissassociated.
+    /// If there are no other `Rc` pointers to this allocation, then [`Weak`]
+    /// pointers to this allocation will be disassociated.
     ///
     /// See also [`get_mut`], which will fail rather than cloning.
     ///
@@ -794,12 +799,12 @@ impl<T: Clone> Rc<T> {
     /// *Rc::make_mut(&mut data) += 1;        // Won't clone anything
     /// *Rc::make_mut(&mut other_data) *= 2;  // Won't clone anything
     ///
-    /// // Now `data` and `other_data` point to different values.
+    /// // Now `data` and `other_data` point to different allocations.
     /// assert_eq!(*data, 8);
     /// assert_eq!(*other_data, 12);
     /// ```
     ///
-    /// [`Weak`] pointers will be dissassociated:
+    /// [`Weak`] pointers will be disassociated:
     ///
     /// ```
     /// use std::rc::Rc;
@@ -837,7 +842,7 @@ impl<T: Clone> Rc<T> {
         // returned is the *only* pointer that will ever be returned to T. Our
         // reference count is guaranteed to be 1 at this point, and we required
         // the `Rc<T>` itself to be `mut`, so we're returning the only possible
-        // reference to the inner value.
+        // reference to the allocation.
         unsafe {
             &mut this.ptr.as_mut().value
         }
@@ -861,11 +866,9 @@ impl Rc<dyn Any> {
     ///     }
     /// }
     ///
-    /// fn main() {
-    ///     let my_string = "Hello World".to_string();
-    ///     print_if_string(Rc::new(my_string));
-    ///     print_if_string(Rc::new(0i8));
-    /// }
+    /// let my_string = "Hello World".to_string();
+    /// print_if_string(Rc::new(my_string));
+    /// print_if_string(Rc::new(0i8));
     /// ```
     pub fn downcast<T: Any>(self) -> Result<Rc<T>, Rc<dyn Any>> {
         if (*self).is::<T>() {
@@ -880,7 +883,7 @@ impl Rc<dyn Any> {
 
 impl<T: ?Sized> Rc<T> {
     /// Allocates an `RcBox<T>` with sufficient space for
-    /// a possibly-unsized value where the value has the layout provided.
+    /// a possibly-unsized inner value where the value has the layout provided.
     ///
     /// The function `mem_to_rcbox` is called with the data pointer
     /// and must return back a (potentially fat)-pointer for the `RcBox<T>`.
@@ -910,7 +913,7 @@ impl<T: ?Sized> Rc<T> {
         inner
     }
 
-    /// Allocates an `RcBox<T>` with sufficient space for an unsized value
+    /// Allocates an `RcBox<T>` with sufficient space for an unsized inner value
     unsafe fn allocate_for_ptr(ptr: *const T) -> *mut RcBox<T> {
         // Allocate for the `RcBox<T>` using the given value.
         Self::allocate_for_layout(
@@ -1113,7 +1116,7 @@ unsafe impl<#[may_dangle] T: ?Sized> Drop for Rc<T> {
 impl<T: ?Sized> Clone for Rc<T> {
     /// Makes a clone of the `Rc` pointer.
     ///
-    /// This creates another pointer to the same inner value, increasing the
+    /// This creates another pointer to the same allocation, increasing the
     /// strong reference count.
     ///
     /// # Examples
@@ -1174,6 +1177,8 @@ impl<T: ?Sized + PartialEq> RcEqIdent<T> for Rc<T> {
 /// store large values, that are slow to clone, but also heavy to check for equality, causing this
 /// cost to pay off more easily. It's also more likely to have two `Rc` clones, that point to
 /// the same value, than two `&T`s.
+///
+/// We can only do this when `T: Eq` as a `PartialEq` might be deliberately irreflexive.
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T: ?Sized + Eq> RcEqIdent<T> for Rc<T> {
     #[inline]
@@ -1191,9 +1196,11 @@ impl<T: ?Sized + Eq> RcEqIdent<T> for Rc<T> {
 impl<T: ?Sized + PartialEq> PartialEq for Rc<T> {
     /// Equality for two `Rc`s.
     ///
-    /// Two `Rc`s are equal if their inner values are equal.
+    /// Two `Rc`s are equal if their inner values are equal, even if they are
+    /// stored in different allocation.
     ///
-    /// If `T` also implements `Eq`, two `Rc`s that point to the same value are
+    /// If `T` also implements `Eq` (implying reflexivity of equality),
+    /// two `Rc`s that point to the same allocation are
     /// always equal.
     ///
     /// # Examples
@@ -1214,7 +1221,8 @@ impl<T: ?Sized + PartialEq> PartialEq for Rc<T> {
     ///
     /// 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
+    /// If `T` also implements `Eq` (implying reflexivity of equality),
+    /// two `Rc`s that point to the same allocation are
     /// never unequal.
     ///
     /// # Examples
@@ -1543,17 +1551,18 @@ impl<'a, T: 'a + Clone> RcFromIter<&'a T, slice::Iter<'a, T>> for Rc<[T]> {
 }
 
 /// `Weak` is a version of [`Rc`] that holds a non-owning reference to the
-/// managed value. The value is accessed by calling [`upgrade`] on the `Weak`
+/// managed allocation. The allocation is accessed by calling [`upgrade`] on the `Weak`
 /// pointer, which returns an [`Option`]`<`[`Rc`]`<T>>`.
 ///
 /// Since a `Weak` reference does not count towards ownership, it will not
-/// prevent the inner value from being dropped, and `Weak` itself makes no
-/// guarantees about the value still being present and may return [`None`]
-/// when [`upgrade`]d.
+/// prevent the value stored in the allocation from being dropped, and `Weak` itself makes no
+/// guarantees about the value still being present. Thus it may return [`None`]
+/// when [`upgrade`]d. Note however that a `Weak` reference *does* prevent the allocation
+/// itself (the backing store) from being deallocated.
 ///
-/// A `Weak` pointer is useful for keeping a temporary reference to the value
-/// within [`Rc`] without extending its lifetime. It is also used to prevent
-/// circular references between [`Rc`] pointers, since mutual owning references
+/// A `Weak` pointer is useful for keeping a temporary reference to the allocation
+/// managed by [`Rc`] without preventing its inner value from being dropped. It is also used to
+/// prevent circular references between [`Rc`] pointers, since mutual owning references
 /// would never allow either [`Rc`] to be dropped. For example, a tree could
 /// have strong [`Rc`] pointers from parent nodes to children, and `Weak`
 /// pointers from children back to their parents.
@@ -1752,10 +1761,10 @@ pub(crate) fn is_dangling<T: ?Sized>(ptr: NonNull<T>) -> bool {
 }
 
 impl<T: ?Sized> Weak<T> {
-    /// Attempts to upgrade the `Weak` pointer to an [`Rc`], extending
-    /// the lifetime of the value if successful.
+    /// Attempts to upgrade the `Weak` pointer to an [`Rc`], delaying
+    /// dropping of the inner value if successful.
     ///
-    /// Returns [`None`] if the value has since been dropped.
+    /// Returns [`None`] if the inner value has since been dropped.
     ///
     /// [`Rc`]: struct.Rc.html
     /// [`None`]: ../../std/option/enum.Option.html
@@ -1789,7 +1798,7 @@ impl<T: ?Sized> Weak<T> {
         }
     }
 
-    /// Gets the number of strong (`Rc`) pointers pointing to this value.
+    /// Gets the number of strong (`Rc`) pointers pointing to this allocation.
     ///
     /// If `self` was created using [`Weak::new`], this will return 0.
     ///
@@ -1803,11 +1812,11 @@ impl<T: ?Sized> Weak<T> {
         }
     }
 
-    /// Gets the number of `Weak` pointers pointing to this value.
+    /// Gets the number of `Weak` pointers pointing to this allocation.
     ///
     /// If `self` was created using [`Weak::new`], this will return `None`. If
     /// not, the returned value is at least 1, since `self` still points to the
-    /// value.
+    /// allocation.
     ///
     /// [`Weak::new`]: #method.new
     #[unstable(feature = "weak_counts", issue = "57977")]
@@ -1832,14 +1841,14 @@ impl<T: ?Sized> Weak<T> {
         }
     }
 
-    /// Returns `true` if the two `Weak`s point to the same value (not just
-    /// values that compare as equal), or if both don't point to any value
+    /// Returns `true` if the two `Weak`s point to the same allocation (similar to
+    /// [`ptr::eq`]), or if both don't point to any allocation
     /// (because they were created with `Weak::new()`).
     ///
     /// # Notes
     ///
     /// Since this compares pointers it means that `Weak::new()` will equal each
-    /// other, even though they don't point to any value.
+    /// other, even though they don't point to any allocation.
     ///
     /// # Examples
     ///
@@ -1871,6 +1880,8 @@ impl<T: ?Sized> Weak<T> {
     /// let third = Rc::downgrade(&third_rc);
     /// assert!(!first.ptr_eq(&third));
     /// ```
+    ///
+    /// [`ptr::eq`]: ../../std/ptr/fn.eq.html
     #[inline]
     #[stable(feature = "weak_ptr_eq", since = "1.39.0")]
     pub fn ptr_eq(&self, other: &Self) -> bool {
@@ -1920,7 +1931,7 @@ impl<T: ?Sized> Drop for Weak<T> {
 
 #[stable(feature = "rc_weak", since = "1.4.0")]
 impl<T: ?Sized> Clone for Weak<T> {
-    /// Makes a clone of the `Weak` pointer that points to the same value.
+    /// Makes a clone of the `Weak` pointer that points to the same allocation.
     ///
     /// # Examples
     ///
diff --git a/src/liballoc/slice.rs b/src/liballoc/slice.rs
index 881d499c074..08243ef7c51 100644
--- a/src/liballoc/slice.rs
+++ b/src/liballoc/slice.rs
@@ -411,25 +411,16 @@ impl<T> [T] {
     /// Basic usage:
     ///
     /// ```
-    /// #![feature(repeat_generic_slice)]
-    ///
-    /// fn main() {
-    ///     assert_eq!([1, 2].repeat(3), vec![1, 2, 1, 2, 1, 2]);
-    /// }
+    /// assert_eq!([1, 2].repeat(3), vec![1, 2, 1, 2, 1, 2]);
     /// ```
     ///
     /// A panic upon overflow:
     ///
     /// ```should_panic
-    /// #![feature(repeat_generic_slice)]
-    /// fn main() {
-    ///     // this will panic at runtime
-    ///     b"0123456789abcdef".repeat(usize::max_value());
-    /// }
+    /// // this will panic at runtime
+    /// b"0123456789abcdef".repeat(usize::max_value());
     /// ```
-    #[unstable(feature = "repeat_generic_slice",
-               reason = "it's on str, why not on slice?",
-               issue = "48784")]
+    #[stable(feature = "repeat_generic_slice", since = "1.40.0")]
     pub fn repeat(&self, n: usize) -> Vec<T> where T: Copy {
         if n == 0 {
             return Vec::new();
diff --git a/src/liballoc/str.rs b/src/liballoc/str.rs
index 9a1342c30d5..83816d8b954 100644
--- a/src/liballoc/str.rs
+++ b/src/liballoc/str.rs
@@ -456,7 +456,7 @@ impl str {
                 }
             }
         }
-        return s;
+        s
     }
 
     /// Converts a [`Box<str>`] into a [`String`] without copying or allocating.
@@ -500,10 +500,8 @@ impl str {
     /// A panic upon overflow:
     ///
     /// ```should_panic
-    /// fn main() {
-    ///     // this will panic at runtime
-    ///     "0123456789abcdef".repeat(usize::max_value());
-    /// }
+    /// // this will panic at runtime
+    /// "0123456789abcdef".repeat(usize::max_value());
     /// ```
     #[stable(feature = "repeat_str", since = "1.16.0")]
     pub fn repeat(&self, n: usize) -> String {
diff --git a/src/liballoc/string.rs b/src/liballoc/string.rs
index abe50fdb7a3..d9927c642b2 100644
--- a/src/liballoc/string.rs
+++ b/src/liballoc/string.rs
@@ -164,10 +164,8 @@ use crate::vec::Vec;
 ///
 /// fn example_func<A: TraitExample>(example_arg: A) {}
 ///
-/// fn main() {
-///     let example_string = String::from("example_string");
-///     example_func(&example_string);
-/// }
+/// let example_string = String::from("example_string");
+/// example_func(&example_string);
 /// ```
 ///
 /// There are two options that would work instead. The first would be to
@@ -198,20 +196,21 @@ use crate::vec::Vec;
 ///
 /// let story = String::from("Once upon a time...");
 ///
-/// let ptr = story.as_ptr();
+// FIXME Update this when vec_into_raw_parts is stabilized
+/// // Prevent automatically dropping the String's data
+/// let mut story = mem::ManuallyDrop::new(story);
+///
+/// let ptr = story.as_mut_ptr();
 /// let len = story.len();
 /// let capacity = story.capacity();
 ///
 /// // story has nineteen bytes
 /// assert_eq!(19, len);
 ///
-/// // Now that we have our parts, we throw the story away.
-/// mem::forget(story);
-///
 /// // We can re-build a String out of ptr, len, and capacity. This is all
 /// // unsafe because we are responsible for making sure the components are
 /// // valid:
-/// let s = unsafe { String::from_raw_parts(ptr as *mut _, len, capacity) } ;
+/// let s = unsafe { String::from_raw_parts(ptr, len, capacity) } ;
 ///
 /// assert_eq!(String::from("Once upon a time..."), s);
 /// ```
@@ -649,6 +648,37 @@ impl String {
         decode_utf16(v.iter().cloned()).map(|r| r.unwrap_or(REPLACEMENT_CHARACTER)).collect()
     }
 
+    /// Decomposes a `String` into its raw components.
+    ///
+    /// Returns the raw pointer to the underlying data, the length of
+    /// the string (in bytes), and the allocated capacity of the data
+    /// (in bytes). These are the same arguments in the same order as
+    /// the arguments to [`from_raw_parts`].
+    ///
+    /// After calling this function, the caller is responsible for the
+    /// memory previously managed by the `String`. The only way to do
+    /// this is to convert the raw pointer, length, and capacity back
+    /// into a `String` with the [`from_raw_parts`] function, allowing
+    /// the destructor to perform the cleanup.
+    ///
+    /// [`from_raw_parts`]: #method.from_raw_parts
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(vec_into_raw_parts)]
+    /// let s = String::from("hello");
+    ///
+    /// let (ptr, len, cap) = s.into_raw_parts();
+    ///
+    /// let rebuilt = unsafe { String::from_raw_parts(ptr, len, cap) };
+    /// assert_eq!(rebuilt, "hello");
+    /// ```
+    #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")]
+    pub fn into_raw_parts(self) -> (*mut u8, usize, usize) {
+        self.vec.into_raw_parts()
+    }
+
     /// Creates a new `String` from a length, capacity, and pointer.
     ///
     /// # Safety
@@ -679,13 +709,16 @@ impl String {
     ///
     /// unsafe {
     ///     let s = String::from("hello");
-    ///     let ptr = s.as_ptr();
+    ///
+    // FIXME Update this when vec_into_raw_parts is stabilized
+    ///     // Prevent automatically dropping the String's data
+    ///     let mut s = mem::ManuallyDrop::new(s);
+    ///
+    ///     let ptr = s.as_mut_ptr();
     ///     let len = s.len();
     ///     let capacity = s.capacity();
     ///
-    ///     mem::forget(s);
-    ///
-    ///     let s = String::from_raw_parts(ptr as *mut _, len, capacity);
+    ///     let s = String::from_raw_parts(ptr, len, capacity);
     ///
     ///     assert_eq!(String::from("hello"), s);
     /// }
diff --git a/src/liballoc/sync.rs b/src/liballoc/sync.rs
index 45f98162e4c..80d6c6e0d43 100644
--- a/src/liballoc/sync.rs
+++ b/src/liballoc/sync.rs
@@ -45,10 +45,10 @@ const MAX_REFCOUNT: usize = (isize::MAX) as usize;
 ///
 /// The type `Arc<T>` provides shared ownership of a value of type `T`,
 /// allocated in the heap. Invoking [`clone`][clone] on `Arc` produces
-/// a new `Arc` instance, which points to the same value on the heap as the
+/// a new `Arc` instance, which points to the same allocation on the heap as the
 /// source `Arc`, while increasing a reference count. When the last `Arc`
-/// pointer to a given value is destroyed, the pointed-to value is also
-/// destroyed.
+/// pointer to a given allocation is destroyed, the value stored in that allocation (often
+/// referred to as "inner value") is also dropped.
 ///
 /// Shared references in Rust disallow mutation by default, and `Arc` is no
 /// exception: you cannot generally obtain a mutable reference to something
@@ -61,7 +61,7 @@ const MAX_REFCOUNT: usize = (isize::MAX) as usize;
 /// Unlike [`Rc<T>`], `Arc<T>` uses atomic operations for its reference
 /// counting. This means that it is thread-safe. The disadvantage is that
 /// atomic operations are more expensive than ordinary memory accesses. If you
-/// are not sharing reference-counted values between threads, consider using
+/// are not sharing reference-counted allocations between threads, consider using
 /// [`Rc<T>`] for lower overhead. [`Rc<T>`] is a safe default, because the
 /// compiler will catch any attempt to send an [`Rc<T>`] between threads.
 /// However, a library might choose `Arc<T>` in order to give library consumers
@@ -85,8 +85,10 @@ const MAX_REFCOUNT: usize = (isize::MAX) as usize;
 ///
 /// The [`downgrade`][downgrade] method can be used to create a non-owning
 /// [`Weak`][weak] pointer. A [`Weak`][weak] pointer can be [`upgrade`][upgrade]d
-/// to an `Arc`, but this will return [`None`] if the value has already been
-/// dropped.
+/// to an `Arc`, but this will return [`None`] if the value stored in the allocation has
+/// already been dropped. In other words, `Weak` pointers do not keep the value
+/// inside the allocation alive; however, they *do* keep the allocation
+/// (the backing store for the value) alive.
 ///
 /// A cycle between `Arc` pointers will never be deallocated. For this reason,
 /// [`Weak`][weak] is used to break cycles. For example, a tree could have
@@ -121,8 +123,8 @@ const MAX_REFCOUNT: usize = (isize::MAX) as usize;
 /// Arc::downgrade(&my_arc);
 /// ```
 ///
-/// [`Weak<T>`][weak] does not auto-dereference to `T`, because the value may have
-/// already been destroyed.
+/// [`Weak<T>`][weak] does not auto-dereference to `T`, because the inner value may have
+/// already been dropped.
 ///
 /// [arc]: struct.Arc.html
 /// [weak]: struct.Weak.html
@@ -221,17 +223,18 @@ impl<T: ?Sized> Arc<T> {
 }
 
 /// `Weak` is a version of [`Arc`] that holds a non-owning reference to the
-/// managed value. The value is accessed by calling [`upgrade`] on the `Weak`
+/// managed allocation. The allocation is accessed by calling [`upgrade`] on the `Weak`
 /// pointer, which returns an [`Option`]`<`[`Arc`]`<T>>`.
 ///
 /// Since a `Weak` reference does not count towards ownership, it will not
-/// prevent the inner value from being dropped, and `Weak` itself makes no
-/// guarantees about the value still being present and may return [`None`]
-/// when [`upgrade`]d.
+/// prevent the value stored in the allocation from being dropped, and `Weak` itself makes no
+/// guarantees about the value still being present. Thus it may return [`None`]
+/// when [`upgrade`]d. Note however that a `Weak` reference *does* prevent the allocation
+/// itself (the backing store) from being deallocated.
 ///
-/// A `Weak` pointer is useful for keeping a temporary reference to the value
-/// within [`Arc`] without extending its lifetime. It is also used to prevent
-/// circular references between [`Arc`] pointers, since mutual owning references
+/// A `Weak` pointer is useful for keeping a temporary reference to the allocation
+/// managed by [`Arc`] without preventing its inner value from being dropped. It is also used to
+/// prevent circular references between [`Arc`] pointers, since mutual owning references
 /// would never allow either [`Arc`] to be dropped. For example, a tree could
 /// have strong [`Arc`] pointers from parent nodes to children, and `Weak`
 /// pointers from children back to their parents.
@@ -345,7 +348,7 @@ impl<T> Arc<T> {
         unsafe { Pin::new_unchecked(Arc::new(data)) }
     }
 
-    /// Returns the contained value, if the `Arc` has exactly one strong reference.
+    /// Returns the inner value, if the `Arc` has exactly one strong reference.
     ///
     /// Otherwise, an [`Err`][result] is returned with the same `Arc` that was
     /// passed in.
@@ -426,7 +429,7 @@ impl<T> Arc<mem::MaybeUninit<T>> {
     /// # Safety
     ///
     /// As with [`MaybeUninit::assume_init`],
-    /// it is up to the caller to guarantee that the value
+    /// it is up to the caller to guarantee that the inner value
     /// really is in an initialized state.
     /// Calling this when the content is not yet fully initialized
     /// causes immediate undefined behavior.
@@ -465,7 +468,7 @@ impl<T> Arc<[mem::MaybeUninit<T>]> {
     /// # Safety
     ///
     /// As with [`MaybeUninit::assume_init`],
-    /// it is up to the caller to guarantee that the value
+    /// it is up to the caller to guarantee that the inner value
     /// really is in an initialized state.
     /// Calling this when the content is not yet fully initialized
     /// causes immediate undefined behavior.
@@ -584,7 +587,7 @@ impl<T: ?Sized> Arc<T> {
         unsafe { NonNull::new_unchecked(Arc::into_raw(this) as *mut _) }
     }
 
-    /// Creates a new [`Weak`][weak] pointer to this value.
+    /// Creates a new [`Weak`][weak] pointer to this allocation.
     ///
     /// [weak]: struct.Weak.html
     ///
@@ -628,7 +631,7 @@ impl<T: ?Sized> Arc<T> {
         }
     }
 
-    /// Gets the number of [`Weak`][weak] pointers to this value.
+    /// Gets the number of [`Weak`][weak] pointers to this allocation.
     ///
     /// [weak]: struct.Weak.html
     ///
@@ -659,7 +662,7 @@ impl<T: ?Sized> Arc<T> {
         if cnt == usize::MAX { 0 } else { cnt - 1 }
     }
 
-    /// Gets the number of strong (`Arc`) pointers to this value.
+    /// Gets the number of strong (`Arc`) pointers to this allocation.
     ///
     /// # Safety
     ///
@@ -710,8 +713,8 @@ impl<T: ?Sized> Arc<T> {
 
     #[inline]
     #[stable(feature = "ptr_eq", since = "1.17.0")]
-    /// Returns `true` if the two `Arc`s point to the same value (not
-    /// just values that compare as equal).
+    /// Returns `true` if the two `Arc`s point to the same allocation
+    /// (in a vein similar to [`ptr::eq`]).
     ///
     /// # Examples
     ///
@@ -725,6 +728,8 @@ impl<T: ?Sized> Arc<T> {
     /// assert!(Arc::ptr_eq(&five, &same_five));
     /// assert!(!Arc::ptr_eq(&five, &other_five));
     /// ```
+    ///
+    /// [`ptr::eq`]: ../../std/ptr/fn.eq.html
     pub fn ptr_eq(this: &Self, other: &Self) -> bool {
         this.ptr.as_ptr() == other.ptr.as_ptr()
     }
@@ -732,7 +737,7 @@ impl<T: ?Sized> Arc<T> {
 
 impl<T: ?Sized> Arc<T> {
     /// Allocates an `ArcInner<T>` with sufficient space for
-    /// a possibly-unsized value where the value has the layout provided.
+    /// a possibly-unsized inner value where the value has the layout provided.
     ///
     /// The function `mem_to_arcinner` is called with the data pointer
     /// and must return back a (potentially fat)-pointer for the `ArcInner<T>`.
@@ -761,7 +766,7 @@ impl<T: ?Sized> Arc<T> {
         inner
     }
 
-    /// Allocates an `ArcInner<T>` with sufficient space for an unsized value.
+    /// Allocates an `ArcInner<T>` with sufficient space for an unsized inner value.
     unsafe fn allocate_for_ptr(ptr: *const T) -> *mut ArcInner<T> {
         // Allocate for the `ArcInner<T>` using the given value.
         Self::allocate_for_layout(
@@ -903,7 +908,7 @@ impl<T: Copy> ArcFromSlice<T> for Arc<[T]> {
 impl<T: ?Sized> Clone for Arc<T> {
     /// Makes a clone of the `Arc` pointer.
     ///
-    /// This creates another pointer to the same inner value, increasing the
+    /// This creates another pointer to the same allocation, increasing the
     /// strong reference count.
     ///
     /// # Examples
@@ -965,15 +970,19 @@ impl<T: ?Sized> Receiver for Arc<T> {}
 impl<T: Clone> Arc<T> {
     /// Makes a mutable reference into the given `Arc`.
     ///
-    /// If there are other `Arc` or [`Weak`][weak] pointers to the same value,
-    /// then `make_mut` will invoke [`clone`][clone] on the inner value to
-    /// ensure unique ownership. This is also referred to as clone-on-write.
+    /// If there are other `Arc` or [`Weak`][weak] pointers to the same allocation,
+    /// then `make_mut` will create a new allocation and invoke [`clone`][clone] on the inner value
+    /// to ensure unique ownership. This is also referred to as clone-on-write.
+    ///
+    /// Note that this differs from the behavior of [`Rc::make_mut`] which disassociates
+    /// any remaining `Weak` pointers.
     ///
     /// See also [`get_mut`][get_mut], which will fail rather than cloning.
     ///
     /// [weak]: struct.Weak.html
     /// [clone]: ../../std/clone/trait.Clone.html#tymethod.clone
     /// [get_mut]: struct.Arc.html#method.get_mut
+    /// [`Rc::make_mut`]: ../rc/struct.Rc.html#method.make_mut
     ///
     /// # Examples
     ///
@@ -988,7 +997,7 @@ impl<T: Clone> Arc<T> {
     /// *Arc::make_mut(&mut data) += 1;         // Won't clone anything
     /// *Arc::make_mut(&mut other_data) *= 2;   // Won't clone anything
     ///
-    /// // Now `data` and `other_data` point to different values.
+    /// // Now `data` and `other_data` point to different allocations.
     /// assert_eq!(*data, 8);
     /// assert_eq!(*other_data, 12);
     /// ```
@@ -1048,14 +1057,14 @@ impl<T: Clone> Arc<T> {
 }
 
 impl<T: ?Sized> Arc<T> {
-    /// Returns a mutable reference to the inner value, if there are
-    /// no other `Arc` or [`Weak`][weak] pointers to the same value.
+    /// Returns a mutable reference into the given `Arc`, if there are
+    /// no other `Arc` or [`Weak`][weak] pointers to the same allocation.
     ///
     /// Returns [`None`][option] otherwise, because it is not safe to
     /// mutate a shared value.
     ///
     /// See also [`make_mut`][make_mut], which will [`clone`][clone]
-    /// the inner value when it's shared.
+    /// the inner value when there are other pointers.
     ///
     /// [weak]: struct.Weak.html
     /// [option]: ../../std/option/enum.Option.html
@@ -1091,7 +1100,7 @@ impl<T: ?Sized> Arc<T> {
         }
     }
 
-    /// Returns a mutable reference to the inner value,
+    /// Returns a mutable reference into the given `Arc`,
     /// without any check.
     ///
     /// See also [`get_mut`], which is safe and does appropriate checks.
@@ -1100,7 +1109,7 @@ impl<T: ?Sized> Arc<T> {
     ///
     /// # Safety
     ///
-    /// Any other `Arc` or [`Weak`] pointers to the same value must not be dereferenced
+    /// Any other `Arc` or [`Weak`] pointers to the same allocation must not be dereferenced
     /// for the duration of the returned borrow.
     /// This is trivially the case if no such pointers exist,
     /// for example immediately after `Arc::new`.
@@ -1244,11 +1253,9 @@ impl Arc<dyn Any + Send + Sync> {
     ///     }
     /// }
     ///
-    /// fn main() {
-    ///     let my_string = "Hello World".to_string();
-    ///     print_if_string(Arc::new(my_string));
-    ///     print_if_string(Arc::new(0i8));
-    /// }
+    /// let my_string = "Hello World".to_string();
+    /// print_if_string(Arc::new(my_string));
+    /// print_if_string(Arc::new(0i8));
     /// ```
     pub fn downcast<T>(self) -> Result<Arc<T>, Self>
     where
@@ -1426,10 +1433,10 @@ impl<T> Weak<T> {
 }
 
 impl<T: ?Sized> Weak<T> {
-    /// Attempts to upgrade the `Weak` pointer to an [`Arc`], extending
-    /// the lifetime of the value if successful.
+    /// Attempts to upgrade the `Weak` pointer to an [`Arc`], delaying
+    /// dropping of the inner value if successful.
     ///
-    /// Returns [`None`] if the value has since been dropped.
+    /// Returns [`None`] if the inner value has since been dropped.
     ///
     /// [`Arc`]: struct.Arc.html
     /// [`None`]: ../../std/option/enum.Option.html#variant.None
@@ -1484,7 +1491,7 @@ impl<T: ?Sized> Weak<T> {
         }
     }
 
-    /// Gets the number of strong (`Arc`) pointers pointing to this value.
+    /// Gets the number of strong (`Arc`) pointers pointing to this allocation.
     ///
     /// If `self` was created using [`Weak::new`], this will return 0.
     ///
@@ -1499,17 +1506,17 @@ impl<T: ?Sized> Weak<T> {
     }
 
     /// Gets an approximation of the number of `Weak` pointers pointing to this
-    /// value.
+    /// allocation.
     ///
     /// If `self` was created using [`Weak::new`], this will return 0. If not,
     /// the returned value is at least 1, since `self` still points to the
-    /// value.
+    /// allocation.
     ///
     /// # Accuracy
     ///
     /// Due to implementation details, the returned value can be off by 1 in
     /// either direction when other threads are manipulating any `Arc`s or
-    /// `Weak`s pointing to the same value.
+    /// `Weak`s pointing to the same allocation.
     ///
     /// [`Weak::new`]: #method.new
     #[unstable(feature = "weak_counts", issue = "57977")]
@@ -1550,14 +1557,14 @@ impl<T: ?Sized> Weak<T> {
         }
     }
 
-    /// Returns `true` if the two `Weak`s point to the same value (not just
-    /// values that compare as equal), or if both don't point to any value
+    /// Returns `true` if the two `Weak`s point to the same allocation (similar to
+    /// [`ptr::eq`]), or if both don't point to any allocation
     /// (because they were created with `Weak::new()`).
     ///
     /// # Notes
     ///
     /// Since this compares pointers it means that `Weak::new()` will equal each
-    /// other, even though they don't point to any value.
+    /// other, even though they don't point to any allocation.
     ///
     /// # Examples
     ///
@@ -1589,6 +1596,8 @@ impl<T: ?Sized> Weak<T> {
     /// let third = Arc::downgrade(&third_rc);
     /// assert!(!first.ptr_eq(&third));
     /// ```
+    ///
+    /// [`ptr::eq`]: ../../std/ptr/fn.eq.html
     #[inline]
     #[stable(feature = "weak_ptr_eq", since = "1.39.0")]
     pub fn ptr_eq(&self, other: &Self) -> bool {
@@ -1598,7 +1607,7 @@ impl<T: ?Sized> Weak<T> {
 
 #[stable(feature = "arc_weak", since = "1.4.0")]
 impl<T: ?Sized> Clone for Weak<T> {
-    /// Makes a clone of the `Weak` pointer that points to the same value.
+    /// Makes a clone of the `Weak` pointer that points to the same allocation.
     ///
     /// # Examples
     ///
@@ -1629,7 +1638,7 @@ impl<T: ?Sized> Clone for Weak<T> {
             }
         }
 
-        return Weak { ptr: self.ptr };
+        Weak { ptr: self.ptr }
     }
 }
 
@@ -1728,6 +1737,8 @@ impl<T: ?Sized + PartialEq> ArcEqIdent<T> for Arc<T> {
 /// store large values, that are slow to clone, but also heavy to check for equality, causing this
 /// cost to pay off more easily. It's also more likely to have two `Arc` clones, that point to
 /// the same value, than two `&T`s.
+///
+/// We can only do this when `T: Eq` as a `PartialEq` might be deliberately irreflexive.
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T: ?Sized + Eq> ArcEqIdent<T> for Arc<T> {
     #[inline]
@@ -1745,10 +1756,11 @@ impl<T: ?Sized + Eq> ArcEqIdent<T> for Arc<T> {
 impl<T: ?Sized + PartialEq> PartialEq for Arc<T> {
     /// Equality for two `Arc`s.
     ///
-    /// Two `Arc`s are equal if their inner values are equal.
+    /// Two `Arc`s are equal if their inner values are equal, even if they are
+    /// stored in different allocation.
     ///
-    /// If `T` also implements `Eq`, two `Arc`s that point to the same value are
-    /// always equal.
+    /// If `T` also implements `Eq` (implying reflexivity of equality),
+    /// two `Arc`s that point to the same allocation are always equal.
     ///
     /// # Examples
     ///
@@ -1768,8 +1780,8 @@ impl<T: ?Sized + PartialEq> PartialEq for Arc<T> {
     ///
     /// 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.
+    /// If `T` also implements `Eq` (implying reflexivity of equality),
+    /// two `Arc`s that point to the same value are never unequal.
     ///
     /// # Examples
     ///
diff --git a/src/liballoc/tests/binary_heap.rs b/src/liballoc/tests/binary_heap.rs
index 0685fa943c0..a44cf1eaf6d 100644
--- a/src/liballoc/tests/binary_heap.rs
+++ b/src/liballoc/tests/binary_heap.rs
@@ -1,10 +1,6 @@
-use std::cmp;
 use std::collections::BinaryHeap;
 use std::collections::binary_heap::{Drain, PeekMut};
-use std::panic::{self, AssertUnwindSafe};
-use std::sync::atomic::{AtomicUsize, Ordering};
-
-use rand::{thread_rng, seq::SliceRandom};
+use std::iter::TrustedLen;
 
 #[test]
 fn test_iterator() {
@@ -19,7 +15,7 @@ fn test_iterator() {
 }
 
 #[test]
-fn test_iterator_reverse() {
+fn test_iter_rev_cloned_collect() {
     let data = vec![5, 9, 3];
     let iterout = vec![3, 5, 9];
     let pq = BinaryHeap::from(data);
@@ -29,7 +25,7 @@ fn test_iterator_reverse() {
 }
 
 #[test]
-fn test_move_iter() {
+fn test_into_iter_collect() {
     let data = vec![5, 9, 3];
     let iterout = vec![9, 5, 3];
     let pq = BinaryHeap::from(data);
@@ -39,7 +35,7 @@ fn test_move_iter() {
 }
 
 #[test]
-fn test_move_iter_size_hint() {
+fn test_into_iter_size_hint() {
     let data = vec![5, 9];
     let pq = BinaryHeap::from(data);
 
@@ -56,7 +52,7 @@ fn test_move_iter_size_hint() {
 }
 
 #[test]
-fn test_move_iter_reverse() {
+fn test_into_iter_rev_collect() {
     let data = vec![5, 9, 3];
     let iterout = vec![3, 5, 9];
     let pq = BinaryHeap::from(data);
@@ -66,6 +62,65 @@ fn test_move_iter_reverse() {
 }
 
 #[test]
+fn test_into_iter_sorted_collect() {
+    let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
+    let it = heap.into_iter_sorted();
+    let sorted = it.collect::<Vec<_>>();
+    assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]);
+}
+
+#[test]
+fn test_drain_sorted_collect() {
+    let mut heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
+    let it = heap.drain_sorted();
+    let sorted = it.collect::<Vec<_>>();
+    assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]);
+}
+
+fn check_exact_size_iterator<I: ExactSizeIterator>(len: usize, it: I) {
+    let mut it = it;
+
+    for i in 0..it.len() {
+        let (lower, upper) = it.size_hint();
+        assert_eq!(Some(lower), upper);
+        assert_eq!(lower, len - i);
+        assert_eq!(it.len(), len - i);
+        it.next();
+    }
+    assert_eq!(it.len(), 0);
+    assert!(it.is_empty());
+}
+
+#[test]
+fn test_exact_size_iterator() {
+    let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
+    check_exact_size_iterator(heap.len(), heap.iter());
+    check_exact_size_iterator(heap.len(), heap.clone().into_iter());
+    check_exact_size_iterator(heap.len(), heap.clone().into_iter_sorted());
+    check_exact_size_iterator(heap.len(), heap.clone().drain());
+    check_exact_size_iterator(heap.len(), heap.clone().drain_sorted());
+}
+
+fn check_trusted_len<I: TrustedLen>(len: usize, it: I) {
+    let mut it = it;
+    for i in 0..len {
+        let (lower, upper) = it.size_hint();
+        if upper.is_some() {
+            assert_eq!(Some(lower), upper);
+            assert_eq!(lower, len - i);
+        }
+        it.next();
+    }
+}
+
+#[test]
+fn test_trusted_len() {
+    let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
+    check_trusted_len(heap.len(), heap.clone().into_iter_sorted());
+    check_trusted_len(heap.len(), heap.clone().drain_sorted());
+}
+
+#[test]
 fn test_peek_and_pop() {
     let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
     let mut sorted = data.clone();
@@ -212,6 +267,15 @@ fn test_drain() {
 }
 
 #[test]
+fn test_drain_sorted() {
+    let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
+
+    assert_eq!(q.drain_sorted().take(5).collect::<Vec<_>>(), vec![9, 8, 7, 6, 5]);
+
+    assert!(q.is_empty());
+}
+
+#[test]
 fn test_extend_ref() {
     let mut a = BinaryHeap::new();
     a.push(1);
@@ -281,9 +345,15 @@ fn assert_covariance() {
 // even if the order may not be correct.
 //
 // Destructors must be called exactly once per element.
+// FIXME: re-enable emscripten once it can unwind again
 #[test]
-#[cfg(not(miri))] // Miri does not support catching panics
+#[cfg(not(any(miri, target_os = "emscripten")))] // Miri does not support catching panics
 fn panic_safe() {
+    use std::cmp;
+    use std::panic::{self, AssertUnwindSafe};
+    use std::sync::atomic::{AtomicUsize, Ordering};
+    use rand::{thread_rng, seq::SliceRandom};
+
     static DROP_COUNTER: AtomicUsize = AtomicUsize::new(0);
 
     #[derive(Eq, PartialEq, Ord, Clone, Debug)]
diff --git a/src/liballoc/tests/boxed.rs b/src/liballoc/tests/boxed.rs
new file mode 100644
index 00000000000..bc3d53bf30d
--- /dev/null
+++ b/src/liballoc/tests/boxed.rs
@@ -0,0 +1,18 @@
+use std::ptr::NonNull;
+use std::mem::MaybeUninit;
+
+#[test]
+fn unitialized_zero_size_box() {
+    assert_eq!(
+        &*Box::<()>::new_uninit() as *const _,
+        NonNull::<MaybeUninit<()>>::dangling().as_ptr(),
+    );
+    assert_eq!(
+        Box::<[()]>::new_uninit_slice(4).as_ptr(),
+        NonNull::<MaybeUninit<()>>::dangling().as_ptr(),
+    );
+    assert_eq!(
+        Box::<[String]>::new_uninit_slice(0).as_ptr(),
+        NonNull::<MaybeUninit<String>>::dangling().as_ptr(),
+    );
+}
diff --git a/src/liballoc/tests/btree/set.rs b/src/liballoc/tests/btree/set.rs
index 35db18c39c8..e4883abc8b5 100644
--- a/src/liballoc/tests/btree/set.rs
+++ b/src/liballoc/tests/btree/set.rs
@@ -48,7 +48,9 @@ fn check<F>(a: &[i32], b: &[i32], expected: &[i32], f: F)
     f(&set_a,
       &set_b,
       &mut |&x| {
-          assert_eq!(x, expected[i]);
+          if i < expected.len() {
+              assert_eq!(x, expected[i]);
+          }
           i += 1;
           true
       });
@@ -74,20 +76,20 @@ fn test_intersection() {
         return;
     }
 
-    let large = (0..1000).collect::<Vec<_>>();
+    let large = (0..100).collect::<Vec<_>>();
     check_intersection(&[], &large, &[]);
     check_intersection(&large, &[], &[]);
     check_intersection(&[-1], &large, &[]);
     check_intersection(&large, &[-1], &[]);
     check_intersection(&[0], &large, &[0]);
     check_intersection(&large, &[0], &[0]);
-    check_intersection(&[999], &large, &[999]);
-    check_intersection(&large, &[999], &[999]);
-    check_intersection(&[1000], &large, &[]);
-    check_intersection(&large, &[1000], &[]);
-    check_intersection(&[11, 5000, 1, 3, 77, 8924, 103],
+    check_intersection(&[99], &large, &[99]);
+    check_intersection(&large, &[99], &[99]);
+    check_intersection(&[100], &large, &[]);
+    check_intersection(&large, &[100], &[]);
+    check_intersection(&[11, 5000, 1, 3, 77, 8924],
                        &large,
-                       &[1, 3, 11, 77, 103]);
+                       &[1, 3, 11, 77]);
 }
 
 #[test]
@@ -95,10 +97,15 @@ fn test_intersection_size_hint() {
     let x: BTreeSet<i32> = [3, 4].iter().copied().collect();
     let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
     let mut iter = x.intersection(&y);
-    assert_eq!(iter.size_hint(), (0, Some(2)));
+    assert_eq!(iter.size_hint(), (1, Some(1)));
     assert_eq!(iter.next(), Some(&3));
     assert_eq!(iter.size_hint(), (0, Some(0)));
     assert_eq!(iter.next(), None);
+
+    iter = y.intersection(&y);
+    assert_eq!(iter.size_hint(), (0, Some(3)));
+    assert_eq!(iter.next(), Some(&1));
+    assert_eq!(iter.size_hint(), (0, Some(2)));
 }
 
 #[test]
@@ -111,6 +118,9 @@ fn test_difference() {
     check_difference(&[1, 12], &[], &[1, 12]);
     check_difference(&[], &[1, 2, 3, 9], &[]);
     check_difference(&[1, 3, 5, 9, 11], &[3, 9], &[1, 5, 11]);
+    check_difference(&[1, 3, 5, 9, 11], &[3, 6, 9], &[1, 5, 11]);
+    check_difference(&[1, 3, 5, 9, 11], &[0, 1], &[3, 5, 9, 11]);
+    check_difference(&[1, 3, 5, 9, 11], &[11, 12], &[1, 3, 5, 9]);
     check_difference(&[-5, 11, 22, 33, 40, 42],
                      &[-12, -5, 14, 23, 34, 38, 39, 50],
                      &[11, 22, 33, 40, 42]);
@@ -119,18 +129,82 @@ fn test_difference() {
         return;
     }
 
-    let large = (0..1000).collect::<Vec<_>>();
+    let large = (0..100).collect::<Vec<_>>();
     check_difference(&[], &large, &[]);
     check_difference(&[-1], &large, &[-1]);
     check_difference(&[0], &large, &[]);
-    check_difference(&[999], &large, &[]);
-    check_difference(&[1000], &large, &[1000]);
-    check_difference(&[11, 5000, 1, 3, 77, 8924, 103],
+    check_difference(&[99], &large, &[]);
+    check_difference(&[100], &large, &[100]);
+    check_difference(&[11, 5000, 1, 3, 77, 8924],
                      &large,
                      &[5000, 8924]);
     check_difference(&large, &[], &large);
     check_difference(&large, &[-1], &large);
-    check_difference(&large, &[1000], &large);
+    check_difference(&large, &[100], &large);
+}
+
+#[test]
+fn test_difference_size_hint() {
+    let s246: BTreeSet<i32> = [2, 4, 6].iter().copied().collect();
+    let s23456: BTreeSet<i32> = (2..=6).collect();
+    let mut iter = s246.difference(&s23456);
+    assert_eq!(iter.size_hint(), (0, Some(3)));
+    assert_eq!(iter.next(), None);
+
+    let s12345: BTreeSet<i32> = (1..=5).collect();
+    iter = s246.difference(&s12345);
+    assert_eq!(iter.size_hint(), (0, Some(3)));
+    assert_eq!(iter.next(), Some(&6));
+    assert_eq!(iter.size_hint(), (0, Some(0)));
+    assert_eq!(iter.next(), None);
+
+    let s34567: BTreeSet<i32> = (3..=7).collect();
+    iter = s246.difference(&s34567);
+    assert_eq!(iter.size_hint(), (0, Some(3)));
+    assert_eq!(iter.next(), Some(&2));
+    assert_eq!(iter.size_hint(), (0, Some(2)));
+    assert_eq!(iter.next(), None);
+
+    let s1: BTreeSet<i32> = (-9..=1).collect();
+    iter = s246.difference(&s1);
+    assert_eq!(iter.size_hint(), (3, Some(3)));
+
+    let s2: BTreeSet<i32> = (-9..=2).collect();
+    iter = s246.difference(&s2);
+    assert_eq!(iter.size_hint(), (2, Some(2)));
+    assert_eq!(iter.next(), Some(&4));
+    assert_eq!(iter.size_hint(), (1, Some(1)));
+
+    let s23: BTreeSet<i32> = (2..=3).collect();
+    iter = s246.difference(&s23);
+    assert_eq!(iter.size_hint(), (1, Some(3)));
+    assert_eq!(iter.next(), Some(&4));
+    assert_eq!(iter.size_hint(), (1, Some(1)));
+
+    let s4: BTreeSet<i32> = (4..=4).collect();
+    iter = s246.difference(&s4);
+    assert_eq!(iter.size_hint(), (2, Some(3)));
+    assert_eq!(iter.next(), Some(&2));
+    assert_eq!(iter.size_hint(), (1, Some(2)));
+    assert_eq!(iter.next(), Some(&6));
+    assert_eq!(iter.size_hint(), (0, Some(0)));
+    assert_eq!(iter.next(), None);
+
+    let s56: BTreeSet<i32> = (5..=6).collect();
+    iter = s246.difference(&s56);
+    assert_eq!(iter.size_hint(), (1, Some(3)));
+    assert_eq!(iter.next(), Some(&2));
+    assert_eq!(iter.size_hint(), (0, Some(2)));
+
+    let s6: BTreeSet<i32> = (6..=19).collect();
+    iter = s246.difference(&s6);
+    assert_eq!(iter.size_hint(), (2, Some(2)));
+    assert_eq!(iter.next(), Some(&2));
+    assert_eq!(iter.size_hint(), (1, Some(1)));
+
+    let s7: BTreeSet<i32> = (7..=19).collect();
+    iter = s246.difference(&s7);
+    assert_eq!(iter.size_hint(), (3, Some(3)));
 }
 
 #[test]
@@ -148,6 +222,18 @@ fn test_symmetric_difference() {
 }
 
 #[test]
+fn test_symmetric_difference_size_hint() {
+    let x: BTreeSet<i32> = [2, 4].iter().copied().collect();
+    let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
+    let mut iter = x.symmetric_difference(&y);
+    assert_eq!(iter.size_hint(), (0, Some(5)));
+    assert_eq!(iter.next(), Some(&1));
+    assert_eq!(iter.size_hint(), (0, Some(4)));
+    assert_eq!(iter.next(), Some(&3));
+    assert_eq!(iter.size_hint(), (0, Some(1)));
+}
+
+#[test]
 fn test_union() {
     fn check_union(a: &[i32], b: &[i32], expected: &[i32]) {
         check(a, b, expected, |x, y, f| x.union(y).all(f))
@@ -162,6 +248,18 @@ fn test_union() {
 }
 
 #[test]
+fn test_union_size_hint() {
+    let x: BTreeSet<i32> = [2, 4].iter().copied().collect();
+    let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
+    let mut iter = x.union(&y);
+    assert_eq!(iter.size_hint(), (3, Some(5)));
+    assert_eq!(iter.next(), Some(&1));
+    assert_eq!(iter.size_hint(), (2, Some(4)));
+    assert_eq!(iter.next(), Some(&2));
+    assert_eq!(iter.size_hint(), (1, Some(2)));
+}
+
+#[test]
 // Only tests the simple function definition with respect to intersection
 fn test_is_disjoint() {
     let one = [1].iter().collect::<BTreeSet<_>>();
@@ -170,7 +268,7 @@ fn test_is_disjoint() {
 }
 
 #[test]
-// Also tests the trivial function definition of is_superset
+// Also implicitly tests the trivial function definition of is_superset
 fn test_is_subset() {
     fn is_subset(a: &[i32], b: &[i32]) -> bool {
         let set_a = a.iter().collect::<BTreeSet<_>>();
@@ -188,23 +286,23 @@ fn test_is_subset() {
     assert_eq!(is_subset(&[1, 2], &[1, 2]), true);
     assert_eq!(is_subset(&[1, 2], &[2, 3]), false);
     assert_eq!(is_subset(&[-5, 11, 22, 33, 40, 42],
-                         &[-12, -5, 14, 23, 11, 34, 22, 38, 33, 42, 39, 40]),
+                         &[-12, -5, 11, 14, 22, 23, 33, 34, 38, 39, 40, 42]),
                true);
     assert_eq!(is_subset(&[-5, 11, 22, 33, 40, 42],
-                         &[-12, -5, 14, 23, 34, 38, 22, 11]),
+                         &[-12, -5, 11, 14, 22, 23, 34, 38]),
                false);
 
     if cfg!(miri) { // Miri is too slow
         return;
     }
 
-    let large = (0..1000).collect::<Vec<_>>();
+    let large = (0..100).collect::<Vec<_>>();
     assert_eq!(is_subset(&[], &large), true);
     assert_eq!(is_subset(&large, &[]), false);
     assert_eq!(is_subset(&[-1], &large), false);
     assert_eq!(is_subset(&[0], &large), true);
     assert_eq!(is_subset(&[1, 2], &large), true);
-    assert_eq!(is_subset(&[999, 1000], &large), false);
+    assert_eq!(is_subset(&[99, 100], &large), false);
 }
 
 #[test]
diff --git a/src/liballoc/tests/lib.rs b/src/liballoc/tests/lib.rs
index 5723a30c0f3..3273feb7b5d 100644
--- a/src/liballoc/tests/lib.rs
+++ b/src/liballoc/tests/lib.rs
@@ -2,19 +2,21 @@
 #![feature(box_syntax)]
 #![feature(drain_filter)]
 #![feature(exact_size_is_empty)]
-#![feature(option_flattening)]
+#![feature(new_uninit)]
 #![feature(pattern)]
-#![feature(repeat_generic_slice)]
 #![feature(trusted_len)]
 #![feature(try_reserve)]
 #![feature(unboxed_closures)]
 #![feature(associated_type_bounds)]
+#![feature(binary_heap_into_iter_sorted)]
+#![feature(binary_heap_drain_sorted)]
 
 use std::hash::{Hash, Hasher};
 use std::collections::hash_map::DefaultHasher;
 
 mod arc;
 mod binary_heap;
+mod boxed;
 mod btree;
 mod cow_str;
 mod fmt;
diff --git a/src/liballoc/tests/str.rs b/src/liballoc/tests/str.rs
index 4332b2e90fd..cb73c7c179c 100644
--- a/src/liballoc/tests/str.rs
+++ b/src/liballoc/tests/str.rs
@@ -483,7 +483,7 @@ mod slice_index {
     }
 
     #[test]
-    #[cfg(not(target_arch = "asmjs"))] // hits an OOM
+    #[cfg(not(target_os = "emscripten"))] // hits an OOM
     #[cfg(not(miri))] // Miri is too slow
     fn simple_big() {
         fn a_million_letter_x() -> String {
diff --git a/src/liballoc/tests/vec.rs b/src/liballoc/tests/vec.rs
index 29a22aa0315..80537217697 100644
--- a/src/liballoc/tests/vec.rs
+++ b/src/liballoc/tests/vec.rs
@@ -944,8 +944,10 @@ fn drain_filter_complex() {
     }
 }
 
+// Miri does not support catching panics
+// FIXME: re-enable emscripten once it can unwind again
 #[test]
-#[cfg(not(miri))] // Miri does not support catching panics
+#[cfg(not(any(miri, target_os = "emscripten")))]
 fn drain_filter_consumed_panic() {
     use std::rc::Rc;
     use std::sync::Mutex;
@@ -995,8 +997,9 @@ fn drain_filter_consumed_panic() {
     }
 }
 
+// FIXME: Re-enable emscripten once it can catch panics
 #[test]
-#[cfg(not(miri))] // Miri does not support catching panics
+#[cfg(not(any(miri, target_os = "emscripten")))] // Miri does not support catching panics
 fn drain_filter_unconsumed_panic() {
     use std::rc::Rc;
     use std::sync::Mutex;
@@ -1281,3 +1284,51 @@ fn test_stable_push_pop() {
     v.pop().unwrap();
     assert_eq!(*v0, 13);
 }
+
+// https://github.com/rust-lang/rust/pull/49496 introduced specialization based on:
+//
+// ```
+// unsafe impl<T: ?Sized> IsZero for *mut T {
+//     fn is_zero(&self) -> bool {
+//         (*self).is_null()
+//     }
+// }
+// ```
+//
+// … to call `RawVec::with_capacity_zeroed` for creating `Vec<*mut T>`,
+// which is incorrect for fat pointers since `<*mut T>::is_null` only looks at the data component.
+// That is, a fat pointer can be “null” without being made entirely of zero bits.
+#[test]
+fn vec_macro_repeating_null_raw_fat_pointer() {
+    let raw_dyn = &mut (|| ()) as &mut dyn Fn() as *mut dyn Fn();
+    let vtable = dbg!(ptr_metadata(raw_dyn));
+    let null_raw_dyn = ptr_from_raw_parts(std::ptr::null_mut(), vtable);
+    assert!(null_raw_dyn.is_null());
+
+    let vec = vec![null_raw_dyn; 1];
+    dbg!(ptr_metadata(vec[0]));
+    assert!(vec[0] == null_raw_dyn);
+
+    // Polyfill for https://github.com/rust-lang/rfcs/pull/2580
+
+    fn ptr_metadata(ptr: *mut dyn Fn()) -> *mut () {
+        unsafe {
+            std::mem::transmute::<*mut dyn Fn(), DynRepr>(ptr).vtable
+        }
+    }
+
+    fn ptr_from_raw_parts(data: *mut (), vtable: *mut()) -> *mut dyn Fn() {
+        unsafe {
+            std::mem::transmute::<DynRepr, *mut dyn Fn()>(DynRepr {
+                data,
+                vtable
+            })
+        }
+    }
+
+    #[repr(C)]
+    struct DynRepr {
+        data: *mut (),
+        vtable: *mut (),
+    }
+}
diff --git a/src/liballoc/vec.rs b/src/liballoc/vec.rs
index e5672f8542f..5b53a6a2899 100644
--- a/src/liballoc/vec.rs
+++ b/src/liballoc/vec.rs
@@ -154,8 +154,8 @@ use crate::raw_vec::RawVec;
 /// println!("{}", v[6]); // it will panic!
 /// ```
 ///
-/// In conclusion: always check if the index you want to get really exists
-/// before doing it.
+/// Use [`get`] and [`get_mut`] if you want to check whether the index is in
+/// the `Vec`.
 ///
 /// # Slicing
 ///
@@ -277,6 +277,8 @@ use crate::raw_vec::RawVec;
 /// The order has changed in the past and may change again.
 ///
 /// [`vec!`]: ../../std/macro.vec.html
+/// [`get`]: ../../std/vec/struct.Vec.html#method.get
+/// [`get_mut`]: ../../std/vec/struct.Vec.html#method.get_mut
 /// [`Index`]: ../../std/ops/trait.Index.html
 /// [`String`]: ../../std/string/struct.String.html
 /// [`&str`]: ../../std/primitive.str.html
@@ -358,6 +360,44 @@ impl<T> Vec<T> {
         }
     }
 
+    /// Decomposes a `Vec<T>` into its raw components.
+    ///
+    /// Returns the raw pointer to the underlying data, the length of
+    /// the vector (in elements), and the allocated capacity of the
+    /// data (in elements). These are the same arguments in the same
+    /// order as the arguments to [`from_raw_parts`].
+    ///
+    /// After calling this function, the caller is responsible for the
+    /// memory previously managed by the `Vec`. The only way to do
+    /// this is to convert the raw pointer, length, and capacity back
+    /// into a `Vec` with the [`from_raw_parts`] function, allowing
+    /// the destructor to perform the cleanup.
+    ///
+    /// [`from_raw_parts`]: #method.from_raw_parts
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(vec_into_raw_parts)]
+    /// let v: Vec<i32> = vec![-1, 0, 1];
+    ///
+    /// let (ptr, len, cap) = v.into_raw_parts();
+    ///
+    /// let rebuilt = unsafe {
+    ///     // We can now make changes to the components, such as
+    ///     // transmuting the raw pointer to a compatible type.
+    ///     let ptr = ptr as *mut u32;
+    ///
+    ///     Vec::from_raw_parts(ptr, len, cap)
+    /// };
+    /// assert_eq!(rebuilt, [4294967295, 0, 1]);
+    /// ```
+    #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")]
+    pub fn into_raw_parts(self) -> (*mut T, usize, usize) {
+        let mut me = mem::ManuallyDrop::new(self);
+        (me.as_mut_ptr(), me.len(), me.capacity())
+    }
+
     /// Creates a `Vec<T>` directly from the raw components of another vector.
     ///
     /// # Safety
@@ -373,7 +413,11 @@ impl<T> Vec<T> {
     ///
     /// Violating these may cause problems like corrupting the allocator's
     /// internal data structures. For example it is **not** safe
-    /// to build a `Vec<u8>` from a pointer to a C `char` array and a `size_t`.
+    /// to build a `Vec<u8>` from a pointer to a C `char` array with length `size_t`.
+    /// It's also not safe to build one from a `Vec<u16>` and its length, because
+    /// the allocator cares about the alignment, and these two types have different
+    /// alignments. The buffer was allocated with alignment 2 (for `u16`), but after
+    /// turning it into a `Vec<u8>` it'll be deallocated with alignment 1.
     ///
     /// The ownership of `ptr` is effectively transferred to the
     /// `Vec<T>` which may then deallocate, reallocate or change the
@@ -389,28 +433,27 @@ impl<T> Vec<T> {
     /// use std::ptr;
     /// use std::mem;
     ///
-    /// fn main() {
-    ///     let mut v = vec![1, 2, 3];
-    ///
-    ///     // Pull out the various important pieces of information about `v`
-    ///     let p = v.as_mut_ptr();
-    ///     let len = v.len();
-    ///     let cap = v.capacity();
+    /// let v = vec![1, 2, 3];
     ///
-    ///     unsafe {
-    ///         // Cast `v` into the void: no destructor run, so we are in
-    ///         // complete control of the allocation to which `p` points.
-    ///         mem::forget(v);
+    // FIXME Update this when vec_into_raw_parts is stabilized
+    /// // Prevent running `v`'s destructor so we are in complete control
+    /// // of the allocation.
+    /// let mut v = mem::ManuallyDrop::new(v);
     ///
-    ///         // Overwrite memory with 4, 5, 6
-    ///         for i in 0..len as isize {
-    ///             ptr::write(p.offset(i), 4 + i);
-    ///         }
+    /// // Pull out the various important pieces of information about `v`
+    /// let p = v.as_mut_ptr();
+    /// let len = v.len();
+    /// let cap = v.capacity();
     ///
-    ///         // Put everything back together into a Vec
-    ///         let rebuilt = Vec::from_raw_parts(p, len, cap);
-    ///         assert_eq!(rebuilt, [4, 5, 6]);
+    /// unsafe {
+    ///     // Overwrite memory with 4, 5, 6
+    ///     for i in 0..len as isize {
+    ///         ptr::write(p.offset(i), 4 + i);
     ///     }
+    ///
+    ///     // Put everything back together into a Vec
+    ///     let rebuilt = Vec::from_raw_parts(p, len, cap);
+    ///     assert_eq!(rebuilt, [4, 5, 6]);
     /// }
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
@@ -1391,12 +1434,10 @@ impl<T> Vec<T> {
     /// ```
     /// #![feature(vec_leak)]
     ///
-    /// fn main() {
-    ///     let x = vec![1, 2, 3];
-    ///     let static_ref: &'static mut [usize] = Vec::leak(x);
-    ///     static_ref[0] += 1;
-    ///     assert_eq!(static_ref, &[2, 2, 3]);
-    /// }
+    /// let x = vec![1, 2, 3];
+    /// let static_ref: &'static mut [usize] = Vec::leak(x);
+    /// static_ref[0] += 1;
+    /// assert_eq!(static_ref, &[2, 2, 3]);
     /// ```
     #[unstable(feature = "vec_leak", issue = "62195")]
     #[inline]
@@ -1734,20 +1775,45 @@ impl_is_zero!(char, |x| x == '\0');
 impl_is_zero!(f32, |x: f32| x.to_bits() == 0);
 impl_is_zero!(f64, |x: f64| x.to_bits() == 0);
 
-unsafe impl<T: ?Sized> IsZero for *const T {
+unsafe impl<T> IsZero for *const T {
     #[inline]
     fn is_zero(&self) -> bool {
         (*self).is_null()
     }
 }
 
-unsafe impl<T: ?Sized> IsZero for *mut T {
+unsafe impl<T> IsZero for *mut T {
     #[inline]
     fn is_zero(&self) -> bool {
         (*self).is_null()
     }
 }
 
+// `Option<&T>`, `Option<&mut T>` and `Option<Box<T>>` are guaranteed to represent `None` as null.
+// For fat pointers, the bytes that would be the pointer metadata in the `Some` variant
+// are padding in the `None` variant, so ignoring them and zero-initializing instead is ok.
+
+unsafe impl<T: ?Sized> IsZero for Option<&T> {
+    #[inline]
+    fn is_zero(&self) -> bool {
+        self.is_none()
+    }
+}
+
+unsafe impl<T: ?Sized> IsZero for Option<&mut T> {
+    #[inline]
+    fn is_zero(&self) -> bool {
+        self.is_none()
+    }
+}
+
+unsafe impl<T: ?Sized> IsZero for Option<Box<T>> {
+    #[inline]
+    fn is_zero(&self) -> bool {
+        self.is_none()
+    }
+}
+
 
 ////////////////////////////////////////////////////////////////////////////////
 // Common trait implementations for Vec