• Represent an operation to be performed on the elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates.
• The classic technique for recovering lost type information.
• Do the right thing based on the type of two objects.
• Double dispatch

Problem

Many distinct and unrelated operations need to be performed on node objects in a heterogeneous aggregate structure. You want to avoid “polluting” the node classes with these operations. And, you don’t want to have to query the type of each node and cast the pointer to the correct type before performing the desired operation.

Discussion

Visitor’s primary purpose is to abstract functionality that can be applied to an aggregate hierarchy of “element” objects. The approach encourages designing lightweight Element classes - because processing functionality is removed from their list of responsibilities. New functionality can easily be added to the original inheritance hierarchy by creating a new Visitor subclass.

Visitor implements “double dispatch”. OO messages routinely manifest “single dispatch” - the operation that is executed depends on: the name of the request, and the type of the receiver. In “double dispatch”, the operation executed depends on: the name of the request, and the type of TWO receivers (the type of the Visitor and the type of the element it visits).

The implementation proceeds as follows. Create a Visitor class hierarchy that defines a pure virtual visit() method in the abstract base class for each concrete derived class in the aggregate node hierarchy. Each visit() method accepts a single argument - a pointer or reference to an original Element derived class.

Each operation to be supported is modelled with a concrete derived class of the Visitor hierarchy. The visit() methods declared in the Visitor base class are now defined in each derived subclass by allocating the “type query and cast” code in the original implementation to the appropriate overloaded visit() method.

Add a single pure virtual accept() method to the base class of the Element hierarchy. accept() is defined to receive a single argument - a pointer or reference to the abstract base class of the Visitor hierarchy.

Each concrete derived class of the Element hierarchy implements the accept() method by simply calling the visit() method on the concrete derived instance of the Visitor hierarchy that it was passed, passing its “this” pointer as the sole argument.

Everything for “elements” and “visitors” is now set-up. When the client needs an operation to be performed, (s)he creates an instance of the Vistor object, calls the accept() method on each Element object, and passes the Visitor object.

The accept() method causes flow of control to find the correct Element subclass. Then when the visit() method is invoked, flow of control is vectored to the correct Visitor subclass. accept() dispatch plus visit() dispatch equals double dispatch.

The Visitor pattern makes adding new operations (or utilities) easy - simply add a new Visitor derived class. But, if the subclasses in the aggregate node hierarchy are not stable, keeping the Visitor subclasses in sync requires a prohibitive amount of effort.

An acknowledged objection to the Visitor pattern is that is represents a regression to functional decomposition - separate the algorithms from the data structures. While this is a legitimate interpretation, perhaps a better perspective/rationale is the goal of promoting non-traditional behavior to full object status.

Structure

The Element hierarchy is instrumented with a “universal method adapter”. The implementation of accept() in each Element derived class is always the same. But – it cannot be moved to the Element base class and inherited by all derived classes because a reference to this in the Element class always maps to the base type Element.

When the polymorphic firstDispatch() method is called on an abstract First object, the concrete type of that object is “recovered”. When the polymorphic secondDispatch() method is called on an abstract Second object, its concrete type is “recovered”. The application functionality appropriate for this pair of types can now be exercised.

Example

The Visitor pattern represents an operation to be performed on the elements of an object structure without changing the classes on which it operates. This pattern can be observed in the operation of a taxi company. When a person calls a taxi company (accepting a visitor), the company dispatches a cab to the customer. Upon entering the taxi the customer, or Visitor, is no longer in control of his or her own transportation, the taxi (driver) is.

Check list

1. Confirm that the current hierarchy (known as the Element hierarchy) will be fairly stable and that the public interface of these classes is sufficient for the access the Visitor classes will require. If these conditions are not met, then the Visitor pattern is not a good match.
2. Create a Visitor base class with a visit(ElementXxx) method for each Element derived type.
3. Add an accept(Visitor) method to the Element hierarchy. The implementation in each Element derived class is always the same – accept( Visitor v ) { v.visit( this ); }. Because of cyclic dependencies, the declaration of the Element and Visitor classes will need to be interleaved.
4. The Element hierarchy is coupled only to the Visitor base class, but the Visitor hierarchy is coupled to each Element derived class. If the stability of the Element hierarchy is low, and the stability of the Visitor hierarchy is high; consider swapping the ‘roles’ of the two hierarchies.
5. Create a Visitor derived class for each “operation” to be performed on Element objects. visit() implementations will rely on the Element’s public interface.
6. The client creates Visitor objects and passes each to Element objects by calling accept().

