The Visitor design pattern [Gamma95, pp 331] is revisited. The proposed visitor is designed to support composite structures which may be subclassified a posteriori in order to provide services with increasing levels of specialization. The proposed visitor is designed to support composite structures with both undistinguished and distinguished relationships. The proposed visitor is complemented with a mechanism to support both inherited (top-down) and synthesized (bottom-up) attribute flow during visitation. This visitor has been generated automatically to support generic, specific, and embedded language processing of Interpreter-Composite syntax-tree structures in the automatic refactoring of web applications.

1. Visitor

The Visitor pattern [Gamma95, pp 331] represents operations to be performed on the nodes or elements of a composite object structure. Visitor allows you to define new operations without changing the classes of the nodes on which they operate. While the visitor pattern represents a regression to functional decomposition by separating state from functional responsibilities, it also restores the notion of OO services to full stature; it promotes lightweight construction of classes by allowing the encapsulation of services away from their client classes.

Consider a group of professors and their students, who wish to spend a day at the museum. Rather than driving themselves to the museum, they hire a shuttle. They hire a guide at the museum to schedule tours and lectures for each individual, based on major, background and preferences. Rather than adding the responsibilities of driving themselves to the museum and teaching themselves, this composite structure of individuals have made use of two visitors which provide these services for them.

Consider the class structure for automotive parts manufacturing. Assume three operations need to be performed on these parts, fabrication cost calculation, fabrication time calculation, and compilation of raw material suppliers. The corresponding UML class structure is shown below.

Figure 1. Composite Structure Operations Without the Visitor pattern

The Visitor pattern allows us to separate and encapsulate all operations for calculating fabrication cost, fabrication time and listing suppliers into servicing classes called visitors.

Figure 2. Composite Structure Operations with the Visitor pattern

Performing these operations on the object structure changes as follows. Notice that a return value has been added to the standard Visitor accept signature in order to return a calculated value (attribute propagation through visits is discussed in a subsequent section).

public class ElectricalPart extends AutoPart {
      public Object accept (AutoPartVisitor v) {
            return v. visit (this);
      }
}

Double Dispatch. In OO languages, the method selected during invocation depends on the type of the receiver or method qualifier (e.g. the type of "electricalPart" above left). This is called single dispatch. In visitors, the operations performed are selected through a double dispatch mechanism; first the type of the composite object being visited (e.g. the type of "electricalPart" above right), and second, the type of the visitor (e.g. the type of "v" which is the type of "fabricationCostVisitor" above right). In the example above, this ensures that in the signature for the visit invocation ("visit (this)"), the parameter is not coerced to a superclass of "ElectricalPart" and thus the signature can be properly matched. In other words, if instead of "electricalPart. accept (fabricationCostVisitor)" we were to say "fabricationCostVisitor. visit (electricalPart)", then we could end up erroneously executing the visit operation for a superclass of "electricalPart". This is because in single-dispatch OO languages, method parameters are not resolved "polymorphically".

Reflective Visitor [Blosser00]. Adding new concrete classes to a composite structure is difficult with the Visitor pattern, because the Visitor interface and all the implementing visitors must be modified. This can be avoided by having one single visit operation for all node types which redirects the request to a private operation for each specific type using reflection. This is a very flexible mechanism that eliminates the need for a visitor interface though it still requires that all node types serviced explicitly by the visitor be known inside the given concrete visitor or its extensions thereof.

2. Motivation for Visitor SC

The Visitor pattern is designed to support operations or services on composite structures where all the node classes are known a priori, and unlike the Reflective Visitor pattern, it cannot be applied when these composite structures are later specialized or subclassed to address foreign concerns. When servicing these specialized composite structures, it may be important that each specialized concern provides its own corresponding localized visitors, such that these local visitors can be mixed and matched to constitute one single global visitor for the entire composite structure. Consider the following examples:

Consider a previous alternative. In Java Tree Builder [Palsberg00], JTB syntax trees are generated automatically from Sun Java CC grammar specifications. The visitor pattern generated by JTB requires the advance knowledge of all the node types in the syntax-directed composite structure. This restricts language processing to one single language and eliminates the possibility of building generic syntax-directed operations to support specific-language processing. In addition, the JTB naming conventions for the children of composite syntax tree nodes render the resulting code unreadable.

