[cfe-dev] [Patch] AST support, and unqualified name lookup for using-directives

[Piotr Rak]

Hi Dough,

2009/1/31 Douglas Gregor <dgregor at apple.com>:
>
> On Jan 30, 2009, at 7:53 PM, Piotr Rak wrote:
>>
>> I have played bit more with using-directives. Attached adds AST
>> support for using-directives (no serialization still), and makes
>> Sema::LookupName look ugly:) I may split it into two separated
>> patches(AST and lookup), if it is needed.
>
> This is a big undertaking; thank you!
>
> I'll do a detailed review later, but one thing in particular caught me eye:
> that sort_heap in CppLookupName is really going to hurt performance. Could
> you give me a short description of why we need it? (Or should I just wait
> until I do that detailed review to get the big picture?)
>

For each Scope (namespace/translation-unit), we need to consider all
using-directives
 which have common ancestor (of nominated namespace, and context
containing using-directive).
I see few ways to solve it:
 - sort by common ancestor, use binary search to find range (we do
that now, we can check other sort algorithms, qsort might be bad,
since memory allocation often creates increasing addresses)
 - use multiset/hashset
 - use linear search (gcc does that)

Which is faster for real code? I don't know, have not messured it
honestly, I tend to belive it will be bit faster than gcc for larger
number of using-directives, or similar..., for small number we lose
now for sure.
I would like to play with it, and tweak it at later point, but I don't
think microbenchmarks are way to go. Moreover, I consider caching this
sorted list in Scope structure (probably not updating online, just
invalidating), then it will always be a win over gcc in terms of time.

There is still other issue, hurting lookup, not addressed by this
patch too, ie. looking in same DeclContext many times.

>> I would also want to also ask, if there is any master plan how to get
>> rid of OverloadedFunctionDecl yet, or anyone actively working on it
>> now?
>
> The master plan is for LookupResult to provide an easy way to iterate over
> the set of overloaded functions that it found, which means providing a
> LookupResult::iterator that understands how LookupResult stores overloaded
> functions (as a pair of iterators into a DeclContext or into an
> IdentifierResolver chain). If it would help with using-directives, I could
> implement LookupResult::iterator relatively soon.

It is not essential now, but at later point I could avoid few
allocations! while merging multiple OverloadedFunctionDecls (now I
reuse first found OverloadedFunctionDecl, and free other).

> Right now, OverloadedFunctionDecl is only created "on demand" by
> LookupResult when the caller requests a Decl*. Callers should be migrated to
> look at the kind of LookupResult they receive from Lookup*Name, so that they
> can handle both ambiguities and overloaded functions. This change can happen
> gradually, and at some point none of the callers will need
> OverloadedFunctionDecl. I haven't been actively working on doing this, but
> for the most part it also isn't hard. The trickiest part is deciding what to
> do with DeclRefExpr's that refer to overloaded functions.

Access to stored FunctionDecls avoiding allocation of
OverloadedFunctionDecl would improve performance in same cases, but
that would be not be big change.

>
>        - Doug
>

Piotr