Modeling a tree node structure

Hi,

I'm new to rust trying to learn, please bear with me if this is something obvious, I trying to create a tree of nodes while keeping a mutable reference to the node being modified current in my example. My naive approach doesn't work as the borrow checker correctly points out, I guess I need to use some kind of pointer for the Node, How would you approach this problem in Rust? Ideally current should be a stack of pointers so when I reach a leaf node I can go up to the previous current.

Cheers,
Jose

struct Node {
    name: String,
    children: Vec<Node>,
}

impl Node {
    fn new(name: &str) -> Self {
        Node {
            name: name.to_owned(),
            children: Vec::new(),
        }
    }
}

struct Tree<'a> {
    root: Node,
    current: Option<&'a mut Node>,
}

impl<'a> Tree<'a> {
    fn new() -> Self {
        let mut tree = Tree {
            root: Node::new("root"),
            current: None,
        };
        tree.current = Some(&mut tree.root);
        tree
    }
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0505]: cannot move out of `tree` because it is borrowed
  --> src/lib.rs:27:9
   |
20 | impl<'a> Tree<'a> {
   |      -- lifetime `'a` defined here
...
26 |         tree.current = Some(&mut tree.root);
   |                             -------------- borrow of `tree.root` occurs here
27 |         tree
   |         ^^^^
   |         |
   |         move out of `tree` occurs here
   |         returning this value requires that `tree.root` is borrowed for `'a`

error[E0515]: cannot return value referencing local data `tree.root`
  --> src/lib.rs:27:9
   |
26 |         tree.current = Some(&mut tree.root);
   |                             -------------- `tree.root` is borrowed here
27 |         tree
   |         ^^^^ returns a value referencing data owned by the current function

Some errors have detailed explanations: E0505, E0515.
For more information about an error, try `rustc --explain E0505`.
error: could not compile `playground` due to 2 previous errors

You seem to be trying to mix the tree structure itself “Tree” with some form of iterator that can step through the tree. (Holding a reference to a node.) This is atypical in Rust and hard to pull off – with a struct layout like you proposed, you’re trying to store the (owned) root node together with a reference into the tree behind that node in the same struct. Such a struct would be considered “self-referential” and the rust compiler does not really support these. There are workarounds or utility structs for self-referential structs but I think you don’t need one at all.

You could just create a

struct Tree {
    root: Node,
}

or perhaps, if you want to support empty trees, a

struct Tree {
    root: Option<Node>,
}

and separately a struct for mutable iteration

struct IterMut<'a> {
    current: Vec<&'a mut [Node]>, // a “stack” of pointers
}

and implement Iterator for it.

I’ll go ahead and try to present an example implementation for you.

3 Likes

Rust generally doesn't like objects that contain pointers into themselves ('self-referential structs') because it expects everything to be relocatable: Moving all of the bits somewhere else shouldn't break anything.

There's three general approaches to this sort of problem in Rust:

2 Likes

Here’s what I meant in code

pub use tree::Tree;
pub mod tree {
    use std::array;

    #[derive(Debug)]
    struct Node {
        name: String,
        children: Vec<Node>,
    }

    impl Node {
        fn new(name: &str) -> Self {
            Node {
                name: name.to_owned(),
                children: Vec::new(),
            }
        }
    }

    #[derive(Debug)]
    pub struct Tree {
        root: Node,
    }

    impl Tree {
        pub fn new() -> Self {
            Self {
                root: Node::new("root"),
            }
        }
        pub fn add_child(&mut self, t: Tree) {
            self.root.children.push(t.root);
        }
        pub fn iter_mut(&mut self) -> IterMut<'_> {
            IterMut {
                current: vec![array::from_mut(&mut self.root)],
            }
        }
    }

    pub struct IterMut<'a> {
        current: Vec<&'a mut [Node]>, // invariant: all slices are non-empty
    }

    impl<'a> Iterator for IterMut<'a> {
        type Item = &'a mut String;

        fn next(&mut self) -> Option<Self::Item> {
            let (node, nodes) = self.current.pop()?.split_first_mut().unwrap();
            if !nodes.is_empty() {
                self.current.push(nodes);
            }
            if !node.children.is_empty() {
                self.current.push(&mut node.children);
            }
            Some(&mut node.name)
        }
    }

    impl<'a> IntoIterator for &'a mut Tree {
        type IntoIter = IterMut<'a>;
        type Item = &'a mut String;

        fn into_iter(self) -> Self::IntoIter {
            self.iter_mut()
        }
    }
}

fn main() {
    let mut t = Tree::new();
    t.add_child(Tree::new());
    let mut n = 0_u8;
    for name in &mut t {
        *name = format!("Node {}", n);
        n += 1;
    }

    dbg!(&t);
}

(playground)

If you want to have access to &mut Tree during iteration instead of &mut String, you can’t use Iterator’s item anymore though (because you need to shorten the lifetime of the returned references), but you can offer a different API:

impl<'a> IterMut<'a> {
    pub fn current_node_mut(&mut self) -> Option<&mut Node> {
        Some(self.current.last_mut()?.first_mut().unwrap())
    }
    pub fn advance(&mut self) {
        self.next();
    }
}

fn main() {
    let mut t = /* … */;

    let mut i = t.iter_mut();
    while let Some(node) = i.current_node_mut() {
        // can e.g. modify the node here
        dbg!(node);

        i.advance();
    }
}

(playground)

5 Likes

I would actually go even further and argue that it's a bad idea in any other language as well. It would be trivial to create such a self-referential, hybrid storage+iterator tree in languages like Java or C# or C or Python. However, it would be a nightmare to use. The state of the iteration would persist across iterations over the collection, and it would be easy to start iterating at the wrong element.

So, my advice to OP is: avoid this, not because it's hard to do in Rust, but because it will likely bite you even if you manage to pull it off.

4 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.