vtable: Underlying algorithm

Question

My understanding of vtables is that, if I have a class Cat with a virtual function speak() with subclasses Lion and HouseCat, there is a vtable which maps speak() to the correct implementation for each Subclass. So a call

cat.speak()

Compiles to

cat.vtable[0]()

That is, a look-up in the vtable position 0 and a call of the function pointer in this position.

My question is: What happens on multiple inheritance?

Let's add a class Pet. Pet has virtual functions speak() and eat(). HouseCat extends Pet, while Lion does not. Now, I need to make sure that

pet.eat()

Compiles as

pet.vtable[1]()

That is vtable[0] needs to be speak(). Pet.eat needs to be slot 1. That is because cat.speak() needs to access slot 0 in the vtable, and if, for a HouseCat, slot 0 happens to be eat, this will go horribly wrong.

How does the compiler ensure that the vtable indexes fit together?

Rocket

The short answer is that the compiler ensures it because that's the compiler's job. That's what it is supposed to do. So it does it. The compiler creates separate vtables for the superclass when it is instantiated by itself, and when it is instantiated as part of the subclass, and assigns the appropriate vtable to the superclass instance, at instantiation time. – Reenareenforce

The even shorter answer is that vtables aren't specified and are implementation-dependent if present. For the gory details of at least one implementation see Stanley Lippman, Inside the C++ Object Model. – Mercola

If you want all the details there's a description of one way of doing it in the Itanium C++ ABI. – Overvalue

The object may contain more than one pointer to a vtable - indeed it will have one per base class with virtual functions. – Overvalue

If B derives from A, then B is-a A: it means every detail of A is reproduced in B, notably the vptr and vtable. Then if B derives from A1, A2, A3, then every detail of Ax is reproduced in B, so it will end up with (at least) as many vptr as the base subobjects. – Thyroid

As a follow up to the other comments, the fact that there can be more than one vptr means it is not necessarily the case that eat must be in position 1. Pet could have a vtable specifying {eat, speak} while Cat keeps a vtable specifying {speak}. – Castoff

@Castoff Most often, the order in the vtable follows the order in the class definition. – Thyroid

Answer 1

Nothing is set by the spec, but typically the compiler would generate one vtable for every immediate non-virtual base class, plus one vtable for the deriving class - and then the vtable for the first base class and the vtable for the derived class will be merged.

So more concretely, what the compiler generates when constructing the classes:

• Cat

  [vptr | Cat fields]
   [0]: speak()
  

• Pet

  [vptr | Pet fields]
   [0]: eat()
  

• Lion

  [vptr | Cat fields | Lion fields]
   [0]: speak()
  

• HouseCat

  [vptr | Cat fields | vptr | Pet fields | HouseCat fields]
   [0]: speak()        [0]: eat()
  

What the compiler generates on calls / casts (variable name is the static type name):

• cat.speak()
  • obj[0][0]() - valid for Cat, Lion and the "Cat" part of HouseCat
• pet.eat()
  • obj[0][0]() - valid for Pet and the "Pet" part of HouseCat
• lion.speak()
  • obj[0][0]() - valid for Lion
• houseCat.speak()
  • obj[0][0]() - valid for the "Cat" part of HouseCat
• houseCat.eat()
  • obj[Cat size][0]() - valid for the "Pet" part of HouseCat
• (Cat)houseCat
  • obj
• (Pet)houseCat
  • obj + Cat size

So I guess the key thing that confused you is that (1) multiple vtables are possible and (2) upcasts might actually return a different address.

More

"then the vtable for the first base class and the vtable for the derived class will be merged" the "first [non-virtual] base class" is usually called the primary base class – Thyroid