3

I'm new to Rust, and as part of the learning process, I'm attempting to create a tree structure where each node has a vector of children and a reference to its parent. I want to create an addChild() function to the node, which takes the value of the new node (i32s for now), adds it to the child-list, and passes a reference to itself as a parent. Following Rust by Example's linked list example, I'm trying to reference the parent with a Box<>. Since I'm both modifying the parent and passing a reference to it, I got stuck, as the borrow checker doesn't want me to dereference the &mut self (see the code below).

From this I have two questions:

  1. What is the correct way to keep a reference the parent in a tree structure? In C I would keep a simple pointer to the parent and some arbitrary collection for the children.

  2. How are you supposed to both modify and pass a reference to an object in the same function in Rust?

Below is the full code for my enum and impl, with an additional test-function to modify self without passing it.


#[derive(Hash, Eq, PartialEq)]
enum Node {
    Elem {
        value: i32,
        parent: Box<Node>,
        children: Vec<Node>,
    },
    Nil,
}

impl Node {
    fn new(value: i32, parent: Box<Node>) -> Node {
        return Node::Elem {
            value: value,
            parent: parent,
            children: Vec::new(),
        };
    }

    // This function works fine
    fn setValue(&mut self, v: i32) {
        match self {
            &mut Node::Elem { ref mut value, .. } => *value = v,
            &mut Node::Nil => {}
        }
    }

    fn addChild(&mut self, value: i32) {
        match self {
            &mut Node::Elem { ref mut children, .. } => {
                (*children).push(Node::new(value, Box::new(*self)))
                // Produces E0507 (Cannot move out of borrowed context)
            } 
            &mut Node::Nil => println!("Failed to add children to empty node"),
        }
    }
}
Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
dromtrund
  • 245
  • 2
  • 7
  • 4
    **Trees** are pretty natural data structures in Rust, but when you add parent pointers to a tree you have a **graph**. Graphs are *much* harder because the ownership of each node becomes very murky. Please check out some existing questions ([1](http://stackoverflow.com/q/28608823/155423), [2](http://stackoverflow.com/q/16911554/155423), [3](http://stackoverflow.com/q/34747464/155423), [4](http://stackoverflow.com/q/27001067/155423), [5](http://stackoverflow.com/q/36565833/155423), and there are more) and then either mark this as a duplicate or [edit] your question to explain the difference. – Shepmaster May 05 '16 at 11:41
  • @Shepmaster Thanks. The goal is not to create a search tree, but a full on back-traceable tree structure of independent objects. The accepted answer in your first post starts with "You can't represent an arbitrary graph structure in safe rust.". Is this really the case? I mean.. it's a pretty fundamental way of representing relationships. Are there no ways of pointing to an object without owning it? – dromtrund May 05 '16 at 17:17
  • 2
    @dromtrund There's some stuff you can do with weak reference counters, but honestly in most cases it's probably better for your sanity to do with `unsafe` and raw pointers as long as you don't expose the unsafe bits to users. – Linear May 05 '16 at 20:18
  • 2
    The other way I never see mentioned is to store the tree nodes in a `Vec` or something and assign each one a unique `Copy`-able ID, and then instead of holding a child/parent pointer just store the ID of your child/parent. – Linear May 05 '16 at 20:21
  • 2
    See [Learning Rust With Entirely Too Many Linked Lists](http://cglab.ca/~abeinges/blah/too-many-lists/book/README.html) which should walk you through a few different solutions to this. – Veedrac May 05 '16 at 20:40

0 Answers0