Can you break the lift?

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)
}

One big problem I can see is that 'a is choosen by the caller. What if it chooses 'static? I would change the signature to something like:

    fn lift<R, F>(root: R, fun: F) -> R
    where
        F: for<'a> FnOnce(&'a R) -> &'a mut R;

The next problem is its actual usefulness. Tthere aren't many ways to get an &'a mut R from an &'a R. The only ways I can think of is calling RefCell::borrow_mut and then RefMut::leaking it, or using Box::leak to get a &'static mut R, both of which aren't really viable. In fact I double this snippet will ever work:

If that .borrow_mut() is like the one of an RefCell then this won't work, because the guard will be dropped at the end of the closure.

1 Like

It is useful, with GhostCell, at least, since then the borrow's lifetime is not tied to a temporary :wink:

That is indeed problematic. It allows exfiltration of the reference, which would be unsafe.

I'm still not quite comfortable with for<'a>.

I would expect that for<'a> would essentially require R: 'static:

  • &'a mut R must be valid for all 'a.
  • &'a mut R is only valid if R: 'a.
  • for<'a> means that 'a could be 'static.

I decided to try it, though, and it works:

use std::{
    cell::UnsafeCell,
    mem,
};

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)
}

struct Node<T> {
    value: T,
    next: UnsafeCell<Option<Box<Self>>>,
}

fn main() {
    let hello = "Hello".to_string();

    let node = Box::new(Node {
        value: &hello,
        next: UnsafeCell::new(None),
    });

    println!("{:?}", node.value);

    let previous = lift(Some(node), |some_node| {
        let node = some_node.as_ref().unwrap();
        unsafe { &mut *node.next.get() }
    });

    assert!(previous.is_none());
}

Note: this is going to leak; by "it works" I meant MIRI was happy enough with it. It only complained about the leak.

And I'm honestly not sure why Node can contain a local reference (hence not 'static) in this case.

I'm going to go ahead and edit the post with the new version of lift; thanks @SkiFire13 .

With GhostCell it could theoretically work, however I think the for<'a> approach would be too restrictive for it since you would need a &'a mut GhostToken<'id> for any 'a that the closure might be called with.

AFAIK for<'a> automatically restricts the set of possible 'a so that the trait/bound is well formed. In other words, it's not R that has to "adapt" to any 'a, but it's the set of possible 'as that is adapted to R.