C++ Objects Part 5: Virtual Base Classes

A virtual base class is a class that is included only once in your derived class no matter how many base classes refer to it. How does this happen?

The answer is two-fold:

First, the actual layout of a class with a virtual base depends on the full class. Consider this case:

class R { };
class B1 : public virtual R { };
class B2 : public virtual R { };
class D : public B1, public B2 { };

In this case R is a virtual base that is included twice in D. The location of R will be different for B1, B2 and D. Each time one of these classes is set up, R is placed in the class once. Since R cannot be in D twice, clearly the location of R relative to B1 and B2 can't be the same when B1 or B2 is the final class vs. D. (If both B1 and B2 took R with them, we'd have two copies in D, which is not acceptable!)

To get around this, we hit the second part of our answer: classes contain pointers to their virtual bases. With non-virtual containment, bases are contained, e.g. a fixed chunk of the derived class's memory is used for the base class. With a virtual base, the derived class simply contains a pointer to the base class. This lets us move R around and adjust the pointer to R (in B1 or B2) at runtime in a way that lets us use different memory layouts for R with various classes that contain B1 or B2.

It should be noted that in D while there is only one copy of R, there are multiple pointers to R - one in B1 and one in B2. This is what assures that the memory layout of B1 and B2 don't change when they are used in a derived class. Only the contents of the layout of B1 and B2 change. The compiler generates code to set up these pointers for us.

For CodeWarrior, pointers to virtual bases come before the pointer to the vtable. This means that to find the vtable we have to know how many virtual bases a class has. Fortunately this information is dependent only on class info that is available at compile time - it never changes.

Here's a C version of what we have above:

struct R {
R_vtable * vtbl;
// R data
};

struct B1_partial {
R * vbase;
B1_vtable * vtbl;
// data for B1
};

struct B1_final {
B1_partial self;
R vbase;
};

struct B2_partial {
R * base;
B2_vtable * vtbl;
// data for B2
};

strut B2_final {
B2_partial self;
R vbase;
};

struct D {
R * vbase;
R vbase_data;
B1_partial base1;
B2_partial base2;
};

One of the interesting things to note here is that B1 and B2 as included in D are not as large as B1 and B2 when used by themselves. This is because B1 and B2 must have storage for the virtual base R at their end when used by themselves. But when used in D, that storage is provided by D.

Now we can see why dynamic cast first goes to the most derived base. Given a ptr to R we have no
idea where the rest of the object is -- position of R varies with the actual final type - that is, the relative position of R in the object is not the same relative to B1 if the real object is B1 or D.

Fortunately the vtable of any object tells us where the final object's real start is. So when R is a virtual base, depending on its final type, it will refer to a vtable that takes into account the actual full class's layout, letting us recover the full type and figure out the true relationship between the virtual base and the whole object.

Note that a static down-cast from a virtual base will cause a compiler error. This is the compiler telling us that it can't even speculate what the memory layout of the virtual base in the final class might be without inspecting the real type at runtime. But dynamic down-casts and even cross-casts are legal, since all dynmic casts are a maximum down cast followed by a possible up-cast.

C++ Objects Part 4: typeid and casts

Now that we have described how multiple inheritance in CodeWarrior C++ works, we can look at how casting and type works in C++. We needed to discuss multiple inheritance first; recall from part 2 that for single inheritance, the "front" of an object in memory is its base. With this system, no work is needed at all to cast when we have only one base class.

For the purpose of this discussion, "full class" means the actual class of an object when it is instantiated - in other-words, the "biggest" downcast we can apply - it's real class.

Please also remember from our previous post that an object that inherits from two base classes has at least two vtables with different layouts. Clearly a pointer to a vtable is not a unique identifier of an object's class, if one object can have two different vtable pointers of different values.

So instead CodeWarrior creates a separate static structure for each class that uniquely identifies it: a type_info structure. This shouldn't be surprising - this is the same structure that you can use with the typeid operator. That is if you do this:

D obj;
const std::type_info& t = (typeid(obj));

"t" is a pointer to the internal type_info structure for class D that is used by the runtime for all operations that require typing. (t is a pointer - it looks like a reference in the C++ code, but in truth they are one and the same to the compiler.)

