Is there a way to implement trait objects with generic functions?

Question

Basically I am trying to implement visitors-coding paradigm, where Expr trait needs to be implemented by Binary struct. I want to use Expr as a trait object. Any entity wanting to interact with Expr will need to implement Visitors trait. The visitor trait should also be a trait object with generic function so that different functions inside the trait can support different types. But this makes Expr and Visitors not trait object safe. Is there a way to implement what I am trying to achieve?

 use crate::token_type::Token;

pub trait Expr {
    fn accept<T>(&self, visitor: &dyn Visitor) -> T;
}

pub trait Visitor {
    fn visit_binary_expr<T>(&self, expr: Binary) -> T;
}

impl Expr for Binary {
    fn accept<T>(self, visitor: &dyn Visitor) -> T {
        visitor.visit_binary_expr(self)
    }
}

pub struct Binary {
    left: Box<dyn Expr>,
    operator: Token,
    right: Box<dyn Expr>,
}

impl Binary {
    fn new(left: Box<dyn Expr>, operator: Token, right: Box<dyn Expr>) -> Self {
        Self {
            left,
            operator,
            right,
        }
    }
}

struct ASTPrinter {}
impl ASTPrinter {
    fn print(&self, expr: Box<dyn Expr>) -> &str {
        expr.accept(self)
    }
}
impl Visitor for ASTPrinter {
    fn visit_binary_expr(&self, expr: Binary) -> &str {
        "binary"
    }
}

Answer 1

First, reconsider if you really want trait objects and not enums. Enums are a better way to model a closed set of types, like expressions.

If you insist on using trait objects, reconsider if your visitor really needs to be able to return something. ()-returning visitors are very simple to implement:

pub trait Expr {
    fn accept(&self, visitor: &mut dyn Visitor);
}

pub trait Visitor {
    fn visit_binary_expr(&mut self, expr: &Binary);
}

impl Expr for Binary {
    fn accept(&self, visitor: &mut dyn Visitor) {
        visitor.visit_binary_expr(self);
    }
}

Now, if you really need trait objects, and you really need to return values, then you need some boilerplate.

The idea is to have a result-type-erased visitor, that wraps a generic visitor but always returns (), and keep the inner visitor's result in a field. Then, we have an accept_impl() that takes &mut dyn Visitor<Result = ()> (that is, a visitor that returns ()), and a wrapper accept() that uses accept_impl() and ErasedVisitor to take any visitor and return its result:

pub trait Visitor {
    type Result;
    fn visit_binary_expr(&mut self, expr: &Binary) -> Self::Result;
}

struct ErasedVisitor<'a, V: Visitor> {
    visitor: &'a mut V,
    result: Option<V::Result>,
}

impl<V: Visitor> Visitor for ErasedVisitor<'_, V> {
    type Result = ();
    fn visit_binary_expr(&mut self, expr: &Binary) {
        self.result = Some(self.visitor.visit_binary_expr(expr));
    }
}

pub trait Expr {
    fn accept_impl(&self, visitor: &mut dyn Visitor<Result = ()>);
}

pub trait ExprExt: Expr {
    fn accept<V: Visitor>(&self, visitor: &mut V) -> V::Result {
        let mut visitor = ErasedVisitor {
            visitor,
            result: None,
        };
        self.accept_impl(&mut visitor);
        visitor.result.unwrap()
    }
}

impl<E: Expr + ?Sized> ExprExt for E {}

Then using this is like:

struct ASTPrinter {}
impl ASTPrinter {
    fn print(&mut self, expr: &dyn Expr) -> &'static str {
        expr.accept(self)
    }
}
impl Visitor for ASTPrinter {
    type Result = &'static str;
    fn visit_binary_expr(&mut self, expr: &Binary) -> &'static str {
        "binary"
    }
}