The objective of the Visitor SC pattern is to provide the following:

3. Standardization of the Visitor Pattern

We now standardize on desirable characteristics of the Visitor Pattern.

Adaptive Traversal Composition. The Composite pattern [Gamma95, pp 163], allows you to represent hierarchies by providing uniform treatment of individual and composite objects. An object in a hierarchy tree is a node. A composite node is comprised of constituent nodes called children. In a composite pattern structure, these children are indistinguished, meaning that the role of one child in relationship to its parent is not differentiable from the role of another child. The Interpreter pattern [Gamma95, pp 243] is a Distinguished Composite pattern; that is, a Composite pattern in which the children of a composite node may be dedicated to specific relationships with their parent. In order to support generic visitation we require that all the node classes in a distinguished or indistinguished composite structure support adaptive traversal composition, by implementing Iterator [Gamma, pp 257], or one or more structure-shy traversal mechanisms. In the case of distinguished composition, the implementation of Iterator could be supported with static "grammar" properties to properly select children among all class fields (see also the Object Grammar pattern [Lieberherr97]), and with the use of reflection. The implementation of Iterator and other traversal interfaces in distinguished composition classes helps isolate traversal from operational concerns (see the Adaptive Traversal pattern [Lieberherr00]).

Adaptive Traversal Inside Visitors. Composite structure traversal is moved to the visitor, because such traversal is an intrinsic part of the control flow of the operations implemented in visitors, and not an inherent characteristic of the composite class being serviced. In addition, visitors can be emplemented as extensions of common traversal visitors. By using adaptive traversal patterns, traversal is decoupled from the composite structure of the serviced classes and generic traversal visitors can also be implemented.

Attribute Flow During Visitation. Visitors are commonly used to affect the state of the visited classes and / or retrieve computed values related to the structure. In addition to visitors' being able to hold a state, visitors need a mechanism for the propagation of visit values or attributes during structure traversal. Inherited attributes are propagated top-down during traversal while synthesized attributes are collected bottom-up during traversal. We modify the visit signature to propagate inherited attributes through a visit parameter, and collect synthesized attributes through a visit return object.

Single Name for Visit Signatures. Instead of using different method names for visits to the different classes in the composite structure (e.g. visitInteger (Integer integer)), we use only one single method name (i.e. visit) overloaded for each class in the structure (e.g. visit (Integer integer)). This gives us the flexibility to implement a visitor interface with either multiple overloaded methods, one for each class, or else with one single method which acts as a Facade [Gamma95] to redirect the call using reflection to the multiple visit methods defined privately inside the visitor [Blosser00].

4. A Visitor for Specializable Composition

The solution is straight forward. We break down Visitor into a visitor dispatcher which perfoms mediation, and one or more visitor delegates which perform the actual visitation.

Figure 3. Automatic Construction Phase of Visitor SC

The following UML class diagram shows the operation building phase. Notice that the "accepts" association between the formatters and Node would be more accurately represented as an association between the traversal delegates and Node which is then inherited by all subclasses, but it was represented instead between the subclasses just to more explicitly display the implementation responsibilities for these operations.

Figure 4. Manual Operation Building Phase with Visitor SC

5. Complementing Visitation with the Attribute Flow Factory Pattern

There are three ways to accumulate state during visitor-driven operations:

Notice that node traversal has been separated from the visit and encapsulated into a structure-independent traversal mechanism. In its simplest form, as it may apply to true indistinguished composite structures, traversal can be implemented with Iterator. In distinguished composite structures, such as Interpreter, where children nodes may be distinguished with dedicated names and for dedicated purposes, variations of the AdaptiveTraversal patterns may be implemented, as explained earlier. Adaptive traversal allows generic support of distinguished composites, such as syntax trees.

Notice also that the mechanics of attribute flow propagation and manipulation have also been separated from the visit itself and into encapsulated attribute flow strategies. This eliminates the redundancy of repeating these flow mechanics in every single visit, and increases the reusability of the visit. For example, consider the implementation of a concrete attribute flow named a StringCollector, which would return a concatenation of all strings collected during the visit. If StringCollector were to be used as the concrete AttributeFlow in the visit above, such visit could be used without change as the generic default visit in a syntax tree formatter or pretty printer.

