"'Tis some visitor," I muttered, "tapping at my chamber door;
Only this and nothing more."
— Edgar Allen Poe, The RavenProblem: You need to add a new method to a hierarchy of classes, but the act of adding it will be painful or damaging to the design.
This is a common problem. For example, you have a hierarchy of Modem objects. The base class has the generic methods common to all modems. The derivatives represent the drivers for many different modem manufacturers and types. You have a requirement to add a new method to the hierarchy named ConfigureForUnix. This method will configure the modem to work with the Unix operating system. It will do something different in each modem derivative, because each different modem has its own particular idiosyncrasies for setting configuration and dealing with Unix.
Unfortunately adding ConfigureForUnix begs a terrible set of questions. What about Windows, what about MacOs, what about Linux? Must we really add a new method to the Modem hierarchy for every new operating system that we use? Clearly this is ugly. We’ll never be able to close the Modem interface. Every time a new operating system comes along, we’ll have to change that interface and redeploy all the modem software.
The Visitor Family of Design Patterns
The Visitor family allows new methods to be added to existing hierarchies without modifying the hierarchies.
The patterns in this family are:
- Visitor
- Acyclic Visitor
- Decorator
- Extension Object
Visitor [1]
Consider the Modem hierarchy in Figure 1. The Modem interface contains the generic methods that all modems can implement. There are three derivatives shown, one that drives a Hayes modem, another that drives a Zoom modem, and a third that drives the modem card produced by Ernie, one of our hardware engineers.
How can we configure these modems for Unix without putting the ConfigureForUnix method in the Modem interface? We can use a technique called dual dispatch, which is the mechanism at the heart of the Visitor pattern.
Figure 2 shows the Visitor structure, and Listings 1, 2, 3, 4, 5, and 6 show the corresponding Java code. Listing 7 shows the test code that both verifies that the Visitor works and demonstrates how another programmer should use it.
Notice how there is a method in the Visitor hierarchy for every derivative of the visited (Modem) hierarchy. This is a kind of 90-degree rotation — from derivatives to methods.
The test code shows that to configure a modem for Unix a programmer creates an instance of the UnixModemConfigurator class and passes it to the accept function of the Modem. The appropriate Modem derivative will then call visit(this) on ModemVisitor, the base class of UnixModemConfigurator. If that derivative is a Hayes, then visit(this) will call public void visit(Hayes). This will deploy to the public void visit(Hayes) function in UnixModemConfigurator, which then configures the Hayes modem for Unix.
Having built this structure, new operating system configuration functions can be added by adding new derivatives of ModemVisitor without altering the Modem hierarchy in any way. So the Visitor pattern substitutes derivatives of ModemVisitor for methods in the Modem hierarchy.
This is called dual dispatch because it involves two polymorphic dispatches. The first is the accept function. This dispatch resolves the type of the object that accept is called upon. The second dispatch is the visit method called from the resolved accept method. The second dispatch resolves to the particular function to be executed.
Thus, Visitor creates a matrix of functions. One axis of the matrix is the different types of modems. The other axis is the different types of operating systems. Every cell in this matrix is filled in with a function that describes how to initialize the particular modem for the particular operating system.
Visitor is fast. It requires only two polymorphic dispatches, regardless of the breadth or depth of the visited hierarchy.
A Dependency Cycle
Notice that the base class of the visited (Modem) hierarchy depends upon the base class of the Visitor hierarchy (ModemVisitor). Notice also that the base class of the Visitor hierarchy has a function for each derivative of the visited hierarchy. Thus there is a cycle of dependencies that ties all the visited derivatives (all the Modems) together. This makes it very difficult to compile the Visitor structure incrementally or to add new derivatives to the visited hierarchy.
The Visitor works very well in programs where the hierarchy to be modified does not need new derivatives very often. If Hayes, Zoom, and Ernie were the only Modem derivatives that were likely to be needed, or if the incidence of new Modem derivatives was expected to be infrequent, then the Visitor would be very appropriate.
On the other hand, if the visited hierarchy is highly volatile such that many new derivatives will need to be created, then the Visitor base class (e.g., ModemVisitor) will have to be modified and recompiled along with all its derivatives every time a new derivative is added to the visited hierarchy. In C++, the situation is even worse. The entire visited hierarchy must be recompiled and redeployed whenever any new derivative is added.
To solve these problems, a variation known as Acyclic Visitor [2] can be used. This variation breaks the dependency cycle by making the Visitor base class (ModemVisitor) degenerate [3]. The lack of any methods in this class means that it does not depend upon the derivatives of the visited hierarchy.
The visitor derivatives also derive from Visitor interfaces. There is one Visitor interface for each derivative of the visited hierarchy. This is a 180-degree rotation from derivatives to interfaces. The accept functions in the visited derivatives cast the Visitor base class [4] to the appropriate Visitor interface. If the cast succeeds, the method invokes the appropriate visit function. Figure 3 shows the structure, and Listings 8, 9, 10, 11, 12, 13, 14, 15, and 16 show the code.
This breaks the dependency cycle and makes it easier to add visited derivatives and do incremental compilations. Unfortunately it also makes the solution much more complex. Worse still, the timing of the cast can depend upon the width and breadth of the visited hierarchy and is therefore hard to characterize.
For hard real-time systems, the large and unpredictable execution time of the cast may make the Acyclic Visitor inappropriate. For other systems, the complexity of the pattern may disqualify it. But for those systems in which the visited hierarchy is volatile and incremental compilation is important, then this pattern can be a good option.
Using Visitor in Report Generators
A very common use of the Visitor pattern is to walk large data structures and generate reports. The value of the Visitor in this case is that the data structure objects do not have to have any report generation code. New reports can be added by adding new Visitors, rather than by changing the code in the data structures. This means that reports can be placed in separate components and individually deployed only to those customers that need them.
Consider a simple data structure that represents a bill of materials (see Figure 4). There is an unlimited number of reports that we could generate from this data structure. We could generate a report of the total cost of an assembly, or we could generate a report that listed all the piece-parts in an assembly.
Each of these reports could be generated by methods in the Part class. For example, getExplodedCost and getPieceCount could be added to the Part class. These methods would be implemented in each derivative of Part such that the appropriate reporting was accomplished. Unfortunately that would mean that every new report that the customers wanted would force us to change the Part hierarchy.
The CCP (Common Closure Principle) [5] told us to separate code that changes for different reasons. The Part hierarchy may change as new kinds of parts are needed. However, it should not change because new kinds of reports are needed. Thus we’d like to separate the reports from the Part hierarchy. The Visitor structure shown in Figure 4 shows how this can be accomplished.
Each new report can be written as a new Visitor. We write the accept function of Assembly to visit the Visitor and also call accept on all the contained Part instances. Thus the entire tree is traversed. For each node in the tree, the appropriate visit function is called on the report. The report accumulates the necessary statistics. The report can then be queried for the interesting data and presented to the user.
This structure allows us to create an unlimited number of reports without affecting the Part hierarchy at all. Moreover, each report can be compiled and distributed independently of all the others. This is nice. Listings 17, 18, 19, 20, 21, 22, and 23 show how this looks in Java.
Other Uses of Visitor
In general, the Visitor pattern can be used in any application where there is a data structure that needs to be interpreted many different ways. Compilers often create intermediate data structures that represent syntactically correct source code. These data structures are then used to generate compiled code. One could imagine Visitors for each different processor and/or optimization scheme. One could also imagine a Visitor that converted the intermediate data structure into a cross reference listing or even a UML diagram.
Many applications make use of configuration data structures. One could imagine the different subsystems of the application initializing themselves from the configuration data by walking it with their own particular Visitors.
In every case where Visitors are used, the data structure being used is independent of the uses to which it is being put. New Visitors can be created, existing Visitors can be changed, and all can be redeployed to installed sites without the recompilation or redeployment of the existing data structures. This is the power of the Visitor.
References and Notes
[1] Erich Gamma et al. Design Patterns (Addison Wesley, 1995), p. 331.
[2] Robert C. Martin et al. Pattern Languages of Program Design 3 (Addison Wesley, 1997), p. 93.
[3] A degenerate class is one that has no methods at all. In C++, it would have a pure virtual destructor. In Java, such classes are called "Marker Interfaces."
[4] In C++, we use dynamic_cast.
[5] See the "publications" section at http://www.objectmentor.com.
Robert C. Martin has been a software professional since 1970. He is president of Object Mentor Inc., a firm of highly experienced experts that offers high level object-oriented software design consulting, training, and development services to major corporations around the world. In 1995, he authored the best-selling book: Designing Object Oriented C++ Applications using the Booch Method, published by Prentice Hall. In 1997, he was chief editor of the book: Pattern Languages of Program Design 3, published by Addison Wesley. In 2000, he was editor of the book More C++ Gems, published by Cambridge Press. From 1996 to 1998, he was the editor-in-chief of the C++ Report. He has published dozens of articles in various trade journals and is a regular speaker at international conferences and trade shows. He is currently working in the area of lightweight productive processes and is a strong advocate and supporter of Extreme Programming.
This article is a segment from a chapter of Advanced Principles, Patterns, and Process of Object Oriented Software Development, Robert C. Martin, Prentice Hall, 2001. Copyright © 2001 Robert C. Martin, All rights reserved.