views:

174

answers:

3

First of all, I want to make myself clear that I do understand that there is no notion of vtables and vptrs in the C++ standard. However I think that virtually all implementations implement the virtual dispatch mechanism in pretty much the same way (correct me if I am wrong, but this isn't the main question). Also, I believe I know how virtual functions work, that is, I can always tell which function will be called, I just need the implementation details.

Suppose someone asked me the following:
"You have base class B with virtual functions v1, v2, v3 and derived class D:B which overrides functions v1 and v3 and adds a virtual function v4. Explain how virtual dispatch works".

I would answer like this:
For each class with virtual functions(in this case B and D) we have a separate array of pointers-to-functions called vtable.
The vtable for B would contain

&B::v1
&B::v2
&B::v3

The vtable for D would contain

&D::v1
&B::v2
&D::v3
&D::v4 

Now the class B contains a member pointer vptr. D naturally inherits it and therefore contains it too. In the constuctor and destructor of B B sets vptr to point to B's vtable. In the constructor and destructor of D D sets it to point to D's vtable.
Any call to a virtual function f on an object x of polymorphic class X is interpreted as a call to x.vptr[f's position in vtables]

The questions are:
1. Do I have any errors in the above description?
2. How does the compiler know f's position in vtable (in detail, please)
3. Does this mean that if a class has two bases then it has two vptrs? What is happening in this case? (try to describe in a similar manner as I did, in as much detail as possible)
4. What's happening in a diamond hierarchy with A on top B,C in the middle and D at the bottom? (A is a virtual base class of B and C)

Thanks in advance.

A: 

Comments:

  • I don't think destructors come into it!

  • A call such as e.g. D d; d.v1(); will probably not be implemented via the vtable, as the compiler can resolve the function address at compile/link-time.

  • The compiler knows f's position because it put it there!

  • Yes, a class with multiple base classes will typically have multiple vptrs (assuming virtual functions in each base class).

  • Scott Meyers' "Effective C++" books explain multiple inheritance and diamonds better than I can; I'd recommend reading them for this (and many other) reasons. Consider them essential reading!

Oli Charlesworth
@Oli: about the first point - they do, otherwise how do you explain that when in Base's destructor a virtual function f is called, Base::f is called and not Derived::f?
Armen Tsirunyan
He's right that destructors don't make virtual calls. In order to do this in a call from a call, it probably would replace the vtable as he described (with caveats that this is all implementation specific)
Lou Franco
@Armen: The same as a virtual call from inside any other member function of `Base`.
Oli Charlesworth
@Oli: I am afraid you are completely wrong. If you call a virtual function from any other base member, the derived's override may be called depending on the dynamic type of the object
Armen Tsirunyan
@Armen: I was not aware of that! (Although after a moment's thought, the reason is obvious.) But nevertheless, the explanation of this is surely pretty simple? The compiler can make this one exception, and resolve the address at compile-time.
Oli Charlesworth
@Oli: The compiler can do anything. My question is about what it *actually* does :)
Armen Tsirunyan
@Armen: Ok, well clearly it *actually* does this! If you want the precise details, just peruse some disassembler...
Oli Charlesworth
@Oli: Btw I have read Meyers, and consulted the relevant chapter before posting this, but he doesn't quite give the answer to my specific question
Armen Tsirunyan
@Armen: In "More Effective C++", item 24, he gives one possible implementation of vptrs for inheritance diamonds. There is no one definitive answer, because implementers will all do it slightly differently!
Oli Charlesworth
To whomever downvoted: could you tell me which part of my answer you object to?
Oli Charlesworth
@Armen: On *the derived's override may be called depending on the dynamic type of the object* In a hierarchy `base` <- `derived` <- `rederived`, with an object of type `rederived` after `~rederived` has completed, the *dynamic type* of the object is `derived`.
David Rodríguez - dribeas
+4  A: 
  1. Looks good to me
  2. Implementation specific, but most are just in source code order -- meaning the order they appear in the class -- starting with the base class, then adding on new virtual functions from the derived. As long as the compiler has a deterministic way of doing this, then anything it wants to do is fine. However, on Windows, to create COM compatible V-Tables, it has to be in source order

  3. (not sure)

  4. (guess) A diamond just means that you could have two copies of a base class B. Virtual inheritance will merge them into one instance. So if you set a member via D1, you can read it via D2. (with C derived from D1, D2, each of them derived from B). I believe that in both cases, the vtables would be identical, as the function pointers are the same -- the memory for data members is what is merged.
Lou Franco
Sorry, but I don't have definitive answers for 3 and 4. I think that there's a step to make sure you have the right vtable, but I don't know the details.
Lou Franco
@Lou: Thank you very much. Answer to point2 was especially valuable
Armen Tsirunyan
+12  A: 

1. Do I have any errors in the above description?

All good. :-)

2. How does the compiler know f's position in vtable

Each vendor will have their own way of doing this, but I always think of the vtable as map of the member function signature to memory offset. So the compiler just maintains this list.

3. Does this mean that if a class has two bases then it has two vptrs? What is happening in this case?

Typically, compilers compose a new vtable which consists of all the vtables of the virtual bases appended together in the order they were specified, along with the vtable pointer of the virtual base. They follow this with the vtable functions of the deriving class. This is extremely vendor-specific, but for class D : B1, B2, you typically see D._vptr[0] == B1._vptr.

multiple inheritance

That image is actually for composing the member fields of an object, but vtables can be composed by the compiler in the exact same way (as far as I understand it).

4. What's happening in a diamond hierarchy with A on top B,C in the middle and D at the bottom? (A is a virtual base class of B and C)

The short answer? Absolute hell. Did you virtually inherit both the bases? Just one of them? Neither of them? Ultimately, the same techniques of composing a vtable for the class are used, but how this is done varies way to wildly, since how it should be done is not at all set in stone. There is a decent explanation of solving the diamond-hierarchy problem here, but, like most of this, it is quite vendor-specific.

Travis Gockel
@Travis: Thanks for your answer. 1. I disagree with you on point one: No virtual dispatch is done from the destructor (the standard explicitly mentions this). 2. OK 3. Great. 4. I specifically mentioned that both B and C derived virtually from A. Thanks again for the answer, appreciate it.
Armen Tsirunyan
Ha! You're right. I never knew that.
Travis Gockel
+1 Overall, but the first point is wrong: the *vptr* is modified by the destructor. When each of the destructors in the hierarchy from the most derived type to the base completes, it updates the *vptr* in the inverse way as the constructors did. Your example is good, but the language will not protect you, it is undefined behavior. Many compilers will introduce a *pure virtual method thunk* that will printout an error message (*pure virtual method called*). Try it. The rationale on the decision of updating the pointer is that the *final overrider* for a method cannot be a destroyed object.
David Rodríguez - dribeas
@David: Since the example is deleted, I can't remember it in detail, but it shouldn't be undefined behavior. Correct be if I am wrong but the behavior is defined and it just calls the cleanup() of the base class.
Armen Tsirunyan
@Armen: The problem is that I had `cleanup` as a pure virtual function, which means there is no way to call it.
Travis Gockel
@David: If (as I've just learned) destructors don't make virtual calls, then why do they need to use the vptr at all, let alone modify it?
Oli Charlesworth
@David, @Travis: Oh, OK then :)
Armen Tsirunyan
@David: It's not? :) I assumed it was... I didn't say it was a quote. I just rephrased what I remembered in my words
Armen Tsirunyan
@Oli Charlesworth: again, can anyone produce a quote from the standard? I have not yet located a quote, but gcc and vs compilers do update the vptr after completing destruction, and calls are dynamically dispatched to the *final overrider*, which at each stage is the most implementation in the most derived, not yet destroyed object.
David Rodríguez - dribeas
@David: This is news to me. What would be rationale behind this?
Oli Charlesworth
@David: Suppose D:B and f is a virt funvtion called from both ~B and ~D and main function contains a single statement D d; MSVC prints D::~D D::f B::~B B::f ...
Armen Tsirunyan
@Armen: That behavior is so because the `vptr` gets updated after `~D` completes and before `~B` starts. Consider adding a `dispatch` method that calls `f()` (`void B::dispatch() { f(); }`) in `B`, and have `~B` call `dispatch`. Now, there is a single definition of `B::dispatch` and as such there is a single implementation. Because it can be called on an object that is alive it has to call `f` using the regular virtual dispatch mechanism. Now, if you run the test you will see the same effect as before: `B::f` is called when `dispatch` is called from the `B` destructor.
David Rodríguez - dribeas
@Armen: ... I guess I was wrong in my interpretation of §12.4/6, I have reread it a couple of times and I agree that it disables *virtual dispatch* when the constructor is running: *once the destructor starts then no virtual method will be dispatched to an object derived from this*, and that needs to be implemented in a vtable system by means of an update of the vptr after the destructor of the most derived object.
David Rodríguez - dribeas
@Oli Charlesworth: If the question is what is the rationale for updating the *vptr*, the answer is that methods that could potentially call virtual methods, and that at the same time can potentially be called from the destructor must not call a *more derived* class when they are called from the destructor (virtual dispatch will not go down to an already destructed object). To ensure this, the virtual dispatch mechanism must be updated after compleeting each destructor so that the vptrs point to the immediately less derived object.
David Rodríguez - dribeas
@David: I see. So it's not that dynamic dispatch doesn't occur, it's that it won't dispatch to a child override relative to the destructor that's currently in progress?
Oli Charlesworth
@Armen, @Oli: I have written a small snippet in [codepad](http://codepad.org/w9AzO5c0). It is my first post there, so if it does not work tell me and I will produce the code somewhere else.
David Rodríguez - dribeas
BTW with regards to point 2, you can have some fun (or pain) by playing around with the order of virtual functions in the header file; compile the implementation, re order something, compile the usage, link... kerboom. (The point being that most compilers are very brittle in that regards.)
BCS