Qualified and unqualified name lookup and IdResolver

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.

First, an explanation of qualified name lookup and how it works in Clang today. Here's an example:

int x; // #1
namespace N {
   int x; // #2
   struct f1 {
     static int x; // #3
   };
}

namespace N {
   struct f2 {
     static int x; // #4
   }
}

int xv = N::x;

The expression N::x involves qualified name lookup, which first looks for "x" within the namespace N. The way this currently works is that there is an IdentifierInfo "x" which contains as list of all of the declarations of "x" in the translation unit, #4 -> #3 -> #2 -> #1. To find "x" in N, we search this list, filtering out those x's that aren't declared in the context 'N', until we find our answer (#2).

The same approach is used for unqualified lookup. Let's say that we add this code at the end of our program above:

namespace N2 {
   void f() {
     int y = x;
   }
}

Here, the unqualified lookup for "x" searches the same chain of declarations for x (#4 -> #3 -> #2 -> #1), this time accepting any declaration that is in the context of "f" or one of its enclosing contexts (N2, translation unit), and eventually finds #1.

The performance concern is that, as translation units get bigger, the chain of declarations for common names ("operator=" in C++ is one such name) can get large, and we're paying for a linear traversal of this list. This will be particularly bad with template metaprograms, where many members are named "value" or "type" by convention, and template metaprogram evaluation can involve the instantiation of thousands of class templates, each with their own "value" or "type" that ends up on the corresponding declaration chain.

The maintainability concern is that the construction of the chain of declarations is very tied to the act of parsing the translation unit. Other ways of getting part of a program into memory--say, deserializing an AST from disk---would have to reconstruct these chains as if we were parsing. There are also some open questions about how one would deal with lookup into base classes: would we need to perform IsDerivedFrom checks for each identifier as part of the check for "is this in my context?".

I propose---and this patch implements---an alternative solution that returns the chain of declarations back to a chain of declarations that occur within the lexical scope of the program. For our function N2::f, the chain for "x" would contain only #1, which is the only "x" within the lexical scope. Essentially, when names get introduced into a scope via a declaration, they are added to the declaration chain for their name; when that scope is destroyed those names are removed from the declaration chain. That way, the declaration chains only contain declarations that can actually be found by unqualified name lookup, and are no deeper than the nesting of lexical scopes.

For qualified name lookup, each DeclContext has the ability to perform a lookup into the declarations it contains. For example, to find N::x, we would ask the DeclContext represented by N whether it has a name "x" in it. The lookup is performed in an efficient data structure: for < 6 declarations in the DeclContext, it's an array; for more declarations, it's a hash table.

In this scheme, C++ unqualified name lookup falls back on qualified name lookup in some cases. For example, let's add this code to the end of the program above:

namespace N { // re-opening namespace!
   void g() {
     int y = x; // needs to find #2
   }
}

Note that "x" was not declared in the *lexical* scope of N::g. However, it was declared in the namespace N, so it should be found by unqualified name lookup. One approach to solving this problem would be to push all of the names in N into scope when we re-open the namespace N, but we don't want to do that because opening a namespace would then be linear time in the number of declarations in the namespace. Imagine pushing all of the declarations for namespace "std" just to put in a specialization of iterator_traits!

This patch implements a different approach. Each scope can have an associated "entity", which is the DeclContext that defines the scope. So, for example, the re-opened scope for "N" has as its entity the DeclContext associated with this declaration of N. When we don't see a name in our lexical scope, and the lexical scope has an associated entity, we perform qualified lookup into that entity. So, since there is no "x" in the lexical scope corresponding to N, we look for N::x and find the x living in the first definition of N. The DeclContexts are linked such that, even though each of the three times we open 'N' we have different DeclContexts (each of which contains just the declarations present in the source for that namespace definition), for name lookup purposes there's only one array/hash table containing all of the declarations of 'N'.

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:
  - Once we've performed unqualified name lookup for a name, we should cache it on the chain of declarations. For example, in N::g, we do some work to find N::x. We should add N::x to the declaration chain---but not the DeclContext!---so that subsequent lookups of x are very fast (since it'll be at the front of the declaration list for "x").
  - We should be building the array/hash table in the DeclContexts lazily, when we need to answer the question "is there an x in N?". This would allow us to remove the special-casing for C.
  - 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.
  - When variables are redeclared (e.g., at translation unit scope), we should be replacing the current declaration with the previous one, rather than pushing both declarations onto the declaration name chain. (This is an existing problem that I did not yet fix).

Comments *greatly* appreciated!

  - Doug

qualified-name-lookup.patch (43.8 KB)

Hi Doug,

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.

-Argiris

Douglas Gregor wrote:

Haven't looked at the patch yet, but I like the concept very much.

Sebastian

Hi Argiris!

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

Hi Doug,

Douglas Gregor 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.

That's all very reasonable. If only the C++ front-end were complete enough to parse real code, we would be able to run tests for comparison.

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.

It would be great if this part can remain simple and separate so that it's easy to try out #2 sometime to see how it impacts performance.

-Argiris

We'll try to do exactly that.

  - Doug

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.

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!

  - Once we've performed unqualified name lookup for a name, we should cache it on the chain of declarations. For example, in N::g, we do some work to find N::x. We should add N::x to the declaration chain---but not the DeclContext!---so that subsequent lookups of x are very fast (since it'll be at the front of the declaration list for "x").

Nice.

  - We should be building the array/hash table in the DeclContexts lazily, when we need to answer the question "is there an x in N?". This would allow us to remove the special-casing for C.

Yes, this would be great.

  - 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.

  - When variables are redeclared (e.g., at translation unit scope), we should be replacing the current declaration with the previous one, rather than pushing both declarations onto the declaration name chain. (This is an existing problem that I did not yet fix).

Sure, incremental improvement is good :slight_smile:

On to the 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 :slight_smile:

+ 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.

+ 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.

+ // Remove the previous declaration from the scope.
+ if (DeclRegionScope->isDeclScope(OrigNS)) {
+ IdResolver.RemoveDecl(OrigNS);
+ DeclRegionScope->RemoveDecl(OrigNS);
+ }

indentation.

+ // 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?

+ 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);

Hi Chris,

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 :slight_smile:

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 :slight_smile:

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! :slight_smile:

Will do.

Finally, when the dust settles on name lookup, can you please add an overview to the Internals doc? :slight_smile: 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

+ 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".

Ok. That's a good reason to leave it out of line if it isn't already implicitly included.

+ 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).

Ok, a comment is good, an assert (if possible) is better :slight_smile:

+ // 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 :slight_smile:

Sure, sounds good.

+ // 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.

Does a block context satisfy the predicate "isFunctionOrMethod"? If so, we need to rename isFunctionOrMethod :slight_smile:

or do you mean !Ctx->isFunctionOrMethod() ?

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.

I don't know what GCC does with this, but I would assume they are only ever found

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.

Ok, you convinced me on irc.

Finally, when the dust settles on name lookup, can you please add an overview to the Internals doc? :slight_smile: 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.

Thanks Doug! I'll take a look at your new patch tomorrow, but feel free to commit it if I don't get to it in time.

-Chris

Sorry, got interrupted and forgot to finish the thought:

... only ever found with unqualified name lookup. It would be interesting to see if ::__builtin_foo works with GCC though.

-Chris