Or otherwise said, is the lift
function presented below actually safe?
What's is this function useful for?
I am trying to write a doubly linked-list, and found myself hitting a wall when I tried to implement the append function. For a simplified view of the code, imagine that a node in the list is:
struct List<T>(Option<(HalfPtr<T>, HalfPtr<T>)>);
struct Node<T> {
value: T,
prev: Option<HalfPtr<T>>, // None if head.
next: Option<HalfPtr<T>>, // None if tail.
}
type HalfPtr<T> = SomeRc<SomeCell<Node<T>>>;
Now, in the course of the append
function, you are provided two lists, and you should "steal" the content of the second and append it to the first:
fn append(&mut self, other: &mut Self) {
// Let's cut the interesting case: both are non-empty.
let (new_head, mid_tail) = self.0.take().unwrap();
let (mid_head, new_tail) = other.0.take().unwrap();
mid_tail.borrow_mut().next = Some(mid_head);
mid_head.borrow_mut().prev = Some(mid_tail); // Oh wait, mid_head was moved!
self.0 = Some((new_head, new_tail));
}
The realization here is that after the lists are connected, you don't retain any pointer to the "mid" nodes. This is why you hand-over mid_head
, and would like to hand-over mid_tail
. But how?
The idea I've been toying with is to use a function I've called lift
, and declared as such:
fn lift<R, F>(root: R, fun: F) -> R
where
F: for<'a> FnOnce(&'a R) -> &'a mut R;
Which is used so:
lift(mid_tail, |mid_tail| {
let mid_head = mid_tail.borrow().prev;
mid_head.borrow_mut()
});
The exact definition is of course, unsafe
:
fn lift<R, F>(root: R, fun: F) -> R
where
F: for<'a> FnOnce(&'a R) -> &'a mut R,
{
let slot = fun(&root) as *mut R;
mem::replace(unsafe { &mut *slot }, root)
}
And I've been wondering whether the function is, actually, safe.
The key observation here is that the lifetime of slot
is, ultimately, tied down to the lifetime of root
-- it's derived from it -- and the definition of lift
ensures that the lifetime of root
outlives that of slot
hence it looks fine.
But I am wondering whether it is fine.
MIRI seems fine with this program, but didn't take the issue in the broken version either so...
Note: previous version, broken by @SkyFire13 who realized that allowing the caller to specify the reference allowed exfiltrating the reference:
fn lift<'a, R, F>(root: R, fun: F) -> R
where
F: FnOnce(&'a R) -> &'a mut R,
{
// Circumvent the borrow-checker; we're going to move `root` after borrowing from it.
let reference = &root as *const R;
let slot = fun(unsafe { *reference });
mem::replace(slot, root)
}