Merge branch 'master' into remove-in-place-alloc

14 files changed, 191 insertions, 238 deletions

diff --git a/library/alloc/src/boxed.rs b/library/alloc/src/boxed.rs
index cae98f8c76f..cff219ec29d 100644
--- a/library/alloc/src/boxed.rs
+++ b/library/alloc/src/boxed.rs
@@ -143,7 +143,7 @@ use core::ops::{
     CoerceUnsized, Deref, DerefMut, DispatchFromDyn, Generator, GeneratorState, Receiver,
 };
 use core::pin::Pin;
-use core::ptr::{self, NonNull, Unique};
+use core::ptr::{self, Unique};
 use core::task::{Context, Poll};
 
 use crate::alloc::{self, AllocRef, Global};
@@ -448,50 +448,6 @@ impl<T: ?Sized> Box<T> {
         Box::leak(b) as *mut T
     }
 
-    /// Consumes the `Box`, returning the wrapped pointer as `NonNull<T>`.
-    ///
-    /// After calling this function, the caller is responsible for the
-    /// memory previously managed by the `Box`. In particular, the
-    /// caller should properly destroy `T` and release the memory. The
-    /// easiest way to do so is to convert the `NonNull<T>` pointer
-    /// into a raw pointer and back into a `Box` with the [`Box::from_raw`]
-    /// function.
-    ///
-    /// Note: this is an associated function, which means that you have
-    /// to call it as `Box::into_raw_non_null(b)`
-    /// instead of `b.into_raw_non_null()`. This
-    /// is so that there is no conflict with a method on the inner type.
-    ///
-    /// [`Box::from_raw`]: struct.Box.html#method.from_raw
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// #![feature(box_into_raw_non_null)]
-    /// #![allow(deprecated)]
-    ///
-    /// 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()) };
-    /// ```
-    #[unstable(feature = "box_into_raw_non_null", issue = "47336")]
-    #[rustc_deprecated(
-        since = "1.44.0",
-        reason = "use `Box::leak(b).into()` or `NonNull::from(Box::leak(b))` instead"
-    )]
-    #[inline]
-    pub fn into_raw_non_null(b: Box<T>) -> NonNull<T> {
-        // Box is recognized as a "unique pointer" by Stacked Borrows, but internally it is a
-        // raw pointer for the type system. Turning it directly into a raw pointer would not be
-        // recognized as "releasing" the unique pointer to permit aliased raw accesses,
-        // so all raw pointer methods go through `leak` which creates a (unique)
-        // mutable reference. Turning *that* to a raw pointer behaves correctly.
-        Box::leak(b).into()
-    }
-
     #[unstable(
         feature = "ptr_internals",
         issue = "none",
diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs
index 24d1f61fa68..6184051316e 100644
--- a/library/alloc/src/collections/btree/map.rs
+++ b/library/alloc/src/collections/btree/map.rs
@@ -174,7 +174,7 @@ impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
 
                     {
                         let out_root = BTreeMap::ensure_is_owned(&mut out_tree.root);
-                        let mut out_node = out_root.push_level();
+                        let mut out_node = out_root.push_internal_level();
                         let mut in_edge = internal.first_edge();
                         while let Ok(kv) = in_edge.right_kv() {
                             let (k, v) = kv.into_kv();
@@ -1080,9 +1080,9 @@ impl<K: Ord, V> BTreeMap<K, V> {
                                 test_node = parent.forget_type();
                             }
                         }
-                        Err(node) => {
+                        Err(_) => {
                             // We are at the top, create a new root node and push there.
-                            open_node = node.into_root_mut().push_level();
+                            open_node = root.push_internal_level();
                             break;
                         }
                     }
@@ -1092,7 +1092,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
                 let tree_height = open_node.height() - 1;
                 let mut right_tree = node::Root::new_leaf();
                 for _ in 0..tree_height {
-                    right_tree.push_level();
+                    right_tree.push_internal_level();
                 }
                 open_node.push(key, value, right_tree);
 
@@ -1171,7 +1171,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
         let mut right = Self::new();
         let right_root = Self::ensure_is_owned(&mut right.root);
         for _ in 0..left_root.height() {
-            right_root.push_level();
+            right_root.push_internal_level();
         }
 
         {
@@ -1255,7 +1255,11 @@ impl<K: Ord, V> BTreeMap<K, V> {
     }
     pub(super) fn drain_filter_inner(&mut self) -> DrainFilterInner<'_, K, V> {
         let front = self.root.as_mut().map(|r| r.as_mut().first_leaf_edge());
-        DrainFilterInner { length: &mut self.length, cur_leaf_edge: front }
+        DrainFilterInner {
+            length: &mut self.length,
+            cur_leaf_edge: front,
+            emptied_internal_root: false,
+        }
     }
 
     /// Calculates the number of elements if it is incorrect.
@@ -1625,6 +1629,7 @@ where
 pub(super) struct DrainFilterInner<'a, K: 'a, V: 'a> {
     length: &'a mut usize,
     cur_leaf_edge: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>,
+    emptied_internal_root: bool,
 }
 
 #[unstable(feature = "btree_drain_filter", issue = "70530")]
