对可变二叉树的递归：`已经借用：BorrowMutError`

Question

我从 Vec 排序节点开始，然后使用此排序 link 这些节点一起形成二叉树，然后返回基本结构

// 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>
}

最后得到由上述Struct形成的二叉树。在这一点上，这些 Struct 是唯一拥有的，所以我认为我可以从使用 Rc<RefCell<Struct>> 转换为 RefCell<Struct>（认为 Box<Struct> 由于内部可变性而不起作用？ )，但我不确定这对我遇到的问题有何帮助或是否有帮助。

在此之后，我需要以一种新颖的方式遍历 Structs，并在整个递归过程中改变属于各种 Structs 的各种 symbols，通过调用.pop_front().

我当前执行此操作会导致 thread 'main' panicked at 'already borrowed: BorrowMutError'.

的各种实例

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

它的功能（请原谅逻辑复杂）：

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));
        }
    }
}

我考虑过使用 Arc<Mutex<Struct>> 来代替遍历，但考虑到它不是多线程的，我认为它没有必要？

我想我可能在这里遗漏了一个相对简单的想法，非常感谢任何帮助。

如果我在问题中遗漏了任何内容，请发表评论，我会尝试添加。

Answer 1

当您在 RefCell 上调用 borrow 或 borrow_mut 时，会创建一个守卫对象（Ref 或 RefMut）以授予对内在价值，只要它存在。这个守卫将锁定 RefCell 直到它超出范围并被销毁。让我们看一下 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

在第一行，例如，row.borrow() returns a Ref<Struct>。这个 Ref 不能立即删除，因为 superscript_row 在 if let 正文中借用了它。所以它一直都活着——直到最后的 }.

这是递归调用traverse_scripts的问题，因为在整个递归调用期间借用了Struct。任何试图在调用堆栈更深的地方借用相同的 Struct 的可变方法都将失败。（不可变地借用它仍然有效。）

第二行superscript_row是借用的。这有同样的问题，但它还有一个更直接的问题：它在同一函数的后面可变地借用，甚至在命中递归调用之前。 borrow_mut 永远不会成功，因为那时 superscript_row 总是已经被借用了。

要解决这两个问题，我们将做两件事：

将每个 Ref 或 RefMut 守卫存储在其自己的变量中并重新使用该守卫，而不是在同一个变量上调用 borrow() 或 borrow_mut()再次.
在递归之前，drop 每个仍然存在的守卫，以便在递归调用中仍然没有借用任何东西。

重写后的部分可能如下所示：

{ // 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.

这看起来很复杂，因为它很复杂。在改变数据结构的同时遍历它是错误的常见来源（在大多数语言中，不仅仅是 Rust）。看起来，至少在 traverse_scripts 中，需要突变的唯一原因是在 symbols 上调用 pop_front，所以如果你可以重新设计数据结构，使得只有 symbols在 RefCell 中，您可以仅使用 & 引用进行遍历，这样会容易得多。另一种常见的方法是编写 return 新数据结构的函数，而不是就地改变它们。

对可变二叉树的递归：`已经借用：BorrowMutError`

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

memory-management

rust

borrowing