Double Dispatch Revisited

Instead, he suggests the clever technique of initially using typeid(type).name() on each argument type to obtain a distinct string, and building a map<pair<string, string>, function_ptr> to register each processing function. Then, given a pair of actual arguments, Meyers uses typeid(reference).name() on each argument to get the strings with which to perform a map lookup.

He points out that there is a drawback to this technique—it doesn't deal with inheritance. In his example, there's a registered processing function, shipAsteroid(), that expects actual parameters (SpaceShip, Asteroid). If you derive CommercialShip and MilitaryShip from SpaceShip, you might expect that when a MilitaryShip collides with an Asteroid, you'd call shipAsteroid() as before. Alas, it doesn't work that way. "Even though a MilitaryShip can be treated like a SpaceShip," notes Meyers, "lookup() has no way of knowing that. Furthermore, there is no easy way of telling it."

In Modern C++ Design: Generic Programming and Design Patterns Applied (Addison-Wesley, 2001), Andrei Alexandrescu also discusses multiple dispatch. "I am convinced," he writes, "there is a solution to the inheritance problem. But, alas, writers of books have deadlines, too."

I am indebted to both writers for most of what follows. I have found that with a somewhat different container, you can get reasonably good results.

Consider a small class (Listing One) to represent an arbitrary pair of GameObject subclass types. You can define a subclass to represent the types (SpaceShip, Asteroid) as in Listing Two, where you take advantage of dynamic_cast to do the type matching. It's important to work with pointers because dynamic_cast produces a zero pointer if the actual object in question cannot be downcast to the specified pointer type.

