| Copyright 2003 Nikolas S. Boyd. All rights reserved. | Nik Boyd |
| Selective Visitor | Object Behavioral |
Represent an operation to be performed on the elements of an object structure, allowing the addition of new operations without changing the classes of the elements operated upon, and allowing the easy addition of new element classes to the framework.
The Visitor pattern1 allows you to define new operations on the elements of an object structure without changing the element classes on which they operate. During usage, a Visitor visits each element in the structure via recursive descent (if the elements are contained in a Composite structure), or via iteration (over the elements of a Collection), or via a combination of both (if the visited elements are both composed and collected).
The Visitor pattern has several useful positive consequences:
Adding new operations is easy. You can define a new operation by adding a new kind of Visitor. In contrast, if you define a new operation within the visited elements, you spread the new functionality over many classes and you must change each element class to define the new operation.
Related and unrelated operations can be maintained separately. Related behavior isn't spread over the various element classes in the object structure. Instead, it's localized in a Visitor class. Unrelated behaviors can be partitioned into their own Visitor subclasses.
Visited structural elements can come from different class hierarchies. Visitors can visit and operate on elements that do not share a common parent class.
Visitors can accumulate state information across an object structure. Without a Visitor, accumulated state would have to be passed as extra arguments to the structure traversal operations, or else cached in some accessible global object(s).
Traditional embodiments of the Visitor pattern also have two negative consequences:
Adding new structural element classes is hard. Each new kind of structural element introduced gives rise to a new abstract operation in the Visitor and a corresponding implementation in every ConcreteVisitor class derived from the abstract Visitor.
Encapsulation decisions are often compromised. Visited structural elements have to expose enough information for each Visitor to operate appropriately. This will often force encapsualtion compromises to ensure that Visitors have the information they need.
The Selective Visitor pattern eliminates the combinatorial explosion that occurs with the traditional Visitor pattern. Also, the Selective Visitor pattern can be extended with the Promised Visitation pattern to control the encapsulation leakage that often results from the traditional Visitor pattern. However, usage of the Selective Visitor pattern depends on programming language support:
Multiple classification is essential. Some object-oriented programming languages support multiple classification, either through implementation inheritance or interface inheritance. Examples include C++ (which supports multiple inheritance of classes) and Java (which supports implementation of separately defined interfaces).
Method overloading is preferable. Some object-oriented programming languages differentiate method signatures based on argument types in addition to method names. Examples of such languages include C++ and Java. While not an absolute requirement, method overloading makes the implementation of the Selective Visitor pattern more convenient.
Reconsider the compiler that represents programs using abstract syntax trees (ASTs) that was described in the original Visitor pattern.1 We still want to separate the analysis and the code generation behaviors from the AST nodes. In the traditional embodiment of the Vistor pattern, we would need to define an abstract NodeVisitor base class. This base class would define visit methods for all the various kinds of AST Nodes to be visited. Then, all the derived visitor classes would implement all the visit methods defined by the abstract NodeVisitor.
However, programming languages that support multiple classification allow us to define each visit method in a narrow, separate, Node-specific Visitor abstraction. Thus, we can have a different abstract class (or interface type) for each kind of Node to be visited. Then, each different kind of concrete Visitor extends only those abstract classes (or implements only those interfaces) defined by the concrete Nodes it needs (and intends) to visit.
Use the Selective Visitor pattern when
ObjectStructure (Program)
- can enumerate its elements,
either as a Composite or as a Collection (or both).
Element (Node)
- serves as a common base
abstraction for the elements included in the (composite or collective) object
structure.
ConcreteElement (AssignmentNode, VariableReferenceNode)
-
implements an accept operation that takes an element-specific visitor as an
argument.
ConcreteElement.Visitor (AssignmentNode.Visitor,
VariableReferenceNode.Visitor)
- defines a visit operation that takes a
specific kind of element as an argument.
ConcreteVisitor (CodeGeneratingVisitor)
- implements all
the specific element visitor abstractions for each kind of element it needs to
visit.
The Selective Visitor pattern has the same benefits conferred by the traditional Visitor pattern:
Visitor makes adding new operations easy. You can add a new operation simply by adding a new kind of visitor.
Visitor cleanly separates related operations from unrelated ones. Algorithms that need to traverse an object structure can be maintained separately from the elements contained in the object structure.
Visitors can cross different class hierarchies. Unlike the Iterator pattern, you aren't restricted to operations on classes derived from a single parent. Visitors can visit and operate on elements that do not share a common parent class.
Visitors can accumulate state information across an object structure. Without a Visitor, accumulated state would have to be passed as extra arguments to the structure traversal operations, or else cached in some accessible global object(s).
In addition, the Selective Visitor pattern confers the following benefits:
Straightforward element class additions. Because each element class comes with its own kind of visitor, concrete visitors can be selective about which elements they visit. Only those concrete visitors that need (and intend) to visit the selected structural elements must implement the corresponding element-specific visitor abstractions.
Explicit type checking. Programming languages that support multiple classification usually have compilers that check method argument types during compilation. Defining each element visitor in a separate type or class abstraction allows these compilers to check that all the declared relationships between visitors and the elements they visit have defined implementations. In effect, the problem of resolving combinations of elements vs. visitors is offloaded to the compiler.
Supportive Programming Environments. The Selective Visitor pattern relies on the ability to derive a class from multiple classification abstractions, whether such classifications are implemented using abstract base classes or (ideally) as declared types. This can be accomplished in C++ using multiple class inheritance and in Java using implementation of multiple interfaces.
Nested Classes or Types. While it may be possible to define each abstract Visitor separately, the preferred embodiment of the Selective Visitor pattern will use a nested definition for each abstract Visitor because of the convenience afforded by such packaging. When defined as a nested abstraction, each visited Element carries its nested Visitor along with it within its declaration. Nested abstraction also simplifies the naming of the abstractions.
Double-Dispatching. While it may be possible to define each visit method by including the name of the element class visited in the method name, the preferred embodiment of the Selective Visitor pattern will take advantage of multiple type dispatching for method resolution, esp. double-dispatching. Thus, the visit methods can use a common protocol without explicitly naming the kind of element visited. Instead, the kind of element visited will be declared in the method arguments of the various visit methods.
CodeGeneratingVisitor.java - a sanitized example of a code generating visitor from a compiler.
Node.java - a sanitized example of an abstract node from an AST.
AssignmentNode.java - a sanitized example of an assignment node from an AST.
VariableReferenceNode.java - a sanitized example of a variable reference node from an AST.
The compiler for the Bistro2 programming language was implemented in Java using the Selective Visitor pattern. The Bistro compiler translates Bistro source code into Java source code, which it then compiles to Java class files using a standard Java compiler. The Bistro compiler code generator visits the AST of a Bistro program using the Selective Visitor pattern. This approach allowed the code generation behavior to be separated from the AST, while allowing the elements of the AST to evolve during the design and development of the Bistro language.
Composite.1 Visitors are often useful for traversing and processing composite object structures.
Acyclic Visitor.3 Use of the traditional Visitor pattern entails referential dependency cycles between the Visitor and the visited Elements. While such dependency cycles ordinarily cause grief with the traditional Visitor pattern, the Selective Visitor pattern mitigates this grief by limiting the scope of each dependency cycle to each Element-specific Visitor / Element pair.
Promised Operations.4 Combining the Facet pattern5 with a variation of the Selective Visitor pattern provides the ability to selectively control the availability of an object's Facet(s) and thereby control availability of the operations associated with each Facet.