Double Dispatch with an Inverted Visitor Pattern

Double dispatch is a technique that determines a course of action based on two factors. If virtual functions and overloading are prime examples of single-dispatch at work, then double dispatch would be using both of these C++ mechanisms in unison. Specifically, if you could call a virtual function through a pointer to a base class, and have the compiler pick not only the proper derived-class implementation of that virtual function, but also pick the proper overloaded instance depending on what you passed in as an argument, that would be a perfect example of double dispatch.

Unfortunately, C++ offers no such inherent capability. I realized this embarassingly late while designing a small for-fun project, and was devastated. Double dispatch seemed like such an elegant way to solve the problem I had before me. I began to think that I was doomed to use an array of function pointers or another less optimal solution.

The good news is that while C++ won't do true double dispatch, it lets you get pretty close. For such a common problem, there are many idioms or patterns that offer solutions. A perfect example of a double dispatch problem is that presented by a windowing system such X-Window (in Unix parlance, "X"). In X, each widget responds differently to each type of event, so the two factors determining course of action are 1) the actual derived class of widget and 2) the type of event. In this article I will use this example to compare possible solutions to the double dispatch problem.

Function Pointers

I'll start with the most obvious solution, a two-dimensional array of function pointers. You can think of this array as a lookup table that specifies which algorithm to use depending on two factors. There might be one column for each widget type, for example, and one row for each event type. It would look something like Table 1.

In this table, all the doXX identifiers represent function pointers. When a certain event occured inside a certain widget, you would simply index into the array based on which event and which widget, then call the function through the pointer stored in that location.

There are many positive aspects to this solution. It is straightforward and easy to impliment. You can initialize and alter the array at run time, meaning you can add new widgets and new events with new libraries, all without recompiling the core engine. Also, as sometimes is the limiting factor, this solution is available even in C.

Unfortunately this solution has no object-oriented qualities. It supports no association between the concepts of widget, event, and event-handler functions. These functions might be dispersed anywhere in the code, and many functions can exist for each possibility if the table is manipulated during run time. Maintaining this collection of functions could be a nightmare.

Keep this solution in the back of your mind. This is a baseline against which all others should be compared. The array might be indexable by identifiers instead of simple integers, such as a hash table would allow, but the core concept is that we index into the table based on the two factors involved in the problem. At this location should be a function pointer containing the code that should be executed for a ScrollBar widget and a MouseClick event, or whichever combination happens to have occured.

The Visitor Pattern

A celebrated solution to the problem of double dispatch is the Visitor pattern, introduced by Gamma [1]. By applying Visitor to this windowing example, one of the factors becomes a "Visitor" and the other becomes an "Element" of the object structure. Elements correspond to the factor that has a true physical representation in an object (e.g., a windowing element), while the Visitor is simply a wrapper around the event handling algorithm(s).

Quite clearly, the widget classes will become Elements and events will become the Visitors. To use the Visitor pattern, both factors should have a base class, most likely virtual. The class whose objects are Visitors is endowed with separate methods for visiting each possible derived Element (widget) class. The classes whose objects are Elements have a single accept function for accepting each representation of Visitor. The resulting class structure appears as in Listing 1.

Using this pattern, you call the proper piece of code whenever any derived class of Widget is visited by any derived class of Event. In many ways this is an ideal solution.

When using the Visitor pattern, you must keep certain things in mind. First, your Visitor class tree can grow freely. You can add new Event classes and override only the visitation methods that the default Event class implementation doesn't satisfy. Adding events is unlikely with this example, though. Events are by nature very unique, and are unlikely to inherit any behavior from their base classes. In fact, most events will derive directly from the base Event class, which would probably have no default behavior at all, being purely virtual.

By contrast, your Element class tree must remain fairly static, for adding a new widget would mean installing new visitation methods in many of the already existing event classes. For example, if you added an ImageButtonWidget, you would have to add visitImageButtonWidget(ImageButtonWidget&) functions in all existing event classes.

It is easier to extend the array in the Visitor (Event) dimension than in the Element (Widget) dimension. But in this example the former's flexibility doesn't gain us much.

