So today I realised that a line of my code is needed to keep Miri with Stacked borrows happy, but is not required for Tree borrows
fn lower_bound<Q>(map: &mut BTreeMap<K, V>, bound: Bound<&Q>) -> Self
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
unsafe {
// Converting map to raw pointer here is necessary to keep Miri happy
// although not when using MIRIFLAGS=-Zmiri-tree-borrows.
let map: *mut BTreeMap<K, V> = map;
let mut s = Self::make(map);
s.push_lower(&mut (*map).tree, bound);
s
}
}
I have been reading about Tree borrows, but my senile brain while registering the general idea is having trouble coping with the details. I might manage to grasp it eventually. It isn't very clear to me whether Tree borrows or Stacked borrows (or something else) is most likely to become the eventual standard. What is your guess?
[ My help request I suppose is for help in understanding better why the code above fails for stacked borrows but not for tree borrows... which I have not fully grasped yet. ]
I don't think either is a slam-dunk; my guess is something between the two.
Each of them allow things the other does not, but also disallows things the other does not. Until decisions are made more formally, I recommend satisfying both.
(Sorry for not analyzing why your code apparently works in one model but not the other.)
I suspect the reason TB accepts the code without the pre conversion to raw pointer where SB doesn't has to do with TB being lazier in general. If I'm guessing correctly, it's essentially due to TB's universal application of the "two-phase" borrow concept; in SB, I expect what roughly happens is that doing &mut (*map).tree invalidates the pointer you used to make the cursor, but with TB, it ends up disallowed to access (*map).tree but still able to modify (*map).len.
When you create the raw pointer first, the &mut (*map).tree reference ends up derived from the self.map pointer, so doesn't invalidate it. I think the "best" way to write this snippet this might be
let mut this = Self::make(map);
// SAFETY: We just initialized this.map from a reference.
// Derive the tree ref from it so it remains valid later.
let root = unsafe { &mut (*this.map).tree };
this.push_lower(root, bound);
this
I'm not super certain on the soundness of the private helpers (at a minimum Self::make should be unsafe or accept &mut since the pointer gets dereferenced) since there's an implicit lifetime assumption that any &mut Tree are subborrows of self.map for the purpose of lifetime extension and whether access to (*self.map).tree can invalidate pointers on your stack. The pub API soundness is what matters most, but many/most of the helpers probably should be unsafe.