Blog

Accepting the Visitors

Thumbnail
Design patterns? Ugh, not those again. I remember sitting in my undergraduate object-oriented design class as our professor went on and on about the Single

Design patterns? Ugh, not those again. I remember sitting in my undergraduate object-oriented design class as our professor went on and on about the Singleton Pattern, the Decorator Pattern, the Composite Pattern, and so many others. Most of them weren't too bad, but some of them started to sound the same after a while. Just when I thought I had gotten the hang of things in that class, we got to the Visitor Pattern.

Whoever named the Visitor Pattern deserves an award for finding a name that sounds like it legitimately describes the pattern, when in reality it doesn't say anything at all and just confuses students when they first learn about it. Seriously, what the heck is a Visitor?!

Okay, maybe I'm getting a little defensive. In any case, I was surprised when I came to Delphix to find that people actually use the Visitor Pattern in the real world. In fact, after just a couple months into the job, I was using the Visitor Pattern myself!

Generally, we can think of a "visitor" as something that specifies what action to perform with various "hosts". In the real world, the Visitor Pattern commonly gets used when we want to traverse a tree-like structure with nodes of different types and perform an action on each node of the tree depending on the type of the node. Here, the hosts are the nodes of the tree, and the visitors specify what action to perform on each type of node. For example, the walkFileTree method in the Files class of the java.nio.file package takes a FileVisitor as an argument that specifies what actions to perform on the files and directories (the nodes) in a file tree.

So why would someone want to use the Visitor Pattern? Well, the main reason is that the Visitor Pattern is a great way to make your code follow the Open/Closed Principle, which is essentially the ability to extend the behavior of a class or module without needing to modify its source code.1 (If that sounds paradoxical to you, don't worry, that's how I felt when I first heard about the Open/Closed Principle too.) The Visitor Pattern also helps decouple the actions we want to perform from the data structures that we perform the actions on.2Before we dive into how the Visitor Pattern achieves these great things and why they're so great, let's try to understand what the Visitor Pattern is and the fundamental mechanism by which it works.

To start, let's pretend we have a bunch of pets: a cat, a dog, a rabbit, and a fish. These pets are quite popular around the neighborhood and frequently have visitors. For some strange reason, our pets tend to assume the mood of whoever is visiting. For example, if our visitor is happy, then all of our pets will act happy; if our visitor is annoyed, then all of our pets will act annoyed; and if our visitor is terrified, then all of our pets will act terrified.

Attempt 1

interface Visitor {
}

class HappyVisitor implements Visitor {
}

class AnnoyedVisitor implements Visitor {
}

class TerrifiedVisitor implements Visitor {
}

interface Pet {
    void actHappy();
    void actAnnoyed();
    void actTerrified();
}

The pets respond to the visitors' moods in their own unique ways. For example, if our dog is happy, he might run around and wag his tail; if our cat is annoyed, she would probably hiss and growl and maybe even spit at us; and if our bunny is terrified, her eyes might bulge.

Here's what the implementation of the Pet interface for our fish might look like.

class Fish implements Pet {
    @Override
    void actHappy() {
        System.out.println("Happy fish: Swim");
    }

