RefCell and OnceCell structures. Recursive always works but iterative does not?

code review
1

I am subjecting myself to some torture in the form of implementing safe data structures to better learn the language, but I think I'm either pushing the limits of safe rust or my understanding of the language.

I am experimenting with RefCell, OnceCell, Rc and Weak by implementing linked lists with head access that only support pushing to the tail, that is, lists that must find their tails in order to grow them. Both with iterative and recursive approaches.

Consider this list made with OnceCell and a node that only contains a reference to the next element:

// SINGLY LIST MADE WITH ONCECELL ----------------------------------------------
struct SinglyOnceNode {
    next: Rc<OnceCell<SinglyOnceNode>>,
}

impl SinglyOnceNode {
    fn new() -> Self {
        Self { next: Rc::new(OnceCell::new()) }
    }
}


pub struct SinglyOnceList {
    head: Rc<OnceCell<SinglyOnceNode>>,
}

impl SinglyOnceList {
    pub fn new() -> Self {
        Self { head: Rc::new(OnceCell::new()) }
    }

    pub fn push_iterative(&self) {
        let mut link = &self.head;
        while let Some(node) = link.get() {
            link = &node.next;
        }
        let _ = link.set(SinglyOnceNode::new());
    }

    pub fn push_recursive(&self) {
        Self::rec(&self.head);
    }

    fn rec(link: &Rc<OnceCell<SinglyOnceNode>>) {
        match link.get() {
            None => { let _ = link.set(SinglyOnceNode::new()); },
            Some(node) => Self::rec(&node.next),
        }
    }
}

This works exactly as expected, a & shared reference is returned to the node and everything is fine.
Now consider the same list but implemented with RefCell:

// SINGLY LIST MADE WITH REFCELL -----------------------------------------------
struct SinglyRefNode {
    next: Option<Rc<RefCell<SinglyRefNode>>>,
}

impl SinglyRefNode {
    fn new() -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Self { next: None }))
    }
}


pub struct SinglyRefList {
    head: Option<Rc<RefCell<SinglyRefNode>>>,
}

impl SinglyRefList {
    pub fn new() -> Self {
        Self { head: None }
    }

    pub fn push_iterative(&mut self) {
        let mut link_opt  = &mut self.head;
        while let Some(link) = link_opt {
            link_opt = &mut link.borrow_mut().next; // <------------ DOESN'T WORK
        }
        link_opt.replace(SinglyRefNode::new());
    }

    pub fn push_recursive(&mut self) {
        Self::rec(&mut self.head);
    }

    fn rec(link: &mut Option<Rc<RefCell<SinglyRefNode>>>) {
        match link {
            None => { link.replace(SinglyRefNode::new()); },
            Some(link) => Self::rec(&mut link.borrow_mut().next),
        }
    }
}

The recursive version works perfectly fine, but the iterative version either doesn't work or I am incapable of making it work.

error[E0716]: temporary value dropped while borrowed
  --> src/main.rs:70:29
   |
69 |         while let Some(link) = link_opt {
   |                                -------- borrow later used here
70 |             link_opt = &mut link.borrow_mut().next; // DOESN'T WORK
   |                             ^^^^^^^^^^^^^^^^^     - temporary value is freed at the end of this statement
   |                             |
   |                             creates a temporary value which is freed while still in use
   |
   = note: consider using a `let` binding to create a longer lived value

I have tried to solve it with the advice but I've been completely incapable. What is the problem here? My understanding by reading "Too Many Linked Lists" Is that .borrow() and .borrow_mut() create a "tunnel" of references and if the tunnel is cut none of the references down the line will work. Am I wrong?.

Also, the recursive version works because it's not tail recursive and therefore all references live in their own stack frames?.

Many thanks!!

2

Each call to link.borrow_mut() creates and returns a RefMut guard object, which maintains the “currently borrowed” state of the cell. You have to keep the guard alive until you are done. Right now, you're not doing that, by immediately taking a borrow of a field of it and not storing the guard anywhere. The recursive version does it automatically because it calls rec before the temporary values from the rest of the expression expire.

But, even if you fixed that, you'd still have the problem that, as long as you work with borrows, you have to keep all of the involved guards alive. This happens naturally in a recursive implementation, but is difficult in an iterative one; it's better to take advantage of your Rc, which lets you keep access to a node without keeping its parents, and so the iterative push can execute in constant space.

pub fn push_iterative(&mut self) {
    match self.head.clone() {
        None => {
            self.head = Some(SinglyRefNode::new());
        }
        Some(mut link) => {
            loop {
                let mut guard = link.borrow_mut();
                if let Some(next) = guard.next.clone() {
                    drop(guard); // drops the borrow and allows assigning to `link`
                    link = next;
                } else {
                    guard.next = Some(SinglyRefNode::new());
                    break;
                }
            }
        }
    }
}

Note that modifying the head has to be done differently because that Option is not inside of any RefCell.

3 Likes
3

recursion works because each time it recurses, you create a shorter lifetime from RefCell::borrow_mut(), it doesn't matter if it's tail recursion in this case, since you don't return any thing. if you tried to return some borrow, then the recursion won't work either.

it is not possible with in the iterative code to create a shorter lifetime for each iteration.

this is not to say, you cannot do it iteratively. the problem is RefCell::borrow_mut() will "shrink" the lifetime. the solution is RefCell::get_mut() (combined with Rc::get_mut():

-link_opt = &mut link.borrow_mut().next; // <------------ DOESN'T WORK
+link_opt = &mut RefCell::get_mut(Rc::get_mut(link).unwrap()).next;

note the unwrap() above could panic if some other code is holding a Rc. this behaves differently than RefCell::borrow_mut(), where it would only panic if other code called RefCell::borrow() or RefCell::borrow_mut(), NOT if they are holding a Rc but without borrowing.

3 Likes
4

I need to try that.

5

you can eliminate the runtime overhead of interior mutability when exclusivity is guaranteed at compile time by the type. so all the standard cell types (including Cell, RefCell, and even UnsafeCell) have a get_mut() method/associated function which is a zero-cost abstraction and completely safe.

types like OnceCell and LazyCell also have get_mut(), though they serve different purpose and have nothing to do with interior mutability, also, LazyCell::get_mut() is unstable yet.

this is also true for their thread safe counterparts, i.e. RwLock::get_mut(), Mutex::get_mut(), though there's a slight complication: these are fallible due to their concurrent nature, namely, RwLock and Mutex could be poisoned.

6

That's very insightful, thank you for your time!

7

Very elegant solution.Thanks!