Sebastian Moleski wrote:
>
> I have heard term before. What exactly is Scott Meyer's double
> dispatch engine? Can anyone point me to some info on it.

It was in Andrei's original post: MEC++ Item 31.  Translated,
that's More Effective C++, by Scott Meyers, published by
Addison-Wesley, Item 31.  Scott goes on, for some 24 pages,
developing a double-dispatch engine.

--
Robert Stewart     |  rob-at-giage-dot-com
Software Engineer  |  using std::disclaimer;
Giage, Inc.        |  http://www.giage.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hi,


I decided to post this to csc++ in addition to clc++m because there's
a related thread in there, and anyway the subject raises some
standard-related questions.

I will present the essentials of a refinement of Scott's DD engine
(MEC++, Item 31) that *almost* works with inheritance, and I would be
curious to hear your opinion.

Disclaimer: you must have groked Item 31.

Scott Meyers' approach was simple: for each pair of std::type_info
objects you want to dispatch upon, you register a pointer to a
function with the double dispatcher. The double dispatcher stores the
information in a std::map. At runtime, when invoked with two unknown
objects, the double dispatcher performs a fast search (logarithmic
time) for type discovery, and if it finds an entry, fires the
appropriate pointer to function.

The addition is to store additional information together with the
registered callback, such as the size of the involved objects and a
secondary pointer to function.

You have that information available at registration time, because the
registration function is a template function:

class BasicDispatcher
{
    ...
    typedef void (*CollisionFnType)(GameObject&, GameObject&);
    template <class Lhs, class Rhs>
    void Add(CollisionFnType);
};

You use Add like so:

void CollideSpaceshipAsteroid(Shape& s1, Shape& s2)
{
    Spaceship& lhs = dynamic_cast<Spaceship&>(s1);
    Asteroid& rhs = dynamic_cast<Asteroid&>(s2);
    ... use lhs and rhs ...
}

BasicDispatcher dd;
dd.Add<Spaceship, Asteroid>(CollideSpaceshipAsteroid);

Okay, everything fine. The advantage of using a template for Add is
that inside Add you have full type information about the two types
involved. So you store in the map: the sizes of the two concrete
objects and some pointers to interesting functions. The mapped type is
a little struct with this information:

class BasicDispatcher
{
    ...
    typedef const char* (*GetAddrType)(Shape&);
    struct MappedType
    {
        CollisionFnType fn_; // this is the only data in Scott's
engine
        // Added (compared to Scott's engine)
        GetAddrType getAddrLhs_;
        GetAddrType getAddrRhs_;
        size_t lhsSize;
        size_t rhsSize;
    };
    ...
    template <class T>
    const char* GetAddr(GameObject& obj)
    {
        return reinterpret_cast<const char*>(
            dynamic_cast<T*>(&obj));
    }
};

Here's a sketch of Add:

template <class Lhs, class Rhs>
void BasicDispatcher::Add(CollisionFnType fn)
{
    MappedType toAdd = { fn, &GetAddr<Lhs>, &GetAddr<Rhs>,
        sizeof(Lhs), sizeof(Rhs) };
    ... insert toAdd in the collision map ...
}

The point is that we stored rich information about Lhs and Rhs in the
map. This includes the sizes of the types and two functions that
return the addresses of the derived (Lhs/Rhs) objects starting from a
pointer to base.

Now here's how this information is used.

When you want to dispatch a call, you look up the map with find(). If
you find an entry, great, invoke the callback and you're done.

If not, you do a linear search through the map, in look for a
compatible call. A compatible call is one for which both
getAddrLhs_(myLhs) and getAddrRhs_(myRhs) return non-null pointers.
Here's some code:

void BasicDispatcher::Collide(GameObject& myLhs, GameObject&  myRhs)
{
    if (map_.find(...typeid stuff ...) != map_end)
    {
        ... cool, invoke the handler ...
        return;
    }
    for (MapType::iterator i = map_.begin(); i != map_.end(); ++i)
    {
        const char* addrLhs = getAddrLhs_(myLhs);
        if (!addrLhs) continue;
        const char* addrLhs = getAddrLhs_(myLhs);
        if (!addrRhs) continue;
        // found a compatible match
        ... add the entry to the map...
        i->second.fn_(lhs, rhs);
        return;
    }
}

I'm not sure I explained the scheme well. The basic idea is that I
look through the map, and I use the two ancillary callbacks to figure
out whether the objects myLhs and myRhs are convertible to some types
registered with the engine. For instance, if I register a collision of
a Spaceship and an Asteroid and then I try to dispatch on a
MilitarySpaceship (derived from Spaceship) and an Asteroid, the loop
above will find the approximate match and will fire the callback.

What's even nicer is that after the linear search the found compatible
entry is added to the map, so next time you dispatch on a
MilitarySpaceship and an Asteroid, you do it in logarithmic time.

Well, things are not so simple. If you now inherit BorgShip from
MilitarySpaceship, you might be in trouble. Say you register
collisions for Spaceship-Asteroid and MilitarySpaceship-Asteroid. Then
you dispatch on a
BorgShip and an Asteroid. Bad - depending on how type_info::before
behaves, you might end up invoking the callback for
Spaceship-Asteroid, instead of the one for MilitarySpaceship-Asteroid.