@@ -1665,6 +1670,17 @@ where
     }
 }
 
+impl<K, V> Drop for DrainFilterInner<'_, K, V> {
+    fn drop(&mut self) {
+        if self.emptied_internal_root {
+            if let Some(handle) = self.cur_leaf_edge.take() {
+                let root = handle.into_node().into_root_mut();
+                root.pop_internal_level();
+            }
+        }
+    }
+}
+
 impl<'a, K: 'a, V: 'a> DrainFilterInner<'a, K, V> {
     /// Allow Debug implementations to predict the next element.
     pub(super) fn peek(&self) -> Option<(&K, &V)> {
@@ -1681,9 +1697,10 @@ impl<'a, K: 'a, V: 'a> DrainFilterInner<'a, K, V> {
             let (k, v) = kv.kv_mut();
             if pred(k, v) {
                 *self.length -= 1;
-                let (k, v, leaf_edge_location) = kv.remove_kv_tracking();
-                self.cur_leaf_edge = Some(leaf_edge_location);
-                return Some((k, v));
+                let RemoveResult { old_kv, pos, emptied_internal_root } = kv.remove_kv_tracking();
+                self.cur_leaf_edge = Some(pos);
+                self.emptied_internal_root |= emptied_internal_root;
+                return Some(old_kv);
             }
             self.cur_leaf_edge = Some(kv.next_leaf_edge());
         }
@@ -2477,7 +2494,7 @@ impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
                     }
                 },
                 Err(root) => {
-                    root.push_level().push(ins_k, ins_v, ins_edge);
+                    root.push_internal_level().push(ins_k, ins_v, ins_edge);
                     return unsafe { &mut *out_ptr };
                 }
             }
@@ -2647,20 +2664,35 @@ impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
         self.remove_kv().1
     }
 
+    // Body of `remove_entry`, separate to keep the above implementations short.
     fn remove_kv(self) -> (K, V) {
         *self.length -= 1;
 
-        let (old_key, old_val, _) = self.handle.remove_kv_tracking();
-        (old_key, old_val)
+        let RemoveResult { old_kv, pos, emptied_internal_root } = self.handle.remove_kv_tracking();
+        let root = pos.into_node().into_root_mut();
+        if emptied_internal_root {
+            root.pop_internal_level();
+        }
+        old_kv
     }
 }
 
