Defining a tree in rust

Question

I am trying to create the structure for an expression tree in rust, and I'd like for it not just to work, but also be efficient (Thus the usage of ids and an array instead of walking through pointers) and also simple to create (As in, I don't want the code for a new tree to be excessively verbose).

Currently, I have something like so:


#[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;
    }
}

With the idea being that for an expression of the form "(name == Alice) && (age >= 30)" I can define a tree like so:

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

This structure does what I want it to do: it should be very fast to traverse using a stack of ints and the code around it isn't too verbose. The problem is, I did this like I would in C++, and Rust doesn't allow me to do it, saying 'cannot borrow tree as mutable more than once at a time'

My questions are: Why can't I do this? I'm mutating the Vec inside of the tree, not the tree itself, so I don't really understand why this happens. How would I go about making this work? Also, in a more general sense, is there a better/more accepted way of doing trees in rust?

Your question does only contain part of the code causing the problem. I also don't quite get the difference between `tree.expr` and `tree.new_expr` (both methods are missing). This makes it harder than it needs to be for us to debug your problem. Please supply a [Minimal, Reproducible Example](https://stackoverflow.com/help/minimal-reproducible-example). You may also be interested in the section "Producing a Minimal, Reproducible Example (MRE) for Rust code" in the [Rust tag wiki](https://stackoverflow.com/tags/rust/info). — Elias Holzmann, Jul 01 '21 at 16:14
Sorry, I kind of messed up the example, expr should be new_expr, but new_expr is reproduced above — JoseCarlosVM, Jul 01 '21 at 16:17
[Link to rust playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=2e208abe21b833f653bc33998ed78c8d) — Elias Holzmann, Jul 01 '21 at 16:33
Thanks, I was trying to fix it up but your version is a lot easier to read, I'll edit my question to use it — JoseCarlosVM, Jul 01 '21 at 16:37
There is a crate that does it: https://crates.io/crates/socarel (I'm the author) — ASLLOP, Sep 27 '21 at 04:40

Elias Holzmann · Accepted Answer · 2021-07-01T20:42:32.290

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

The point of the borrow checker is to prevent you from having data races, in this case it prevents two concurrent modifications of the Vec. The borrow checker accomplishes this by not allowing two mutable references to the ExprTree that owns the Vec to exist at the same time, in effect making it impossible to concurrently change the Vec.

However, in your example, the ExprTree is indeed never borrowed mutably more than once. Because the example is a bit complicated, I will explain the problem using this piece of code:

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

The following would happen here if this code was executed:

tree is borrowed mutably to call tree.new_expr("name", None, None)
- first mutable borrow is created
- method is executed on the first mutable borrow
- method returns 0
- first mutable borrow is destroyed
tree is again borrowed mutably to call tree.new_expr("name", Some(0), None) (0is the value returned by the first call to new_expr()
- second mutable borrow is created
- method is executed on the second mutable borrow
- method returns 0
- second mutable borrow is destroyed

As you can see, the first mutable borrow is destroyed before the second mutable borrow is created. So why does this not compile?

This is a known edge case that the borrow checker currently handles suboptimally (meaning it it is too conservative – it rejects sound code: Better than the alternative ;-)). See for example this answer.

Defining a tree in rust

1 Answers1