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

[Douglas Gregor]

Hi Chris,

On Dec 8, 2008, at 11:44 AM, Chris Lattner wrote:

> On Dec 4, 2008, at 5:30 PM, Douglas Gregor wrote:
>> The attached patch changes how we perform both qualified and  
>> unqualified name lookup in Clang. It represents a significant  
>> departure from the approach currently implemented in Clang, but I  
>> believe it will have performance and maintainability benefits in  
>> the future.
>
> Hi Doug,
>
> I think this is a great step forward.

Thanks for the review!

>
>> This patch is neither complete nor fully-optimized. It should not  
>> degrade performance in C, because the array/hash table data  
>> structures are not built in C. However, there are more optimization  
>> opportunities:
>
> I think that this patch should only go in if you're committed to  
> doing these improvements.  I'm somewhat scared that C and C++ will  
> diverge even more.  If you're planning to do these, then I'm all for  
> the change!

Updated patch coming, which makes quite a few improvements in this  
area. However, some replies to your comments below...

>> 	- We should make RecordDecl derive from DeclContext, and replace  
>> the current storage and name lookup for fields  
>> (RecordDecl::getMember, a linear search) with lookup into the  
>> DeclContext. This will give us faster lookup for records with many  
>> members. A similar thing could be done for Objective-C interfaces/ 
>> implementations.
>
> Yep, we should migrate ObjC as well.  I think it is important that  
> we keep it and C and C++ all consistent where possible.

*That* will need to be a follow-on patch.

> +  /// LookupPtr - Pointer to a data structure used to lookup
> +  /// declarations within this context. If the context contains fewer
> +  /// than seven declarations, the number of declarations is provided
> +  /// in the 3 lowest-order bits and the upper bits are treated as a
> +  /// pointer to an array of NamedDecl pointers. If the context
> +  /// contains seven or more declarations, the upper bits are treated
> +  /// as a pointer to a DenseMap<DeclarationName, TwoNamedDecls>.
> +  llvm::PointerIntPair<void*, 3> LookupPtr;
>
> Very clever.  I never thought of using the low bits as a counter,  
> I'll have to remember that :)

I was pretty proud of that.

>
> +  lookup_result lookup(ASTContext &Context, DeclarationName Name);
> +  lookup_const_result lookup(ASTContext &Context, DeclarationName  
> Name) const;
>
> Since the impl of the second lookup function is just a  
> const_cast'ing forwarding function for the first one, it might be  
> worth putting it inline in the header.

Then we'd need to include "clang/AST/DeclarationName.h".

>
>
> +    if (NamespaceDecl *OrigNS = dyn_cast_or_null<NamespaceDecl> 
> (PrevDecl)) {
> +      // This is an extended namespace definition.
> +      // Attach this namespace decl to the chain of extended  
> namespace
> +      // definitions.
> +      NamespaceDecl *NextNS = OrigNS;
> +      while (NextNS->getNextNamespace())
> +	NextNS = NextNS->getNextNamespace();
>
> Is it necessary to walk the entire list of namespaces here?  Would  
> it be possible to keep the list built and maintained backwards?   
> Also, slightly wonky indentation.

Actually, we'll never actually go into the loop, now that PrevDecl is  
always the most recent declaration of this namespace. Good catch.

> +  // Determine whether the current context supports qualified name
> +  // lookup. If so, we may insert this declaration into the current
> +  // context.
> +  bool SupportQualifiedNameLookup = getLangOptions().CPlusPlus &&
> +    (isa<TranslationUnitDecl>(CurContext) ||
> +     isa<NamespaceDecl>(CurContext) ||
> +     isa<CXXRecordDecl>(CurContext) ||
> +     (getLangOptions().CPlusPlus0x && isa<EnumDecl>(CurContext)));
>
> can this be split out into a predicate method on CurContext?

This is gone in the upcoming patch.

>
> +  if (ScopedDecl *SD = dyn_cast<ScopedDecl>(D))
> +    CurContext->addDecl(Context, SD, SupportQualifiedNameLookup);
> +  else if (CXXFieldDecl *FD = dyn_cast<CXXFieldDecl>(D))
> +    FD->getParent()->insert(Context, FD);
> +
>   IdResolver.AddDecl(D);
> }
>
> Is there an "else" for this?  If not, it would be good to make it  
> assert and die.  If so, it would be good to add a comment.

There's no "else", so I've added a comment. Basically, if it's going  
to be in a DeclContext, it's going to be a ScopedDecl. No exceptions.  
(For reference: CXXFieldDecl is gone in the new patch, and FieldDecl  
is a ScopedDecl).

> +  } else {
> +    if (getLangOptions().CPlusPlus &&
> +	(NS & (Decl::IDNS_Ordinary | Decl::IDNS_Tag))) {
> +      // Name lookup for ordinary names and tag names in C++ requires
> +      // looking into scopes that aren't strictly lexical, and
> +      // therefore we walk through the context as well as walking
> +      // through the scopes.
>
> To reduce nesting, please turn this into } else if (...) {

Okay.

>
> +	// Check whether the IdResolver has anything in this scope.
> +	// FIXME: The isDeclScope check could be expensive. Can we do  
> better?
> +	while (I != IdResolver.end() && S->isDeclScope(*I)) {
> +	  if ((*I)->getIdentifierNamespace() & NS)
> +	    return *I;
> +	
> +	  ++I;
> +	}
>
> How about getting the decls context and using that?  Do scopes have  
> an associated context?

Some scopes have an associated "entity", which ends up being a  
DeclContext, but there's no mapping from DeclContext -> Scope (because  
Scope is a transient thing only available at parse time). The  
isDeclScope check is just a lookup in a (typically relatively small)  
set, so it shouldn't be *that* expensive. I'll leave the FIXME and  
think about it more, later :)
>
> The while loop might be more natural as a 'for' loop, to pull the + 
> +I into the loop condition.

