How is dynamic_cast implemented

Question

Consider this simple hierarchy:

class Base { public: virtual ~Base() { } };
class Derived : public Base { };

Trying to downcast Base* p to Derived* is possible using dynamic_cast<Derived*>(p). I used to think dynamic_cast works by comparing the vtable pointer in p to the one in a Derived object.

But what if we derive another class from Derived? We now have:

class Derived2 : public Derived { };

In this case:

Base* base = new Derived2;
Derived* derived = dynamic_cast<Derived*>(base);

We still get a successful downcast, even though the vtable pointer in Derived2 has nothing to do with a vtable pointer in Derived.

How does it actually work? How can the dynamic_cast know whether Derived2 was derived from Derived (what if Derived was declared in a different library)?

I am looking for specific details about how this actually works (preferably in GCC, but others are fine too). This question is not a duplicate of this question (which doesn't specify how it actually works).

Answer 1

How can the dynamic_cast know whether Derived2 was derived from Derived (what if Derived was declared in a different library)?

The answer to that is surprisingly simple: dynamic_cast can know this by keeping this knowledge around.

When the compiler generates code it keeps around the data about the class hierarchies in some sort of table that dynamic_cast can look up later. That table can be attached to the vtable pointer for easy lookup by the dynamic_cast implementation. The data neeeded for typeid for those classes can also be stored along with those.

If libraries are involved, this sort of thing usually requires these type information structures to be exposed in the libraries, just like with functions. It is possible, for example, to get a linker error that looks like "Undefined reference to 'vtable for XXX'" (and boy, are those annoying!), again, just like with functions.

Answer 2

Magic.

Just kidding. If you really want to research this in detail, the code that implements it for GCC is in libsupc++, a part of libstdc++.

https://github.com/mirrors/gcc/tree/master/libstdc%2B%2B-v3/libsupc%2B%2B

Specifically, look for all files with tinfo or type_info in their name.

Or read the description here, that's probably a lot more accessible:

https://itanium-cxx-abi.github.io/cxx-abi/abi.html#rtti

This details the format of the type information the compiler generates and should give you clues how the runtime support then finds the right casting path.

Answer 3

How can the dynamic_cast know whether Derived2 was derived from Derived (what if Derived was declared in a different library)?

The dynamic_cast itself does not know anything, its the compiler that knows those facts. A vtable does not necessarily contain only pointers to virtual functions.

Here's how I would (naively) do it: my vtable will contain pointer(s) to some type information (RTTI) used by dynamic_cast. The RTTI for a type will contain pointers to base classes, so I can go up the class hierarchy. Pseudocode for the cast would look like this:

Base* base = new Derived2; //base->vptr[RTTI_index] points to RTTI_of(Derived2)

//dynamic_cast<Derived*>(base):
RTTI* pRTTI = base->vptr[RTTI_index];
while (pRTTI && *pRTTI != RTTI_of(Derived))
{
  pRTTI = pRTTI->ParentRTTI;
}
if (pRTTI) return (Derived*)(base);
return NULL;