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