It it possible to extract and return &T from Option:Rc:RefCell:Box:Smthg?

help
1

Hello, Option<Rc<RefCell<Box strikes again.

I want somehow extract and return &T from Option<Rc<RefCell<Box<Node>>>>. I managed to do it with Option<Rc<RefCell<Box>>>, but looks like additional wrapper breaks everything. Is this even possible? Thanks.

Simplified code:

#[derive(Debug)]
struct Node<T: Ord> {
    pub value: T,
    left: NodePtr<T>,
    right: NodePtr<T>,
    parent: NodePtr<T>
}

type NodePtr<T> = Option<Rc<RefCell<Box<Node<T>>>>>;

#[derive(Debug)]
struct BinaryTree<T: Ord> {
    root: NodePtr<T>,
}

#[derive(Debug)]
struct A<'a, T: Ord> {
    stack: Vec<&'a NodePtr<T>>,
    current: &'a NodePtr<T>,
}

impl<'a, T: 'a + Ord> Iterator for A<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        return match self.current {
            Some(ref root) => {
                Some(&RefCell::borrow(Rc::borrow(&root)).value) // ????
            },

            None => None,
        }
    }
}

playground

2

I might not have answers, but I do have questions; questions like, "why would you want to do this besides why not?" and "do you keep a set of Russian dolls by your bedside?", and "oh weird, I wonder why that doesn't work?"

Towards that last one, I suppose we have to think about memory allocation.
So it looks like the thing that works is four nested smart pointers, "Option<Rc<RefCell<Box"
And the thing that didn't work was 4 nested smart pointers with the innermost one pointing at a Node, which at least hypothetically, Box should be able to abstract for you. If we head on over to the Box store, we see that Box should allocate memory on the Heap for your Node thingy.

What I'm curious about is why that shouldn't work, since that seems to be the breaking point. And that's about where I throw in the towel.

3

You can't*, because it's unsafe per borrow checking rules. If you return "bare" reference, it means you haven't kept the lock of RefCell locked, and therefore the value you're referencing is might be modified or destroyed at any moment.

You can return Rc, because it keeps ownership of the value. You can return Ref (not RefCell, but the inner one), because it holds both the reference and the lock.

If you can use privacy of the implementation to guarantee there's no way to get hold of a Node other than via your abstraction, then you could use unsafe to force that through, as long as you explain to the borrow checker that the reference you're giving out is borrowed from the wrapper object for the tree, so it will stop it from being mutated while the reference is live. But then for the same reason you could skip Rc and RefCell too, because you can control ownership and usage of the nodes.

*) the exception is if you have exclusive access to the value, and then both Rc and RefCell have get_mut shortcut that bypasses refcounting and locking. In tree structures it's rarely practical to do that.

BTW: Use std::collections::BTreeSet. It's going to be faster than a binary tree, and already does everything, safely.

2 Likes
4

With regards to RefCell and not being able to keep it locked without a Ref, that's not entirely true. It 'just' requires truly leaking memory to create a guard that lives at least as long as the original reference.

fn leak(r: &RefCell<T>) -> Option<&T> {
    let guard = r.try_borrow().ok()?;
    let leaked = Box::leak(Box::new(guard));
    Some(&*leaked)
}

There's a recent unstable feature, cell_leak, to allow this without leaking a box. However, in both of these instances it will not be possible to acquire a mutable reference to the contained value again except through acquiring &mut RefCell and calling RefCell::get_mut.

The above code though is evidence that it might be sound to manually use unsafe to extend the lifetime when forgetting the Ref as well. I'll not demonstrate that code though as I don't think it's very a good idea to use it.

5

Option and RefCell are not smart pointers; if they were, you could simply dereference them.

1 Like
6

It does not demonstrate that. Your code above will leave the ref cell borrowed forever, so you can never mutably borrow it after running that function.

2 Likes
7

That was worded weirdly and my intent did not get across.

[..] when forgetting the Ref as well.

Forgetting the Ref will do precisely that as well. It will also leave the ref cell borrowed and does not allow mutably borrowing it after. In fact, it's precisely the already accepted implementation of the unstable feature :wink:

pub fn leak(orig: Ref<'b, T>) -> &'b T {
    // By forgetting this Ref we ensure that the borrow counter in the RefCell never goes back
    // to UNUSED again. No further mutable references can be created from the original cell.
    mem::forget(orig.borrow);
    orig.value
}

A user defined unsafe equivalent would be:

pub fn leak(orig: Ref<'b, T>) -> &'b T {
    let orig = core::mem::ManuallyDrop::new(orig);
    // this transmute extends the lifetime of the borrowed reference. We 
    // borrow from the referenced cell and dropping the guard is akin to
    // never releasing our original claim to that borrow.
    unsafe { std::transmute(&*orig) }
}
8

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.