[cfe-dev] Handling inherited virtuals

Douglas Gregor dgregor at apple.com
Sun Feb 8 10:28:17 PST 2009


Hi Sebastian,

On Feb 8, 2009, at 9:01 AM, Sebastian Redl wrote:
> 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 :)

> 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



More information about the cfe-dev mailing list