Double Dispatch: The Visitor Pattern

I’ll be frank, I don’t like the Visitor Pattern.  It’s a hack.  It’s just a way of getting around a deficiency in the language.  Basically, extending the functionality of objects is what inheritance is for.  The whole reason the visitor pattern exists is to deal with the times that this model falls down.  Proxies and the decorator pattern could also be considered object extension mechanisms, but I’ve already dealt with them.  Another reason I don’t like it is that it relies fairly heavily on abusing function overloading, and it’s extremely brittle with regards to changes in your inheritance structure.

A note: it is often assumed that the visitor pattern has something to do with iteration and trees.  Whilst it can be used in such scenarios, it’s not really the point and often there’s a simpler solution.  So, what I’m going to talk about is double dispatch.

There’s basically two limitations to virtual methods:

• You can’t add them to an existing class.
• Sometimes you don’t want to add them to an existing class.  This is usually because doing so would violate the single responsibility principle.

The visitor pattern is a way around this limitation, but it’s not elegant.  What’s worse, it requires you to be able to modify the target classes, so it doesn’t even fully address the first limitation. Whilst it can be useful, it’s always worth examining exactly why you need a visitor.  It can be a code smell.

Implementing the Visitor Pattern

Let’s say that we wish to write a routine that processes messages in a trading system.  We’ll say for the sake of argument there are order messages, execution messages and allocation messages.  Now, the “object orientated” way of doing this would be to add processing method directly to the class, but that isn’t possible or desirable in C#.

So, we define a “visitor” interface

interface IMessageVisitor {
    void Visit(OrderMessage message);
    void Visit(AllocationMessage message);
    void Visit(ExecutionMessage message);
}

and we add a method to the IMessage interface.

void Visit(IMessageVisitor visitor); 

It’s probably worth defining an interface IVisitable<TVisitor> for this purpose. 

internal interfaceIVisitable<TVisitor> {
   void Visit(TVisitor visitor);
}

We now implement the following method in every one of our target classes:

void override Visit(IMessageVisitor visitor) { visitor.Visit(this); }

Note that you can’t implement this code the once in a base class, because it won’t work.  What this code does is to abuse function overloading.  If the message is an allocation message, it will call the “Visit Allocation Message” routine.  If you’ve got an “Automated Allocation Message” that inherits from allocation message, it’ll call the same routine.  The same semantics, in other words, as a virtual function.

If, on the other hand, you wanted to specialize the “Automated Allocation Message”, you’d need to change the IMessageVisitor.  It’s not a perfect solution.

Alternatives to the Visitor Pattern

It’s worth noting that many modern “typeless” programming languages allow you to add methods directly to classes at runtime.  This provides a strong alternative to the visitor pattern.  It doesn’t violate the single responsibility principle as long as you segregate the scope of the routines.  If you can’t modify the target classes, a (carefully written) big ugly cascading if statement can be used instead of implementing IVisitable.  Finally, you could use a chain of responsibility instead, which is effectively a well-structured cascading if statement, but a lot more flexible. 

The catch is: any of the above solutions don’t get you the magic static type checking of the visitor pattern.

In general terms, if you’ve only got a small number of implementations of a given IVisitor class, you should probably just consider adding virtual functions directly to the calling classes.  If, on the other hand, you have fifty, the visitor pattern may be pretty much the only way to keep your problem space manageable.

Tree Walking

The classic gang of four example of tree walking is actually a mix of the visitor pattern and the composite pattern.  With this, the parent nodes visit method automatically call visit on their children.  Seriously, just don’t do this unless you absolutely have to.  You’ve mixed the dispatch behaviour with iteration behaviour, there’s no way for the caller to figure out the structure of the tree and you can’t vary between depth and breadth first iteration.  Here’s some code that’s often more useful than doing the composite and visitor trick:

interface INode<TNode> {
    IEnumerable<TNode> Children { get; }
}
IEnumerable<TNode> DepthFirst<TNode>(TNode root) 
where TNode: INode<TNode>
{
    return new[] { root }.Union(root.Children.SelectMany(c => DepthFirst(c)));
}
IEnumerable<TNode> BreadthFirst<TNode>(TNode root)
where TNode : INode<TNode>
{
    return BreadthFirst<TNode>(new[] { root });
}
IEnumerable<TNode> BreadthFirst<TNode>(IEnumerable<TNode> children)
where TNode : INode<TNode>
{
    return children.Union(children.SelectMany(c => BreadthFirst(c)));
} 

UPDATE:  This article used to contain text about the composite pattern, which I’ve removed.  You can find my revised thoughts about composite pattern here, or the original text with editorial here.