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

**URL:** <https://users.rust-lang.org/t/refcell-and-oncecell-structures-recursive-always-works-but-iterative-does-not/128387>\
**Category:** code review\
**Created:** [April 16, 2025, 10:56pm UTC](https://users.rust-lang.org/t/refcell-and-oncecell-structures-recursive-always-works-but-iterative-does-not/128387 "2025-04-16T22:56:36Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![Arkarlos](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/arkarlos/32/46982_2.png) [@Arkarlos](https://users.rust-lang.org/u/Arkarlos)\
**Post date:** [April 16, 2025, 10:56pm UTC](https://users.rust-lang.org/t/refcell-and-oncecell-structures-recursive-always-works-but-iterative-does-not/128387/1 "2025-04-16T22:56:36Z")

</div>

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:

```rust
// 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`:

```rust
// 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.

```rust
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!!

---

<div class="post-metadata">

**Author:** ![kpreid](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/kpreid/32/22420_2.png) [@kpreid](https://users.rust-lang.org/u/kpreid)\
**Post date:** [April 16, 2025, 11:45pm UTC](https://users.rust-lang.org/t/refcell-and-oncecell-structures-recursive-always-works-but-iterative-does-not/128387/2 "2025-04-16T23:45:14Z")

</div>

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.

```rust
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`.

---

<div class="post-metadata">

**Author:** ![nerditation](https://avatars.discourse-cdn.com/v4/letter/n/e79b87/32.png) [@nerditation](https://users.rust-lang.org/u/nerditation)\
**Post date:** [April 16, 2025, 11:58pm UTC](https://users.rust-lang.org/t/refcell-and-oncecell-structures-recursive-always-works-but-iterative-does-not/128387/3 "2025-04-16T23:58:08Z")

</div>

> [@Arkarlos](#):
>
> Also, the recursive version works because it's not tail recursive and therefore all references live in their own stack frames?

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()`:

```diff
-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.

---

<div class="post-metadata">

**Author:** ![MOCKBA](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/mockba/32/41423_2.png) [@MOCKBA](https://users.rust-lang.org/u/MOCKBA)\
**Post date:** [April 17, 2025, 3:35am UTC](https://users.rust-lang.org/t/refcell-and-oncecell-structures-recursive-always-works-but-iterative-does-not/128387/4 "2025-04-17T03:35:05Z")

</div>

> [@nerditation](#):
>
> `link_opt =&mut RefCell::get_mut(Rc::get_mut(link).unwrap()).next;`

I need to try that.

---

<div class="post-metadata">

**Author:** ![nerditation](https://avatars.discourse-cdn.com/v4/letter/n/e79b87/32.png) [@nerditation](https://users.rust-lang.org/u/nerditation)\
**Post date:** [April 17, 2025, 4:06am UTC](https://users.rust-lang.org/t/refcell-and-oncecell-structures-recursive-always-works-but-iterative-does-not/128387/5 "2025-04-17T04:06:39Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Arkarlos](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/arkarlos/32/46982_2.png) [@Arkarlos](https://users.rust-lang.org/u/Arkarlos)\
**Post date:** [April 17, 2025, 6:33pm UTC](https://users.rust-lang.org/t/refcell-and-oncecell-structures-recursive-always-works-but-iterative-does-not/128387/6 "2025-04-17T18:33:52Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Arkarlos](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/arkarlos/32/46982_2.png) [@Arkarlos](https://users.rust-lang.org/u/Arkarlos)\
**Post date:** [April 17, 2025, 6:37pm UTC](https://users.rust-lang.org/t/refcell-and-oncecell-structures-recursive-always-works-but-iterative-does-not/128387/7 "2025-04-17T18:37:11Z")

</div>

Very elegant solution.Thanks!

---

<div class="post-metadata">

**Author:** ![system](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/system/32/51372_2.png) [@system](https://users.rust-lang.org/u/system)\
**Post date:** [July 16, 2025, 6:37pm UTC](https://users.rust-lang.org/t/refcell-and-oncecell-structures-recursive-always-works-but-iterative-does-not/128387/8 "2025-07-16T18:37:29Z")

</div>

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.