11.4 The Brute-Force Approach Automated

Because in some situations the speed of the brute-force approach can be unbeatable, it's worth paying attention to implementing such a dispatcher. Here's where typelists can be of help.

Recall from Chapter 3 that Loki defines a typelist facility—a collection of structures and compile-time algorithms that allow you to manipulate collections of types. A brute-force implementation of multimethods can use a client-provided typelist that specifies the classes in the hierarchy (in our example, Rectangle, Poly, Ellipse, etc.). Then a recursive template can generate the sequence of if-else statements.

In the general case, we can dispatch on different collections of types, so the typelist for the left-hand operand can differ from the one for the right-hand operand.

Let's try outlining a StaticDispatcher class template that performs the type deduction algorithm and then fires a function in another class. Explanations follow the code.

template


<


   class Executor,


   class BaseLhs,


   class TypesLhs,


   class BaseRhs = BaseLhs,


   class TypesRhs = TypesLhs


   typename ResultType = void


>


class StaticDispatcher


{


   typedef typename TypesLhs::Head Head;


   typedef typename TypesLhs::Tail Tail;


public:


   static ResultType Go(BaseLhs& lhs, BaseRhs& rhs,


      Executor exec)


   {


      if (Head* p1 = dynamic_cast<Head*>(&lhs))


      {


         return StaticDispatcher<Executor, BaseLhs,


            NullType, BaseRhs, TypesRhs>::DispatchRhs(


               *p1, rhs, exec);


      }


      else


      {


         return StaticDispatcher<Executor, BaseLhs,


            Tail, BaseRhs, TypesRhs>::Go(


               lhs, rhs, exec);


      }


   }


   ...


};

If you are familiar with typelists, the workings of StaticDispatcher are seen to be quite simple. StaticDispatcher has surprisingly little code for what it does.

StaticDispatcher has six template parameters. Executor is the type of the object that does the actual processing—in our example, hatching the intersection area. We'll discuss what Executor looks like a bit later.

BaseLhs and BaseRhs are the base types of the arguments on the left-hand side and the right-hand side, respectively. TypesLhs and TypesRhs are typelists containing the possible derived types for the two arguments. The default values of BaseRhs and TypesRhs foster a dispatcher for types in the same class hierarchy, as is the case with the drawing program example.

ResultType is the type of the result of the double-dispatch operation. In the general case, the dispatched function can return an arbitrary type. StaticDispatcher supports this dimension of genericity and forwards the result to the caller.

StaticDispatcher::Go tries a dynamic cast to the first type found in the TypesLhs typelist, against the address of lhs. If the dynamic cast fails, Go delegates to the remainder (tail) of TypesLhs in a recursive call to itself. (This is not a true recursive call, because each time we have a different instantiation of StaticDispatcher.)

The net effect is that Go performs a suite of if-else statements that apply dynamic_cast to each type in the typelist. When a match is found, Go invokes DispatchRhs. DispatchRhs does the second and last step of the type deduction—finding the dynamic type of rhs.

template <...>


class StaticDispatcher


{


   ... as above ...


   template <class SomeLhs>


   static ResultType DispatchRhs(SomeLhs& lhs, BaseRhs& rhs,


      Executor exec)


   {


      typedef typename TypesRhs::Head Head;


      typedef typename TypesRhs::Tail Tail;





      if (Head* p2 = dynamic_cast<Head*>(&rhs))


      {


         return exec.Fire(lhs, *p2);


      }


      else


      {


          return StaticDispatcher<Executor, SomeLhs,


             NullType, BaseRhs, Tail>::DispatchRhs(


                lhs, rhs, exec);


      }


   }


};

DispatchRhs performs the same algorithm for rhs as Go applied for lhs. In addition, when the dynamic cast on rhs succeeds, DispatchRhs calls Executor::Fire, passing it the two discovered types. Again, the code that the compiler generates is a suite of if-else statements. Interestingly, the compiler generates one such suite of if-else statements for each type in TypesLhs. Effectively, StaticDispatcher manages to generate an exponential amount of code with two typelists and a fixed codebase. This is an asset, but also a potential danger—too much code can hurt compile times, program size, and total execution time.

To treat the limit conditions that stop the compile-time recursion, we need to specialize StaticDispatcher for two cases: The type of lhs is not found in TypesLhs, and the type of rhs is not found in TypesRhs.

The first case (error on lhs) appears when you invoke Go on a StaticDispatcher with NullType as TypesLhs. This is the sign that the search depleted TypesLhs. (Recall from Chapter 3 that NullType is used to signal the last element in any typelist.)

template


<


   class Executor,


   class BaseLhs,


   class BaseRhs,


   class TypesRhs,


   typename ResultType


>


class StaticDispatcher<Executor, BaseLhs, NullType,


   BaseRhs, TypesRhs, ResultType>


{


   static void Go(BaseLhs& lhs, BaseRhs& rhs, Executor exec)


   {


      exec.OnError(lhs, rhs);


   }


};

Error handling is elegantly delegated to the Executor class, as you will see later in the discussion on Executor.

