How to support two visitors which returns different return value types in Rust?

Question

I am trying to implement a Visitor pattern in Rust. I am not able to find a way to support two visitors which return different return value types.

Playground link

trait Visited<R> {
    fn accept (self: &Self, v: &dyn Visitor<R>) -> R;
}

trait Visitor<R> {
    fn visit_a(&self, a: &A<R>) -> R;
    fn visit_b(&self, b: &B) -> R;
}

I've implemented two data structures that can be visited.

// ---- A ----
struct A<R> {
    value: String,
    b: Box<dyn Visited<R>>,
}

impl<R> Visited<R> for A<R> {
    fn accept (&self, v: &dyn Visitor<R>) -> R {
        v.visit_a(self)
    }
}

// ---- B ----
struct B {
    value: i32,
}
impl<R> Visited<R> for B {
    fn accept(&self, v: &dyn Visitor<R>) -> R {
        v.visit_b(self)
    }
}

This worked okay when I just had a concrete visitor.

struct Visitor1 {}
impl Visitor<String> for Visitor1 {
    fn visit_a(&self, a: &A<String>) -> String {
        let b = a.b.accept(self);
        format!("visitor1.visit_a(): {} {}", a.value, b)
    }
    fn visit_b(&self, b: &B) -> String {
        format!("visitor1.visit_b(): {}", b.value)
    }
}

However, the whole point of the Visitor pattern is to let multiple algorithm to be applied against the data structure.

When I wanted to add another visitor, I couldn't figure out how to make it work.

struct Visitor2 {}
impl Visitor<i32> for Visitor2 {
    fn visit_a(&self, a: &A<i32>) -> i32 {
        123
    }
    fn visit_b(&self, b: &B) -> i32 {
        456
    }
}

fn main() {
    let a = A {
        value: "HELLO".to_string(),
        b: Box::new(B{ value: 32 })
    };
    let v1 = Visitor1{};
    let s: String = a.accept(&v1);
    println!("{}", s);

    let v2 = Visitor2{};
    let v: i32 = a.accept(&v2);
    println!("{}", v);
}

The type of a is inferred as A<String>, and the a.accept(&v2) caused a type mismatch error.

I'd like to tell a to be visited by Visitor1 and Visitor2. How can I do this?

Answer 1

If you return only 'static types, you can use type erasure. The idea is to create a trait, ErasedVisitor, that is not generic and instead return Box<dyn Any>, and implement this trait for all Visitors and use it internally. This mean, though, that you cannot use a generic parameter, only an associated type (otherwise you get "unconstrained type parameter":

trait Visited {
    fn accept_dyn(&self, v: &dyn ErasedVisitor) -> Box<dyn Any>;
    fn accept<V: Visitor>(&self, v: &V) -> V::Result
    where
        Self: Sized,
    {
        *self.accept_dyn(v).downcast().unwrap()
    }
}

impl<T: ?Sized + Visited> Visited for &'_ T {
    fn accept_dyn(&self, v: &dyn ErasedVisitor) -> Box<dyn Any> {
        T::accept_dyn(&**self, v)
    }
}

impl<T: ?Sized + Visited> Visited for &'_ mut T {
    fn accept_dyn(&self, v: &dyn ErasedVisitor) -> Box<dyn Any> {
        T::accept_dyn(&**self, v)
    }
}

impl<T: ?Sized + Visited> Visited for Box<T> {
    fn accept_dyn(&self, v: &dyn ErasedVisitor) -> Box<dyn Any> {
        T::accept_dyn(&**self, v)
    }
}

trait Visitor {
    type Result: 'static;
    fn visit_a(&self, a: &A) -> Self::Result;
    fn visit_b(&self, b: &B) -> Self::Result;
}

trait ErasedVisitor {
    fn visit_a(&self, a: &A) -> Box<dyn Any>;
    fn visit_b(&self, b: &B) -> Box<dyn Any>;
}

impl<V: ?Sized + Visitor> ErasedVisitor for V {
    fn visit_a(&self, a: &A) -> Box<dyn Any> {
        Box::new(<Self as Visitor>::visit_a(self, a))
    }
    fn visit_b(&self, b: &B) -> Box<dyn Any> {
        Box::new(<Self as Visitor>::visit_b(self, b))
    }
}

struct A {
    value: String,
    b: Box<dyn Visited>,
}

impl Visited for A {
    fn accept_dyn(&self, v: &dyn ErasedVisitor) -> Box<dyn Any> {
        v.visit_a(self)
    }
}

Playground.

But if you can, the best way is to use static polymorphism (generics) instead of dynamic dispatch.