Handling inherited virtuals

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

Hi Sebastian,

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.

Interestingly enough, this is the same kind of lookup that we need for conversion functions, because we need to gather *all* of the conversion functions in all base classes (regardless of type), and conversion functions declared in derived classes hide conversion functions with the same signature in base classes. We should be able to handle both with the same data structure and lookup routines.

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

Local name lookup won't help with searching base classes, unfortunately. It's only really good for determining what entities have the name N within a given class.

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.

That seems like the best approach.. keep track of all of the virtual functions within this data structure, which supports searching (is there a virtual function with this signature that I'll be overriding?) and iteration (are any of the virtual functions still pure?).

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

Fun!

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.

This seems entirely reasonable to me. I'm also hoping it can be the same data structure we use for conversion functions :slight_smile:

Whether this should be part of another lookup structure is a
different question.

I think the answer is "no". This is a separable, C++-class-specific data structure that probably won't tie in very well with the existing lookup structures.

  - Doug

Hi Sebastian,

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! :slight_smile:

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

In the "common" non-multiple inheritance case, you could just keep a count of the number of abstract functions you have in a class. If a class is singly derived from it, each abstract method it defines just decrements the count, and any new abstract functions it adds increments the count.

This doesn't help you in the MI case, but hey it might help :slight_smile:

-Chris

Hi Sebastian,

2009/2/8 Sebastian Redl <sebastian.redl@getdesigned.at>:

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?

CodeGen will do something like this, yes, but it’s likely that it will need to walk the list of non-static member functions linearly anyway to perform vtable layout. Besides, from a performance perspective, we have to do vtable layout far fewer times than we need to check “does this override a virtual?”.

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…

Deleted functions are very, very easy; it’s just a bit that we check before actually using a function name (after overload resolution).

Defaulted members will take a little more work, but right now that work mostly involves actually synthesizing the implicitly-defined members when we need them. Currently, we just pretend that they exist :slight_smile:

  • Doug