A visitor pattern implementation in Rust


I have recently been studying the ANTLR parser-generator framework, and one of its core approaches is separating the core parsing logic from implementation details. It achieves this using two major patterns – the Listener pattern and the Visitor pattern. This is easily achieved in an Object-oriented language like Java. I was curious to see how that would translate into a language like Rust, hence this post.

Rust, while not quite being an Object-oriented language, does support static and dynamic dispatch. In this case, we are interested in dynamic dispatch, and “Trait Objects” are the main way in which Rust support this feature. However, one problem with using trait objects is that the runtime really doesn’t directly provide us with any way of retrieving the specific type at runtime. This means that calling any struct specific methods on the fly isn’t really that straightforward. The other problem (specific to the Visitor pattern) is that Rust doesn’t have the notion of method overloading. This means that the only sane approach to implementing the pattern in Rust would be to pattern match against the trait object and invoke the appropriate logic, which leads us back to the first point.

A bit of Googling leads us to a practical (if not so elegant) approach of determining the concrete type that implemented the trait at runtime by using std::any::Any. This approach entails providing a method that returns a trait object of type Any for each concrete type that implements the trait, and also explicitly checking the concrete type during pattern matching – there really is no way of extracting the concrete type directly. Instead, we have to try downcasting the trait object to each concrete type and checking if we have a match or not. While this approach works fine for our custom types (the types and count of which we know), this clearly wouldn’t work in a scenario where we are working with third-party types.

In any case, here is the code implementing a simple Visitor pattern where we visit each component of a House type, and perform some custom processing independent of the actual data structures.

Here is the overall layout of the code:

Macushla:rust_visitor z0ltan$ tree
.
├── Cargo.lock
├── Cargo.toml
└── src
    ├── lib.rs
    ├── main.rs
    └── visitors.rs

1 directory, 5 files

Here is the client code, main.rs:

extern crate rust_visitor;

use rust_visitor::*;

fn main() {
    let house = House::new();

    // simply print out the house elements
    house.accept(&visitors::HouseElementListVisitor::new());
   
    println!();
     
    // do something with the elements of a house
    house.accept(&visitors::HouseElementDemolishVisitor::new());
}

So we can see that we create the House element, and then pass in two different implementations of the HouseElementVisitor trait.

Here is the code defining the components of a House:

use std::any::Any;

pub mod visitors;

use visitors::HouseElementVisitor;

/// This represents and element of a house.
/// Each type that implements this trait
/// supports being processed by a visitor.
pub trait HouseElement {
    fn accept(&self, visitor: &HouseElementVisitor);
    fn as_any(&self) -> &Any;
}


/// Define the house entity and its elements

pub struct House {
    components: Vec<Box<HouseElement>>,
}

impl House {
    pub fn new() -> Self {
        House {
            components: vec![Box::new(Livingroom::new()), Box::new(Bedroom::new()), 
                            Box::new(Bathroom::new()), Box::new(Kitchen::new())],
        }
    }
}

impl HouseElement for House {
    fn accept(&self, visitor: &HouseElementVisitor) {
        for component in self.components.iter() {
            component.accept(visitor);
        }

        visitor.visit(self);
    }

    fn as_any(&self) -> &Any { self }
}

struct Livingroom {}

impl Livingroom {
    fn new() -> Self {
        Livingroom{}
    }
}

impl HouseElement for Livingroom {
    fn accept(&self, visitor: &HouseElementVisitor) {
        visitor.visit(self);
    }

    fn as_any(&self) -> &Any { self }
}


struct Bedroom {}

impl Bedroom {
    fn new() -> Self {
        Bedroom {}
    }
}

impl HouseElement for Bedroom {
    fn accept(&self, visitor: &HouseElementVisitor) {
        visitor.visit(self);
    }

    fn as_any(&self) -> &Any { self }
}


struct Bathroom {}

impl Bathroom {
    fn new() -> Self {
        Bathroom {}
    }
}

impl HouseElement for Bathroom {
    fn accept(&self, visitor: &HouseElementVisitor) {
        visitor.visit(self);
    }

    fn as_any(&self) -> &Any { self }
}


pub struct Kitchen {}

impl Kitchen {
    fn new() -> Self {
        Kitchen {}
    }
}

impl HouseElement for Kitchen {
    fn accept(&self, visitor: &HouseElementVisitor) {
        visitor.visit(self);
    }

    fn as_any(&self) -> &Any { self }
}

