New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Visitor pattern: can it be properly implemented in Rust? #55

Open
barsan-ds opened this Issue Mar 21, 2017 · 3 comments

Comments

Projects
None yet
3 participants
@barsan-ds

barsan-ds commented Mar 21, 2017

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

This comment has been minimized.

FraGag commented Mar 22, 2017

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.

@Peternator7

This comment has been minimized.

Peternator7 commented Apr 30, 2017

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

This comment has been minimized.

FraGag commented Apr 30, 2017

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.

cheezgi added a commit to cheezgi/piccolo that referenced this issue Dec 6, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment