Visitor

Intent

• 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. [GoF, p331]
• The classic technique for recovering lost type information. [John Vlissides]
• Do the right thing based on the type of two objects.
• Double dispatch

Problem

Structure Summary

Structure category:  

Discussion

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

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

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().

Before and after

// BEFORE - The interface for "operations" are 
// specified in the Color base class and imple-
// mented in the Color derived classes.

// AFTER - The Color hierarchy specifies a
// single "accept()" method, and then the pre-
// vious "count()" and "call()" methods are
// implemented as Visitor derived classes.
// When accept() is called on a Color object,
// that is the first dispatch.  When visit()
// is called on a Visitor object, that is the
// second dispatch; and the "right thing" can
// be done based on the type of both objects.

class Color {
public:
   virtual void count() = 0;
   virtual void call()  = 0;
   static void report_num() {
      cout << "Reds " << s_num_red
           << ", Blus " << s_num_blu << '\n';
   }
protected:
   static int s_num_red, s_num_blu;
};
int Color::s_num_red = 0;
int Color::s_num_blu = 0;

class Red : public Color {
public:
   void count() { ++s_num_red; }
   void call() { eye(); }
   void eye() { cout << "Red::eye\n"; }
};

class Blu : public Color {
public:
   void count() { ++s_num_blu; }
   void call() { sky(); }
   void sky() { cout << "Blu::sky\n"; }
};

int main( void ) {
   Color* set[] = { new Red, new Blu, new Blu,
                    new Red, new Red, 0 };
   for (int i=0; set[i]; ++i) {
      set[i]->count();
      set[i]->call();
   }
   Color::report_num();
}

// Red::eye
// Blu::sky
// Blu::sky
// Red::eye
// Red::eye
// Reds 3, Blus 2

class Color {
public:
   virtual void accept( class Visitor* ) = 0;
};

class Red : public Color {
public:
   /*virtual*/ void accept( Visitor* );
   void eye() { cout << "Red::eye\n"; }
};
class Blu : public Color {
public:
   /*virtual*/ void accept( Visitor* );
   void sky() { cout << "Blu::sky\n"; }
};

class Visitor {
public:
   virtual void visit( Red* ) = 0;
   virtual void visit( Blu* ) = 0;
};

class CountVisitor : public Visitor {
public:
   CountVisitor() { m_num_red = m_num_blu = 0; }
   /*virtual*/ void visit( Red* ) { ++m_num_red; }
   /*virtual*/ void visit( Blu* ) { ++m_num_blu; }
   void report_num() {
      cout << "Reds " << m_num_red
           << ", Blus " << m_num_blu << '\n';
   }
private:
   int  m_num_red, m_num_blu;
};

class CallVisitor : public Visitor {
public:
   /*virtual*/ void visit( Red* r ) { r->eye(); }
   /*virtual*/ void visit( Blu* b ) { b->sky(); }
};

void Red::accept( Visitor* v ) { v->visit( this ); }
void Blu::accept( Visitor* v ) { v->visit( this ); }

int main( void ) {
   Color* set[] = { new Red, new Blu, new Blu,
                    new Red, new Red, 0 };
   CountVisitor  count_operation;
   CallVisitor   call_operation;
   for (int i=0; set[i]; i++) {
      set[i]->accept( &count_operation );
      set[i]->accept( &call_operation );
   }
   count_operation.report_num();
}

// Red::eye
// Blu::sky
// Blu::sky
// Red::eye
// Red::eye
// Reds 3, Blus 2

Rules of thumb

Iterator can traverse a Composite. Visitor can apply an operation over a Composite. [GoF, p173]

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. [Johnson, Huni, Engel, 1995, p8]

The Visitor pattern is the classic technique for recovering lost type information without resorting to dynamic casts. [Vlissides, "Type Laundering", C++ Report, Feb 97, p48]

Notes

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

[It also is useful when you want to perform the right algorithm, based on the type of two (or more) objects (aka "double dispatch"). Example algorithms might be: process a "collision" between different kinds of SpaceGame objects, compute the distance between different kinds of shapes, or compute the intersection between different kinds of shapes.]

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

Notes from the Sep-Oct 2000 issue of IEEE Software. McGraw and Felten (authors of 2 Java security books) describe their Jslint tool (statically scans Java code for security vulnerabilities). The end of the article summarized -

"Jslint parses the source file into a syntax tree that it can traverse using the Visitor design pattern. This pattern encapsulates each operation on a syntax tree into a single object called a Visitor, allowing users to define new operations on a tree without changing the tree elements. It encodes each [security] rule in a single Visitor that traverses the parse tree looking for instances of the violation in question ..... Users can easily port our tool to scan other languages by following three simple steps:"

1. replace the Java grammar
2. write a new set of Visitor classes
3. add a new user interface