SemaLookup.cpp revision a0ac8911efa482aa004c707cf1bb7d5cffc716bb
1//===--------------------- SemaLookup.cpp - Name Lookup ------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements name lookup for C, C++, Objective-C, and 11// Objective-C++. 12// 13//===----------------------------------------------------------------------===// 14#include "Sema.h" 15#include "clang/AST/ASTContext.h" 16#include "clang/AST/CXXInheritance.h" 17#include "clang/AST/Decl.h" 18#include "clang/AST/DeclCXX.h" 19#include "clang/AST/DeclObjC.h" 20#include "clang/AST/DeclTemplate.h" 21#include "clang/AST/Expr.h" 22#include "clang/AST/ExprCXX.h" 23#include "clang/Parse/DeclSpec.h" 24#include "clang/Basic/Builtins.h" 25#include "clang/Basic/LangOptions.h" 26#include "llvm/ADT/STLExtras.h" 27#include "llvm/ADT/SmallPtrSet.h" 28#include "llvm/Support/ErrorHandling.h" 29#include <set> 30#include <vector> 31#include <iterator> 32#include <utility> 33#include <algorithm> 34 35using namespace clang; 36 37namespace { 38 class UnqualUsingEntry { 39 const DeclContext *Nominated; 40 const DeclContext *CommonAncestor; 41 42 public: 43 UnqualUsingEntry(const DeclContext *Nominated, 44 const DeclContext *CommonAncestor) 45 : Nominated(Nominated), CommonAncestor(CommonAncestor) { 46 } 47 48 const DeclContext *getCommonAncestor() const { 49 return CommonAncestor; 50 } 51 52 const DeclContext *getNominatedNamespace() const { 53 return Nominated; 54 } 55 56 // Sort by the pointer value of the common ancestor. 57 struct Comparator { 58 bool operator()(const UnqualUsingEntry &L, const UnqualUsingEntry &R) { 59 return L.getCommonAncestor() < R.getCommonAncestor(); 60 } 61 62 bool operator()(const UnqualUsingEntry &E, const DeclContext *DC) { 63 return E.getCommonAncestor() < DC; 64 } 65 66 bool operator()(const DeclContext *DC, const UnqualUsingEntry &E) { 67 return DC < E.getCommonAncestor(); 68 } 69 }; 70 }; 71 72 /// A collection of using directives, as used by C++ unqualified 73 /// lookup. 74 class UnqualUsingDirectiveSet { 75 typedef llvm::SmallVector<UnqualUsingEntry, 8> ListTy; 76 77 ListTy list; 78 llvm::SmallPtrSet<DeclContext*, 8> visited; 79 80 public: 81 UnqualUsingDirectiveSet() {} 82 83 void visitScopeChain(Scope *S, Scope *InnermostFileScope) { 84 // C++ [namespace.udir]p1: 85 // During unqualified name lookup, the names appear as if they 86 // were declared in the nearest enclosing namespace which contains 87 // both the using-directive and the nominated namespace. 88 DeclContext *InnermostFileDC 89 = static_cast<DeclContext*>(InnermostFileScope->getEntity()); 90 assert(InnermostFileDC && InnermostFileDC->isFileContext()); 91 92 for (; S; S = S->getParent()) { 93 if (!(S->getFlags() & Scope::DeclScope)) 94 continue; 95 96 if (DeclContext *Ctx = static_cast<DeclContext*>(S->getEntity())) { 97 DeclContext *EffectiveDC = (Ctx->isFileContext() ? Ctx : InnermostFileDC); 98 visit(Ctx, EffectiveDC); 99 } else { 100 Scope::udir_iterator I = S->using_directives_begin(), 101 End = S->using_directives_end(); 102 103 for (; I != End; ++I) 104 visit(I->getAs<UsingDirectiveDecl>(), InnermostFileDC); 105 } 106 } 107 } 108 109 // Visits a context and collect all of its using directives 110 // recursively. Treats all using directives as if they were 111 // declared in the context. 112 // 113 // A given context is only every visited once, so it is important 114 // that contexts be visited from the inside out in order to get 115 // the effective DCs right. 116 void visit(DeclContext *DC, DeclContext *EffectiveDC) { 117 if (!visited.insert(DC)) 118 return; 119 120 addUsingDirectives(DC, EffectiveDC); 121 } 122 123 // Visits a using directive and collects all of its using 124 // directives recursively. Treats all using directives as if they 125 // were declared in the effective DC. 126 void visit(UsingDirectiveDecl *UD, DeclContext *EffectiveDC) { 127 DeclContext *NS = UD->getNominatedNamespace(); 128 if (!visited.insert(NS)) 129 return; 130 131 addUsingDirective(UD, EffectiveDC); 132 addUsingDirectives(NS, EffectiveDC); 133 } 134 135 // Adds all the using directives in a context (and those nominated 136 // by its using directives, transitively) as if they appeared in 137 // the given effective context. 138 void addUsingDirectives(DeclContext *DC, DeclContext *EffectiveDC) { 139 llvm::SmallVector<DeclContext*,4> queue; 140 while (true) { 141 DeclContext::udir_iterator I, End; 142 for (llvm::tie(I, End) = DC->getUsingDirectives(); I != End; ++I) { 143 UsingDirectiveDecl *UD = *I; 144 DeclContext *NS = UD->getNominatedNamespace(); 145 if (visited.insert(NS)) { 146 addUsingDirective(UD, EffectiveDC); 147 queue.push_back(NS); 148 } 149 } 150 151 if (queue.empty()) 152 return; 153 154 DC = queue.back(); 155 queue.pop_back(); 156 } 157 } 158 159 // Add a using directive as if it had been declared in the given 160 // context. This helps implement C++ [namespace.udir]p3: 161 // The using-directive is transitive: if a scope contains a 162 // using-directive that nominates a second namespace that itself 163 // contains using-directives, the effect is as if the 164 // using-directives from the second namespace also appeared in 165 // the first. 166 void addUsingDirective(UsingDirectiveDecl *UD, DeclContext *EffectiveDC) { 167 // Find the common ancestor between the effective context and 168 // the nominated namespace. 169 DeclContext *Common = UD->getNominatedNamespace(); 170 while (!Common->Encloses(EffectiveDC)) 171 Common = Common->getParent(); 172 Common = Common->getPrimaryContext(); 173 174 list.push_back(UnqualUsingEntry(UD->getNominatedNamespace(), Common)); 175 } 176 177 void done() { 178 std::sort(list.begin(), list.end(), UnqualUsingEntry::Comparator()); 179 } 180 181 typedef ListTy::iterator iterator; 182 typedef ListTy::const_iterator const_iterator; 183 184 iterator begin() { return list.begin(); } 185 iterator end() { return list.end(); } 186 const_iterator begin() const { return list.begin(); } 187 const_iterator end() const { return list.end(); } 188 189 std::pair<const_iterator,const_iterator> 190 getNamespacesFor(DeclContext *DC) const { 191 return std::equal_range(begin(), end(), DC->getPrimaryContext(), 192 UnqualUsingEntry::Comparator()); 193 } 194 }; 195} 196 197// Retrieve the set of identifier namespaces that correspond to a 198// specific kind of name lookup. 199inline unsigned 200getIdentifierNamespacesFromLookupNameKind(Sema::LookupNameKind NameKind, 201 bool CPlusPlus) { 202 unsigned IDNS = 0; 203 switch (NameKind) { 204 case Sema::LookupOrdinaryName: 205 case Sema::LookupOperatorName: 206 case Sema::LookupRedeclarationWithLinkage: 207 IDNS = Decl::IDNS_Ordinary; 208 if (CPlusPlus) 209 IDNS |= Decl::IDNS_Tag | Decl::IDNS_Member; 210 break; 211 212 case Sema::LookupTagName: 213 IDNS = Decl::IDNS_Tag; 214 break; 215 216 case Sema::LookupMemberName: 217 IDNS = Decl::IDNS_Member; 218 if (CPlusPlus) 219 IDNS |= Decl::IDNS_Tag | Decl::IDNS_Ordinary; 220 break; 221 222 case Sema::LookupNestedNameSpecifierName: 223 case Sema::LookupNamespaceName: 224 IDNS = Decl::IDNS_Ordinary | Decl::IDNS_Tag | Decl::IDNS_Member; 225 break; 226 227 case Sema::LookupObjCProtocolName: 228 IDNS = Decl::IDNS_ObjCProtocol; 229 break; 230 231 case Sema::LookupObjCImplementationName: 232 IDNS = Decl::IDNS_ObjCImplementation; 233 break; 234 235 case Sema::LookupObjCCategoryImplName: 236 IDNS = Decl::IDNS_ObjCCategoryImpl; 237 break; 238 } 239 return IDNS; 240} 241 242// Necessary because CXXBasePaths is not complete in Sema.h 243void Sema::LookupResult::deletePaths(CXXBasePaths *Paths) { 244 delete Paths; 245} 246 247void Sema::LookupResult::resolveKind() { 248 unsigned N = Decls.size(); 249 250 // Fast case: no possible ambiguity. 251 if (N <= 1) return; 252 253 // Don't do any extra resolution if we've already resolved as ambiguous. 254 if (Kind == Ambiguous) return; 255 256 llvm::SmallPtrSet<NamedDecl*, 16> Unique; 257 258 bool Ambiguous = false; 259 bool HasTag = false, HasFunction = false, HasNonFunction = false; 260 261 unsigned UniqueTagIndex = 0; 262 263 unsigned I = 0; 264 while (I < N) { 265 NamedDecl *D = Decls[I]; 266 assert(D == D->getUnderlyingDecl()); 267 268 NamedDecl *CanonD = cast<NamedDecl>(D->getCanonicalDecl()); 269 if (!Unique.insert(CanonD)) { 270 // If it's not unique, pull something off the back (and 271 // continue at this index). 272 Decls[I] = Decls[--N]; 273 } else if (isa<UnresolvedUsingDecl>(D)) { 274 // FIXME: proper support for UnresolvedUsingDecls. 275 Decls[I] = Decls[--N]; 276 } else { 277 // Otherwise, do some decl type analysis and then continue. 278 if (isa<TagDecl>(D)) { 279 if (HasTag) 280 Ambiguous = true; 281 UniqueTagIndex = I; 282 HasTag = true; 283 } else if (D->isFunctionOrFunctionTemplate()) { 284 HasFunction = true; 285 } else { 286 if (HasNonFunction) 287 Ambiguous = true; 288 HasNonFunction = true; 289 } 290 I++; 291 } 292 } 293 294 // C++ [basic.scope.hiding]p2: 295 // A class name or enumeration name can be hidden by the name of 296 // an object, function, or enumerator declared in the same 297 // scope. If a class or enumeration name and an object, function, 298 // or enumerator are declared in the same scope (in any order) 299 // with the same name, the class or enumeration name is hidden 300 // wherever the object, function, or enumerator name is visible. 301 // But it's still an error if there are distinct tag types found, 302 // even if they're not visible. (ref?) 303 if (HasTag && !Ambiguous && (HasFunction || HasNonFunction)) 304 Decls[UniqueTagIndex] = Decls[--N]; 305 306 Decls.set_size(N); 307 308 if (HasFunction && HasNonFunction) 309 Ambiguous = true; 310 311 if (Ambiguous) 312 setAmbiguous(LookupResult::AmbiguousReference); 313 else if (N > 1) 314 Kind = LookupResult::FoundOverloaded; 315 else 316 Kind = LookupResult::Found; 317} 318 319/// @brief Converts the result of name lookup into a single (possible 320/// NULL) pointer to a declaration. 321/// 322/// The resulting declaration will either be the declaration we found 323/// (if only a single declaration was found), an 324/// OverloadedFunctionDecl (if an overloaded function was found), or 325/// NULL (if no declaration was found). This conversion must not be 326/// used anywhere where name lookup could result in an ambiguity. 327/// 328/// The OverloadedFunctionDecl conversion is meant as a stop-gap 329/// solution, since it causes the OverloadedFunctionDecl to be 330/// leaked. FIXME: Eventually, there will be a better way to iterate 331/// over the set of overloaded functions returned by name lookup. 332NamedDecl *Sema::LookupResult::getAsSingleDecl(ASTContext &C) const { 333 size_t size = Decls.size(); 334 if (size == 0) return 0; 335 if (size == 1) return *begin(); 336 337 if (isAmbiguous()) return 0; 338 339 iterator I = begin(), E = end(); 340 341 OverloadedFunctionDecl *Ovl 342 = OverloadedFunctionDecl::Create(C, (*I)->getDeclContext(), 343 (*I)->getDeclName()); 344 for (; I != E; ++I) { 345 NamedDecl *ND = *I; 346 assert(ND->getUnderlyingDecl() == ND 347 && "decls in lookup result should have redirections stripped"); 348 assert(ND->isFunctionOrFunctionTemplate()); 349 if (isa<FunctionDecl>(ND)) 350 Ovl->addOverload(cast<FunctionDecl>(ND)); 351 else 352 Ovl->addOverload(cast<FunctionTemplateDecl>(ND)); 353 // FIXME: UnresolvedUsingDecls. 354 } 355 356 return Ovl; 357} 358 359void Sema::LookupResult::addDeclsFromBasePaths(const CXXBasePaths &P) { 360 CXXBasePaths::paths_iterator I, E; 361 DeclContext::lookup_iterator DI, DE; 362 for (I = P.begin(), E = P.end(); I != E; ++I) 363 for (llvm::tie(DI,DE) = I->Decls; DI != DE; ++DI) 364 addDecl(*DI); 365} 366 367void Sema::LookupResult::setAmbiguousBaseSubobjects(CXXBasePaths &P) { 368 Paths = new CXXBasePaths; 369 Paths->swap(P); 370 addDeclsFromBasePaths(*Paths); 371 resolveKind(); 372 setAmbiguous(AmbiguousBaseSubobjects); 373} 374 375void Sema::LookupResult::setAmbiguousBaseSubobjectTypes(CXXBasePaths &P) { 376 Paths = new CXXBasePaths; 377 Paths->swap(P); 378 addDeclsFromBasePaths(*Paths); 379 resolveKind(); 380 setAmbiguous(AmbiguousBaseSubobjectTypes); 381} 382 383void Sema::LookupResult::print(llvm::raw_ostream &Out) { 384 Out << Decls.size() << " result(s)"; 385 if (isAmbiguous()) Out << ", ambiguous"; 386 if (Paths) Out << ", base paths present"; 387 388 for (iterator I = begin(), E = end(); I != E; ++I) { 389 Out << "\n"; 390 (*I)->print(Out, 2); 391 } 392} 393 394// Adds all qualifying matches for a name within a decl context to the 395// given lookup result. Returns true if any matches were found. 396static bool LookupDirect(Sema::LookupResult &R, 397 const DeclContext *DC, 398 DeclarationName Name, 399 Sema::LookupNameKind NameKind, 400 unsigned IDNS) { 401 bool Found = false; 402 403 DeclContext::lookup_const_iterator I, E; 404 for (llvm::tie(I, E) = DC->lookup(Name); I != E; ++I) 405 if (Sema::isAcceptableLookupResult(*I, NameKind, IDNS)) 406 R.addDecl(*I), Found = true; 407 408 return Found; 409} 410 411// Performs C++ unqualified lookup into the given file context. 412static bool 413CppNamespaceLookup(Sema::LookupResult &R, ASTContext &Context, DeclContext *NS, 414 DeclarationName Name, Sema::LookupNameKind NameKind, 415 unsigned IDNS, UnqualUsingDirectiveSet &UDirs) { 416 417 assert(NS && NS->isFileContext() && "CppNamespaceLookup() requires namespace!"); 418 419 // Perform direct name lookup into the LookupCtx. 420 bool Found = LookupDirect(R, NS, Name, NameKind, IDNS); 421 422 // Perform direct name lookup into the namespaces nominated by the 423 // using directives whose common ancestor is this namespace. 424 UnqualUsingDirectiveSet::const_iterator UI, UEnd; 425 llvm::tie(UI, UEnd) = UDirs.getNamespacesFor(NS); 426 427 for (; UI != UEnd; ++UI) 428 if (LookupDirect(R, UI->getNominatedNamespace(), Name, NameKind, IDNS)) 429 Found = true; 430 431 R.resolveKind(); 432 433 return Found; 434} 435 436static bool isNamespaceOrTranslationUnitScope(Scope *S) { 437 if (DeclContext *Ctx = static_cast<DeclContext*>(S->getEntity())) 438 return Ctx->isFileContext(); 439 return false; 440} 441 442// Find the next outer declaration context corresponding to this scope. 443static DeclContext *findOuterContext(Scope *S) { 444 for (S = S->getParent(); S; S = S->getParent()) 445 if (S->getEntity()) 446 return static_cast<DeclContext *>(S->getEntity())->getPrimaryContext(); 447 448 return 0; 449} 450 451bool 452Sema::CppLookupName(LookupResult &R, Scope *S, DeclarationName Name, 453 LookupNameKind NameKind, bool RedeclarationOnly) { 454 assert(getLangOptions().CPlusPlus && 455 "Can perform only C++ lookup"); 456 unsigned IDNS 457 = getIdentifierNamespacesFromLookupNameKind(NameKind, /*CPlusPlus*/ true); 458 459 // If we're testing for redeclarations, also look in the friend namespaces. 460 if (RedeclarationOnly) { 461 if (IDNS & Decl::IDNS_Tag) IDNS |= Decl::IDNS_TagFriend; 462 if (IDNS & Decl::IDNS_Ordinary) IDNS |= Decl::IDNS_OrdinaryFriend; 463 } 464 465 Scope *Initial = S; 466 IdentifierResolver::iterator 467 I = IdResolver.begin(Name), 468 IEnd = IdResolver.end(); 469 470 // First we lookup local scope. 471 // We don't consider using-directives, as per 7.3.4.p1 [namespace.udir] 472 // ...During unqualified name lookup (3.4.1), the names appear as if 473 // they were declared in the nearest enclosing namespace which contains 474 // both the using-directive and the nominated namespace. 475 // [Note: in this context, "contains" means "contains directly or 476 // indirectly". 477 // 478 // For example: 479 // namespace A { int i; } 480 // void foo() { 481 // int i; 482 // { 483 // using namespace A; 484 // ++i; // finds local 'i', A::i appears at global scope 485 // } 486 // } 487 // 488 for (; S && !isNamespaceOrTranslationUnitScope(S); S = S->getParent()) { 489 // Check whether the IdResolver has anything in this scope. 490 bool Found = false; 491 for (; I != IEnd && S->isDeclScope(DeclPtrTy::make(*I)); ++I) { 492 if (isAcceptableLookupResult(*I, NameKind, IDNS)) { 493 Found = true; 494 R.addDecl(*I); 495 } 496 } 497 if (Found) { 498 R.resolveKind(); 499 return true; 500 } 501 502 if (DeclContext *Ctx = static_cast<DeclContext*>(S->getEntity())) { 503 DeclContext *OuterCtx = findOuterContext(S); 504 for (; Ctx && Ctx->getPrimaryContext() != OuterCtx; 505 Ctx = Ctx->getLookupParent()) { 506 if (Ctx->isFunctionOrMethod()) 507 continue; 508 509 // Perform qualified name lookup into this context. 510 // FIXME: In some cases, we know that every name that could be found by 511 // this qualified name lookup will also be on the identifier chain. For 512 // example, inside a class without any base classes, we never need to 513 // perform qualified lookup because all of the members are on top of the 514 // identifier chain. 515 if (LookupQualifiedName(R, Ctx, Name, NameKind, RedeclarationOnly)) 516 return true; 517 } 518 } 519 } 520 521 // Stop if we ran out of scopes. 522 // FIXME: This really, really shouldn't be happening. 523 if (!S) return false; 524 525 // Collect UsingDirectiveDecls in all scopes, and recursively all 526 // nominated namespaces by those using-directives. 527 // 528 // FIXME: Cache this sorted list in Scope structure, and DeclContext, so we 529 // don't build it for each lookup! 530 531 UnqualUsingDirectiveSet UDirs; 532 UDirs.visitScopeChain(Initial, S); 533 UDirs.done(); 534 535 // Lookup namespace scope, and global scope. 536 // Unqualified name lookup in C++ requires looking into scopes 537 // that aren't strictly lexical, and therefore we walk through the 538 // context as well as walking through the scopes. 539 540 for (; S; S = S->getParent()) { 541 DeclContext *Ctx = static_cast<DeclContext *>(S->getEntity()); 542 if (Ctx->isTransparentContext()) 543 continue; 544 545 assert(Ctx && Ctx->isFileContext() && 546 "We should have been looking only at file context here already."); 547 548 // Check whether the IdResolver has anything in this scope. 549 bool Found = false; 550 for (; I != IEnd && S->isDeclScope(DeclPtrTy::make(*I)); ++I) { 551 if (isAcceptableLookupResult(*I, NameKind, IDNS)) { 552 // We found something. Look for anything else in our scope 553 // with this same name and in an acceptable identifier 554 // namespace, so that we can construct an overload set if we 555 // need to. 556 Found = true; 557 R.addDecl(*I); 558 } 559 } 560 561 // Look into context considering using-directives. 562 if (CppNamespaceLookup(R, Context, Ctx, Name, NameKind, IDNS, UDirs)) 563 Found = true; 564 565 if (Found) { 566 R.resolveKind(); 567 return true; 568 } 569 570 if (RedeclarationOnly && !Ctx->isTransparentContext()) 571 return false; 572 } 573 574 return !R.empty(); 575} 576 577/// @brief Perform unqualified name lookup starting from a given 578/// scope. 579/// 580/// Unqualified name lookup (C++ [basic.lookup.unqual], C99 6.2.1) is 581/// used to find names within the current scope. For example, 'x' in 582/// @code 583/// int x; 584/// int f() { 585/// return x; // unqualified name look finds 'x' in the global scope 586/// } 587/// @endcode 588/// 589/// Different lookup criteria can find different names. For example, a 590/// particular scope can have both a struct and a function of the same 591/// name, and each can be found by certain lookup criteria. For more 592/// information about lookup criteria, see the documentation for the 593/// class LookupCriteria. 594/// 595/// @param S The scope from which unqualified name lookup will 596/// begin. If the lookup criteria permits, name lookup may also search 597/// in the parent scopes. 598/// 599/// @param Name The name of the entity that we are searching for. 600/// 601/// @param Loc If provided, the source location where we're performing 602/// name lookup. At present, this is only used to produce diagnostics when 603/// C library functions (like "malloc") are implicitly declared. 604/// 605/// @returns The result of name lookup, which includes zero or more 606/// declarations and possibly additional information used to diagnose 607/// ambiguities. 608bool Sema::LookupName(LookupResult &R, Scope *S, DeclarationName Name, 609 LookupNameKind NameKind, bool RedeclarationOnly, 610 bool AllowBuiltinCreation, SourceLocation Loc) { 611 if (!Name) return false; 612 613 if (!getLangOptions().CPlusPlus) { 614 // Unqualified name lookup in C/Objective-C is purely lexical, so 615 // search in the declarations attached to the name. 616 unsigned IDNS = 0; 617 switch (NameKind) { 618 case Sema::LookupOrdinaryName: 619 IDNS = Decl::IDNS_Ordinary; 620 break; 621 622 case Sema::LookupTagName: 623 IDNS = Decl::IDNS_Tag; 624 break; 625 626 case Sema::LookupMemberName: 627 IDNS = Decl::IDNS_Member; 628 break; 629 630 case Sema::LookupOperatorName: 631 case Sema::LookupNestedNameSpecifierName: 632 case Sema::LookupNamespaceName: 633 assert(false && "C does not perform these kinds of name lookup"); 634 break; 635 636 case Sema::LookupRedeclarationWithLinkage: 637 // Find the nearest non-transparent declaration scope. 638 while (!(S->getFlags() & Scope::DeclScope) || 639 (S->getEntity() && 640 static_cast<DeclContext *>(S->getEntity()) 641 ->isTransparentContext())) 642 S = S->getParent(); 643 IDNS = Decl::IDNS_Ordinary; 644 break; 645 646 case Sema::LookupObjCProtocolName: 647 IDNS = Decl::IDNS_ObjCProtocol; 648 break; 649 650 case Sema::LookupObjCImplementationName: 651 IDNS = Decl::IDNS_ObjCImplementation; 652 break; 653 654 case Sema::LookupObjCCategoryImplName: 655 IDNS = Decl::IDNS_ObjCCategoryImpl; 656 break; 657 } 658 659 // Scan up the scope chain looking for a decl that matches this 660 // identifier that is in the appropriate namespace. This search 661 // should not take long, as shadowing of names is uncommon, and 662 // deep shadowing is extremely uncommon. 663 bool LeftStartingScope = false; 664 665 for (IdentifierResolver::iterator I = IdResolver.begin(Name), 666 IEnd = IdResolver.end(); 667 I != IEnd; ++I) 668 if ((*I)->isInIdentifierNamespace(IDNS)) { 669 if (NameKind == LookupRedeclarationWithLinkage) { 670 // Determine whether this (or a previous) declaration is 671 // out-of-scope. 672 if (!LeftStartingScope && !S->isDeclScope(DeclPtrTy::make(*I))) 673 LeftStartingScope = true; 674 675 // If we found something outside of our starting scope that 676 // does not have linkage, skip it. 677 if (LeftStartingScope && !((*I)->hasLinkage())) 678 continue; 679 } 680 681 R.addDecl(*I); 682 683 if ((*I)->getAttr<OverloadableAttr>()) { 684 // If this declaration has the "overloadable" attribute, we 685 // might have a set of overloaded functions. 686 687 // Figure out what scope the identifier is in. 688 while (!(S->getFlags() & Scope::DeclScope) || 689 !S->isDeclScope(DeclPtrTy::make(*I))) 690 S = S->getParent(); 691 692 // Find the last declaration in this scope (with the same 693 // name, naturally). 694 IdentifierResolver::iterator LastI = I; 695 for (++LastI; LastI != IEnd; ++LastI) { 696 if (!S->isDeclScope(DeclPtrTy::make(*LastI))) 697 break; 698 R.addDecl(*LastI); 699 } 700 } 701 702 R.resolveKind(); 703 704 return true; 705 } 706 } else { 707 // Perform C++ unqualified name lookup. 708 if (CppLookupName(R, S, Name, NameKind, RedeclarationOnly)) 709 return true; 710 } 711 712 // If we didn't find a use of this identifier, and if the identifier 713 // corresponds to a compiler builtin, create the decl object for the builtin 714 // now, injecting it into translation unit scope, and return it. 715 if (NameKind == LookupOrdinaryName || 716 NameKind == LookupRedeclarationWithLinkage) { 717 IdentifierInfo *II = Name.getAsIdentifierInfo(); 718 if (II && AllowBuiltinCreation) { 719 // If this is a builtin on this (or all) targets, create the decl. 720 if (unsigned BuiltinID = II->getBuiltinID()) { 721 // In C++, we don't have any predefined library functions like 722 // 'malloc'. Instead, we'll just error. 723 if (getLangOptions().CPlusPlus && 724 Context.BuiltinInfo.isPredefinedLibFunction(BuiltinID)) 725 return false; 726 727 NamedDecl *D = LazilyCreateBuiltin((IdentifierInfo *)II, BuiltinID, 728 S, RedeclarationOnly, Loc); 729 if (D) R.addDecl(D); 730 return (D != NULL); 731 } 732 } 733 } 734 return false; 735} 736 737/// @brief Perform qualified name lookup in the namespaces nominated by 738/// using directives by the given context. 739/// 740/// C++98 [namespace.qual]p2: 741/// Given X::m (where X is a user-declared namespace), or given ::m 742/// (where X is the global namespace), let S be the set of all 743/// declarations of m in X and in the transitive closure of all 744/// namespaces nominated by using-directives in X and its used 745/// namespaces, except that using-directives are ignored in any 746/// namespace, including X, directly containing one or more 747/// declarations of m. No namespace is searched more than once in 748/// the lookup of a name. If S is the empty set, the program is 749/// ill-formed. Otherwise, if S has exactly one member, or if the 750/// context of the reference is a using-declaration 751/// (namespace.udecl), S is the required set of declarations of 752/// m. Otherwise if the use of m is not one that allows a unique 753/// declaration to be chosen from S, the program is ill-formed. 754/// C++98 [namespace.qual]p5: 755/// During the lookup of a qualified namespace member name, if the 756/// lookup finds more than one declaration of the member, and if one 757/// declaration introduces a class name or enumeration name and the 758/// other declarations either introduce the same object, the same 759/// enumerator or a set of functions, the non-type name hides the 760/// class or enumeration name if and only if the declarations are 761/// from the same namespace; otherwise (the declarations are from 762/// different namespaces), the program is ill-formed. 763static bool LookupQualifiedNameInUsingDirectives(Sema::LookupResult &R, 764 DeclContext *StartDC, 765 DeclarationName Name, 766 Sema::LookupNameKind NameKind, 767 unsigned IDNS) { 768 assert(StartDC->isFileContext() && "start context is not a file context"); 769 770 DeclContext::udir_iterator I = StartDC->using_directives_begin(); 771 DeclContext::udir_iterator E = StartDC->using_directives_end(); 772 773 if (I == E) return false; 774 775 // We have at least added all these contexts to the queue. 776 llvm::DenseSet<DeclContext*> Visited; 777 Visited.insert(StartDC); 778 779 // We have not yet looked into these namespaces, much less added 780 // their "using-children" to the queue. 781 llvm::SmallVector<NamespaceDecl*, 8> Queue; 782 783 // We have already looked into the initial namespace; seed the queue 784 // with its using-children. 785 for (; I != E; ++I) { 786 NamespaceDecl *ND = (*I)->getNominatedNamespace()->getOriginalNamespace(); 787 if (Visited.insert(ND).second) 788 Queue.push_back(ND); 789 } 790 791 // The easiest way to implement the restriction in [namespace.qual]p5 792 // is to check whether any of the individual results found a tag 793 // and, if so, to declare an ambiguity if the final result is not 794 // a tag. 795 bool FoundTag = false; 796 bool FoundNonTag = false; 797 798 Sema::LookupResult LocalR; 799 800 bool Found = false; 801 while (!Queue.empty()) { 802 NamespaceDecl *ND = Queue.back(); 803 Queue.pop_back(); 804 805 // We go through some convolutions here to avoid copying results 806 // between LookupResults. 807 bool UseLocal = !R.empty(); 808 Sema::LookupResult &DirectR = UseLocal ? LocalR : R; 809 bool FoundDirect = LookupDirect(DirectR, ND, Name, NameKind, IDNS); 810 811 if (FoundDirect) { 812 // First do any local hiding. 813 DirectR.resolveKind(); 814 815 // If the local result is a tag, remember that. 816 if (DirectR.isSingleTagDecl()) 817 FoundTag = true; 818 else 819 FoundNonTag = true; 820 821 // Append the local results to the total results if necessary. 822 if (UseLocal) { 823 R.addAllDecls(LocalR); 824 LocalR.clear(); 825 } 826 } 827 828 // If we find names in this namespace, ignore its using directives. 829 if (FoundDirect) { 830 Found = true; 831 continue; 832 } 833 834 for (llvm::tie(I,E) = ND->getUsingDirectives(); I != E; ++I) { 835 NamespaceDecl *Nom = (*I)->getNominatedNamespace(); 836 if (Visited.insert(Nom).second) 837 Queue.push_back(Nom); 838 } 839 } 840 841 if (Found) { 842 if (FoundTag && FoundNonTag) 843 R.setAmbiguousQualifiedTagHiding(); 844 else 845 R.resolveKind(); 846 } 847 848 return Found; 849} 850 851/// @brief Perform qualified name lookup into a given context. 852/// 853/// Qualified name lookup (C++ [basic.lookup.qual]) is used to find 854/// names when the context of those names is explicit specified, e.g., 855/// "std::vector" or "x->member". 856/// 857/// Different lookup criteria can find different names. For example, a 858/// particular scope can have both a struct and a function of the same 859/// name, and each can be found by certain lookup criteria. For more 860/// information about lookup criteria, see the documentation for the 861/// class LookupCriteria. 862/// 863/// @param LookupCtx The context in which qualified name lookup will 864/// search. If the lookup criteria permits, name lookup may also search 865/// in the parent contexts or (for C++ classes) base classes. 866/// 867/// @param Name The name of the entity that we are searching for. 868/// 869/// @param Criteria The criteria that this routine will use to 870/// determine which names are visible and which names will be 871/// found. Note that name lookup will find a name that is visible by 872/// the given criteria, but the entity itself may not be semantically 873/// correct or even the kind of entity expected based on the 874/// lookup. For example, searching for a nested-name-specifier name 875/// might result in an EnumDecl, which is visible but is not permitted 876/// as a nested-name-specifier in C++03. 877/// 878/// @returns The result of name lookup, which includes zero or more 879/// declarations and possibly additional information used to diagnose 880/// ambiguities. 881bool Sema::LookupQualifiedName(LookupResult &R, DeclContext *LookupCtx, 882 DeclarationName Name, LookupNameKind NameKind, 883 bool RedeclarationOnly) { 884 assert(LookupCtx && "Sema::LookupQualifiedName requires a lookup context"); 885 886 if (!Name) 887 return false; 888 889 // If we're performing qualified name lookup (e.g., lookup into a 890 // struct), find fields as part of ordinary name lookup. 891 unsigned IDNS 892 = getIdentifierNamespacesFromLookupNameKind(NameKind, 893 getLangOptions().CPlusPlus); 894 if (NameKind == LookupOrdinaryName) 895 IDNS |= Decl::IDNS_Member; 896 897 // Make sure that the declaration context is complete. 898 assert((!isa<TagDecl>(LookupCtx) || 899 LookupCtx->isDependentContext() || 900 cast<TagDecl>(LookupCtx)->isDefinition() || 901 Context.getTypeDeclType(cast<TagDecl>(LookupCtx))->getAs<TagType>() 902 ->isBeingDefined()) && 903 "Declaration context must already be complete!"); 904 905 // Perform qualified name lookup into the LookupCtx. 906 if (LookupDirect(R, LookupCtx, Name, NameKind, IDNS)) { 907 R.resolveKind(); 908 return true; 909 } 910 911 // Don't descend into implied contexts for redeclarations. 912 // C++98 [namespace.qual]p6: 913 // In a declaration for a namespace member in which the 914 // declarator-id is a qualified-id, given that the qualified-id 915 // for the namespace member has the form 916 // nested-name-specifier unqualified-id 917 // the unqualified-id shall name a member of the namespace 918 // designated by the nested-name-specifier. 919 // See also [class.mfct]p5 and [class.static.data]p2. 920 if (RedeclarationOnly) 921 return false; 922 923 // If this is a namespace, look it up in 924 if (LookupCtx->isFileContext()) 925 return LookupQualifiedNameInUsingDirectives(R, LookupCtx, Name, NameKind, 926 IDNS); 927 928 // If this isn't a C++ class, we aren't allowed to look into base 929 // classes, we're done. 930 if (!isa<CXXRecordDecl>(LookupCtx)) 931 return false; 932 933 // Perform lookup into our base classes. 934 CXXRecordDecl *LookupRec = cast<CXXRecordDecl>(LookupCtx); 935 CXXBasePaths Paths; 936 Paths.setOrigin(LookupRec); 937 938 // Look for this member in our base classes 939 CXXRecordDecl::BaseMatchesCallback *BaseCallback = 0; 940 switch (NameKind) { 941 case LookupOrdinaryName: 942 case LookupMemberName: 943 case LookupRedeclarationWithLinkage: 944 BaseCallback = &CXXRecordDecl::FindOrdinaryMember; 945 break; 946 947 case LookupTagName: 948 BaseCallback = &CXXRecordDecl::FindTagMember; 949 break; 950 951 case LookupOperatorName: 952 case LookupNamespaceName: 953 case LookupObjCProtocolName: 954 case LookupObjCImplementationName: 955 case LookupObjCCategoryImplName: 956 // These lookups will never find a member in a C++ class (or base class). 957 return false; 958 959 case LookupNestedNameSpecifierName: 960 BaseCallback = &CXXRecordDecl::FindNestedNameSpecifierMember; 961 break; 962 } 963 964 if (!LookupRec->lookupInBases(BaseCallback, Name.getAsOpaquePtr(), Paths)) 965 return false; 966 967 // C++ [class.member.lookup]p2: 968 // [...] If the resulting set of declarations are not all from 969 // sub-objects of the same type, or the set has a nonstatic member 970 // and includes members from distinct sub-objects, there is an 971 // ambiguity and the program is ill-formed. Otherwise that set is 972 // the result of the lookup. 973 // FIXME: support using declarations! 974 QualType SubobjectType; 975 int SubobjectNumber = 0; 976 for (CXXBasePaths::paths_iterator Path = Paths.begin(), PathEnd = Paths.end(); 977 Path != PathEnd; ++Path) { 978 const CXXBasePathElement &PathElement = Path->back(); 979 980 // Determine whether we're looking at a distinct sub-object or not. 981 if (SubobjectType.isNull()) { 982 // This is the first subobject we've looked at. Record its type. 983 SubobjectType = Context.getCanonicalType(PathElement.Base->getType()); 984 SubobjectNumber = PathElement.SubobjectNumber; 985 } else if (SubobjectType 986 != Context.getCanonicalType(PathElement.Base->getType())) { 987 // We found members of the given name in two subobjects of 988 // different types. This lookup is ambiguous. 989 R.setAmbiguousBaseSubobjectTypes(Paths); 990 return true; 991 } else if (SubobjectNumber != PathElement.SubobjectNumber) { 992 // We have a different subobject of the same type. 993 994 // C++ [class.member.lookup]p5: 995 // A static member, a nested type or an enumerator defined in 996 // a base class T can unambiguously be found even if an object 997 // has more than one base class subobject of type T. 998 Decl *FirstDecl = *Path->Decls.first; 999 if (isa<VarDecl>(FirstDecl) || 1000 isa<TypeDecl>(FirstDecl) || 1001 isa<EnumConstantDecl>(FirstDecl)) 1002 continue; 1003 1004 if (isa<CXXMethodDecl>(FirstDecl)) { 1005 // Determine whether all of the methods are static. 1006 bool AllMethodsAreStatic = true; 1007 for (DeclContext::lookup_iterator Func = Path->Decls.first; 1008 Func != Path->Decls.second; ++Func) { 1009 if (!isa<CXXMethodDecl>(*Func)) { 1010 assert(isa<TagDecl>(*Func) && "Non-function must be a tag decl"); 1011 break; 1012 } 1013 1014 if (!cast<CXXMethodDecl>(*Func)->isStatic()) { 1015 AllMethodsAreStatic = false; 1016 break; 1017 } 1018 } 1019 1020 if (AllMethodsAreStatic) 1021 continue; 1022 } 1023 1024 // We have found a nonstatic member name in multiple, distinct 1025 // subobjects. Name lookup is ambiguous. 1026 R.setAmbiguousBaseSubobjects(Paths); 1027 return true; 1028 } 1029 } 1030 1031 // Lookup in a base class succeeded; return these results. 1032 1033 DeclContext::lookup_iterator I, E; 1034 for (llvm::tie(I,E) = Paths.front().Decls; I != E; ++I) 1035 R.addDecl(*I); 1036 R.resolveKind(); 1037 return true; 1038} 1039 1040/// @brief Performs name lookup for a name that was parsed in the 1041/// source code, and may contain a C++ scope specifier. 1042/// 1043/// This routine is a convenience routine meant to be called from 1044/// contexts that receive a name and an optional C++ scope specifier 1045/// (e.g., "N::M::x"). It will then perform either qualified or 1046/// unqualified name lookup (with LookupQualifiedName or LookupName, 1047/// respectively) on the given name and return those results. 1048/// 1049/// @param S The scope from which unqualified name lookup will 1050/// begin. 1051/// 1052/// @param SS An optional C++ scope-specifier, e.g., "::N::M". 1053/// 1054/// @param Name The name of the entity that name lookup will 1055/// search for. 1056/// 1057/// @param Loc If provided, the source location where we're performing 1058/// name lookup. At present, this is only used to produce diagnostics when 1059/// C library functions (like "malloc") are implicitly declared. 1060/// 1061/// @param EnteringContext Indicates whether we are going to enter the 1062/// context of the scope-specifier SS (if present). 1063/// 1064/// @returns True if any decls were found (but possibly ambiguous) 1065bool Sema::LookupParsedName(LookupResult &R, Scope *S, const CXXScopeSpec *SS, 1066 DeclarationName Name, LookupNameKind NameKind, 1067 bool RedeclarationOnly, bool AllowBuiltinCreation, 1068 SourceLocation Loc, 1069 bool EnteringContext) { 1070 if (SS && SS->isInvalid()) { 1071 // When the scope specifier is invalid, don't even look for 1072 // anything. 1073 return false; 1074 } 1075 1076 if (SS && SS->isSet()) { 1077 if (DeclContext *DC = computeDeclContext(*SS, EnteringContext)) { 1078 // We have resolved the scope specifier to a particular declaration 1079 // contex, and will perform name lookup in that context. 1080 if (!DC->isDependentContext() && RequireCompleteDeclContext(*SS)) 1081 return false; 1082 1083 return LookupQualifiedName(R, DC, Name, NameKind, RedeclarationOnly); 1084 } 1085 1086 // We could not resolve the scope specified to a specific declaration 1087 // context, which means that SS refers to an unknown specialization. 1088 // Name lookup can't find anything in this case. 1089 return false; 1090 } 1091 1092 // Perform unqualified name lookup starting in the given scope. 1093 return LookupName(R, S, Name, NameKind, RedeclarationOnly, 1094 AllowBuiltinCreation, Loc); 1095} 1096 1097 1098/// @brief Produce a diagnostic describing the ambiguity that resulted 1099/// from name lookup. 1100/// 1101/// @param Result The ambiguous name lookup result. 1102/// 1103/// @param Name The name of the entity that name lookup was 1104/// searching for. 1105/// 1106/// @param NameLoc The location of the name within the source code. 1107/// 1108/// @param LookupRange A source range that provides more 1109/// source-location information concerning the lookup itself. For 1110/// example, this range might highlight a nested-name-specifier that 1111/// precedes the name. 1112/// 1113/// @returns true 1114bool Sema::DiagnoseAmbiguousLookup(LookupResult &Result, DeclarationName Name, 1115 SourceLocation NameLoc, 1116 SourceRange LookupRange) { 1117 assert(Result.isAmbiguous() && "Lookup result must be ambiguous"); 1118 1119 switch (Result.getAmbiguityKind()) { 1120 case LookupResult::AmbiguousBaseSubobjects: { 1121 CXXBasePaths *Paths = Result.getBasePaths(); 1122 QualType SubobjectType = Paths->front().back().Base->getType(); 1123 Diag(NameLoc, diag::err_ambiguous_member_multiple_subobjects) 1124 << Name << SubobjectType << getAmbiguousPathsDisplayString(*Paths) 1125 << LookupRange; 1126 1127 DeclContext::lookup_iterator Found = Paths->front().Decls.first; 1128 while (isa<CXXMethodDecl>(*Found) && 1129 cast<CXXMethodDecl>(*Found)->isStatic()) 1130 ++Found; 1131 1132 Diag((*Found)->getLocation(), diag::note_ambiguous_member_found); 1133 1134 return true; 1135 } 1136 1137 case LookupResult::AmbiguousBaseSubobjectTypes: { 1138 Diag(NameLoc, diag::err_ambiguous_member_multiple_subobject_types) 1139 << Name << LookupRange; 1140 1141 CXXBasePaths *Paths = Result.getBasePaths(); 1142 std::set<Decl *> DeclsPrinted; 1143 for (CXXBasePaths::paths_iterator Path = Paths->begin(), 1144 PathEnd = Paths->end(); 1145 Path != PathEnd; ++Path) { 1146 Decl *D = *Path->Decls.first; 1147 if (DeclsPrinted.insert(D).second) 1148 Diag(D->getLocation(), diag::note_ambiguous_member_found); 1149 } 1150 1151 return true; 1152 } 1153 1154 case LookupResult::AmbiguousTagHiding: { 1155 Diag(NameLoc, diag::err_ambiguous_tag_hiding) << Name << LookupRange; 1156 1157 llvm::SmallPtrSet<NamedDecl*,8> TagDecls; 1158 1159 LookupResult::iterator DI, DE = Result.end(); 1160 for (DI = Result.begin(); DI != DE; ++DI) 1161 if (TagDecl *TD = dyn_cast<TagDecl>(*DI)) { 1162 TagDecls.insert(TD); 1163 Diag(TD->getLocation(), diag::note_hidden_tag); 1164 } 1165 1166 for (DI = Result.begin(); DI != DE; ++DI) 1167 if (!isa<TagDecl>(*DI)) 1168 Diag((*DI)->getLocation(), diag::note_hiding_object); 1169 1170 // For recovery purposes, go ahead and implement the hiding. 1171 Result.hideDecls(TagDecls); 1172 1173 return true; 1174 } 1175 1176 case LookupResult::AmbiguousReference: { 1177 Diag(NameLoc, diag::err_ambiguous_reference) << Name << LookupRange; 1178 1179 LookupResult::iterator DI = Result.begin(), DE = Result.end(); 1180 for (; DI != DE; ++DI) 1181 Diag((*DI)->getLocation(), diag::note_ambiguous_candidate) << *DI; 1182 1183 return true; 1184 } 1185 } 1186 1187 llvm::llvm_unreachable("unknown ambiguity kind"); 1188 return true; 1189} 1190 1191static void 1192addAssociatedClassesAndNamespaces(QualType T, 1193 ASTContext &Context, 1194 Sema::AssociatedNamespaceSet &AssociatedNamespaces, 1195 Sema::AssociatedClassSet &AssociatedClasses); 1196 1197static void CollectNamespace(Sema::AssociatedNamespaceSet &Namespaces, 1198 DeclContext *Ctx) { 1199 if (Ctx->isFileContext()) 1200 Namespaces.insert(Ctx); 1201} 1202 1203// \brief Add the associated classes and namespaces for argument-dependent 1204// lookup that involves a template argument (C++ [basic.lookup.koenig]p2). 1205static void 1206addAssociatedClassesAndNamespaces(const TemplateArgument &Arg, 1207 ASTContext &Context, 1208 Sema::AssociatedNamespaceSet &AssociatedNamespaces, 1209 Sema::AssociatedClassSet &AssociatedClasses) { 1210 // C++ [basic.lookup.koenig]p2, last bullet: 1211 // -- [...] ; 1212 switch (Arg.getKind()) { 1213 case TemplateArgument::Null: 1214 break; 1215 1216 case TemplateArgument::Type: 1217 // [...] the namespaces and classes associated with the types of the 1218 // template arguments provided for template type parameters (excluding 1219 // template template parameters) 1220 addAssociatedClassesAndNamespaces(Arg.getAsType(), Context, 1221 AssociatedNamespaces, 1222 AssociatedClasses); 1223 break; 1224 1225 case TemplateArgument::Declaration: 1226 // [...] the namespaces in which any template template arguments are 1227 // defined; and the classes in which any member templates used as 1228 // template template arguments are defined. 1229 if (ClassTemplateDecl *ClassTemplate 1230 = dyn_cast<ClassTemplateDecl>(Arg.getAsDecl())) { 1231 DeclContext *Ctx = ClassTemplate->getDeclContext(); 1232 if (CXXRecordDecl *EnclosingClass = dyn_cast<CXXRecordDecl>(Ctx)) 1233 AssociatedClasses.insert(EnclosingClass); 1234 // Add the associated namespace for this class. 1235 while (Ctx->isRecord()) 1236 Ctx = Ctx->getParent(); 1237 CollectNamespace(AssociatedNamespaces, Ctx); 1238 } 1239 break; 1240 1241 case TemplateArgument::Integral: 1242 case TemplateArgument::Expression: 1243 // [Note: non-type template arguments do not contribute to the set of 1244 // associated namespaces. ] 1245 break; 1246 1247 case TemplateArgument::Pack: 1248 for (TemplateArgument::pack_iterator P = Arg.pack_begin(), 1249 PEnd = Arg.pack_end(); 1250 P != PEnd; ++P) 1251 addAssociatedClassesAndNamespaces(*P, Context, 1252 AssociatedNamespaces, 1253 AssociatedClasses); 1254 break; 1255 } 1256} 1257 1258// \brief Add the associated classes and namespaces for 1259// argument-dependent lookup with an argument of class type 1260// (C++ [basic.lookup.koenig]p2). 1261static void 1262addAssociatedClassesAndNamespaces(CXXRecordDecl *Class, 1263 ASTContext &Context, 1264 Sema::AssociatedNamespaceSet &AssociatedNamespaces, 1265 Sema::AssociatedClassSet &AssociatedClasses) { 1266 // C++ [basic.lookup.koenig]p2: 1267 // [...] 1268 // -- If T is a class type (including unions), its associated 1269 // classes are: the class itself; the class of which it is a 1270 // member, if any; and its direct and indirect base 1271 // classes. Its associated namespaces are the namespaces in 1272 // which its associated classes are defined. 1273 1274 // Add the class of which it is a member, if any. 1275 DeclContext *Ctx = Class->getDeclContext(); 1276 if (CXXRecordDecl *EnclosingClass = dyn_cast<CXXRecordDecl>(Ctx)) 1277 AssociatedClasses.insert(EnclosingClass); 1278 // Add the associated namespace for this class. 1279 while (Ctx->isRecord()) 1280 Ctx = Ctx->getParent(); 1281 CollectNamespace(AssociatedNamespaces, Ctx); 1282 1283 // Add the class itself. If we've already seen this class, we don't 1284 // need to visit base classes. 1285 if (!AssociatedClasses.insert(Class)) 1286 return; 1287 1288 // -- If T is a template-id, its associated namespaces and classes are 1289 // the namespace in which the template is defined; for member 1290 // templates, the member template’s class; the namespaces and classes 1291 // associated with the types of the template arguments provided for 1292 // template type parameters (excluding template template parameters); the 1293 // namespaces in which any template template arguments are defined; and 1294 // the classes in which any member templates used as template template 1295 // arguments are defined. [Note: non-type template arguments do not 1296 // contribute to the set of associated namespaces. ] 1297 if (ClassTemplateSpecializationDecl *Spec 1298 = dyn_cast<ClassTemplateSpecializationDecl>(Class)) { 1299 DeclContext *Ctx = Spec->getSpecializedTemplate()->getDeclContext(); 1300 if (CXXRecordDecl *EnclosingClass = dyn_cast<CXXRecordDecl>(Ctx)) 1301 AssociatedClasses.insert(EnclosingClass); 1302 // Add the associated namespace for this class. 1303 while (Ctx->isRecord()) 1304 Ctx = Ctx->getParent(); 1305 CollectNamespace(AssociatedNamespaces, Ctx); 1306 1307 const TemplateArgumentList &TemplateArgs = Spec->getTemplateArgs(); 1308 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I) 1309 addAssociatedClassesAndNamespaces(TemplateArgs[I], Context, 1310 AssociatedNamespaces, 1311 AssociatedClasses); 1312 } 1313 1314 // Add direct and indirect base classes along with their associated 1315 // namespaces. 1316 llvm::SmallVector<CXXRecordDecl *, 32> Bases; 1317 Bases.push_back(Class); 1318 while (!Bases.empty()) { 1319 // Pop this class off the stack. 1320 Class = Bases.back(); 1321 Bases.pop_back(); 1322 1323 // Visit the base classes. 1324 for (CXXRecordDecl::base_class_iterator Base = Class->bases_begin(), 1325 BaseEnd = Class->bases_end(); 1326 Base != BaseEnd; ++Base) { 1327 const RecordType *BaseType = Base->getType()->getAs<RecordType>(); 1328 // In dependent contexts, we do ADL twice, and the first time around, 1329 // the base type might be a dependent TemplateSpecializationType, or a 1330 // TemplateTypeParmType. If that happens, simply ignore it. 1331 // FIXME: If we want to support export, we probably need to add the 1332 // namespace of the template in a TemplateSpecializationType, or even 1333 // the classes and namespaces of known non-dependent arguments. 1334 if (!BaseType) 1335 continue; 1336 CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(BaseType->getDecl()); 1337 if (AssociatedClasses.insert(BaseDecl)) { 1338 // Find the associated namespace for this base class. 1339 DeclContext *BaseCtx = BaseDecl->getDeclContext(); 1340 while (BaseCtx->isRecord()) 1341 BaseCtx = BaseCtx->getParent(); 1342 CollectNamespace(AssociatedNamespaces, BaseCtx); 1343 1344 // Make sure we visit the bases of this base class. 1345 if (BaseDecl->bases_begin() != BaseDecl->bases_end()) 1346 Bases.push_back(BaseDecl); 1347 } 1348 } 1349 } 1350} 1351 1352// \brief Add the associated classes and namespaces for 1353// argument-dependent lookup with an argument of type T 1354// (C++ [basic.lookup.koenig]p2). 1355static void 1356addAssociatedClassesAndNamespaces(QualType T, 1357 ASTContext &Context, 1358 Sema::AssociatedNamespaceSet &AssociatedNamespaces, 1359 Sema::AssociatedClassSet &AssociatedClasses) { 1360 // C++ [basic.lookup.koenig]p2: 1361 // 1362 // For each argument type T in the function call, there is a set 1363 // of zero or more associated namespaces and a set of zero or more 1364 // associated classes to be considered. The sets of namespaces and 1365 // classes is determined entirely by the types of the function 1366 // arguments (and the namespace of any template template 1367 // argument). Typedef names and using-declarations used to specify 1368 // the types do not contribute to this set. The sets of namespaces 1369 // and classes are determined in the following way: 1370 T = Context.getCanonicalType(T).getUnqualifiedType(); 1371 1372 // -- If T is a pointer to U or an array of U, its associated 1373 // namespaces and classes are those associated with U. 1374 // 1375 // We handle this by unwrapping pointer and array types immediately, 1376 // to avoid unnecessary recursion. 1377 while (true) { 1378 if (const PointerType *Ptr = T->getAs<PointerType>()) 1379 T = Ptr->getPointeeType(); 1380 else if (const ArrayType *Ptr = Context.getAsArrayType(T)) 1381 T = Ptr->getElementType(); 1382 else 1383 break; 1384 } 1385 1386 // -- If T is a fundamental type, its associated sets of 1387 // namespaces and classes are both empty. 1388 if (T->getAs<BuiltinType>()) 1389 return; 1390 1391 // -- If T is a class type (including unions), its associated 1392 // classes are: the class itself; the class of which it is a 1393 // member, if any; and its direct and indirect base 1394 // classes. Its associated namespaces are the namespaces in 1395 // which its associated classes are defined. 1396 if (const RecordType *ClassType = T->getAs<RecordType>()) 1397 if (CXXRecordDecl *ClassDecl 1398 = dyn_cast<CXXRecordDecl>(ClassType->getDecl())) { 1399 addAssociatedClassesAndNamespaces(ClassDecl, Context, 1400 AssociatedNamespaces, 1401 AssociatedClasses); 1402 return; 1403 } 1404 1405 // -- If T is an enumeration type, its associated namespace is 1406 // the namespace in which it is defined. If it is class 1407 // member, its associated class is the member’s class; else 1408 // it has no associated class. 1409 if (const EnumType *EnumT = T->getAs<EnumType>()) { 1410 EnumDecl *Enum = EnumT->getDecl(); 1411 1412 DeclContext *Ctx = Enum->getDeclContext(); 1413 if (CXXRecordDecl *EnclosingClass = dyn_cast<CXXRecordDecl>(Ctx)) 1414 AssociatedClasses.insert(EnclosingClass); 1415 1416 // Add the associated namespace for this class. 1417 while (Ctx->isRecord()) 1418 Ctx = Ctx->getParent(); 1419 CollectNamespace(AssociatedNamespaces, Ctx); 1420 1421 return; 1422 } 1423 1424 // -- If T is a function type, its associated namespaces and 1425 // classes are those associated with the function parameter 1426 // types and those associated with the return type. 1427 if (const FunctionType *FnType = T->getAs<FunctionType>()) { 1428 // Return type 1429 addAssociatedClassesAndNamespaces(FnType->getResultType(), 1430 Context, 1431 AssociatedNamespaces, AssociatedClasses); 1432 1433 const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FnType); 1434 if (!Proto) 1435 return; 1436 1437 // Argument types 1438 for (FunctionProtoType::arg_type_iterator Arg = Proto->arg_type_begin(), 1439 ArgEnd = Proto->arg_type_end(); 1440 Arg != ArgEnd; ++Arg) 1441 addAssociatedClassesAndNamespaces(*Arg, Context, 1442 AssociatedNamespaces, AssociatedClasses); 1443 1444 return; 1445 } 1446 1447 // -- If T is a pointer to a member function of a class X, its 1448 // associated namespaces and classes are those associated 1449 // with the function parameter types and return type, 1450 // together with those associated with X. 1451 // 1452 // -- If T is a pointer to a data member of class X, its 1453 // associated namespaces and classes are those associated 1454 // with the member type together with those associated with 1455 // X. 1456 if (const MemberPointerType *MemberPtr = T->getAs<MemberPointerType>()) { 1457 // Handle the type that the pointer to member points to. 1458 addAssociatedClassesAndNamespaces(MemberPtr->getPointeeType(), 1459 Context, 1460 AssociatedNamespaces, 1461 AssociatedClasses); 1462 1463 // Handle the class type into which this points. 1464 if (const RecordType *Class = MemberPtr->getClass()->getAs<RecordType>()) 1465 addAssociatedClassesAndNamespaces(cast<CXXRecordDecl>(Class->getDecl()), 1466 Context, 1467 AssociatedNamespaces, 1468 AssociatedClasses); 1469 1470 return; 1471 } 1472 1473 // FIXME: What about block pointers? 1474 // FIXME: What about Objective-C message sends? 1475} 1476 1477/// \brief Find the associated classes and namespaces for 1478/// argument-dependent lookup for a call with the given set of 1479/// arguments. 1480/// 1481/// This routine computes the sets of associated classes and associated 1482/// namespaces searched by argument-dependent lookup 1483/// (C++ [basic.lookup.argdep]) for a given set of arguments. 1484void 1485Sema::FindAssociatedClassesAndNamespaces(Expr **Args, unsigned NumArgs, 1486 AssociatedNamespaceSet &AssociatedNamespaces, 1487 AssociatedClassSet &AssociatedClasses) { 1488 AssociatedNamespaces.clear(); 1489 AssociatedClasses.clear(); 1490 1491 // C++ [basic.lookup.koenig]p2: 1492 // For each argument type T in the function call, there is a set 1493 // of zero or more associated namespaces and a set of zero or more 1494 // associated classes to be considered. The sets of namespaces and 1495 // classes is determined entirely by the types of the function 1496 // arguments (and the namespace of any template template 1497 // argument). 1498 for (unsigned ArgIdx = 0; ArgIdx != NumArgs; ++ArgIdx) { 1499 Expr *Arg = Args[ArgIdx]; 1500 1501 if (Arg->getType() != Context.OverloadTy) { 1502 addAssociatedClassesAndNamespaces(Arg->getType(), Context, 1503 AssociatedNamespaces, 1504 AssociatedClasses); 1505 continue; 1506 } 1507 1508 // [...] In addition, if the argument is the name or address of a 1509 // set of overloaded functions and/or function templates, its 1510 // associated classes and namespaces are the union of those 1511 // associated with each of the members of the set: the namespace 1512 // in which the function or function template is defined and the 1513 // classes and namespaces associated with its (non-dependent) 1514 // parameter types and return type. 1515 DeclRefExpr *DRE = 0; 1516 TemplateIdRefExpr *TIRE = 0; 1517 Arg = Arg->IgnoreParens(); 1518 if (UnaryOperator *unaryOp = dyn_cast<UnaryOperator>(Arg)) { 1519 if (unaryOp->getOpcode() == UnaryOperator::AddrOf) { 1520 DRE = dyn_cast<DeclRefExpr>(unaryOp->getSubExpr()); 1521 TIRE = dyn_cast<TemplateIdRefExpr>(unaryOp->getSubExpr()); 1522 } 1523 } else { 1524 DRE = dyn_cast<DeclRefExpr>(Arg); 1525 TIRE = dyn_cast<TemplateIdRefExpr>(Arg); 1526 } 1527 1528 OverloadedFunctionDecl *Ovl = 0; 1529 if (DRE) 1530 Ovl = dyn_cast<OverloadedFunctionDecl>(DRE->getDecl()); 1531 else if (TIRE) 1532 Ovl = TIRE->getTemplateName().getAsOverloadedFunctionDecl(); 1533 if (!Ovl) 1534 continue; 1535 1536 for (OverloadedFunctionDecl::function_iterator Func = Ovl->function_begin(), 1537 FuncEnd = Ovl->function_end(); 1538 Func != FuncEnd; ++Func) { 1539 FunctionDecl *FDecl = dyn_cast<FunctionDecl>(*Func); 1540 if (!FDecl) 1541 FDecl = cast<FunctionTemplateDecl>(*Func)->getTemplatedDecl(); 1542 1543 // Add the namespace in which this function was defined. Note 1544 // that, if this is a member function, we do *not* consider the 1545 // enclosing namespace of its class. 1546 DeclContext *Ctx = FDecl->getDeclContext(); 1547 CollectNamespace(AssociatedNamespaces, Ctx); 1548 1549 // Add the classes and namespaces associated with the parameter 1550 // types and return type of this function. 1551 addAssociatedClassesAndNamespaces(FDecl->getType(), Context, 1552 AssociatedNamespaces, 1553 AssociatedClasses); 1554 } 1555 } 1556} 1557 1558/// IsAcceptableNonMemberOperatorCandidate - Determine whether Fn is 1559/// an acceptable non-member overloaded operator for a call whose 1560/// arguments have types T1 (and, if non-empty, T2). This routine 1561/// implements the check in C++ [over.match.oper]p3b2 concerning 1562/// enumeration types. 1563static bool 1564IsAcceptableNonMemberOperatorCandidate(FunctionDecl *Fn, 1565 QualType T1, QualType T2, 1566 ASTContext &Context) { 1567 if (T1->isDependentType() || (!T2.isNull() && T2->isDependentType())) 1568 return true; 1569 1570 if (T1->isRecordType() || (!T2.isNull() && T2->isRecordType())) 1571 return true; 1572 1573 const FunctionProtoType *Proto = Fn->getType()->getAs<FunctionProtoType>(); 1574 if (Proto->getNumArgs() < 1) 1575 return false; 1576 1577 if (T1->isEnumeralType()) { 1578 QualType ArgType = Proto->getArgType(0).getNonReferenceType(); 1579 if (Context.getCanonicalType(T1).getUnqualifiedType() 1580 == Context.getCanonicalType(ArgType).getUnqualifiedType()) 1581 return true; 1582 } 1583 1584 if (Proto->getNumArgs() < 2) 1585 return false; 1586 1587 if (!T2.isNull() && T2->isEnumeralType()) { 1588 QualType ArgType = Proto->getArgType(1).getNonReferenceType(); 1589 if (Context.getCanonicalType(T2).getUnqualifiedType() 1590 == Context.getCanonicalType(ArgType).getUnqualifiedType()) 1591 return true; 1592 } 1593 1594 return false; 1595} 1596 1597/// \brief Find the protocol with the given name, if any. 1598ObjCProtocolDecl *Sema::LookupProtocol(IdentifierInfo *II) { 1599 Decl *D = LookupSingleName(TUScope, II, LookupObjCProtocolName); 1600 return cast_or_null<ObjCProtocolDecl>(D); 1601} 1602 1603/// \brief Find the Objective-C category implementation with the given 1604/// name, if any. 1605ObjCCategoryImplDecl *Sema::LookupObjCCategoryImpl(IdentifierInfo *II) { 1606 Decl *D = LookupSingleName(TUScope, II, LookupObjCCategoryImplName); 1607 return cast_or_null<ObjCCategoryImplDecl>(D); 1608} 1609 1610void Sema::LookupOverloadedOperatorName(OverloadedOperatorKind Op, Scope *S, 1611 QualType T1, QualType T2, 1612 FunctionSet &Functions) { 1613 // C++ [over.match.oper]p3: 1614 // -- The set of non-member candidates is the result of the 1615 // unqualified lookup of operator@ in the context of the 1616 // expression according to the usual rules for name lookup in 1617 // unqualified function calls (3.4.2) except that all member 1618 // functions are ignored. However, if no operand has a class 1619 // type, only those non-member functions in the lookup set 1620 // that have a first parameter of type T1 or "reference to 1621 // (possibly cv-qualified) T1", when T1 is an enumeration 1622 // type, or (if there is a right operand) a second parameter 1623 // of type T2 or "reference to (possibly cv-qualified) T2", 1624 // when T2 is an enumeration type, are candidate functions. 1625 DeclarationName OpName = Context.DeclarationNames.getCXXOperatorName(Op); 1626 LookupResult Operators; 1627 LookupName(Operators, S, OpName, LookupOperatorName); 1628 1629 assert(!Operators.isAmbiguous() && "Operator lookup cannot be ambiguous"); 1630 1631 if (Operators.empty()) 1632 return; 1633 1634 for (LookupResult::iterator Op = Operators.begin(), OpEnd = Operators.end(); 1635 Op != OpEnd; ++Op) { 1636 if (FunctionDecl *FD = dyn_cast<FunctionDecl>(*Op)) { 1637 if (IsAcceptableNonMemberOperatorCandidate(FD, T1, T2, Context)) 1638 Functions.insert(FD); // FIXME: canonical FD 1639 } else if (FunctionTemplateDecl *FunTmpl 1640 = dyn_cast<FunctionTemplateDecl>(*Op)) { 1641 // FIXME: friend operators? 1642 // FIXME: do we need to check IsAcceptableNonMemberOperatorCandidate, 1643 // later? 1644 if (!FunTmpl->getDeclContext()->isRecord()) 1645 Functions.insert(FunTmpl); 1646 } 1647 } 1648} 1649 1650static void CollectFunctionDecl(Sema::FunctionSet &Functions, 1651 Decl *D) { 1652 if (FunctionDecl *Func = dyn_cast<FunctionDecl>(D)) 1653 Functions.insert(Func); 1654 else if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) 1655 Functions.insert(FunTmpl); 1656} 1657 1658void Sema::ArgumentDependentLookup(DeclarationName Name, bool Operator, 1659 Expr **Args, unsigned NumArgs, 1660 FunctionSet &Functions) { 1661 // Find all of the associated namespaces and classes based on the 1662 // arguments we have. 1663 AssociatedNamespaceSet AssociatedNamespaces; 1664 AssociatedClassSet AssociatedClasses; 1665 FindAssociatedClassesAndNamespaces(Args, NumArgs, 1666 AssociatedNamespaces, 1667 AssociatedClasses); 1668 1669 QualType T1, T2; 1670 if (Operator) { 1671 T1 = Args[0]->getType(); 1672 if (NumArgs >= 2) 1673 T2 = Args[1]->getType(); 1674 } 1675 1676 // C++ [basic.lookup.argdep]p3: 1677 // Let X be the lookup set produced by unqualified lookup (3.4.1) 1678 // and let Y be the lookup set produced by argument dependent 1679 // lookup (defined as follows). If X contains [...] then Y is 1680 // empty. Otherwise Y is the set of declarations found in the 1681 // namespaces associated with the argument types as described 1682 // below. The set of declarations found by the lookup of the name 1683 // is the union of X and Y. 1684 // 1685 // Here, we compute Y and add its members to the overloaded 1686 // candidate set. 1687 for (AssociatedNamespaceSet::iterator NS = AssociatedNamespaces.begin(), 1688 NSEnd = AssociatedNamespaces.end(); 1689 NS != NSEnd; ++NS) { 1690 // When considering an associated namespace, the lookup is the 1691 // same as the lookup performed when the associated namespace is 1692 // used as a qualifier (3.4.3.2) except that: 1693 // 1694 // -- Any using-directives in the associated namespace are 1695 // ignored. 1696 // 1697 // -- Any namespace-scope friend functions declared in 1698 // associated classes are visible within their respective 1699 // namespaces even if they are not visible during an ordinary 1700 // lookup (11.4). 1701 DeclContext::lookup_iterator I, E; 1702 for (llvm::tie(I, E) = (*NS)->lookup(Name); I != E; ++I) { 1703 Decl *D = *I; 1704 // If the only declaration here is an ordinary friend, consider 1705 // it only if it was declared in an associated classes. 1706 if (D->getIdentifierNamespace() == Decl::IDNS_OrdinaryFriend) { 1707 DeclContext *LexDC = D->getLexicalDeclContext(); 1708 if (!AssociatedClasses.count(cast<CXXRecordDecl>(LexDC))) 1709 continue; 1710 } 1711 1712 FunctionDecl *Fn; 1713 if (!Operator || !(Fn = dyn_cast<FunctionDecl>(D)) || 1714 IsAcceptableNonMemberOperatorCandidate(Fn, T1, T2, Context)) 1715 CollectFunctionDecl(Functions, D); 1716 } 1717 } 1718} 1719