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