+struct RemoveResult<'a, K, V> {
+    // Key and value removed.
+    old_kv: (K, V),
+    // Unique location at the leaf level that the removed KV lopgically collapsed into.
+    pos: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
+    // Whether the remove left behind and empty internal root node, that should be removed
+    // using `pop_internal_level`.
+    emptied_internal_root: bool,
+}
+
 impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV> {
-    /// Removes a key/value-pair from the map, and returns that pair, as well as
-    /// the leaf edge corresponding to that former pair.
-    fn remove_kv_tracking(
-        self,
-    ) -> (K, V, Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) {
+    /// Removes a key/value-pair from the tree, and returns that pair, as well as
+    /// the leaf edge corresponding to that former pair. It's possible this leaves
+    /// an empty internal root node, which the caller should subsequently pop from
+    /// the map holding the tree. The caller should also decrement the map's length.
+    fn remove_kv_tracking(self) -> RemoveResult<'a, K, V> {
         let (mut pos, old_key, old_val, was_internal) = match self.force() {
             Leaf(leaf) => {
                 let (hole, old_key, old_val) = leaf.remove();
@@ -2689,6 +2721,7 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInter
         };
 
         // Handle underflow
+        let mut emptied_internal_root = false;
         let mut cur_node = unsafe { ptr::read(&pos).into_node().forget_type() };
         let mut at_leaf = true;
         while cur_node.len() < node::MIN_LEN {
@@ -2709,8 +2742,8 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInter
 
                     let parent = edge.into_node();
                     if parent.len() == 0 {
-                        // We must be at the root
-                        parent.into_root_mut().pop_level();
+                        // This empty parent must be the root, and should be popped off the tree.
+                        emptied_internal_root = true;
                         break;
                     } else {
                         cur_node = parent.forget_type();
@@ -2737,7 +2770,7 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInter
             pos = unsafe { unwrap_unchecked(pos.next_kv().ok()).next_leaf_edge() };
         }
 
-        (old_key, old_val, pos)
+        RemoveResult { old_kv: (old_key, old_val), pos, emptied_internal_root }
     }
 }
 
@@ -2745,7 +2778,7 @@ impl<K, V> node::Root<K, V> {
     /// Removes empty levels on the top, but keep an empty leaf if the entire tree is empty.
     fn fix_top(&mut self) {
         while self.height() > 0 && self.as_ref().len() == 0 {
-            self.pop_level();
+            self.pop_internal_level();
         }
     }
 
@@ -2817,8 +2850,16 @@ fn handle_underfull_node<K, V>(
     let (is_left, mut handle) = match parent.left_kv() {
         Ok(left) => (true, left),
         Err(parent) => {
-            let right = unsafe { unwrap_unchecked(parent.right_kv().ok()) };
-            (false, right)
+            match parent.right_kv() {
+                Ok(right) => (false, right),
+                Err(_) => {
+                    // The underfull node has an empty parent, so it is the only child
+                    // of an empty root. It is destined to become the new root, thus
+                    // allowed to be underfull. The empty parent should be removed later
+                    // by `pop_internal_level`.
+                    return AtRoot;
+                }
+            }
         }
     };
 
diff --git a/library/alloc/src/collections/btree/navigate.rs b/library/alloc/src/collections/btree/navigate.rs
index 44f0e25bbd7..0dcb5930964 100644
--- a/library/alloc/src/collections/btree/navigate.rs
+++ b/library/alloc/src/collections/btree/navigate.rs
@@ -19,7 +19,7 @@ impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::E
                 Ok(internal_kv) => return Ok(internal_kv),
                 Err(last_edge) => match last_edge.into_node().ascend() {
                     Ok(parent_edge) => parent_edge.forget_node_type(),
-                    Err(root) => return Err(root.forget_type()),
+                    Err(root) => return Err(root),
                 },
             }
         }
@@ -40,7 +40,7 @@ impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::E
                 Ok(internal_kv) => return Ok(internal_kv),
                 Err(last_edge) => match last_edge.into_node().ascend() {
                     Ok(parent_edge) => parent_edge.forget_node_type(),
-                    Err(root) => return Err(root.forget_type()),
+                    Err(root) => return Err(root),
                 },
             }
         }
diff --git a/library/alloc/src/collections/btree/node.rs b/library/alloc/src/collections/btree/node.rs
index f7bd64608d6..b767d9ebed7 100644
--- a/library/alloc/src/collections/btree/node.rs
+++ b/library/alloc/src/collections/btree/node.rs
@@ -191,8 +191,9 @@ impl<K, V> Root<K, V> {
     }
 
     /// Adds a new internal node with a single edge, pointing to the previous root, and make that
-    /// new node the root. This increases the height by 1 and is the opposite of `pop_level`.
-    pub fn push_level(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> {
+    /// new node the root. This increases the height by 1 and is the opposite of
+    /// `pop_internal_level`.
+    pub fn push_internal_level(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> {
         let mut new_node = Box::new(unsafe { InternalNode::new() });
         new_node.edges[0].write(unsafe { BoxedNode::from_ptr(self.node.as_ptr()) });
 
@@ -213,11 +214,12 @@ impl<K, V> Root<K, V> {
         ret
     }
 
-    /// Removes the root node, using its first child as the new root. This cannot be called when
-    /// the tree consists only of a leaf node. As it is intended only to be called when the root
-    /// has only one edge, no cleanup is done on any of the other children of the root.
-    /// This decreases the height by 1 and is the opposite of `push_level`.
-    pub fn pop_level(&mut self) {
+    /// Removes the internal root node, using its first child as the new root.
+    /// As it is intended only to be called when the root has only one child,
+    /// no cleanup is done on any of the other children of the root.
+    /// This decreases the height by 1 and is the opposite of `push_internal_level`.
+    /// Panics if there is no internal level, i.e. if the root is a leaf.
+    pub fn pop_internal_level(&mut self) {
         assert!(self.height > 0);
 
         let top = self.node.ptr;
@@ -305,12 +307,6 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
         self.height
     }
 
-    /// Removes any static information about whether this node is a `Leaf` or an
-    /// `Internal` node.
-    pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
-        NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData }
-    }
-
     /// Temporarily takes out another, immutable reference to the same node.
     fn reborrow(&self) -> NodeRef<marker::Immut<'_>, K, V, Type> {
         NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData }
@@ -466,12 +462,6 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
     fn into_val_slice(self) -> &'a [V] {
         unsafe { slice::from_raw_parts(MaybeUninit::first_ptr(&self.as_leaf().vals), self.len()) }
     }
-
-    fn into_slices(self) -> (&'a [K], &'a [V]) {
-        // SAFETY: equivalent to reborrow() except not requiring Type: 'a
-        let k = unsafe { ptr::read(&self) };
-        (k.into_key_slice(), self.into_val_slice())
-    }
 }
 
 impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
