Is there a way to express the following relationship?

I'm sorry for the bad title, I have no clue how to express the issue in a single line

Recently, I was making an implementation for the visitor pattern in rust, and I wanted to use generic traits for each different node instead of just having a huge trait with a bunch of "visit_expr" and "visit_operation" methods.

I wanted to express the following relationship:

// A trait that says that a type can traverse a family of nodes
trait Visitor<F> where F : NodeFamily {
  type Output;

// A trait for implementing the visiting logic for each different node
trait Visit<N> : Visitor<N::Family> where N : Node {
  fn visit(&mut self, node: &N) -> Self::Output;

// A trait to be implemented on each node for declaring which family it belongs to
trait Node {
  type Family: NodeFamily;

// A type that implements this node would group different nodes together;
// likely to be implemented on an enum or a type containing Box<dyn Node<Family = Self>>...
trait NodeFamily : Sized {
  // this function would be responsible for routing the visitor to the proper nodes
  fn accept<V>(&self, v: &mut V) -> <V as Visitor<Self>>::Output
    V : Visitor<Self>,
    // here comes the tricky bit, we also want V to know how to visit every possible node that belongs to our family:
    for<N : Node<Family = Self>> V : Visit<N>;

I am aware that last bit isn't rust code, but I based it off the for<> syntax that we have for lifetimes, I don't believe that today in rust we can express that relationship, but what would be a proper, or idiomatic, way of doing this?

Is there a precedent for semantics like this in other languages? And could something like this eventually come to rust?

One problem I realized that this could lead to is: an external crate could declare a new type that implements node for a family it doesn't own, and this could break external code that has a visitor for that family since there would be no Visit implementation for that new node.

I was able to solve my problem by moving the generic Visitor to the trait level rather than the function, which allows us to put trait bounds on the impl blocks, but it feels hacky (so much that I made a macro that does that since it becomes a lot of boilerplate) Here's the macro line that ensures this relationship of V must implement Visit for all N that implements Node<Family = Self>: visita/ at main · jvcmarcenes/visita · GitHub (the naming is a bit different and the crate isn't documented yet, but it shows what I'm talking about)

I think this is why it's not possible as stated -- the orphan rules are designed to avoid this sort of breakage at a distance. To avoid this sort of breakage, you would have to have a way to force implementors of Visit<N> to only do so with a blanket implementation that didn't exclude any Nodes (local, current, foreign, or future):

impl<F, N: Node<Family = F>> Visit<N> for Me { /* ... */ }

You can't do force this on the implementation level, but you can move it internal to the trait:

trait Visit<F: NodeFamily>: Visitor<F> {
    // Implementors have to be able to handle any arbitrary `Node`
    // from the `NodeFamily`
    fn visit<N: Node<Family = F>>(&mut self, node: &N) -> Self::Output;

At which point there's no reason to keep Visitor and Visit separate.

But you lose the ability to have an implementation per Node type, so I suspect this doesn't meet your desired behavior.

There may still be a way by making something more generic and then constraining that (sorry for being so vague, it's just a tickle in my mind), but I don't have time to play with it more at the moment.

But you lose the ability to have an implementation per Node type, so I suspect this doesn't meet your desired behavior.

Yeah, the whole point of the visitor pattern would be to have different implementations for each node...

As I said, I think that what I wanted to do is impossible currently in rust, and because of the orphan rule, may never be possible

To be fairly honest Rust generally doesn't cope well with traditional object-oriented design patterns, because Rust is not an object-oriented programming language.
Often you can adapt some concepts of the design pattern to make it comply with Rust but sometimes you just have to accept that its completely feasible for an OOP pattern to simply not be translatable into Rust code, which is fine imho, because Rust was not designed for these patterns but rather brings its own patterns to the table.

1 Like