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