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