10.5 Back to the "Cyclic" Visitor

The generic Acyclic Visitor implementation defined in the previous section should be satisfactory in most situations. However, if you are developing a speed-hungry application, that dynamic cast in Accept might render you pensive and your speed measurements could make you downright depressed. Here's why. If you use dynamic_cast against some object, the runtime support has quite a few things to do. The RTTI code must figure out whether the conversion to the target type is legal and, if it is, must compute a pointer to that target type.

Let's detail a bit how a compiler writer can achieve this. One reasonable solution is to assign a unique integral identifier to each type in the program. The integral identifier also comes in handy when it comes to exception handling, so it's quite a wise integrating solution. Then in each class's virtual table, the compiler puts (a pointer to) a table of identifiers of all its subtypes. Together with these identifiers, the compiler has to store the offsets of the relative positions of the subobjects within the big object. This would be enough information to perform a dynamic cast correctly. When a dynamic_cast <T2*>(p1) occurs and p1 is of type "pointer to T1," the runtime support code walks through the table of types for p1. If a match with T2 is found, the runtime support code will perform the needed pointer arithmetic and pass back the result. Otherwise, the result is a null pointer. Details—such as multiple inheritance—render the dynamic cast code even more complicated and slower.

The solution just outlined has O(n) complexity with respect to the number of base classes of a class. In other words, the time taken by a dynamic cast increases linearly as you use deeper and broader inheritance hierarchies.

Another solution is to use hash tables, thus offering increased speed at the expense of memory use. Yet another solution might use a big matrix for the whole application, thus making the dynamic cast take constant time, but at a significant cost in size, especially for programs with many classes. (A possible idea would be to compress that matrix; all this reveals the wonderful life of C++ compiler writers.)

The bottom line is that dynamic_cast does have a cost, which is unpredictable and can become unacceptable for some particular needs of an application. This means we should extend our Visitor implementation to accommodate the GoF "cyclic" Visitor, which is faster because it doesn't use dynamic_cast, but is harder to maintain.

Recall from the opening of this chapter how the GoF Visitor works. The following list summarizes the main differences between the GoF Visitor and the Acyclic Visitor as implemented by Loki.

• The BaseVisitor class is no longer a strawman; it defines one Visit pure virtual member function for each visited type (assuming we decide to rely on overloading).

• The AcceptImpl function must change. Ideally, the DEFINE_VISITABLE() macro remains unchanged.

Now, it all boils down to this: We have a collection of types we want to visit. Say they are DocElement, Paragraph, and RasterBitmap. How can we express and manipulate a collection of types? The question is a transparent hint to refer to Chapter 3, which describes typelists in detail and defines a complete typelist facility.

Typelists are exactly what we need here. We want to pass a typelist to a CyclicVisitor template as a template argument, thus saying, "I want this CyclicVisitor to be able to visit the following types." It would be elegant to say

// Forward declarations needed by the typelist below


class DocElement;


class Paragraph;


class RasterBitmap;





// Visits DocElement, Paragraph, and RasterBitmap


typedef CyclicVisitor


<


   void, // return type


   TYPELIST_3(DocElement, Paragraph, RasterBitmap)


>


MyVisitor;

CyclicVisitor depends by name on DocElement, Paragraph, and RasterBitmap.

Let's see which additions we need to make to the current codebase. We use the same procedure we used in Chapter 9 for defining a generic Abstract Factory implementation:

// Consult Visitor.h for the definition of Private::VisitorBinder<R>


template <typename R, class TList>


class CyclicVisitor : public GenScatterHierarchy<TList,


   Private::VisitorBinder<R>::Result>


{


   typedef R ReturnType;


   template <class Visited>


   ReturnType Visit(Visited& host)


   {


      Visitor<Visited>& subObj = *this;


      return subObj.Visit(host);


   }


};

Remarkably, CyclicVisitor uses Visitor as a building block. Refer to Chapter 3 for the technique and to Chapter 9 for a similar example. Essentially, CyclicVisitor inherits a Visitor<T> for each type T in the typelist TList.

The net effect is that if you pass CyclicVisitor a typelist, it ends up inheriting from Visitor instantiated with every type in that typelist, thus declaring one Visit pure virtual function per type. In other words, it's functionally equivalent to the base Visitor as prescribed by the GoF Visitor pattern.

After you specify your CyclicVisitor of choice through a typedef, say MyVisitor, all you have to do is use the DEFINE_CYCLIC_VISITABLE(MyVisitor) macro in your visitable classes appropriately. For example:

typedef CyclicVisitor


<


   void, // return type


   TYPELIST_3(DocElement, Paragraph, RasterBitmap)


>


MyVisitor;





class DocElement


{


public:


   virtual void Visit(MyVisitor&) = 0;


};





class Paragraph : public DocElement


{


public:


   DEFINE_CYCLIC_VISITABLE(MyVisitor);


};

That's it! Just as in a handmade implementation of the GoF Visitor, you still have to contribute some discipline. The difference now is that the number of things you have to remember and implement yourself is much smaller. To make a hierarchy visitable with our GoF Visitor implementation, do the following:

• Forward declare all the classes in the hierarchy.

• Write a typedef for CyclicVisitor, instantiated with the return type and with the list of the types you want to visit. (Let's call it MyVisitor.)

• Define a virtual pure function Visit for your base class.

• Add DEFINE_CYCLIC_VISITABLE(MyVisitor) to each class of your hierarchy, or implement Accept by hand for classes that you want to sport a different behavior.

• Have each of your concrete visitors inherit from MyVisitor.

• Update the MyVisitor template instantiation (the typedef) whenever you add a new class to the visitable hierarchy, then—sigh—recompile.

Compared with a handmade GoF Visitor implementation, the generic approach is cleaner. The number of points of maintenance is reduced to your MyVisitor type definition.

As a practical piece of advice for designing with Visitor, it's best to start with the Acyclic Visitor, which is easier to maintain, and switch to the GoF Visitor only if you really must optimize. The nice part is that the generic componentry makes it very easy to experiment—you need change only one declaration. There's no code to hack into. The details of implementing Visitor are in the library. You need adjust only the declarative link between the client and library in order to achieve two different implementations of Visitor.