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?

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.