Every vtable starts with a pointer to a type_info structure, identifying the full type of an object. When an object has two vtables (as in our multiple inheritance case), both vtables point to the same type_info structure. No two classes will ever share a vtable (even if a derived class never overrides any member functions) so this is okay. Because both vtables point to the same type_info, we can get our full runtime class for an object no matter which base we have a pointer to.

Static Casts

With this in mind, let's look at static casts. A static cast is a cast between C++ class types whose effects are fully known at compile time. That is, the compiler uses compile-time type information to change the type (and possibly the pointer value) for an object. The compiler looks at the layout in memory of the base class and the derived class and adjusts the pointer as much as is needed. (When we have only one base class, a static cast will not need to adjust the pointer at all, because the base class is always first in memory.)

There are some casts that cannot be performed statically at all, but we will get to this later. Also, we can't check whether the cast is safe at compile time. If we have a pointer to X that we cast to type Y but the object is not actually of type Y, the compiler will not care and we may crash later.

Full Class and Offsets

When we first introduced the layout of a vtable we mentioned that there is an "offset" right after the type_info. But what is this offset?

The offset in a vtable is the number of bytes that a pointer to an object whose type uses this vtable must be adjusted to find the full class of the object.

So in our case where we have two bases, each embedded somewhere in a class, the vtable of each base contains the offset to recover the full object. Note that one vtable will probably have an offset of 0, and this vtable is the one we will use for the "full" class, so that we never adjust the pointer when we already have the full class.

(As far as I can tell, CodeWarrior layers all static vtables for a class consecutively, so when given a pointer to the first one, it can actually generate calls into any vtable, because their relative positioning is fixed.)

Dynamic Casts

A dynamic cast converts the type of an object using run-time information. The cast returns NULL if the object can't be viewed as a given type. Since dynamic casts look at the object at run-time and can see the full class of the object, they can perform casts that we can't do using only compile-time information.

