TITLE: Thoughts on RTTI (run-time-type-identification)

PROBLEM: skochhar@cvbnet.cv.com (Sandeep Kochhar x4618 5-2 @ Computervision)

Currently, I'm still using a fairly  standard scheme for run-time
type checking (that works fine with C-front 2.1-based compilers),
[...]

The problem that I'm facing is that IsKindOf(A, B) when A is *not*
a subclass of B has to go all the way up to the root of A's class
hierarchy, making function calls...  Doing this several million
times in a graphics application can actually start affecting
performance...

1. Are there better ways to do runtime type checking that would make
   IsKindOf constant-time, or at least avoid upto N function calls, where
   N is the depth of A in the class hierarchy.


RESPONSE: rmartin@rcmcon.com (Robert Martin)

Yes, you can get RTTI behavior in very fast constant time.  Below is
the pattern to use.  I am sure that you can figure out ways to improve
upon it.  Of course all of the convolutions below are moot if you have
a compiler that supports RTTI...

class Base
{
  public:
    virtual void Handle(class BaseHandler&) const = 0;
};

class BaseHandler
{
  public:
    virtual void HandleD1(class D1*) const = 0;
    virtual void HandleD2(class D2*) const = 0;
};

class D1 : public Base
{
  public:
    virtual void Handle(BaseHandler& h) {h.HandleD1(this);}
};

class D2 : public Base
{
  public:
    virtual void Handle(BaseHandler& h) {h.HandleD2(this);}
};


class CastHandler : public BaseHandler
{
  public:
    CastHandler() :itsD1(0), itsD2(0) {}
    virtual void HandleD1(D1* d1) {itsD1 = d1;}
    virtual void HandleD2(D2* d2) {itsD2 = d2;}
    D1* GetD1() const {return itsD1;}
    D2* GetD2() const {return itsD2;}
  private:
    D1* itsD1;
    D2* itsD2;
};

D1* dynamicCastD1(const Base* b)
{
    CastHandler h;
    b->Hande(h);
    return h.GetD1();
}

D2* dynamicCastD2(const Base* b)
{
    CastHandler h;
    b->Hande(h);
    return h.GetD2();
}

> bs@alice.att.com (Bjarne Stroustrup) writes:
>
>Most (but not all) code is best written without RTTI and (in my
>opinion) RTTI of all forms are overused (in C++ and other languages).

Quit right.  Cases where RTTI *is* useful, however, are abundant.  For
example, the cannonical case of the basket of fruit.

I have a basket of fruit:  Apples, Oranges, Pears, Bananas, etc.  I
pass this basket around to people at a picnic.  Some people can only
eat apples, some can only eat pears, etc.

Each person object must be able to identify the fruit that they can
eat:

class Person
{
  virtual void SelectFruit(Basket<Fruit*>&) = 0;
  virtual void Eat(Fruit*) = 0;
};

class OrangeEatingPerson : public Person
{
  public:
    virtual void SelectFruit(Basket<Fruit*>& b)
    {
        Orange *o = 0;
        for(Iterator<Fruit*>i(b); !o && i; i++)
        {
          Fruit* f = *i; 
          Orange* o = dynamic_cast<Orange*>(f);
          if (o)
          {
              b.Remove(o);
              Eat(o);
          }
        }
    }
};

Some people will complain that you could do this without RTTI if you
placed IsOrange, IsApple, IsPear methods in Fruit.  However there are
two issues with this.  First, such code is nothing more than a simple
form of RTTI.  Secondly, it forces ugly dependencies into Fruit.
Fruit must now change whenever a new kind of fruit is added.  In
general, base classes should not depend upon their derivatives.

Others may suggest that the above could be accompolished by putting
IsGoodForOrangeEater, isGoodForAppleEater, isGoodForPearEater
functions in Fruit.  While subtly different from the above, I think
that the same two issues apply, except that now the dependency in Fruit
is upon the various Eaters.  We probably don't want Fruit knowing
about all the Eaters since we may want to reuse Fruit in a context
which does not *have* eaters.

Finally, some will suggest that Fruit should have an EatMe(Person*)
virtual function, and that each Person should have a set of virtual
Eat functions for each kind of fruit.  Such functions will be
implemented to do nothing, if it is the wrong kind of fruit; or to eat
the fruit if it is appropriate to that kind of person.  However
careful inspection of such code will show it to be equivalent to the
"Handler" code in the RTTI example that I posted above.  In effect,
such code *is* RTTI.

The big benefit that the compiler's new RTTI feature brings is that
RTTI can be accomplished without the strange dependencies that
"Handlers" force us into.  Consider the BaseHander class above.  It
knows about all the derivatives of Base.  And Base knows about
BaseHandler.  Thus by transitivity, Base has source code dependencies
upon its Derivatives.  When new derivatives are added, BaseHandler
will have to change, and Base (and therfore all its derivatives) will
have to be recompiled.  

I will use RTTI if it helps me to avoid such tangled dependencies.
On the other hand, I will avoid RTTI in cases where it adds unwanted
dependencies.  For example:

void SelectFruit(Fruit* f, Person* p)
{
    OrangeEater* oe = dynamic_cast<OrangeEater*>(p);
    PearEater*   pe = dynamic_cast<PearEater*>(p);

    Orange* orange = dynamic_cast<Ornage*>(f);
    Pear*   pear   = dynamic_cast<Pear*>(f);

    if (oe && orange) oe->Eat(orange);
    else if (pe && pear) pe->Eat(pear);
}

This function is hopelessly dependent upon every kind of person and
every kind of fruit.  Whenever a new kind of person or fruit is added
this function must be changed.  

It is far better to pass the fruit base class to the person and have
the person use RTTI to figure out if it is appropriate.  Why?  Because
the person already has a dependency on the fruit.  OrangeEaters
already have a dependency upon Orange.  Thus it harms nothing if they
dynamically cast a Fruit to an Orange.  No new dependency is added.