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