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