6. A Reflective Visitor SC Pattern

Having all nodes in a subdomain always visited by the local visitor delegate for that domain offers many advantages. In visitor-intensive applications, it is convenient to make sure that the implemented operations are localized, in order to insure that a decision has been made about the processing of each node in the subdomain, and visitor interfaces provide such reassurances. For example, in language processing, it is convenient to know that all the decisions regarding name resolution for embedded SQL are being made the SQL visitor and not passed on to the enclosing ColdFusion visitor. However, if we remove the contractual requirement that all nodes in every subdomain must be visited by its local delegate, we can replace all single-dispatching sequences in the Visitor SC pattern with one multiple dispatching operation using reflection. The accept method would no longer be necessary but left in the pattern for consistency with future versions of a visitor pattern. Coercions can be eliminate and the accept method implemented as prescribed in the original Visitor pattern. Only one visitor dispatcher class, independent of any composite structure, would be needed, and with one single visit operation, as follows:

      public void accept (Visitor v) {  
         v. visit (this);
      }

      public class Visitor {
            ...

            Vector orderedDelegates = new Vector ();

            public Attribute visit (Object node, Attribute inherited) {
                  Object [] parameters = new Object [] {node, inherited}
                  Class [] parameterClasses = new Class [] {o. getClass (), Attribute. class};
                  ListIterator it = orderedDelegates. listIterator ();
                  while (it. hasNext ()) {
                        try {
                              Object delegate = it. next ();
                              Method delegateVisit = delegate. next (). getClass (). getMethod ("visit", parameterClasses);
                              return (Attribute) delegateVisit. invoke (delegate, parameters);
                        }
                        catch (NoSuchMethodException e) { }
                  }
                  throw new Error ("No such visitor method found");
            }

      }

The following figure shows the architecture for the automatic construction phase using reflective multiple dispatching.

Figure 5. The Automatic Construction Phase Using Reflective Dispatching

Notice how the construction phase has been simplified by using reflection, though must of the simplification comes from the elimination of the contractual interfaces for subdomain visitors.

6. Experience

The Visitor SC pattern as described in this paper has been used extensively as the major infrastructure for the construction of operations over embedded syntax tree structures in the eKnowlogie language processing environment. The classes and organization presented under the automatic generation phase is generated automatically, including syntax tree classes from language grammars and including support for adaptive traversal and the abstract flow factory. This Visitor SC pattern has provided support for convenient generic and embedded multi-language processing, as needed for the ColdFusion to Java J2EE Migrator refactoring technology. ColdFusion applications are web applications written in Html with embedded ColdFusion which in turn contains embedded SQL.

7. References

[Blosser00] Jeremy Blosser. The Reflective Visitor Design Pattern. JavaWorld, July 14, 2000.

[Cooper98] James W. Cooper. The Design Patterns Java Companion . IBM Watson Research Center, 1998.

[Gamma95] Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides. Design Patterns, Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995.

[Grand98] Mark Grand. Patterns in Java, Volume 1 . John Wiley & Sons, 1998.

[Grand99] Mark Grand. Patterns in Java, Volume 2. John Wiley & Sons, 1999.

[Hillside] Patterns Library.

[Huston02] Vince Huston. Design Patterns , see Abstract Factory, Composite, Facade, Interpreter , Iterator, Mediator , Visitor . Feb 11, 2002.

[Lieberherr97] Karl Lieberherr. The Object Grammar Pattern . Patterns for Adaptive Programming, Jan 5, 1997.

[Lieberherr00] Karl Lieberherr. The Adaptive Traversal Pattern . Patterns for Adaptive Programming, Sept 15, 2000.

[Moore00] John Moore. Delegation vrs Inheritance . jGuru, March 23, 2000.

[Palsberg00] Jens Palsberg, Kevin Tao, Wanjun Wang. Java Tree Builder. Evolution of Software via Adaptive Programming, DARPA EDCS. Purdue University, August 6, 2000.

[Sintes01] Tony Sintes. True Delegation , JavaWorld, Sept 14, 2001.