How can I iteratively traverse a tree built with Rc> while mutably matching on enums?

Question

I cannot find a way to do simple tree traversal without recursion within the guidelines of the borrow checker.

Advent of Code 2021 Day 18 has numbers that can be represented either by a pair of numbers or by a value (perfect for Rust enums). There are also parts of the problem where I'm using a stack to traverse the tree so I'm using Rc<RefCell<T>> to represent child nodes. This led me to the following representation:

use std::{cell::RefCell, rc::Rc};

enum Number {
    Pair(Rc<RefCell<Number>>, Rc<RefCell<Number>>),
    Value(u8),
}

I'm trying to make a function that updates the value of the left-most value in a Number. Writing the recursive version took a few tries but ended up working. However, I cannot get an iterative version to compile no matter what I try. The combination of matching the node and having to borrow with RefMut leads me to borrow/lifetime problems. This is what I'm trying to do:

fn propagate_left(mut node: &Rc<RefCell<Number>>, val: u8) {
    loop {
        let mut ref_mut = node.borrow_mut();
        match &mut (*ref_mut) {
            Number::Pair(left_node, _) => {
                node = left_node;
            }
            Number::Value(number_val) => {
                *number_val += val;
                return;
            }
        }
    }
}

error[E0597]: `ref_mut` does not live long enough
  --> src/lib.rs:11:22
   |
8  | fn propagate_left(mut node: &Rc<RefCell<Number>>, val: u8) {
   |                             - let's call the lifetime of this reference `'1`
...
11 |         match &mut (*ref_mut) {
   |                      ^^^^^^^ borrowed value does not live long enough
12 |             Number::Pair(left_node, _) => {
   |                          --------- assignment requires that `ref_mut` is borrowed for `'1`
...
20 |     }
   |     - `ref_mut` dropped here while still borrowed

Is there any way to make this work without using unsafe code or recursion?

I used a Vec for storage and indices in my structures to avoid this kind of problem in other puzzles but I wanted to try with references in this one.

I understand but the point of doing these puzzles is trying out different things in Rust. Here I wanted to do the traversal without recursion, using a stack which made using Box impractical. I'm sure there are other (simpler) ways of doing it, I'm just wondering if there is a solution to this specific problem without changing the premises. — Julien Hirel, Dec 21 '21 at 17:50
As I mentioned I'm using a stack in another part of the puzzle, and if I'm not mistaken I cannot copy the Box pointer to store it in my stack while I'm traversing. — Julien Hirel, Dec 21 '21 at 17:58
*using a stack in another part of the puzzle* — we cannot help with code that isn't a part of the question. If you have limitations that need to be respected, they need to be included here, as code instead of prose. Otherwise you will get answers that aren't acceptable. — Shepmaster, Dec 21 '21 at 18:00
Yes, thank you for the answer ! I was just wondering if I was missing an obvious way to write this without changing the data representation or using recursion (I'm aware these solve the issue). Sorry if this seems like a simple syntax problem. If you add your code as an answer I can accept it — Julien Hirel, Dec 21 '21 at 18:15

score 2 · Accepted Answer · answered Dec 21 '21 at 18:24

The problem with your attempt is that the lifetime of the return value of node.borrow_mut() is tied to node, but you are attempting to store that result into a variable that has a caller-provided lifetime. When the current iteration's borrow_mut() ends, the reference (used by left_node) expires and you cannot store something with a shorter lifetime into a variable with a longer lifetime — the entire point of memory safety.

A workaround is to avoid concurrently using references (&) and reference counting (Rc). Using only Rc, you can clone the child and replace the temporary variable:

use std::{cell::RefCell, rc::Rc};

enum Number {
    Pair(Rc<RefCell<Number>>, Rc<RefCell<Number>>),
    Value(u8),
}

fn propagate_left(mut node: Rc<RefCell<Number>>, val: u8) {
    loop {
        let next = match &mut *node.borrow_mut() {
            Number::Pair(left_node, _) => Rc::clone(left_node),
            Number::Value(number_val) => {
                *number_val += val;
                return;
            }
        };

        node = next;
    }
}

You can also use only references and avoid Rc / RefCell completely:

enum Number {
    Pair(Box<Number>, Box<Number>),
    Value(u8),
}

fn propagate_left(mut node: &mut Number, val: u8) {
    loop {
        match node {
            Number::Pair(left_node, _) => {
                node = left_node;
            }
            Number::Value(number_val) => {
                *number_val += val;
                return;
            }
        };
    }
}

How can I iteratively traverse a tree built with Rc> while mutably matching on enums?

1 Answers1