Rules of thumb

• The abstract syntax tree of Interpreter is a Composite (therefore Iterator and Visitor are also applicable).
• Iterator can traverse a Composite. Visitor can apply an operation over a Composite.
• The Visitor pattern is like a more powerful Command pattern because the visitor may initiate whatever is appropriate for the kind of object it encounters.
• The Visitor pattern is the classic technique for recovering lost type information without resorting to dynamic casts.

Notes

The November 2000 issue of JavaPro has an article by James Cooper (author of a Java companion to the GoF) on the Visitor design pattern. He suggests it “turns the tables on our object-oriented model and creates an external class to act on data in other classes … while this may seem unclean … there are good reasons for doing it.”

His primary example. Suppose you have a hierarchy of Employee-Engineer-Boss. They all enjoy a normal vacation day accrual policy, but, Bosses also participate in a “bonus” vacation day program. As a result, the interface of class Boss is different than that of class Engineer. We cannot polymorphically traverse a Composite-like organization and compute a total of the organization’s remaining vacation days. “The Visitor becomes more useful when there are several classes with different interfaces and we want to encapsulate how we get data from these classes.”

His benefits for Visitor include:

• Add functions to class libraries for which you either do not have the source or cannot change the source
• Obtain data from a disparate collection of unrelated classes and use it to present the results of a global calculation to the user program
• Gather related operations into a single class rather than force you to change or derive classes to add these operations
• Collaborate with the Composite pattern

Visitor is not good for the situation where “visited” classes are not stable. Every time a new Composite hierarchy derived class is added, every Visitor derived class must be amended.

Vistor in Delphi

This session consists of the development of a small application to read and pretty-print XML and CSV files. Along the way, we explain and demonstrate the use of the following patterns: State, Interpreter, Visitor, Strategy, Command, Memento, and Facade.

Represent an operation to be performed on the elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates.

What the Visitor pattern does is move the operations on the tree (or other object structure) from the nodes of the tree to another class. This class needs enough information in the interface of each node to perform the operation, so sometimes this can mean more public properties and methods than you might like.

Visitors have been described in Delphi before so we won’t dwell overly on them. Essentially, what you need to do is declare a Visitor class, which declares a Visit operation for each node type in the object structure. Here’s the base visitor class for the XML interpreter:

  1: TXmlInterpreterVisitor = class(TObject)

  2: private

  3: protected

  4:   procedure Visit(Exp : TXmlStartTag); overload; virtual;

  5:   procedure Visit(Exp : TXmlEndTag); overload; virtual;

  6:   procedure Visit(Exp : TXmlNode); overload; virtual;

  7:   procedure Visit(Exp : TXmlTagList); overload; virtual;

  8:   procedure Visit(Exp : TXmlProlog); overload; virtual;

  9:   procedure Visit(Exp : TXmlDoc); overload; virtual;

 10: public

 11: end;

Visit methods are virtual so that visitor descendants can choose which methods to implement - it may not be necessary to implement them all. I’ve used function overloading as the signature is of necessity different for each, but this is not essential, and you could use more explicit names e.g. VisitXmlStartTag. The advantage of the function overloading is that it makes the code a little easier to follow, in my opinion.

In the base expression class we need to define an abstract Accept method. As for search and replace, the Delphi compiler forces us to implement the method in all the expression classes. You can see from the TXmlDoc implementation that the code is practically identical to the SearchAndReplace method shown earlier:

  1: procedure TXmlDoc.Accept(Visitor : TxmlInterpreterVisitor);

  2: begin

  3:   Visitor.Visit(Self);

  4:  

  5:   if Assigned(Prolog) then begin

  6:     Prolog.Accept(Visitor);

  7:   end;

  8: 

  9:   if Assigned(TagList) then begin

 10:     TagList.Accept(Visitor);

 11:   end;

 12: end;

