How can I create a polymorphic tree/graph using Rc?

Question

I have a polymorphic, reference counted tree structure in C++:

struct Node {
  std::vector<std::shared_ptr<Node>> children;
};

Each node of the tree might have its own data and its own implementations. To illustrating the idea:

struct Named : public Node {
  std::string name;
};

Node root;
int main() {
  root.children.push_back(std::shared_ptr(new Named{"Hello World"}));
}

Circular references are solved by std::weak_ptr<T>.

I tried the following in Rust:

use rc::{Rc, RefCell};

struct Node {
    children: Vec<Rc<RefCell<Node>>>,
}

How I would make the tree structure polymorphic at this point? As far as I know, I can only inherit traits from traits.

My best guess is to use some kind of trait that conforms to the tree-like structure, but I find it tedious to make each implementing struct a children vector. This code illustrates the idea; I have not tested it and I'm not sure if it has any errors:

trait TreeLike {
    fn get_children(&mut self) -> &mut Vec<Rc<RefCell<dyn TreeLike>>>;
}

struct A {
    children: Vec<Rc<RefCell<TreeLike>>>,
}

impl TreeLike for A {
    fn get_children(&mut self) -> &mut Vec<Rc<RefCell<dyn TreeLike>>> {
        return children;
    }
}

struct A {
    children: Vec<Rc<RefCell<TreeLike>>>,
}

impl TreeLike for B {
    fn get_children(&mut self) -> &mut Vec<Rc<RefCell<dyn TreeLike>>> {
        return children;
    }
}

I'm not even sure if you can use traits to own the data at this point. This also adds unnecessary virtual dispatches that are solved by direct data access in C++.

Answer 1

You only want to use dyn when you want the ability to mix and match implementations of TreeLike, but you don't seem to based on the C++ example.

You want to reference Self instead of dyn TreeLike:

trait TreeLike {
    fn get_children(&mut self) -> &mut Vec<Rc<RefCell<Self>>>;
}

Used like so:

struct A {
    children: Vec<Rc<RefCell<A>>>, // Note how I'm referencing the actual type here
}

impl TreeLike for A {
    fn get_children(&mut self) -> &mut Vec<Rc<RefCell<Self>>> {
        &mut self.children // and that it's fine to return here as here Self == A
    }
}