[cfe-dev] Name lookup approach

[Douglas Gregor]

On Jan 8, 2009, at 6:17 AM, Zhongxing Xu wrote:
> Currently we have two mechanisms to do name lookup:  
> IdentifierResolver and DeclContext. In Sema::LookupDecl(), we  
> combine the two approaches to fulfil the name lookup task. I really  
> feel that the code in Sema::LookupDecl() logically uninituitive and  
> error prone. Could we use DeclContext exclusively to do name lookup  
> and eliminate the IdentifierResolver use?

Currently, no; the chains of declarations held in the  
IdentifierResolver contain information local declarations that are all  
in the same DeclContext. For example:

void f(int x) { // #1
   {
     int x; // #2
       {
         int x; // #3

        printf("%i", x); //  this 'x' refers to #3
       }
   }	
}

Here, the IdentifierResolver has a chain of declarations #3 -> #2 ->  
#1 for the name 'x'. However, all three 'x's live in the DeclContext  
associated with f's FunctionDecl.

Now, it is possible that we want compound statements to be  
DeclContexts, so that the 'x's would be be in different DeclContexts.  
That might be a good generalization (regardless of whether we use it  
for name lookup), because it would mean that more of the scope  
structure of the program is present in the ASTs after parsing. But,  
that gets to your comment below...

> I think that way could make name lookup logically more clear. My  
> only concern is if that could cause performance lost?


Yes, it would most certainly cause performance degradation if we used  
DeclContext for all name lookup. The beauty of IdentifierResolver is  
that the chain of declarations in scope for a particular name is  
attached to the IdentifierInfo for the name, so it's O(1) to find the  
first declaration with that name that's in scope. If we're using just  
DeclContexts, we'd have to walk the scope chain upward, checking  
DeclContext along the way (each check is either a search through a  
small array or a hash table lookup).

In fact, some of the optimization comments in LookupDecl (and other  
optimization ideas that have yet to be written down) involve trying to  
skip calls to DeclContext::lookup when we know that we would have  
found the answer on the IdentifierResolver chain if there were an  
answer.

So, I think the complexity of LookupDecl is inherent to solving the  
problem efficiently. It's also extremely important to performance:  
when compiling a C++ program that includes <iostream>, GCC spends 26%  
of its time in name lookup.

	- Doug