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