2 files changed, 21 insertions, 13 deletions
diff --git a/src/liballoc/collections/btree/node.rs b/src/liballoc/collections/btree/node.rs
index 260e51d635d..f40e0b0c304 100644
--- a/src/liballoc/collections/btree/node.rs
+++ b/src/liballoc/collections/btree/node.rs
@@ -397,6 +397,7 @@ impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
 
     /// Borrows a view into the values stored in the node.
     /// The caller must ensure that the node is not the shared root.
+    /// This function is not public, so doesn't have to support shared roots like `keys` does.
     fn vals(&self) -> &[V] {
         self.reborrow().into_val_slice()
     }
@@ -514,6 +515,7 @@ impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
     }
 
     /// The caller must ensure that the node is not the shared root.
+    /// This function is not public, so doesn't have to support shared roots like `keys` does.
     fn keys_mut(&mut self) -> &mut [K] {
         unsafe { self.reborrow_mut().into_key_slice_mut() }
     }
@@ -589,20 +591,15 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
         unsafe { &mut *(self.root as *mut Root<K, V>) }
     }
 
+    /// The caller must ensure that the node is not the shared root.
     fn into_key_slice_mut(mut self) -> &'a mut [K] {
-        // Same as for `into_key_slice` above, we try to avoid a run-time check.
-        if (mem::align_of::<NodeHeader<K, V, K>>() > mem::align_of::<NodeHeader<K, V>>()
-            || mem::size_of::<NodeHeader<K, V, K>>() != mem::size_of::<NodeHeader<K, V>>())
-            && self.is_shared_root()
-        {
-            &mut []
-        } else {
-            unsafe {
-                slice::from_raw_parts_mut(
-                    MaybeUninit::first_ptr_mut(&mut (*self.as_leaf_mut()).keys),
-                    self.len(),
-                )
-            }
+        debug_assert!(!self.is_shared_root());
+        // We cannot be the shared root, so `as_leaf_mut` is okay.
+        unsafe {
+            slice::from_raw_parts_mut(
+                MaybeUninit::first_ptr_mut(&mut (*self.as_leaf_mut()).keys),
+                self.len(),
+            )
         }
     }
 
diff --git a/src/liballoc/collections/btree/search.rs b/src/liballoc/collections/btree/search.rs
index 3f3c49a2ef8..48cbf67eea2 100644
--- a/src/liballoc/collections/btree/search.rs
+++ b/src/liballoc/collections/btree/search.rs
@@ -46,6 +46,11 @@ where
     }
 }
 
+/// Returns the index in the node at which the key (or an equivalent) exists
+/// or could exist, and whether it exists in the node itself. If it doesn't
+/// exist in the node itself, it may exist in the subtree with that index
+/// (if the node has subtrees). If the key doesn't exist in node or subtree,
+/// the returned index is the position or subtree to insert at.
 pub fn search_linear<BorrowType, K, V, Type, Q: ?Sized>(
     node: &NodeRef<BorrowType, K, V, Type>,
     key: &Q,
@@ -54,6 +59,12 @@ where
     Q: Ord,
     K: Borrow<Q>,
 {
+    // This function is defined over all borrow types (immutable, mutable, owned),
+    // and may be called on the shared root in each case.
+    // Crucially, we use `keys()` here, i.e., we work with immutable data.
+    // `keys_mut()` does not support the shared root, so we cannot use it.
+    // Using `keys()` is fine here even if BorrowType is mutable, as all we return
+    // is an index -- not a reference.
     for (i, k) in node.keys().iter().enumerate() {
         match key.cmp(k.borrow()) {
             Ordering::Greater => {}