rust - 用 Rust 定义一棵树

Question

我正在尝试在 Rust 中创建表达式树的结构，我希望它不仅能够工作，而且还要高效(因此使用 ids 和数组而不是遍历指针)并且还易于创建(例如，我不希望新树的代码过于冗长)。

目前，我有这样的事情:

#[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 不允许我这样做，说“不能一次多次借用 tree 作为可变的”

我的问题是:为什么我不能这样做？我正在改变树内部的 Vec ，而不是树本身，所以我真的不明白为什么会发生这种情况。我将如何去做这项工作？ 另外，从更一般的意义上来说，是否有更好/更容易接受的方法来处理使用rust 的树木？

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 的两个可变引用同时存在来实现此目的，实际上使得不可能同时更改 >向量。

但是，在您的示例中，ExprTree 确实从未多次可变借用。由于示例有点复杂，我将使用这段代码来解释问题:

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

如果执行此代码，则会发生以下情况:

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

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

这是借用检查器当前处理欠佳的已知边缘情况(这意味着它过于保守 - 它拒绝声音代码:比替代方案更好;-))。例如，参见this answer .