[cfe-dev] [Patch] AST support, and unqualified name lookup for using-directives
Douglas Gregor
dgregor at apple.com
Tue Feb 3 11:24:13 PST 2009
Hi Piotr,
On Feb 2, 2009, at 3:53 PM, Piotr Rak wrote:
> Thanks for review, and great comments!
>
> I have addressed most of issues in attached version.
> It also partially fixes other thing I have noticed, similar failure to
> one from first version of patch with namespaces, now with tags.
> Fix is not complete though, but behaviour is right. One commented out
> in test is incorrectly diagnosed. I'll try send fix ASAP.
Got it; some review and comments follow, but I've committed your patch
already with a few tweaks. Thank you!
> There is risk we don't check LookupResult for ambiguities in more
> cases too... We need will need more tests.
Yes, definitely. Eventually, it's probably safest if we remove the
implicit conversion from LookupResult -> Decl*, then audit all uses of
getAsDecl. However, there are other issues we need to solve first :)
> I have checked with gcc
> testsuite, and we pass all tests that have 'using namespace', and
> don't include standard library headers, use using-declaration, or
> require strong-using now.
Wonderful.
>> This is what I was looking for. We can cache the results of this
>> operation
>> in the Scope structure or (in some cases) DeclContext. Performing
>> this
>> operation once per LookupName call would be quite painful; but if
>> the number
>> of times we need to do this is proportional instead to the number of
>> using-directives, that would be fine.
>>
>
> I would like to avoid making DeclContext heavier, without big
> benfit... Scope sounds better to me.I have put some effort to avoid
> that, because:
>
> - C doesn't need it.
> - There will be houndreds DeclContext's in typical code
> - I will be surprised if there we were many more than 20 Scope objects
> in typical
> code at one time
> - Scope has short pretty life, if we compare it to DeclContext.
> - Other AST clients can't benefit from that information anyway...
Sure, but qualified name lookup goes through DeclContexts, not through
Scopes, so qualified name lookup can't benefit from caching if it
isn't cached in the DeclContext.
Anyway, if we generalized the DenseMap inside DeclContext so that it
was relatively easy to add "extra" names (like you did with the
special DeclarationName for using directives), then it should be easy
to create a special name for the cached set of namespaces and put
those into the DeclContext. That can come with a later patch, of course.
>> + } else if (UsingDirectiveDecl *UD = dyn_cast<UsingDirectiveDecl>
>> (D)) {
>> + // print using-directive decl (e.g. "using namespace x;")
>> + const char *ns;
>> + if (const IdentifierInfo *II = UD->getUsedNamespace()-
>> >getIdentifier())
>> + ns = II->getName();
>> + else
>> + ns = "<anonymous>";
>> + fprintf(F, "\"%s %s;\"",UD->getDeclKindName(), ns);
>>
>> Is it even possible to have a using directive that nominates an
>> anonymous
>> namespace? I guess it depends on how we implement unnamed namespaces.
>>
>
> That reveals, how I plan deal with anonymous namespaces for name
> lookup :)
> I wanted add implicit using-directive in enclosing context (as
> Sebastian already pointed out). This should be enough, assuming that,
> we work only with single translation unit.
That's a perfectly reasonable assumption.
> In fact, I was planing to implement unqualified/qualified name lookup,
> gcc strong-using/inline namespace and anonymous namespaces together,
> but later it turned out to be too big for one patch!
Yikes! It's good to take those separately... anonymous namespaces
should be a simple follow-on to this patch. Inline namespaces, on the
other hand, don't need to interact with this patch: they should just
be transparent DeclContexts (see the comment in
DeclContext::isTransparentContext() in lib/AST/DeclBase.cpp).
>> Should Sema::ActOnUsingDirective assert that the scope S it gets is a
>> DeclScope?
>>
>> + // Ensure, that decls are being added to orginal namespace.
>> + // Ctx = Ctx->getPrimaryContext(); XXX: needless
>> + Ctx->addDecl(UDir);
>>
>> Right, we don't need that Ctx = Ctx->getPrimaryContext() here, but
>> we will
>> need it later...
>
> No we won't, using-directive should be added to lexical context, and
> only be visible
> in semantic context, just like other NamedDecls. This is how
> DeclContext::addDecl works now, so we don't need anything special
> here, right?
Right. I see that the getPrimaryContext() is already implicit in the
way we deal with nominated namespaces, so my comment about needing it
later was wrong.
>
>> + case LResult::AmbiguousBaseSubobjectTypes:
>> + case LResult::AmbiguousBaseSubobjects: {
>> + // FIXME: Do we care about later possibly found
>> + // AmbiguousBaseSubobjectTypes, or AmbiguousBaseSubobjects?
>> + // Is it ever possible?
>>
>> I don't believe this is ever possible, since using directives can't
>> occur at
>> class scope. We should probably have an assert() here.
>
> It shouldn't be possible, however it is, probably because we look more
> than once in same DeclContext.
Sure, but we never look into a DeclContext that's associated with a
class, because using directives don't ever nominate classes.
>> + case LResult::FoundOverloaded:
>> + if (FoundOverloaded) {
>> + // We have one spare OverloadedFunctionDecl already, so we
>> store
>> + // its function decls and free it.
>> + OverloadedFunctionDecl *Ovl =
>> + cast<OverloadedFunctionDecl>(I->getAsDecl());
>> +
>> + OverloadedFunctionDecl::function_iterator
>> + FI = Ovl->function_begin(),
>> + FEnd = Ovl->function_end();
>> +
>> + for (FI; FI != FEnd; ++FI)
>> + FoundDecls.push_back(*FI);
>> +
>> + Ovl->Destroy(Context);
>> + } else {
>> + // First time we found OverloadedFunctionDecl, we want to
>> conserve
>> + // it, and possibly add other found Decls later.
>> + FoundOverloaded = cast<OverloadedFunctionDecl>(I->getAsDecl
>> ());
>> + }
>> + break;
>>
>> In the "else" branch, don't you need to add all of the decls to
>> FoundDecls?
>
> No, because I reuse first OverloadedFunctionDecl I find, so it has
> them already, do you see otherwise?
Okay, I understand now. The FoundDecls not in the
OverloadedFunctionDecl get added to the OverloadedFunctionDecl later.
>> + DeclsVecTy::iterator DI = FoundDecls.begin(), DEnd =
>> FoundDecls.end();
>> + std::sort(DI, DEnd);
>> + DEnd = std::unique(DI, DEnd);
>>
>> I have to wonder if it would be easier just to insert everything
>> into a
>> SmallPtrSet and then just iterate over the results, especially
>> given the
>> code below it:
>>
>> + if (FoundOverloaded) {
>> + // We found overloaded functions result. We want to add any
>> other
>> + // found decls, that are not already in FoundOverloaded, and are
>> functions
>> + // or methods.
>> + OverloadedFunctionDecl::function_iterator
>> + FBegin = FoundOverloaded->function_begin(),
>> + FEnd = FoundOverloaded->function_end();
>> + for (DI ; DI < DEnd; ++DI) {
>> + FunctionDecl *Fun = dyn_cast<FunctionDecl>(*DI);
>> + if (Fun && (std::find(FBegin, FEnd, Fun) != FEnd)) { /*
>> Skip.*/ }
>> + else DEnd = std::remove(DI, DEnd, *DI);
>> + }
>>
>> This is O(n^2) in [DI, DEnd), because remove() is linear time.
>> Sure, [DI,
>> DIEnd) should be pretty small---and so should [FBegin, FEnd) which
>> we search
>> through linearly---but I think this whole section would be cleaner
>> (and no
>> less efficient) with SmallPtrSet.
>
> Would it fair, to fix it once OverloadedFunctionDecl dies, from
> exactly small detail you mentioned below... Decls need to be added in
> same order we found it.
We can fix it later, although I don't think we need this fix to be
tied to the demise of OverloadedFunctionDecl.
>> + // We might find FunctionDecls in two (or more) distinct
>> DeclContexts.
>> + Decl *D = MaybeConstructOverloadSet(Context, DI, DEnd);
>> + if ((FoundLen == 1) || isa<OverloadedFunctionDecl>(D))
>> + return LResult::CreateLookupResult(Context, D);
>>
>> It's very interesting that this implements 3.4.3.2p5 (a comment and
>> quote
>> from the standard here would help!), although I think there's one
>> issue:
>> MaybeConstructOverloadSet(Context, DI, DEnd) expects that, if the
>> sequence
>> [DI, DEnd) contains both object and tag names, that the object
>> names precede
>> the tag names. This won't necessarily be the case with [DI, DEnd),
>> since we
>> put decls into FoundDecls in the order we found them.
>
> Are you sure it is right, in last final draft I have 3.4.3.2.p5 is:
>
> "During the lookup of a qualified namespace member name, if the lookup
> finds more than one declaration of the member, and if one
> declaration introduces a class name or enumeration name and the other
> declarations either introduce the same object, the same enumerator or
> a set of functions, the non-type name hides the class or enumeration
> name if and only if the declarations are from the same namespace;
> otherwise
> (the declarations are from different namespaces), the program is ill-
> formed."
Oh, interesting! I had misread that.
>> + // Collect UsingDirectiveDecls in all scopes, and recursivly all
>> + // nominated namespaces by those using-directives.
>> + // UsingDirectives are pushed to heap, in common ancestor pointer
>> + // value order.
>> + UsingDirectivesTy UDirs;
>> + for (Scope *SC = Initial; SC; SC = SC->getParent())
>> + AddScopeUsingDirectives(SC, UDirs);
>> +
>> + // Sort heapified UsingDirectiveDecls.
>> + std::sort_heap(UDirs.begin(), UDirs.end());
>>
>> Could we move this computation down below the part that looks in
>> local
>> scopes for names? For example, if we have something like this:
>>
>> namespace N { int i; }
>> using namespace N;
>>
>> int f(int i) {
>> return i;
>> }
>
> Now 'i' is found before sort for this case, we return result in line
> 562:
> return std::make_pair(true, Result);
>
> I have checked that in debugger, do you see otherwise?
I see it now. Thanks.
>> When doing name lookup for "i", we'll never look into a namespace
>> or global
>> scope, so there's no reason to go through the effort of looking for
>> using
>> directives.
>>
>> + for (; S && isFunctionScope(S); S = S->getParent()) {
>> // ...
>> + // NB: Icky, we need to look in function scope, but we need to
>> check
>> its
>> + // parent DeclContext, in case it is out of line method
>> definition.
>> + if (S->getEntity() && isFunctionScope(S))
>> + break;
>>
>> This doesn't look right... function scopes have entities (the
>> FunctionDecl);
>> it's only when that entity is a C++ member function that we need to
>> look
>> into its (semantic) parent *after* we've looked in function scope.
>> This look
>> should exit out once we hit a scope S whose entity is a
>> NamespaceDecl or
>> TranslationUnitDecl; after that, we need to start worrying about
>> using
>> directives.
>
> If we did not break here; Scope->getEntity() would be translation-unit
> or namespace, for out of line member function definition, and we would
> not perform member name lookup. It is true, we could do
> LookupQualifiedName here, and stop later at translation-unit namespace
> Scope. Is that what you wanted me to implement?
I think so :)
I'm hoping we can leverage LookupQualifiedName when we're looking into
scopes that also permit qualified name lookup (classes, namespaces,
translation unit/global scope). However, your comment below is making
me think that we shouldn't try to do this.
>> + for (llvm::tie(UI, UEnd) =
>> + FindUsingDirsByAncestors(UDirs, Ctx); UI != UEnd; ++UI) {
>> + // FIXME: We will have to ensure, that we won't consider
>> + // again using-directives during qualified name lookup!
>> + // (Once using-directives support for qualified name
>> lookup gets
>> + // implemented).
>> + if (LookupResult R = LookupQualifiedName((*UI)-
>> >getUsedNamespace(),
>> + Name, NameKind, RedeclarationOnly))
>> + LookupResults.push_back(R);
>>
>> Regarding this FIXME, I think CppLookupName will become a bit
>> easier if
>> LookupQualifiedName understood how to search for those names within
>> its
>> DeclContext that should be found via using directives. In particular,
>> LookupQualifiedName could take an optional "UsingDirectivesTy const
>> *UDirs"
>> parameter that it would use to determine which other namespaces to
>> search
>> in. I think the end result would be clearer (and more functional).
>
> LookupQualifiedName will need to get logic for using-directives, which
> is quite different from what we want for unqualified name lookup. That
> means, it would get 2 modes for:
> - unqualified name lookup
> - qualified name lookup
>
> Qualified name lookup is quite complicated too unfortunately, involves
> tracking visited
> contexts, etc...
> Beside we will probably need off switch for considering
> using-directives for ADL, because of 3.4.2.p3.
> If it is not essential to land this patch, I would like to implement
> qualified name lookup first.
Okay, understood.
I'm planning to work on argument dependent lookup now (it's next on
"the list"). I don't think it will collide with what you're doing
because it's a narrow form of lookup that is not likely to go through
Lookup*Name at all. We'll see :)
One thing I noticed about ActOnTag:
@@ -2824,8 +2826,20 @@ Sema::DeclTy *Sema::ActOnTag(Scope *S, unsigned
TagSpec, TagKind TK,
} else if (Name) {
// If this is a named struct, check to see if there was a
previous forward
// declaration or definition.
- Decl *D = LookupName(S, Name, LookupTagName);
- PrevDecl = dyn_cast_or_null<NamedDecl>(D);
+ LookupResult R = LookupName(S, Name, LookupTagName);
+ if (R.isAmbiguous()) {
+ DiagnoseAmbiguousLookup(R, Name, NameLoc);
+ // FIXME: This is not best way to recover from case like:
+ //
+ // struct S s;
+ //
+ // causes needless err_ovl_no_viable_function_in_init latter.
+ Name = 0;
+ PrevDecl = 0;
+ Invalid = true;
+ }
+ else
+ PrevDecl = dyn_cast_or_null<NamedDecl>(static_cast<Decl*>(R));
if (!getLangOptions().CPlusPlus && TK != TK_Reference) {
// FIXME: This makes sure that we ignore the contexts associated
This is going to diagnose ambiguities even when we shouldn't because,
for example, we might be declaring a class or enum type in a new
scope, but LookupName is finding something ambiguous in a different
(parent) scope. I added two test cases here, one involving using-
directives and one involving base-class lookup, that trigger the bug.
However, I think it's best if I tackle this one. I've been doing a bit
of work in ActOnTag recently, and I have both the C and C++ rules
fresh in my mind.
Thanks for the great contribution!
- Doug
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20090203/cdba566b/attachment.html>
More information about the cfe-dev
mailing list