[cfe-dev] Handling inherited virtuals

[Piotr Rak]

Hi Sebastian,

2009/2/8 Sebastian Redl <sebastian.redl at getdesigned.at>:
> Hi,
>
> Thinking about handling of virtual function overriding in C++, and how
> Clang should handle it.
>
> The issue: for every member function declaration, marked virtual or not,
> we have to determine if it overrides an inherited virtual function. If
> it does, it automatically becomes virtual. Also, if any inherited pure
> virtuals are not overridden, the class is abstract.
>
> This means there are two sub-problems.
> 1) Determine if any given function overrides an inherited virtual.
> 2) Determine if all inherited abstract virtuals have been overridden.
>
> Problem 1 simply comes down to looking up the function. We could use a
> naive search, we could try to piggyback on name lookup, or we can write
> a separate lookup structure for this.
> The problem with naive search is obvious. It's a linear search through
> *all* member functions of *all* directly and indirectly inherited classes.
> The problem with name lookup is that it is not really suited for this.
> For example:
>
> struct A { virtual void f(); };
> struct B : A { void f(int); /* doesn't override */ };
> struct C : B { void f(); /* overrides A::f() */ };
>
> However, the way name lookup works, it will only find B::f(int). Another
> problem is with two functions with identical signatures inherited from
> different classes; name lookup will complain about ambiguity, overriding
> simply overrides both.
> We can probably use local name lookup to accelerate searching through
> all bases, though. (Not sure. I've lost track of what name lookup can do.)
> The problem with a separate lookup structure is the additional overhead.
> But this brings me to the second problem.
>
> To determine if all pure functions have been overridden, we have to look
> at all the functions declared pure and check if they have been
> overridden. We can use a naive search, we can keep a list of the
> abstract functions each class has, and we can embed this information
> into the separate lookup structure from above.
> The issue is complicated by the rules with multiple and virtual
> inheritance. For example:
>
> struct A { virtual void f() = 0; }; // abstract
> struct B1 : A { void f(); }; // not abstract
> struct B2 : A {}; // abstract
> struct C1 : virtual A { void f(); }; // not abstract
> struct C2 : virtual A {}; // abstract
> struct D : B1, B2 {}; // abstract - doesn't override A::f() inherited via B2
> struct E : C1, C2 {}; // not abstract  - A::f() is overridden by C1.
>
> (To make things even more complicated, if B2 overrides f(), that's just
> fine, but if C2 overrides it, E is in error, because there are two equal
> overriders of A::f().)

And to make it even *more* complicated, consider role of
using-declarations here! :)

> Naive searching is pretty much a no-starter. We have to make a
> depth-first search through the entire inheritance hierarchy, collecting
> pure functions, and then check every class on the path back to see if it
> overrides these functions, so we can kick them out again, which means a
> lot of work checking if a function overrides another, which we already
> did above.
> Therefore we should probably keep a list of abstract functions for each
> class. Whether this should be part of another lookup structure is a
> different question.
>
> Comments? Ideas?

Yes, I think we need such structure, member lookup would be quite
expensive with out it.
It will more or less correspond v-table of class, if we will try to
avoid it here and do tricks with lookup (which would be slow), we will
need build it in Codegen, right?
If we will insist on saving space for classes without virtual
functions, (and base classes without virtual functions) we can add
artificial another artificial name and put it in DeclContext lookup
sturucture, as we did with using-directives.

This list could hold also members from base class by introduced
using-declarations, but I am not quite sure (they can also appear at
any DeclScope with slightly different semantic).

We we also have to keep track of C++0x deleted/(defaulted?) members someday...

Piotr