Friday, May 1, 2009

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.

No comments: