|
|
|
|
Advertisement
|
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:
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 is a template-based technique for finding reasonable solutions to the above- mentioned problems. It allows:
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.
The technique uses following approach:
Table [ Tag ] = &Visit( Class ), where:
Table is the virtual tableTag is a tag valueVisit is the visit handler (a thunk: details follow)Class is the class that has integer value "tag"The remainder of this article takes an in-depth look at an implementation.
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
and GetTag 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.
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()
};
VTableThe 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.
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.
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
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 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.
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.
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.
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.
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 );
}
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).
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.
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.
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 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.
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.
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.
Have an opinion about the Cooperative Visitor? Discuss this article in the Articles Forum topic, Cooperative Visitor: A Template Technique for Visitor Creation.
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
Anand Shankar Krishnamoorthi is an exploring C++ developer with 4 years of professional experience. His interests include C++ design, compilers, programming languages, performance analysis and optimization.
|
Sponsored Links
|