Agreed.

>
>
> +	// If there is an entity associated with this scope, it's a
> +	// DeclContext. We might need to perform qualified lookup into
> +	// it.
> +	DeclContext *Ctx = static_cast<DeclContext *>(S->getEntity());
> +	while (Ctx && Ctx->isFunctionOrMethod())
> +	  Ctx = Ctx->getParent();
>
> Can you have more than one function/method context?  If no, please  
> convert the while to if.

IIUC,  we could have a block context inside of a function context.

>
> +	while (Ctx && (Ctx->isNamespace() || Ctx->isCXXRecord())) {
> +	  // Look for declarations of this name in this scope.
> +	  for (DeclContext::lookup_const_result I = Ctx->lookup(Context,  
> Name);
> +	       I.first != I.second; ++I.first) {
> +	    // FIXME: Cache this result in the IdResolver
> +	    if ((*I.first)->getIdentifierNamespace() & NS)
> +	      return  *I.first;
> +	  }
> +
> +	  Ctx = Ctx->getParent();
> +	}
>
> I think that this would be better to split out as a (potentially  
> virtual?) method on the context.  This would make it easier to  
> extend with different sorts of contexts.

Okay.

>  For example, could 'enableLazyBuiltinCreation' be handled as a  
> "lookup" on the global (or maybe a new 'builtin') scope instead of  
> as a special case hack?

Well, maybe. It depends somewhat on whether we want to permit  
qualified lookup to find these names ('::__builtin_foo') or not. One  
could imagine that they live in an imaginary scope outside of the  
translation unit, so you can never actually find them via unqualified  
lookup.

>
>
> +      // Scan up the scope chain looking for a decl that matches this
> +      // identifier
> +      // that is in the appropriate namespace.  This search should
> +      // not take long, as
> +      // shadowing of names is uncommon, and deep shadowing is
> +      // extremely uncommon.
> +      for (; I != IdResolver.end(); ++I)
> +	if ((*I)->getIdentifierNamespace() & NS)
> +	  return *I;
>
> Please wrap the comment better, and avoid evaluating .end() every  
> time through the loop.

Okay.

>
>
>           if (OldDecl == PrevDecl) {
>             // Remove the name binding for the previous
> +            // declaration.
> +	    //	    if (cast<ScopedDecl>(PrevDecl)->getLexicalDeclContext()  
> == CurContext) {
> +	    if (S->isDeclScope(PrevDecl)) {
>
> commented out code.

Oops.

>
>
> +	  // Add this declaration
> +	  if (getLangOptions().CPlusPlus)
> +	    CurContext->addDecl(Context, NewFD, false);
>
> +	  // In C++, check default arguments now that we have merged decls.
> +	  if (getLangOptions().CPlusPlus)
> +	    CheckCXXDefaultArguments(NewFD);
>
> should these be merged into one "if"?

Sure.

>
>
>   const RecordType *BaseRecord = Base->getType()->getAsRecordType();
> +  DeclContext::lookup_const_result Lookup
> +    = cast<CXXRecordType>(BaseRecord)->getDecl()->lookup(Context,  
> OpName);
>
> This will go away when C and C++ use the same lookup for struct  
> fields, right?

Yes. The upcoming patch will do this.

> +DeclContext::lookup_result
> +DeclContext::lookup(ASTContext &Context, DeclarationName Name) {
> ..
> +    }
> +  } else {
>
> How about "return Result" at the end of the "if".  This lets you  
> unnest the 'else' clause.

Okay.

> +DeclContext::lookup_iterator
> +DeclContext::insert(ASTContext &Context, NamedDecl *D) {
> +  DeclContext *PrimaryContext = getPrimaryContext(Context);
> +  if (PrimaryContext != this)
> +    return PrimaryContext->insert(Context, D);
> +
> +  unsigned Size = LookupPtr.getInt();
> +  if (Size < LookupIsMap) {
>
> There are various places where you compare against LookupIsMap in  
> different ways (some using != some using <), how about introducing a  
> private isLookupMap() method or something like that?  In this case,  
> the fact that LookupIsMap is the largest value really doesn't have  
> anything to do with the algorithm.  If you don't like the predicate  
> method, please change it to use !=.

A predicate is fine.

> Another option would be to pull the array/map code into its own  
> generic class (out of the DeclContext class), which might be the  
> real best solution.

What it does is far too specific to end up in its own generic class.

> *ahhh*, this is because there are tabs in the file!  Please zap  
> them! :)

Will do.

>
> Finally, when the dust settles on name lookup, can you please add an  
> overview to the Internals doc? :)  The issues are nuanced enough  
> that a high level overview would be very useful.

Yeah, I will. I want to make sure I've gotten it right for the truly  
ugly cases (using declarations and such) before investing too much  
time in documentation.

	- Doug