Recursive data structures and returning ownership of self

help
#1

tl;dr Can a method pass ownership of its owning object back to the caller?

What I wish to do is have a structure witch is recursive and a method to add children that can be chained.

Given the structure:

struct Node {
    value:String,
    children:Vec<Box<Node>>,
}

I want a method add_child that I can chain;

impl Node {
    fn add_child<'a>(&'a mut self, child:Node) -> & mut Node {
        self.children.push(Box::<Node>::new(child));
        self
    }

Then I can say:

    let mut a = Node::new("a");

    let mut h = Node::new("ah");
    let i = Node::new("ahi");
    
    a.add_child(h.add_child(i)); // Fails

That will not work because add_child expects a object Node (and takes ownership) but returns a reference.

I would like add_child to pass the ownership of self to the caller. I do not think this possible…

Below is a complete listing of my little test programme that compiles and runs.

struct Node {
    value:String,
    children:Vec<Box<Node>>,
}
    
impl Node {
    fn add_child<'a>(&'a mut self, child:Node) -> & mut Node {
        self.children.push(Box::<Node>::new(child));
        self
    }
    fn new(value:&str) -> Node {
        Node{
            value:value.to_string(),
            children:vec![],
        }
    }
    fn print(&self) {
        self._print(0);
    }
        
    fn _print(&self, d:usize) -> usize{
        for _ in 0..d {
            print!(" ");
        }
        println!("{}", self.value);
        // Recursive call.  Base case when no children
        let _:Vec<usize> = self.children.iter().map(|x| x._print(d+1)).collect();
        d
    }
}


fn main() {
    let mut a = Node::new("a");

    let mut h = Node::new("ah");
    let i = Node::new("ahi");
    // 51 |     a.add_child(h.add_child(i));
    //    |                 ^^^^^^^^^^^^^^ expected struct `Node`, found &mut Node
    //    |
    //    = note: expected type `Node`
    //               found type `&mut Node`
    // a.add_child(h.add_child(i));
    h.add_child(i);
    a.add_child(h);
    a.print();
}
1 Like
#2

add_child returns a borrow (&T), not an owned object (T), so a.add_child(h.add_child(i)) is simply a type error. You can’t give ownership of a borrowed object (that’s stealing!)

You have to write it like this:

h.add_child(i);
a.add_child(h);

If you made add_child return owned Self, then a.add_child(h.add_child(i)) would work, but then you’d have to do:

let h = h.add_child(i);

in order not to lose access to h, which is weird.

In languages without ownership semantics any way to access an object is equivalent. In Rust the way to achieve that is to wrap objects in Rc or Arc.

If instead of Node you use Rc<Node>, you’ll be able to return a clone of Rc<Node>, and all Rc references will be equally useful.

3 Likes
#3

That is good advice. Can I use Rc where I am using Box?

I cannot see why not. I will try…

#4

Use it instead of Box.

You may also need to use RefCell or Mutex in it or in fields inside, since Rc makes its content read only.

#5

As I write I am trying to see how I can get add_child to return a correct value

    fn add_child<'a>(&'a mut self, child:Rc<Node>) -> Rc<Node> {
        self.children.push(child);
        self
    }

Nope.

error[E0308]: mismatched types
  --> src/main.rs:10:9
   |
8  |     fn add_child<'a>(&'a mut self, child:Rc<Node>) -> Rc<Node> {
   |                                                       -------- expected `std::rc::Rc<Node>` because of return type
9  |         self.children.push(child);
10 |         self
   |         ^^^^ expected struct `std::rc::Rc`, found mutable reference
   |
   = note: expected type `std::rc::Rc<Node>`
              found type `&'a mut Node`

That error makes sense. But how do I get back to the object through the self reference?

I have not used Rc until now…

#6

Return Rc::clone(self). Thanks to Rc that clone is cheap.

1 Like
#7

I get the error:

10 |         Rc::clone(self)
   |                   ^^^^ expected struct `std::rc::Rc`, found struct `Node`
   |
   = note: expected type `&std::rc::Rc<Node>`
              found type `&'a mut Node`

Function is now…

    fn add_child<'a>(&'a mut self, child:Rc<Node>) -> Rc<Node> {
        self.children.push(child);
        Rc::clone(self)
    }
#8

I would point out that graph data structures aren’t recommended in Rust, and modern processors can’t process them efficiently due to the large number of cache misses that incur.

Instead, you can use arenas[0] as an alternative to simulate graph data structures with less effort, without the downsides. Rather than allocating each individual node on the heap, you’d store each node in a single arena (vector).

In your case, each node would store the indexes of their sub-nodes, and this would allow you to share the same indexes with multiple nodes in the arena.

#9

There are trade offs. I am looking for the boundaries.

I know that technique (arena).

I am hoping that I can trade some computational efficiency for expressiveness.

a.add_child(newNode(..).add_child()) is very expressive. But if I cannot I cannot!

I am used to writing in Perl or C++ where this is trivial. I am used to Rust limiting my options - I get why - but finding those boundaries is hard. (Maybe not so trivial in Perl…)

#10

Ah, sorry. I forgot you’ve got &Node, not &Rc<Node> here. So you’d need to jump through more hoops to get &Rc<Node> as self.

Instead of digging deeper in that direction, maybe take a step back. This should work:

 a.add_child({h.add_child(i); h})
1 Like
#11

You can make it expressive with the builder pattern.

#12

Bingo!