When you generalize that subclass (as in Listing Three), you just construct a container of such objects and search that. The important point is that, even for a subclass object myMilitaryShip, dynamic_cast<const SpaceShip*> produces a nonzero pointer. The catch is that this test is ambiguous. You still have the general-purpose processing function shipAsteroid(SpaceShip&, Asteroid&)—but suppose that MilitaryShips get special treatment (maybe they're more heavily armored) and need a special routine such as militaryShipAsteroid(MilitaryShip&, Asteroid&). Every MilitaryShip object actually matches both routines, so this registry can't rely on unique lookup.

The problem resembles catching an exception of a particular type. Suppose you have an Error base class with a subclass ErrorRuntime, which in turn has a subclass ErrorBounds. You could write incorrect code like that in Listing Four where, if dubiousRoutine() throws an ErrorBounds exception, it will not be caught by the ErrorBounds clause. Every ErrorBounds object is an ErrorRuntime as well, so that exception will be caught by the ErrorRuntime clause instead. To distinguish between ErrorBounds and all other ErrorRuntime exceptions, the classes in question must be written like Listing Five.

In the same spirit, you can construct a sequence container (a list) of EntryBase objects and perform a linear search. Invoke the first Entry for which matches() returns true—thus, the burden is on you to populate the list in a reasonable order.

Naturally, you can't just construct a list<EntryBase>: That would slice every Entry subclass object, which is hardly what you want. To be properly polymorphic, your list must store pointers to EntryBase. But that raises uncomfortable questions about the life span of the EntryBase objects: When the list is destroyed, what happens to all of those objects?

This is what smart pointers are all about. std::auto_ptr can't be used in STL containers. But the Boost Library (http://www .boost.org/) provides a couple of varieties of smart pointers, and boost::shared_ptr seems ideal for the job. For convenience, I'll typedef boost::shared_ptr<EntryBase> as EntryPtr.

The container, then, is a list<EntryPtr>; see Listing Six. How will you actually search it? Well, you'll be called with two specific GameObject (subclass) references, as in Listing Seven.

boost::bind() is so cool that it deserves more discussion than I can give it here. For our purposes, the boost::bind() syntax in Listing Seven essentially says: For each item in mDispatch, call matches(param1, param2), and stop when it returns true. boost::bind() automatically handles the fact that the items in mDispatch are smart pointers, as well as the fact that matches() is actually a member function of the referenced class.

Once we've found the right EntryPtr, calling it isn't hard. You must bind some sort of function or function object (called a "functor"); see Listing Eight. Any class with an operator() method accepting two GameObject& parameters works.

Since each Entry subclass already knows its Functor's parameter types, you can also equip it with a virtual method to perform the appropriate downcasting, as in Listing Nine. Therefore, you can provide a function like Listing Ten. This lets you code each Functor using the specific GameObject subclasses that it expects to process. For example, you can write shipAsteroid(SpaceShip&, Asteroid&) rather than shipAsteroid(GameObject&, GameObject&) with internal downcasts.

All that remains is to populate the DispatchTable. You want to provide a function to append new Entry objects to the existing container. Naturally, since this function must instantiate a template class, it must be a template function.

The template function must accept two "types" as well as a Functor. While it should be possible to provide those types as explicit template parameters (for example, add<SpaceShip, Asteroid>(shipAsteroid)), the Microsoft Visual C++ 6 compiler (to name one example) doesn't support that construct.

But you can borrow again from Alexandrescu and wrap these types as lightweight objects:

template<typename T>

struct Type {};

This lets you pass these types to the template function as extra parameters; see Listing Eleven. Then, as both Meyers and Alexandrescu suggest, you can add support for symmetry. Your collision-detection algorithm might turn up a given pair of colliding GameObjects in either order, (SpaceShip, Asteroid) or (Asteroid, SpaceShip). You don't want your collision-processing code to have to be sensitive to that.

Listing Twelve shows an add() function that supports inserting symmetrical Entry objects. This usage of boost::bind() simply reverses the Functor's actual arguments. Having symmetrical entries in the registry lets you write Listing Thirteen without worrying about whether the collision pair was actually detected as (Asteroid, SpaceShip). Both cases are handled by the same code.

I generalized the resulting DoubleDispatch class (available electronically; see "Resource Center," page 7) as a template so that you need not constrain the client to use a specific parameter base class—or a specific return type for the registered functions.

To illustrate how you can use this class, I've included a test program (also available electronically).

The excerpt in Listing Fourteen shows the calls that instantiate and populate the dispatcher, along with some hardcoded test collisions. That program produces the output in Listing Fifteen.

A number of refinements are possible:

• It would be useful to be able to erase() a specific Entry from the DoubleDispatch table. This is relatively straightforward: The Entry template class can capture its parameter types' typeid() values and implement an operator==() method that compares them directly. I wanted to avoid cluttering this discussion with that mechanism, though; the lookup and dispatch code does not depend on typeid() comparisons.
• Not every C++ compiler accepts void as the ReturnType template parameter because of the constructs shown in Listing Sixteen. There's template magic you can use to address that, but for present purposes, it only obscures the code.

• A more serious limitation is the need to register processing functions in a specific order. That implies that all registration calls are made by a central piece of code, which means that adding new GameObject subclasses requires maintaining that code.

I've also built a Java variation on DoubleDispatch (available electronically) where you need not break out EntryBase and Entry: Each Entry simply references the Class objects representing its two parameter types. And given the Class.isAssignableFrom(Class) method, I built an Entry.shouldPrecede(Entry) method that permits DoubleDispatch.add() to search the existing list for a good place to insert the new Entry. So in Java, you can call DoubleDispatch.add() to register new processing routines from many places in your program.

I would like to do the same in C++, but it's hard to compare two Entry template objects constructed at different times. I want to be able to examine the class types embedded in each Entry object to discover inheritance relationships—but I know of no way to do that without actually attempting to instantiate an object of one of the parameter types, which seems like a bad idea.

It's worth noting that Alexandrescu describes template magic that you can use to discover the inheritance relationship between two classes. To do that, however, both class types must be available at the same point in the code. And if you're willing to stipulate that the relevant types must all be available at the same place, then you don't need to extend DoubleDispatch because you can simply write the add() calls in an appropriate order.

DDJ

Listing One

class EntryBase
{
public:
    virtual bool matches(const GameObject& param1,
                         const GameObject& param2) const = 0;
};

Back to Article

Listing Two

class Entry: public EntryBase
{
public:
    virtual bool matches(const GameObject& param1,
                         const GameObject& param2) const
    {
        return (dynamic_cast<const SpaceShip*>(¶m1) != 0 &&
                dynamic_cast<const  Asteroid*>(¶m2) != 0);
    }
};

Back to Article

Listing Three

template<typename Type1, typename Type2>
class Entry: public EntryBase
{
public:
    virtual bool matches(const GameObject& param1,
                         const GameObject& param2) const
    {
        return (dynamic_cast<const Type1*>(¶m1) != 0 &&
                dynamic_cast<const Type2*>(¶m2) != 0);
    }
};

Back to Article

Listing Four

try
{
    dubiousRoutine();
}
catch (const ErrorRuntime& e)
{
    ...
}
catch (const ErrorBounds& e)        // whoops, never reached!
{
    ...
}
catch (const Error& e)
{
    ...
}

Back to Article

Listing Five

try
{
    dubiousRoutine();
}
catch (const ErrorBounds& e)        // better
{
    ...

}
catch (const ErrorRuntime& e)
{
    ...
}
catch (const Error& e)
{
    ...
}

Back to Article

Listing Six

typedef boost::shared_ptr<EntryBase> as EntryPtr;
typedef std::list<EntryPtr> DispatchTable;
DispatchTable mDispatch;

Back to Article

Listing Seven

// Look up the first matching entry.
EntryPtr lookup(const GameObject& param1, const GameObject& param2) const
{
    DispatchTable::const_iterator found =
        std::find_if(mDispatch.begin(), mDispatch.end(),
                     boost::bind(&EntryBase::matches, _1,
                                 boost::ref(param1), boost::ref(param2)));
    if (found != mDispatch.end())
        return *found;
    return 0;
}

Back to Article

Listing Eight

template<typename Type1, typename Type2, class Functor>
class Entry: public EntryBase
{
    // Bind whatever function or function object the instantiator passed.
    Functor mFunc;
public:
    Entry(Functor func): mFunc(func) {}
    virtual bool matches(const GameObject& param1,
                         const GameObject& param2) const { ... }
};

Back to Article

Listing Nine

class EntryBase
{
public:
    ...
    virtual void operator()(GameObject& param1,
                            GameObject& param2) const = 0;
};

template<typename Type1, typename Type2, class Functor>
class Entry: public EntryBase
{
    Functor mFunc;
public:
    Entry(Functor func): mFunc(func) {}
    ...
    virtual void operator()(GameObject& param1,
                            GameObject& param2) const
    {
        mFunc(dynamic_cast<Type1&>(param1),
              dynamic_cast<Type2&>(param2));
    }
};

Back to Article

Listing Ten

void call(GameObject& param1, GameObject& param2) const
{
    EntryPtr found = lookup(param1, param2);
    if (found.get() == 0)
        return; 
    (*found)(param1, param2); // call the Functor we found
}

Back to Article

Listing Eleven

template<typename Type1, typename Type2, class Functor>
void insert(const Type<Type1>&, const Type<Type2>&, Functor func)
{
    mDispatch.insert(mDispatch.end(),
                     EntryPtr(new Entry<Type1, Type2, Functor>(func)));
}

Back to Article

Listing Twelve

template<typename Type1, typename Type2, class Functor>
void add(const Type<Type1>& t1, const Type<Type2>& t2, Functor func,
         bool symmetrical = false)
{
    insert(t1, t2, func);
    if (symmetrical)
        insert(t2, t1, boost::bind(func, _2, _1));
}

Back to Article

Listing Thirteen

void shipAsteroid(SpaceShip& ship, Asteroid& rock)
{
  cout << rock.stringize() << " has pulverized " << ship.stringize() << endl;
}

Back to Article

Listing Fourteen

typedef DoubleDispatch<int, GameObject> DD;
DD dispatcher;
dispatcher.add(DD::Type<SpaceShip>(), DD::Type<Asteroid>(),
               shipAsteroid, true);
dispatcher.add(DD::Type<SpaceShip>(), DD::Type<SpaceStation>(),
               shipStation, true);
dispatcher.add(DD::Type<Asteroid>(), DD::Type<SpaceStation>(),
               asteroidStation, true);

    // Instantiate a few GameObjects.  Make sure we refer to them
    // polymorphically, and don't let them leak.
    std::auto_ptr<GameObject> home(new SpaceStation("Terra Station"));
    std::auto_ptr<GameObject> obstacle(new Asteroid("Ganymede"));
    std::auto_ptr<GameObject> tug(new CommercialShip("Pilotfish"));
    std::auto_ptr<GameObject> patrol(new MilitaryShip("Enterprise"));

    // Try colliding them.
    dispatcher(*home, *tug);        // reverse params, SpaceShip subclass
    dispatcher(*patrol, *home);     // forward params, SpaceShip subclass
    dispatcher(*obstacle, *home);   // forward params
    dispatcher(*home, *obstacle);   // reverse params
    dispatcher(*tug, *obstacle);    // forward params, SpaceShip subclass
    dispatcher(*obstacle, *patrol); // reverse params, SpaceShip subclass

Back to Article

Listing Fifteen

class CommercialShip Pilotfish has docked at class SpaceStation Terra Station
class MilitaryShip Enterprise has docked at class SpaceStation Terra Station
class Asteroid Ganymede has damaged class SpaceStation Terra Station
class Asteroid Ganymede has damaged class SpaceStation Terra Station
class Asteroid Ganymede has pulverized class CommercialShip Pilotfish
class Asteroid Ganymede has pulverized class MilitaryShip Enterprise

Back to Article

Listing Sixteen

ReturnType operator()(ParamBaseType& param1, ParamBaseType& param2) const
{
  EntryPtr found = lookup(param1, param2);
   if (found.get() == 0)
     return ReturnType();          // return void() ?!?
  return (*found)(param1, param2); //return (value returned by void function)
}

Back to Article