@@ -980,10 +970,9 @@ impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marke
 
 impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Immut<'a>, K, V, NodeType>, marker::KV> {
     pub fn into_kv(self) -> (&'a K, &'a V) {
-        unsafe {
-            let (keys, vals) = self.node.into_slices();
-            (keys.get_unchecked(self.idx), vals.get_unchecked(self.idx))
-        }
+        let keys = self.node.into_key_slice();
+        let vals = self.node.into_val_slice();
+        unsafe { (keys.get_unchecked(self.idx), vals.get_unchecked(self.idx)) }
     }
 }
 
@@ -1362,6 +1351,20 @@ unsafe fn move_edges<K, V>(
     }
 }
 
+impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Leaf> {
+    /// Removes any static information asserting that this node is a `Leaf` node.
+    pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
+        NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData }
+    }
+}
+
+impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
+    /// Removes any static information asserting that this node is an `Internal` node.
+    pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
+        NodeRef { height: self.height, node: self.node, root: self.root, _marker: PhantomData }
+    }
+}
+
 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
     pub fn forget_node_type(
         self,
diff --git a/library/alloc/src/collections/linked_list.rs b/library/alloc/src/collections/linked_list.rs
index 1f875f6c521..02a746f0e24 100644
--- a/library/alloc/src/collections/linked_list.rs
+++ b/library/alloc/src/collections/linked_list.rs
@@ -1110,32 +1110,17 @@ impl<T> IterMut<'_, T> {
     /// Inserts the given element just after the element most recently returned by `.next()`.
     /// The inserted element does not appear in the iteration.
     ///
-    /// # Examples
-    ///
-    /// ```
-    /// #![feature(linked_list_extras)]
-    ///
-    /// use std::collections::LinkedList;
-    ///
-    /// let mut list: LinkedList<_> = vec![1, 3, 4].into_iter().collect();
-    ///
-    /// {
-    ///     let mut it = list.iter_mut();
-    ///     assert_eq!(it.next().unwrap(), &1);
-    ///     // insert `2` after `1`
-    ///     it.insert_next(2);
-    /// }
-    /// {
-    ///     let vec: Vec<_> = list.into_iter().collect();
-    ///     assert_eq!(vec, [1, 2, 3, 4]);
-    /// }
-    /// ```
+    /// This method will be removed soon.
     #[inline]
     #[unstable(
         feature = "linked_list_extras",
         reason = "this is probably better handled by a cursor type -- we'll see",
         issue = "27794"
     )]
+    #[rustc_deprecated(
+        reason = "Deprecated in favor of CursorMut methods. This method will be removed soon.",
+        since = "1.47.0"
+    )]
     pub fn insert_next(&mut self, element: T) {
         match self.head {
             // `push_back` is okay with aliasing `element` references
@@ -1163,27 +1148,17 @@ impl<T> IterMut<'_, T> {
 
     /// Provides a reference to the next element, without changing the iterator.
     ///
-    /// # Examples
-    ///
-    /// ```
-    /// #![feature(linked_list_extras)]
-    ///
-    /// use std::collections::LinkedList;
-    ///
-    /// let mut list: LinkedList<_> = vec![1, 2, 3].into_iter().collect();
-    ///
-    /// let mut it = list.iter_mut();
-    /// assert_eq!(it.next().unwrap(), &1);
-    /// assert_eq!(it.peek_next().unwrap(), &2);
-    /// // We just peeked at 2, so it was not consumed from the iterator.
-    /// assert_eq!(it.next().unwrap(), &2);
-    /// ```
+    /// This method will be removed soon.
     #[inline]
     #[unstable(
         feature = "linked_list_extras",
         reason = "this is probably better handled by a cursor type -- we'll see",
         issue = "27794"
     )]
