[cfe-dev] Handling inherited virtuals

[Sebastian Redl]

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().)

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?

Sebastian