Copyright 2003 Nikolas S. Boyd. All rights reserved. Nik Boyd

Selective Visitor Object Behavioral

Intent

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.

Motivation

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:

Traditional embodiments of the Visitor pattern also have two negative consequences:

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:

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.

Applicability

Use the Selective Visitor pattern when

Structure

Participants

Collaborations

Consequences

The Selective Visitor pattern has the same benefits conferred by the traditional Visitor pattern:

  1. Visitor makes adding new operations easy. You can add a new operation simply by adding a new kind of visitor.

  2. 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.

  3. 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.

  4. 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:

  1. 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.

  2. 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.

Implementation

  1. 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.

  2. 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.

  3. 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.

Sample Code

Known Uses

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.

Related Patterns

References

  1. Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley Publishing, Inc., 1995. ISBN 0-201-63361-2.
  2. Nik Boyd. The Bistro Project. bistro.sourceforge.net.
  3. Robert Martin. Acyclic Visitor, in Pattern Languages of Program Design, vol. 3. Addison-Wesley Publishing, Inc., 1997. ISBN 0-201-31011-2.
  4. Nik Boyd. Promised Operations. www.educery.com, 2003.
  5. Erich Gamma. Extension Object (aka Facet), in Pattern Languages of Program Design, vol. 3. Addison-Wesley Publishing, Inc., 1997. ISBN 0-201-31011-2.