Another consequence of using the Visitor pattern is that you "store" the algorithm in the Visitor. This may not seem at first to be a problem, but I have never quite been able to reconcile this policy with the ideology of object-oriented (OO) design. Obviously, there are two choices on where to store the actual algorithm, and it may not seem to matter whether the algorithm resides in the Element or the Visitor. But the Element is often the better choice, as in the example above, in which the Element tree was the widget class tree from the windowing library. It would be best if the widget itself contained the algorithm for how it reacts to various events. It makes more sense from an OO point of view, and provides the algorithm access to the internals of the Element, which it will probably need.

A final and mostly aesthetic consequence of using Visitor is that many different visitation methods are less pleasing to a C++ programmer than overloaded methods. Unfortunately, if we were to try to change the pattern to use overloaded methods in the Visitor it would cease to function properly, because C++ does not support resolving virtual functions and overloaded methods at the same time.

In respect to a classic and well-designed pattern, Visitor solves the problem of double dispatch well. Visitor enables add-on libraries of new events to be added without recompiling the core engine. Notwithstanding some unsettling gut feelings, the Visitor pattern could very well be the best solution for double dispatch on many occasions, even if it seems not quite right for this article's example. Note that as presented Visitor does not enable adding new widget classes with an add-on library. You might find yourself wishing you could trade one widget for another.

Inverting the Visitor Pattern

In this section, I invert the Visitor pattern to arrive at a better solution. Inverting the Visitor pattern means moving the event-handling algorithms from the Visitor class to the Element classes:

class Event // the Visitor
{
public:
    virtual visit(Widget& w) { w.handleEvent(*this); }
}
class Widget // Element
{
public:
    virtual handleEvent(Event&)               
    { /* default algorithm */ }
    virtual handleDerivedEvent(DerivedEvent&)
    { /* default algorithm */ }
}

Now instead of each Widget accepting the Event in turn, the Event visits each Widget in turn. While state information related to the Event can still be hidden in the Event itself, behavior is now coupled with the concrete Widget object instead of with the external Event trigger.

It's still desirable to use overloaded functions in the Widget class. But wait, I said this wouldn't work. It won't, but the following snippet will get us closer to an answer:

class Event
{
public:
    virtual visit(Widget& w) { w.handleEvent(*this); }
}

class DerivedEvent : public Event
{
public:
    virtual visit(Widget& w) { w.handleEvent(*this); }
}

class Widget
{
public:
    virtual handleEvent(Event&) { /* default algorithm */ }
}

class DerivedWidget : public Widget
{
public:
    virtual handleEvent(Event&) { /* This will get called */ }
    virtual handleEvent(DerivedEvent&)
    { /* This won't get called */ }
}

With these changes I have reached what I would call an almost perfect solution, with the possible exception that it doesn't seem to work. The above code will compile, but it will not work the way we'd like. All calls to visit(Widget&) passing in any DerivedWidget will resolve to the handleEvent(Event&) method, not the overloaded handleEvent(DerivedEvent&). So close but yet so far.

Or maybe not so far. The problem here is that the compiler has to resolve virtual functions and overloading at the same time. What if I gave it a break and let it do one at a time? If the base class Widget is changed to:

class Widget
{
public:
    virtual handleEvent(Event&) { /* default algorithm */ }
    virtual handleEvent(DerivedEvent&)
    { /* default algorithm */ }
}

class DerivedWidget : public Widget
{
public:
    virtual handleEvent(Event&) { /* This will get called */ }
    virtual handleEvent(DerivedEvent&) { /* This will too! */ }
}

now it works! I've allowed the compiler to handle the overloaded functions first, and then deal with the separate virtuality of the functions.

You may notice, after some testing, one thing still lacking; If a DerivedWidget doesn't override a particular handleEvent function, the default is to call the base class Widget version, since the compiler resolves the virtual nature of the function last. So if you pass a DerivedEvent to a DerivedWidget, and you haven't overridden handleEvent(DerivedEvent&), the compiler will not call any DerivedWidget::handleEvent(DerivedEvent&) method (since it does not exist), nor does it call an overridden DerivedWidget::handleEvent(Event&). Rather, the compiler calls Widget::handleEvent(DerivedEvent&). But, by using some clever defaults, such as:

class Widget
{
public:
    virtual handleEvent(Event&)
       { /* default event handling */ }
    virtual handleEvent(DerivedEvent& e)
    { handleEvent((Event&)e); }
}

