Your question is interesting, however I fear that you are aiming too big as a first question, so I will answer in several steps, if you don't mind :)
Disclaimer: I am no compiler writer, and though I have certainly studied the subject, my word should be taken with caution. There will me inaccuracies. And I am not that well versed in RTTI. Also, since this is not standard, what I describe are possibilities.
1. How to implement inheritance ?
Note: I will leave out alignment issues, they just mean that some padding could be included between the blocks
Let's leave it out virtual methods, for now, and concentrate on how inheritance is implemented, down below.
The truth is that inheritance and composition share a lot:
struct B { int t; int u; };
struct C { B b; int v; int w; };
struct D: B { int v; int w; };
Are going to look like:
B:
+-----+-----+
| t | u |
+-----+-----+
C:
+-----+-----+-----+-----+
| B | v | w |
+-----+-----+-----+-----+
D:
+-----+-----+-----+-----+
| B | v | w |
+-----+-----+-----+-----+
Shocking isn't it :) ?
This means, however, than multiple inheritance is quite simple to figure out:
struct A { int r; int s; };
struct M: A, B { int v; int w; };
M:
+-----+-----+-----+-----+-----+-----+
| A | B | v | w |
+-----+-----+-----+-----+-----+-----+
Using these diagrams, let's see what happens when casting a derived pointer to a base pointer:
M* pm = new M();
A* pa = pm; // points to the A subpart of M
B* pb = pm; // points to the B subpart of M
Using our previous diagram:
M:
+-----+-----+-----+-----+-----+-----+
| A | B | v | w |
+-----+-----+-----+-----+-----+-----+
^ ^
pm pb
pa
The fact that the address of pb is slightly different from that of pm is handled through pointer arithmetic automatically for you by the compiler.
2. How to implement virtual inheritance ?
Virtual inheritance is tricky: you need to ensure that a single V (for virtual) object will be shared by all the other subobjects. Let's define a simple diamond inheritance.
struct V { int t; };
struct B: virtual V { int u; };
struct C: virtual V { int v; };
struct D: B, C { int w; };
I'll leave out the representation, and concentrate on ensuring that in a D object, both the B and C subparts share the same subobject. How can it be done ?
- Remember that a class size should be constant
- Remember that when designed, neither B nor C can foresee whether they will be used together or not
The solution that has been found is therefore simple: B and C only reserve space for a pointer to V, and:
- if you build a stand-alone
B, the constructor will allocate a V on the heap, which will be handled automatically
- if you build
B as part of a D, the B subpart will expect the D constructor to pass the pointer to the location of V
And idem for C, obviously.
In D, an optimization allow the constructor to reserve space for V right in the object, because D does not inherit virtually from either B or C, giving the diagram you have shown (though we don't have yet virtual methods).
B: (and C is similar)
+-----+-----+
| V* | u |
+-----+-----+
D:
+-----+-----+-----+-----+-----+-----+
| B | C | w | A |
+-----+-----+-----+-----+-----+-----+
Remark now that casting from B to A is slightly trickier than simple pointer arithmetic: you need follow the pointer in B rather than simple pointer arithmetic.
There is a worse case though, up-casting. If I give you a pointer to A how do you know how to get back to B ?
In this case, the magic is performed by dynamic_cast, but this require some support (ie, information) stored somewhere. This is the so called RTTI (Run-Time Type Information). dynamic_cast will first determine that A is part of a D through some magic, then query D's runtime information to know where within D the B subobject is stored.
If we were in case where there is no B subobject, it would either return 0 (pointer form) or throw a bad_cast exception (reference form).
3. How to implement virtual methods ?
In general virtual methods are implemented through a v-table (ie, a table of pointer to functions) per class, and v-ptr to this table per-object. This is not the sole possible implementation, and it has been demonstrated that others could be faster, however it is both simple and with a predictable overhead (both in term of memory and dispatch speed).
If we take a simple base class object, with a virtual method:
struct B { virtual foo(); };
For the computer, there is no such things as member methods, so in fact you have:
struct B { VTable* vptr; };
void Bfoo(B* b);
struct BVTable { RTTI* rtti; void (*foo)(B*); };
When you derive from B:
struct D: B { virtual foo(); virtual bar(); };
You now have two virtual methods, one overrides B::foo, the other is brand new. The computer representation is akin to:
struct D { VTable* vptr; }; // single table, even for two methods
void Dfoo(D* d); void Dbar(D* d);
struct DVTable { RTTI* rtti; void (*foo)(D*); void (*foo)(B*); };
Note how BVTable and DVTable are so similar (since we put foo before bar) ? It's important!
D* d = /**/;
B* b = d; // noop, no needfor arithmetic
b->foo();
Let's translate the call to foo in machine language (somewhat):
// 1. get the vptr
void* vptr = b; // noop, it's stored at the first byte of B
// 2. get the pointer to foo function
void (*foo)(B*) = vptr[1]; // 0 is for RTTI
// 3. apply foo
(*foo)(b);
Those vptrs are initialized by the constructors of the objects, when executing the constructor of D, here is what happened:
D::D() calls B::B() first and foremost, to initiliaze its subpartsB::B() initialize vptr to point to its vtable, then returnsD::D() initialize vptr to point to its vtable, overriding B's
Therefore, vptr here pointed to D's vtable, and thus the foo applied was D's. For B it was completely transparent.
Here B and D share the same vptr!
4. Virtual tables in multi-inheritance
Unfortunately this sharing is not always possible.
First, as we have seen, in the case of virtual inheritance, the "shared" item is positionned oddly in the final complete object. It therefore has its own vptr. That's 1.
Second, in case of multi-inheritance, the first base is aligned with the complete object, but the second base cannot be (they both need space for their data), therefore it cannot share its vptr. That's 2.
Third, the first base is aligned with the complete object, thus offering us the same layout that in the case of simple inheritance (the same optimization opportunity). That's 3.
Quite simple, no ?
Ais handled very specially in such a case. – Dextrogcc/cp/class.cfunctionsbuild_primary_vtable()andbuild_secondary_vtable()all the optimizations dangle from there. – Redeeming