Tree traversal in Rust vs Borrow Checker

Question

I'm attempting to implement a tree structure in Rust, traverse it, and modify it, and I'm running into trouble with the borrow checker. My setup is more or less the following:

#![feature(slicing_syntax)]

use std::collections::HashMap;

#[deriving(PartialEq, Eq, Hash)]
struct Id {
    id: int,  // let’s pretend it’s that
}

struct Node {
    children: HashMap<Id, Box<Node>>,
    decoration: String,
    // other fields
}

struct Tree {
   root: Box<Node>
}

impl Tree {
    /// Traverse the nodes along the specified path.
    /// Return the node at which traversal stops either because the path is exhausted
    /// or because there are no more nodes matching the path.
    /// Also return any remaining steps in the path that did not have matching nodes.
    fn traverse_path<'p>(&mut self, mut path: &'p [Id]) -> (&mut Box<Node>, &'p [Id]) {
        let mut node = &mut self.root;
        loop {
            match node.children.get_mut(&path[0]) {
                Some(child_node) => {
                    path = path[1..];
                    node = child_node;
                },
                None => {
                    break;
                }
            }
        }
        (node, path)
    }
}

I have mutable references here because I want to be able to mutate the node returned by the method. For example, an add method would call traverse_path and then add nodes for the remainder of the path that did not have matching nodes.

This produces these errors:

s.rs:28:19: 28:32 error: cannot borrow `node.children` as mutable more than once at a time
s.rs:28             match node.children.get_mut(&path[0]) {
                          ^~~~~~~~~~~~~
s.rs:28:19: 28:32 note: previous borrow of `node.children` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `node.children` until the borrow ends
s.rs:28             match node.children.get_mut(&path[0]) {
                          ^~~~~~~~~~~~~
s.rs:39:6: 39:6 note: previous borrow ends here
s.rs:25     fn traverse_path<'p>(&mut self, mut path: &'p [Id]) -> (&mut Box<Node>, &'p [Id]) {
...
s.rs:39     }
            ^
s.rs:31:21: 31:38 error: cannot assign to `node` because it is borrowed
s.rs:31                     node = child_node;
                            ^~~~~~~~~~~~~~~~~
s.rs:28:19: 28:32 note: borrow of `node` occurs here
s.rs:28             match node.children.get_mut(&path[0]) {
                          ^~~~~~~~~~~~~
s.rs:38:10: 38:14 error: cannot borrow `*node` as mutable more than once at a time
s.rs:38         (node, path)
                 ^~~~
s.rs:28:19: 28:32 note: previous borrow of `node.children` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `node.children` until the borrow ends
s.rs:28             match node.children.get_mut(&path[0]) {
                          ^~~~~~~~~~~~~
s.rs:39:6: 39:6 note: previous borrow ends here
s.rs:25     fn traverse_path<'p>(&mut self, mut path: &'p [Id]) -> (&mut Box<Node>, &'p [Id]) {
...
s.rs:39     }
            ^
error: aborting due to 3 previous errors

I understand why the borrow checker doesn't like this code, but I don't know how to make this work.

I also attempted an alternate implementation using an iterator using code like the following:

struct PathIter<'a> {
    path: &'a [Id],
    node: &'a mut Box<Node>
}
impl<'a> Iterator<Box<Node>> for PathIter<'a> {
    fn next(&mut self) -> Option<Box<Node>> {
        let child = self.node.get_child(&self.path[0]);
        if child.is_some() {
            self.path = self.path[1..];
            self.node = child.unwrap();
        }
        child
    }
}

The errors here ended up being lifetime-related:

src/http_prefix_tree.rs:147:27: 147:53 error: cannot infer an appropriate lifetime for autoref due to conflicting requirements
src/http_prefix_tree.rs:147     let child = self.node.get_child(&self.path[0]);
                                                  ^~~~~~~~~~~~~~~~~~~~~~~~~~
src/http_prefix_tree.rs:146:3: 153:4 help: consider using an explicit lifetime parameter as shown: fn next(&'a mut self) -> Option<Box<Node>>
src/http_prefix_tree.rs:146   fn next(&mut self) -> Option<Box<Node>> {
src/http_prefix_tree.rs:147     let child = self.node.get_child(&self.path[0]);
src/http_prefix_tree.rs:148     if child.is_some() {
src/http_prefix_tree.rs:149       self.path = self.path[1..];
src/http_prefix_tree.rs:150       self.node = child.unwrap();
src/http_prefix_tree.rs:151     }

Another thing I'm interested in is to collect the values of the decoration field for matching nodes and display these values if the path was fully exhausted. My very first thought was to have backlinks from the nodes to their parents, but the only example of this I found was Rawlink in DList, which scared me off. My next hope is that the iterator implementation (if I can get it to work) would lend itself naturally to something like that. Is that the right track to pursue?

Ah, strict lexical scope. Causes such a raft of annoying problems in just a few places, this sort of thing being one of them. — Chris Morgan
Incidentally, &Box<T> or &mut Box<T> is a bad thing to end up with; you should be dealing with &mut T instead, e.g. by doing &mut *self.root instead of &mut self.root. — Chris Morgan
This is similar to stackoverflow.com/q/27083544/1256624 , but the desire to return node means I haven't been able to convince the compiler to accept it without unsafe. — huon
@ChrisMorgan Could you elaborate on why references to boxes are a bad thing to end up with? Is this a matter of style, or are there more insidious dangers? — Ray

Francis Gagné Francis Gagné · Accepted Answer · 2014-12-31T10:34:00

Here's a variant of your first approach, using recursion to avoid borrowing conflicts. The iterative equivalent fails to compile because Rust is too strict when dealing with mutable borrowed pointers to mutable values.

impl Node {
    fn traverse_path<'p>(&mut self, mut path: &'p [Id]) -> (&mut Node, &'p [Id]) { // '
        if self.children.contains_key(&path[0]) {
            self.children[path[0]].traverse_path(path[1..])
        } else {
            (self, path)
        }
    }
}

impl Tree {
    /// Traverse the nodes along the specified path.
    /// Return the node at which traversal stops either because the path is exhausted
    /// or because there are no more nodes matching the path.
    /// Also return any remaining steps in the path that did not have matching nodes.
    fn traverse_path<'p>(&mut self, mut path: &'p [Id]) -> (&mut Node, &'p [Id]) { // '
        self.root.traverse_path(path)
    }
}

Note that I've changed the return type from &mut Box<Node> to &mut Node; you don't need to reveal to your users that you're using a Box in your implementation. Also, see how Node::traverse_path first checks if there's a value in the map using contains_key(), then retrieving the value using indexing. This means that the value is looked up twice, but that's the only way I've found to make this work without requiring unsafe code.

P.S.: You can change the root in Tree to be a Node, rather than a Box<Node>.

Tree traversal in Rust vs Borrow Checker

1 Answers