The Default Visitor Idiom

The text of this post was originally in the next post, about our preprocessor framework for C++ Visitors. But I realized that it was a huge distraction from that material, and deserved its own post. To illustrate some points, it builds on the toy Expression hierarchy described here, but using the improved Visitor idiom described here.

Recall that in the Default Visitor idiom, concrete Visitor classes need not implement every enter() function. Whichever classes do not have an enter() will call the enter() of their parent class (the same goes for exit() of course). It's hard to imagine the usefulness in the toy Expression hierarchy of our earlier Visitor posts. To make the example a little more complicated, we'll add some simple Statement classes to our toy visited hierarchy, including an abstract class which is not entirely realistic: MultiStatement, representing a Statement that itself contains one or more other Statements.

Here are the definitions of our new Statement classes (as before, with the disclaimer that it's a toy and not too cleverly designed):

class Statement {
public:
  Statement();
  virtual ~Statement() throw() = 0;
  virtual void accept(Visitor &v) const = 0;
};

class Assignment : public Statement {
public:
  Assignment(Expression *lhs, Expression *rhs);
  virtual ~Assignment() throw();

  const Expression &lhs() const;
  const Expression &rhs() const;
  void accept(Visitor &v) const;

private:
  Expression *_lhs;
  Expression *_rhs;
};

class MultiStatement : public Statement {
public:
  MultiStatement();
  virtual ~MultiStatement() throw();
};

class Block : public MultiStatement {
public:
  Block();
  virtual ~Block() throw();

  const std::vector<Statement *> &stmts() const;
  void accept(Visitor &v) const;

  void addStmt(Statement *stmt);

private:
  std::vector<Statement *> _stmts;
};

class IfElse : public MultiStatement {
public:
  IfElse(Expression *condition, Statement *ifBranch,
         Statement *elseBranch = NULL);
  virtual ~IfElse() throw();

  const Expression &condition() const;
  const Statement &ifBranch() const;
  const Statement *elseBranch() const;
  void accept(Visitor &v) const;

private:
  Expression *_condition;
  Statement *_ifBranch;
  Statement *_elseBranch;
};

The Statement::accept() functions look like this:

void Assignment::accept(Visitor &v) const
{
  if (v.enter(*this)) {
    v.visit(_lhs);
    v.visit(_rhs);
    v.exit(*this);
  }
}

void Block::accept(Visitor &v) const
{
  if (v.enter(*this)) {
    std::vector<Statement *>::const_iterator it;
    for (it = stmts().begin();
         it != stmts().end(); ++it) {
      const Statement *s = *it;
      v.visit(s);
    }
    v.exit(*this);
  }
}

void IfElse::accept(Visitor &v) const
{
  if (v.enter(*this)) {
    v.visit(*_condition);
    v.visit(*_ifBranch);
    v.visit(_elseBranch);
    v.exit(*this);
  }
}

Note that Visitor pushes polymorphism a little farther than C++ inheritance does. As shown in IfElse::accept(), it can visit Statements or Expressions, despite the fact that they do not have a common ancestor! Depending on your project, you may find it convenient to group various independent hierarchies into common Visitor classes. Minor detail: we do need to add Visitor::visit() inline functions for Statement pointers and references, as we did for Expressions.

Here's an example that shows the expressive power of Default Visitor: a class that collects the set of Variables assigned to in a piece of code. For brevity I'll just show the class function definitions, not the class declaration:

FindLhsVars::FindLhsVars()
  : Visitor(), _vars(), _lhs(false)
{
}

bool FindLhsVars::enter(const MultiStatement &)
{
  return true;
}

bool FindLhsVars::enter(const Assignment &a)
{
  _lhs = true;
  visit(a.lhs());
  _lhs = false;
  return false;
}

bool FindLhsVars::enter(const Variable &v)
{
  if (_lhs) {
    _vars.insert(v.name());
  }
  return false;
}

const std::set<std::string> &FindLhsVars::
vars() const
{
  return _vars;
}

It might not seem like much in our toy example, but consider if you had a realistic language hierarchy, and your Visitor was not a Default Visitor. You would have to tediously define an enter() function for every class in the hierarchy, instead of for three classes. Furthermore, unlike the textbook concrete Visitor, FindLhsVars is likely to still work correctly without any changes if you add a class to the hierarchy. I can't say enough good things about Default Visitor -- it takes one of the sourest Visitor lemons and makes it into a very sweet lemonade.

The next post provides some preprocessor tricks that take a lot of the grunt-work out of adding classes to a Visitor, while also bulletproofing your derived concrete Visitors.

Easier-to-Use C++ Visitors

A recent post described the basic structure of the Visitor design pattern for C++. We used the visitFoo()/accept() idiom presented in the GoF book.

Now let's tweak the design a bit, to make things a little prettier, and to make it easier to derive classes from Visitor. After that, I'll need to do another post on preprocessor tricks that generate boilerplate code and set up compile-time errors for common Visitor coding mistakes.

Cosmetic Changes

It's a little awkward to invoke the Visitor code by calling a member function of the visited base class -- obj.accept(v) -- so let's add inline functions to Visitor to provide the more natural idiom of v.visit(obj):

  void visit(const Expression &e) {
    e.accept(*this);
  }
  void visit(const Expression *e) {
    if (e) {
      e->accept(*this);
    }
  }

Note: this means that Visitor.hpp includes Expression.hpp. That is the correct dependency -- Visitors know more about Expressions than vice versa. Thus, Expression.hpp will declare class Visitor instead of including Visitor.hpp.

Don't be tempted to use operator()(const Expression &e) instead of visit(). At first it sounds clever that you will be able to write Print print(stream); print(obj);, but it's bewildering to new readers of your code, and it will even make you scratch your own head when you revisit that code a year into the future. It's much easier to read Print printer(stream); printer.visit(obj);. Trust me, I've been there, trying to figure out what my own program was doing.

Next, I disagree with encoding the type names into the Visitor function names -- it sounds silly to read the declarations aloud: visitOperation(Operation &) -- is there an echo in here? C++ has function overloading -- let's use it, and give all the Visitor members the same short name. We just used up visit(), so we'll have to think of something else. For reasons that will make more sense in a moment, let's use the name enter():

  virtual void enter(const Variable &);
  virtual void enter(const Number &);
  virtual void enter(const Operation &);

A pleasant side effect of this is that there is less room for error when you change the name of a class. If the type name is encoded in the function name, and you forget to change the function name in a concrete visitor, you have just disabled the visitor for that type.

Ease-of-use

Let's fix some usability defects in the basic Visitor implementation. The worst one is that a recursive operation has to know the structure of the visited objects -- see Print::visitOperation() in the earlier post. That is a breakdown of encapsulation, or responsibility, or both.

On the other hand, some concrete Visitors do not want to recurse into subobjects -- they just want to operate on the one visited object. To accomodate both kinds of Visitor, we move the recursiveness into accept() -- makes sense, it's the object's responsibility -- but change the signature of enter() to allow the derived Visitor to choose whether to recurse or not, by returning either true (recurse) or false (don't).

Now the enter() prototypes look like this:

  virtual bool enter(const Variable &);
  virtual bool enter(const Number &);
  virtual bool enter(const Operation &);

The no-op defaults in the base class return false. I went around and around with myself on the question of whether to make recursion the default, but I think the answer is, If your Visitor works harder by recursing, it should require more code to get it done -- overriding the defaults to recurse where needed.

Now that responsibility for recursion has returned to the visited hierarchy, Operation::accept() looks like this:

void Operation::accept(Visitor &v) const
{
  if (v.enter(*this)) {
    std::vector<Expression *>::const_iterator it;
    for (it = operands().begin();
         it != operands().end();
         ++it) {
      const Expression *e = *it;
      v.visit(e);
    }
    v.exit(*this);
  }
}

Handling recursion in the object does the trick most of the time, but the sad thing is, it still doesn't fix the encapsulation issue with our pretty-printer example. To print an infix expression, the Print Visitor has to know the structure of Operator. That's just a fact of life, but if we change the Visitor interface just a tiny bit, we can at least print expressions in prefix and postfix notations without loss of encapsulation. All that's needed is an exit() function to correspond to the enter() function, which will close parentheses for prefix expressions, or print the operator for postfix expressions.

As you can guess, the exit() function returns void, and the default implementation in abstract base Visitor does nothing. If you have sharp eyes, you'll notice that I already added a call to it in Operation::accept() above. It only gets called if the Visitor chose to recurse. Now a postfix pretty-printer is much simpler than the infix version presented in the earlier post:

bool Postfixer::enter(const Variable &v)
{
  _str << v.name() << " ";
  return false;
}

bool Postfixer::enter(const Number &n)
{
  _str << n.value() << " ";
  return false;
}

bool Postfixer::enter(const Operation &o)
{
  return true;
}

void Postfixer::exit(const Operation &o)
{
  _str << o.symbol() << " ";
}

Most importantly, it knows nothing about the structure of Operation.

This post has dragged on long enough, but there is one last ease-of-use improvement I want to make to our Visitor. It must implement the Default Visitor idiom, which makes the double-dispatch polymorphic in both parameters. In simpler terms, if the concrete visitor does not implement, say, enter(Foo &), the default action is not "do nothing", it is enter(ParentOfFoo &). It's hard to visualize the benefit of this in my tiny toy example, but in a realistic hierarchy -- for example, a language hierarchy with abstract Declarations, Statements, and Expressions -- it often saves a lot of coding. Note that in our example, it means we have to add a function to Visitor that hasn't been there before: enter(Expression &).

Next up, some preprocessor magic which generates a lot of the code for these Visitors -- including the Default Visitor fallbacks -- and which also gives you distant early warning of certain common typos.

C++ Visitors: Basic Implementation

In the last post, I described the pros and cons of the Visitor design pattern, and promised some sample C++. This post has a basic implementation of Visitor, to illustrate the concepts. In later posts, we'll build a more powerful and yet more user-friendly Visitor, and use some preprocessor tricks to partially foolproof the use of Visitor.

One place that I've found Visitor useful is in class hierarchies that describe a language -- in my case, usually a hardware description language, but it would apply equally to classes representing a programming or scripting language. In a language project, you often find yourself traversing a parse tree of the input code, performing functions which can't properly be said to be the responsibility of the language classes. Even if you could make a case for adding virtual functions to achieve the task, it makes sense to keep the related functionality together in one file. But you want to dispatch on the node type, so that your code doesn't devolve into a forest of switch statements. This is exactly the place to use Visitor.

Since language parse trees are a common place to apply Visitor, let's start our sample C++ code with a toy class hierarchy for expressions. There are only three concrete classes: Variable, Number, and Operation, all derived from abstract Expression. I kept these classes very simple for brevity's sake, hopefully more care would go into their design in real life:

class Expression {
public:
 Expression();
 virtual ~Expression() throw() = 0;
 virtual void accept(Visitor &v) const = 0;
};

class Number : public Expression {
public:
 explicit Number(int value);
 virtual ~Number() throw();
 int value() const;
 virtual void accept(Visitor &v) const;

private:
 int _value;
};

class Variable : public Expression {
public:
 explicit Variable(const std::string &name);
 virtual ~Variable() throw();
 std::string name() const;
 virtual void accept(Visitor &v) const;

private:
 std::string _name;
};

class Operation : public Expression {
public:
 enum Operator {
   PLUS, MINUS, MAX_OPERATOR
 };
 Operation(const Operator &op,
           Expression *lhsOrOnly,
           Expression *rhs = NULL);
 virtual ~Operation() throw();
 Operator op() const;
 const char *symbol() const;
 const std::vector<Expression *> &operands() const;
 virtual void accept(Visitor &v) const;

private:
 Operator _op;
 std::vector<Expression *> _operands;
};

Notice that Expression has a pure virtual accept() function. We need that in order to bounce into the correct function in Visitor classes -- we'll discuss that in a moment. Now let's see what the abstract base Visitor class looks like. It's just an interface, any real visiting work will be done by concrete visitors derived from this. As I said, we'll be making the interface more sophisticated in the next post, but here's our first crack at it:

class Visitor {
public:
 Visitor();
 virtual ~Visitor();

 virtual void visitVariable(const Variable &);
 virtual void visitNumber(const Number &);
 virtual void visitOperation(const Operation &);
};

Our first implementation of accept() is quite simple, so I'll only show one example:

void Operation::accept(Visitor &v) const
{
 v.visitOperation(*this);
}

C++ Visitors are coded with this accept/visitFoo idiom to work around C++'s lack of multiple dispatch. Calling visitor.visit(*expr) would pick visit()'s signature at compile time based on the static type of expr. So we have to call expr->accept(visitor), which picks the accept() function at run time based on expr's actual type. Inside accept(), *this has the correct static type and can go to the correct member of the Visitor.

Some things to note about this code:

1. It's usually reasonable for accept() to be a const function and visit*() to take const references. But you may need it to be otherwise. Remember, Visitors are like external virtual functions. Will the virtual functions you'll add be const or non-const?
2. On the other hand, you definitely want visit*() to be non-const, and for accept to take a non-const reference. Concrete Visitor classes may need to store some state.
3. Make ~Visitor() virtual but not pure, and don't declare private copy/assign members (see 5.3.1) for Visitor, so that derived Visitors can rely on compiler defaults if they wish.
4. For the same reason, it seems better to define no-op defaults for the visit*() functions instead of making them pure virtual.
5. As written, Operation::accept() does not traverse the Expressions contained in the Operation. That means that concrete Visitors have to do so themselves if they want to. Really such traversal should be Operation's responsibility; we'll add that capability in our next pass.
   

So how do you use this thing? A simple example is class Print : public Visitor, which will print one of our Expressions. The interface is self-explanatory -- a constructor and inherited virtual visit*() functions -- so I'll just give the implementation:

Print::Print(std::ostream &str)
 : Visitor()
 , _str(str)
{
}

void Print::visitVariable(const Variable &v)
{
 _str << v.name();
}

void Print::visitNumber(const Number &n)
{
 _str << n.value();
}

void Print::visitOperation(const Operation &o)
{
 _str << "(";
 std::vector<Expression *>::const_iterator it =
   o.operands().begin();

 while (it != o.operands().end()) {
   const Expression *e = *it;
   ++it;
   if (it == o.operands().end()) {
     // Print unary or binary operator.
     _str << o.symbol();
   }
   e->accept(*this);
 }
 _str << ")";
}

The Print class is suitable for framing in an ostream shift operator:

std::ostream &operator<<(
 std::ostream &str, const Expression &expr)
{
 Print printer(str);
 expr.accept(printer);
 return str;
}

There you go. The basics of C++ Visitors. The toy example doesn't really do justice to how useful they are: Visitors are a big help when you have a big hierarchy to deal with. But the simple design presented here runs into some difficulties when you have a big hierarchy. Coming up, I'll show you some tricks to get the power of Visitors while softening some of the difficulties with using them.

Here is the complete list of posts in this series:

• C++ Visitor Pattern: Motivation
• C++ Visitors: Basic Implementation (this post)
• Easier-to-Use C++ Visitor
• The Default Visitor Idiom
• Handy C++ Visitor Macros

C++ Visitor Pattern: Motivation

The Visitor design pattern is perhaps not the best-loved of the GoF patterns. One indication of its unpopularity is its position as the last pattern in the GoF Design Patterns book. But I have found it useful in several projects, and would like to share some Visitor tricks I've learned along the way.

In C++, Visitor is an abstract base class, with a set of one-argument virtual functions -- one for each class in a forest of hierarchies -- thereby providing "multiple-dispatch" of some piece of functionality. Virtual functions are an example of single-dispatch: based on the type of an object, the correct virtual function is called. Multiple-dispatch means that a function is selected based on more than one type: in this case, the type of the visitor, and the type of the class it visits.

Have you ever been writing some code, and thought: "I wish I could add a virtual function to these classes, without changing the class interfaces"? If so, that is exactly what Visitor allows. Of course, you have to have designed the class to accept a Visitor first, but after that, you have this "external virtual function" capability.

Another way in which Visitor is helpful in big C++ projects, is that it allows you to have good source file hygiene -- as described in our coding standard -- but still keep related functionality in one place. An example is pretty-printing of an Expression hierarchy: to make consistency easier to maintain, you would like all the printing functions to be in a single file, which would violate our source file standards if implemented by virtual functions in the classes.

Sounds good, why is Visitor unpopular? There are a couple of valid complaints about the pattern. First, it can make for difficulties when adding a new class to a visited hierarchy. This is somewhat mitigated by the Default Visitor variant, and we can also use some preprocessor tricks to create a compile- or link-time error for Visitors which must be extended for some or all new classes. It's also worth mentioning that if the Visitor functionality were instead implemented as a pure virtual function, the same amount of work is required (except for tracking down all the Visitors).

Secondly, effective use of Visitors may imply a loss of encapsulation. If a Visitor is to do meaningful work on an object, it may need access to implementation details that -- all other things being equal -- we would prefer to hide inside the class.

Nevertheless, Visitor can be a very useful design pattern. In coming posts I will present some practical C++ examples for getting the most out of it.

Here is the complete list of posts in this series:

• C++ Visitor Pattern: Motivation (this post)
• C++ Visitors: Basic Implementation
• Easier-to-Use C++ Visitor
• The Default Visitor Idiom
• Handy C++ Visitor Macros