The Visitor pattern provides a way to add new polymorphic behavior to a class hierarchy without changing the hierarchy. Visitor has another advantage over virtual functions in that it localizes behavior to the visitor class rather than spreading it across the hierarchy.
As the need for Visitor is discovered, a programmer has two choices:
- Create visitors by hand or
- Use template libraries such as Loki [4] to automate visitor creation.
Irrespective of what option the programmer chooses, the problem inherent to visitor soon crops up—visitor commits to too much too early.
The standard visitor implementation requires implementing a "bouncing" function in every visitable class that calls the appropriate Visit method in the visitor. This function is generally called Accept:
class Shape {
public:
// bouncing function
virtual int Accept( ShapeVisitor& visitor )
{
return visitor.Visit( *this ); // call ShapeVisitor::Visit( Shape& )
}
};
class Circle : public Shape {
public:
virtual int Accept( ShapeVisitor& visitor )
{
return visitor.Visit( *this ); // call ShapeVisitor::Visit( Circle& )
}
};
The Accept function is virtual and it invokes the appropriate Visit method, which is also virtual. This implements a limited form of multiple dispatch called double-dispatch.
Since the Accept function must be virtual, it cannot be a template—it must hard-code all the knowledge about visitation, the return type, and the number of arguments.
As a result, a print method implemented as a visitor for the Shape hierarchy above must return an int while it might be better to return void or the output stream itself. Visitor often forces the programmer to write useless return statements and then store the return values as member variables. All arguments must also be marshaled as member variables.
class ShapePrinter : public ShapeVisitor {
std::ostream& output_; // marshall stream as member
public:
ShapePrinter( std;:ostream& o )
: output_( o )
{ }
virtual int Visit( Shape& shape ) { /* print shape */ return 0; }
virtual int Visit( Circle& circle ) { /* print circle */ return 0; }
};
The same operation expressed as a virtual function is cleaner:
class Shape {
public:
virtual void print( std::ostream& output )
{
// print shape
}
};
class Circle : public Shape {
public:
virtual void print( std::ostream& output )
{
// print circle
}
};
Once a hierarchy commits to a return type, it's pretty much stuck with it forever.
Another serious limitation is that while it is easy to const-qualify a virtual function, it is difficult to specify const/non-const visitors. Expressing virtual functions as visitors requires implementing the visitor pattern twice for a hierarchy— once each for the non const and const versions. It is impossible to implement const visitors and non-const visitors for the same hierarchy using the Loki library[2][4] .
The standard visitor also has a cyclic dependency problem: every class knows about the visitor which knows about all other classes in the hierarchy. This often causes recompilation of modules when a new class is added. There's a solution to this called Acyclic Visitor[1] that uses dynamic casts to overcome this problem but is slower than cyclic visitor.
Cooperative Visitor
Cooperative Visitor is a template-based technique for finding reasonable solutions to the above- mentioned problems. It allows:
- Flexibility of acyclic visitor with performance closer to cyclic visitor
- Easier to use, maintain and modify
- Better semantic names rather than "visit"
- Easy creation of const/non-const visitors
- Flexible return and argument types
- Dynamic configuration of visitation behavior
- Implementing a default handler
- Developing template code upon visitor
The print example could be expressed using Cooperative Visitor as:
class ShapePrinter : public Visitor< const Shape, void > {
std::ostream& output_;
public:
ShapePrinter( std::ostream& o ) : output_( o )
{
Visits( *this, Seq< Shape, Circle >::Type(), PrintInvoker() );
}
public:
void print( const Shape& shape ) { /* print shape */ }
void print( const Circle& circle ) { /* print circle */ }
typedef VISIT_INVOKER( print ) PrintInvoker;
};
ShapePrinter decides the return type as well as the const-ness through template arguments to Visitor. The visit methods are not virtual and are called print. There is no cyclic dependency: Shape and Circle know nothing about ShapePrinter. The stream could also be passed as an extra argument to print.
Internals
The technique uses following approach:
- Generate a unique tag ( integer value) for every visitable class in a hierarchy
- Provide a way for every visitable object to return its tag
- Build a "virtual function table" where:
-
Table [ Tag ] = &Visit( Class ), where:
- Where
Tableis the virtual table Tagis a tag valueVisitis the visit handler (a thunk: details follow)Classis the class that has integer value "tag"
- Where
-
- When a visit operation is requested on an object, the tag of the object is retrieved and used as index into the "vtable." Then the visit function is invoked with the object as the argument.
The remainder of this article takes an in-depth look at an implementation.
Generating tags
C++'s enumeration types generate unique integer values but require knowledge of the number of tags (classes), a coupling similar to cyclic dependency. Templates provide a clean solution.
For every hierarchy we can generate a tag counter to keep track of next available tag:
template< typename Base >
struct TagCounter
{
static size_t s_counter; // declaration
}
template< typename Base >
size_t TagCounter< Base >::s_counter; // definition: default 0
For every visitable class, we can create a variable to store its tag:
template< typename Visitable, typename Base >
struct TagHolder {
static size_t s_tag;
};
A tag is initialized the first time It is requested:
template< typename Visitable, typename Base >
size_t GetTag()
{
size_t& tag = TagHolder< const Visitable, const Base >::s_tag;
if( tag == 0 ) {
// first time : generate tag
tag = ++TagCounter< const Base >::s_counter;
}
return tag;
}
The GetTag templates applies const qualifier to its arguments and so GetTag<Circle, Shape> and GetTag<const Circle, Shape> both return the same tag value. This prevents unnecessary tag generation and treats const/non-const objects in the same way.
To ensure initialization at startup, we force a call to GetTag while defining the tag variable.
template< typename Visitable, typename Base > size_t TagHolder< Visitable, Base >:: s_tag = GetTag< Visitable, Base >();
This tag generation technique doesn't require class definitions of Visitable and avoids cyclic dependencies. We cannot use local static variables in header files since a compiler could generate local static variables in every compilation unit.
Multi-threaded use of the tag generation technique during startup should be avoided or otherwise would require the counter variable would need to be wrapped using a synchronization primitive.
Tag retrieval
Curiously Recurring Template Pattern ( CRTP )[3] allows defining a helper function in Base that every Visitable class can use to retrieve its tag:
// Base class must inherit from BaseVisitable
template< typename Base >
struct VisitableBase {
template< typename Visitable >
size_t GetTagHelper( const Visitable* /* this */ ) const
{
return GetTag< Visitable, Base >();
}
};
A macro helps defining a virtual function in every Visitable class to return its tag:
#define VIS_DEFINE_VISITABLE() \
virtual size_t Tag() const \
{ \
return GetTagHelper( this ); \
}
Visitable is an empty base class and the compiler could optimize it away. Here's how a client would look like (similar to Loki):
class Shape : public VisitableBase< Shape > {
public:
VIS_DEFINE_VISITABLE()
};
class Circle : public Shape {
public:
VIS_DEFINE_VISITABLE()
};
The VTable
The VTable is parameterized over the type of function it holds as well as the Base class.
template< typename Base, typename Func >
class VTable {
std::vector< Func > table_; // storage
A new function is added to the table by passing the Visitable to find out the slot.
template< typename Visitable >
void add( Func f )
{
size_t index = GetTag< Visitable, Base >(); // find the slot
if( index >= table_.size() ) {
// find function for Base if it exists
const size_t base_tag = GetTag< Base, Base >();
Func default_function = ( base_tag >= table_.size() ) ? 0
: table_[ base_tag ];
// expand the table
table_.resize( index + 1, default_function );
}
table_[ index ] = f;
}
An indexing operation is also provided:
Func operator[] ( size_t index ) const
{
if( index >= table_.size() )
index = GetTag< Base, Base >();
return table_[ index ];
}
}; // VTable
The VTable defaults to function for Base during expansion and retrieval resulting in a behavior closer to cyclic than acyclic visitor.
The Cooperative Visitor
Cooperative Visitor technique allows implementing visitors that take N arguments. For this discussion we look at a library implementation that allows creating visitors that take just one argument: the object being visited.
template< typename Base, typename ReturnType > class Visitor;
Clients derive from Visitor and implement necessary visit methods:
class ShapeVisitor : public Visitor< Shape, double > {
public:
double Visit( Shape& ) { /* implementation */ }
double Visit( Circle& ) { /* implementation */ }
double Visit( Polygon& ) { /* implementation */ }
};
Due to complexities involved in implementing single, multiple, and virtual inheritance, member functions of one class cannot be safely casted to member functions of another class.
So member functions of ShapeVisitor must somehow be transformed into member functions of Visitor so that they can be stored in the VTable. This is accomplished using thunks.
Member function thunks
Thunks are small functions that map data from one form to another. They are often used to cast the this pointer and arguments before calling another function. Thunks are found in Loki Library (trampoline trick) and also used by compilers to implement virtual functions. We use thunks to generate functions in Visitor that calls visit functions in its derived classes:
template< typename Base, typename ReturnType >
class Visitor {
template< typename VisitorImpl, typename Visitable >
ReturnType thunk( Base& b )
{
// first dispatch: eg: cast to ShapeVisitor&
VisitorImpl& visitor = static_cast< VisitorImpl& >( *this );
// second dispatch: eg: cast to Circle&
Visitable& visitable = static_cast< Visitable& >( b );
// invoke visit method: eg: call ShapeVisitor::Visit( Circle& )
return visitor.Visit( visitable );
}
The thunk member template is a thunk generating engine and a thunk has the signature ReturnType (Visitor::*)( Base& ). Since a thunk transforms actual Visit methods defined in derived visitor implementation classes to member functions of the Visitor class, it is a form of adapter. The thunks are stored in a statically created VTable and each Visitor instance holds a pointer to a vtable.
typedef ReturnType (Visitor::*Func) ( Base& ); const VTable< const Base, Func >* vtable_; // vtable pointer
The function call operator implements the visitation. It retrieves the tag from the object and uses it as index to fetch the thunk from the vtable. Then it calls the thunk to initiate visitation:
ReturnType operator() ( Base& b )
{
Func thunk = (*vtable_ )[ b.Tag() ]; // fetch thunk
return ( this->*thunk ) ( b ); // pointer to member function syntax
}
}; // Visitor
Policy-based design
We can achieve name independence by using a policy class, Invoker, that calls the visit method. This allows context based names for visit functions and is important in light of this excerpt: "the Visitor Pattern has nothing to do with visitation—the name was a real stumbling block for me" (Scott Meyers, My Most Important C++ Aha! Moments ..Ever[8]
template< typename VisitorImpl, typename Visitable, typename Invoker >
ReturnType thunk( Base& b )
{
VisitorImpl& visitor = static_cast< VisitorImpl& >( *this );
Visitable& visitable = static_cast< Visitable& >( b );
return Invoker::Invoke( visitor, visitable );
}
A Invoker that uses print functions can be written as follows:
struct PrintInvoker {
template< typename VisitorImpl, typename Visitable >
static ReturnType Invoke(VisitorImpl& visitor, Visitable& visitable )
{
check_member_function< ReturnType, VisitorImpl, Visitable >
( &Visitor::print ); // compile time assertion
return visitor.print( visitable );
}
};
check_member_function is a compile-time assertion that would result in errors if the function VisitorImpl::print( Visitable& ) was not found. This prevents the compiler from silently choosing VisitorImpl::print( Base& ). The print functions can return any type that is convertible to ReturnType.
A macro can ease creating invokers :
#define VISIT_INVOKER( name ) \
struct { \
same code as print invoker but uses name \
}
VISIT_INVOKER creates an anonymous struct that clients could typedef within their Visitor implementations.
class ShapeRenderer : public Visitor< const Shape > { // const visitor
public:
void render( const Shape& ) { /* degenerate case */}
void render( const Circle& ) { /* draw a circle */ }
typedef VISIT_INVOKER( render ) RenderInvoker;
};
Const-Visitors
Const-Visitors have visit methods of form ReturnType Visit( const Visitable& ). The following template code expresses the relationship between Base and Visitable:
template< typename Visitable, typename Base >
struct GetVisitMethodArgumentType {
typedef Visitable Type; // ReturnType Visit( Visitable& )
};
// specialize for const Base
template< typename Visitable, typename Base >
struct GetVisitMethodArgumentType< Visitable, const Base > {
typedef const Visitable Type; // ReturnType Visit( const Visitable& )
};
The thunk engine makes use of the above class template to perform either const or non-const visitation.
template< typename VisitorImpl, typename Visitable, typename Invoker >
ReturnType thunk( Base& b )
{
typdef typename GetVisitMethodArgumentType< Visitable, Base >
::Type VisitableType;
VisitorImpl& visitor = static_cast< VisitorImpl& >( *this );
VisitableType & visitable = static_cast< VisitableType & >( b );
return Invoker::Invoke( visitor, visitable );
}
Visitor< Shape, int > and Visitor< const Shape, Shape* > are a non-const visitor returning int and a const visitor returning Shape* respectively.
Creating VTables
Typelists are especially useful for automating table creation[2]. We use a minimalistic implementation borrowed from Loki library. The Seq template helps creating typelists:
typedef Seq< Shape, Circle, Rect, Square >::Type VisitedList1; typedef Seq< Note, GraceNote >::Type VisitedList2;
In order to execute some code for every type in a typelist, we need to implement an "action class" with operator():
struct Action {
template< typename T >
void operator() ( const T* /* type hint */ )
{
// do something for type T
}
};
The action can be applied for every type in a typelist:
apply( VisitedList1(), Action() ); // Shape, Circle, Rect, Square apply( VisitedList2(), Action() ); // Note, GraceNote
That's all we need to know about typelists to create vtables. We implement a parameterized action class that creates vtables:
template< typename Visitor, typename VisitedList, typename Invoker >
struct CreateVtable {
typename Visitor::VTable vtable_; /* vtable object */
The list of classes that need to be visited is represented by VisitedList. For every class in the list, the appropriate thunk is instantiated and added to the vtable:
template< typename Visitable >
void operator () ( const Visitable* /* hint */ )
{
vtable_.template add< Visitable > ( // add to vtable
&Visitor::template thunk < // instantiate thunk
Visitor,
Visitable,
Invoker
>
);
}
The constructor adds the function for Base first and then invokes apply to create the complete vtable with slots filled:
CreateVtable()
{
// add Base's visit function first
( *this ) ( static_cast< typename Visitor::Base* >( 0 ) );
// add visit function for each type in VisitedList
apply( VisitedList(), *this );
}
}; // CreateVtable
Vtables can be shared between Visitor instances by creating static vtables. This can be achieved through static members of template classes:
template< typename Visitor, typename VisitedList, typename Invoker >
struct GetStaticVtable {
// declare static instanceof vtable
static CreateVtable< Visitor, VisitedList, Invoker > s_table;
// provide conversion operator
operator const typename Visitor::VTable*() const
{
return &s_table.vtable_;
}
};
Type inference provided by functions is helpful for easing client usage:
// global helper function
template< typename Visitor, typename VisitedList, typename Invoker >
void Visits( Visitor& visitor, const VisitedList&, const Invoker& )
{
// instantiate the static vtable and set the vtable pointer
visitor.vtable_ = GetStaticVtable< Visitor, VisitedList, Invoker >();
}
A separate vtable is created for a combination of Visitor, VisitedList, Invoker types.
The client needs to call Visits in the constructors of the Visitors being implemented. This allows minimizing recompilation by moving the constructor body into cpp files. The alternative of passing the list of visited classes as another template parameter to Visitor wouldn't allow this flexibility. Also for every list of passed as a template argument, a new Visitor class would be generated, preventing Visitors that return the same type from having a common base class.
Putting it all together: examples
Here's how a client might implement a cloning const visitor for a shape hierarchy:
class Cloner : public Visitor< const Shape, Shape* > {
public:
Cloner()
{
// set the vtable pointer
Visits( *this, Seq< Circle, Square, Rect >::Type(),
CloneInvoker() );
}
private:
template< typename SomeShape >
SomeShape * clone( const SomeShape& s) { return new SomeShape( s ); }
typedef VISIT_INVOKER( clone ) CloneInvoker;
};
void func( const Shape& s )
{
Cloner clone;
Shape* copy = clone( s ); // invoke () operator
// do some stuff
}
There's also ability to change behavior by choosing a different vtable during runtime:
class Renderer : public Visitor< const Shape, void > {
public:
Renderer( bool curved )
{
if(curved )
Visits( *this, Seq< Circle, Bezier >::Type(), DrawInvoker() );
else
Visits( *this, Seq< Square, Rect >::Type(), DrawInvoker() );
}
void draw( const Shape& );
void draw( const Bezier& );
// other draw implementations
typedef VISIT_INVOKER( draw ) DrawInvoker;
};
The Visitor pattern is especially useful in compilers for manipulating syntax tree representations of a source program. Consider a syntax tree hierarchy:
class ASTree : public VisitableBase< ASTree > {
VIS_DEFINE_VISITABLE()
};
class Expression : public ASTree {
VIS_DEFINE_VISITABLE()
};
class UnaryExpression : public Expression {
// expression formed by operators unary +, -, & etc
VIS_DEFINE_VISITABLE()
};
class BinaryExpression : public Expression {
// expressions formed by binary arithmetic operators +, -, *, / etc
// shift operators, assignment operators etc
VIS_DEFINE_VISITABLE()
};
class Statement : public ASTree {
VIS_DEFINE_VISITABLE()
};
class IfStatement : public Statement{
VIS_DEFINE_VISITABLE()
};
class ForStatement : public Statement{
VIS_DEFINE_VISITABLE()
};
A visitor is ideal for type checking syntax trees, pretty-printing, transforming etc. Cooperative Visitor is especially useful since some operation on trees are non modifying, others modifying; each operation has different return type, etc.
Here's how a type-checking visitor may be written in stages. A type checker also annotates the syntax tree with the type for each node in the tree and also returns the type of the node being processed:
// type check expressions
class ExpressionChecker : public Visitor< ASTree, Type* > {
public:
typedef Seq< UnaryExpression, BinaryExpression >::Type VisitedList;
ExpressionChecker()
{
Visits( *this, VisitedList(), TypeCheckInvoker () );
}
Type* type_check( ASTree& );
Type* type_check( UnaryExpression& );
Type* type_check( BinaryExpression& );
typedef VISIT_INVOKER( type_check ) TypeCheckInvoker;
};
// type check statements
class StatementChecker : public ExpressionChecker {
public:
// list of typechecked statements
typedef Seq< IfStatement, ForStatement >::Type List;
// merge the lists
typedef Append< List, ExpressionChecker::VisitedList >::Type VisitedList;
StatementChecker()
{
Visits( *this, VisitedList(), TypeCheckInvoker () );
}
Type* type_check( IfStatement& );
Type* type_check( ForStatement& );
// make Expressionchecker's methods visible
using ExpressionChecker::type_check;
};
It should be possible to automate building visitors in stages mimicking C++'s virtual table mechanism without the user having specifying the merged list of types being visited as above.
Future directions
Default vtable
When a visitor is constructed, unless Visits is invoked, the vtable_ pointer is null. Compile time techniques could be used to ensure that a visitor always has a valid vtable.
Casting
static_cast won't work with virtual inheritance. Hence the thunk needs to handle casting to Visitable as a policy as well. This allows choice on a per class basis. Another alternative would be for the Tag virtual function to return the tag as well as the this pointer (as void* to prevent any implicit casting). A thunk would then take a void* as argument and reinterpret_cast it to appropriate Visitable type.
template< typename VisitorImpl, typename Visitable, typename Invoker >
ReturnType thunk( void* b ) // or const-void *
{
VisitorImpl& visitor = static_cast< VisitorImpl& >( *this );
VisitableType * visitable = reinterpret_cast< VisitableType* >( b
);
return Invoker::Invoke( visitor, *visitable );
}
ReturnType operator() ( Base& b )
{
// fetch tag and this pointer
std::pair< size_t, void* > tag_ptr = b.TagAndPtr();
Func thunk = (*vtable_ )[ tag_ptr.first ];
return ( this->*thunk ) ( tag_ptr.second );
}
Fast Visitor
Cooperative Visitor technique avoids the dynamic_cast required by acyclic visitor yet provides a similar amount of flexibility. It's performance should be closer to that of cyclic visitor. A virtual function call could be eliminated if visitable classes stored the tags as a member rather than returning them from a virtual function (Tag).
DLLs
Windows DLLs present a problem: every DLL gets its own copy of static variables. This would result in the same class being associated with different tags in different DLLs. This problem can be solved by exporting tag generation functions from a single DLL and ensuring that each copy of tag variable for a class is initialized with the same tag value. This can be achieved without any change to the client usage model presented in the article. A complete discussion is beyond the scope of this article.
Ad-Hoc Visitor
All forms of visitor pattern require modifying the class hierarchy: the Accept method or the Tag method. In a hierarchy where such a change is not possible, typeid could be used to provide a form of ad-hoc visitation[5]. The vtable would then be a map with type_info objects as keys and thunks as values. Ad-hoc visitation could be specified as a template argument to the visitor and much of other client usage should remain unchanged.
Custom Signature for Visit Methods
Variadic templates (C++0x) would be of great help in defining visitors that take N arguments. Having ability to pass extra arguments avoids having to implement such state as members of the Visitor.
Static Visit Methods
Static functions can be defined easily whereas once a class is defined one cannot add new member functions to it. Static visit methods would provide even more flexibility.
Instance vtables
Certain visitor instances could create and own their own vtables rather than using shared static vtables. This allows per object level dynamism but increases visitor construction cost.
Conclusions
Cooperative Visitor technique provides the flexibility of Acyclic visitor with performance that approaches the Cyclic visitor. Cooperative Visitor provides advantages over standard visitor implementations by allowing configuration: the name of visit methods, the return type, the const-ness, the number of arguments. The ease of use approaches that of other Visitor implementations and libraries. The technique is standard C++ and is portable.
End notes
1. Robert Martin, Acylic Visitor presents a technique discussion of the Acyclic Visitor Pattern
http://www.objectmentor.com/resources/articles/acv.pdf
2. Andrei Alexandrescu. Modern C++ Design (Addison-Wesley Longman, 2001) is a good reference for generic programming, typelists, policy-based design, visitor pattern and the Loki Library.
3. James Coplien, Curiously Recurring Template Patterns. February 1995
4. Loki Library
http://loki-lib.sourceforge.net
5. Andrei Alexandrescu, Generic Programming: Typelists and Applications, Dr Dobbs Journal, 2003
http://www.ddj.com/dept/cpp/184403813;jsessionid=2AAAVOCJBEGSYQSNDLRCKH0 CJUNN2JVN?_requestid=1305388
6. Walter Bright. Backyard Hotrodding C++:, May 23, 2006, is another article which inspired the Cooperative Visitor technique
http://www.artima.com/cppsource/backyard.html
7. E.Gamma et al. Design Patterns ( Addison-Wesley Longman, 1995)
8. Scott Meyers, My Most Important C++ Aha! Moments, Ever September, 2006, discusses among other things, the counter intuitiveness of the Visitor pattern.
http://www.artima.com/cppsource/top_cpp_aha_moments.html
Talk back!
Have an opinion? Readers have already posted 11 comments about this article. Why not add yours?
About the author
-
Artima provides consulting and training services to help you make the most of Scala, reactive
and functional programming, enterprise systems, big data, and testing.
2070 N Broadway Unit 305
Walnut Creek CA 94597
USA
(925) 918-1769 (Phone)