SemaLookup.cpp revision ff7bf10d1cb8274573589a41fd570396d7abb2ed
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 (DeclContext *Ctx = static_cast<DeclContext*>(S->getEntity())) { 94 DeclContext *EffectiveDC = (Ctx->isFileContext() ? Ctx : InnermostFileDC); 95 visit(Ctx, EffectiveDC); 96 } else { 97 Scope::udir_iterator I = S->using_directives_begin(), 98 End = S->using_directives_end(); 99 100 for (; I != End; ++I) 101 visit(I->getAs<UsingDirectiveDecl>(), InnermostFileDC); 102 } 103 } 104 } 105 106 // Visits a context and collect all of its using directives 107 // recursively. Treats all using directives as if they were 108 // declared in the context. 109 // 110 // A given context is only every visited once, so it is important 111 // that contexts be visited from the inside out in order to get 112 // the effective DCs right. 113 void visit(DeclContext *DC, DeclContext *EffectiveDC) { 114 if (!visited.insert(DC)) 115 return; 116 117 addUsingDirectives(DC, EffectiveDC); 118 } 119 120 // Visits a using directive and collects all of its using 121 // directives recursively. Treats all using directives as if they 122 // were declared in the effective DC. 123 void visit(UsingDirectiveDecl *UD, DeclContext *EffectiveDC) { 124 DeclContext *NS = UD->getNominatedNamespace(); 125 if (!visited.insert(NS)) 126 return; 127 128 addUsingDirective(UD, EffectiveDC); 129 addUsingDirectives(NS, EffectiveDC); 130 } 131 132 // Adds all the using directives in a context (and those nominated 133 // by its using directives, transitively) as if they appeared in 134 // the given effective context. 135 void addUsingDirectives(DeclContext *DC, DeclContext *EffectiveDC) { 136 llvm::SmallVector<DeclContext*,4> queue; 137 while (true) { 138 DeclContext::udir_iterator I, End; 139 for (llvm::tie(I, End) = DC->getUsingDirectives(); I != End; ++I) { 140 UsingDirectiveDecl *UD = *I; 141 DeclContext *NS = UD->getNominatedNamespace(); 142 if (visited.insert(NS)) { 143 addUsingDirective(UD, EffectiveDC); 144 queue.push_back(NS); 145 } 146 } 147 148 if (queue.empty()) 149 return; 150 151 DC = queue.back(); 152 queue.pop_back(); 153 } 154 } 155 156 // Add a using directive as if it had been declared in the given 157 // context. This helps implement C++ [namespace.udir]p3: 158 // The using-directive is transitive: if a scope contains a 159 // using-directive that nominates a second namespace that itself 160 // contains using-directives, the effect is as if the 161 // using-directives from the second namespace also appeared in 162 // the first. 163 void addUsingDirective(UsingDirectiveDecl *UD, DeclContext *EffectiveDC) { 164 // Find the common ancestor between the effective context and 165 // the nominated namespace. 166 DeclContext *Common = UD->getNominatedNamespace(); 167 while (!Common->Encloses(EffectiveDC)) 168 Common = Common->getParent(); 169 Common = Common->getPrimaryContext(); 170 171 list.push_back(UnqualUsingEntry(UD->getNominatedNamespace(), Common)); 172 } 173 174 void done() { 175 std::sort(list.begin(), list.end(), UnqualUsingEntry::Comparator()); 176 } 177 178 typedef ListTy::iterator iterator; 179 typedef ListTy::const_iterator const_iterator; 180 181 iterator begin() { return list.begin(); } 182 iterator end() { return list.end(); } 183 const_iterator begin() const { return list.begin(); } 184 const_iterator end() const { return list.end(); } 185 186 std::pair<const_iterator,const_iterator> 187 getNamespacesFor(DeclContext *DC) const { 188 return std::equal_range(begin(), end(), DC->getPrimaryContext(), 189 UnqualUsingEntry::Comparator()); 190 } 191 }; 192} 193 194// Retrieve the set of identifier namespaces that correspond to a 195// specific kind of name lookup. 196inline unsigned 197getIdentifierNamespacesFromLookupNameKind(Sema::LookupNameKind NameKind, 198 bool CPlusPlus) { 199 unsigned IDNS = 0; 200 switch (NameKind) { 201 case Sema::LookupOrdinaryName: 202 case Sema::LookupOperatorName: 203 case Sema::LookupRedeclarationWithLinkage: 204 IDNS = Decl::IDNS_Ordinary; 205 if (CPlusPlus) 206 IDNS |= Decl::IDNS_Tag | Decl::IDNS_Member; 207 break; 208 209 case Sema::LookupTagName: 210 IDNS = Decl::IDNS_Tag; 211 break; 212 213 case Sema::LookupMemberName: 214 IDNS = Decl::IDNS_Member; 215 if (CPlusPlus) 216 IDNS |= Decl::IDNS_Tag | Decl::IDNS_Ordinary; 217 break; 218 219 case Sema::LookupNestedNameSpecifierName: 220 case Sema::LookupNamespaceName: 221 IDNS = Decl::IDNS_Ordinary | Decl::IDNS_Tag | Decl::IDNS_Member; 222 break; 223 224 case Sema::LookupObjCProtocolName: 225 IDNS = Decl::IDNS_ObjCProtocol; 226 break; 227 228 case Sema::LookupObjCImplementationName: 229 IDNS = Decl::IDNS_ObjCImplementation; 230 break; 231 232 case Sema::LookupObjCCategoryImplName: 233 IDNS = Decl::IDNS_ObjCCategoryImpl; 234 break; 235 } 236 return IDNS; 237} 238 239// Necessary because CXXBasePaths is not complete in Sema.h 240void Sema::LookupResult::deletePaths(CXXBasePaths *Paths) { 241 delete Paths; 242} 243 244void Sema::LookupResult::resolveKind() { 245 unsigned N = Decls.size(); 246 247 // Fast case: no possible ambiguity. 248 if (N <= 1) return; 249 250 // Don't do any extra resolution if we've already resolved as ambiguous. 251 if (ResultKind == Ambiguous) return; 252 253 llvm::SmallPtrSet<NamedDecl*, 16> Unique; 254 255 bool Ambiguous = false; 256 bool HasTag = false, HasFunction = false, HasNonFunction = false; 257 258 unsigned UniqueTagIndex = 0; 259 260 unsigned I = 0; 261 while (I < N) { 262 NamedDecl *D = Decls[I]; 263 assert(D == D->getUnderlyingDecl()); 264 265 NamedDecl *CanonD = cast<NamedDecl>(D->getCanonicalDecl()); 266 if (!Unique.insert(CanonD)) { 267 // If it's not unique, pull something off the back (and 268 // continue at this index). 269 Decls[I] = Decls[--N]; 270 } else if (isa<UnresolvedUsingDecl>(D)) { 271 // FIXME: proper support for UnresolvedUsingDecls. 272 Decls[I] = Decls[--N]; 273 } else { 274 // Otherwise, do some decl type analysis and then continue. 275 if (isa<TagDecl>(D)) { 276 if (HasTag) 277 Ambiguous = true; 278 UniqueTagIndex = I; 279 HasTag = true; 280 } else if (D->isFunctionOrFunctionTemplate()) { 281 HasFunction = true; 282 } else { 283 if (HasNonFunction) 284 Ambiguous = true; 285 HasNonFunction = true; 286 } 287 I++; 288 } 289 } 290 291 // C++ [basic.scope.hiding]p2: 292 // A class name or enumeration name can be hidden by the name of 293 // an object, function, or enumerator declared in the same 294 // scope. If a class or enumeration name and an object, function, 295 // or enumerator are declared in the same scope (in any order) 296 // with the same name, the class or enumeration name is hidden 297 // wherever the object, function, or enumerator name is visible. 298 // But it's still an error if there are distinct tag types found, 299 // even if they're not visible. (ref?) 300 if (HasTag && !Ambiguous && (HasFunction || HasNonFunction)) 301 Decls[UniqueTagIndex] = Decls[--N]; 302 303 Decls.set_size(N); 304 305 if (HasFunction && HasNonFunction) 306 Ambiguous = true; 307 308 if (Ambiguous) 309 setAmbiguous(LookupResult::AmbiguousReference); 310 else if (N > 1) 311 ResultKind = LookupResult::FoundOverloaded; 312 else 313 ResultKind = LookupResult::Found; 314} 315 316/// @brief Converts the result of name lookup into a single (possible 317/// NULL) pointer to a declaration. 318/// 319/// The resulting declaration will either be the declaration we found 320/// (if only a single declaration was found), an 321/// OverloadedFunctionDecl (if an overloaded function was found), or 322/// NULL (if no declaration was found). This conversion must not be 323/// used anywhere where name lookup could result in an ambiguity. 324/// 325/// The OverloadedFunctionDecl conversion is meant as a stop-gap 326/// solution, since it causes the OverloadedFunctionDecl to be 327/// leaked. FIXME: Eventually, there will be a better way to iterate 328/// over the set of overloaded functions returned by name lookup. 329NamedDecl *Sema::LookupResult::getAsSingleDecl(ASTContext &C) const { 330 size_t size = Decls.size(); 331 if (size == 0) return 0; 332 if (size == 1) return *begin(); 333 334 if (isAmbiguous()) return 0; 335 336 iterator I = begin(), E = end(); 337 338 OverloadedFunctionDecl *Ovl 339 = OverloadedFunctionDecl::Create(C, (*I)->getDeclContext(), 340 (*I)->getDeclName()); 341 for (; I != E; ++I) { 342 NamedDecl *ND = *I; 343 assert(ND->getUnderlyingDecl() == ND 344 && "decls in lookup result should have redirections stripped"); 345 assert(ND->isFunctionOrFunctionTemplate()); 346 if (isa<FunctionDecl>(ND)) 347 Ovl->addOverload(cast<FunctionDecl>(ND)); 348 else 349 Ovl->addOverload(cast<FunctionTemplateDecl>(ND)); 350 // FIXME: UnresolvedUsingDecls. 351 } 352 353 return Ovl; 354} 355 356void Sema::LookupResult::addDeclsFromBasePaths(const CXXBasePaths &P) { 357 CXXBasePaths::paths_iterator I, E; 358 DeclContext::lookup_iterator DI, DE; 359 for (I = P.begin(), E = P.end(); I != E; ++I) 360 for (llvm::tie(DI,DE) = I->Decls; DI != DE; ++DI) 361 addDecl(*DI); 362} 363 364void Sema::LookupResult::setAmbiguousBaseSubobjects(CXXBasePaths &P) { 365 Paths = new CXXBasePaths; 366 Paths->swap(P); 367 addDeclsFromBasePaths(*Paths); 368 resolveKind(); 369 setAmbiguous(AmbiguousBaseSubobjects); 370} 371 372void Sema::LookupResult::setAmbiguousBaseSubobjectTypes(CXXBasePaths &P) { 373 Paths = new CXXBasePaths; 374 Paths->swap(P); 375 addDeclsFromBasePaths(*Paths); 376 resolveKind(); 377 setAmbiguous(AmbiguousBaseSubobjectTypes); 378} 379 380void Sema::LookupResult::print(llvm::raw_ostream &Out) { 381 Out << Decls.size() << " result(s)"; 382 if (isAmbiguous()) Out << ", ambiguous"; 383 if (Paths) Out << ", base paths present"; 384 385 for (iterator I = begin(), E = end(); I != E; ++I) { 386 Out << "\n"; 387 (*I)->print(Out, 2); 388 } 389} 390 391// Adds all qualifying matches for a name within a decl context to the 392// given lookup result. Returns true if any matches were found. 393static bool LookupDirect(Sema::LookupResult &R, 394 const DeclContext *DC) { 395 bool Found = false; 396 397 DeclContext::lookup_const_iterator I, E; 398 for (llvm::tie(I, E) = DC->lookup(R.getLookupName()); I != E; ++I) 399 if (Sema::isAcceptableLookupResult(*I, R.getLookupKind(), 400 R.getIdentifierNamespace())) 401 R.addDecl(*I), Found = true; 402 403 return Found; 404} 405 406// Performs C++ unqualified lookup into the given file context. 407static bool 408CppNamespaceLookup(Sema::LookupResult &R, ASTContext &Context, DeclContext *NS, 409 UnqualUsingDirectiveSet &UDirs) { 410 411 assert(NS && NS->isFileContext() && "CppNamespaceLookup() requires namespace!"); 412 413 // Perform direct name lookup into the LookupCtx. 414 bool Found = LookupDirect(R, NS); 415 416 // Perform direct name lookup into the namespaces nominated by the 417 // using directives whose common ancestor is this namespace. 418 UnqualUsingDirectiveSet::const_iterator UI, UEnd; 419 llvm::tie(UI, UEnd) = UDirs.getNamespacesFor(NS); 420 421 for (; UI != UEnd; ++UI) 422 if (LookupDirect(R, UI->getNominatedNamespace())) 423 Found = true; 424 425 R.resolveKind(); 426 427 return Found; 428} 429 430static bool isNamespaceOrTranslationUnitScope(Scope *S) { 431 if (DeclContext *Ctx = static_cast<DeclContext*>(S->getEntity())) 432 return Ctx->isFileContext(); 433 return false; 434} 435 436// Find the next outer declaration context corresponding to this scope. 437static DeclContext *findOuterContext(Scope *S) { 438 for (S = S->getParent(); S; S = S->getParent()) 439 if (S->getEntity()) 440 return static_cast<DeclContext *>(S->getEntity())->getPrimaryContext(); 441 442 return 0; 443} 444 445bool Sema::CppLookupName(LookupResult &R, Scope *S) { 446 assert(getLangOptions().CPlusPlus && 447 "Can perform only C++ lookup"); 448 LookupNameKind NameKind = R.getLookupKind(); 449 unsigned IDNS 450 = getIdentifierNamespacesFromLookupNameKind(NameKind, /*CPlusPlus*/ true); 451 452 // If we're testing for redeclarations, also look in the friend namespaces. 453 if (R.isForRedeclaration()) { 454 if (IDNS & Decl::IDNS_Tag) IDNS |= Decl::IDNS_TagFriend; 455 if (IDNS & Decl::IDNS_Ordinary) IDNS |= Decl::IDNS_OrdinaryFriend; 456 } 457 458 R.setIdentifierNamespace(IDNS); 459 460 DeclarationName Name = R.getLookupName(); 461 462 Scope *Initial = S; 463 IdentifierResolver::iterator 464 I = IdResolver.begin(Name), 465 IEnd = IdResolver.end(); 466 467 // First we lookup local scope. 468 // We don't consider using-directives, as per 7.3.4.p1 [namespace.udir] 469 // ...During unqualified name lookup (3.4.1), the names appear as if 470 // they were declared in the nearest enclosing namespace which contains 471 // both the using-directive and the nominated namespace. 472 // [Note: in this context, "contains" means "contains directly or 473 // indirectly". 474 // 475 // For example: 476 // namespace A { int i; } 477 // void foo() { 478 // int i; 479 // { 480 // using namespace A; 481 // ++i; // finds local 'i', A::i appears at global scope 482 // } 483 // } 484 // 485 for (; S && !isNamespaceOrTranslationUnitScope(S); S = S->getParent()) { 486 // Check whether the IdResolver has anything in this scope. 487 bool Found = false; 488 for (; I != IEnd && S->isDeclScope(DeclPtrTy::make(*I)); ++I) { 489 if (isAcceptableLookupResult(*I, NameKind, IDNS)) { 490 Found = true; 491 R.addDecl(*I); 492 } 493 } 494 if (Found) { 495 R.resolveKind(); 496 return true; 497 } 498 499 if (DeclContext *Ctx = static_cast<DeclContext*>(S->getEntity())) { 500 DeclContext *OuterCtx = findOuterContext(S); 501 for (; Ctx && Ctx->getPrimaryContext() != OuterCtx; 502 Ctx = Ctx->getLookupParent()) { 503 if (Ctx->isFunctionOrMethod()) 504 continue; 505 506 // Perform qualified name lookup into this context. 507 // FIXME: In some cases, we know that every name that could be found by 508 // this qualified name lookup will also be on the identifier chain. For 509 // example, inside a class without any base classes, we never need to 510 // perform qualified lookup because all of the members are on top of the 511 // identifier chain. 512 if (LookupQualifiedName(R, Ctx)) 513 return true; 514 } 515 } 516 } 517 518 // Stop if we ran out of scopes. 519 // FIXME: This really, really shouldn't be happening. 520 if (!S) return false; 521 522 // Collect UsingDirectiveDecls in all scopes, and recursively all 523 // nominated namespaces by those using-directives. 524 // 525 // FIXME: Cache this sorted list in Scope structure, and DeclContext, so we 526 // don't build it for each lookup! 527 528 UnqualUsingDirectiveSet UDirs; 529 UDirs.visitScopeChain(Initial, S); 530 UDirs.done(); 531 532 // Lookup namespace scope, and global scope. 533 // Unqualified name lookup in C++ requires looking into scopes 534 // that aren't strictly lexical, and therefore we walk through the 535 // context as well as walking through the scopes. 536 537 for (; S; S = S->getParent()) { 538 DeclContext *Ctx = static_cast<DeclContext *>(S->getEntity()); 539 if (Ctx->isTransparentContext()) 540 continue; 541 542 assert(Ctx && Ctx->isFileContext() && 543 "We should have been looking only at file context here already."); 544 545 // Check whether the IdResolver has anything in this scope. 546 bool Found = false; 547 for (; I != IEnd && S->isDeclScope(DeclPtrTy::make(*I)); ++I) { 548 if (isAcceptableLookupResult(*I, NameKind, IDNS)) { 549 // We found something. Look for anything else in our scope 550 // with this same name and in an acceptable identifier 551 // namespace, so that we can construct an overload set if we 552 // need to. 553 Found = true; 554 R.addDecl(*I); 555 } 556 } 557 558 // Look into context considering using-directives. 559 if (CppNamespaceLookup(R, Context, Ctx, UDirs)) 560 Found = true; 561 562 if (Found) { 563 R.resolveKind(); 564 return true; 565 } 566 567 if (R.isForRedeclaration() && !Ctx->isTransparentContext()) 568 return false; 569 } 570 571 return !R.empty(); 572} 573 574/// @brief Perform unqualified name lookup starting from a given 575/// scope. 576/// 577/// Unqualified name lookup (C++ [basic.lookup.unqual], C99 6.2.1) is 578/// used to find names within the current scope. For example, 'x' in 579/// @code 580/// int x; 581/// int f() { 582/// return x; // unqualified name look finds 'x' in the global scope 583/// } 584/// @endcode 585/// 586/// Different lookup criteria can find different names. For example, a 587/// particular scope can have both a struct and a function of the same 588/// name, and each can be found by certain lookup criteria. For more 589/// information about lookup criteria, see the documentation for the 590/// class LookupCriteria. 591/// 592/// @param S The scope from which unqualified name lookup will 593/// begin. If the lookup criteria permits, name lookup may also search 594/// in the parent scopes. 595/// 596/// @param Name The name of the entity that we are searching for. 597/// 598/// @param Loc If provided, the source location where we're performing 599/// name lookup. At present, this is only used to produce diagnostics when 600/// C library functions (like "malloc") are implicitly declared. 601/// 602/// @returns The result of name lookup, which includes zero or more 603/// declarations and possibly additional information used to diagnose 604/// ambiguities. 605bool Sema::LookupName(LookupResult &R, Scope *S, bool AllowBuiltinCreation) { 606 DeclarationName Name = R.getLookupName(); 607 if (!Name) return false; 608 609 LookupNameKind NameKind = R.getLookupKind(); 610 611 if (!getLangOptions().CPlusPlus) { 612 // Unqualified name lookup in C/Objective-C is purely lexical, so 613 // search in the declarations attached to the name. 614 unsigned IDNS = 0; 615 switch (NameKind) { 616 case Sema::LookupOrdinaryName: 617 IDNS = Decl::IDNS_Ordinary; 618 break; 619 620 case Sema::LookupTagName: 621 IDNS = Decl::IDNS_Tag; 622 break; 623 624 case Sema::LookupMemberName: 625 IDNS = Decl::IDNS_Member; 626 break; 627 628 case Sema::LookupOperatorName: 629 case Sema::LookupNestedNameSpecifierName: 630 case Sema::LookupNamespaceName: 631 assert(false && "C does not perform these kinds of name lookup"); 632 break; 633 634 case Sema::LookupRedeclarationWithLinkage: 635 // Find the nearest non-transparent declaration scope. 636 while (!(S->getFlags() & Scope::DeclScope) || 637 (S->getEntity() && 638 static_cast<DeclContext *>(S->getEntity()) 639 ->isTransparentContext())) 640 S = S->getParent(); 641 IDNS = Decl::IDNS_Ordinary; 642 break; 643 644 case Sema::LookupObjCProtocolName: 645 IDNS = Decl::IDNS_ObjCProtocol; 646 break; 647 648 case Sema::LookupObjCImplementationName: 649 IDNS = Decl::IDNS_ObjCImplementation; 650 break; 651 652 case Sema::LookupObjCCategoryImplName: 653 IDNS = Decl::IDNS_ObjCCategoryImpl; 654 break; 655 } 656 657 // Scan up the scope chain looking for a decl that matches this 658 // identifier that is in the appropriate namespace. This search 659 // should not take long, as shadowing of names is uncommon, and 660 // deep shadowing is extremely uncommon. 661 bool LeftStartingScope = false; 662 663 for (IdentifierResolver::iterator I = IdResolver.begin(Name), 664 IEnd = IdResolver.end(); 665 I != IEnd; ++I) 666 if ((*I)->isInIdentifierNamespace(IDNS)) { 667 if (NameKind == LookupRedeclarationWithLinkage) { 668 // Determine whether this (or a previous) declaration is 669 // out-of-scope. 670 if (!LeftStartingScope && !S->isDeclScope(DeclPtrTy::make(*I))) 671 LeftStartingScope = true; 672 673 // If we found something outside of our starting scope that 674 // does not have linkage, skip it. 675 if (LeftStartingScope && !((*I)->hasLinkage())) 676 continue; 677 } 678 679 R.addDecl(*I); 680 681 if ((*I)->getAttr<OverloadableAttr>()) { 682 // If this declaration has the "overloadable" attribute, we 683 // might have a set of overloaded functions. 684 685 // Figure out what scope the identifier is in. 686 while (!(S->getFlags() & Scope::DeclScope) || 687 !S->isDeclScope(DeclPtrTy::make(*I))) 688 S = S->getParent(); 689 690 // Find the last declaration in this scope (with the same 691 // name, naturally). 692 IdentifierResolver::iterator LastI = I; 693 for (++LastI; LastI != IEnd; ++LastI) { 694 if (!S->isDeclScope(DeclPtrTy::make(*LastI))) 695 break; 696 R.addDecl(*LastI); 697 } 698 } 699 700 R.resolveKind(); 701 702 return true; 703 } 704 } else { 705 // Perform C++ unqualified name lookup. 706 if (CppLookupName(R, S)) 707 return true; 708 } 709 710 // If we didn't find a use of this identifier, and if the identifier 711 // corresponds to a compiler builtin, create the decl object for the builtin 712 // now, injecting it into translation unit scope, and return it. 713 if (NameKind == LookupOrdinaryName || 714 NameKind == LookupRedeclarationWithLinkage) { 715 IdentifierInfo *II = Name.getAsIdentifierInfo(); 716 if (II && AllowBuiltinCreation) { 717 // If this is a builtin on this (or all) targets, create the decl. 718 if (unsigned BuiltinID = II->getBuiltinID()) { 719 // In C++, we don't have any predefined library functions like 720 // 'malloc'. Instead, we'll just error. 721 if (getLangOptions().CPlusPlus && 722 Context.BuiltinInfo.isPredefinedLibFunction(BuiltinID)) 723 return false; 724 725 NamedDecl *D = LazilyCreateBuiltin((IdentifierInfo *)II, BuiltinID, 726 S, R.isForRedeclaration(), 727 R.getNameLoc()); 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 assert(StartDC->isFileContext() && "start context is not a file context"); 765 766 DeclContext::udir_iterator I = StartDC->using_directives_begin(); 767 DeclContext::udir_iterator E = StartDC->using_directives_end(); 768 769 if (I == E) return false; 770 771 // We have at least added all these contexts to the queue. 772 llvm::DenseSet<DeclContext*> Visited; 773 Visited.insert(StartDC); 774 775 // We have not yet looked into these namespaces, much less added 776 // their "using-children" to the queue. 777 llvm::SmallVector<NamespaceDecl*, 8> Queue; 778 779 // We have already looked into the initial namespace; seed the queue 780 // with its using-children. 781 for (; I != E; ++I) { 782 NamespaceDecl *ND = (*I)->getNominatedNamespace()->getOriginalNamespace(); 783 if (Visited.insert(ND).second) 784 Queue.push_back(ND); 785 } 786 787 // The easiest way to implement the restriction in [namespace.qual]p5 788 // is to check whether any of the individual results found a tag 789 // and, if so, to declare an ambiguity if the final result is not 790 // a tag. 791 bool FoundTag = false; 792 bool FoundNonTag = false; 793 794 Sema::LookupResult LocalR(Sema::LookupResult::Temporary, R); 795 796 bool Found = false; 797 while (!Queue.empty()) { 798 NamespaceDecl *ND = Queue.back(); 799 Queue.pop_back(); 800 801 // We go through some convolutions here to avoid copying results 802 // between LookupResults. 803 bool UseLocal = !R.empty(); 804 Sema::LookupResult &DirectR = UseLocal ? LocalR : R; 805 bool FoundDirect = LookupDirect(DirectR, ND); 806 807 if (FoundDirect) { 808 // First do any local hiding. 809 DirectR.resolveKind(); 810 811 // If the local result is a tag, remember that. 812 if (DirectR.isSingleTagDecl()) 813 FoundTag = true; 814 else 815 FoundNonTag = true; 816 817 // Append the local results to the total results if necessary. 818 if (UseLocal) { 819 R.addAllDecls(LocalR); 820 LocalR.clear(); 821 } 822 } 823 824 // If we find names in this namespace, ignore its using directives. 825 if (FoundDirect) { 826 Found = true; 827 continue; 828 } 829 830 for (llvm::tie(I,E) = ND->getUsingDirectives(); I != E; ++I) { 831 NamespaceDecl *Nom = (*I)->getNominatedNamespace(); 832 if (Visited.insert(Nom).second) 833 Queue.push_back(Nom); 834 } 835 } 836 837 if (Found) { 838 if (FoundTag && FoundNonTag) 839 R.setAmbiguousQualifiedTagHiding(); 840 else 841 R.resolveKind(); 842 } 843 844 return Found; 845} 846 847/// @brief Perform qualified name lookup into a given context. 848/// 849/// Qualified name lookup (C++ [basic.lookup.qual]) is used to find 850/// names when the context of those names is explicit specified, e.g., 851/// "std::vector" or "x->member". 852/// 853/// Different lookup criteria can find different names. For example, a 854/// particular scope can have both a struct and a function of the same 855/// name, and each can be found by certain lookup criteria. For more 856/// information about lookup criteria, see the documentation for the 857/// class LookupCriteria. 858/// 859/// @param LookupCtx The context in which qualified name lookup will 860/// search. If the lookup criteria permits, name lookup may also search 861/// in the parent contexts or (for C++ classes) base classes. 862/// 863/// @param Name The name of the entity that we are searching for. 864/// 865/// @param Criteria The criteria that this routine will use to 866/// determine which names are visible and which names will be 867/// found. Note that name lookup will find a name that is visible by 868/// the given criteria, but the entity itself may not be semantically 869/// correct or even the kind of entity expected based on the 870/// lookup. For example, searching for a nested-name-specifier name 871/// might result in an EnumDecl, which is visible but is not permitted 872/// as a nested-name-specifier in C++03. 873/// 874/// @returns The result of name lookup, which includes zero or more 875/// declarations and possibly additional information used to diagnose 876/// ambiguities. 877bool Sema::LookupQualifiedName(LookupResult &R, DeclContext *LookupCtx) { 878 assert(LookupCtx && "Sema::LookupQualifiedName requires a lookup context"); 879 880 if (!R.getLookupName()) 881 return false; 882 883 // If we're performing qualified name lookup (e.g., lookup into a 884 // struct), find fields as part of ordinary name lookup. 885 LookupNameKind NameKind = R.getLookupKind(); 886 unsigned IDNS 887 = getIdentifierNamespacesFromLookupNameKind(NameKind, 888 getLangOptions().CPlusPlus); 889 if (NameKind == LookupOrdinaryName) 890 IDNS |= Decl::IDNS_Member; 891 892 R.setIdentifierNamespace(IDNS); 893 894 // Make sure that the declaration context is complete. 895 assert((!isa<TagDecl>(LookupCtx) || 896 LookupCtx->isDependentContext() || 897 cast<TagDecl>(LookupCtx)->isDefinition() || 898 Context.getTypeDeclType(cast<TagDecl>(LookupCtx))->getAs<TagType>() 899 ->isBeingDefined()) && 900 "Declaration context must already be complete!"); 901 902 // Perform qualified name lookup into the LookupCtx. 903 if (LookupDirect(R, LookupCtx)) { 904 R.resolveKind(); 905 return true; 906 } 907 908 // Don't descend into implied contexts for redeclarations. 909 // C++98 [namespace.qual]p6: 910 // In a declaration for a namespace member in which the 911 // declarator-id is a qualified-id, given that the qualified-id 912 // for the namespace member has the form 913 // nested-name-specifier unqualified-id 914 // the unqualified-id shall name a member of the namespace 915 // designated by the nested-name-specifier. 916 // See also [class.mfct]p5 and [class.static.data]p2. 917 if (R.isForRedeclaration()) 918 return false; 919 920 // If this is a namespace, look it up in the implied namespaces. 921 if (LookupCtx->isFileContext()) 922 return LookupQualifiedNameInUsingDirectives(R, LookupCtx); 923 924 // If this isn't a C++ class, we aren't allowed to look into base 925 // classes, we're done. 926 if (!isa<CXXRecordDecl>(LookupCtx)) 927 return false; 928 929 // Perform lookup into our base classes. 930 CXXRecordDecl *LookupRec = cast<CXXRecordDecl>(LookupCtx); 931 CXXBasePaths Paths; 932 Paths.setOrigin(LookupRec); 933 934 // Look for this member in our base classes 935 CXXRecordDecl::BaseMatchesCallback *BaseCallback = 0; 936 switch (R.getLookupKind()) { 937 case LookupOrdinaryName: 938 case LookupMemberName: 939 case LookupRedeclarationWithLinkage: 940 BaseCallback = &CXXRecordDecl::FindOrdinaryMember; 941 break; 942 943 case LookupTagName: 944 BaseCallback = &CXXRecordDecl::FindTagMember; 945 break; 946 947 case LookupOperatorName: 948 case LookupNamespaceName: 949 case LookupObjCProtocolName: 950 case LookupObjCImplementationName: 951 case LookupObjCCategoryImplName: 952 // These lookups will never find a member in a C++ class (or base class). 953 return false; 954 955 case LookupNestedNameSpecifierName: 956 BaseCallback = &CXXRecordDecl::FindNestedNameSpecifierMember; 957 break; 958 } 959 960 if (!LookupRec->lookupInBases(BaseCallback, 961 R.getLookupName().getAsOpaquePtr(), Paths)) 962 return false; 963 964 // C++ [class.member.lookup]p2: 965 // [...] If the resulting set of declarations are not all from 966 // sub-objects of the same type, or the set has a nonstatic member 967 // and includes members from distinct sub-objects, there is an 968 // ambiguity and the program is ill-formed. Otherwise that set is 969 // the result of the lookup. 970 // FIXME: support using declarations! 971 QualType SubobjectType; 972 int SubobjectNumber = 0; 973 for (CXXBasePaths::paths_iterator Path = Paths.begin(), PathEnd = Paths.end(); 974 Path != PathEnd; ++Path) { 975 const CXXBasePathElement &PathElement = Path->back(); 976 977 // Determine whether we're looking at a distinct sub-object or not. 978 if (SubobjectType.isNull()) { 979 // This is the first subobject we've looked at. Record its type. 980 SubobjectType = Context.getCanonicalType(PathElement.Base->getType()); 981 SubobjectNumber = PathElement.SubobjectNumber; 982 } else if (SubobjectType 983 != Context.getCanonicalType(PathElement.Base->getType())) { 984 // We found members of the given name in two subobjects of 985 // different types. This lookup is ambiguous. 986 R.setAmbiguousBaseSubobjectTypes(Paths); 987 return true; 988 } else if (SubobjectNumber != PathElement.SubobjectNumber) { 989 // We have a different subobject of the same type. 990 991 // C++ [class.member.lookup]p5: 992 // A static member, a nested type or an enumerator defined in 993 // a base class T can unambiguously be found even if an object 994 // has more than one base class subobject of type T. 995 Decl *FirstDecl = *Path->Decls.first; 996 if (isa<VarDecl>(FirstDecl) || 997 isa<TypeDecl>(FirstDecl) || 998 isa<EnumConstantDecl>(FirstDecl)) 999 continue; 1000 1001 if (isa<CXXMethodDecl>(FirstDecl)) { 1002 // Determine whether all of the methods are static. 1003 bool AllMethodsAreStatic = true; 1004 for (DeclContext::lookup_iterator Func = Path->Decls.first; 1005 Func != Path->Decls.second; ++Func) { 1006 if (!isa<CXXMethodDecl>(*Func)) { 1007 assert(isa<TagDecl>(*Func) && "Non-function must be a tag decl"); 1008 break; 1009 } 1010 1011 if (!cast<CXXMethodDecl>(*Func)->isStatic()) { 1012 AllMethodsAreStatic = false; 1013 break; 1014 } 1015 } 1016 1017 if (AllMethodsAreStatic) 1018 continue; 1019 } 1020 1021 // We have found a nonstatic member name in multiple, distinct 1022 // subobjects. Name lookup is ambiguous. 1023 R.setAmbiguousBaseSubobjects(Paths); 1024 return true; 1025 } 1026 } 1027 1028 // Lookup in a base class succeeded; return these results. 1029 1030 DeclContext::lookup_iterator I, E; 1031 for (llvm::tie(I,E) = Paths.front().Decls; I != E; ++I) 1032 R.addDecl(*I); 1033 R.resolveKind(); 1034 return true; 1035} 1036 1037/// @brief Performs name lookup for a name that was parsed in the 1038/// source code, and may contain a C++ scope specifier. 1039/// 1040/// This routine is a convenience routine meant to be called from 1041/// contexts that receive a name and an optional C++ scope specifier 1042/// (e.g., "N::M::x"). It will then perform either qualified or 1043/// unqualified name lookup (with LookupQualifiedName or LookupName, 1044/// respectively) on the given name and return those results. 1045/// 1046/// @param S The scope from which unqualified name lookup will 1047/// begin. 1048/// 1049/// @param SS An optional C++ scope-specifier, e.g., "::N::M". 1050/// 1051/// @param Name The name of the entity that name lookup will 1052/// search for. 1053/// 1054/// @param Loc If provided, the source location where we're performing 1055/// name lookup. At present, this is only used to produce diagnostics when 1056/// C library functions (like "malloc") are implicitly declared. 1057/// 1058/// @param EnteringContext Indicates whether we are going to enter the 1059/// context of the scope-specifier SS (if present). 1060/// 1061/// @returns True if any decls were found (but possibly ambiguous) 1062bool Sema::LookupParsedName(LookupResult &R, Scope *S, const CXXScopeSpec *SS, 1063 bool AllowBuiltinCreation, bool EnteringContext) { 1064 if (SS && SS->isInvalid()) { 1065 // When the scope specifier is invalid, don't even look for 1066 // anything. 1067 return false; 1068 } 1069 1070 if (SS && SS->isSet()) { 1071 if (DeclContext *DC = computeDeclContext(*SS, EnteringContext)) { 1072 // We have resolved the scope specifier to a particular declaration 1073 // contex, and will perform name lookup in that context. 1074 if (!DC->isDependentContext() && RequireCompleteDeclContext(*SS)) 1075 return false; 1076 1077 R.setContextRange(SS->getRange()); 1078 1079 return LookupQualifiedName(R, DC); 1080 } 1081 1082 // We could not resolve the scope specified to a specific declaration 1083 // context, which means that SS refers to an unknown specialization. 1084 // Name lookup can't find anything in this case. 1085 return false; 1086 } 1087 1088 // Perform unqualified name lookup starting in the given scope. 1089 return LookupName(R, S, AllowBuiltinCreation); 1090} 1091 1092 1093/// @brief Produce a diagnostic describing the ambiguity that resulted 1094/// from name lookup. 1095/// 1096/// @param Result The ambiguous name lookup result. 1097/// 1098/// @param Name The name of the entity that name lookup was 1099/// searching for. 1100/// 1101/// @param NameLoc The location of the name within the source code. 1102/// 1103/// @param LookupRange A source range that provides more 1104/// source-location information concerning the lookup itself. For 1105/// example, this range might highlight a nested-name-specifier that 1106/// precedes the name. 1107/// 1108/// @returns true 1109bool Sema::DiagnoseAmbiguousLookup(LookupResult &Result) { 1110 assert(Result.isAmbiguous() && "Lookup result must be ambiguous"); 1111 1112 DeclarationName Name = Result.getLookupName(); 1113 SourceLocation NameLoc = Result.getNameLoc(); 1114 SourceRange LookupRange = Result.getContextRange(); 1115 1116 switch (Result.getAmbiguityKind()) { 1117 case LookupResult::AmbiguousBaseSubobjects: { 1118 CXXBasePaths *Paths = Result.getBasePaths(); 1119 QualType SubobjectType = Paths->front().back().Base->getType(); 1120 Diag(NameLoc, diag::err_ambiguous_member_multiple_subobjects) 1121 << Name << SubobjectType << getAmbiguousPathsDisplayString(*Paths) 1122 << LookupRange; 1123 1124 DeclContext::lookup_iterator Found = Paths->front().Decls.first; 1125 while (isa<CXXMethodDecl>(*Found) && 1126 cast<CXXMethodDecl>(*Found)->isStatic()) 1127 ++Found; 1128 1129 Diag((*Found)->getLocation(), diag::note_ambiguous_member_found); 1130 1131 return true; 1132 } 1133 1134 case LookupResult::AmbiguousBaseSubobjectTypes: { 1135 Diag(NameLoc, diag::err_ambiguous_member_multiple_subobject_types) 1136 << Name << LookupRange; 1137 1138 CXXBasePaths *Paths = Result.getBasePaths(); 1139 std::set<Decl *> DeclsPrinted; 1140 for (CXXBasePaths::paths_iterator Path = Paths->begin(), 1141 PathEnd = Paths->end(); 1142 Path != PathEnd; ++Path) { 1143 Decl *D = *Path->Decls.first; 1144 if (DeclsPrinted.insert(D).second) 1145 Diag(D->getLocation(), diag::note_ambiguous_member_found); 1146 } 1147 1148 return true; 1149 } 1150 1151 case LookupResult::AmbiguousTagHiding: { 1152 Diag(NameLoc, diag::err_ambiguous_tag_hiding) << Name << LookupRange; 1153 1154 llvm::SmallPtrSet<NamedDecl*,8> TagDecls; 1155 1156 LookupResult::iterator DI, DE = Result.end(); 1157 for (DI = Result.begin(); DI != DE; ++DI) 1158 if (TagDecl *TD = dyn_cast<TagDecl>(*DI)) { 1159 TagDecls.insert(TD); 1160 Diag(TD->getLocation(), diag::note_hidden_tag); 1161 } 1162 1163 for (DI = Result.begin(); DI != DE; ++DI) 1164 if (!isa<TagDecl>(*DI)) 1165 Diag((*DI)->getLocation(), diag::note_hiding_object); 1166 1167 // For recovery purposes, go ahead and implement the hiding. 1168 Result.hideDecls(TagDecls); 1169 1170 return true; 1171 } 1172 1173 case LookupResult::AmbiguousReference: { 1174 Diag(NameLoc, diag::err_ambiguous_reference) << Name << LookupRange; 1175 1176 LookupResult::iterator DI = Result.begin(), DE = Result.end(); 1177 for (; DI != DE; ++DI) 1178 Diag((*DI)->getLocation(), diag::note_ambiguous_candidate) << *DI; 1179 1180 return true; 1181 } 1182 } 1183 1184 llvm::llvm_unreachable("unknown ambiguity kind"); 1185 return true; 1186} 1187 1188static void 1189addAssociatedClassesAndNamespaces(QualType T, 1190 ASTContext &Context, 1191 Sema::AssociatedNamespaceSet &AssociatedNamespaces, 1192 Sema::AssociatedClassSet &AssociatedClasses); 1193 1194static void CollectNamespace(Sema::AssociatedNamespaceSet &Namespaces, 1195 DeclContext *Ctx) { 1196 if (Ctx->isFileContext()) 1197 Namespaces.insert(Ctx); 1198} 1199 1200// \brief Add the associated classes and namespaces for argument-dependent 1201// lookup that involves a template argument (C++ [basic.lookup.koenig]p2). 1202static void 1203addAssociatedClassesAndNamespaces(const TemplateArgument &Arg, 1204 ASTContext &Context, 1205 Sema::AssociatedNamespaceSet &AssociatedNamespaces, 1206 Sema::AssociatedClassSet &AssociatedClasses) { 1207 // C++ [basic.lookup.koenig]p2, last bullet: 1208 // -- [...] ; 1209 switch (Arg.getKind()) { 1210 case TemplateArgument::Null: 1211 break; 1212 1213 case TemplateArgument::Type: 1214 // [...] the namespaces and classes associated with the types of the 1215 // template arguments provided for template type parameters (excluding 1216 // template template parameters) 1217 addAssociatedClassesAndNamespaces(Arg.getAsType(), Context, 1218 AssociatedNamespaces, 1219 AssociatedClasses); 1220 break; 1221 1222 case TemplateArgument::Template: { 1223 // [...] the namespaces in which any template template arguments are 1224 // defined; and the classes in which any member templates used as 1225 // template template arguments are defined. 1226 TemplateName Template = Arg.getAsTemplate(); 1227 if (ClassTemplateDecl *ClassTemplate 1228 = dyn_cast<ClassTemplateDecl>(Template.getAsTemplateDecl())) { 1229 DeclContext *Ctx = ClassTemplate->getDeclContext(); 1230 if (CXXRecordDecl *EnclosingClass = dyn_cast<CXXRecordDecl>(Ctx)) 1231 AssociatedClasses.insert(EnclosingClass); 1232 // Add the associated namespace for this class. 1233 while (Ctx->isRecord()) 1234 Ctx = Ctx->getParent(); 1235 CollectNamespace(AssociatedNamespaces, Ctx); 1236 } 1237 break; 1238 } 1239 1240 case TemplateArgument::Declaration: 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.hasSameUnqualifiedType(T1, ArgType)) 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.hasSameUnqualifiedType(T2, ArgType)) 1589 return true; 1590 } 1591 1592 return false; 1593} 1594 1595/// \brief Find the protocol with the given name, if any. 1596ObjCProtocolDecl *Sema::LookupProtocol(IdentifierInfo *II) { 1597 Decl *D = LookupSingleName(TUScope, II, LookupObjCProtocolName); 1598 return cast_or_null<ObjCProtocolDecl>(D); 1599} 1600 1601/// \brief Find the Objective-C category implementation with the given 1602/// name, if any. 1603ObjCCategoryImplDecl *Sema::LookupObjCCategoryImpl(IdentifierInfo *II) { 1604 Decl *D = LookupSingleName(TUScope, II, LookupObjCCategoryImplName); 1605 return cast_or_null<ObjCCategoryImplDecl>(D); 1606} 1607 1608void Sema::LookupOverloadedOperatorName(OverloadedOperatorKind Op, Scope *S, 1609 QualType T1, QualType T2, 1610 FunctionSet &Functions) { 1611 // C++ [over.match.oper]p3: 1612 // -- The set of non-member candidates is the result of the 1613 // unqualified lookup of operator@ in the context of the 1614 // expression according to the usual rules for name lookup in 1615 // unqualified function calls (3.4.2) except that all member 1616 // functions are ignored. However, if no operand has a class 1617 // type, only those non-member functions in the lookup set 1618 // that have a first parameter of type T1 or "reference to 1619 // (possibly cv-qualified) T1", when T1 is an enumeration 1620 // type, or (if there is a right operand) a second parameter 1621 // of type T2 or "reference to (possibly cv-qualified) T2", 1622 // when T2 is an enumeration type, are candidate functions. 1623 DeclarationName OpName = Context.DeclarationNames.getCXXOperatorName(Op); 1624 LookupResult Operators(*this, OpName, SourceLocation(), LookupOperatorName); 1625 LookupName(Operators, S); 1626 1627 assert(!Operators.isAmbiguous() && "Operator lookup cannot be ambiguous"); 1628 1629 if (Operators.empty()) 1630 return; 1631 1632 for (LookupResult::iterator Op = Operators.begin(), OpEnd = Operators.end(); 1633 Op != OpEnd; ++Op) { 1634 if (FunctionDecl *FD = dyn_cast<FunctionDecl>(*Op)) { 1635 if (IsAcceptableNonMemberOperatorCandidate(FD, T1, T2, Context)) 1636 Functions.insert(FD); // FIXME: canonical FD 1637 } else if (FunctionTemplateDecl *FunTmpl 1638 = dyn_cast<FunctionTemplateDecl>(*Op)) { 1639 // FIXME: friend operators? 1640 // FIXME: do we need to check IsAcceptableNonMemberOperatorCandidate, 1641 // later? 1642 if (!FunTmpl->getDeclContext()->isRecord()) 1643 Functions.insert(FunTmpl); 1644 } 1645 } 1646} 1647 1648static void CollectFunctionDecl(Sema::FunctionSet &Functions, 1649 Decl *D) { 1650 if (FunctionDecl *Func = dyn_cast<FunctionDecl>(D)) 1651 Functions.insert(Func); 1652 else if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) 1653 Functions.insert(FunTmpl); 1654} 1655 1656void Sema::ArgumentDependentLookup(DeclarationName Name, bool Operator, 1657 Expr **Args, unsigned NumArgs, 1658 FunctionSet &Functions) { 1659 // Find all of the associated namespaces and classes based on the 1660 // arguments we have. 1661 AssociatedNamespaceSet AssociatedNamespaces; 1662 AssociatedClassSet AssociatedClasses; 1663 FindAssociatedClassesAndNamespaces(Args, NumArgs, 1664 AssociatedNamespaces, 1665 AssociatedClasses); 1666 1667 QualType T1, T2; 1668 if (Operator) { 1669 T1 = Args[0]->getType(); 1670 if (NumArgs >= 2) 1671 T2 = Args[1]->getType(); 1672 } 1673 1674 // C++ [basic.lookup.argdep]p3: 1675 // Let X be the lookup set produced by unqualified lookup (3.4.1) 1676 // and let Y be the lookup set produced by argument dependent 1677 // lookup (defined as follows). If X contains [...] then Y is 1678 // empty. Otherwise Y is the set of declarations found in the 1679 // namespaces associated with the argument types as described 1680 // below. The set of declarations found by the lookup of the name 1681 // is the union of X and Y. 1682 // 1683 // Here, we compute Y and add its members to the overloaded 1684 // candidate set. 1685 for (AssociatedNamespaceSet::iterator NS = AssociatedNamespaces.begin(), 1686 NSEnd = AssociatedNamespaces.end(); 1687 NS != NSEnd; ++NS) { 1688 // When considering an associated namespace, the lookup is the 1689 // same as the lookup performed when the associated namespace is 1690 // used as a qualifier (3.4.3.2) except that: 1691 // 1692 // -- Any using-directives in the associated namespace are 1693 // ignored. 1694 // 1695 // -- Any namespace-scope friend functions declared in 1696 // associated classes are visible within their respective 1697 // namespaces even if they are not visible during an ordinary 1698 // lookup (11.4). 1699 DeclContext::lookup_iterator I, E; 1700 for (llvm::tie(I, E) = (*NS)->lookup(Name); I != E; ++I) { 1701 Decl *D = *I; 1702 // If the only declaration here is an ordinary friend, consider 1703 // it only if it was declared in an associated classes. 1704 if (D->getIdentifierNamespace() == Decl::IDNS_OrdinaryFriend) { 1705 DeclContext *LexDC = D->getLexicalDeclContext(); 1706 if (!AssociatedClasses.count(cast<CXXRecordDecl>(LexDC))) 1707 continue; 1708 } 1709 1710 FunctionDecl *Fn; 1711 if (!Operator || !(Fn = dyn_cast<FunctionDecl>(D)) || 1712 IsAcceptableNonMemberOperatorCandidate(Fn, T1, T2, Context)) 1713 CollectFunctionDecl(Functions, D); 1714 } 1715 } 1716} 1717