+    #[rustc_deprecated(
+        reason = "Deprecated in favor of CursorMut methods. This method will be removed soon.",
+        since = "1.47.0"
+    )]
     pub fn peek_next(&mut self) -> Option<&mut T> {
         if self.len == 0 {
             None
diff --git a/library/alloc/src/collections/linked_list/tests.rs b/library/alloc/src/collections/linked_list/tests.rs
index b8c93a28bba..ad643a7bdf1 100644
--- a/library/alloc/src/collections/linked_list/tests.rs
+++ b/library/alloc/src/collections/linked_list/tests.rs
@@ -154,33 +154,6 @@ fn test_clone_from() {
 }
 
 #[test]
-fn test_insert_prev() {
-    let mut m = list_from(&[0, 2, 4, 6, 8]);
-    let len = m.len();
-    {
-        let mut it = m.iter_mut();
-        it.insert_next(-2);
-        loop {
-            match it.next() {
-                None => break,
-                Some(elt) => {
-                    it.insert_next(*elt + 1);
-                    match it.peek_next() {
-                        Some(x) => assert_eq!(*x, *elt + 2),
-                        None => assert_eq!(8, *elt),
-                    }
-                }
-            }
-        }
-        it.insert_next(0);
-        it.insert_next(1);
-    }
-    check_links(&m);
-    assert_eq!(m.len(), 3 + len * 2);
-    assert_eq!(m.into_iter().collect::<Vec<_>>(), [-2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1]);
-}
-
-#[test]
 #[cfg_attr(target_os = "emscripten", ignore)]
 fn test_send() {
     let n = list_from(&[1, 2, 3]);
diff --git a/library/alloc/src/collections/vec_deque/tests.rs b/library/alloc/src/collections/vec_deque/tests.rs
index e5edfe02a52..d74f91c752c 100644
--- a/library/alloc/src/collections/vec_deque/tests.rs
+++ b/library/alloc/src/collections/vec_deque/tests.rs
@@ -107,7 +107,8 @@ fn test_insert() {
     let cap = tester.capacity();
 
     // len is the length *after* insertion
-    for len in 1..cap {
+    let minlen = if cfg!(miri) { cap - 1 } else { 1 }; // Miri is too slow
+    for len in minlen..cap {
         // 0, 1, 2, .., len - 1
         let expected = (0..).take(len).collect::<VecDeque<_>>();
         for tail_pos in 0..cap {
@@ -221,7 +222,8 @@ fn test_remove() {
     let cap = tester.capacity();
 
     // len is the length *after* removal
-    for len in 0..cap - 1 {
+    let minlen = if cfg!(miri) { cap - 2 } else { 0 }; // Miri is too slow
+    for len in minlen..cap - 1 {
         // 0, 1, 2, .., len - 1
         let expected = (0..).take(len).collect::<VecDeque<_>>();
         for tail_pos in 0..cap {
@@ -251,7 +253,8 @@ fn test_range() {
     let mut tester: VecDeque<usize> = VecDeque::with_capacity(7);
 
     let cap = tester.capacity();
-    for len in 0..=cap {
+    let minlen = if cfg!(miri) { cap - 1 } else { 0 }; // Miri is too slow
+    for len in minlen..=cap {
         for tail in 0..=cap {
             for start in 0..=len {
                 for end in start..=len {
@@ -384,7 +387,8 @@ fn test_split_off() {
     let cap = tester.capacity();
 
     // len is the length *before* splitting
-    for len in 0..cap {
+    let minlen = if cfg!(miri) { cap - 1 } else { 0 }; // Miri is too slow
+    for len in minlen..cap {
         // index to split at
         for at in 0..=len {
             // 0, 1, 2, .., at - 1 (may be empty)
@@ -495,8 +499,9 @@ fn test_vec_from_vecdeque() {
 fn test_clone_from() {
     let m = vec![1; 8];
     let n = vec![2; 12];
-    for pfv in 0..8 {
-        for pfu in 0..8 {
+    let limit = if cfg!(miri) { 4 } else { 8 }; // Miri is too slow
+    for pfv in 0..limit {
+        for pfu in 0..limit {
             for longer in 0..2 {
                 let (vr, ur) = if longer == 0 { (&m, &n) } else { (&n, &m) };
                 let mut v = VecDeque::from(vr.clone());
diff --git a/library/alloc/src/fmt.rs b/library/alloc/src/fmt.rs
index 26077f3c8d1..b83b3024295 100644
--- a/library/alloc/src/fmt.rs
+++ b/library/alloc/src/fmt.rs
@@ -83,7 +83,7 @@
 //! # 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 (corresponding to `format_spec` in [the syntax](#syntax)). These
 //! parameters affect the string representation of what's being formatted.
 //!
 //! ## Width
diff --git a/library/alloc/src/lib.rs b/library/alloc/src/lib.rs
index 90e2d2531c5..097db30d634 100644
--- a/library/alloc/src/lib.rs
+++ b/library/alloc/src/lib.rs
@@ -69,13 +69,13 @@
 #![warn(deprecated_in_future)]
 #![warn(missing_docs)]
 #![warn(missing_debug_implementations)]
-#![deny(intra_doc_link_resolution_failure)] // rustdoc is run without -D warnings
 #![allow(explicit_outlives_requirements)]
 #![allow(incomplete_features)]
 #![deny(unsafe_op_in_unsafe_fn)]
 #![cfg_attr(not(test), feature(generator_trait))]
 #![cfg_attr(test, feature(test))]
 #![feature(allocator_api)]
+#![feature(array_chunks)]
 #![feature(allow_internal_unstable)]
 #![feature(arbitrary_self_types)]
 #![feature(box_patterns)]
diff --git a/library/alloc/src/rc.rs b/library/alloc/src/rc.rs
index c3af42c0cbb..c0c638292bb 100644
--- a/library/alloc/src/rc.rs
+++ b/library/alloc/src/rc.rs
@@ -645,29 +645,6 @@ impl<T: ?Sized> Rc<T> {
         unsafe { Self::from_ptr(rc_ptr) }
     }
 
-    /// Consumes the `Rc`, returning the wrapped pointer as `NonNull<T>`.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// #![feature(rc_into_raw_non_null)]
-    /// #![allow(deprecated)]
-    ///
-    /// use std::rc::Rc;
-    ///
-    /// let x = Rc::new("hello".to_owned());
-    /// let ptr = Rc::into_raw_non_null(x);
-    /// let deref = unsafe { ptr.as_ref() };
-    /// assert_eq!(deref, "hello");
-    /// ```
-    #[unstable(feature = "rc_into_raw_non_null", issue = "47336")]
-    #[rustc_deprecated(since = "1.44.0", reason = "use `Rc::into_raw` instead")]
-    #[inline]
-    pub fn into_raw_non_null(this: Self) -> NonNull<T> {
-        // safe because Rc guarantees its pointer is non-null
-        unsafe { NonNull::new_unchecked(Rc::into_raw(this) as *mut _) }
-    }
-
     /// Creates a new [`Weak`][weak] pointer to this allocation.
     ///
     /// [weak]: struct.Weak.html
@@ -1713,8 +1690,9 @@ impl<T> Weak<T> {
 
     /// Consumes the `Weak<T>` and turns it into a raw pointer.
     ///
-    /// This converts the weak pointer into a raw pointer, preserving the original weak count. It
-    /// can be turned back into the `Weak<T>` with [`from_raw`].
+    /// This converts the weak pointer into a raw pointer, while still preserving the ownership of
+    /// one weak reference (the weak count is not modified by this operation). It can be turned
+    /// back into the `Weak<T>` with [`from_raw`].
     ///
     /// The same restrictions of accessing the target of the pointer as with
     /// [`as_ptr`] apply.
@@ -1749,17 +1727,18 @@ impl<T> Weak<T> {
     /// This can be used to safely get a strong reference (by calling [`upgrade`]
     /// later) or to deallocate the weak count by dropping the `Weak<T>`.
     ///
-    /// It takes ownership of one weak count (with the exception of pointers created by [`new`],
-    /// as these don't have any corresponding weak count).
+    /// It takes ownership of one weak reference (with the exception of pointers created by [`new`],
+    /// as these don't own anything; the method still works on them).
     ///
     /// # Safety
     ///
-    /// The pointer must have originated from the [`into_raw`]  and must still own its potential
-    /// weak reference count.
+    /// The pointer must have originated from the [`into_raw`] and must still own its potential
+    /// weak reference.
     ///
-    /// It is allowed for the strong count to be 0 at the time of calling this, but the weak count
-    /// must be non-zero or the pointer must have originated from a dangling `Weak<T>` (one created
-    /// by [`new`]).
+    /// It is allowed for the strong count to be 0 at the time of calling this. Nevertheless, this
+    /// takes ownership of one weak reference currently represented as a raw pointer (the weak
+    /// count is not modified by this operation) and therefore it must be paired with a previous
+    /// call to [`into_raw`].
     ///
     /// # Examples
     ///
@@ -2120,7 +2099,7 @@ impl<T: ?Sized> Unpin for Rc<T> {}
 ///
 /// - This function is safe for any argument if `T` is sized, and
 /// - if `T` is unsized, the pointer must have appropriate pointer metadata
-///   aquired from the real instance that you are getting this offset for.
+///   acquired from the real instance that you are getting this offset for.
 unsafe fn data_offset<T: ?Sized>(ptr: *const T) -> isize {
     // Align the unsized value to the end of the `RcBox`.
     // Because it is ?Sized, it will always be the last field in memory.
diff --git a/library/alloc/src/slice.rs b/library/alloc/src/slice.rs
index 3d51115fe01..b791c775548 100644
--- a/library/alloc/src/slice.rs
+++ b/library/alloc/src/slice.rs
@@ -95,6 +95,8 @@ use crate::borrow::ToOwned;
 use crate::boxed::Box;
 use crate::vec::Vec;
 
+#[unstable(feature = "array_chunks", issue = "74985")]
+pub use core::slice::ArrayChunks;
 #[stable(feature = "slice_get_slice", since = "1.28.0")]
 pub use core::slice::SliceIndex;
 #[stable(feature = "from_ref", since = "1.28.0")]
diff --git a/library/alloc/src/string.rs b/library/alloc/src/string.rs
index 05398ca68c8..d7d7b6bd157 100644
--- a/library/alloc/src/string.rs
+++ b/library/alloc/src/string.rs
@@ -2196,6 +2196,9 @@ pub trait ToString {
 /// since `fmt::Write for String` never returns an error itself.
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T: fmt::Display + ?Sized> ToString for T {
+    // A common guideline is to not inline generic functions. However,
+    // remove `#[inline]` from this method causes non-negligible regression.
+    // See <https://github.com/rust-lang/rust/pull/74852> as last attempt try to remove it.
     #[inline]
     default fn to_string(&self) -> String {
         use fmt::Write;
diff --git a/library/alloc/src/sync.rs b/library/alloc/src/sync.rs
index bd70639428a..7d5f24ec4ad 100644
--- a/library/alloc/src/sync.rs
+++ b/library/alloc/src/sync.rs
@@ -646,29 +646,6 @@ impl<T: ?Sized> Arc<T> {
         }
     }
 
-    /// Consumes the `Arc`, returning the wrapped pointer as `NonNull<T>`.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// #![feature(rc_into_raw_non_null)]
-    /// #![allow(deprecated)]
-    ///
-    /// use std::sync::Arc;
-    ///
-    /// let x = Arc::new("hello".to_owned());
-    /// let ptr = Arc::into_raw_non_null(x);
-    /// let deref = unsafe { ptr.as_ref() };
-    /// assert_eq!(deref, "hello");
-    /// ```
-    #[unstable(feature = "rc_into_raw_non_null", issue = "47336")]
-    #[rustc_deprecated(since = "1.44.0", reason = "use `Arc::into_raw` instead")]
-    #[inline]
-    pub fn into_raw_non_null(this: Self) -> NonNull<T> {
-        // safe because Arc guarantees its pointer is non-null
-        unsafe { NonNull::new_unchecked(Arc::into_raw(this) as *mut _) }
-    }
-
     /// Creates a new [`Weak`][weak] pointer to this allocation.
     ///
     /// [weak]: struct.Weak.html
@@ -1483,8 +1460,9 @@ impl<T> Weak<T> {
 
     /// Consumes the `Weak<T>` and turns it into a raw pointer.
     ///
-    /// This converts the weak pointer into a raw pointer, preserving the original weak count. It
-    /// can be turned back into the `Weak<T>` with [`from_raw`].
+    /// This converts the weak pointer into a raw pointer, while still preserving the ownership of
+    /// one weak reference (the weak count is not modified by this operation). It can be turned
+    /// back into the `Weak<T>` with [`from_raw`].
     ///
     /// The same restrictions of accessing the target of the pointer as with
     /// [`as_ptr`] apply.
@@ -1514,24 +1492,23 @@ impl<T> Weak<T> {
         result
     }
 
-    /// Converts a raw pointer previously created by [`into_raw`] back into
-    /// `Weak<T>`.
+    /// Converts a raw pointer previously created by [`into_raw`] back into `Weak<T>`.
     ///
     /// This can be used to safely get a strong reference (by calling [`upgrade`]
     /// later) or to deallocate the weak count by dropping the `Weak<T>`.
     ///
-    /// It takes ownership of one weak count (with the exception of pointers created by [`new`],
-    /// as these don't have any corresponding weak count).
+    /// It takes ownership of one weak reference (with the exception of pointers created by [`new`],
+    /// as these don't own anything; the method still works on them).
     ///
     /// # Safety
     ///
     /// The pointer must have originated from the [`into_raw`] and must still own its potential
-    /// weak reference count.
-    ///
-    /// It is allowed for the strong count to be 0 at the time of calling this, but the weak count
-    /// must be non-zero or the pointer must have originated from a dangling `Weak<T>` (one created
-    /// by [`new`]).
+    /// weak reference.
     ///
+    /// It is allowed for the strong count to be 0 at the time of calling this. Nevertheless, this
+    /// takes ownership of one weak reference currently represented as a raw pointer (the weak
+    /// count is not modified by this operation) and therefore it must be paired with a previous
+    /// call to [`into_raw`].
     /// # Examples
     ///
     /// ```
@@ -2276,7 +2253,7 @@ impl<T: ?Sized> Unpin for Arc<T> {}
 ///
 /// - This function is safe for any argument if `T` is sized, and
 /// - if `T` is unsized, the pointer must have appropriate pointer metadata
-///   aquired from the real instance that you are getting this offset for.
+///   acquired from the real instance that you are getting this offset for.
 unsafe fn data_offset<T: ?Sized>(ptr: *const T) -> isize {
     // Align the unsized value to the end of the `ArcInner`.
     // Because it is `?Sized`, it will always be the last field in memory.
diff --git a/library/alloc/src/vec.rs b/library/alloc/src/vec.rs
index f5a3d0cd4af..786d1b6ba82 100644
--- a/library/alloc/src/vec.rs
+++ b/library/alloc/src/vec.rs
@@ -65,7 +65,7 @@ use core::hash::{Hash, Hasher};
 use core::intrinsics::{arith_offset, assume};
 use core::iter::{FromIterator, FusedIterator, TrustedLen};
 use core::marker::PhantomData;
-use core::mem::{self, ManuallyDrop};
+use core::mem::{self, ManuallyDrop, MaybeUninit};
 use core::ops::Bound::{Excluded, Included, Unbounded};
 use core::ops::{self, Index, IndexMut, RangeBounds};
 use core::ptr::{self, NonNull};
@@ -1510,20 +1510,59 @@ impl<T> Vec<T> {
     /// Simple usage:
     ///
     /// ```
-    /// #![feature(vec_leak)]
-    ///
     /// let x = vec![1, 2, 3];
-    /// let static_ref: &'static mut [usize] = Vec::leak(x);
+    /// let static_ref: &'static mut [usize] = x.leak();
     /// static_ref[0] += 1;
     /// assert_eq!(static_ref, &[2, 2, 3]);
     /// ```
-    #[unstable(feature = "vec_leak", issue = "62195")]
+    #[stable(feature = "vec_leak", since = "1.47.0")]
     #[inline]
-    pub fn leak<'a>(vec: Vec<T>) -> &'a mut [T]
+    pub fn leak<'a>(self) -> &'a mut [T]
     where
         T: 'a, // Technically not needed, but kept to be explicit.
     {
-        Box::leak(vec.into_boxed_slice())
+        Box::leak(self.into_boxed_slice())
+    }
+
+    /// Returns the remaining spare capacity of the vector as a slice of
+    /// `MaybeUninit<T>`.
+    ///
+    /// The returned slice can be used to fill the vector with data (e.g. by
+    /// reading from a file) before marking the data as initialized using the
+    /// [`set_len`] method.
+    ///
+    /// [`set_len`]: #method.set_len
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(vec_spare_capacity, maybe_uninit_extra)]
+    ///
+    /// // Allocate vector big enough for 10 elements.
+    /// let mut v = Vec::with_capacity(10);
+    ///
+    /// // Fill in the first 3 elements.
+    /// let uninit = v.spare_capacity_mut();
+    /// uninit[0].write(0);
+    /// uninit[1].write(1);
+    /// uninit[2].write(2);
+    ///
+    /// // Mark the first 3 elements of the vector as being initialized.
+    /// unsafe {
+    ///     v.set_len(3);
+    /// }
+    ///
+    /// assert_eq!(&v, &[0, 1, 2]);
+    /// ```
+    #[unstable(feature = "vec_spare_capacity", issue = "75017")]
+    #[inline]
+    pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
+        unsafe {
+            slice::from_raw_parts_mut(
+                self.as_mut_ptr().add(self.len) as *mut MaybeUninit<T>,
+                self.buf.capacity() - self.len,
+            )
+        }
     }
 }