Recursion over a mutable binary tree: `already borrowed: BorrowMutError`

Question

I'm beginning with a Vec of sorted nodes, then using this sorting to link these nodes together in a binary tree and then returning the base struct

// Test name
#[derive(Clone)]
struct Struct {
    parent: Option<Rc<RefCell<Struct>>>,
    superscript: Option<Rc<RefCell<Struct>>>,
    subscript: Option<Rc<RefCell<Struct>>>,
    height: u32,
    center: u32,
    symbols: VecDeque<u8>
}

Ending up with a binary tree formed by the above Structs. At this point, these Structs are uniquely owned, so I think I could convert from using Rc<RefCell<Struct>> to RefCell<Struct> (think Box<Struct> doesn't work due to internal mutability?), but I'm not sure how or if this helps with the problem I'm encountering.

After this, I need to iterate in a novel manner through the Structs, and mutate the various symbols belonging to the various Structs throughout the recursion, via calling .pop_front().

My current implementation doing this leads to various instances of thread 'main' panicked at 'already borrowed: BorrowMutError'.

Playground link: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=636c93088f5a431d0d430d42283348f3

The function for it (please excuse the convoluted logic):

fn traverse_scripts(row: Rc<RefCell<Struct>>) {
    if let Some(superscript_row) = &row.borrow().superscript {
        if let Some(superscript_symbol) = superscript_row.borrow().symbols.front() {
            if let Some(current_row_symbol) = row.borrow().symbols.front()  {
                if superscript_symbol < current_row_symbol {
                    println!("^{{{}",*superscript_symbol);
                    superscript_row.borrow_mut().symbols.pop_front();
                    traverse_scripts(Rc::clone(superscript_row));
                }
            }
            else {
                println!("^{{{}",*superscript_symbol);
                superscript_row.borrow_mut().symbols.pop_front();
                traverse_scripts(Rc::clone(superscript_row));
            }
        }
    }

    if let Some(subscript_row) = &row.borrow().subscript {
        if let Some(subscript_symbol) = subscript_row.borrow().symbols.front() {
            if let Some(current_row_symbol) = row.borrow().symbols.front() {
                if subscript_symbol < current_row_symbol  {
                    print!("_{{{}",*subscript_symbol);
                    subscript_row.borrow_mut().symbols.pop_front();
                    traverse_scripts(Rc::clone(subscript_row));
                }
            }
            else {
                print!("_{{{}",*subscript_symbol);
                subscript_row.borrow_mut().symbols.pop_front();
                traverse_scripts(Rc::clone(subscript_row));
            }
        }
    }

    if let Some(current_row_symbol) = row.borrow().symbols.front()  {
        if let Some(parent_row) = &row.borrow().parent {
            if let Some(parent_symbol) = parent_row.borrow().symbols.front() {
                if current_row_symbol < parent_symbol {
                    print!(" {}",*current_row_symbol);
                    row.borrow_mut().symbols.pop_front();
                    traverse_scripts(Rc::clone(&row));
                }
            }
        }
        else {
            print!(" {}",*current_row_symbol);
            row.borrow_mut().symbols.pop_front();
            traverse_scripts(Rc::clone(&row));
        }
    }

    if let Some(parent_row) = &row.borrow().parent {
        if let Some(parent_symbol) = parent_row.borrow().symbols.front() {
            print!("}} {}",*parent_symbol);
            row.borrow_mut().symbols.pop_front();
            traverse_scripts(Rc::clone(parent_row));
        } else {
            print!("}}");
            traverse_scripts(Rc::clone(parent_row));
        }
    }
}

I've considered using Arc<Mutex<Struct>> instead for the traversal, but given its not multi-threaded I don't think it's neccessary?

I imagine I might be missing a relatively simple idea here, I would really appreciate any help.

If I've missed anything in my question please drop a comment and I'll try to add it.

Answer 1

When you call borrow or borrow_mut on a RefCell, a guard object (Ref or RefMut) is created that grants access to the inner value for as long as it exists. This guard will lock the RefCell until it goes out of scope and is destroyed. Let's look at a portion of traverse_scripts:

if let Some(superscript_row) = &row.borrow().superscript { // row is borrowed
    if let Some(superscript_symbol) = superscript_row.borrow().symbols.front() { // superscript_row is borrowed
        if let Some(current_row_symbol) = row.borrow().symbols.front() { // row is borrowed again
            if superscript_symbol < current_row_symbol {
                println!("^{{{}", *superscript_symbol);
                superscript_row.borrow_mut().symbols.pop_front(); // superscript_row is borrowed mutably (ERROR)
                traverse_scripts(Rc::clone(superscript_row)); // recursive call while row and superscript_row are borrowed (ERROR)
            }
        } else {
            println!("^{{{}", *superscript_symbol);
            superscript_row.borrow_mut().symbols.pop_front(); // superscript_row is borrowed mutably (ERROR)
            traverse_scripts(Rc::clone(superscript_row)); // recursive call while row and superscript_row are borrowed (ERROR)
        } // row is no longer borrowed twice
    } // superscript_row is no longer borrowed
} // row is no longer borrowed

In the first line, for example, row.borrow() returns a Ref<Struct>. This Ref can't be dropped immediately, because it's being borrowed during the if let body by superscript_row. So it stays alive that whole time -- until the final }.