There is a need to detect the inheritance relationship between
Spaceship and MilitarySpaceship *at runtime*, and by now I guess those
of you who've followed the thread "Class representation in memory" on
csc++ will understand what I am going to do.

I have all the data: pointers to objects and object sizes. I just have
to do some comparisons and I can disambiguate between
Spaceship-Asteroid and MilitarySpaceship-Asteroid.

Unfortunately, the scheme isn't perfect. The caveat is that the
algorithm cannot disambiguate between two classes that have the same
size. For instance, if MilitarySpaceship and Spaceship have the same
size, the engine wil report an ambiguity for a BorgShip when in fact
it should have invoked a collision involving a MilitarySpaceship.

Well, I think I haven't been quite clear, but I hope I gave an idea on
how things work. Essentially, I save some data (sizes + callbacks) at
registration time (when I have rich type information). Then I use that
saved data to implement support for inheritance.

My question essentially is: is this stuff crap (because it doesn't
handle all inheritance cases, reporting "false ambiguities"), or is it
a no-nonsense step forward to a better double dispatch engine? Some
said the latter, but I'm not that convinced.

I'm highly interested in getting input, comments, impressions etc.
about the above. Thanks.


Andrei



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Andrei Alexandrescu" <andrewalex@hotmail.com> writes:
> void CollideSpaceshipAsteroid(Shape& s1, Shape& s2)
> {
>     Spaceship& lhs = dynamic_cast<Spaceship&>(s1);
>     Asteroid& rhs = dynamic_cast<Asteroid&>(s2);
>     ... use lhs and rhs ...
> }
>
> BasicDispatcher dd;
> dd.Add<Spaceship, Asteroid>(CollideSpaceshipAsteroid);

Hmm.. I guess you could provide an interface that deduced those two
template arguments from the type of the function, so the user would
just write functions with real types, and you would provide a wrapper
that did all the dynamic_casts. Will be a small complication, but I
guess it will result in a better interface for the user.

> If not, you do a linear search through the map, in look for a
> compatible call. A compatible call is one for which both
> getAddrLhs_(myLhs) and getAddrRhs_(myRhs) return non-null pointers.
> Here's some code:
>
> void BasicDispatcher::Collide(GameObject& myLhs, GameObject&  myRhs)
> {
>     if (map_.find(...typeid stuff ...) != map_end)
>     {
>         ... cool, invoke the handler ...
>         return;
>     }
>     for (MapType::iterator i = map_.begin(); i != map_.end(); ++i)
>     {
>         const char* addrLhs = getAddrLhs_(myLhs);
>         if (!addrLhs) continue;
>         const char* addrLhs = getAddrLhs_(myLhs);

I guess you mean Rhs here.

>         if (!addrRhs) continue;
[snip]
> Well, things are not so simple. If you now inherit BorgShip from
> MilitarySpaceship, you might be in trouble. Say you register
> collisions for Spaceship-Asteroid and MilitarySpaceship-Asteroid. Then
> you dispatch on a
> BorgShip and an Asteroid. Bad - depending on how type_info::before
> behaves, you might end up invoking the callback for
> Spaceship-Asteroid, instead of the one for MilitarySpaceship-Asteroid.
>
> There is a need to detect the inheritance relationship between
> Spaceship and MilitarySpaceship *at runtime*, and by now I guess those
> of you who've followed the thread "Class representation in memory" on
> csc++ will understand what I am going to do.

Oh no! Not that :). How about the following scheme for achieving the same:

You register, along with all the rest of the data for each collision
function, a prototype instance of each class supported.  Then, at the
Add method, you try to dynamic_cast each prototype instance already
registered to the type being registered, and record the results in a
2-d table [of bools] representing inheritance relations between the
classes. Similarly, you try to dynamic_cast the prototype instance
being registered to each already registered type using the GetAddr
mechanism. From these (after a sequence of registrations), you obtain
a two-dimensional table of allowed dynamic_casts, which you can use at
run-time to determine which class is the most specialised from the
ones registered. [the details are a bit sketchy yet, especially if you
have multiple inheritance, but I hope you get the idea].
--
 Esa Pulkkinen                        | C++ programmers do it virtually
 E-Mail:  esap@cs.tut.fi              | everywhere with class, resulting
 WWW   :  http://www.cs.tut.fi/~esap/ | in multiple inheritance.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

I have heard term before. What exactly is Scott Meyer's double
dispatch engine? Can anyone point me to some info on it.

--
Sebastian Moleski



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Esa Pulkkinen <esap@cs.tut.fi> wrote in message
news:87em73ftuo.fsf@c156a.w2.ton.tut.fi...
> Hmm.. I guess you could provide an interface that deduced those two
> template arguments from the type of the function, so the user would
> just write functions with real types, and you would provide a
wrapper
> that did all the dynamic_casts. Will be a small complication, but I
> guess it will result in a better interface for the user.

That's another subject: "Automating conversions in Scott's DD engine."
For simplifying things, in this post I discussed only inheritance
issues. Discussing in full these and other known aspects of DD takes
about 50 pages :o}.

> You register, along with all the rest of the data for each collision
> function, a prototype instance of each class supported.

I did consider this scheme, but I rejected it as too inconveninent. I
don't think the user will want to a pointer to a possibly complex
object just for the DD engine to fiddle with.

Alternatively, I can create prototypes inside Add() with new, but what
if the user disabled the default constructor?


Andrei


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]