The Visitor Pattern: A generic and still type-safe approach

Every once in a while I find myself in a situation, where the visitor design pattern comes in handy to perform a set of different operations on the elements of an object hierarchy. Normally I would start then designing a Visitor and Visitable interface, dedicated to the problem right at my hands.

Having done this for a couple of times, I asked myself, whether there might be some essence in all those visitor pattern implementations, which might be worth being extracted into a basic Visitor resp. Visitable interface, allowing for further reuse. The challenge when creating such interfaces is to design them in a generic, but still type-safe manner.

Optimally, the elements of a concrete object hierarchy should only be visitable by an associated hierachy of visitors, while these visitors should only be able to visit the elements of exactly this hierarchy. This requirement is met by the following design:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

package org.gm.visitorpattern; public interface Visitor<V extends Visitor<V, T>, T extends Visitable<V, T>> { void dispatchVisit(T visitable); } ... public interface Visitable<V extends Visitor<V, T>, T extends Visitable<V, T>> { public void accept(V visitor); }

Through the use of type parameters the interfaces are generic, independent of any concrete application of the pattern. Despite this genericity, the design fulfills our requirement, that elements of a concrete visitable hierarchy only accept visitors of an associated visitor hierarchy and vice versa. This coupling between a concrete visitable hierarchy and an associated hierarchy of visitor classes is ensured by leveraging so-called "self-bound" or "self-referential generics" (Visitor<V extends Visitor<V, T>, ...).

To make things a bit clearer, let's use those interfaces to apply the visitor pattern to a hierarchy of file system objects (files and directories), that can be visited by file system visitors. The interface to represent file system objects is derived from Visitable:

1 2 3 4 5 6 7 8 9 10

package org.gm.visitorpattern.sample; import org.gm.visitorpattern.Visitable; public interface FileSystemObject extends Visitable<FileSystemVisitor, FileSystemObject> { String getName(); }

As implementation of this interface let's first create a file class:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

package org.gm.visitorpattern.sample; public class File implements FileSystemObject { private long size; protected String name; public File(String name, long size) { this.name = name; this.size = size; } public long getSize() { return size; } @Override public void accept(FileSystemVisitor visitor) { visitor.visit(this); } @Override public String getName() { return name; } }

Of course we need a class to represent directories as well:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

package org.gm.visitorpattern.sample; import java.util.ArrayList; import java.util.List; public class Directory implements FileSystemObject { private List<FileSystemObject> children = new ArrayList<FileSystemObject>(); protected String name; public Directory(String name, FileSystemObject... children) { this.name = name; for (FileSystemObject fso : children) { this.children.add(fso); } } public List<FileSystemObject> getChildren() { return children; } @Override public void accept(FileSystemVisitor visitor) { visitor.visit(this); } @Override public String getName() { return name; } }

One might create an abstract base class for both implementations (which could hold the name property and other common logic), but we will skip this for the sake of simplicity.

Now its time to create a derivation of the Visitor interface, that has to be implemented by all concrete file system visitors. According to the visitor pattern we specify an overloaded version of the visit method for each class of the visited object hierarchy:

1 2 3 4 5 6 7 8 9 10 11 12

package org.gm.visitorpattern.sample; import org.gm.visitorpattern.Visitor; public interface FileSystemVisitor extends Visitor<FileSystemVisitor, FileSystemObject> { void visit(File file); void visit(Directory directory); }

By specifying the concrete values for the type parameters of the Visitor and Visitable interfaces as shown in the FileSystemObject resp. FileSystemVisitor interfaces, we ensure that file system objects can only be visited by file system vistors, while those only can visit file system objects. Actually, there wouldn't have been any way around this (welcome) restriction due to the self-bound type parameters in the super interfaces.

To conclude the example, let's develop a file system visitor, that calculates the size of a directory with all its files and sub directories:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

package org.gm.visitorpattern.sample; public class SizeCalculationVisitor implements FileSystemVisitor { private long totalSize = 0; @Override public void dispatchVisit(FileSystemObject visitable) { visitable.accept(this); } @Override public void visit(File file) { totalSize += file.getSize(); } @Override public void visit(Directory directory) { for (FileSystemObject oneChild : directory.getChildren()) { oneChild.accept(this); } } public long getTotalSize() { return totalSize; } }

Finally let's test our new visitor:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

package org.gm.visitorpattern.sample; import static org.junit.Assert.assertEquals; import org.junit.Before; import org.junit.Test; public class VisitorPatternTest { private FileSystemObject root; @Before public void setup() { root = new Directory("root", new File("file1.txt", 100), new Directory("dir1", new File("dir1_file1.txt", 200), new File("dir1_file2.txt", 200)), new File("file2.txt", 400)); } @Test public void testGetOperations() { SizeCalculationVisitor visitor = new SizeCalculationVisitor(); visitor.dispatchVisit(root); assertEquals(900, visitor.getTotalSize()); } }

What is it worth for?

So, what's the use of the generic Visitor and Visitable interfaces? First, they help implementing the visitor design pattern properly. For my part, I am always forgetting about the implementation details – by deriving from the interfaces, there isn't much left that I could do wrong.

At second, visitor and visitors are recognizable as such not only by some naming convention or similar but inherently by their types. So if an application needs to perform operations on all visitables or visitors – across the bounds of hierarchies – it can do so by inspecting their types.