Discussion about Visitor pattern

[barsan-md]

Maybe there is something I'm missing because the lack of Rust syntax/concepts understanding (I'm still learning, sorry) but the goal of the Visitor pattern is not only to "allow multiple different algorithms to be written over the same data". The main reason when visitor pattern is used is to allow dynamic double dispatch. Say you have a pair of abstract Visitor and Data and you don't know at compile time what the actual type of Data and Visitor is, you can just say data.accept(visitor) and let the magic happen.
Just look at https://en.wikipedia.org/wiki/Visitor_pattern#C.2B.2B_example
This is perfectly doable in any OO language.

Refering to the example, how can I have a
let d : Data = some of(Stmt, Name, Expr, ...);
let v : Visitor = some of(Interpreter, ...);
and say d.accept(v) without doing match on types anywhere.

Can this be done in Rust?

[FraGag]

Certainly. You just need to define two traits:

trait Data {
    fn accept<V: Visitor>(&self, visitor: &mut V) -> V::Result;
}

trait Visitor {
    type Result;

    fn visit_stmt(&mut self, stmt: &Stmt) -> Self::Result;
    fn visit_name(&mut self, name: &Name) -> Self::Result;
    fn visit_expr(&mut self, expr: &Expr) -> Self::Result;
}

impl Data for Stmt {
    fn accept<V: Visitor>(&self, visitor: &mut V) -> V::Result {
        visitor.visit_stmt(self)
    }
}

impl Data for Name {
    fn accept<V: Visitor>(&self, visitor: &mut V) -> V::Result {
        visitor.visit_name(self)
    }
}

impl Data for Expr {
    fn accept<V: Visitor>(&self, visitor: &mut V) -> V::Result {
        visitor.visit_expr(self)
    }
}

impl Visitor for Interpreter {
    fn visit_stmt(&mut self, stmt: &Stmt) -> Self::Result { unimplemented!() }
    fn visit_name(&mut self, name: &Name) -> Self::Result { unimplemented!() }
    fn visit_expr(&mut self, expr: &Expr) -> Self::Result { unimplemented!() }
}

Serde uses visitors in this way to decouple serialization/deserialization from the data format.

[pm100]

I know this is old but I am trying to do the same thing. The problem with the above is that the Data objects are specialized to the visitor. Ie I cannot build a parse tree and unleash several visitors in sequence to it. I really want to generate a tree that is neutral to the visitor type.

I know this is doable because antlr4rust generates the correct data structure to do it - so why not copy that. Because its outrageously convoluted and its hard to tell which bits are needed for that part of the solution and which bits are needed to implement other bits of behavior that I dont need

[Peternator7]

Follow up question. With specialization you implement the visitor pattern similar to this:

#![feature(specialization)]

pub trait Visitor<T> {
    fn visit(&mut self, t:&T);
}

pub trait Visitable: Sized {
    fn accept<T>(&self, t: &mut T) where T: Visitor<Self> {
        t.visit(self);
    }
}

struct Expr;
impl Visitable for Expr {}

struct Term;
impl Visitable for Term {}

struct Vis;

impl <T> Visitor<T> for Vis where T: Visitable{
    default fn visit(&mut self, _: &T) {
        unimplemented!();
    }
}

impl Visitor<Expr> for Vis {
    fn visit(&mut self, _: &Expr) {
        println!("Visiting an Expression");
    }
}

impl Visitor<Term> for Vis {
    fn visit(&mut self, _: &Term) {
        println!("Visiting a Term");
    }
}

fn main() {
    let mut v = Vis;
    Expr.accept(&mut v);
    Term.accept(&mut v);
}

What are the thoughts on doing something like this vs creating a visit_* for each method that is needed?

[FraGag]

That's clever! In fact, if you don't need a default visit implementation, you don't even need specialization: you can remove the impl<T> Visitor<T> for Vis and it will work so long as Visitor<X> is implemented for each visitable X.

What's particular about that technique, as opposed to traditional visitors, is that an external crate could add a new Visitable type (let's call it X) and could implement Visitor<X> for a new or an existing visitor (you can't do something like that on existing types with interfaces in Java or .NET) or just fall back to the default, if it's present.

Another interesting fact is that if you control the value to be visited and you provide your own visitor, then you only need to implement the Visitor<X> traits you actually use.

A disadvantage of that technique is that it's harder to make a trait object for a Visitor that supports all visitable types: you'll have to define a new trait that has each Visitor<X> as a supertrait. For example:

pub trait Visitor2
where
    Self: Visitor<Expr>,
    Self: Visitor<Term>,
{
}

impl<T> Visitor2 for T
where
    T: Visitor<Expr>,
    T: Visitor<Term>,
{
}

Then the bound T: ?Sized needs to be added to Visitable::accept for the trait object to be accepted.

[jedbrown]

An issue with using generics here is that you can't invoke Visitable::accept in a dyn Visitable, so the dispatch is only dynamic in one argument (the Visitor). With the named visit_xyz() methods, you can start with a dyn Visitable and a dyn Visitor, as in

    let vs: &[&dyn Visitor] = &[&V0, &V1];
    let ds: &[&dyn Data] = &[&Stmt, &Name, &Expr];
    for d in ds {
        for v in vs {
            d.accept(*v);
        }
    }

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=293c62d3ee32dc693bc37718f52ea1fb

One can easily add new visitors, but adding new data requires adding methods to the Visitor trait. This is essentially the same situation as using enum Data {Stmt, Name, Expr}, albeit different syntax.

I'm not aware of a safe way to do dynamic multiple dispatch that is extensible in both arguments. This comment by Graydon Hoare (and the whole post above) offers some insight into the design decision: https://graydon2.dreamwidth.org/189377.html?thread=627649#cmt627649
Note that Julia inherits a CLOS-style object model with fully extensible multimethods.

[vbrandl]

Following my comment on HN it would be great to specify use cases when the visitor pattern should be used. Most of the time, pattern matching should be good enough and is more idiomatic Rust.

[marcantonio]

I think you identified the main drawback in your comment: the need for a common super type. I recently wrote something like the following:

for node in ast {
    match node {
        AstNode::Expr(expr) => IrRetVal::Expr(self.gen_expr_ir(expr)?),
        AstNode::Proto(proto) => IrRetVal::Func(self.gen_proto_ir(proto)?),
        AstNode::Func(func) => IrRetVal::Func(self.gen_func_ir(func)?),
    };
    ...
}

The need for the IrRetVal enum to tie it all together makes the pattern far less elegant IMO. Maybe it is more idiomatic though?

[MarcoIeni]

Changed the title of the issue because visitor pattern exists here