Best Practice for Traits Being Used by Traits

help
1

I'm currently working on a small test library to showcase simple graph algorithms (e.g. DFS and BFS) for trees and what difference it makes in regards to performance and resource consumption to use lists, hash maps, etc. as data structures.

To make it a bit more approachable, I wanted to show that no matter the data, as long as certain set of data is available, the algorithms are quite generic. This generic approach is where my knowledge of Rust is quite a bit lacking.

For now, I have the following traits defined and I would like to make it better:

pub trait Node {
    /// Reference ID of the original node to allow for a mapping of the internal structure to the original one. Unique and also used as identifier for a node in this library.
    fn reference(&self) -> usize;

    /// The children of a node. Uses [reference] to correctly identify a node.
    fn children(&self) -> &Vec<usize>;
}

pub trait Tree {
    /// Setup  the internal data structure so that the algorithms can properly run
    fn init<N>(&mut self, root: usize, nodes: Vec<N>) -> Result<(), InvalidArgumentError>
    where
        N: Node;

    fn get_root(&self) -> Result<usize, GenericError>;

   ...
}

I would have then implemented using the following struct:

pub struct SimpleNode {
    ...
}

pub struct SimpleTree {
    root: usize,
    nodes: HashMap<usize, Box<dyn Node>>,
}

It feels like the wrong approach and I would highly appreciate pointers on how to make it better :slight_smile:

2

There’s no such thing as a perfect generic interface. Everything you do will make some things easier and other things harder. That said, here are some suggestions:

  • fn children(&self) -> &Vec<usize>;

    This obligates the node to own a Vec, which does not make sense if the tree has a fixed maximum number of children. Use a slice reference instead, so the implementor of Node has more freedom:

    fn children(&self) -> &[usize];

    As a general principle: &Vec<T> usually should nod appear anywhere in an API, because it is more constraining than &[T] to no good effect. (The only additional thing you can do with &Vec<T> is examine its capacity.)

  • If SimpleTree is meant to be used with SimpleNode, then it should own SimpleNodes, not Box<dyn Node>. Presuming this is true, then the problem with the Tree trait is that init obligates the implementor to accept any type of node at all. It should instead use an associated type, so that the implementor can choose the node type:

    pub trait Tree {
    type Node;
    fn init(&mut self, root: usize, nodes: Vec<Self::Node>) -> Result<(), InvalidArgumentError>;
    ...
}

  • If your goal is to use the Tree trait as an interface between tree types and algorithms on trees, then you should not have an init method like this — the tree should be given to the algorithm already initialized (perhaps empty, perhaps nonempty). A trait should focus on one particular operation or closely related set of operations; traits should, when feasible, be designed and named as verbs, not nouns.

  • InvalidArgument and GenericError sound awfully suspicious.

    • If the errors mean things like “you passed an invalid node ID”, then that should not be a Result return at all — it should be a panic. For any erroneous input which indicates a bug in the caller, you should panic, not clutter the API with error cases that should never occur in an actual program.
    • If the errors are to allow the implementor to fail for their own reasons, then you should let them choose the error type, too, as an associated type.
4 Likes
3

Thank you for the detailed answer :slight_smile:

Do you happen to have some favourite resources you use as a reference (blogs, posts, etc.) for such topics?

4

Sorry, I mostly don't collect resources like that. All of this is built on experience, not guides.

5

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.