The mutable reference to node.links is invalidated after this function call, but the function stores it in self.root, right? I think you should use core::ptr::addr_of_mut!(node.links) instead. Note that the let node = unsafe { &mut *Box::into_raw(node) }; is also invalidated once this function returns. So maybe let node = Box::into_raw(node); and then addr_of_mut!((*node).links)? The &mut self.root is fine if there are no pointers to self.root only pointers stored in self.root.

I think I need to update my mental model here.

What is invalidating node.links? How would using addr_of_mut!(node.links) avoid this invalidation?

Thinking a bit more about this, this &mut node.links doesn't get invalidated, but the previous &mut node.links does due to this &mut node.links. addr_of_mut!(node.links) avoids this problem by directly creating a raw pointer without an intermediate mutable reference. It is valid to have multiple raw pointers to the same value, but creating one mutable reference invalidates all other references and pointers.

What model are you using to determine what gets invalidated?

I quickly read the model in the stacked borrows paper and my understanding is that the code is ok now. The reason is that the borrow stack for each byte that makes up node contains: [..., SharedRW, Unique(n), ...], where SharedRW refers to the raw pointer returned by into_raw() and Unique(n) refers to the mutable reference created on line 248. So any new raw references that I create in the function can still be used after the function returns because they will be resolved by the SharedRW entry (until I call from_raw(), which will pop that SharedRW entry) because raw pointers are not "tagged".

IOW, I don't agree with your claim that "creating one mutable reference invalidates all other pointers" -- my understanding is that it invalidates all other pointers on top of it in the borrow stack. Pointers below it continue to be valid until something else pops them off.

I am new to stacked borrows though, so my understanding may be wrong. Where does it not match yours?

I quickly read the model in the stacked borrows paper and my understanding is that the code is ok now. The reason is that the borrow stack for each byte that makes up node contains: [..., SharedRW, Unique(n), ...], where SharedRW refers to the raw pointer returned by into_raw() and Unique(n) refers to the mutable reference created on line 248. So any new raw references that I create in the function can still be used after the function returns because they will be resolved by the SharedRW entry (until I call from_raw(), which will pop that SharedRW entry) because raw pointers are not "tagged".

You will end up with SharedRW(k), Unique(l), SharedRW(m) in this case. It is fine with the default options of miri as the raw pointer can resolve to either SharedRW, but it isn't when -Zmiri-track-raw-pointers as it will only resolve to SharedRW(m) which is popped of the borrow stack at the next &mut item.links in addition SharedRW(m) only covers links and not the whole item, so accessing the rest of the item through it is not allowed.

IOW, I don't agree with your claim that "creating one mutable reference invalidates all other pointers" -- my understanding is that it invalidates all other pointers on top of it in the borrow stack. Pointers below it continue to be valid until something else pops them off.

Yeah, I was simplifying a bit. Maybe a bit too much.

You will end up with SharedRW(k), Unique(l), SharedRW(m) in this case. It is fine with the default options of miri as the raw pointer can resolve to either SharedRW, but it isn't when -Zmiri-track-raw-pointers as it will only resolve to SharedRW(m) which is popped of the borrow stack at the next &mut item.links in addition SharedRW(m) only covers links and not the whole item, so accessing the rest of the item through it is not allowed.

From miri's readme about -Zmiri-track-raw-pointers: This can make valid code fail to pass the checks. So I'm not so concerned about it, I'm concerned about the code correctness wrt the model. Do we agree that it is correct (wrt the model)?

Part of the reason I declared a &mut Node was to avoid having to add more SAFETY justifications in each of its uses (4 other places), but now I realise that 3 of them are &mut node.links so I can avoid repeating the justification by storing a raw pointer in a variable and reusing it.

I'll make this change and upload it shortly.

The new version is UB free I think.