class DerivedWidget : public Widget
{
public:
    virtual handleEvent(Event&)
       { /* This will get called */ }
 // virtual handleEvent(DerivedEvent&)
 // { /* Commented out */ }
}

the compiler will forward the call to Widget::handleEvent(DerivedEvent&) to handleEvent(Event&), which then resolves to the overridden DerivedWidget::handleEvent(Event&) instead.

Evaluating the Inverted Visitor

If you divide the above solution into two major steps, that of 1) inverting the Visitor pattern, and 2) resolving the virtual and overloaded function collision, then there are really two separate solutions offered here for double dispatch. If you stop after the first step, you can apply the Visitor pattern in its inverted form to a problem such as this article's example and achieve all the benefits of a cleaner design. You also get the more logical benefit of being able to add Widgets through add-on libraries. This is in and of itself a useful alternative.

Making both changes, however, leads to a solution that is very appealing at least in its ability to give you the advantages of virtual functions and function overloading within the same context. In your DerivedWidgets you override only the event handlers for those events your new widget is interested in. However, if you neglect to override a handler in a derived class, and one of its base classes does override the handler, you must take care in how you call the functions in order to get the behavior you want.

Consider the following:

class Widget
{
public:
    virtual handleEvent(Event&)
       { /* default event handling */ }
    virtual handleEvent(DerivedEvent& e)
    { handleEvent((Event&)e); }
}

class DerivedWidget : public Widget
{
public:
    virtual handleEvent(Event&)
       { /* overridden */ }
    virtual handleEvent(DerivedEvent&)
    { /* This gets called */ }
}

class NewWidget : public DerivedWidget
{
public:
    virtual handleEvent(Event&)
       { /* Instead of this */ }
 // virtual handleEvent(DerivedEvent&)
 // { /* commented out */ }
}

Suppose you have a base-class pointer (or reference) to a NewWidget object, and you invoke handleEvent via that pointer (or reference), passing a DerivedEvent& as an argument. Then the compiler will call DerivedWidget::handleEvent(DerivedEvent&). On the other hand, if you call handleEvent via a direct reference to your NewWidget object, you've elimated the need for the compiler to resolve the virtual function call, so it goes on to resolve overloading and calls NewWidget::handleEvent(Event&). So understanding the behavior becomes more complex.

The default behavior — that is, the redirecting of event handling to a <MostDerivedClass>::handleEvent(Event&) through the clever implementation of Widget::handleEvent(DerivedEvent&) — is replaced when any of <MostDerivedClass>'s base classes has overridden that specific handleEvent version. Yet this behavior becomes the default again if you use a direct reference to the <MostDerivedClass>. It is an unfortunate limitation of this solution. This solution resolves the overloaded functions first, and thus they have less priority than the virtual nature of the functions, unless this nature is reversed by using a direct reference. To keep the behavior more standardized you should definitely avoid using direct references to DerivedWidget classes, and you could omit the clever redirection in the base class altogether. Even so, I think this technique is quite useful when used appropriately.

Another impact of this new solution is that adding a new Event requires changing the base class Widget and recompiling the entire Widget library. Adding a new Widget is straightforward and can still be done with add-on libraries. Likewise, this technique preserves the other benefit from inverting the Visitor pattern, which places the algorithm inside the Widget's handleEvent functions.

For reference, Listing 2 shows a test run and explanation of the inverted Visitor pattern and overloading implementation.

Summary

C++ does not allow true double dispatch, an example being it cannot resolve virtual function calls and overloading at the same time. However, there are a variety of techniques you can use to simulate double dispatch in C++. A table of function pointers, while versatile, does not support object-oriented programming and can be hard to maintain. The Visitor pattern is an effective implementation of double dispatch that enables Events to be added without recompilation. But Visitor is not always optimum for GUI applications because it stores the event-handling algorithms in Event classes, and these classes must be modified each time an Element is added. In GUI applications especially, Elements are more likely to be added than Events. Inverting the Visitor pattern yields an implementation more suitable to GUI applications. This technique can be enhanced by adding overloading; the trick is to provide a way for the compiler to resolve overloading and virtual function calls separately. A disadvantage to adding overloading in this manner is increased complexity of function call behavior.

Reference

David Gould is a Software Engineer at Physitron, Inc. where he develops distributed scientific visualization tools using CORBA, Java, and C++. He can be reached at http://www.physitron.com/~gould/, or by email at [email protected].