As can be seen, each implementation of the HouseElement trait defines a method, as_any that returns self as the specific type of the trait object, &Any. This will help the visitor implementation match and find the actual concrete type to do the processing specific to that visitor and that particular HouseElement component.

Finally, here is the actual implementation of the visitors:

//! This module defines the `HouseElementVisitor` trait which defines the capabilities
//! of a type to process the components of a `HouseElement` entity, and also defines
//! a couple of visitor types that do completely different processing.

use ::*;

pub trait HouseElementVisitor {
    fn visit(&self, element: &HouseElement);
}

pub struct HouseElementListVisitor {}

impl HouseElementListVisitor {
    pub fn new() -> Self {
        HouseElementListVisitor {}
    }
}

impl HouseElementVisitor for  HouseElementListVisitor {
    fn visit(&self, element: &HouseElement) {
        if element.as_any()
            .downcast_ref::<House>()
            .is_some() {
            println!("Visiting the House...");
        }

        if element.as_any()
            .downcast_ref::<Livingroom>()
            .is_some() {
            println!("Visiting the Living Room...");
        }

        if element.as_any()
            .downcast_ref::<Bedroom>()
            .is_some() {
            println!("Visiting the bedroom...");
        }

        if element.as_any()
            .downcast_ref::<Kitchen>()
            .is_some() {
                println!("Visiting the kitchen...");
        }
    }
}


pub struct HouseElementDemolishVisitor {}

impl HouseElementDemolishVisitor {
    pub fn new() -> Self {
        HouseElementDemolishVisitor {}
    }
}

impl HouseElementVisitor for HouseElementDemolishVisitor {
    fn visit(&self, element: &HouseElement) {
        if element.as_any()
            .downcast_ref::<House>()
            .is_some() {
            println!("Annihilating the House...!!!");
        }

        if element.as_any()
            .downcast_ref::<Livingroom>()
            .is_some() {
            println!("Bombing the Living Room...!!!");
        }

        if element.as_any()
            .downcast_ref::<Bedroom>()
            .is_some() {
            println!("Decimating the bedroom...!!!");
        }

        if element.as_any()
            .downcast_ref::<Kitchen>()
            .is_some() {
                println!("Destroying the kitchen...!!!");
        }
    }
}

Dirty, but at least it works. The problem, as mentioned before, is that in order to perform specific processing using dynamic dispatch, we use the trait object &HouseElement. However, in order to match against the concrete type, we need to try and match the downcasted reference against each concrete type. This is what the element.as_any().downcast_ref::() code does.

Let’s try it out!

Macushla:rust_visitor z0ltan$ cargo run
   Compiling rust_visitor v0.1.0 (file:///Users/z0ltan/Projects/Blog/Visitor_in_Rust/rust_visitor)
    Finished dev [unoptimized + debuginfo] target(s) in 0.56 secs
     Running `target/debug/rust_visitor`
Visiting the Living Room...
Visiting the bedroom...
Visiting the kitchen...
Visiting the House...

Bombing the Living Room...!!!
Decimating the bedroom...!!!
Destroying the kitchen...!!!
Annihilating the House...!!!

Excellent! Clunky and inelegant, but at least it works.

UPDATE: The implementations of the HouseElementVisitor trait can be simplified into a more elegant match expression block and using the is method of the Any trait as shown below:

Updated HouseElementListVisitor:

impl HouseElementVisitor for  HouseElementListVisitor {
    fn visit(&self, element: &HouseElement) {
        match element.as_any() {
            house if house.is::<House>() => println!("Visiting the house..."),
            living if living.is::<Livingroom>() => println!("Visiting the Living room..."),
            bedroom if bedroom.is::<Bedroom>() => println!("Visiting the bedroom..."),
            kitchen if kitchen.is::<Kitchen>() => println!("Visiting the kitchen..."),
            _ => {}
        }
    }
}

And the HouseElementDemolishVisitor implementation:

impl HouseElementVisitor for HouseElementDemolishVisitor {
    fn visit(&self, element: &HouseElement) {
        match element.as_any() {
            house if house.is::<House>() => println!("Annihilating the house...!!!"),
            living if living.is::<Livingroom>() => println!("Bombing the Living room...!!!"),
            bedroom if bedroom.is::<Bedroom>() => println!("Decimating the bedroom...!!!"),
            kitchen if kitchen.is::<Kitchen>() => println!("Destroying the kitchen...!!!"),
            _ => {}
        }
    }
}

Much more readable in my opinion, and it also hides the somewhat ugly downcast_ref::() bit!

Advertisements
A visitor pattern implementation in Rust

Speak your mind!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s