The only difference is that we call the Visit method of the Visitor, which is passed as a parameter. Actually, I cheated a bit in one other method too, in order to make pretty printing work better, but if I skip lightly over it you’ll never notice.

Once the visitor code is in place in the syntax tree code, adding new visitors does not require any more changes to that code, only the declaration of new visitor classes.

A concrete visitor class is defined in XmlInterpreterVisitors.pas, showing how to implement a pretty printer. The parser is quite capable of taking a very badly formatted XML file and creating the syntax tree. We will regenerate the document all nicely laid out, like the example XML we saw earlier.

The class definition is:

  1: TXmlPrettyPrinter = class(TXmlInterpreterVisitor)

  2: private

  3:   FList   : TStringList;

  4:   FIndent : Integer;

  5: 

  6:   function GetText : string;

  7: protected

  8:   procedure AddString(AStr : string);

  9: public

 10:   constructor Create;

 11:   destructor  Destroy; override;

 12:  

 13:   procedure Visit(Exp : TXmlStartTag); override;

 14:   procedure Visit(Exp : TXmlEndTag); override;

 15:   procedure Visit(Exp : TXmlNode); override;

 16:   procedure Visit(Exp : TXmlProlog); override;

 17:   procedure Clear;

 18:  

 19:   property Text : string read GetText;

 20: end;
  

As you can see, we don’t need to implement a visitor for every expression class, as not all of them require anything to be printed. In fact, it’s only those that have terminal sub-expressions that will get anything printed. That is, the start and end tags, the data in a node, and the prolog.

We’ll keep track of the indent at each point, and on each new line we will prepend the correct number of spaces. I’ve decided to collect the newly formatted text in a TStringList as it will keep track of new lines for me. The GetText function just accesses the Text property of the list.

Some of the Visit methods are:

  1: procedure TXmlPrettyPrinter.Visit(Exp : TXmlStartTag);

  2: begin

  3:   AddString('<' + Exp.TagName + '>');

  4:   Inc(FIndent,IndentAmount);

  5: end;

  6: 

  7: procedure TXmlPrettyPrinter.Visit(Exp : TXmlEndTag);

  8: begin

  9:   Dec(FIndent,IndentAmount);

 10:   AddString('</' + Exp.TagName + '>');

 11:   AddString('');

 12: end;

 13: 

 14: procedure TXmlPrettyPrinter.Visit(Exp : TXmlNode);

 15: begin

 16:   if Exp.Data = '' then begin

 17:     // Print an empty tag

 18:     AddString('<' + Exp.StartTag.TagName + '/>');

 19:   end else begin

 20:     AddString(Format('<%s>%s</%s>',

 21:                      [Exp.StartTag.TagName,

 22:                       Exp.Data,

 23:                       Exp.EndTag.TagName]));

 24:   end;

 25: end;

On finding a start tag, we add the tag to the list, then increment the indent. On an end tag we do the reverse, decrementing first to bring it back into line with the start tag. We also add a blank line after the tag. As it happens, this will only be the case for tags surrounding XML collections, as the place I cheated is on individual data nodes. I arranged the TXmlNode.Accept routine so that if there is no TagList, the start and end tags are not visited, but are left to be dealt with in the node visitor method, as shown above. This is a cheat purely to let me print the tags and data on one line more easily.

Adding a new operation on the syntax tree is easy, we just add a new visitor (we could reimplement the search and replace this way, for instance). Now related operations are all in one class, and unrelated ones would be in different classes, rather than the Interpreter classes containing many unrelated operations in each class.

Visitor is a really nice pattern, and quite often useful. It is similar to Iterator in that it is used to traverse object structures, but Visitor also works when there is no common parent for the structure items. However, it does have some disadvantages. We mentioned breaking encapsulation earlier, but it can also make life difficult if you often need to add new elements to your structure. For instance, if we added new grammar rules, then we would need to add new methods to the base visitor, and check every concrete visitor to see if it also needed to reflect the changes.

So we can now read both XML and CSV files. It’s time to start feeding them documents.