Visitor pattern

Definition

The Gang of Four defines the Visitor as:

Represent an operation to be performed on elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates.

The nature of the Visitor makes it an ideal pattern to plug into public APIs thus allowing its clients to perform operations on a class using a “visiting” class without having to modify the source.

Motivation

Consider the design of a 2D computer-aided design (CAD) system. At its core there are several types to represent basic geometric shapes like circles, lines, and arcs. The entities are ordered into layers, and at the top of the type hierarchy is the drawing, which is simply a list of layers, plus some added properties.

A fundamental operation on this type hierarchy is saving a drawing to the system's native file format. At first glance it may seem acceptable to add local save methods to all types in the hierarchy. But it is also useful to be able to save drawings to other file formats. Adding ever more methods for saving into many different file formats soon clutters the relatively pure original geometric data structure.

A naive way to solve this would be to maintain separate functions for each file format. Such a save function would take a drawing as input, traverse it, and encode into that specific file format. As this is done for each added different format, duplication between the functions accumulates. For example, saving a circle shape in a raster format requires very similar code no matter what specific raster form is used, and is different from other primitive shapes. The case for other primitive shapes like lines and polygons is similar. Thus, the code becomes a large outer loop traversing through the objects, with a large decision tree inside the loop querying the type of the object. Another problem with this approach is that it is very easy to miss a shape in one or more savers, or a new primitive shape is introduced, but the save routine is implemented only for one file type and not others, leading to code extension and maintenance problems.

Instead, the Visitor pattern can be applied. It encodes a logical operation on the whole hierarchy into one class containing one method per type. In the CAD example, each save function would be implemented as a separate Visitor subclass. This would remove all duplication of type checks and traversal steps. It would also make the compiler complain if a shape is omitted.

Another motive is to reuse iteration code. For example, iterating over a directory structure could be implemented with a visitor pattern. This would allow creating file searches, file backups, directory removal, etc., by implementing a visitor for each function while reusing the iteration code.

Details

The visitor pattern requires a programming language that supports single dispatch. Under this condition, consider two objects, each of some class type; one is termed the element, and the other is visitor. An element has an accept method that can take the visitor as an argument. The accept method calls a visit method of the visitor; the element passes itself as an argument to the visit method. Thus:

When the accept method is called in the program, its implementation is chosen based on both:

The dynamic type of the element.

The static type of the visitor.

When the associated visit method is called, its implementation is chosen based on both:

The dynamic type of the visitor.

The static type of the element as known from within the implementation of the accept method, which is the same as the dynamic type of the element. (As a bonus, if the visitor can't handle an argument of the given element's type, then the compiler will catch the error.)

Thus, the implementation of the visit method is chosen based on both:

The dynamic type of the element.

The dynamic type of the visitor.

This effectively implements double dispatch. For languages which object systems support multiple dispatch, not only single dispatch, such as Common Lisp, implementing the visitor pattern in them is trivial.

In this way, one algorithm can be written to traverse a graph of elements, and many different kinds of operations can be performed during that traversal by supplying different kinds of visitors to interact with the elements based on the dynamic types of both the elements and the visitors.

Some languages (e.g., C# via the Dynamic Language Runtime (DLR)) support multiple dispatch, which greatly simplifies implementing the Visitor pattern (a.k.a. Dynamic Visitor) by allowing use of simple function overloading to cover all the cases being visited. A dynamic visitor, provided it operates on public data only, conforms to the open/closed principle (since it does not modify extant structures) and to the single responsibility principle (since it implements the Visitor pattern in a separate component).

C# example

This example shows how to print a tree representing a numeric expression involving literals and their addition. The same example is presented using both classic and Dynamic Language Runtime implementations.

Classic visitor

A classic visitor where the Print operations for each type are implemented in one ExpressionPrinter class as a number of overloads of the Visit method.

Dynamic Visitor

This example declares a separate ExpressionPrinter class that takes care of the printing. Note that the expression classes have to expose their members to make this possible.

Output

dispatching ArchivedFiledispatching SplitFiledispatching ExtractedFile

Java example

The following example is in the language Java, and shows how the contents of a tree of nodes (in this case describing the components of a car) can be printed. Instead of creating print methods for each node subclass (Wheel, Engine, Body, and Car), one visitor class (CarElementPrintVisitor) performs the required printing action. Because different node subclasses require slightly different actions to print properly, CarElementPrintVisitor dispatches actions based on the class of the argument passed to its visit method. CarElementDoVisitor, which is analogous to a save operation for a different file format, does likewise.

Sources

A more flexible approach to this pattern is to create a wrapper class implementing the interface defining the accept method. The wrapper contains a reference pointing to the ICarElement that could be initialized through the constructor. This approach avoids having to implement an interface on each element. See article Java Tip 98 article below

Output

Visiting front left wheelVisiting front right wheelVisiting back left wheelVisiting back right wheelVisiting bodyVisiting engineVisiting carKicking my front left wheelKicking my front right wheelKicking my back left wheelKicking my back right wheelMoving my bodyStarting my engineStarting my car

Output

"front-left-wheel""front-right-wheel""rear-right-wheel""rear-right-wheel""body""engine"kicking wheel "front-left-wheel" 42 timeskicking wheel "front-right-wheel" 42 timeskicking wheel "rear-right-wheel" 42 timeskicking wheel "rear-right-wheel" 42 timesdon't know how "body" and 42 should interactstarting engine "engine" 42 timeskicking wheel "front-left-wheel" symbolically using symbol ABCkicking wheel "front-right-wheel" symbolically using symbol ABCkicking wheel "rear-right-wheel" symbolically using symbol ABCkicking wheel "rear-right-wheel" symbolically using symbol ABCdon't know how "body" and ABC should interactstarting engine "engine" symbolically using symbol ABC

Notes

The other-object parameter is superfluous in traverse. The reason is that it is possible to use an anonymous function that calls the desired target method with a lexically captured object:

Now, the multiple dispatch occurs in the call issued from the body of the anonymous function, and so traverse is just a mapping function that distributes a function application over the elements of an object. Thus all traces of the Visitor Pattern disappear, except for the mapping function, in which there is no evidence of two objects being involved. All knowledge of there being two objects and a dispatch on their types is in the lambda function.

Related design patterns

Command pattern – encapsulates like the visitor pattern one or more functions in an object to present them to a caller; unlike the visitor, this pattern does not enclose a principle to traverse the object structure

Iterator pattern – defines a traversal principle like the visitor pattern, without making a type differentiation within the traversed objects