Auto merge of #75060 - JohnTitor:rollup-aq8sfxf, r=JohnTitor

Rollup of 10 pull requests

Successful merges:

 - #74686 (BTreeMap: remove into_slices and its unsafe block)
 - #74762 (BTreeMap::drain_filter should not touch the root during iteration)
 - #74781 (Clean up E0733 explanation)
 - #74874 (BTreeMap: define forget_type only when relevant)
 - #74974 (Make tests faster in Miri)
 - #75010 (Update elasticlunr-rs and ammonia transitive deps)
 - #75041 (Replaced log with tracing crate)
 - #75044 (Clean up E0744 explanation)
 - #75054 (Rename rustc_middle::cstore::DepKind to CrateDepKind)
 - #75057 (Avoid dumping rustc invocations to stdout)

Failed merges:

 - #74827 (Move bulk of BTreeMap::insert method down to new method on handle)

r? @ghost

10 files changed, 442 insertions, 82 deletions

diff --git a/library/alloc/benches/btree/map.rs b/library/alloc/benches/btree/map.rs
index 38d19c59ad1..7c2e5694a62 100644
--- a/library/alloc/benches/btree/map.rs
+++ b/library/alloc/benches/btree/map.rs
@@ -282,3 +282,305 @@ pub fn iter_10k(b: &mut Bencher) {
 pub fn iter_1m(b: &mut Bencher) {
     bench_iter(b, 1_000, 1_000_000);
 }
+
+const FAT: usize = 256;
+
+// The returned map has small keys and values.
+// Benchmarks on it have a counterpart in set.rs with the same keys and no values at all.
+fn slim_map(n: usize) -> BTreeMap<usize, usize> {
+    (0..n).map(|i| (i, i)).collect::<BTreeMap<_, _>>()
+}
+
+// The returned map has small keys and large values.
+fn fat_val_map(n: usize) -> BTreeMap<usize, [usize; FAT]> {
+    (0..n).map(|i| (i, [i; FAT])).collect::<BTreeMap<_, _>>()
+}
+
+// The returned map has large keys and values.
+fn fat_map(n: usize) -> BTreeMap<[usize; FAT], [usize; FAT]> {
+    (0..n).map(|i| ([i; FAT], [i; FAT])).collect::<BTreeMap<_, _>>()
+}
+
+#[bench]
+pub fn clone_slim_100(b: &mut Bencher) {
+    let src = slim_map(100);
+    b.iter(|| src.clone())
+}
+
+#[bench]
+pub fn clone_slim_100_and_clear(b: &mut Bencher) {
+    let src = slim_map(100);
+    b.iter(|| src.clone().clear())
+}
+
+#[bench]
+pub fn clone_slim_100_and_drain_all(b: &mut Bencher) {
+    let src = slim_map(100);
+    b.iter(|| src.clone().drain_filter(|_, _| true).count())
+}
+
+#[bench]
+pub fn clone_slim_100_and_drain_half(b: &mut Bencher) {
+    let src = slim_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 100 / 2);
+        assert_eq!(map.len(), 100 / 2);
+    })
+}
+
+#[bench]
+pub fn clone_slim_100_and_into_iter(b: &mut Bencher) {
+    let src = slim_map(100);
+    b.iter(|| src.clone().into_iter().count())
+}
+
+#[bench]
+pub fn clone_slim_100_and_pop_all(b: &mut Bencher) {
+    let src = slim_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        while map.pop_first().is_some() {}
+        map
+    });
+}
+
+#[bench]
+pub fn clone_slim_100_and_remove_all(b: &mut Bencher) {
+    let src = slim_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
+            let v = map.remove(&elt);
+            debug_assert!(v.is_some());
+        }
+        map
+    });
+}
+
+#[bench]
+pub fn clone_slim_100_and_remove_half(b: &mut Bencher) {
+    let src = slim_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        for i in (0..100).step_by(2) {
+            let v = map.remove(&i);
+            debug_assert!(v.is_some());
+        }
+        assert_eq!(map.len(), 100 / 2);
+        map
+    })
+}
+
+#[bench]
+pub fn clone_slim_10k(b: &mut Bencher) {
+    let src = slim_map(10_000);
+    b.iter(|| src.clone())
+}
+
+#[bench]
+pub fn clone_slim_10k_and_clear(b: &mut Bencher) {
+    let src = slim_map(10_000);
+    b.iter(|| src.clone().clear())
+}
+
+#[bench]
+pub fn clone_slim_10k_and_drain_all(b: &mut Bencher) {
+    let src = slim_map(10_000);
+    b.iter(|| src.clone().drain_filter(|_, _| true).count())
+}
+
+#[bench]
+pub fn clone_slim_10k_and_drain_half(b: &mut Bencher) {
+    let src = slim_map(10_000);
+    b.iter(|| {
+        let mut map = src.clone();
+        assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 10_000 / 2);
+        assert_eq!(map.len(), 10_000 / 2);
+    })
+}
+
+#[bench]
+pub fn clone_slim_10k_and_into_iter(b: &mut Bencher) {
+    let src = slim_map(10_000);
+    b.iter(|| src.clone().into_iter().count())
+}
+
+#[bench]
+pub fn clone_slim_10k_and_pop_all(b: &mut Bencher) {
+    let src = slim_map(10_000);
+    b.iter(|| {
+        let mut map = src.clone();
+        while map.pop_first().is_some() {}
+        map
+    });
+}
+
+#[bench]
+pub fn clone_slim_10k_and_remove_all(b: &mut Bencher) {
+    let src = slim_map(10_000);
+    b.iter(|| {
+        let mut map = src.clone();
+        while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
+            let v = map.remove(&elt);
+            debug_assert!(v.is_some());
+        }
+        map
+    });
+}
+
+#[bench]
+pub fn clone_slim_10k_and_remove_half(b: &mut Bencher) {
+    let src = slim_map(10_000);
+    b.iter(|| {
+        let mut map = src.clone();
+        for i in (0..10_000).step_by(2) {
+            let v = map.remove(&i);
+            debug_assert!(v.is_some());
+        }
+        assert_eq!(map.len(), 10_000 / 2);
+        map
+    })
+}
+
+#[bench]
+pub fn clone_fat_val_100(b: &mut Bencher) {
+    let src = fat_val_map(100);
+    b.iter(|| src.clone())
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_clear(b: &mut Bencher) {
+    let src = fat_val_map(100);
+    b.iter(|| src.clone().clear())
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_drain_all(b: &mut Bencher) {
+    let src = fat_val_map(100);
+    b.iter(|| src.clone().drain_filter(|_, _| true).count())
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_drain_half(b: &mut Bencher) {
+    let src = fat_val_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 100 / 2);
+        assert_eq!(map.len(), 100 / 2);
+    })
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_into_iter(b: &mut Bencher) {
+    let src = fat_val_map(100);
+    b.iter(|| src.clone().into_iter().count())
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_pop_all(b: &mut Bencher) {
+    let src = fat_val_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        while map.pop_first().is_some() {}
+        map
+    });
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_remove_all(b: &mut Bencher) {
+    let src = fat_val_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
+            let v = map.remove(&elt);
+            debug_assert!(v.is_some());
+        }
+        map
+    });
+}
+
+#[bench]
+pub fn clone_fat_val_100_and_remove_half(b: &mut Bencher) {
+    let src = fat_val_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        for i in (0..100).step_by(2) {
+            let v = map.remove(&i);
+            debug_assert!(v.is_some());
+        }
+        assert_eq!(map.len(), 100 / 2);
+        map
+    })
+}
+
+#[bench]
+pub fn clone_fat_100(b: &mut Bencher) {
+    let src = fat_map(100);
+    b.iter(|| src.clone())
+}
+
+#[bench]
+pub fn clone_fat_100_and_clear(b: &mut Bencher) {
+    let src = fat_map(100);
+    b.iter(|| src.clone().clear())
+}
+
+#[bench]
+pub fn clone_fat_100_and_drain_all(b: &mut Bencher) {
+    let src = fat_map(100);
+    b.iter(|| src.clone().drain_filter(|_, _| true).count())
+}
+
+#[bench]
+pub fn clone_fat_100_and_drain_half(b: &mut Bencher) {
+    let src = fat_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        assert_eq!(map.drain_filter(|i, _| i[0] % 2 == 0).count(), 100 / 2);
+        assert_eq!(map.len(), 100 / 2);
+    })
+}
+
+#[bench]
+pub fn clone_fat_100_and_into_iter(b: &mut Bencher) {
+    let src = fat_map(100);
+    b.iter(|| src.clone().into_iter().count())
+}
+
+#[bench]
+pub fn clone_fat_100_and_pop_all(b: &mut Bencher) {
+    let src = fat_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        while map.pop_first().is_some() {}
+        map
+    });
+}
+
+#[bench]
+pub fn clone_fat_100_and_remove_all(b: &mut Bencher) {
+    let src = fat_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
+            let v = map.remove(&elt);
+            debug_assert!(v.is_some());
+        }
+        map
+    });
+}
+
+#[bench]
+pub fn clone_fat_100_and_remove_half(b: &mut Bencher) {
+    let src = fat_map(100);
+    b.iter(|| {
+        let mut map = src.clone();
+        for i in (0..100).step_by(2) {
+            let v = map.remove(&[i; FAT]);
+            debug_assert!(v.is_some());
+        }
+        assert_eq!(map.len(), 100 / 2);
+        map
+    })
+}
diff --git a/library/alloc/benches/btree/set.rs b/library/alloc/benches/btree/set.rs
index 2518506b9b5..07bf5093727 100644
--- a/library/alloc/benches/btree/set.rs
+++ b/library/alloc/benches/btree/set.rs
@@ -50,27 +50,31 @@ macro_rules! set_bench {
     };
 }
 
