10.3 An Implementation Refinement: The Acyclic Visitor

So you have decided to use Visitor. Let's get pragmatic. In a real-life project, how should you organize the code?

A dependency analysis of the earlier example reveals the following:

• For the DocElement class definition to compile, it must know about the DocElementVisitor because DocElementVisitor appears in the DocElement::Accept member function signature. A forward declaration would suffice.

• For the DocElementVisitor class definition to compile, it has to know about all the concrete classes (at least) in the DocElement hierarchy because the class names appear in DocElementVisitor's VisitXxx member functions.

This type of dependency is called a cyclic dependency. Cyclic dependencies are well-known maintenance bottlenecks. DocElement needs DocElementVisitor, and Doc ElementVisitor needs all of DocElement's hierarchy. Consequently, DocElement depends on its own subclasses. Actually, this is a cyclic name dependency; that is, the class definitions depend only on their names in order to compile. Thus, a sensible division of classes into files would look like this:

// File DocElementVisitor.h


class DocElement;


class Paragraph;


class RasterBitmap;


... forward declarations for all DocElement derivatives ...





class DocElementVisitor


{


   virtual void VisitParagraph(Paragraph&) = 0;


   virtual void VisitRasterBitmap(RasterBitmap&) = 0;


   ... other similar functions ...


};


// File DocElement.h


class DocElementVisitor;





class DocElement


{


public:


   virtual void Accept(DocElementVisitor&) = 0;


   ...


};

Furthermore, each one-line Accept implementation needs the definition of DocElement Visitor, and each concrete visitor has to include its classes of interest. All this leads to an intricate map of dependencies.

What becomes really cumbersome is adding new derivatives to DocElements. But hold on, we're not supposed to add any new elements to the DocElement hierarchy. Visitor applies best to stable hierarchies to which you want to add operations without touching them. Recall, however, that Visitor can do this for you at the expense of making it hard to add derivatives to the visited hierarchy (in our example, the hierarchy rooted in DocElement).

But life is change. Let's face it, here on Earth, there's no such thing as a stable hierarchy. Occasionally you will have to add a new class to the DocElement hierarchy. For the previous example, here's what you must do to add a class VectorGraphic derived from DocElement:

• Go to DocElementVisitor.h and add a new forward declaration for VectorGraphic.

• Add a new pure overload to DocElementVisitor, as follows:

  
  
  class DocElementVisitor
  
  
  {
  
  
     ... as before ...
  
  
     virtual void VisitVectorGraphic(VectorGraphic&) = 0;
  
  
  };
  
  
  

• Go to every concrete visitor and implement VisitVectorGraphic. Depending on the task, the function can be a do-nothing function. Alternatively, you can define DocElementVisitor::VisitVectorGraphic as a do-nothing, as opposed to a pure, function, but in this case, the compiler won't remind you if you don't implement it in concrete visitors.

• Implement Accept in the VectorGraphic class. Don't forget to do this. If you derive directly from DocElement and forget to implement Accept, there's no problem—you'll get a compile-time error. But if you derive from another class, such as Graphic, and if that class defines Accept, the compiler won't utter a word about your forgetting to make VectorGraphic visitable. This bug won't be detected until runtime, when you notice that your Visitor framework refuses to call any implementation of VisitVectorGraphic. Quite a nasty bug to deal with.

Corollary: All of the DocElement and DocElementVisitor hierarchies will be recompiled, and you need to add a considerable amount of mechanical code, all simply to keep things working. Depending on the size of the project, this requirementcould range from being annoying to being totally unacceptable.

Robert Martin (1996) invented an interesting variation of the Visitor pattern that leverages dynamic_cast to eliminate cyclicity. His approach defines a strawman base class, BaseVisitor, for the visitor hierarchy. BaseVisitor is only a carrier of type information. It doesn't have any content; therefore, it is totally decoupled. The visited hierarchy's Accept member function accepts a reference to BaseVisitor and applies dynamic_cast against it to detect a matching visitor. If Accept finds a match, it jumps from the visited hierarchy to the visitor hierarchy.

This might sound weird at first, but it's very simple. Let's see how we can implement an acyclic visitor for our DocElement/DocElementVisitor design. First, we define a visitor archetypal base class, the strawman.

class DocElementVisitor


{


public:


   virtual void ~DocElementVisitor() {}


};

