实现可变树结构

Question

我正在尝试动态构建树并在下降期间、在叶子上和备份期间修改树的部分内容。我相信我对如何在 Rust 中做这样的事情存在根本性的误解。这是我的代码：

struct Node {
    children: Vec<Node>,
    data: usize,
}

impl Node {
    pub fn new() -> Node {
        Node {
            children: vec![],
            data: 0,
        }
    }

    pub fn expand(&mut self) {
        self.children = vec![Node::new(), Node::new()];
    }

    pub fn is_leaf(&self) -> bool {
        self.children.len() == 0
    }
}

pub fn main() {
    let mut root = Node::new();
    for _ in 0..10 {
        let mut node = &mut root;
        let mut path = vec![];
        // Descend and potential modify the node in the process
        while !node.is_leaf() {
            let index = 0;
            path.push(index);
            node = &mut node.children[index];
        }
        // Do something to the leaf node
        node.expand();
        // Do something during "backup" (in my case it doesn't matter
        // in which order the modification is happening).
        node = &mut root;
        for &i in path.iter() {
            node.data += 1;
            node = &mut node.children[i];
        }
    }
}

这是来自编译器的错误消息：

error[E0502]: cannot borrow `*node` as immutable because `node.children` is also borrowed as mutable
  --> src/main.rs:29:16
   |
29 |         while !node.is_leaf() {
   |                ^^^^ immutable borrow occurs here
...
32 |             node = &mut node.children[index];
   |                         ------------- mutable borrow occurs here
...
43 |     }
   |     - mutable borrow ends here

error[E0506]: cannot assign to `node` because it is borrowed
  --> src/main.rs:32:13
   |
32 |             node = &mut node.children[index];
   |             ^^^^^^^^^^^^-------------^^^^^^^
   |             |           |
   |             |           borrow of `node` occurs here
   |             assignment to borrowed `node` occurs here

error[E0499]: cannot borrow `node.children` as mutable more than once at a time
  --> src/main.rs:32:25
   |
32 |             node = &mut node.children[index];
   |                         ^^^^^^^^^^^^^
   |                         |
   |                         second mutable borrow occurs here
   |                         first mutable borrow occurs here
...
43 |     }
   |     - first borrow ends here

error[E0499]: cannot borrow `*node` as mutable more than once at a time
  --> src/main.rs:35:9
   |
32 |             node = &mut node.children[index];
   |                         ------------- first mutable borrow occurs here
...
35 |         node.expand();
   |         ^^^^ second mutable borrow occurs here
...
43 |     }
   |     - first borrow ends here

error[E0506]: cannot assign to `node` because it is borrowed
  --> src/main.rs:38:9
   |
32 |             node = &mut node.children[index];
   |                         ------------- borrow of `node` occurs here
...
38 |         node = &mut root;
   |         ^^^^^^^^^^^^^^^^ assignment to borrowed `node` occurs here

error[E0499]: cannot borrow `root` as mutable more than once at a time
  --> src/main.rs:38:21
   |
26 |         let mut node = &mut root;
   |                             ---- first mutable borrow occurs here
...
38 |         node = &mut root;
   |                     ^^^^ second mutable borrow occurs here
...
43 |     }
   |     - first borrow ends here

error[E0506]: cannot assign to `node` because it is borrowed
  --> src/main.rs:41:13
   |
32 |             node = &mut node.children[index];
   |                         ------------- borrow of `node` occurs here
...
41 |             node = &mut node.children[i];
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `node` occurs here

error[E0499]: cannot borrow `node.children` as mutable more than once at a time
  --> src/main.rs:41:25
   |
32 |             node = &mut node.children[index];
   |                         ------------- first mutable borrow occurs here
...
41 |             node = &mut node.children[i];
   |                         ^^^^^^^^^^^^^ second mutable borrow occurs here
42 |         }
43 |     }
   |     - first borrow ends here

Answer 1

这里同时发生了几件事。简单的答案是：您正在尝试为同一项目创建多个可变借用。 Rust 禁止您创建多个借用，即使您不尝试修改它们（因为这比尝试正式证明您的程序正确更容易）。

由于您基本上是尝试以命令式方式实现递归函数，因此我建议您转向更函数式的方法来解决您的问题。我将逻辑从你的循环中移出到直接在 Node.

上实现的递归函数中

struct Node {
    children: Vec<Node>,
    data: usize,
}

impl Node {

    pub fn new() -> Node {
        Node {
            children: vec!(),
            data: 0
        }
    }

    pub fn expand(&mut self) {
        self.children = vec!(Node::new(), Node::new());
    }

    pub fn is_leaf(&self) -> bool {
        self.children.len() == 0
    }

    fn expand_leaf_and_inc(&mut self) {
        if self.is_leaf() {
            self.expand();
        } else {
            let index = 0;
            self.children[index].expand_leaf_and_inc();
        }
        self.data += 1
    }
}

pub fn main() {
    let mut root = Node::new();
    for _ in 0..10 {
        root.expand_leaf_and_inc();
    }
}

如果你想保持势在必行，你可以使用 {node}.children 技巧移出 &mut 借用而不是重新借用它们：

let mut root = Node::new();
for _ in 0..10 {
    let mut path = vec![];
    {
        let mut node = &mut root;
        // Descend and potential modify the node in the process
        while !node.is_leaf() {
            let index = 0;
            path.push(index);
            node = &mut {node}.children[index];
        }
        // Do something to the leaf node
        node.expand();
    }
    // Do something during "backup" (in my case it doesn't matter
    // in which order the modification is happening).
    let mut node = &mut root;
    for &i in path.iter() {
        node.data += 1;
        node = &mut {node}.children[i];
    }
}

实现可变树结构

Implementing a mutable tree structure

tree

mutable

rust