协作式Visitor: 基于模板来创建Visitor的技巧

大致看完这篇文章，感觉非常好，人家才四年C++，已经达到此水平，佩服。原文位于：
http://www.artima.com/cppsource/cooperative_visitor.html

This article presents a flexible and efficient variation of the Visitor design pattern in C++ that accommodates arbitrary argument and return types.

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:

1. Create visitors by hand or
2. 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:

1. Generate a unique tag ( integer value) for every visitable class in a hierarchy
2. Provide a way for every visitable object to return its tag
3. Build a "virtual function table" where:
   
   • Table [ Tag ] = &Visit( Class ), where:
     
     • Where Table is the virtual table
     • Tag is a tag value
     • Visit is the visit handler (a thunk: details follow)
     • Class is the class that has integer value "tag"
4. 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 and GetTag<const shape=""></const> 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.

Talk back!

Have an opinion about the Cooperative Visitor? Discuss this article in the Articles Forum topic, Cooperative Visitor: A Template Technique for Visitor Creation.

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

About the author

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.

<script type="text/javascript"><!-- google_ad_client = "ca-pub-7104628658411459"; /* wide1 */ google_ad_slot = "8564482570"; google_ad_width = 728; google_ad_height = 90; //--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>