(Consider a DLL that returns an object of some unknown type, but as a pointer to a base type. Without run-time type information, the compiler has no idea what real type that object is, because it doesn't have the source code. In practice even if we did have the code, the compiler can't track that object's pointers through all of the strange things C++ can do to memory.)

A dynamic cast works by examining the type_info structures of an object and using that information to perform the cast. So to understand dynamic casts, we'll need to look a the type_info structure.

The type_info structure contains a pointer to a static string that names the class - all dynamic casts will use class string-name comparisons to find equivalent type. It then contains a pointer to a "null-terminated" variable-length array of info about base classes. Each item in this array contains a pointer to the type_info of a base class (if this pointer is null, that indicates null termination) and an offset indicating how much the pointer to the full object must be adjusted to cast to this type.

It should be noted that this list of base classes contains all bases, not just immediate bases! In other words, if we have a class Z that derives from Y and Y derives from X, the array of base classes for Z contains X and Y! This means that with a single linear search of the list, we can find any possible base. We do not have to search the entire tree.

(As a side note, each type_info's array contains pointers to parents, so you can follow the chain of inheritance from type_info to type_info. As far as I can tell in CodeWarrior there is no recording of which bases are "immediate bases", as you never need this info in C++. Perhaps the order of the bases in the list would tell us but I am not sure.)

Dynamic cast is therefore a two-step process:

1. Given the vtable of a pointer to an object, use the offset to recover a pointer to the full class. (All adjustments will then be made from this pointer.) This is the equivalent of down-casting to the full class.

2. Search the type_info of the full class for the type we want - in other words, go through a list of all bases. If we find one, use the offset to adjust the pointer again. If the search in step 2 fails, return NULL.

(I am leaving out ambiguous base classes - we'll cover that later!)

C++ Objects Part 3: Multiple Inheritance

In my previous post I described how single inheritance works with the CodeWarrior C++ compiler - by placing the superclass as the first item in the subclass in memory (and pulling the same trick for the vtable). Now to something more complicated: multiple inheritance!

One thing is clear: we can't do the same trick for multiple inheritance as we can for single inheritance...only one superclass can be first!

The trick: change the pointer when we change the "class" of the pointer. We simply stick both bases into our subclass, but if we cast from the superclass to the second base, we move the pointer in memory to point to the second base class (since it isn't at the same address).

You can see this for yourself with a program like this:
class a { int a_; };
class b { int b_; };
class c : public a, public b { };
int main()
{
c obj;
printf("a=0x%08x, b=0x%08x, c=0x%08x\n", (a*)&obj,(b*)&obj,(c*)&obj);
}

When we print out a ptr to our object casted, we get this
a=0xbffff460, b=0xbffff464, c=0xbffff460

Note that when we cast to b, the address of our pointer moves in memory! This is because c contains a first in memory, then b second.

So we've at least solved the problem for object data: we'll put the base classes into the derived class sequentially and adjust the pointer any time we change the type, so that we point to the base WITHIN the derived class no matter where it is. This meets our rule that a pointer to the base must look like the base. It does because we move the pointer until it does.

Now let's apply the rule to vtables. We must have a pointer to a vtable as the first item in an object. So if the pointer to an object can point to either of two memory locations (the start of the first or second base) then we can't escape logic: we need TWO pointers to vtables!

The format of a vtable depends on the class we think we have; the contents of a vtable depend on the class we really have. So when we have multiple inheritance, we will have multiple vtables, so that each one can be formatted based on the base class (but filled with function pointers from the derived classes.

This example will get lengthy, so I will abridge it a little bit...

class B1 { virtual void b1(); };
class B2 { virtual void b2(); };
class D : public B1, public B2 { virtual void b1(),virtual void b2(),virtual void d(); } ;

In C we might have this:

struct B1_vtable {
typeid * type_id_ptr;
int offset;
// ptrs to B1 virt funcs
};
struct B2_vtable {
typeid * type_id_ptr;
int offset;
// ptrs to B2 virt funcs
};
struct D_vtable {
B1_vtable parent1;
B2_vtable parent2;
// ptrs to D vfuncs
};

Because D contains the first base's virtual function table first, the "header" information (type-id and offset) for the first base are used for the derived class. This will be important later. Because all of the virtual functions are consecutive in memory, when we have the derived class we can easily find any virtual method's function pointer.

(So when I say we have two vtables really we have one big vtable with two vtables embedded inside it.)

void B1_b1() {}
void B2_b2() {}
void D_b1() {}
void D_b2() {}
void D_d() {}

static type_id B1_type_id = { ... };
static type_id B2_type_id = { ... };
static type_id D_type_id = { ... };

// Virtual functions for B1:
static D_vtable sB1_vtable = { &B1_type_id, 0, B1_b1 };
// Virtual functions for B2:
static B2_vtable sB2_vtable = { &B2_type_id, 0, B2_b2 };

So far there are no surprises here, until we look at the virtual function tables for D:

// Virtual functions for D
static D_vtable sD_vtable = { { &D_type_id,0, D_b1 }, { &D_type_id, -sizeof(B1), D_b2 }, D_d };

Here we have a vtable that contains two vtables within it. Thus we have two pointers to our type-IDs. If we have a pointer to the second one, it looks like the vtable used when looking at our object of type D as if it was a B2. Remember that the pointer to the object changes as we cast, and that controls which vtables is used. (Whenever we call the virtual method b2(), we have a pointer to a B2* and therefore our object pointer is adjusted to the second vtable where we get a D_b2 object.

This is the first time the 'offset' parameter of the vtable isn't 0. I'll explain this in the next post, but for now trust that, since B2 is not the first parent class inside D, it needs a non-zero offset.

struct B1 {
B1_vtable * vtable;
// data for b2
};

struct B2 {
B2_vtable * vtable;
// data for b2
};

struct D {
B1 base1; // base1.vtable inited to &sD_vtable.parent1
B2 base2; // base2.vtable inited to &sD_vtable.parent2
// derived data for D
}

When D is initialized, the vtable for B1 is inited to one value and the vtable for B2 is inited to another value.

C++ Objects Part 2: Single Inheritance

In my previous article I described the basic layout of a C++ object in Metrowerks CodeWarrior, with a pointer in the object to a static table of function pointers and a class description structure. Now we can look at how single inheritance is implemented.

Simple inheritance is, well, simple: the derived class simply contains the first class at the beginning and new data later in memory. The same thing is true for the vtable - new entries are tacked on the end.

(Please note that this is not true for virtual base classes - I'll get to that later.)

This meets our rule: a pointer to X must be laid out the same. Since derived class Y contains X at its beginning, the first bytes of Y look like an X.

Here's subclassing from the last post...

class bar : public foo {
virtual void b(float); // ovrrride
virtual void new_method(int);
char * new_member;
};

virtual base class - only one copy of the base no matter how we derive. How?

struct bar_vtable {
foo_vtable parent;
void (* new_method_func)(int);
};

void bar_b(float);
void bar_new_method(int);

static type_id bar_type_id = { ... };
static bar_vtable sbar_vtable = { &bar_type_id, 0, foo_a, bar_b, bar_new_method };

struct bar {
foo parent; /* superclass goes first. */
char * new_member; /* then new members. */
};

Note that a new vtable is made for the derived class, which may contain a mix of functions - here we have the "a" virtual function from the superclass, an overridden "b" function (bar_b, an override, goes into a slot in foo's vtable), and then a new virtual function in the end.

In fact, bar_b in a slot in a foo_vtable is where the "magic" of overrides happen. This is what lets us call a method from a foo * and get a method from a bar object. Because an object points to its classes vtable, we get that class's behavior.

C++ Objects Part 1: Basic Object Memory Layout

I spent a few minutes dissecting the C++ internal runtime structure for objects within Metrowerks CodeWarrior. There's some internal guts that C++ generates when you make objects; the format is not standardized between compilers, but looking at one implementation reveals some of the costs and implications of C++ objects and inheritance.

C++ breaks objects with methods down into data structures and functions, with function pointers used for virtual functions. Polymorphism depends on our ability to apply fixed unchanging code to diverse data structures and get meaningful execution. Therefore we can immediately postulate one rule that applies to all objects, no matter what C++ feature is used (inheritance, multiple inheritance, virtual base classes, etc): the in-memory layout of a pointer to class X must have a fixed layout no matter what real derived type the object has.

I'm only going to describe the case where objects have virtual functions and run-time type information. Based on the actual code and compiler settings, the compiler may sometimes eliminate these features, changing the in-memory structure, but that's a topic for another blog entry.

CodeWarrior (like virtually all C++ compilers, no pun intended) implements virtual methods via virtual function tables (vtables), which are static structures containing one function pointer for each virtual function. An object has a pointer to its class's vtable before any other object data; there is only one copy of the vtable per class - it's immutable and shared. (This makes objects smaller than having pointers to each virtual function in the actual object.)

The virtual function table actually contains two more entries before the function pointers: a pointer to a "type ID" structure, a separate structure that describes the class itself, and a memory offset whose use we'll look at later. So if we have this C++ code:

class foo {
virtual void a(int);
virtual void b(float);
int c;
float d;
};

The equivalent C code would look something like this:

struct foo_vtable {
typeid * type_id_ptr;
int offset;
void (* ptr_to_a)(int);
void (* ptr_to_b)(float);
};

void foo_a(int) { }
void foo_b(float) { }

static type_id foo_type_id = { ... };
static foo_vtable sfoo_vtable = { &foo_type_id, 0, foo_a, foo_b };

struct foo {
foo_vtable * vtable; // gets inited to &sfoo_vtable
int c;
float d;
};

Class type is stored separately - first ptr in the v-table. Motivation for this will be clear later.
Vtable has an offset - also understood later.

Virtual Base Class - Not Needed for Interfaces

I was going to argue that virtual base classes are logical for interfaces, because we really only need each interface once. E.g.:

class IDeletable {
public:
virtual void delete()=0;
};

class IDrawable : public virtual IDeletable {
public:
virtual void Draw()=0;
};

class ISerializable : public virtual IDeletable {
public:
virtual void Serialize()=0;
};

void PersistentDrawing : public virtual IDrawable, public virtual ISerializable {
};

Turns out we don't need to virtualize the base classes. Virtualizing the base class is used when we have multiple copies of the base class inherited from different objects and we don't want actual copies of the base class.

But Don Box points out in "Essential COM" that this isn't necessary. In particular because the interfaces are truly empty - only a virtual function table, there is no harm in having multiple copies of them in an object. The virtual functions will be overriden correctly even if that base is represented multiple times. (The memory layout for this is moderately surprising, but I'll comment on this some other time.)

Inherit the Wind

Usually I post here after concluding something, usually after a discussion. But this post is the part that comes first - groping with the underlying issues.

Unfortunately a number of my software engineering books are temporarily inaccessible. We packed our (unsorted) library when we moved a few months ago, and because we are redoing a large chunk of the house, everything is still in boxes. As if having to search linearly for any book wasn't demoralizing enough to a programmer, some of the boxes are on top of each other, making whole ranges very difficult to get to. My spirit is broken by O(N).

Anyway, the issue is: given a series of interfaces to a conceptual hierarchy and an implementation hierarchy, how do you implement this in C++? The following gets very ugly very fast:

class IPoint {
virtual Point2 Get()=0;
};
class IBezierPoint : public IPoint {
virtual Vector2 GetCtl()=0;
};

class WED_Point : public IPoint {
virtual Point2 Get()=0;
Point2 internal_pt;
};

If you've done this kind of design before, you can see how we're about to go straight off the clifff...

class WED_BezierPoint : public, um, um.

The problem is that if I inherit from my base implementation (WED_Point) and my full supported interface (IBezierPoint) I pick up two instances of the interface IPoint. This will not make C++ happy and is almost surely not what we want. (The result will be a bunch of "method not overridden" warnings and probably a lot of incorrect polymorphic behavior.)

There are only three ways to solve this in C++ and they all suck in different ways:

1. Don't inherit implementation. This is what I would tell anyone else - inheriting implementation is evil, bla bla bla. In otherwords, WED_BezierPoint derives only from IBezierPoint and reimplements storage for its base point. Because WED_BezierPoint supports the IPoint interface (by way of IBezierPoint) clients still get the appearance of polymorphism via the interface, which is what we really care about.

The only problem with this is that we end up recoding a lot of implementation. Inheritence of implementation is almost always a lousy idea, but in this case I can't help but think that it's giving us something similar to database normalization. Still, one could definitely argue that all algoirthm code should be working with IBezierPoint or IPoint and thus the repeat-implementation is really a non-issue. So breaking the implementation hierarchy might be the least-skanky thing to do.

1a. It should be noted that we can make an implementation hierarchy and contain it in classes derived from the interfaces but not each other. This is a "bridge" pattern and will get us out of trouble in a lot of different design cases.

2. Don't inherit interface. In otherwords, IBezierPoint doesn't derive from IPoint. This solves the problem, but with a rather weird result: IBezierPoints might not be points at all.

You can argue that since these interfaces are meant to be run-time cast and checked anyway, that this is okay, but I think we lose something here. It would be nice to require that all bezier points be points - that is what we mean, so having the compiler require it is nice. I'd have to catagorize this fix as skanky.

(It should be noted that having independent interfaces is a good thing a lot of the time. Just maybe not when a very clear IS-A relationship exists.)

3. Make the interfaces virtual base classes. Do two C++ wrongs make a right? Probably not, but for the sake of argument, if all interfaces are virtual base classes then we can have the IPoint interface from two places at once.

One warning about this: if you make your interfaces virtual you need to subclass from them virtually in two places - both when one interface is derived from another and when a base implementation class derives from an interface. (The implementation derivation can be non-virtual - as long as all but one relationship is virtual, C++ will figure out what we mean, at least in CodeWarrior where I tested this.)

I suppose it should be noted that, as gross as using virtual base classes is, if you derive your C++ interfaces from some kind of common casting base (read: IUnknown) it has to be a virtual base class anyway.

Prototypes - Your Annoying Friend

Depending on your C++ compiler, when you start a project, C++ may require a prototype declaration for functions or not.

You really want prototypes! Here's why:

According to some byzantine aspect of C/C++, if you use a function that isn't defined and you don't have C++ requiring prototypes, then C++ will assume that the function (a) exists and (b) takes arguments that are exactly like what you are passing!

Now if the function doens't exist, you don't need prototypes to help you - you'll get a link error later on saying "we never found this function". Prototypes are better because it doesn't take a full compile to find out.

But where things really get ugly is if the function does exist, but the calling conventions you passed in assume an implicit conversion. For example, imagine if your function goes like this:

void some_happy_func(float n);

Now you call it like this:

some_happy_func(2.0);

Without prototypes, this probably will cause a lot of pain. Why? Well, 2.0 is a double-precision argument! If some_happy_func's prototype exists, the compiler will create an implicit conversion. But if it doesn't, the compiler will assume some_happy_func takes doubles, and generate an incorrect stack (with a double on it). When some_happy_func actually runs, it will interpret the low 32 bits of that double as a float and all hell will break loose.

In my experience, when prototypes reuqirements are off it's really easy to lose track of whether you've included a needed header or not, causing possibly subtle bugs where functions fail sometimes based on the calling code's headers. If the failure causes a hard-to-detect bug it can take a while to unravel this.