Search code examples
rustvisitor-patterntrait-objects

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


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"
    }
}

Solution

  • 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"
        }
    }