Rollup merge of #58431 - RalfJung:btree, r=Mark-Simulacrum

fix overlapping references in BTree

This fixes two kinds of overlapping references in BTree (both found by running the BTree test suite in Miri).

In `into_slices_mut`, we did `k.into_key_slice_mut()` followed by `self.into_val_slice_mut()` (where `k` is a copy of `self`). Calling `into_val_slice_mut` calls `self.len()`, which creates a shared reference to `NodeHeader`, which unfortunately (due to padding) overlaps with the mutable reference returned by `into_key_slice_mut`.  Hence the key slice got (partially) invalidated.  The fix is to avoid creating an `&NodeHeader` after the first slice got created.

In the iterators, we used to first create the references that will be returned, and then perform the walk on the tree.  Walking the tree creates references (such as `&mut InternalNode`) that overlap with all of the keys and values stored in a pointer; in particular, they overlap with the references the iterator will later return. This is fixed by reordering the operations of walking the tree and obtaining the inner references.

The test suite still passes (and it passes in Miri now!), but there is a lot of code here that I do not understand...

0 files changed, 0 insertions, 0 deletions