C++ double dispatch “extensible” without RTTI

Question

Does anyone know a way to have double dispatch handled correctly in C++ without using RTTI and dynamic_cast<> and also a solution, in which the class hierarchy is extensible, that is the base class can be derived from further and its definition/implementation does not need to know about that?
I suspect there is no way, but I'd be glad to be proven wrong :)

Answer 1

The first thing to realize is that double (or higher order) dispatch doesn't scale. With single dispatch, and n types, you need n functions; for double dispatch n^2, and so on. How you handle this problem partially determines how you handle double dispatch. One obvious solution is to limit the number of derived types, by creating a closed hierarchy; in that case, double dispatch can be implemented easily using a variant of the visitor pattern. If you don't close the hierarchy, then you have several possible approaches.

If you insist that every pair corresponds to a function, then you basically need a:

std::map<std::pair<std::type_index, std::type_index>, void (*)(Base const& lhs, Base const& rhs)>
                dispatchMap;

(Adjust the function signature as necessary.) You also have to implement the n^2 functions, and insert them into the dispatchMap. (I'm assuming here that you use free functions; there's no logical reason to put them in one of the classes rather than the other.) After that, you call:

(*dispatchMap[std::make_pair( std::type_index( typeid( obj1 ) ), std::type_index( typeid( obj2 ) )])( obj1, obj2 );

(You'll obviously want to wrap that into a function; it's not the sort of thing you want scattered all over the code.)

A minor variant would be to say that only certain combinations are legal. In this case, you can use find on the dispatchMap, and generate an error if you don't find what you're looking for. (Expect a lot of errors.) The same solution could e used if you can define some sort of default behavior.

If you want to do it 100% correctly, with some of the functions able to handle an intermediate class and all of its derivatives, you then need some sort of more dynamic searching, and ordering to control overload resolution. Consider for example:

            Base
         /       \
        /         \
       I1          I2
      /  \        /  \
     /    \      /    \
    D1a   D1b   D2a   D2b

If you have an f(I1, D2a) and an f(D1a, I2), which one should be chosen. The simplest solution is just a linear search, selecting the first which can be called (as determined by dynamic_cast on pointers to the objects), and manually managing the order of insertion to define the overload resolution you wish. With n^2 functions, this could become slow fairly quickly, however. Since there is an ordering, it should be possible to use std::map, but the ordering function is going to be decidedly non-trivial to implement (and will still have to use dynamic_cast all over the place).

All things considered, my suggestion would be to limit double dispatch to small, closed hierarchies, and stick to some variant of the visitor pattern.

Answer 2

The "visitor pattern" in C++ is often equated with double dispatch. It uses no RTTI or dynamic_casts.

See also the answers to this question.

Answer 3

The first problem is trivial. dynamic_cast involves two things: run-time check and a type cast. The former requires RTTI, the latter does not. All you need to do to replace dynamic_cast with a functionality that does the same without requiring RTTI is to have your own method to check the type at run-time. To do this, all you need is a simple virtual function that returns some sort of identification of what type it is or what more-specific interface it complies to (that can be an enum, an integer ID, even a string). For the cast, you can safely do a static_cast once you have already done the run-time check yourself and you are sure that the type you are casting to is in the object's hierarchy. So, that solves the problem of emulating the "full" functionality of dynamic_cast without needing the built-in RTTI. Another, more involved solution is to create your own RTTI system (like it is done in several softwares, like LLVM that Matthieu mentioned).

The second problem is a big one. How to create a double dispatch mechanism that scales well with an extensible class hierarchy. That's hard. At compile-time (static polymorphism), this can be done quite nicely with function overloads (and/or template specializations). At run-time, this is much harder. As far as I know, the only solution, as mentioned by Konrad, is to keep a dispatch table of function pointers (or something of that nature). With some use of static polymorphism and splitting dispatch functions into categories (like function signatures and stuff), you can avoid having to violate type safety, in my opinion. But, before implementing this, you should think very hard about your design to see if this double dispatch is really necessary, if it really needs to be a run-time dispatch, and if it really needs to have a separate function for each combination of two classes involved (maybe you can come up with a reduced and fixed number of abstract classes that capture all the truly distinct methods you need to implement).

Answer 4

You may want to check how LLVM implement isa<>, dyn_cast<> and cast<> as a template system, since it's compiled without RTTI.

It is a bit cumbersome (requires tidbits of code in every class involved) but very lightweight.

LLVM Programmer's Manual has a nice example and a reference to the implementation.

(All 3 methods share the same tidbit of code)

Answer 5

You can fake the behaviour by implementing the compile-time logic of multiple dispatch yourself. However, this is extremely tedious. Bjarne Stroustrup has co-authored a paper describing how this could be implemented in a compiler.

The underlying mechanism – a dispatch table – could be dynamically generated. However, using this approach you would of course lose all syntactical support. You’d need to to maintain 2-dimensional matrix of method pointers and manually look up the correct method depending on the argument types. This would render a simple (hypothetical) call

collision(foo, bar);

at least as complicated as

DynamicDispatchTable::lookup(collision_signature, FooClass, BarClass)(foo, bar);

since you didn’t want to use RTTI. And this is assuming that all your methods take only two arguments. As soon as more arguments are required (even if those aren’t part of the multiple dispatch) this becomes more complicated still, and would require circumventing type safety.