+fn slim_set(n: usize) -> BTreeSet<usize> {
+    (0..n).collect::<BTreeSet<_>>()
+}
+
 #[bench]
 pub fn clone_100(b: &mut Bencher) {
-    let src = pos(100);
+    let src = slim_set(100);
     b.iter(|| src.clone())
 }
 
 #[bench]
 pub fn clone_100_and_clear(b: &mut Bencher) {
-    let src = pos(100);
+    let src = slim_set(100);
     b.iter(|| src.clone().clear())
 }
 
 #[bench]
 pub fn clone_100_and_drain_all(b: &mut Bencher) {
-    let src = pos(100);
+    let src = slim_set(100);
     b.iter(|| src.clone().drain_filter(|_| true).count())
 }
 
 #[bench]
 pub fn clone_100_and_drain_half(b: &mut Bencher) {
-    let src = pos(100);
+    let src = slim_set(100);
     b.iter(|| {
         let mut set = src.clone();
         assert_eq!(set.drain_filter(|i| i % 2 == 0).count(), 100 / 2);
@@ -80,13 +84,13 @@ pub fn clone_100_and_drain_half(b: &mut Bencher) {
 
 #[bench]
 pub fn clone_100_and_into_iter(b: &mut Bencher) {
-    let src = pos(100);
+    let src = slim_set(100);
     b.iter(|| src.clone().into_iter().count())
 }
 
 #[bench]
 pub fn clone_100_and_pop_all(b: &mut Bencher) {
-    let src = pos(100);
+    let src = slim_set(100);
     b.iter(|| {
         let mut set = src.clone();
         while set.pop_first().is_some() {}
@@ -96,11 +100,12 @@ pub fn clone_100_and_pop_all(b: &mut Bencher) {
 
 #[bench]
 pub fn clone_100_and_remove_all(b: &mut Bencher) {
-    let src = pos(100);
+    let src = slim_set(100);
     b.iter(|| {
         let mut set = src.clone();
         while let Some(elt) = set.iter().copied().next() {
-            set.remove(&elt);
+            let ok = set.remove(&elt);
+            debug_assert!(ok);
         }
         set
     });
@@ -108,11 +113,12 @@ pub fn clone_100_and_remove_all(b: &mut Bencher) {
 
 #[bench]
 pub fn clone_100_and_remove_half(b: &mut Bencher) {
-    let src = pos(100);
+    let src = slim_set(100);
     b.iter(|| {
         let mut set = src.clone();
-        for i in (2..=100 as i32).step_by(2) {
-            set.remove(&i);
+        for i in (0..100).step_by(2) {
+            let ok = set.remove(&i);
+            debug_assert!(ok);
         }
         assert_eq!(set.len(), 100 / 2);
         set
@@ -121,25 +127,25 @@ pub fn clone_100_and_remove_half(b: &mut Bencher) {
 
 #[bench]
 pub fn clone_10k(b: &mut Bencher) {
-    let src = pos(10_000);
+    let src = slim_set(10_000);
     b.iter(|| src.clone())
 }
 
 #[bench]
 pub fn clone_10k_and_clear(b: &mut Bencher) {
-    let src = pos(10_000);
+    let src = slim_set(10_000);
     b.iter(|| src.clone().clear())
 }
 
 #[bench]
 pub fn clone_10k_and_drain_all(b: &mut Bencher) {
-    let src = pos(10_000);
+    let src = slim_set(10_000);
     b.iter(|| src.clone().drain_filter(|_| true).count())
 }
 
 #[bench]
 pub fn clone_10k_and_drain_half(b: &mut Bencher) {
-    let src = pos(10_000);
+    let src = slim_set(10_000);
     b.iter(|| {
         let mut set = src.clone();
         assert_eq!(set.drain_filter(|i| i % 2 == 0).count(), 10_000 / 2);
@@ -149,13 +155,13 @@ pub fn clone_10k_and_drain_half(b: &mut Bencher) {
 
 #[bench]
 pub fn clone_10k_and_into_iter(b: &mut Bencher) {
-    let src = pos(10_000);
+    let src = slim_set(10_000);
     b.iter(|| src.clone().into_iter().count())
 }
 
 #[bench]
 pub fn clone_10k_and_pop_all(b: &mut Bencher) {
-    let src = pos(10_000);
+    let src = slim_set(10_000);
     b.iter(|| {
         let mut set = src.clone();
         while set.pop_first().is_some() {}
@@ -165,11 +171,12 @@ pub fn clone_10k_and_pop_all(b: &mut Bencher) {
 
 #[bench]
 pub fn clone_10k_and_remove_all(b: &mut Bencher) {
-    let src = pos(10_000);
+    let src = slim_set(10_000);
     b.iter(|| {
         let mut set = src.clone();
         while let Some(elt) = set.iter().copied().next() {
-            set.remove(&elt);
+            let ok = set.remove(&elt);
+            debug_assert!(ok);
         }
         set
     });
@@ -177,11 +184,12 @@ pub fn clone_10k_and_remove_all(b: &mut Bencher) {
 
 #[bench]
 pub fn clone_10k_and_remove_half(b: &mut Bencher) {
-    let src = pos(10_000);
+    let src = slim_set(10_000);
     b.iter(|| {
         let mut set = src.clone();
-        for i in (2..=10_000 as i32).step_by(2) {
-            set.remove(&i);
+        for i in (0..10_000).step_by(2) {
+            let ok = set.remove(&i);
+            debug_assert!(ok);
         }
         assert_eq!(set.len(), 10_000 / 2);
         set
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/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/tests/slice.rs b/library/alloc/tests/slice.rs
index 75b76bb73ed..147f7f7d0c7 100644
--- a/library/alloc/tests/slice.rs
+++ b/library/alloc/tests/slice.rs
@@ -1721,8 +1721,8 @@ fn panic_safe() {
 
     let mut rng = thread_rng();
 
-    // Miri is too slow
-    let lens = if cfg!(miri) { (1..10).chain(20..21) } else { (1..20).chain(70..MAX_LEN) };
+    // Miri is too slow (but still need to `chain` to make the types match)
+    let lens = if cfg!(miri) { (1..10).chain(0..0) } else { (1..20).chain(70..MAX_LEN) };
     let moduli: &[u32] = if cfg!(miri) { &[5] } else { &[5, 20, 50] };
 
     for len in lens {
diff --git a/library/core/tests/num/flt2dec/random.rs b/library/core/tests/num/flt2dec/random.rs
index 0ebc0881f52..e5656eb204c 100644
--- a/library/core/tests/num/flt2dec/random.rs
+++ b/library/core/tests/num/flt2dec/random.rs
@@ -188,7 +188,7 @@ fn exact_f32_random_equivalence_test() {
 fn exact_f64_random_equivalence_test() {
     use core::num::flt2dec::strategy::dragon::format_exact as fallback;
     // Miri is too slow
-    let n = if cfg!(miri) { 3 } else { 1_000 };
+    let n = if cfg!(miri) { 2 } else { 1_000 };
 
     for k in 1..21 {
         f64_random_equivalence_test(
diff --git a/library/core/tests/num/flt2dec/strategy/grisu.rs b/library/core/tests/num/flt2dec/strategy/grisu.rs
index ff8373c6455..7e6c8add333 100644
--- a/library/core/tests/num/flt2dec/strategy/grisu.rs
+++ b/library/core/tests/num/flt2dec/strategy/grisu.rs
@@ -2,6 +2,7 @@ use super::super::*;
 use core::num::flt2dec::strategy::grisu::*;
 
 #[test]
+#[cfg_attr(miri, ignore)] // Miri is too slow
 fn test_cached_power() {
     assert_eq!(CACHED_POW10.first().unwrap().1, CACHED_POW10_FIRST_E);
     assert_eq!(CACHED_POW10.last().unwrap().1, CACHED_POW10_LAST_E);
diff --git a/library/core/tests/slice.rs b/library/core/tests/slice.rs
index 27cc7fce1da..42b483f33ba 100644
--- a/library/core/tests/slice.rs
+++ b/library/core/tests/slice.rs
@@ -1358,15 +1358,15 @@ fn sort_unstable() {
     use core::slice::heapsort;
     use rand::{rngs::StdRng, seq::SliceRandom, Rng, SeedableRng};
 
-    // Miri is too slow
-    let large_range = if cfg!(miri) { 0..0 } else { 500..510 };
+    // Miri is too slow (but still need to `chain` to make the types match)
+    let lens = if cfg!(miri) { (2..20).chain(0..0) } else { (2..25).chain(500..510) };
     let rounds = if cfg!(miri) { 1 } else { 100 };
 
     let mut v = [0; 600];
     let mut tmp = [0; 600];
     let mut rng = StdRng::from_entropy();
 
-    for len in (2..25).chain(large_range) {
+    for len in lens {
         let v = &mut v[0..len];
         let tmp = &mut tmp[0..len];