Implementing a mutable tree structure

Question

I'm trying to dynamically build a tree and modify parts of the tree during descent, at the leaves, and during backup. I believe I have a fundamental misunderstanding on how to do something like this in Rust. Here's my code:

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

And this the error message from the compiler:

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

oli_obk · Accepted Answer · 2017-09-05 17:16:23Z

9

There are a few things going on here at the same time. The simple answer is: you are trying to create multiple mutable borrows to the same item. Rust forbids you from creating multiple borrows, even if you are not trying to modify them (because that's easier than trying to formally prove that your program is correct).

Since you basically tried to implement a recursive function in an imperative way, I suggest you move to a more functional approach to your problem. I moved out the logic from your loop into a recursive function that is directly implemented on 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();
    }
}

If you want to stay imperative, you can use the {node}.children trick to move out of &mut borrows instead of reborrowing them:

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

edited Sep 5, 2017 at 17:16

answered Mar 27, 2015 at 8:52

oli_obk

31.7k8 gold badges93 silver badges105 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

ujh Over a year ago

That was a pretty neat trick in the previous version, where you introduced a new scope during the assignment of path.

ujh Over a year ago

And I knew it! I was thinking too imperative. I still need to come to terms with the somewhat functional nature of Rust.

Collectives™ on Stack Overflow

Implementing a mutable tree structure

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related