在 Rust 中定义一棵树

Question

我正在尝试为 Rust 中的表达式树创建结构，我希望它不仅可以工作，而且要高效（因此使用 id 和数组而不是遍历指针）而且创建起来也很简单（例如，我不希望新树的代码过于冗长）。

目前，我有这样的东西：


#[derive(Debug, Default)]
struct ExprTree {
    tree: Vec<Node>,
}

#[derive(Debug)]
struct Node {
    index: usize,
    content: String,
    lhs: Option<usize>,
    rhs: Option<usize>,
}

impl Node {
    fn new(id: usize, content: &str, lhs: Option<usize>, rhs: Option<usize>) -> Self {
        Self {
            index: id,
            content: content.to_string(),
            lhs: lhs,
            rhs: rhs
        }
    }
}

impl ExprTree {
    fn new() -> Self {
        Self {
            tree: Vec::new()
        }
    }

    fn new_expr(&mut self, content: &str, lhs: Option<usize>, rhs: Option<usize>) -> usize {
        let id = self.tree.len();
        self.tree.push(Node::new(id, content, lhs, rhs));
        return id;
    }
}

我的想法是，对于“(name == Alice) && (age >= 30)”形式的表达式，我可以这样定义一棵树：

 fn main() {
    let mut tree = ExprTree::new();
    tree.new_expr(
        "&&",
        Some(tree.new_expr(
            "==",
            Some(tree.new_expr("name", None, None)),
            Some(tree.new_expr("Alice", None, None)),
        )),
        Some(tree.new_expr(
            ">=",
            Some(tree.new_expr("age", None, None)),
            Some(tree.new_expr("30", None, None)),
        )),
    );
}

这个结构完成了我想要它做的事情：使用整数堆栈进行遍历应该非常快，并且围绕它的代码也不会太冗长。问题是，我像在 C++ 中那样做了这个，而 Rust 不允许我这样做，说 'cannot borrow tree as mutable more than once at a time'

我的问题是：为什么我不能这样做？我正在改变树内部的 Vec，而不是树本身，所以我真的不明白为什么会这样。我将如何着手进行这项工作？此外，从更一般的意义上讲，是否有一种 better/more 可以接受的处理树木生锈的方法？

Answer 1

I'm mutating the Vec inside of the tree, not the tree itself, so I don't really understand why this happens.

借用检查器的作用是防止出现数据竞争，在这种情况下，它可以防止对 Vec 进行两次并发修改。借用检查器通过不允许对拥有 Vec 的 ExprTree 的两个可变引用同时存在来实现这一点，实际上不可能同时更改 Vec.

但是，在您的示例中，ExprTree 确实从未多次以可变方式借用。因为例子有点复杂，我就用这段代码来说明问题：

    let mut tree = ExprTree::new();
    tree.new_expr(
        "&&",
        Some(tree.new_expr("name", None, None)),
        None,
    );

如果执行这段代码，会发生以下情况：

tree 可变借用调用 tree.new_expr("name", None, None)
- 第一个可变借用已创建
- 方法在第一个可变借用时执行
- 方法returns0
- 第一个可变借用被销毁
tree再次可变借用调用tree.new_expr("name", Some(0), None)（0是第一次调用new_expr()返回的值
- 第二个可变借用已创建
- 方法在第二个可变借用时执行
- 方法returns0
- 第二个可变借用被销毁

如您所见，第一个可变借用在创建第二个可变借用之前被销毁。那么为什么不能编译呢？

这是一个已知的边缘情况，借用检查器目前处理得不是很理想（这意味着它过于保守——它拒绝合理的代码：比替代方案更好 ;-)）。例如参见 [=25=].

在 Rust 中定义一棵树

Defining a tree in rust

tree

rust