Selective Visitor

Copyright 2003,2020 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 element classes 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:

  • 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 encapsulation 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 Visitor 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.

selective.node.visitor

Applicability

Use the Selective Visitor pattern when

  • you’re using a programming language that supports multiple classification (and ideally method overloading).
  • you want different kinds of operations on (different kinds of) elements in a composite structure.
  • you want to avoid extraneous operations in component classes that are not their essential responsibilities.
  • you want to easily add new kinds of components to the structure without compromising their existing designs.

Structure

selective.visitor

Participants

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

  • Element.Visitor (Node.Visitor)
    – serves as a base abstraction for concrete element type resolution.

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

Collaborations

  • A client that uses the Selective Visitor pattern creates a ConcreteVisitor object
  • The client traverses the ObjectStructure, visiting each element with the ConcreteVisitor.
  • The base Element class accepts an abstract Visitor, and sends itself to the Visitor.
  • The base Visitor class visits an abstract Element, and sends itself to the Element.
  • Each derived ConcreteElement class accepts a corresponding kind of Visitor.
  • When needed, dispatch shuttles back and forth between Visitors and Elements.
  • Ultimately, the ConcreteVisitor can then access the available state of each visited ConcreteElement.
  • Those elements that are themselves composites bear the responsibility for sending visitors to their nested components.

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

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

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.
  3. Robert Martin. Acyclic Visitor, also in Pattern Languages of Program Design, Volume 3. Addison-Wesley Publishing, Inc., 1997. ISBN 0-201-31011-2.
  4. Nik Boyd, Promised Operations. educery.dev, 2003.
  5. Erich Gamma. Extension Object (aka Facet), also in Pattern Languages of Program Design, Volume 3. Addison-Wesley Publishing, Inc., 1997. ISBN 0-201-31011-2.