[cfe-dev] Qualified and unqualified name lookup and IdResolver

[Douglas Gregor]

Hi Argiris!

On Dec 4, 2008, at 7:58 PM, Argiris Kirtzidis wrote:
> I like the idea, for unqualified lookup, of declaration chains based  
> on lexical scope plus fall back to qualified lookup.

> But for qualified lookup, did you consider using the "array 
> +hashtable efficient data structure" not for answering "does N  
> contain x ?" (#1) but for answering "is x contained in N ?" (#2) ?
> (I mean an identifier having that data structure for storing the  
> DeclContexts where it appears).
> Both cases may have to deal with large number of declarations; #1  
> may deal with namespaces with lots of decls, while #2 may deal with  
> decls contained in lots of namespaces.
> The difference is that #1 optimizes for namespaces with few  
> declarations while #2 optimizes for "differently named" declarations  
> which is more common.
> Also, #2 will immediately answer for not-declared-before  
> identifiers, without requiring any lookup.

I did think about #2, but I don't think it's the right architecture  
and I think there are more performance issues lurking, particularly in  
the case where we are instantiating many templates that all contain  
members with the same names.

On the architecture side: the problem with having a data structure  
hanging off the identifiers is that the data structure has global  
knowledge: it needs to know about every "x" in every context. That  
makes it hard to build up the data structure in any way other than  
directly parsing the translation unit. For example, a module system  
that supports lazy deserialization might be careful to only record  
that the identifier "std" exists in the global namespace. When someone  
writes "std::vector", qualified lookup into std forces "std" to be  
populated by loading its declarations (but not the declarations they  
contain). It would be quite easy to implement this with #1, since  
DeclContext can be taught to deserialize when something performs a  
lookup() on it. Perhaps we could do something similar with #2, but it  
seems less obvious to me.

But, much of my bias comes from the fact that I find #1 to be far  
easier to reason about.

Overall, I think the decision between #1 and #2 would actually have a  
very small impact on the compiler. Most of the work in my patch is in  
making the declaration chains contain only identifiers in our lexical  
scope, and the "perform qualified lookup of name 'x' in scope 'y'"  
part is relatively separate. If you do want to go try implementing #2,  
make sure you use DeclContext::getPrimaryContext before trying to  
match the context of a declaration, because in

   namespace N {
	int x;
   }
   namespace N {
	int y;
   }

N::x and N::y have different DeclContexts (but they have the same  
primary DeclContext).

	- Doug