    @Override
    void actAnnoyed() {
        System.out.println("Annoyed fish: "Keep swimming");
    }

    @Override
    void actTerrified() {
        System.out.println("Terrified fish: "Maybe swim slightly faster");
    }
}

The implementations for our other pets are analogous.

One day, a neighbor decides to stop by and visit our pets. Let's write some code that makes our pets respond appropriately to the visitor.

List<Pet> pets = Arrays.asList(new Dog(), new Cat(), new Rabbit(), new Fish());
Visitor visitor = answerTheDoor();

if (visitor instanceof HappyVisitor) {
    for (Pet pet : pets) {
        pet.actHappy();
    }
} else if (visitor instanceof AnnoyedVisitor) {
    for (Pet pet : pets) {
        pet.actAnnoyed();
    }
} else if (visitor instanceof TerrifiedVisitor) {
    for (Pet pet : pets) {
        pet.actTerrified();
    }
}

Well, that looks less than ideal. Our code is getting quite repetitive. If we only had one pet or if our neighbors were always happy when they visited, the code wouldn't be so bad -- we might be able to get rid of the for-loops or the chain of if-statements. But we have several pets, and our neighbors come in a variety of moods. And perhaps in the future, we'll decide to get some more pets, or maybe our neighbor will be grumpy the next time he visits. What if our neighbors start coming in more moods than we can keep track of and we forget to include one of the types of visitors in our chain of if-statements? It looks like our code is rather error-prone has the potential to get quite unwieldy.

Let's see if we can rewrite our code to be a little less repetitive. It would be nice if we could just let our pets know who visited and let them respond automatically based on the visitor's mood rather than trying to figure out the visitor's mood ourselves and explicitly telling our pets how to react to the visitor. It's a good thing our pets are accepting of visitors of all kinds.

Attempt 2

interface Pet {
    void accept(HappyVisitor visitor);
    void accept(AnnoyedVisitor visitor);
    void accept(TerrifiedVisitor visitor);
}

// Implementations for Dog, Cat, and Rabbit
...

class Fish implements Pet {
    @Override
    void accept(HappyVisitor visitor) {
        System.out.println("Happy fish: Swim");
    }

    @Override
    void accept(AnnoyedVisitor visitor) {
        System.out.println("Annoyed fish: Keep swimming");
    }

    @Override
    void accept(TerrifiedVisitor visitor) {
        System.out.println("Terrified fish: Maybe swim slightly faster");
    }
}

Now, we can make our code a lot simpler.

List<Pet> pets = Arrays.asList(new Dog(), new Cat(), new Rabbit(), new Fish());
Visitor visitor = answerTheDoor();

for (Pet pet : pets) {
    pet.accept(visitor);
}

Wow, that looks a lot better! Unfortunately, the Java compiler doesn't seem to like our code anymore though. The compiler is complaining about the line

    pet.accept(visitor);

and rightly so. But why? At runtime, we're expecting Java to figure out which specific type of Pet we have and which specific type of Visitor we have, and then to call the appropriate method. This is called "double dispatch", or more generally, "multiple dispatch". However, Java (like many other languages) only does "single dispatch". This means that it determines which method to call by resolving the concrete type of just the object whose method we're calling (in this case, the pet). It is our responsibility to explicitly tell Java the concrete type of the argument (in our example, the visitor) if we want Java to be able to figure out which method to call. So it looks like we're back to using those if-statements to figure out what kind of visitor we have. But the idea of having our pets figure out what kind of visitor we have sounds better than what we were doing originally, since it at least lets us avoid the duplication between the visitor types (e.g., HappyVisitor) and the names of the methods that tell our pets how to act (e.g., actHappy). Let's see what that code looks like with the logic to determine the type of visitor pushed to the pets.

Attempt 3

interface Pet {
    void accept(Visitor visitor);
}

// Implementations for Dog, Cat, and Rabbit
...

class Fish implements Pet {
    @Override
    void accept(Visitor visitor) {
        if (visitor instanceof HappyVisitor) {
            System.out.println("Happy fish: Swim");
        } else if (visitor instanceof AnnoyedVisitor) {
            System.out.println("Annoyed fish: Keep swimming");
        } else if (visitor instanceof TerrifiedVisitor) {
            System.out.println("Terrified fish: Maybe swim slightly faster");
        }
    }
}

This lets us keep the simpler code that we liked from our second attempt, and this time, the Java compiler doesn't complain since we now have a single accept method that takes any Visitor rather than multiple accept methods that take different concrete subclasses of Visitor.

List<Pet> pets = Arrays.asList(new Dog(), new Cat(), new Rabbit(), new Fish());
Visitor visitor = answerTheDoor();

for (Pet pet : pets) {
    pet.accept(visitor);
}

Unfortunately, we now have the same if-else chain repeated for every single type of pet. And that means we might forget to include one of the cases if our visitors start coming in more moods than we can keep track of since the compiler doesn't enforce that we're handling all the cases. But wait! Inside each accept method, we know exactly which type of Pet we're working with. Java figured that out for us when we called the pet's accept method. We can use a similar trick to get Java to figure out what kind of Visitor we have too. Once a pet accepts a visitor, we could ask the visitor to visit the pet by calling a corresponding visit method with the concrete pet as an argument. Then Java would resolve the concrete type of the Visitor, and we'd know exactly which type of Pet and which type of Visitor we have without using any if-statements! In the following code, notice how each Pet implementation simply passes itself to the Visitor of an unknown concrete type. Once we're in the pet's accept method, we've already figured out what type of Pet we're working with, so we can safely pass it to the visitor. All the Java runtime needs to do now is figure out what type of Visitor we're working with, which it knows how to do. Also, notice how the Visitor interface contains one visit method per if-statement in the previous implementation, meaning that it contains one method for each type of Pet. This ensures that the Visitor implementations won't compile unless they handle every possible type of Pet.

Attempt 4

interface Visitor {
    void visit(Dog dog);
    void visit(Cat cat);
    void visit(Rabbit rabbit);
    void visit(Fish fish);
}

class HappyVisitor implements Visitor {
    // Implementations of visit() for Dog, Cat, and Rabbit
    ...

    @Override
    void visit(Fish fish) {
        System.out.println("Happy fish: Swim");
    }
}

class AnnoyedVisitor implements Visitor {
    // Implementations of visit() for Dog, Cat, and Rabbit
    ...

    @Override
    void visit(Fish fish) {
        System.out.println("Annoyed fish: Keep swimming");
    }
}

class TerrifiedVisitor implements Visitor {
    // Implementations of visit() for Dog, Cat, and Rabbit
    ...

    @Override
    void visit(Fish fish) {
        System.out.println("Terrified fish: Maybe swim slightly faster");
    }
}

interface Pet {
    void accept(Visitor visitor);
}

class Dog implements Pet {
    @Override
    void accept(Visitor visitor) {
        visitor.visit(this);
    }
}

class Cat implements Pet {
    @Override
    void accept(Visitor visitor) {
        visitor.visit(this);
    }
}

class Rabbit implements Pet {
    @Override
    void accept(Visitor visitor) {
        visitor.visit(this);
    }
}

class Fish implements Pet {
    @Override
    void accept(Visitor visitor) {
        visitor.visit(this);
    }
}

We can still keep that simple code we liked from earlier, too.

List<Pet> pets = Arrays.asList(new Dog(), new Cat(), new Rabbit(), new Fish());
Visitor visitor = answerTheDoor();

for (Pet pet : pets) {
    pet.accept(visitor);
}

In our final version of the code, we are using the Visitor Pattern. Notice that there are no more if-statements anywhere. The compiler will force us to implement our pets' reactions to every mood a visitor can come in. Furthermore, given any Pet and any Visitor, the correct code will automatically get executed. We the programmers don't have to think about making sure the right code gets executed under the right conditions anymore.

Fundamentally, the Visitor Pattern works by simulating "double dispatch" in languages that only offer "single dispatch". To achieve the effect of "double dispatch", the Visitor Pattern essentially just performs "single dispatch" twice, first by calling the host's (in our example, the pet's) accept method and then by calling the visitor's visit method.

Food for thought: How could we use an extension of the Visitor Pattern to simulate "triple dispatch", where we want to determine what code to execute based on an object whose method we call and two arguments to the method? What about "quadruple dispatch"?

Looking at our final version of the code, it's easy to see that we've separated the actions that our pets perform from the implementations of the pets. The pets are implemented in the classes Dog, Cat, Rabbit, and Fish, while their behaviors are implemented in the classes HappyVisitor, AnnoyedVisitor, and TerrifiedVisitor. This allows us to add new behaviors for our pets at any time in a type-safe way just by adding new Visitor implementations, without having to change any of the existing Pet implementations! In situations where we need to add new functionality to existing code that we can't change, the Visitor Pattern is a nifty solution and exemplifies the Open/Closed Principle.

In traditional object-oriented programming, we define the behaviors that objects can perform in the form of an interface. We can then easily create new objects that conform to the interface, thereby implementing the pre-defined behaviors. In contrast, the Visitor Pattern defines the objects in the system ahead of time (the methods in the Visitor interface corresponding to each of the hosts are fixed), but allows us to easily add new behaviors to those pre-defined objects.

Going back to our example of the Files class, the inclusion of the walkFileTree method allows the user to define the functionality they'd like to have when it comes to files and directories. Absent this, the Java authors would have to add methods like deleteAllFiles and renameAllDirectories whenever they wanted to expose new functionality. This is cumbersome and inflexible, particularly because a new version of Java only gets released every few years.

In any large production codebase, there will be some cases when we need the ability to add new objects that implement existing behaviors and other cases when we want to add new behaviors to existing objects. The decision to use the Visitor Pattern involves a tradeoff between the flexibility to add new objects and the flexibility to add new behaviors. In many cases, the decision is not so clear-cut. Having the Visitor Pattern in our toolbox at Delphix gives us the ability to make that tradeoff and pick the right tool for the job.