Heterogenous containers in Rust for a graph

Question

I am a C++ programmer learning Rust, and one of my main use cases is a graph-based computation engine. In my graph I have store a homogeneous type, and then I derive from this with a more specific type e.g. in C++

class BaseNode {
  public:
    BaseNode(std::vector<std::shared_ptr<BaseNode>>& parents);
    virtual ~BaseNode() = default;

    virtual void update(); 
    const std::vector<std::shared_ptr<BaseNode>>& parents() const;
    ...
};

template<typename T>
class TypedNode<T> : public BaseNode {
  public:
    const T& value() const { return value_; }

    ...
  private:
    T value_;
}

The idea is that the graph is traversed and update() is called on each node. The node knows what each of its parents "true type" is and so in its update() can do something like static_cast<TypedNode<DataBlob>>(parents()[0]).

How do I achieve something like this in Rust?

I thought about having a design like this:

trait BaseNode {
    fn parents(&self) -> &Vec<dyn BaseNode>;
}

trait TypedNode<T>: BaseNode {
    fn value(&self) -> &T;
}

But I read that I won't be able to cast the "trait object" from a BaseNode into a TypedNode<T>. (Or can I do it somehow using unsafe?). The other alternative I thought would be to have a struct that stores the data in Any and then to cast that, but does that incur some runtime cost?

Answer 1

If all node's parents have the same type then you can use that approach:

trait BaseNode {
    type Parent: BaseNode;
    fn parents(&self) -> &[Self::Parent];
}

trait TypedNode<P: BaseNode>: BaseNode<Parent = P> {
    type ValueType;
   fn value(&self) -> &Self::ValueType;
}

Rust playground

I'm not sure if I understand your question. Please let me know if it doesn't work for you.