Partial (non-overlapping) mutability of a BTreeMap (or more accurately a BTreeTree)

We need a BTreeMap with some unusual properties:

  1. Having a child borrowed (mutably or immutably) shouldn't prevent adding/removing nodes on the parent, as long as such nodes aren't borrowed.
  2. To mutably borrow a child requires mutably borrowing the parent.

These are based on the following property of Rust structs:

// boilerplate
let x = &mut a.x;
let y = &mut a.y;
// can use both x and y, since they're non-overlapping.

But how do you extend the idea of "non-overlapping" to heap-allocated collections? (Rust structs require you to define the struct at compile-time, so you can't just "add fields" to a borrowed struct. But there's no reason a heap-allocated collection should have the same limitations.

It would be possible to write a correct BTreeMap that allows this, but you can't do it with the BTreeMap in std because its interface is not sufficiently powerful.

The iter_mut method allows you to do this on most collections. On slices, you can do it with split_at_mut. However I don't think there are any collections in std that allow modifications of its structure (e.g. adding nodes to a BTreeMap) while such borrows are active.

2 Likes

Ah, so we guess we'd need to bring our own Ref/Mut/etc wrappers somehow...