The do-nothing virtual destructor does two important things. First, it gives DocElementVisitor RTTI (runtime type information) capabilities. (Only types with at least one virtual function support dynamic_cast.) Second, the virtual destructor ensures correct polymorphic destruction of DocElementVisitor objects. A polymorphic hierarchy without virtual destructors engenders undefined behavior if a derived object is destroyed via a pointer to a base object. Thus, we nicely solve two dangerous problems with one line of code.

The DocElement class definition remains the same. Of interest to us is its definition of the Accept(DocElementVisitor&) pure virtual function.

Then, for each derived class in the visited hierarchy (the one rooted in DocElement), we define a small visiting class that has only one function, VisitXxxx. For instance, for Paragraph, we define the following:

class ParagraphVisitor


{


public:


   virtual void VisitParagraph(Paragraph&) = 0;


};

The Paragraph::Accept implementation looks like this:

void Paragraph::Accept(Visitor& v)


{


   if (ParagraphVisitor* p =


      dynamic_cast<ParagraphVisitor*>(&v))


   {


      p->VisitParagraph(*this);


   }


   else


   {


      optionally call a catch-all function


   }


}

The prima donna here is dynamic_cast, which enables the runtime system to figure out whether v is actually a subobject of an object that also implements ParagraphVisitor and, if so, to obtain a pointer to that ParagraphVisitor.

RasterBitmap and the other DocElement-derived classes define similar implementations of Accept. Finally, a concrete visitor derives from DocElementVisitor and the archetypal visitors of all classes that are of interest to it. For instance:

class DocStats :


   public DocElementVisitor,  // Required


   public ParagraphVisitor,   // Wants to visit Paragraph objects


   public RasterBitmapVisitor // Wants to visit RasterBitmap


                              // objects


{


public:


   void VisitParagraph(Paragraph& par)


   {


      chars_ += par.NumChars();


      words_ += par.NumWords();


   }


   void VisitRasterBitmap(RasterBitmap&)


   {


      ++images_;


   }


};

The resulting class structure is presented in Figure 10.2. The horizontal dotted lines depict dependency layers, and the vertical ones depict the insulation between hierarchies. Notice how dynamic_cast provides the means to jump magically from one hierarchy to the other by leveraging the strawman DocElementVisitor class.

The described structure encompasses a lot of details and interactions. However, the basic structure is simple. Let's recap everything by analyzing an event flow. We assume that we have a pointer, pDocElem, to a DocElement whose dynamic ("real") type is Paragraph. Then we do the following:

DocStats stats;


pDocElem->Accept(stats);

The following events happen, in order.

Let's examine the new dependency chart.

• DocElement's class definition depends on DocElementVisitor by name. Dependency by name means that a forward declaration of DocElementVisitor is enough.

• ParagraphVisitor—and, in general, all XxxVisitor base classes—depends by name on the classes that it visits.

• The Paragraph::Accept implementation fully depends on ParagraphVisitor. Full dependency means that the full class definition is needed in order to compile the code.

• Any concrete visitor's class definition fully depends on DocElementVisitor and on all of the base visitors XxxVisitor that it wants to visit.

The Acyclic Visitor pattern eliminates cyclic dependencies but in exchange leaves you with even more work to do. Basically, from now on, you must maintain two parallel sets of classes: the visited hierarchy rooted in DocElement; and the visitor classes XxxVisitor, one for each concrete visited class. Maintaining two parallel class hierarchies is not desirable because it requires much discipline and attention.

A note on efficiency in comparing the "plain" Visitor with the Acyclic Visitor: In the latter, there's one extra dynamic cast in the path. Its cost in time might be constant or might increase logarithmically or linearly with the number of polymorphic classes in the program, depending on your compiler vendor. The cost might be important if efficiency is an issue. So in some cases you might be forced to use the "plain" Visitor and to maintain cyclic dependencies.

Because of this overall grim picture, Visitor is, unsurprisingly, a controversial pattern. Even Ralph Gamma of GoF fame says that on his list of bottom-ten patterns, Visitor is at the very bottom (Vlissides 1999).

Visitor is clumsy, rigid, hard to extend, and hard to maintain. However, with perseverance and diligence we can put together a Visitor library implementation that is win-win: easy to use, extend, and maintain. The next sections show how.