This is a problem for recursively calling traverse_scripts because the Struct is borrowed during the entire recursive call. Any attempt to borrow the same Struct mutably deeper in the call stack will fail. (Borrowing it immutably does still work.)

In the second line superscript_row is borrowed. This has the same problem, but it also has a more immediate one: it's borrowed mutably later in the same function, even before hitting the recursive call. That borrow_mut can never succeed because superscript_row is always already borrowed at that point.

To fix both problems, we'll do two things:

1. Store each Ref or RefMut guard in a variable of its own and re-use that guard, instead of calling borrow() or borrow_mut() on the same variable again.
2. Before recursing, drop each of the still-living guards so that nothing is still borrowed inside the recursive call.

Here's what that section might look like rewritten:

{ // This scope will constrain the lifetime of row_ref
    let row_ref = row.borrow();
    if let Some(superscript_row) = &row_ref.superscript {
        let mut child = superscript_row.borrow_mut(); // use borrow_mut here because we know we'll need it later
        if let Some(superscript_symbol) = child.symbols.front() {
            if let Some(current_row_symbol) = row_ref.symbols.front() {
                if superscript_symbol < current_row_symbol {
                    println!("^{{{}", *superscript_symbol);
                    child.symbols.pop_front();
                    drop(child); // child is no longer needed, so drop it before recursing
                    // Since superscript_row borrows from row_ref, we must Rc::clone it before
                    // dropping row_ref so that we can still pass it to traverse_scripts.
                    let superscript_row = Rc::clone(superscript_row);
                    drop(row_ref); // row_ref is no longer needed, so drop it before recursing
                    traverse_scripts(superscript_row);
                }
            } else {
                println!("^{{{}", *superscript_symbol);
                child.symbols.pop_front();
                // see comments earlier
                drop(child);
                let superscript_row = Rc::clone(superscript_row);
                drop(row_ref);
                traverse_scripts(superscript_row);
            }
        }
    } // child is dropped here (if it wasn't already). superscript_row is no longer borrowed
} // row_ref is dropped here (if it wasn't already). row is no longer borrowed

Full-program playground.

This looks complicated because it is complicated. Traversing over a data structure while mutating it is a common source of bugs (in most languages, not just Rust). It looks like, in traverse_scripts at least, the only reason for needing mutation is to call pop_front on symbols, so if you can redesign the data structure such that only symbols is in a RefCell, you could do the traversal with only & references, which would be much easier. Another common approach is to write functions that return new data structures instead of mutating them in place.