The second case (error on rhs) appears when you invoke DispatchRhs on a Static Dispatcher with NullType as TypesRhs. Hence the following specialization:

template


<


   class Executor,


   class BaseLhs,


   class TypesLhs,


   class BaseRhs,


   class TypesRhs,


   typename ResultType


>


class StaticDispatcher<Executor, BaseLhs, TypesLhs,


   BaseRhs, NullType, ResultType>


{


public:


   static void DispatchRhs(BaseLhs& lhs, BaseRhs& rhs,


      Executor& exec)


   {


      exec.OnError(lhs, rhs);


   }


};

It is time now to discuss what Executor must implement to take advantage of the double-dispatch engine we have just defined.

StaticDispatcher deals only with type discovery. After finding the right types and objects, it passes them to a call of Executor::Fire. To differentiate these calls, Executor must implement several overloads of Fire. For example, the Executor class for hatching shape intersections is as follows:

class HatchingExecutor


{


public:


   // Various intersection algorithms


   void Fire(Rectangle&, Rectangle&);


   void Fire(Rectangle&, Ellipse&);


   void Fire(Rectangle&, Poly&);


   void Fire(Ellipse&, Poly&);


   void Fire(Ellipse&, Ellipse&);


   void Fire(Poly&, Poly&);





   // Error handling routine


   void OnError(Shape&, Shape&);


};

You use HatchingExecutor with StaticDispatcher as shown in the following code:

typedef StaticDispatcher<HatchingExecutor, Shape,


   TYPELIST_3(Rectangle, Ellipse, Poly)> Dispatcher;


Shape *p1 = ...;


Shape *p2 = ...;


HatchingExecutor exec;


Dispatcher::Go(*p1, *p2, exec);

This code invokes the appropriate Fire overload in the HatchingExecutor class. You can see the StaticDispatcher class template as a mechanism that achieves dynamic overloading—it defers overloading rules to runtime. This makes StaticDispatcher remarkably easy to use. You just implement HatchingExecutor with the overloading rules in mind, and then you use StaticDispatcher as a black box that does the magic of applying overloading rules at runtime.

As a nice side effect, StaticDispatcher will unveil any overloading ambiguities at compile time. For instance, assume you don't declare HatchingExecutor::Fire(Ellipse&, Poly&). Instead, you declare HatchingExecutor::Fire(Ellipse&, Shape&) and Hatching Executor::Fire(Shape&, Poly&). Calling HatchingExecutor::Fire with an Ellipse and a Poly would result in an ambiguity—both functions compete to handle the call. Remarkably, StaticDispatcher signals the same error for you and with the same level Multimethods Chapter 11 of detail. StaticDispatcher is a tool that's very consistent with the existing C++ overloading rules.

What happens in the case of a runtime error—for instance, if you pass a Circle as one of the arguments of StaticDispatcher::Go? As hinted earlier, StaticDispatcher handles border cases by simply calling Executor::OnError with the original (not cast) lhs and rhs. This means that, in our example, HatchingExecutor::OnError (Shape&, Shape&) is the error handling routine. You can use this routine to do whatever you find appropriate—when it's called, it means that StaticDispatcher gave up on finding the dynamic types.

As discussed in the previous section, inheritance adds problems to a bruteforce dispatcher. That is, the following instantiation of StaticDispatcher has a bug:

typedef StaticDispatcher


<


   SomeExecutor,


   Shape,


   TYPELIST_4(Rectangle, Ellipse, Poly, RoundedRectangle)


>


MyDispatcher;

If you pass a RoundedRectangle to MyDispatcher, it will be considered a Rectangle. The dynamic_cast<Rectangle*> succeeds on a pointer to a RoundedRectangle, and because the dynamic_cast<RoundedRectangle*> is lower on the food chain, it will never be given a chance. The correct instantiation is

typedef StaticDispatcher


<


   SomeExecutor,


   Shape,


   TYPELIST_4(RoundedRectangle, Ellipse, Poly, Rectangle)


>


Dispatcher;

The general rule is to put the most derived types at the front of the typelist.

It would be nice if this transformation could be applied automatically, and typelists do support that. We have a means to detect inheritance at compile time (Chapter 2), and typelists can be sorted. This led to the DerivedToFront compile-time algorithm in Chapter 3.

All we have to do to take advantage of automatic sorting is to modify the implementation of StaticDispatcher as follows:

template <...>


class StaticDispatcher


{


   typedef typename DerivedToFront<


      typename TypesLhs::Head>::Result Head;


   typedef typename DerivedToFront<


      typename TypesLhs::Tail>::Result Tail;


public:


   ... as above ...


};

After all this handy automation, don't forget that all we have obtained is the code generation part. The dependency problems are still with us. Although it makes it very easy to implement brute-force multimethods, StaticDispatcher still has a dependency on all the types in the hierarchy. Its advantages are speed (if there are not too many types in the hierarchy) and nonintrusiveness—you don't have to modify a hierarchy to use StaticDispatcher with it.