Preamble
This paper provides a way to solve famous "multimethods problem". The main merits of the proposed solution are:
- no use of type casts of any kind (dynamic, static, reinterpret, const or C-style)
- no use of RTTI;
- no use of preprocessor;
- strong type safety;
- separate compilation;
- constant time of multimethod execution;
- no dynamic memory allocation (via
new
or malloc
) during multimethod call;
- no use of nonstandard libraries;
- only standard C++ features is used.
The Problem
Let's consider following example.
Suppose we have a simple hierarchy of geometrical shapes and want to write a function answering the question: "do two (or more) shapes intersect". Shapes hierarchy may look as follows.
Function, that checks for shapes intersections, must work with IShape
references, i.e. in polymorphic manner. For example:
void foo( IShape_& _shape0, IShape_& _shape1 ) {
bool f = CheckIntersection( _shape0, _shape1 );
}
...
Rect_ rect( Point_( 1, 1), Point_( 2, 2) );
Triangle_ tri( Point_( 0, 0), Point_( 2, 0), Point_( 0, 2) );
foo( rect, tri );
It corresponds to object-oriented view of virtual methods execution, where we don't care about concrete types of objects, because appropriate method is called automatically, via virtual method invocation mechanism [1].
Indeed, it's easy to write specialized intersection functions (for intersecting rectangle against triangle, for example). However, when CheckIntersection
is called, there is no information about concrete types of its arguments. And there is no compiler support to do this job.
Run-time type determination
Nevertheless, there is a regular way to determine concrete object type at run-time using well-known Visitor
pattern [2]. This method is also called dual dispatching. Each visitable object should implement method Visit
that accepts reference to special object - dispatcher. Dispatcher should have a set of Dispatch
methods that accepts references to concrete types of visitable objects. Simple example of Visitor
pattern usage is shown below.
struct Triangle_;
struct Rect_;
struct IDispatcher_ {
virtual void Dispatch( Triangle_& _shape ) = 0;
virtual void Dispatch( Rect_& _shape ) = 0;
};
struct IShape_ {
virtual void Visit( IDispatcher_& _dsp ) = 0;
};
struct Triangle_ : public IShape_ {
virtual void Visit( IDispatcher_& _dsp ) {
_dsp.Dispatch( *this );
}
};
struct Rect_ : public IShape_ {
virtual void Visit( IDispatcher_& _dsp ) {
_dsp.Dispatch( *this );
}
};
struct Dispatcher_ : public IDispatcher_ {
virtual void Dispatch( Triangle_& _shape ) {
cout << "This is a triangle." << endl;
}
virtual void Dispatch( Rect_& _shape ) {
cout << "This is a rect." << endl;
}
};
void PrintType( IShape_& _shape ) {
Dispatcher_ dsp;
_shape.Visit( dsp );
}
int main()
{
Rect_ rect;
Triangle_ triangle;
PrintType( rect );
PrintType( triangle );
return 0;
}
This programs prints:
This is a rect.
This is a triangle.
This method has a constant overhead: two virtual method calls plus object construction on stack.
Visitable shapes
We will use the Visitor
pattern to implement multimethods. All particular shapes should be visitable objects, i. e. all of them should implement Visit
method. We can write the following code:
class IShapesDsp_;
struct IShape_ {
typedef IShapesDsp_ IDispatcher;
virtual void Visit( IDispatcher& _dispatcher ) = 0;
};
#include "IShape.h"
#include "Point.h"
class Rect_
: public IShape_
{
public:
Rect_( Point_ const& _top_left, Point_ const& _bottom_right );
Point_ const& GetTopLeft();
Point_ const& GetBottomRight();
virtual void Visit( IDispatcher& _dispatcher );
private:
Point_ top_left;
Point_ bottom_right;
};
Note that when we declare Visit
methods we don't need to have a full definition of IShapesDsp
, forward declaration is ok. In other words, declaration of shapes depends only on IShapesDsp
name.
Dispatcher interface generation
We will generate dispatcher interface from typelist of used shapes. Typelists are discussed in [3]. Very lightweight type-list implementation will be used for simplicity.
Using partial template specialization mechanism [4], dispatcher interface will be generated using following code:
template< typename TItem >
struct IDispatchPart_ {
virtual void Dispatch( TItem& _item ) = 0;
};
template< typename TItems >
struct IDispatcher_
: public IDispatchPart_< typename TItems::item >
, public IDispatcher_< typename TItems::next > {};
template<>
struct IDispatcher_< ListEnd_ > {};
class Rect_;
class Square_;
class Triangle_;
class RightTriangle_;
typedef TypeList_< Rect_,
TypeList_< Square_,
TypeList_< Triangle_,
TypeList_< RightTriangle_
> > > > Shapes_;
class IShapesDsp_ : public IDispatcher_< Shapes_ > {};
The following hierarchy will be generated:
Note that the declaration of IShapesDsp
doesn't depend on shapes declarations, it depends only on their names.
Shapes implementation
Although shapes don't depend on IShapesDsp
declaration, their implementations do. Now, when IShapesDsp
is declared, we can implement shapes' Visit
methods.
#include "IShapesDsp.h"
template< typename TShape, typename IDispatcher >
void VisitImpl( TShape& _self, IDispatcher& _dispatcher )
{
IDispatchPart_< TShape >& part = _dispatcher;
part.Dispatch( _self );
}
#include "Rect.h"
#include "VisitImpl.h"
void Rect_::Visit( IDispatcher& _dispatcher ) {
VisitImpl( *this, _dispatcher );
}
void Triangle_::Visit( IDispatcher& _dispatcher ) {
VisitImpl( *this, _dispatcher );
}
Dispatcher generation
Now we have the dispatcher interface and the set of nodes, which can be visited by this interface implementations. These implementations will be generated from type-list using the following code:
template < typename TItems,
typename IDsp,
typename TMixedImpl
>
class Dispatcher_
: public Dispatcher_< typename TItems::next, IDsp, TMixedImpl >
{
typedef Dispatcher_< typename TItems::next, IDsp, TMixedImpl > TBase;
typedef typename TItems::item TItem;
virtual void Dispatch( TItem& _item ) {
Implement( _item );
}
};
template < typename IDsp,
typename TMixedImpl
>
class Dispatcher_<ListEnd_, IDsp, TMixedImpl >
: public IDsp
, public TMixedImpl {};
This Dispatcher
overrides all pure virtual Dispatch
methods that were declared in IDsp
.Implementations of these methods are redirected to a mixin class, passed as TMixedImpl
parameter.
MultiMethods gateway
Now, when we know how to generate dispatchers, we can write our CheckIntersection
function. It is a non-template free function that can be located in a *.cpp file. We will overload CheckIntersection
for each arity of multimethod. n-ary multimethod is executed in n steps. Each i-th step begins with dispatcher creation. This dispatcher is used to determine concrete type of i-th multimethod's argument. Information of this type is propagated to the next step and so on. At the last step, where types of all arguments are known, fully specialized implementation is invoked.
Here are the dual and triple versions:
struct IntersectionsBulk_
{
template< typename TShape0, typename TShape1 >
struct DualImpl_ : public DualIntersecter_< TShape0, TShape1 > {};
template< typename TShape0, typename TShape1, typename TShape2 >
struct TripleImpl_
: public TripleIntersecter_< TShape0, TShape1, TShape2 > {};
};
bool CheckIntersection( IShape_& _shape0, IShape_& _shape1 )
{
Dispatcher_< Shapes_, IShapesDsp_, FirstStep_<2, IntersectionsBulk_> > dsp;
dsp.UnknownArg( 1, _shape1 );
_shape0.Visit( dsp );
return dsp.GetResult();
}
bool CheckIntersection( IShape_& _shape0, IShape_& _shape1, IShape_& _shape2 )
{
Dispatcher_< Shapes_, IShapesDsp_, FirstStep_<3, IntersectionsBulk_> > dsp;
dsp.UnknownArg( 1, _shape1 );
dsp.UnknownArg( 2, _shape2 );
_shape0.Visit( dsp );
return dsp.GetResult();
}
Let's look at FirstStep template class declaration:
template< int Arity, typename TImplBulk >
struct FirstStep_ : public FirstStepBase_< Arity > {
protected:
template< typename TShape0 >
inline void Implement( TShape0& _arg0 ) {
Dispatcher_< Shapes_, IShapesDsp_, SecondStep_< TShape0,
Arity, TImplBulk > > dsp;
dsp.Arg0( _arg0 );
for ( int i = 1; i < Arity; ++i )
dsp.UnknownArg( i, *unknown[i] );
unknown[1]->Visit( dsp );
SetResult( dsp.GetResult() );
}
};
It has two template parameters:
- arity of executed multimethod;
- intersection checker specializations container.
Also it has one template method - Implement
, which will be called from an outer dispatcher. In Implement
method the next dispatcher is created. Note, that SecondStep
receives type information about first argument and a typed reference to it.
SecondStep
template class has two specializations. There is a general version that works like FirstStep
and a specialized binary version, which is shown below.
template< typename TShape0, typename TImplBulk >
struct SecondStep_< TShape0, 2, TImplBulk > : public SecondStepBase_< TShape0, 2 > {
protected:
template< typename TShape1 >
inline void Implement( TShape1& _arg1 ) {
typedef typename TImplBulk::DualImpl_< TShape0, TShape1 >::Impl_ TImpl;
SetResult( TImpl::Implement( *arg0, _arg1 ) );
}
};
Specialized multimethod implementations
Specialized versions of intersection checkers are called via static methods of XXXIntersecter
template class. There is a dedicated class for each arity. These classes should be defined in place where multimethod execution is done (Intersection.cpp in our example).
The DualIntersecter
class is for dual multimethods. Firstly, forward declaration of DualIntersecter
is provided:
template< typename TShape0, typename TShape1 >
struct DualIntersecter_;
After that the specialized versions can be added. For crossing rectangles against triangles we will write:
class Rect_;
class Triangle_;
template<>
struct DualIntersecter_< Rect_, Triangle_ >
{
typedef DualIntersecter_< Rect_, Triangle_ > Impl_;
static bool Implement( Rect_& _shape0, Triangle_& _shape1 );
};
bool DualIntersecter_< Rect_, Triangle_ >
::Implement( Rect_& _shape0, Triangle_& _shape1 )
{
std::cout << "Intersecting rectangle against triangle." << std::endl;
return true;
}
It is obvious that CheckIntersection
function is commutative, but compiler doesn't know about it. We must provide a reverse specialization for crossing triangles against rectangles. It can be done very easy:
template <typename TShape0, typename TShape1>
struct DualReverse_
{
typedef DualReverse_< TShape0, TShape1 > Impl_;
static bool Implement( TShape0& _arg0, TShape1& _arg1 )
{
typedef DualIntersecter_< TShape1, TShape0 >::Impl_ TImpl;
return TImpl::Implement( _arg1, _arg0 );
}
};
template<>
struct DualIntersecter_< Triangle_, Rect_ >
: public DualReverse_< Triangle_, Rect_ > {};
Partial intersection specialization
Suppose we don't want to write specialized versions to intersect squares against any another shapes, because it can be done via rectangle facilities. Here we can use partial intersection specialization. Note that we should declare three specializations to avoid ambiguity.
#include "Square.h"
template< typename TShape1 >
struct DualIntersecter_< Square_, TShape1 >
: public DualIntersecter_< Rect_, TShape1 > {};
template<>
struct DualIntersecter_< Square_, Square_ >
: public DualIntersecter_< Rect_, Rect_ > {};
template< typename TShape0 >
struct DualIntersecter_< TShape0, Square_ >
: public DualReverse_< TShape0, Square_ > {};
Specialization redirection
Note that each specialization declares Impl
typedef. In trivial cases specialization simply re-declares itself. But this typedef allows us to overcome some C++ limitations. Suppose we want to write specialization, that should intersect any two shapes, which are convertible to rectangles. But C++ template specialization lookup algorithm is unable to work with relations between types. That's why we will declare most general DualIntersecter
specialization that checks relations between types, provides specialization for crossing rectangular shapes and in other cases redirects to DualIntersecter2
. This specialization redirection pattern can be applied sequentially.
#include "TypeStuff.h"
#include "Rect.h"
#include "Square.h"
struct RectsIntersecter_ {
typedef RectsIntersecter_ Impl_;
static bool Implement( Rect_& _shape0, Rect_& _shape1 );
};
template< typename TShape0, typename TShape1 >
struct DualIntersecter2_;
template< typename TShape0, typename TShape1 >
struct DualIntersecter_ {
static bool const both_rectangular =
IsConvertible_< TShape0, Rect_ >::value &&
IsConvertible_< TShape1, Rect_ >::value;
typedef typename
If_< both_rectangular,
RectsIntersecter_::Impl_,
typename DualIntersecter2_< TShape0, TShape1 >::Impl_ >::type
Impl_;
};
bool RectsIntersecter_::Implement( Rect_& _shape0, Rect_& _shape1 ) {
std::cout << "Intersecting rectangle against rectangle." << std::endl;
return true;
}
Instead of specialization redirection nested if meta-functions can be used.
Hierarchy furling
Suppose we don't want to write specialized versions to intersect equilateral triangles against any other shapes, because it can be done via triangle ones. Solution is very easy - just don't override Visit
method in EquilateralTriangle
and don't include this type in shapes type-list.
Integrity
In this approach compiler maintains integrity. It is impossible to forget some specialization, because compiler refuses to accept such programs. For example, it's impossible to comment any of dual specializations #include directives in Intersection.cpp.
However, for debug and development reasons, some specializations subset can be temporarily replaced by a most general specialization of XXXIntersecter
. We use this technique for triple intersections.
Overhead
Multimethod execution has constant overhead. This overhead depends only on multimethod arity. When n-ary multimethod is executed:
- 2 * n virtual methods are called;
- n auxiliary objects are constructed on stack;
- n * (n + c) non-virtual get/set methods are called (may be inlined), where c is a small constant.
Dependencies
Let's look on our example dependency diagram:
As you can see, client code depends only on shapes library interface. Client code doesn't include typelists, dispatcher interface and its implementations. That's why there is no compilation time growing. And even if specializations configuration changes, client code will not be recompiled.
Compilation in separate modules
Moreover, some shapes and their intersection checkers' specializations can be moved into separate module (DLL).The essence of the matter is that Visit
method can be implemented using dynamic_cast
. It can receive a reference to some polymorphic object and cast it to the appropriate IDispatchPart
. But this solution isn't discussed here in detail, because it breaks the beautiful type safety concept.
History
This work based on MultiMethods Implementation via Deferred Dispatching. The main advantage against previous solution is a separate compilation possibility.
Acknowledgements
Special thanks to:
- Alexander Evdokimov;
- Michael Litvinov.
References
- Bjarne Stroustrup. The C++ Programming Language. Addison-Wesley, third edition, August 1997.
- Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns - Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995.
- Andrei Alexandrescu. Modern C++ Design. Addison-Wesley, C++ In-Depth series. 2001.
- David Vandevoorde and Nicolai M. Josuttis. C++ Templates: The Complete Guide. Addison-Wesley, 2003.