SemaLookup.cpp revision 4cc12c6e47a200cf166ac21efc09dd033f34c9b2
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 "clang/Sema/Sema.h" 15#include "clang/Sema/SemaInternal.h" 16#include "clang/Sema/Lookup.h" 17#include "clang/Sema/Overload.h" 18#include "clang/Sema/DeclSpec.h" 19#include "clang/Sema/Scope.h" 20#include "clang/Sema/ScopeInfo.h" 21#include "clang/Sema/TemplateDeduction.h" 22#include "clang/Sema/ExternalSemaSource.h" 23#include "clang/AST/ASTContext.h" 24#include "clang/AST/CXXInheritance.h" 25#include "clang/AST/Decl.h" 26#include "clang/AST/DeclCXX.h" 27#include "clang/AST/DeclObjC.h" 28#include "clang/AST/DeclTemplate.h" 29#include "clang/AST/Expr.h" 30#include "clang/AST/ExprCXX.h" 31#include "clang/Basic/Builtins.h" 32#include "clang/Basic/LangOptions.h" 33#include "llvm/ADT/DenseSet.h" 34#include "llvm/ADT/STLExtras.h" 35#include "llvm/ADT/SmallPtrSet.h" 36#include "llvm/ADT/StringMap.h" 37#include "llvm/Support/ErrorHandling.h" 38#include <limits> 39#include <list> 40#include <set> 41#include <vector> 42#include <iterator> 43#include <utility> 44#include <algorithm> 45 46using namespace clang; 47using namespace sema; 48 49namespace { 50 class UnqualUsingEntry { 51 const DeclContext *Nominated; 52 const DeclContext *CommonAncestor; 53 54 public: 55 UnqualUsingEntry(const DeclContext *Nominated, 56 const DeclContext *CommonAncestor) 57 : Nominated(Nominated), CommonAncestor(CommonAncestor) { 58 } 59 60 const DeclContext *getCommonAncestor() const { 61 return CommonAncestor; 62 } 63 64 const DeclContext *getNominatedNamespace() const { 65 return Nominated; 66 } 67 68 // Sort by the pointer value of the common ancestor. 69 struct Comparator { 70 bool operator()(const UnqualUsingEntry &L, const UnqualUsingEntry &R) { 71 return L.getCommonAncestor() < R.getCommonAncestor(); 72 } 73 74 bool operator()(const UnqualUsingEntry &E, const DeclContext *DC) { 75 return E.getCommonAncestor() < DC; 76 } 77 78 bool operator()(const DeclContext *DC, const UnqualUsingEntry &E) { 79 return DC < E.getCommonAncestor(); 80 } 81 }; 82 }; 83 84 /// A collection of using directives, as used by C++ unqualified 85 /// lookup. 86 class UnqualUsingDirectiveSet { 87 typedef llvm::SmallVector<UnqualUsingEntry, 8> ListTy; 88 89 ListTy list; 90 llvm::SmallPtrSet<DeclContext*, 8> visited; 91 92 public: 93 UnqualUsingDirectiveSet() {} 94 95 void visitScopeChain(Scope *S, Scope *InnermostFileScope) { 96 // C++ [namespace.udir]p1: 97 // During unqualified name lookup, the names appear as if they 98 // were declared in the nearest enclosing namespace which contains 99 // both the using-directive and the nominated namespace. 100 DeclContext *InnermostFileDC 101 = static_cast<DeclContext*>(InnermostFileScope->getEntity()); 102 assert(InnermostFileDC && InnermostFileDC->isFileContext()); 103 104 for (; S; S = S->getParent()) { 105 if (DeclContext *Ctx = static_cast<DeclContext*>(S->getEntity())) { 106 DeclContext *EffectiveDC = (Ctx->isFileContext() ? Ctx : InnermostFileDC); 107 visit(Ctx, EffectiveDC); 108 } else { 109 Scope::udir_iterator I = S->using_directives_begin(), 110 End = S->using_directives_end(); 111 112 for (; I != End; ++I) 113 visit(*I, InnermostFileDC); 114 } 115 } 116 } 117 118 // Visits a context and collect all of its using directives 119 // recursively. Treats all using directives as if they were 120 // declared in the context. 121 // 122 // A given context is only every visited once, so it is important 123 // that contexts be visited from the inside out in order to get 124 // the effective DCs right. 125 void visit(DeclContext *DC, DeclContext *EffectiveDC) { 126 if (!visited.insert(DC)) 127 return; 128 129 addUsingDirectives(DC, EffectiveDC); 130 } 131 132 // Visits a using directive and collects all of its using 133 // directives recursively. Treats all using directives as if they 134 // were declared in the effective DC. 135 void visit(UsingDirectiveDecl *UD, DeclContext *EffectiveDC) { 136 DeclContext *NS = UD->getNominatedNamespace(); 137 if (!visited.insert(NS)) 138 return; 139 140 addUsingDirective(UD, EffectiveDC); 141 addUsingDirectives(NS, EffectiveDC); 142 } 143 144 // Adds all the using directives in a context (and those nominated 145 // by its using directives, transitively) as if they appeared in 146 // the given effective context. 147 void addUsingDirectives(DeclContext *DC, DeclContext *EffectiveDC) { 148 llvm::SmallVector<DeclContext*,4> queue; 149 while (true) { 150 DeclContext::udir_iterator I, End; 151 for (llvm::tie(I, End) = DC->getUsingDirectives(); I != End; ++I) { 152 UsingDirectiveDecl *UD = *I; 153 DeclContext *NS = UD->getNominatedNamespace(); 154 if (visited.insert(NS)) { 155 addUsingDirective(UD, EffectiveDC); 156 queue.push_back(NS); 157 } 158 } 159 160 if (queue.empty()) 161 return; 162 163 DC = queue.back(); 164 queue.pop_back(); 165 } 166 } 167 168 // Add a using directive as if it had been declared in the given 169 // context. This helps implement C++ [namespace.udir]p3: 170 // The using-directive is transitive: if a scope contains a 171 // using-directive that nominates a second namespace that itself 172 // contains using-directives, the effect is as if the 173 // using-directives from the second namespace also appeared in 174 // the first. 175 void addUsingDirective(UsingDirectiveDecl *UD, DeclContext *EffectiveDC) { 176 // Find the common ancestor between the effective context and 177 // the nominated namespace. 178 DeclContext *Common = UD->getNominatedNamespace(); 179 while (!Common->Encloses(EffectiveDC)) 180 Common = Common->getParent(); 181 Common = Common->getPrimaryContext(); 182 183 list.push_back(UnqualUsingEntry(UD->getNominatedNamespace(), Common)); 184 } 185 186 void done() { 187 std::sort(list.begin(), list.end(), UnqualUsingEntry::Comparator()); 188 } 189 190 typedef ListTy::const_iterator const_iterator; 191 192 const_iterator begin() const { return list.begin(); } 193 const_iterator end() const { return list.end(); } 194 195 std::pair<const_iterator,const_iterator> 196 getNamespacesFor(DeclContext *DC) const { 197 return std::equal_range(begin(), end(), DC->getPrimaryContext(), 198 UnqualUsingEntry::Comparator()); 199 } 200 }; 201} 202 203// Retrieve the set of identifier namespaces that correspond to a 204// specific kind of name lookup. 205static inline unsigned getIDNS(Sema::LookupNameKind NameKind, 206 bool CPlusPlus, 207 bool Redeclaration) { 208 unsigned IDNS = 0; 209 switch (NameKind) { 210 case Sema::LookupOrdinaryName: 211 case Sema::LookupRedeclarationWithLinkage: 212 IDNS = Decl::IDNS_Ordinary; 213 if (CPlusPlus) { 214 IDNS |= Decl::IDNS_Tag | Decl::IDNS_Member | Decl::IDNS_Namespace; 215 if (Redeclaration) 216 IDNS |= Decl::IDNS_TagFriend | Decl::IDNS_OrdinaryFriend; 217 } 218 break; 219 220 case Sema::LookupOperatorName: 221 // Operator lookup is its own crazy thing; it is not the same 222 // as (e.g.) looking up an operator name for redeclaration. 223 assert(!Redeclaration && "cannot do redeclaration operator lookup"); 224 IDNS = Decl::IDNS_NonMemberOperator; 225 break; 226 227 case Sema::LookupTagName: 228 if (CPlusPlus) { 229 IDNS = Decl::IDNS_Type; 230 231 // When looking for a redeclaration of a tag name, we add: 232 // 1) TagFriend to find undeclared friend decls 233 // 2) Namespace because they can't "overload" with tag decls. 234 // 3) Tag because it includes class templates, which can't 235 // "overload" with tag decls. 236 if (Redeclaration) 237 IDNS |= Decl::IDNS_Tag | Decl::IDNS_TagFriend | Decl::IDNS_Namespace; 238 } else { 239 IDNS = Decl::IDNS_Tag; 240 } 241 break; 242 case Sema::LookupLabel: 243 IDNS = Decl::IDNS_Label; 244 break; 245 246 case Sema::LookupMemberName: 247 IDNS = Decl::IDNS_Member; 248 if (CPlusPlus) 249 IDNS |= Decl::IDNS_Tag | Decl::IDNS_Ordinary; 250 break; 251 252 case Sema::LookupNestedNameSpecifierName: 253 IDNS = Decl::IDNS_Type | Decl::IDNS_Namespace; 254 break; 255 256 case Sema::LookupNamespaceName: 257 IDNS = Decl::IDNS_Namespace; 258 break; 259 260 case Sema::LookupUsingDeclName: 261 IDNS = Decl::IDNS_Ordinary | Decl::IDNS_Tag 262 | Decl::IDNS_Member | Decl::IDNS_Using; 263 break; 264 265 case Sema::LookupObjCProtocolName: 266 IDNS = Decl::IDNS_ObjCProtocol; 267 break; 268 269 case Sema::LookupAnyName: 270 IDNS = Decl::IDNS_Ordinary | Decl::IDNS_Tag | Decl::IDNS_Member 271 | Decl::IDNS_Using | Decl::IDNS_Namespace | Decl::IDNS_ObjCProtocol 272 | Decl::IDNS_Type; 273 break; 274 } 275 return IDNS; 276} 277 278void LookupResult::configure() { 279 IDNS = getIDNS(LookupKind, SemaRef.getLangOptions().CPlusPlus, 280 isForRedeclaration()); 281 282 // If we're looking for one of the allocation or deallocation 283 // operators, make sure that the implicitly-declared new and delete 284 // operators can be found. 285 if (!isForRedeclaration()) { 286 switch (NameInfo.getName().getCXXOverloadedOperator()) { 287 case OO_New: 288 case OO_Delete: 289 case OO_Array_New: 290 case OO_Array_Delete: 291 SemaRef.DeclareGlobalNewDelete(); 292 break; 293 294 default: 295 break; 296 } 297 } 298} 299 300void LookupResult::sanity() const { 301 assert(ResultKind != NotFound || Decls.size() == 0); 302 assert(ResultKind != Found || Decls.size() == 1); 303 assert(ResultKind != FoundOverloaded || Decls.size() > 1 || 304 (Decls.size() == 1 && 305 isa<FunctionTemplateDecl>((*begin())->getUnderlyingDecl()))); 306 assert(ResultKind != FoundUnresolvedValue || sanityCheckUnresolved()); 307 assert(ResultKind != Ambiguous || Decls.size() > 1 || 308 (Decls.size() == 1 && (Ambiguity == AmbiguousBaseSubobjects || 309 Ambiguity == AmbiguousBaseSubobjectTypes))); 310 assert((Paths != NULL) == (ResultKind == Ambiguous && 311 (Ambiguity == AmbiguousBaseSubobjectTypes || 312 Ambiguity == AmbiguousBaseSubobjects))); 313} 314 315// Necessary because CXXBasePaths is not complete in Sema.h 316void LookupResult::deletePaths(CXXBasePaths *Paths) { 317 delete Paths; 318} 319 320/// Resolves the result kind of this lookup. 321void LookupResult::resolveKind() { 322 unsigned N = Decls.size(); 323 324 // Fast case: no possible ambiguity. 325 if (N == 0) { 326 assert(ResultKind == NotFound || ResultKind == NotFoundInCurrentInstantiation); 327 return; 328 } 329 330 // If there's a single decl, we need to examine it to decide what 331 // kind of lookup this is. 332 if (N == 1) { 333 NamedDecl *D = (*Decls.begin())->getUnderlyingDecl(); 334 if (isa<FunctionTemplateDecl>(D)) 335 ResultKind = FoundOverloaded; 336 else if (isa<UnresolvedUsingValueDecl>(D)) 337 ResultKind = FoundUnresolvedValue; 338 return; 339 } 340 341 // Don't do any extra resolution if we've already resolved as ambiguous. 342 if (ResultKind == Ambiguous) return; 343 344 llvm::SmallPtrSet<NamedDecl*, 16> Unique; 345 llvm::SmallPtrSet<QualType, 16> UniqueTypes; 346 347 bool Ambiguous = false; 348 bool HasTag = false, HasFunction = false, HasNonFunction = false; 349 bool HasFunctionTemplate = false, HasUnresolved = false; 350 351 unsigned UniqueTagIndex = 0; 352 353 unsigned I = 0; 354 while (I < N) { 355 NamedDecl *D = Decls[I]->getUnderlyingDecl(); 356 D = cast<NamedDecl>(D->getCanonicalDecl()); 357 358 // Redeclarations of types via typedef can occur both within a scope 359 // and, through using declarations and directives, across scopes. There is 360 // no ambiguity if they all refer to the same type, so unique based on the 361 // canonical type. 362 if (TypeDecl *TD = dyn_cast<TypeDecl>(D)) { 363 if (!TD->getDeclContext()->isRecord()) { 364 QualType T = SemaRef.Context.getTypeDeclType(TD); 365 if (!UniqueTypes.insert(SemaRef.Context.getCanonicalType(T))) { 366 // The type is not unique; pull something off the back and continue 367 // at this index. 368 Decls[I] = Decls[--N]; 369 continue; 370 } 371 } 372 } 373 374 if (!Unique.insert(D)) { 375 // If it's not unique, pull something off the back (and 376 // continue at this index). 377 Decls[I] = Decls[--N]; 378 continue; 379 } 380 381 // Otherwise, do some decl type analysis and then continue. 382 383 if (isa<UnresolvedUsingValueDecl>(D)) { 384 HasUnresolved = true; 385 } else if (isa<TagDecl>(D)) { 386 if (HasTag) 387 Ambiguous = true; 388 UniqueTagIndex = I; 389 HasTag = true; 390 } else if (isa<FunctionTemplateDecl>(D)) { 391 HasFunction = true; 392 HasFunctionTemplate = true; 393 } else if (isa<FunctionDecl>(D)) { 394 HasFunction = true; 395 } else { 396 if (HasNonFunction) 397 Ambiguous = true; 398 HasNonFunction = true; 399 } 400 I++; 401 } 402 403 // C++ [basic.scope.hiding]p2: 404 // A class name or enumeration name can be hidden by the name of 405 // an object, function, or enumerator declared in the same 406 // scope. If a class or enumeration name and an object, function, 407 // or enumerator are declared in the same scope (in any order) 408 // with the same name, the class or enumeration name is hidden 409 // wherever the object, function, or enumerator name is visible. 410 // But it's still an error if there are distinct tag types found, 411 // even if they're not visible. (ref?) 412 if (HideTags && HasTag && !Ambiguous && 413 (HasFunction || HasNonFunction || HasUnresolved)) { 414 if (Decls[UniqueTagIndex]->getDeclContext()->getRedeclContext()->Equals( 415 Decls[UniqueTagIndex? 0 : N-1]->getDeclContext()->getRedeclContext())) 416 Decls[UniqueTagIndex] = Decls[--N]; 417 else 418 Ambiguous = true; 419 } 420 421 Decls.set_size(N); 422 423 if (HasNonFunction && (HasFunction || HasUnresolved)) 424 Ambiguous = true; 425 426 if (Ambiguous) 427 setAmbiguous(LookupResult::AmbiguousReference); 428 else if (HasUnresolved) 429 ResultKind = LookupResult::FoundUnresolvedValue; 430 else if (N > 1 || HasFunctionTemplate) 431 ResultKind = LookupResult::FoundOverloaded; 432 else 433 ResultKind = LookupResult::Found; 434} 435 436void LookupResult::addDeclsFromBasePaths(const CXXBasePaths &P) { 437 CXXBasePaths::const_paths_iterator I, E; 438 DeclContext::lookup_iterator DI, DE; 439 for (I = P.begin(), E = P.end(); I != E; ++I) 440 for (llvm::tie(DI,DE) = I->Decls; DI != DE; ++DI) 441 addDecl(*DI); 442} 443 444void LookupResult::setAmbiguousBaseSubobjects(CXXBasePaths &P) { 445 Paths = new CXXBasePaths; 446 Paths->swap(P); 447 addDeclsFromBasePaths(*Paths); 448 resolveKind(); 449 setAmbiguous(AmbiguousBaseSubobjects); 450} 451 452void LookupResult::setAmbiguousBaseSubobjectTypes(CXXBasePaths &P) { 453 Paths = new CXXBasePaths; 454 Paths->swap(P); 455 addDeclsFromBasePaths(*Paths); 456 resolveKind(); 457 setAmbiguous(AmbiguousBaseSubobjectTypes); 458} 459 460void LookupResult::print(llvm::raw_ostream &Out) { 461 Out << Decls.size() << " result(s)"; 462 if (isAmbiguous()) Out << ", ambiguous"; 463 if (Paths) Out << ", base paths present"; 464 465 for (iterator I = begin(), E = end(); I != E; ++I) { 466 Out << "\n"; 467 (*I)->print(Out, 2); 468 } 469} 470 471/// \brief Lookup a builtin function, when name lookup would otherwise 472/// fail. 473static bool LookupBuiltin(Sema &S, LookupResult &R) { 474 Sema::LookupNameKind NameKind = R.getLookupKind(); 475 476 // If we didn't find a use of this identifier, and if the identifier 477 // corresponds to a compiler builtin, create the decl object for the builtin 478 // now, injecting it into translation unit scope, and return it. 479 if (NameKind == Sema::LookupOrdinaryName || 480 NameKind == Sema::LookupRedeclarationWithLinkage) { 481 IdentifierInfo *II = R.getLookupName().getAsIdentifierInfo(); 482 if (II) { 483 // If this is a builtin on this (or all) targets, create the decl. 484 if (unsigned BuiltinID = II->getBuiltinID()) { 485 // In C++, we don't have any predefined library functions like 486 // 'malloc'. Instead, we'll just error. 487 if (S.getLangOptions().CPlusPlus && 488 S.Context.BuiltinInfo.isPredefinedLibFunction(BuiltinID)) 489 return false; 490 491 if (NamedDecl *D = S.LazilyCreateBuiltin((IdentifierInfo *)II, 492 BuiltinID, S.TUScope, 493 R.isForRedeclaration(), 494 R.getNameLoc())) { 495 R.addDecl(D); 496 return true; 497 } 498 499 if (R.isForRedeclaration()) { 500 // If we're redeclaring this function anyway, forget that 501 // this was a builtin at all. 502 S.Context.BuiltinInfo.ForgetBuiltin(BuiltinID, S.Context.Idents); 503 } 504 505 return false; 506 } 507 } 508 } 509 510 return false; 511} 512 513/// \brief Determine whether we can declare a special member function within 514/// the class at this point. 515static bool CanDeclareSpecialMemberFunction(ASTContext &Context, 516 const CXXRecordDecl *Class) { 517 // Don't do it if the class is invalid. 518 if (Class->isInvalidDecl()) 519 return false; 520 521 // We need to have a definition for the class. 522 if (!Class->getDefinition() || Class->isDependentContext()) 523 return false; 524 525 // We can't be in the middle of defining the class. 526 if (const RecordType *RecordTy 527 = Context.getTypeDeclType(Class)->getAs<RecordType>()) 528 return !RecordTy->isBeingDefined(); 529 530 return false; 531} 532 533void Sema::ForceDeclarationOfImplicitMembers(CXXRecordDecl *Class) { 534 if (!CanDeclareSpecialMemberFunction(Context, Class)) 535 return; 536 537 // If the default constructor has not yet been declared, do so now. 538 if (Class->needsImplicitDefaultConstructor()) 539 DeclareImplicitDefaultConstructor(Class); 540 541 // If the copy constructor has not yet been declared, do so now. 542 if (!Class->hasDeclaredCopyConstructor()) 543 DeclareImplicitCopyConstructor(Class); 544 545 // If the copy assignment operator has not yet been declared, do so now. 546 if (!Class->hasDeclaredCopyAssignment()) 547 DeclareImplicitCopyAssignment(Class); 548 549 // If the destructor has not yet been declared, do so now. 550 if (!Class->hasDeclaredDestructor()) 551 DeclareImplicitDestructor(Class); 552} 553 554/// \brief Determine whether this is the name of an implicitly-declared 555/// special member function. 556static bool isImplicitlyDeclaredMemberFunctionName(DeclarationName Name) { 557 switch (Name.getNameKind()) { 558 case DeclarationName::CXXConstructorName: 559 case DeclarationName::CXXDestructorName: 560 return true; 561 562 case DeclarationName::CXXOperatorName: 563 return Name.getCXXOverloadedOperator() == OO_Equal; 564 565 default: 566 break; 567 } 568 569 return false; 570} 571 572/// \brief If there are any implicit member functions with the given name 573/// that need to be declared in the given declaration context, do so. 574static void DeclareImplicitMemberFunctionsWithName(Sema &S, 575 DeclarationName Name, 576 const DeclContext *DC) { 577 if (!DC) 578 return; 579 580 switch (Name.getNameKind()) { 581 case DeclarationName::CXXConstructorName: 582 if (const CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(DC)) 583 if (Record->getDefinition() && 584 CanDeclareSpecialMemberFunction(S.Context, Record)) { 585 if (Record->needsImplicitDefaultConstructor()) 586 S.DeclareImplicitDefaultConstructor( 587 const_cast<CXXRecordDecl *>(Record)); 588 if (!Record->hasDeclaredCopyConstructor()) 589 S.DeclareImplicitCopyConstructor(const_cast<CXXRecordDecl *>(Record)); 590 } 591 break; 592 593 case DeclarationName::CXXDestructorName: 594 if (const CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(DC)) 595 if (Record->getDefinition() && !Record->hasDeclaredDestructor() && 596 CanDeclareSpecialMemberFunction(S.Context, Record)) 597 S.DeclareImplicitDestructor(const_cast<CXXRecordDecl *>(Record)); 598 break; 599 600 case DeclarationName::CXXOperatorName: 601 if (Name.getCXXOverloadedOperator() != OO_Equal) 602 break; 603 604 if (const CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(DC)) 605 if (Record->getDefinition() && !Record->hasDeclaredCopyAssignment() && 606 CanDeclareSpecialMemberFunction(S.Context, Record)) 607 S.DeclareImplicitCopyAssignment(const_cast<CXXRecordDecl *>(Record)); 608 break; 609 610 default: 611 break; 612 } 613} 614 615// Adds all qualifying matches for a name within a decl context to the 616// given lookup result. Returns true if any matches were found. 617static bool LookupDirect(Sema &S, LookupResult &R, const DeclContext *DC) { 618 bool Found = false; 619 620 // Lazily declare C++ special member functions. 621 if (S.getLangOptions().CPlusPlus) 622 DeclareImplicitMemberFunctionsWithName(S, R.getLookupName(), DC); 623 624 // Perform lookup into this declaration context. 625 DeclContext::lookup_const_iterator I, E; 626 for (llvm::tie(I, E) = DC->lookup(R.getLookupName()); I != E; ++I) { 627 NamedDecl *D = *I; 628 if (R.isAcceptableDecl(D)) { 629 R.addDecl(D); 630 Found = true; 631 } 632 } 633 634 if (!Found && DC->isTranslationUnit() && LookupBuiltin(S, R)) 635 return true; 636 637 if (R.getLookupName().getNameKind() 638 != DeclarationName::CXXConversionFunctionName || 639 R.getLookupName().getCXXNameType()->isDependentType() || 640 !isa<CXXRecordDecl>(DC)) 641 return Found; 642 643 // C++ [temp.mem]p6: 644 // A specialization of a conversion function template is not found by 645 // name lookup. Instead, any conversion function templates visible in the 646 // context of the use are considered. [...] 647 const CXXRecordDecl *Record = cast<CXXRecordDecl>(DC); 648 if (!Record->isDefinition()) 649 return Found; 650 651 const UnresolvedSetImpl *Unresolved = Record->getConversionFunctions(); 652 for (UnresolvedSetImpl::iterator U = Unresolved->begin(), 653 UEnd = Unresolved->end(); U != UEnd; ++U) { 654 FunctionTemplateDecl *ConvTemplate = dyn_cast<FunctionTemplateDecl>(*U); 655 if (!ConvTemplate) 656 continue; 657 658 // When we're performing lookup for the purposes of redeclaration, just 659 // add the conversion function template. When we deduce template 660 // arguments for specializations, we'll end up unifying the return 661 // type of the new declaration with the type of the function template. 662 if (R.isForRedeclaration()) { 663 R.addDecl(ConvTemplate); 664 Found = true; 665 continue; 666 } 667 668 // C++ [temp.mem]p6: 669 // [...] For each such operator, if argument deduction succeeds 670 // (14.9.2.3), the resulting specialization is used as if found by 671 // name lookup. 672 // 673 // When referencing a conversion function for any purpose other than 674 // a redeclaration (such that we'll be building an expression with the 675 // result), perform template argument deduction and place the 676 // specialization into the result set. We do this to avoid forcing all 677 // callers to perform special deduction for conversion functions. 678 TemplateDeductionInfo Info(R.getSema().Context, R.getNameLoc()); 679 FunctionDecl *Specialization = 0; 680 681 const FunctionProtoType *ConvProto 682 = ConvTemplate->getTemplatedDecl()->getType()->getAs<FunctionProtoType>(); 683 assert(ConvProto && "Nonsensical conversion function template type"); 684 685 // Compute the type of the function that we would expect the conversion 686 // function to have, if it were to match the name given. 687 // FIXME: Calling convention! 688 FunctionProtoType::ExtProtoInfo EPI = ConvProto->getExtProtoInfo(); 689 EPI.ExtInfo = EPI.ExtInfo.withCallingConv(CC_Default); 690 EPI.ExceptionSpecType = EST_None; 691 EPI.NumExceptions = 0; 692 QualType ExpectedType 693 = R.getSema().Context.getFunctionType(R.getLookupName().getCXXNameType(), 694 0, 0, EPI); 695 696 // Perform template argument deduction against the type that we would 697 // expect the function to have. 698 if (R.getSema().DeduceTemplateArguments(ConvTemplate, 0, ExpectedType, 699 Specialization, Info) 700 == Sema::TDK_Success) { 701 R.addDecl(Specialization); 702 Found = true; 703 } 704 } 705 706 return Found; 707} 708 709// Performs C++ unqualified lookup into the given file context. 710static bool 711CppNamespaceLookup(Sema &S, LookupResult &R, ASTContext &Context, 712 DeclContext *NS, UnqualUsingDirectiveSet &UDirs) { 713 714 assert(NS && NS->isFileContext() && "CppNamespaceLookup() requires namespace!"); 715 716 // Perform direct name lookup into the LookupCtx. 717 bool Found = LookupDirect(S, R, NS); 718 719 // Perform direct name lookup into the namespaces nominated by the 720 // using directives whose common ancestor is this namespace. 721 UnqualUsingDirectiveSet::const_iterator UI, UEnd; 722 llvm::tie(UI, UEnd) = UDirs.getNamespacesFor(NS); 723 724 for (; UI != UEnd; ++UI) 725 if (LookupDirect(S, R, UI->getNominatedNamespace())) 726 Found = true; 727 728 R.resolveKind(); 729 730 return Found; 731} 732 733static bool isNamespaceOrTranslationUnitScope(Scope *S) { 734 if (DeclContext *Ctx = static_cast<DeclContext*>(S->getEntity())) 735 return Ctx->isFileContext(); 736 return false; 737} 738 739// Find the next outer declaration context from this scope. This 740// routine actually returns the semantic outer context, which may 741// differ from the lexical context (encoded directly in the Scope 742// stack) when we are parsing a member of a class template. In this 743// case, the second element of the pair will be true, to indicate that 744// name lookup should continue searching in this semantic context when 745// it leaves the current template parameter scope. 746static std::pair<DeclContext *, bool> findOuterContext(Scope *S) { 747 DeclContext *DC = static_cast<DeclContext *>(S->getEntity()); 748 DeclContext *Lexical = 0; 749 for (Scope *OuterS = S->getParent(); OuterS; 750 OuterS = OuterS->getParent()) { 751 if (OuterS->getEntity()) { 752 Lexical = static_cast<DeclContext *>(OuterS->getEntity()); 753 break; 754 } 755 } 756 757 // C++ [temp.local]p8: 758 // In the definition of a member of a class template that appears 759 // outside of the namespace containing the class template 760 // definition, the name of a template-parameter hides the name of 761 // a member of this namespace. 762 // 763 // Example: 764 // 765 // namespace N { 766 // class C { }; 767 // 768 // template<class T> class B { 769 // void f(T); 770 // }; 771 // } 772 // 773 // template<class C> void N::B<C>::f(C) { 774 // C b; // C is the template parameter, not N::C 775 // } 776 // 777 // In this example, the lexical context we return is the 778 // TranslationUnit, while the semantic context is the namespace N. 779 if (!Lexical || !DC || !S->getParent() || 780 !S->getParent()->isTemplateParamScope()) 781 return std::make_pair(Lexical, false); 782 783 // Find the outermost template parameter scope. 784 // For the example, this is the scope for the template parameters of 785 // template<class C>. 786 Scope *OutermostTemplateScope = S->getParent(); 787 while (OutermostTemplateScope->getParent() && 788 OutermostTemplateScope->getParent()->isTemplateParamScope()) 789 OutermostTemplateScope = OutermostTemplateScope->getParent(); 790 791 // Find the namespace context in which the original scope occurs. In 792 // the example, this is namespace N. 793 DeclContext *Semantic = DC; 794 while (!Semantic->isFileContext()) 795 Semantic = Semantic->getParent(); 796 797 // Find the declaration context just outside of the template 798 // parameter scope. This is the context in which the template is 799 // being lexically declaration (a namespace context). In the 800 // example, this is the global scope. 801 if (Lexical->isFileContext() && !Lexical->Equals(Semantic) && 802 Lexical->Encloses(Semantic)) 803 return std::make_pair(Semantic, true); 804 805 return std::make_pair(Lexical, false); 806} 807 808bool Sema::CppLookupName(LookupResult &R, Scope *S) { 809 assert(getLangOptions().CPlusPlus && "Can perform only C++ lookup"); 810 811 DeclarationName Name = R.getLookupName(); 812 813 // If this is the name of an implicitly-declared special member function, 814 // go through the scope stack to implicitly declare 815 if (isImplicitlyDeclaredMemberFunctionName(Name)) { 816 for (Scope *PreS = S; PreS; PreS = PreS->getParent()) 817 if (DeclContext *DC = static_cast<DeclContext *>(PreS->getEntity())) 818 DeclareImplicitMemberFunctionsWithName(*this, Name, DC); 819 } 820 821 // Implicitly declare member functions with the name we're looking for, if in 822 // fact we are in a scope where it matters. 823 824 Scope *Initial = S; 825 IdentifierResolver::iterator 826 I = IdResolver.begin(Name), 827 IEnd = IdResolver.end(); 828 829 // First we lookup local scope. 830 // We don't consider using-directives, as per 7.3.4.p1 [namespace.udir] 831 // ...During unqualified name lookup (3.4.1), the names appear as if 832 // they were declared in the nearest enclosing namespace which contains 833 // both the using-directive and the nominated namespace. 834 // [Note: in this context, "contains" means "contains directly or 835 // indirectly". 836 // 837 // For example: 838 // namespace A { int i; } 839 // void foo() { 840 // int i; 841 // { 842 // using namespace A; 843 // ++i; // finds local 'i', A::i appears at global scope 844 // } 845 // } 846 // 847 DeclContext *OutsideOfTemplateParamDC = 0; 848 for (; S && !isNamespaceOrTranslationUnitScope(S); S = S->getParent()) { 849 DeclContext *Ctx = static_cast<DeclContext*>(S->getEntity()); 850 851 // Check whether the IdResolver has anything in this scope. 852 bool Found = false; 853 for (; I != IEnd && S->isDeclScope(*I); ++I) { 854 if (R.isAcceptableDecl(*I)) { 855 Found = true; 856 R.addDecl(*I); 857 } 858 } 859 if (Found) { 860 R.resolveKind(); 861 if (S->isClassScope()) 862 if (CXXRecordDecl *Record = dyn_cast_or_null<CXXRecordDecl>(Ctx)) 863 R.setNamingClass(Record); 864 return true; 865 } 866 867 if (!Ctx && S->isTemplateParamScope() && OutsideOfTemplateParamDC && 868 S->getParent() && !S->getParent()->isTemplateParamScope()) { 869 // We've just searched the last template parameter scope and 870 // found nothing, so look into the the contexts between the 871 // lexical and semantic declaration contexts returned by 872 // findOuterContext(). This implements the name lookup behavior 873 // of C++ [temp.local]p8. 874 Ctx = OutsideOfTemplateParamDC; 875 OutsideOfTemplateParamDC = 0; 876 } 877 878 if (Ctx) { 879 DeclContext *OuterCtx; 880 bool SearchAfterTemplateScope; 881 llvm::tie(OuterCtx, SearchAfterTemplateScope) = findOuterContext(S); 882 if (SearchAfterTemplateScope) 883 OutsideOfTemplateParamDC = OuterCtx; 884 885 for (; Ctx && !Ctx->Equals(OuterCtx); Ctx = Ctx->getLookupParent()) { 886 // We do not directly look into transparent contexts, since 887 // those entities will be found in the nearest enclosing 888 // non-transparent context. 889 if (Ctx->isTransparentContext()) 890 continue; 891 892 // We do not look directly into function or method contexts, 893 // since all of the local variables and parameters of the 894 // function/method are present within the Scope. 895 if (Ctx->isFunctionOrMethod()) { 896 // If we have an Objective-C instance method, look for ivars 897 // in the corresponding interface. 898 if (ObjCMethodDecl *Method = dyn_cast<ObjCMethodDecl>(Ctx)) { 899 if (Method->isInstanceMethod() && Name.getAsIdentifierInfo()) 900 if (ObjCInterfaceDecl *Class = Method->getClassInterface()) { 901 ObjCInterfaceDecl *ClassDeclared; 902 if (ObjCIvarDecl *Ivar = Class->lookupInstanceVariable( 903 Name.getAsIdentifierInfo(), 904 ClassDeclared)) { 905 if (R.isAcceptableDecl(Ivar)) { 906 R.addDecl(Ivar); 907 R.resolveKind(); 908 return true; 909 } 910 } 911 } 912 } 913 914 continue; 915 } 916 917 // Perform qualified name lookup into this context. 918 // FIXME: In some cases, we know that every name that could be found by 919 // this qualified name lookup will also be on the identifier chain. For 920 // example, inside a class without any base classes, we never need to 921 // perform qualified lookup because all of the members are on top of the 922 // identifier chain. 923 if (LookupQualifiedName(R, Ctx, /*InUnqualifiedLookup=*/true)) 924 return true; 925 } 926 } 927 } 928 929 // Stop if we ran out of scopes. 930 // FIXME: This really, really shouldn't be happening. 931 if (!S) return false; 932 933 // If we are looking for members, no need to look into global/namespace scope. 934 if (R.getLookupKind() == LookupMemberName) 935 return false; 936 937 // Collect UsingDirectiveDecls in all scopes, and recursively all 938 // nominated namespaces by those using-directives. 939 // 940 // FIXME: Cache this sorted list in Scope structure, and DeclContext, so we 941 // don't build it for each lookup! 942 943 UnqualUsingDirectiveSet UDirs; 944 UDirs.visitScopeChain(Initial, S); 945 UDirs.done(); 946 947 // Lookup namespace scope, and global scope. 948 // Unqualified name lookup in C++ requires looking into scopes 949 // that aren't strictly lexical, and therefore we walk through the 950 // context as well as walking through the scopes. 951 952 for (; S; S = S->getParent()) { 953 // Check whether the IdResolver has anything in this scope. 954 bool Found = false; 955 for (; I != IEnd && S->isDeclScope(*I); ++I) { 956 if (R.isAcceptableDecl(*I)) { 957 // We found something. Look for anything else in our scope 958 // with this same name and in an acceptable identifier 959 // namespace, so that we can construct an overload set if we 960 // need to. 961 Found = true; 962 R.addDecl(*I); 963 } 964 } 965 966 if (Found && S->isTemplateParamScope()) { 967 R.resolveKind(); 968 return true; 969 } 970 971 DeclContext *Ctx = static_cast<DeclContext *>(S->getEntity()); 972 if (!Ctx && S->isTemplateParamScope() && OutsideOfTemplateParamDC && 973 S->getParent() && !S->getParent()->isTemplateParamScope()) { 974 // We've just searched the last template parameter scope and 975 // found nothing, so look into the the contexts between the 976 // lexical and semantic declaration contexts returned by 977 // findOuterContext(). This implements the name lookup behavior 978 // of C++ [temp.local]p8. 979 Ctx = OutsideOfTemplateParamDC; 980 OutsideOfTemplateParamDC = 0; 981 } 982 983 if (Ctx) { 984 DeclContext *OuterCtx; 985 bool SearchAfterTemplateScope; 986 llvm::tie(OuterCtx, SearchAfterTemplateScope) = findOuterContext(S); 987 if (SearchAfterTemplateScope) 988 OutsideOfTemplateParamDC = OuterCtx; 989 990 for (; Ctx && !Ctx->Equals(OuterCtx); Ctx = Ctx->getLookupParent()) { 991 // We do not directly look into transparent contexts, since 992 // those entities will be found in the nearest enclosing 993 // non-transparent context. 994 if (Ctx->isTransparentContext()) 995 continue; 996 997 // If we have a context, and it's not a context stashed in the 998 // template parameter scope for an out-of-line definition, also 999 // look into that context. 1000 if (!(Found && S && S->isTemplateParamScope())) { 1001 assert(Ctx->isFileContext() && 1002 "We should have been looking only at file context here already."); 1003 1004 // Look into context considering using-directives. 1005 if (CppNamespaceLookup(*this, R, Context, Ctx, UDirs)) 1006 Found = true; 1007 } 1008 1009 if (Found) { 1010 R.resolveKind(); 1011 return true; 1012 } 1013 1014 if (R.isForRedeclaration() && !Ctx->isTransparentContext()) 1015 return false; 1016 } 1017 } 1018 1019 if (R.isForRedeclaration() && Ctx && !Ctx->isTransparentContext()) 1020 return false; 1021 } 1022 1023 return !R.empty(); 1024} 1025 1026/// @brief Perform unqualified name lookup starting from a given 1027/// scope. 1028/// 1029/// Unqualified name lookup (C++ [basic.lookup.unqual], C99 6.2.1) is 1030/// used to find names within the current scope. For example, 'x' in 1031/// @code 1032/// int x; 1033/// int f() { 1034/// return x; // unqualified name look finds 'x' in the global scope 1035/// } 1036/// @endcode 1037/// 1038/// Different lookup criteria can find different names. For example, a 1039/// particular scope can have both a struct and a function of the same 1040/// name, and each can be found by certain lookup criteria. For more 1041/// information about lookup criteria, see the documentation for the 1042/// class LookupCriteria. 1043/// 1044/// @param S The scope from which unqualified name lookup will 1045/// begin. If the lookup criteria permits, name lookup may also search 1046/// in the parent scopes. 1047/// 1048/// @param Name The name of the entity that we are searching for. 1049/// 1050/// @param Loc If provided, the source location where we're performing 1051/// name lookup. At present, this is only used to produce diagnostics when 1052/// C library functions (like "malloc") are implicitly declared. 1053/// 1054/// @returns The result of name lookup, which includes zero or more 1055/// declarations and possibly additional information used to diagnose 1056/// ambiguities. 1057bool Sema::LookupName(LookupResult &R, Scope *S, bool AllowBuiltinCreation) { 1058 DeclarationName Name = R.getLookupName(); 1059 if (!Name) return false; 1060 1061 LookupNameKind NameKind = R.getLookupKind(); 1062 1063 if (!getLangOptions().CPlusPlus) { 1064 // Unqualified name lookup in C/Objective-C is purely lexical, so 1065 // search in the declarations attached to the name. 1066 if (NameKind == Sema::LookupRedeclarationWithLinkage) { 1067 // Find the nearest non-transparent declaration scope. 1068 while (!(S->getFlags() & Scope::DeclScope) || 1069 (S->getEntity() && 1070 static_cast<DeclContext *>(S->getEntity()) 1071 ->isTransparentContext())) 1072 S = S->getParent(); 1073 } 1074 1075 unsigned IDNS = R.getIdentifierNamespace(); 1076 1077 // Scan up the scope chain looking for a decl that matches this 1078 // identifier that is in the appropriate namespace. This search 1079 // should not take long, as shadowing of names is uncommon, and 1080 // deep shadowing is extremely uncommon. 1081 bool LeftStartingScope = false; 1082 1083 for (IdentifierResolver::iterator I = IdResolver.begin(Name), 1084 IEnd = IdResolver.end(); 1085 I != IEnd; ++I) 1086 if ((*I)->isInIdentifierNamespace(IDNS)) { 1087 if (NameKind == LookupRedeclarationWithLinkage) { 1088 // Determine whether this (or a previous) declaration is 1089 // out-of-scope. 1090 if (!LeftStartingScope && !S->isDeclScope(*I)) 1091 LeftStartingScope = true; 1092 1093 // If we found something outside of our starting scope that 1094 // does not have linkage, skip it. 1095 if (LeftStartingScope && !((*I)->hasLinkage())) 1096 continue; 1097 } 1098 1099 R.addDecl(*I); 1100 1101 if ((*I)->getAttr<OverloadableAttr>()) { 1102 // If this declaration has the "overloadable" attribute, we 1103 // might have a set of overloaded functions. 1104 1105 // Figure out what scope the identifier is in. 1106 while (!(S->getFlags() & Scope::DeclScope) || 1107 !S->isDeclScope(*I)) 1108 S = S->getParent(); 1109 1110 // Find the last declaration in this scope (with the same 1111 // name, naturally). 1112 IdentifierResolver::iterator LastI = I; 1113 for (++LastI; LastI != IEnd; ++LastI) { 1114 if (!S->isDeclScope(*LastI)) 1115 break; 1116 R.addDecl(*LastI); 1117 } 1118 } 1119 1120 R.resolveKind(); 1121 1122 return true; 1123 } 1124 } else { 1125 // Perform C++ unqualified name lookup. 1126 if (CppLookupName(R, S)) 1127 return true; 1128 } 1129 1130 // If we didn't find a use of this identifier, and if the identifier 1131 // corresponds to a compiler builtin, create the decl object for the builtin 1132 // now, injecting it into translation unit scope, and return it. 1133 if (AllowBuiltinCreation && LookupBuiltin(*this, R)) 1134 return true; 1135 1136 // If we didn't find a use of this identifier, the ExternalSource 1137 // may be able to handle the situation. 1138 // Note: some lookup failures are expected! 1139 // See e.g. R.isForRedeclaration(). 1140 return (ExternalSource && ExternalSource->LookupUnqualified(R, S)); 1141} 1142 1143/// @brief Perform qualified name lookup in the namespaces nominated by 1144/// using directives by the given context. 1145/// 1146/// C++98 [namespace.qual]p2: 1147/// Given X::m (where X is a user-declared namespace), or given ::m 1148/// (where X is the global namespace), let S be the set of all 1149/// declarations of m in X and in the transitive closure of all 1150/// namespaces nominated by using-directives in X and its used 1151/// namespaces, except that using-directives are ignored in any 1152/// namespace, including X, directly containing one or more 1153/// declarations of m. No namespace is searched more than once in 1154/// the lookup of a name. If S is the empty set, the program is 1155/// ill-formed. Otherwise, if S has exactly one member, or if the 1156/// context of the reference is a using-declaration 1157/// (namespace.udecl), S is the required set of declarations of 1158/// m. Otherwise if the use of m is not one that allows a unique 1159/// declaration to be chosen from S, the program is ill-formed. 1160/// C++98 [namespace.qual]p5: 1161/// During the lookup of a qualified namespace member name, if the 1162/// lookup finds more than one declaration of the member, and if one 1163/// declaration introduces a class name or enumeration name and the 1164/// other declarations either introduce the same object, the same 1165/// enumerator or a set of functions, the non-type name hides the 1166/// class or enumeration name if and only if the declarations are 1167/// from the same namespace; otherwise (the declarations are from 1168/// different namespaces), the program is ill-formed. 1169static bool LookupQualifiedNameInUsingDirectives(Sema &S, LookupResult &R, 1170 DeclContext *StartDC) { 1171 assert(StartDC->isFileContext() && "start context is not a file context"); 1172 1173 DeclContext::udir_iterator I = StartDC->using_directives_begin(); 1174 DeclContext::udir_iterator E = StartDC->using_directives_end(); 1175 1176 if (I == E) return false; 1177 1178 // We have at least added all these contexts to the queue. 1179 llvm::DenseSet<DeclContext*> Visited; 1180 Visited.insert(StartDC); 1181 1182 // We have not yet looked into these namespaces, much less added 1183 // their "using-children" to the queue. 1184 llvm::SmallVector<NamespaceDecl*, 8> Queue; 1185 1186 // We have already looked into the initial namespace; seed the queue 1187 // with its using-children. 1188 for (; I != E; ++I) { 1189 NamespaceDecl *ND = (*I)->getNominatedNamespace()->getOriginalNamespace(); 1190 if (Visited.insert(ND).second) 1191 Queue.push_back(ND); 1192 } 1193 1194 // The easiest way to implement the restriction in [namespace.qual]p5 1195 // is to check whether any of the individual results found a tag 1196 // and, if so, to declare an ambiguity if the final result is not 1197 // a tag. 1198 bool FoundTag = false; 1199 bool FoundNonTag = false; 1200 1201 LookupResult LocalR(LookupResult::Temporary, R); 1202 1203 bool Found = false; 1204 while (!Queue.empty()) { 1205 NamespaceDecl *ND = Queue.back(); 1206 Queue.pop_back(); 1207 1208 // We go through some convolutions here to avoid copying results 1209 // between LookupResults. 1210 bool UseLocal = !R.empty(); 1211 LookupResult &DirectR = UseLocal ? LocalR : R; 1212 bool FoundDirect = LookupDirect(S, DirectR, ND); 1213 1214 if (FoundDirect) { 1215 // First do any local hiding. 1216 DirectR.resolveKind(); 1217 1218 // If the local result is a tag, remember that. 1219 if (DirectR.isSingleTagDecl()) 1220 FoundTag = true; 1221 else 1222 FoundNonTag = true; 1223 1224 // Append the local results to the total results if necessary. 1225 if (UseLocal) { 1226 R.addAllDecls(LocalR); 1227 LocalR.clear(); 1228 } 1229 } 1230 1231 // If we find names in this namespace, ignore its using directives. 1232 if (FoundDirect) { 1233 Found = true; 1234 continue; 1235 } 1236 1237 for (llvm::tie(I,E) = ND->getUsingDirectives(); I != E; ++I) { 1238 NamespaceDecl *Nom = (*I)->getNominatedNamespace(); 1239 if (Visited.insert(Nom).second) 1240 Queue.push_back(Nom); 1241 } 1242 } 1243 1244 if (Found) { 1245 if (FoundTag && FoundNonTag) 1246 R.setAmbiguousQualifiedTagHiding(); 1247 else 1248 R.resolveKind(); 1249 } 1250 1251 return Found; 1252} 1253 1254/// \brief Callback that looks for any member of a class with the given name. 1255static bool LookupAnyMember(const CXXBaseSpecifier *Specifier, 1256 CXXBasePath &Path, 1257 void *Name) { 1258 RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl(); 1259 1260 DeclarationName N = DeclarationName::getFromOpaquePtr(Name); 1261 Path.Decls = BaseRecord->lookup(N); 1262 return Path.Decls.first != Path.Decls.second; 1263} 1264 1265/// \brief Determine whether the given set of member declarations contains only 1266/// static members, nested types, and enumerators. 1267template<typename InputIterator> 1268static bool HasOnlyStaticMembers(InputIterator First, InputIterator Last) { 1269 Decl *D = (*First)->getUnderlyingDecl(); 1270 if (isa<VarDecl>(D) || isa<TypeDecl>(D) || isa<EnumConstantDecl>(D)) 1271 return true; 1272 1273 if (isa<CXXMethodDecl>(D)) { 1274 // Determine whether all of the methods are static. 1275 bool AllMethodsAreStatic = true; 1276 for(; First != Last; ++First) { 1277 D = (*First)->getUnderlyingDecl(); 1278 1279 if (!isa<CXXMethodDecl>(D)) { 1280 assert(isa<TagDecl>(D) && "Non-function must be a tag decl"); 1281 break; 1282 } 1283 1284 if (!cast<CXXMethodDecl>(D)->isStatic()) { 1285 AllMethodsAreStatic = false; 1286 break; 1287 } 1288 } 1289 1290 if (AllMethodsAreStatic) 1291 return true; 1292 } 1293 1294 return false; 1295} 1296 1297/// \brief Perform qualified name lookup into a given context. 1298/// 1299/// Qualified name lookup (C++ [basic.lookup.qual]) is used to find 1300/// names when the context of those names is explicit specified, e.g., 1301/// "std::vector" or "x->member", or as part of unqualified name lookup. 1302/// 1303/// Different lookup criteria can find different names. For example, a 1304/// particular scope can have both a struct and a function of the same 1305/// name, and each can be found by certain lookup criteria. For more 1306/// information about lookup criteria, see the documentation for the 1307/// class LookupCriteria. 1308/// 1309/// \param R captures both the lookup criteria and any lookup results found. 1310/// 1311/// \param LookupCtx The context in which qualified name lookup will 1312/// search. If the lookup criteria permits, name lookup may also search 1313/// in the parent contexts or (for C++ classes) base classes. 1314/// 1315/// \param InUnqualifiedLookup true if this is qualified name lookup that 1316/// occurs as part of unqualified name lookup. 1317/// 1318/// \returns true if lookup succeeded, false if it failed. 1319bool Sema::LookupQualifiedName(LookupResult &R, DeclContext *LookupCtx, 1320 bool InUnqualifiedLookup) { 1321 assert(LookupCtx && "Sema::LookupQualifiedName requires a lookup context"); 1322 1323 if (!R.getLookupName()) 1324 return false; 1325 1326 // Make sure that the declaration context is complete. 1327 assert((!isa<TagDecl>(LookupCtx) || 1328 LookupCtx->isDependentContext() || 1329 cast<TagDecl>(LookupCtx)->isDefinition() || 1330 Context.getTypeDeclType(cast<TagDecl>(LookupCtx))->getAs<TagType>() 1331 ->isBeingDefined()) && 1332 "Declaration context must already be complete!"); 1333 1334 // Perform qualified name lookup into the LookupCtx. 1335 if (LookupDirect(*this, R, LookupCtx)) { 1336 R.resolveKind(); 1337 if (isa<CXXRecordDecl>(LookupCtx)) 1338 R.setNamingClass(cast<CXXRecordDecl>(LookupCtx)); 1339 return true; 1340 } 1341 1342 // Don't descend into implied contexts for redeclarations. 1343 // C++98 [namespace.qual]p6: 1344 // In a declaration for a namespace member in which the 1345 // declarator-id is a qualified-id, given that the qualified-id 1346 // for the namespace member has the form 1347 // nested-name-specifier unqualified-id 1348 // the unqualified-id shall name a member of the namespace 1349 // designated by the nested-name-specifier. 1350 // See also [class.mfct]p5 and [class.static.data]p2. 1351 if (R.isForRedeclaration()) 1352 return false; 1353 1354 // If this is a namespace, look it up in the implied namespaces. 1355 if (LookupCtx->isFileContext()) 1356 return LookupQualifiedNameInUsingDirectives(*this, R, LookupCtx); 1357 1358 // If this isn't a C++ class, we aren't allowed to look into base 1359 // classes, we're done. 1360 CXXRecordDecl *LookupRec = dyn_cast<CXXRecordDecl>(LookupCtx); 1361 if (!LookupRec || !LookupRec->getDefinition()) 1362 return false; 1363 1364 // If we're performing qualified name lookup into a dependent class, 1365 // then we are actually looking into a current instantiation. If we have any 1366 // dependent base classes, then we either have to delay lookup until 1367 // template instantiation time (at which point all bases will be available) 1368 // or we have to fail. 1369 if (!InUnqualifiedLookup && LookupRec->isDependentContext() && 1370 LookupRec->hasAnyDependentBases()) { 1371 R.setNotFoundInCurrentInstantiation(); 1372 return false; 1373 } 1374 1375 // Perform lookup into our base classes. 1376 CXXBasePaths Paths; 1377 Paths.setOrigin(LookupRec); 1378 1379 // Look for this member in our base classes 1380 CXXRecordDecl::BaseMatchesCallback *BaseCallback = 0; 1381 switch (R.getLookupKind()) { 1382 case LookupOrdinaryName: 1383 case LookupMemberName: 1384 case LookupRedeclarationWithLinkage: 1385 BaseCallback = &CXXRecordDecl::FindOrdinaryMember; 1386 break; 1387 1388 case LookupTagName: 1389 BaseCallback = &CXXRecordDecl::FindTagMember; 1390 break; 1391 1392 case LookupAnyName: 1393 BaseCallback = &LookupAnyMember; 1394 break; 1395 1396 case LookupUsingDeclName: 1397 // This lookup is for redeclarations only. 1398 1399 case LookupOperatorName: 1400 case LookupNamespaceName: 1401 case LookupObjCProtocolName: 1402 case LookupLabel: 1403 // These lookups will never find a member in a C++ class (or base class). 1404 return false; 1405 1406 case LookupNestedNameSpecifierName: 1407 BaseCallback = &CXXRecordDecl::FindNestedNameSpecifierMember; 1408 break; 1409 } 1410 1411 if (!LookupRec->lookupInBases(BaseCallback, 1412 R.getLookupName().getAsOpaquePtr(), Paths)) 1413 return false; 1414 1415 R.setNamingClass(LookupRec); 1416 1417 // C++ [class.member.lookup]p2: 1418 // [...] If the resulting set of declarations are not all from 1419 // sub-objects of the same type, or the set has a nonstatic member 1420 // and includes members from distinct sub-objects, there is an 1421 // ambiguity and the program is ill-formed. Otherwise that set is 1422 // the result of the lookup. 1423 QualType SubobjectType; 1424 int SubobjectNumber = 0; 1425 AccessSpecifier SubobjectAccess = AS_none; 1426 1427 for (CXXBasePaths::paths_iterator Path = Paths.begin(), PathEnd = Paths.end(); 1428 Path != PathEnd; ++Path) { 1429 const CXXBasePathElement &PathElement = Path->back(); 1430 1431 // Pick the best (i.e. most permissive i.e. numerically lowest) access 1432 // across all paths. 1433 SubobjectAccess = std::min(SubobjectAccess, Path->Access); 1434 1435 // Determine whether we're looking at a distinct sub-object or not. 1436 if (SubobjectType.isNull()) { 1437 // This is the first subobject we've looked at. Record its type. 1438 SubobjectType = Context.getCanonicalType(PathElement.Base->getType()); 1439 SubobjectNumber = PathElement.SubobjectNumber; 1440 continue; 1441 } 1442 1443 if (SubobjectType 1444 != Context.getCanonicalType(PathElement.Base->getType())) { 1445 // We found members of the given name in two subobjects of 1446 // different types. If the declaration sets aren't the same, this 1447 // this lookup is ambiguous. 1448 if (HasOnlyStaticMembers(Path->Decls.first, Path->Decls.second)) { 1449 CXXBasePaths::paths_iterator FirstPath = Paths.begin(); 1450 DeclContext::lookup_iterator FirstD = FirstPath->Decls.first; 1451 DeclContext::lookup_iterator CurrentD = Path->Decls.first; 1452 1453 while (FirstD != FirstPath->Decls.second && 1454 CurrentD != Path->Decls.second) { 1455 if ((*FirstD)->getUnderlyingDecl()->getCanonicalDecl() != 1456 (*CurrentD)->getUnderlyingDecl()->getCanonicalDecl()) 1457 break; 1458 1459 ++FirstD; 1460 ++CurrentD; 1461 } 1462 1463 if (FirstD == FirstPath->Decls.second && 1464 CurrentD == Path->Decls.second) 1465 continue; 1466 } 1467 1468 R.setAmbiguousBaseSubobjectTypes(Paths); 1469 return true; 1470 } 1471 1472 if (SubobjectNumber != PathElement.SubobjectNumber) { 1473 // We have a different subobject of the same type. 1474 1475 // C++ [class.member.lookup]p5: 1476 // A static member, a nested type or an enumerator defined in 1477 // a base class T can unambiguously be found even if an object 1478 // has more than one base class subobject of type T. 1479 if (HasOnlyStaticMembers(Path->Decls.first, Path->Decls.second)) 1480 continue; 1481 1482 // We have found a nonstatic member name in multiple, distinct 1483 // subobjects. Name lookup is ambiguous. 1484 R.setAmbiguousBaseSubobjects(Paths); 1485 return true; 1486 } 1487 } 1488 1489 // Lookup in a base class succeeded; return these results. 1490 1491 DeclContext::lookup_iterator I, E; 1492 for (llvm::tie(I,E) = Paths.front().Decls; I != E; ++I) { 1493 NamedDecl *D = *I; 1494 AccessSpecifier AS = CXXRecordDecl::MergeAccess(SubobjectAccess, 1495 D->getAccess()); 1496 R.addDecl(D, AS); 1497 } 1498 R.resolveKind(); 1499 return true; 1500} 1501 1502/// @brief Performs name lookup for a name that was parsed in the 1503/// source code, and may contain a C++ scope specifier. 1504/// 1505/// This routine is a convenience routine meant to be called from 1506/// contexts that receive a name and an optional C++ scope specifier 1507/// (e.g., "N::M::x"). It will then perform either qualified or 1508/// unqualified name lookup (with LookupQualifiedName or LookupName, 1509/// respectively) on the given name and return those results. 1510/// 1511/// @param S The scope from which unqualified name lookup will 1512/// begin. 1513/// 1514/// @param SS An optional C++ scope-specifier, e.g., "::N::M". 1515/// 1516/// @param EnteringContext Indicates whether we are going to enter the 1517/// context of the scope-specifier SS (if present). 1518/// 1519/// @returns True if any decls were found (but possibly ambiguous) 1520bool Sema::LookupParsedName(LookupResult &R, Scope *S, CXXScopeSpec *SS, 1521 bool AllowBuiltinCreation, bool EnteringContext) { 1522 if (SS && SS->isInvalid()) { 1523 // When the scope specifier is invalid, don't even look for 1524 // anything. 1525 return false; 1526 } 1527 1528 if (SS && SS->isSet()) { 1529 if (DeclContext *DC = computeDeclContext(*SS, EnteringContext)) { 1530 // We have resolved the scope specifier to a particular declaration 1531 // contex, and will perform name lookup in that context. 1532 if (!DC->isDependentContext() && RequireCompleteDeclContext(*SS, DC)) 1533 return false; 1534 1535 R.setContextRange(SS->getRange()); 1536 1537 return LookupQualifiedName(R, DC); 1538 } 1539 1540 // We could not resolve the scope specified to a specific declaration 1541 // context, which means that SS refers to an unknown specialization. 1542 // Name lookup can't find anything in this case. 1543 return false; 1544 } 1545 1546 // Perform unqualified name lookup starting in the given scope. 1547 return LookupName(R, S, AllowBuiltinCreation); 1548} 1549 1550 1551/// @brief Produce a diagnostic describing the ambiguity that resulted 1552/// from name lookup. 1553/// 1554/// @param Result The ambiguous name lookup result. 1555/// 1556/// @param Name The name of the entity that name lookup was 1557/// searching for. 1558/// 1559/// @param NameLoc The location of the name within the source code. 1560/// 1561/// @param LookupRange A source range that provides more 1562/// source-location information concerning the lookup itself. For 1563/// example, this range might highlight a nested-name-specifier that 1564/// precedes the name. 1565/// 1566/// @returns true 1567bool Sema::DiagnoseAmbiguousLookup(LookupResult &Result) { 1568 assert(Result.isAmbiguous() && "Lookup result must be ambiguous"); 1569 1570 DeclarationName Name = Result.getLookupName(); 1571 SourceLocation NameLoc = Result.getNameLoc(); 1572 SourceRange LookupRange = Result.getContextRange(); 1573 1574 switch (Result.getAmbiguityKind()) { 1575 case LookupResult::AmbiguousBaseSubobjects: { 1576 CXXBasePaths *Paths = Result.getBasePaths(); 1577 QualType SubobjectType = Paths->front().back().Base->getType(); 1578 Diag(NameLoc, diag::err_ambiguous_member_multiple_subobjects) 1579 << Name << SubobjectType << getAmbiguousPathsDisplayString(*Paths) 1580 << LookupRange; 1581 1582 DeclContext::lookup_iterator Found = Paths->front().Decls.first; 1583 while (isa<CXXMethodDecl>(*Found) && 1584 cast<CXXMethodDecl>(*Found)->isStatic()) 1585 ++Found; 1586 1587 Diag((*Found)->getLocation(), diag::note_ambiguous_member_found); 1588 1589 return true; 1590 } 1591 1592 case LookupResult::AmbiguousBaseSubobjectTypes: { 1593 Diag(NameLoc, diag::err_ambiguous_member_multiple_subobject_types) 1594 << Name << LookupRange; 1595 1596 CXXBasePaths *Paths = Result.getBasePaths(); 1597 std::set<Decl *> DeclsPrinted; 1598 for (CXXBasePaths::paths_iterator Path = Paths->begin(), 1599 PathEnd = Paths->end(); 1600 Path != PathEnd; ++Path) { 1601 Decl *D = *Path->Decls.first; 1602 if (DeclsPrinted.insert(D).second) 1603 Diag(D->getLocation(), diag::note_ambiguous_member_found); 1604 } 1605 1606 return true; 1607 } 1608 1609 case LookupResult::AmbiguousTagHiding: { 1610 Diag(NameLoc, diag::err_ambiguous_tag_hiding) << Name << LookupRange; 1611 1612 llvm::SmallPtrSet<NamedDecl*,8> TagDecls; 1613 1614 LookupResult::iterator DI, DE = Result.end(); 1615 for (DI = Result.begin(); DI != DE; ++DI) 1616 if (TagDecl *TD = dyn_cast<TagDecl>(*DI)) { 1617 TagDecls.insert(TD); 1618 Diag(TD->getLocation(), diag::note_hidden_tag); 1619 } 1620 1621 for (DI = Result.begin(); DI != DE; ++DI) 1622 if (!isa<TagDecl>(*DI)) 1623 Diag((*DI)->getLocation(), diag::note_hiding_object); 1624 1625 // For recovery purposes, go ahead and implement the hiding. 1626 LookupResult::Filter F = Result.makeFilter(); 1627 while (F.hasNext()) { 1628 if (TagDecls.count(F.next())) 1629 F.erase(); 1630 } 1631 F.done(); 1632 1633 return true; 1634 } 1635 1636 case LookupResult::AmbiguousReference: { 1637 Diag(NameLoc, diag::err_ambiguous_reference) << Name << LookupRange; 1638 1639 LookupResult::iterator DI = Result.begin(), DE = Result.end(); 1640 for (; DI != DE; ++DI) 1641 Diag((*DI)->getLocation(), diag::note_ambiguous_candidate) << *DI; 1642 1643 return true; 1644 } 1645 } 1646 1647 llvm_unreachable("unknown ambiguity kind"); 1648 return true; 1649} 1650 1651namespace { 1652 struct AssociatedLookup { 1653 AssociatedLookup(Sema &S, 1654 Sema::AssociatedNamespaceSet &Namespaces, 1655 Sema::AssociatedClassSet &Classes) 1656 : S(S), Namespaces(Namespaces), Classes(Classes) { 1657 } 1658 1659 Sema &S; 1660 Sema::AssociatedNamespaceSet &Namespaces; 1661 Sema::AssociatedClassSet &Classes; 1662 }; 1663} 1664 1665static void 1666addAssociatedClassesAndNamespaces(AssociatedLookup &Result, QualType T); 1667 1668static void CollectEnclosingNamespace(Sema::AssociatedNamespaceSet &Namespaces, 1669 DeclContext *Ctx) { 1670 // Add the associated namespace for this class. 1671 1672 // We don't use DeclContext::getEnclosingNamespaceContext() as this may 1673 // be a locally scoped record. 1674 1675 // We skip out of inline namespaces. The innermost non-inline namespace 1676 // contains all names of all its nested inline namespaces anyway, so we can 1677 // replace the entire inline namespace tree with its root. 1678 while (Ctx->isRecord() || Ctx->isTransparentContext() || 1679 Ctx->isInlineNamespace()) 1680 Ctx = Ctx->getParent(); 1681 1682 if (Ctx->isFileContext()) 1683 Namespaces.insert(Ctx->getPrimaryContext()); 1684} 1685 1686// \brief Add the associated classes and namespaces for argument-dependent 1687// lookup that involves a template argument (C++ [basic.lookup.koenig]p2). 1688static void 1689addAssociatedClassesAndNamespaces(AssociatedLookup &Result, 1690 const TemplateArgument &Arg) { 1691 // C++ [basic.lookup.koenig]p2, last bullet: 1692 // -- [...] ; 1693 switch (Arg.getKind()) { 1694 case TemplateArgument::Null: 1695 break; 1696 1697 case TemplateArgument::Type: 1698 // [...] the namespaces and classes associated with the types of the 1699 // template arguments provided for template type parameters (excluding 1700 // template template parameters) 1701 addAssociatedClassesAndNamespaces(Result, Arg.getAsType()); 1702 break; 1703 1704 case TemplateArgument::Template: 1705 case TemplateArgument::TemplateExpansion: { 1706 // [...] the namespaces in which any template template arguments are 1707 // defined; and the classes in which any member templates used as 1708 // template template arguments are defined. 1709 TemplateName Template = Arg.getAsTemplateOrTemplatePattern(); 1710 if (ClassTemplateDecl *ClassTemplate 1711 = dyn_cast<ClassTemplateDecl>(Template.getAsTemplateDecl())) { 1712 DeclContext *Ctx = ClassTemplate->getDeclContext(); 1713 if (CXXRecordDecl *EnclosingClass = dyn_cast<CXXRecordDecl>(Ctx)) 1714 Result.Classes.insert(EnclosingClass); 1715 // Add the associated namespace for this class. 1716 CollectEnclosingNamespace(Result.Namespaces, Ctx); 1717 } 1718 break; 1719 } 1720 1721 case TemplateArgument::Declaration: 1722 case TemplateArgument::Integral: 1723 case TemplateArgument::Expression: 1724 // [Note: non-type template arguments do not contribute to the set of 1725 // associated namespaces. ] 1726 break; 1727 1728 case TemplateArgument::Pack: 1729 for (TemplateArgument::pack_iterator P = Arg.pack_begin(), 1730 PEnd = Arg.pack_end(); 1731 P != PEnd; ++P) 1732 addAssociatedClassesAndNamespaces(Result, *P); 1733 break; 1734 } 1735} 1736 1737// \brief Add the associated classes and namespaces for 1738// argument-dependent lookup with an argument of class type 1739// (C++ [basic.lookup.koenig]p2). 1740static void 1741addAssociatedClassesAndNamespaces(AssociatedLookup &Result, 1742 CXXRecordDecl *Class) { 1743 1744 // Just silently ignore anything whose name is __va_list_tag. 1745 if (Class->getDeclName() == Result.S.VAListTagName) 1746 return; 1747 1748 // C++ [basic.lookup.koenig]p2: 1749 // [...] 1750 // -- If T is a class type (including unions), its associated 1751 // classes are: the class itself; the class of which it is a 1752 // member, if any; and its direct and indirect base 1753 // classes. Its associated namespaces are the namespaces in 1754 // which its associated classes are defined. 1755 1756 // Add the class of which it is a member, if any. 1757 DeclContext *Ctx = Class->getDeclContext(); 1758 if (CXXRecordDecl *EnclosingClass = dyn_cast<CXXRecordDecl>(Ctx)) 1759 Result.Classes.insert(EnclosingClass); 1760 // Add the associated namespace for this class. 1761 CollectEnclosingNamespace(Result.Namespaces, Ctx); 1762 1763 // Add the class itself. If we've already seen this class, we don't 1764 // need to visit base classes. 1765 if (!Result.Classes.insert(Class)) 1766 return; 1767 1768 // -- If T is a template-id, its associated namespaces and classes are 1769 // the namespace in which the template is defined; for member 1770 // templates, the member template's class; the namespaces and classes 1771 // associated with the types of the template arguments provided for 1772 // template type parameters (excluding template template parameters); the 1773 // namespaces in which any template template arguments are defined; and 1774 // the classes in which any member templates used as template template 1775 // arguments are defined. [Note: non-type template arguments do not 1776 // contribute to the set of associated namespaces. ] 1777 if (ClassTemplateSpecializationDecl *Spec 1778 = dyn_cast<ClassTemplateSpecializationDecl>(Class)) { 1779 DeclContext *Ctx = Spec->getSpecializedTemplate()->getDeclContext(); 1780 if (CXXRecordDecl *EnclosingClass = dyn_cast<CXXRecordDecl>(Ctx)) 1781 Result.Classes.insert(EnclosingClass); 1782 // Add the associated namespace for this class. 1783 CollectEnclosingNamespace(Result.Namespaces, Ctx); 1784 1785 const TemplateArgumentList &TemplateArgs = Spec->getTemplateArgs(); 1786 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I) 1787 addAssociatedClassesAndNamespaces(Result, TemplateArgs[I]); 1788 } 1789 1790 // Only recurse into base classes for complete types. 1791 if (!Class->hasDefinition()) { 1792 // FIXME: we might need to instantiate templates here 1793 return; 1794 } 1795 1796 // Add direct and indirect base classes along with their associated 1797 // namespaces. 1798 llvm::SmallVector<CXXRecordDecl *, 32> Bases; 1799 Bases.push_back(Class); 1800 while (!Bases.empty()) { 1801 // Pop this class off the stack. 1802 Class = Bases.back(); 1803 Bases.pop_back(); 1804 1805 // Visit the base classes. 1806 for (CXXRecordDecl::base_class_iterator Base = Class->bases_begin(), 1807 BaseEnd = Class->bases_end(); 1808 Base != BaseEnd; ++Base) { 1809 const RecordType *BaseType = Base->getType()->getAs<RecordType>(); 1810 // In dependent contexts, we do ADL twice, and the first time around, 1811 // the base type might be a dependent TemplateSpecializationType, or a 1812 // TemplateTypeParmType. If that happens, simply ignore it. 1813 // FIXME: If we want to support export, we probably need to add the 1814 // namespace of the template in a TemplateSpecializationType, or even 1815 // the classes and namespaces of known non-dependent arguments. 1816 if (!BaseType) 1817 continue; 1818 CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(BaseType->getDecl()); 1819 if (Result.Classes.insert(BaseDecl)) { 1820 // Find the associated namespace for this base class. 1821 DeclContext *BaseCtx = BaseDecl->getDeclContext(); 1822 CollectEnclosingNamespace(Result.Namespaces, BaseCtx); 1823 1824 // Make sure we visit the bases of this base class. 1825 if (BaseDecl->bases_begin() != BaseDecl->bases_end()) 1826 Bases.push_back(BaseDecl); 1827 } 1828 } 1829 } 1830} 1831 1832// \brief Add the associated classes and namespaces for 1833// argument-dependent lookup with an argument of type T 1834// (C++ [basic.lookup.koenig]p2). 1835static void 1836addAssociatedClassesAndNamespaces(AssociatedLookup &Result, QualType Ty) { 1837 // C++ [basic.lookup.koenig]p2: 1838 // 1839 // For each argument type T in the function call, there is a set 1840 // of zero or more associated namespaces and a set of zero or more 1841 // associated classes to be considered. The sets of namespaces and 1842 // classes is determined entirely by the types of the function 1843 // arguments (and the namespace of any template template 1844 // argument). Typedef names and using-declarations used to specify 1845 // the types do not contribute to this set. The sets of namespaces 1846 // and classes are determined in the following way: 1847 1848 llvm::SmallVector<const Type *, 16> Queue; 1849 const Type *T = Ty->getCanonicalTypeInternal().getTypePtr(); 1850 1851 while (true) { 1852 switch (T->getTypeClass()) { 1853 1854#define TYPE(Class, Base) 1855#define DEPENDENT_TYPE(Class, Base) case Type::Class: 1856#define NON_CANONICAL_TYPE(Class, Base) case Type::Class: 1857#define NON_CANONICAL_UNLESS_DEPENDENT_TYPE(Class, Base) case Type::Class: 1858#define ABSTRACT_TYPE(Class, Base) 1859#include "clang/AST/TypeNodes.def" 1860 // T is canonical. We can also ignore dependent types because 1861 // we don't need to do ADL at the definition point, but if we 1862 // wanted to implement template export (or if we find some other 1863 // use for associated classes and namespaces...) this would be 1864 // wrong. 1865 break; 1866 1867 // -- If T is a pointer to U or an array of U, its associated 1868 // namespaces and classes are those associated with U. 1869 case Type::Pointer: 1870 T = cast<PointerType>(T)->getPointeeType().getTypePtr(); 1871 continue; 1872 case Type::ConstantArray: 1873 case Type::IncompleteArray: 1874 case Type::VariableArray: 1875 T = cast<ArrayType>(T)->getElementType().getTypePtr(); 1876 continue; 1877 1878 // -- If T is a fundamental type, its associated sets of 1879 // namespaces and classes are both empty. 1880 case Type::Builtin: 1881 break; 1882 1883 // -- If T is a class type (including unions), its associated 1884 // classes are: the class itself; the class of which it is a 1885 // member, if any; and its direct and indirect base 1886 // classes. Its associated namespaces are the namespaces in 1887 // which its associated classes are defined. 1888 case Type::Record: { 1889 CXXRecordDecl *Class 1890 = cast<CXXRecordDecl>(cast<RecordType>(T)->getDecl()); 1891 addAssociatedClassesAndNamespaces(Result, Class); 1892 break; 1893 } 1894 1895 // -- If T is an enumeration type, its associated namespace is 1896 // the namespace in which it is defined. If it is class 1897 // member, its associated class is the member's class; else 1898 // it has no associated class. 1899 case Type::Enum: { 1900 EnumDecl *Enum = cast<EnumType>(T)->getDecl(); 1901 1902 DeclContext *Ctx = Enum->getDeclContext(); 1903 if (CXXRecordDecl *EnclosingClass = dyn_cast<CXXRecordDecl>(Ctx)) 1904 Result.Classes.insert(EnclosingClass); 1905 1906 // Add the associated namespace for this class. 1907 CollectEnclosingNamespace(Result.Namespaces, Ctx); 1908 1909 break; 1910 } 1911 1912 // -- If T is a function type, its associated namespaces and 1913 // classes are those associated with the function parameter 1914 // types and those associated with the return type. 1915 case Type::FunctionProto: { 1916 const FunctionProtoType *Proto = cast<FunctionProtoType>(T); 1917 for (FunctionProtoType::arg_type_iterator Arg = Proto->arg_type_begin(), 1918 ArgEnd = Proto->arg_type_end(); 1919 Arg != ArgEnd; ++Arg) 1920 Queue.push_back(Arg->getTypePtr()); 1921 // fallthrough 1922 } 1923 case Type::FunctionNoProto: { 1924 const FunctionType *FnType = cast<FunctionType>(T); 1925 T = FnType->getResultType().getTypePtr(); 1926 continue; 1927 } 1928 1929 // -- If T is a pointer to a member function of a class X, its 1930 // associated namespaces and classes are those associated 1931 // with the function parameter types and return type, 1932 // together with those associated with X. 1933 // 1934 // -- If T is a pointer to a data member of class X, its 1935 // associated namespaces and classes are those associated 1936 // with the member type together with those associated with 1937 // X. 1938 case Type::MemberPointer: { 1939 const MemberPointerType *MemberPtr = cast<MemberPointerType>(T); 1940 1941 // Queue up the class type into which this points. 1942 Queue.push_back(MemberPtr->getClass()); 1943 1944 // And directly continue with the pointee type. 1945 T = MemberPtr->getPointeeType().getTypePtr(); 1946 continue; 1947 } 1948 1949 // As an extension, treat this like a normal pointer. 1950 case Type::BlockPointer: 1951 T = cast<BlockPointerType>(T)->getPointeeType().getTypePtr(); 1952 continue; 1953 1954 // References aren't covered by the standard, but that's such an 1955 // obvious defect that we cover them anyway. 1956 case Type::LValueReference: 1957 case Type::RValueReference: 1958 T = cast<ReferenceType>(T)->getPointeeType().getTypePtr(); 1959 continue; 1960 1961 // These are fundamental types. 1962 case Type::Vector: 1963 case Type::ExtVector: 1964 case Type::Complex: 1965 break; 1966 1967 // If T is an Objective-C object or interface type, or a pointer to an 1968 // object or interface type, the associated namespace is the global 1969 // namespace. 1970 case Type::ObjCObject: 1971 case Type::ObjCInterface: 1972 case Type::ObjCObjectPointer: 1973 Result.Namespaces.insert(Result.S.Context.getTranslationUnitDecl()); 1974 break; 1975 } 1976 1977 if (Queue.empty()) break; 1978 T = Queue.back(); 1979 Queue.pop_back(); 1980 } 1981} 1982 1983/// \brief Find the associated classes and namespaces for 1984/// argument-dependent lookup for a call with the given set of 1985/// arguments. 1986/// 1987/// This routine computes the sets of associated classes and associated 1988/// namespaces searched by argument-dependent lookup 1989/// (C++ [basic.lookup.argdep]) for a given set of arguments. 1990void 1991Sema::FindAssociatedClassesAndNamespaces(Expr **Args, unsigned NumArgs, 1992 AssociatedNamespaceSet &AssociatedNamespaces, 1993 AssociatedClassSet &AssociatedClasses) { 1994 AssociatedNamespaces.clear(); 1995 AssociatedClasses.clear(); 1996 1997 AssociatedLookup Result(*this, AssociatedNamespaces, AssociatedClasses); 1998 1999 // C++ [basic.lookup.koenig]p2: 2000 // For each argument type T in the function call, there is a set 2001 // of zero or more associated namespaces and a set of zero or more 2002 // associated classes to be considered. The sets of namespaces and 2003 // classes is determined entirely by the types of the function 2004 // arguments (and the namespace of any template template 2005 // argument). 2006 for (unsigned ArgIdx = 0; ArgIdx != NumArgs; ++ArgIdx) { 2007 Expr *Arg = Args[ArgIdx]; 2008 2009 if (Arg->getType() != Context.OverloadTy) { 2010 addAssociatedClassesAndNamespaces(Result, Arg->getType()); 2011 continue; 2012 } 2013 2014 // [...] In addition, if the argument is the name or address of a 2015 // set of overloaded functions and/or function templates, its 2016 // associated classes and namespaces are the union of those 2017 // associated with each of the members of the set: the namespace 2018 // in which the function or function template is defined and the 2019 // classes and namespaces associated with its (non-dependent) 2020 // parameter types and return type. 2021 Arg = Arg->IgnoreParens(); 2022 if (UnaryOperator *unaryOp = dyn_cast<UnaryOperator>(Arg)) 2023 if (unaryOp->getOpcode() == UO_AddrOf) 2024 Arg = unaryOp->getSubExpr(); 2025 2026 UnresolvedLookupExpr *ULE = dyn_cast<UnresolvedLookupExpr>(Arg); 2027 if (!ULE) continue; 2028 2029 for (UnresolvedSetIterator I = ULE->decls_begin(), E = ULE->decls_end(); 2030 I != E; ++I) { 2031 // Look through any using declarations to find the underlying function. 2032 NamedDecl *Fn = (*I)->getUnderlyingDecl(); 2033 2034 FunctionDecl *FDecl = dyn_cast<FunctionDecl>(Fn); 2035 if (!FDecl) 2036 FDecl = cast<FunctionTemplateDecl>(Fn)->getTemplatedDecl(); 2037 2038 // Add the classes and namespaces associated with the parameter 2039 // types and return type of this function. 2040 addAssociatedClassesAndNamespaces(Result, FDecl->getType()); 2041 } 2042 } 2043} 2044 2045/// IsAcceptableNonMemberOperatorCandidate - Determine whether Fn is 2046/// an acceptable non-member overloaded operator for a call whose 2047/// arguments have types T1 (and, if non-empty, T2). This routine 2048/// implements the check in C++ [over.match.oper]p3b2 concerning 2049/// enumeration types. 2050static bool 2051IsAcceptableNonMemberOperatorCandidate(FunctionDecl *Fn, 2052 QualType T1, QualType T2, 2053 ASTContext &Context) { 2054 if (T1->isDependentType() || (!T2.isNull() && T2->isDependentType())) 2055 return true; 2056 2057 if (T1->isRecordType() || (!T2.isNull() && T2->isRecordType())) 2058 return true; 2059 2060 const FunctionProtoType *Proto = Fn->getType()->getAs<FunctionProtoType>(); 2061 if (Proto->getNumArgs() < 1) 2062 return false; 2063 2064 if (T1->isEnumeralType()) { 2065 QualType ArgType = Proto->getArgType(0).getNonReferenceType(); 2066 if (Context.hasSameUnqualifiedType(T1, ArgType)) 2067 return true; 2068 } 2069 2070 if (Proto->getNumArgs() < 2) 2071 return false; 2072 2073 if (!T2.isNull() && T2->isEnumeralType()) { 2074 QualType ArgType = Proto->getArgType(1).getNonReferenceType(); 2075 if (Context.hasSameUnqualifiedType(T2, ArgType)) 2076 return true; 2077 } 2078 2079 return false; 2080} 2081 2082NamedDecl *Sema::LookupSingleName(Scope *S, DeclarationName Name, 2083 SourceLocation Loc, 2084 LookupNameKind NameKind, 2085 RedeclarationKind Redecl) { 2086 LookupResult R(*this, Name, Loc, NameKind, Redecl); 2087 LookupName(R, S); 2088 return R.getAsSingle<NamedDecl>(); 2089} 2090 2091/// \brief Find the protocol with the given name, if any. 2092ObjCProtocolDecl *Sema::LookupProtocol(IdentifierInfo *II, 2093 SourceLocation IdLoc) { 2094 Decl *D = LookupSingleName(TUScope, II, IdLoc, 2095 LookupObjCProtocolName); 2096 return cast_or_null<ObjCProtocolDecl>(D); 2097} 2098 2099void Sema::LookupOverloadedOperatorName(OverloadedOperatorKind Op, Scope *S, 2100 QualType T1, QualType T2, 2101 UnresolvedSetImpl &Functions) { 2102 // C++ [over.match.oper]p3: 2103 // -- The set of non-member candidates is the result of the 2104 // unqualified lookup of operator@ in the context of the 2105 // expression according to the usual rules for name lookup in 2106 // unqualified function calls (3.4.2) except that all member 2107 // functions are ignored. However, if no operand has a class 2108 // type, only those non-member functions in the lookup set 2109 // that have a first parameter of type T1 or "reference to 2110 // (possibly cv-qualified) T1", when T1 is an enumeration 2111 // type, or (if there is a right operand) a second parameter 2112 // of type T2 or "reference to (possibly cv-qualified) T2", 2113 // when T2 is an enumeration type, are candidate functions. 2114 DeclarationName OpName = Context.DeclarationNames.getCXXOperatorName(Op); 2115 LookupResult Operators(*this, OpName, SourceLocation(), LookupOperatorName); 2116 LookupName(Operators, S); 2117 2118 assert(!Operators.isAmbiguous() && "Operator lookup cannot be ambiguous"); 2119 2120 if (Operators.empty()) 2121 return; 2122 2123 for (LookupResult::iterator Op = Operators.begin(), OpEnd = Operators.end(); 2124 Op != OpEnd; ++Op) { 2125 NamedDecl *Found = (*Op)->getUnderlyingDecl(); 2126 if (FunctionDecl *FD = dyn_cast<FunctionDecl>(Found)) { 2127 if (IsAcceptableNonMemberOperatorCandidate(FD, T1, T2, Context)) 2128 Functions.addDecl(*Op, Op.getAccess()); // FIXME: canonical FD 2129 } else if (FunctionTemplateDecl *FunTmpl 2130 = dyn_cast<FunctionTemplateDecl>(Found)) { 2131 // FIXME: friend operators? 2132 // FIXME: do we need to check IsAcceptableNonMemberOperatorCandidate, 2133 // later? 2134 if (!FunTmpl->getDeclContext()->isRecord()) 2135 Functions.addDecl(*Op, Op.getAccess()); 2136 } 2137 } 2138} 2139 2140Sema::SpecialMemberOverloadResult *Sema::LookupSpecialMember(CXXRecordDecl *D, 2141 CXXSpecialMember SM, 2142 bool ConstArg, 2143 bool VolatileArg, 2144 bool RValueThis, 2145 bool ConstThis, 2146 bool VolatileThis) { 2147 D = D->getDefinition(); 2148 assert((D && !D->isBeingDefined()) && 2149 "doing special member lookup into record that isn't fully complete"); 2150 if (RValueThis || ConstThis || VolatileThis) 2151 assert((SM == CXXCopyAssignment || SM == CXXMoveAssignment) && 2152 "constructors and destructors always have unqualified lvalue this"); 2153 if (ConstArg || VolatileArg) 2154 assert((SM != CXXDefaultConstructor && SM != CXXDestructor) && 2155 "parameter-less special members can't have qualified arguments"); 2156 2157 llvm::FoldingSetNodeID ID; 2158 ID.AddPointer(D); 2159 ID.AddInteger(SM); 2160 ID.AddInteger(ConstArg); 2161 ID.AddInteger(VolatileArg); 2162 ID.AddInteger(RValueThis); 2163 ID.AddInteger(ConstThis); 2164 ID.AddInteger(VolatileThis); 2165 2166 void *InsertPoint; 2167 SpecialMemberOverloadResult *Result = 2168 SpecialMemberCache.FindNodeOrInsertPos(ID, InsertPoint); 2169 2170 // This was already cached 2171 if (Result) 2172 return Result; 2173 2174 Result = BumpAlloc.Allocate<SpecialMemberOverloadResult>(); 2175 Result = new (Result) SpecialMemberOverloadResult(ID); 2176 SpecialMemberCache.InsertNode(Result, InsertPoint); 2177 2178 if (SM == CXXDestructor) { 2179 if (!D->hasDeclaredDestructor()) 2180 DeclareImplicitDestructor(D); 2181 CXXDestructorDecl *DD = D->getDestructor(); 2182 assert(DD && "record without a destructor"); 2183 Result->setMethod(DD); 2184 Result->setSuccess(DD->isDeleted()); 2185 Result->setConstParamMatch(false); 2186 return Result; 2187 } 2188 2189 // Prepare for overload resolution. Here we construct a synthetic argument 2190 // if necessary and make sure that implicit functions are declared. 2191 CanQualType CanTy = Context.getCanonicalType(Context.getTagDeclType(D)); 2192 DeclarationName Name; 2193 Expr *Arg = 0; 2194 unsigned NumArgs; 2195 2196 if (SM == CXXDefaultConstructor) { 2197 Name = Context.DeclarationNames.getCXXConstructorName(CanTy); 2198 NumArgs = 0; 2199 if (D->needsImplicitDefaultConstructor()) 2200 DeclareImplicitDefaultConstructor(D); 2201 } else { 2202 if (SM == CXXCopyConstructor || SM == CXXMoveConstructor) { 2203 Name = Context.DeclarationNames.getCXXConstructorName(CanTy); 2204 if (!D->hasDeclaredCopyConstructor()) 2205 DeclareImplicitCopyConstructor(D); 2206 // TODO: Move constructors 2207 } else { 2208 Name = Context.DeclarationNames.getCXXOperatorName(OO_Equal); 2209 if (!D->hasDeclaredCopyAssignment()) 2210 DeclareImplicitCopyAssignment(D); 2211 // TODO: Move assignment 2212 } 2213 2214 QualType ArgType = CanTy; 2215 if (ConstArg) 2216 ArgType.addConst(); 2217 if (VolatileArg) 2218 ArgType.addVolatile(); 2219 2220 // This isn't /really/ specified by the standard, but it's implied 2221 // we should be working from an RValue in the case of move to ensure 2222 // that we prefer to bind to rvalue references, and an LValue in the 2223 // case of copy to ensure we don't bind to rvalue references. 2224 // Possibly an XValue is actually correct in the case of move, but 2225 // there is no semantic difference for class types in this restricted 2226 // case. 2227 ExprValueKind VK; 2228 if (SM == CXXCopyConstructor || SM == CXXCopyAssignment) 2229 VK = VK_LValue; 2230 else 2231 VK = VK_RValue; 2232 2233 NumArgs = 1; 2234 Arg = new (Context) OpaqueValueExpr(SourceLocation(), ArgType, VK); 2235 } 2236 2237 // Create the object argument 2238 QualType ThisTy = CanTy; 2239 if (ConstThis) 2240 ThisTy.addConst(); 2241 if (VolatileThis) 2242 ThisTy.addVolatile(); 2243 Expr::Classification Classification = 2244 (new (Context) OpaqueValueExpr(SourceLocation(), ThisTy, 2245 RValueThis ? VK_RValue : VK_LValue))-> 2246 Classify(Context); 2247 2248 // Now we perform lookup on the name we computed earlier and do overload 2249 // resolution. Lookup is only performed directly into the class since there 2250 // will always be a (possibly implicit) declaration to shadow any others. 2251 OverloadCandidateSet OCS((SourceLocation())); 2252 DeclContext::lookup_iterator I, E; 2253 Result->setConstParamMatch(false); 2254 2255 llvm::tie(I, E) = D->lookup(Name); 2256 assert((I != E) && 2257 "lookup for a constructor or assignment operator was empty"); 2258 for ( ; I != E; ++I) { 2259 Decl *DD = *I; 2260 2261 if (UsingShadowDecl *U = dyn_cast<UsingShadowDecl>(D)) 2262 DD = U->getTargetDecl(); 2263 2264 if (DD->isInvalidDecl()) 2265 continue; 2266 2267 if (CXXMethodDecl *M = dyn_cast<CXXMethodDecl>(DD)) { 2268 if (SM == CXXCopyAssignment || SM == CXXMoveAssignment) 2269 AddMethodCandidate(M, DeclAccessPair::make(M, AS_public), D, ThisTy, 2270 Classification, &Arg, NumArgs, OCS, true); 2271 else 2272 AddOverloadCandidate(M, DeclAccessPair::make(M, AS_public), &Arg, 2273 NumArgs, OCS, true); 2274 2275 // Here we're looking for a const parameter to speed up creation of 2276 // implicit copy methods. 2277 if ((SM == CXXCopyAssignment && M->isCopyAssignmentOperator()) || 2278 (SM == CXXCopyConstructor && 2279 cast<CXXConstructorDecl>(M)->isCopyConstructor())) { 2280 QualType ArgType = M->getType()->getAs<FunctionProtoType>()->getArgType(0); 2281 if (!ArgType->isReferenceType() || 2282 ArgType->getPointeeType().isConstQualified()) 2283 Result->setConstParamMatch(true); 2284 } 2285 } else if (FunctionTemplateDecl *Tmpl = 2286 dyn_cast<FunctionTemplateDecl>(DD)) { 2287 if (SM == CXXCopyAssignment || SM == CXXMoveAssignment) 2288 AddMethodTemplateCandidate(Tmpl, DeclAccessPair::make(Tmpl, AS_public), 2289 D, 0, ThisTy, Classification, &Arg, NumArgs, 2290 OCS, true); 2291 else 2292 AddTemplateOverloadCandidate(Tmpl, DeclAccessPair::make(Tmpl, AS_public), 2293 0, &Arg, NumArgs, OCS, true); 2294 } 2295 } 2296 2297 OverloadCandidateSet::iterator Best; 2298 switch (OCS.BestViableFunction(*this, SourceLocation(), Best)) { 2299 case OR_Success: 2300 Result->setMethod(cast<CXXMethodDecl>(Best->Function)); 2301 Result->setSuccess(true); 2302 break; 2303 2304 case OR_Deleted: 2305 Result->setMethod(cast<CXXMethodDecl>(Best->Function)); 2306 Result->setSuccess(false); 2307 break; 2308 2309 case OR_Ambiguous: 2310 case OR_No_Viable_Function: 2311 Result->setMethod(0); 2312 Result->setSuccess(false); 2313 break; 2314 } 2315 2316 return Result; 2317} 2318 2319/// \brief Look up the default constructor for the given class. 2320CXXConstructorDecl *Sema::LookupDefaultConstructor(CXXRecordDecl *Class) { 2321 SpecialMemberOverloadResult *Result = 2322 LookupSpecialMember(Class, CXXDefaultConstructor, false, false, false, 2323 false, false); 2324 2325 return cast_or_null<CXXConstructorDecl>(Result->getMethod()); 2326} 2327 2328/// \brief Look up the copying constructor for the given class. 2329CXXConstructorDecl *Sema::LookupCopyingConstructor(CXXRecordDecl *Class, 2330 unsigned Quals, 2331 bool *ConstParamMatch) { 2332 assert(!(Quals & ~(Qualifiers::Const | Qualifiers::Volatile)) && 2333 "non-const, non-volatile qualifiers for copy ctor arg"); 2334 SpecialMemberOverloadResult *Result = 2335 LookupSpecialMember(Class, CXXCopyConstructor, Quals & Qualifiers::Const, 2336 Quals & Qualifiers::Volatile, false, false, false); 2337 2338 if (ConstParamMatch) 2339 *ConstParamMatch = Result->hasConstParamMatch(); 2340 2341 return cast_or_null<CXXConstructorDecl>(Result->getMethod()); 2342} 2343 2344/// \brief Look up the constructors for the given class. 2345DeclContext::lookup_result Sema::LookupConstructors(CXXRecordDecl *Class) { 2346 // If the implicit constructors have not yet been declared, do so now. 2347 if (CanDeclareSpecialMemberFunction(Context, Class)) { 2348 if (Class->needsImplicitDefaultConstructor()) 2349 DeclareImplicitDefaultConstructor(Class); 2350 if (!Class->hasDeclaredCopyConstructor()) 2351 DeclareImplicitCopyConstructor(Class); 2352 } 2353 2354 CanQualType T = Context.getCanonicalType(Context.getTypeDeclType(Class)); 2355 DeclarationName Name = Context.DeclarationNames.getCXXConstructorName(T); 2356 return Class->lookup(Name); 2357} 2358 2359/// \brief Look up the copying assignment operator for the given class. 2360CXXMethodDecl *Sema::LookupCopyingAssignment(CXXRecordDecl *Class, 2361 unsigned Quals, bool RValueThis, 2362 unsigned ThisQuals, 2363 bool *ConstParamMatch) { 2364 assert(!(Quals & ~(Qualifiers::Const | Qualifiers::Volatile)) && 2365 "non-const, non-volatile qualifiers for copy assignment arg"); 2366 assert(!(ThisQuals & ~(Qualifiers::Const | Qualifiers::Volatile)) && 2367 "non-const, non-volatile qualifiers for copy assignment this"); 2368 SpecialMemberOverloadResult *Result = 2369 LookupSpecialMember(Class, CXXCopyAssignment, Quals & Qualifiers::Const, 2370 Quals & Qualifiers::Volatile, RValueThis, 2371 ThisQuals & Qualifiers::Const, 2372 ThisQuals & Qualifiers::Volatile); 2373 2374 if (ConstParamMatch) 2375 *ConstParamMatch = Result->hasConstParamMatch(); 2376 2377 return Result->getMethod(); 2378} 2379 2380/// \brief Look for the destructor of the given class. 2381/// 2382/// During semantic analysis, this routine should be used in lieu of 2383/// CXXRecordDecl::getDestructor(). 2384/// 2385/// \returns The destructor for this class. 2386CXXDestructorDecl *Sema::LookupDestructor(CXXRecordDecl *Class) { 2387 return cast<CXXDestructorDecl>(LookupSpecialMember(Class, CXXDestructor, 2388 false, false, false, 2389 false, false)->getMethod()); 2390} 2391 2392void ADLResult::insert(NamedDecl *New) { 2393 NamedDecl *&Old = Decls[cast<NamedDecl>(New->getCanonicalDecl())]; 2394 2395 // If we haven't yet seen a decl for this key, or the last decl 2396 // was exactly this one, we're done. 2397 if (Old == 0 || Old == New) { 2398 Old = New; 2399 return; 2400 } 2401 2402 // Otherwise, decide which is a more recent redeclaration. 2403 FunctionDecl *OldFD, *NewFD; 2404 if (isa<FunctionTemplateDecl>(New)) { 2405 OldFD = cast<FunctionTemplateDecl>(Old)->getTemplatedDecl(); 2406 NewFD = cast<FunctionTemplateDecl>(New)->getTemplatedDecl(); 2407 } else { 2408 OldFD = cast<FunctionDecl>(Old); 2409 NewFD = cast<FunctionDecl>(New); 2410 } 2411 2412 FunctionDecl *Cursor = NewFD; 2413 while (true) { 2414 Cursor = Cursor->getPreviousDeclaration(); 2415 2416 // If we got to the end without finding OldFD, OldFD is the newer 2417 // declaration; leave things as they are. 2418 if (!Cursor) return; 2419 2420 // If we do find OldFD, then NewFD is newer. 2421 if (Cursor == OldFD) break; 2422 2423 // Otherwise, keep looking. 2424 } 2425 2426 Old = New; 2427} 2428 2429void Sema::ArgumentDependentLookup(DeclarationName Name, bool Operator, 2430 Expr **Args, unsigned NumArgs, 2431 ADLResult &Result, 2432 bool StdNamespaceIsAssociated) { 2433 // Find all of the associated namespaces and classes based on the 2434 // arguments we have. 2435 AssociatedNamespaceSet AssociatedNamespaces; 2436 AssociatedClassSet AssociatedClasses; 2437 FindAssociatedClassesAndNamespaces(Args, NumArgs, 2438 AssociatedNamespaces, 2439 AssociatedClasses); 2440 if (StdNamespaceIsAssociated && StdNamespace) 2441 AssociatedNamespaces.insert(getStdNamespace()); 2442 2443 QualType T1, T2; 2444 if (Operator) { 2445 T1 = Args[0]->getType(); 2446 if (NumArgs >= 2) 2447 T2 = Args[1]->getType(); 2448 } 2449 2450 // C++ [basic.lookup.argdep]p3: 2451 // Let X be the lookup set produced by unqualified lookup (3.4.1) 2452 // and let Y be the lookup set produced by argument dependent 2453 // lookup (defined as follows). If X contains [...] then Y is 2454 // empty. Otherwise Y is the set of declarations found in the 2455 // namespaces associated with the argument types as described 2456 // below. The set of declarations found by the lookup of the name 2457 // is the union of X and Y. 2458 // 2459 // Here, we compute Y and add its members to the overloaded 2460 // candidate set. 2461 for (AssociatedNamespaceSet::iterator NS = AssociatedNamespaces.begin(), 2462 NSEnd = AssociatedNamespaces.end(); 2463 NS != NSEnd; ++NS) { 2464 // When considering an associated namespace, the lookup is the 2465 // same as the lookup performed when the associated namespace is 2466 // used as a qualifier (3.4.3.2) except that: 2467 // 2468 // -- Any using-directives in the associated namespace are 2469 // ignored. 2470 // 2471 // -- Any namespace-scope friend functions declared in 2472 // associated classes are visible within their respective 2473 // namespaces even if they are not visible during an ordinary 2474 // lookup (11.4). 2475 DeclContext::lookup_iterator I, E; 2476 for (llvm::tie(I, E) = (*NS)->lookup(Name); I != E; ++I) { 2477 NamedDecl *D = *I; 2478 // If the only declaration here is an ordinary friend, consider 2479 // it only if it was declared in an associated classes. 2480 if (D->getIdentifierNamespace() == Decl::IDNS_OrdinaryFriend) { 2481 DeclContext *LexDC = D->getLexicalDeclContext(); 2482 if (!AssociatedClasses.count(cast<CXXRecordDecl>(LexDC))) 2483 continue; 2484 } 2485 2486 if (isa<UsingShadowDecl>(D)) 2487 D = cast<UsingShadowDecl>(D)->getTargetDecl(); 2488 2489 if (isa<FunctionDecl>(D)) { 2490 if (Operator && 2491 !IsAcceptableNonMemberOperatorCandidate(cast<FunctionDecl>(D), 2492 T1, T2, Context)) 2493 continue; 2494 } else if (!isa<FunctionTemplateDecl>(D)) 2495 continue; 2496 2497 Result.insert(D); 2498 } 2499 } 2500} 2501 2502//---------------------------------------------------------------------------- 2503// Search for all visible declarations. 2504//---------------------------------------------------------------------------- 2505VisibleDeclConsumer::~VisibleDeclConsumer() { } 2506 2507namespace { 2508 2509class ShadowContextRAII; 2510 2511class VisibleDeclsRecord { 2512public: 2513 /// \brief An entry in the shadow map, which is optimized to store a 2514 /// single declaration (the common case) but can also store a list 2515 /// of declarations. 2516 class ShadowMapEntry { 2517 typedef llvm::SmallVector<NamedDecl *, 4> DeclVector; 2518 2519 /// \brief Contains either the solitary NamedDecl * or a vector 2520 /// of declarations. 2521 llvm::PointerUnion<NamedDecl *, DeclVector*> DeclOrVector; 2522 2523 public: 2524 ShadowMapEntry() : DeclOrVector() { } 2525 2526 void Add(NamedDecl *ND); 2527 void Destroy(); 2528 2529 // Iteration. 2530 typedef NamedDecl * const *iterator; 2531 iterator begin(); 2532 iterator end(); 2533 }; 2534 2535private: 2536 /// \brief A mapping from declaration names to the declarations that have 2537 /// this name within a particular scope. 2538 typedef llvm::DenseMap<DeclarationName, ShadowMapEntry> ShadowMap; 2539 2540 /// \brief A list of shadow maps, which is used to model name hiding. 2541 std::list<ShadowMap> ShadowMaps; 2542 2543 /// \brief The declaration contexts we have already visited. 2544 llvm::SmallPtrSet<DeclContext *, 8> VisitedContexts; 2545 2546 friend class ShadowContextRAII; 2547 2548public: 2549 /// \brief Determine whether we have already visited this context 2550 /// (and, if not, note that we are going to visit that context now). 2551 bool visitedContext(DeclContext *Ctx) { 2552 return !VisitedContexts.insert(Ctx); 2553 } 2554 2555 bool alreadyVisitedContext(DeclContext *Ctx) { 2556 return VisitedContexts.count(Ctx); 2557 } 2558 2559 /// \brief Determine whether the given declaration is hidden in the 2560 /// current scope. 2561 /// 2562 /// \returns the declaration that hides the given declaration, or 2563 /// NULL if no such declaration exists. 2564 NamedDecl *checkHidden(NamedDecl *ND); 2565 2566 /// \brief Add a declaration to the current shadow map. 2567 void add(NamedDecl *ND) { ShadowMaps.back()[ND->getDeclName()].Add(ND); } 2568}; 2569 2570/// \brief RAII object that records when we've entered a shadow context. 2571class ShadowContextRAII { 2572 VisibleDeclsRecord &Visible; 2573 2574 typedef VisibleDeclsRecord::ShadowMap ShadowMap; 2575 2576public: 2577 ShadowContextRAII(VisibleDeclsRecord &Visible) : Visible(Visible) { 2578 Visible.ShadowMaps.push_back(ShadowMap()); 2579 } 2580 2581 ~ShadowContextRAII() { 2582 for (ShadowMap::iterator E = Visible.ShadowMaps.back().begin(), 2583 EEnd = Visible.ShadowMaps.back().end(); 2584 E != EEnd; 2585 ++E) 2586 E->second.Destroy(); 2587 2588 Visible.ShadowMaps.pop_back(); 2589 } 2590}; 2591 2592} // end anonymous namespace 2593 2594void VisibleDeclsRecord::ShadowMapEntry::Add(NamedDecl *ND) { 2595 if (DeclOrVector.isNull()) { 2596 // 0 - > 1 elements: just set the single element information. 2597 DeclOrVector = ND; 2598 return; 2599 } 2600 2601 if (NamedDecl *PrevND = DeclOrVector.dyn_cast<NamedDecl *>()) { 2602 // 1 -> 2 elements: create the vector of results and push in the 2603 // existing declaration. 2604 DeclVector *Vec = new DeclVector; 2605 Vec->push_back(PrevND); 2606 DeclOrVector = Vec; 2607 } 2608 2609 // Add the new element to the end of the vector. 2610 DeclOrVector.get<DeclVector*>()->push_back(ND); 2611} 2612 2613void VisibleDeclsRecord::ShadowMapEntry::Destroy() { 2614 if (DeclVector *Vec = DeclOrVector.dyn_cast<DeclVector *>()) { 2615 delete Vec; 2616 DeclOrVector = ((NamedDecl *)0); 2617 } 2618} 2619 2620VisibleDeclsRecord::ShadowMapEntry::iterator 2621VisibleDeclsRecord::ShadowMapEntry::begin() { 2622 if (DeclOrVector.isNull()) 2623 return 0; 2624 2625 if (DeclOrVector.is<NamedDecl *>()) 2626 return DeclOrVector.getAddrOf<NamedDecl *>(); 2627 2628 return DeclOrVector.get<DeclVector *>()->begin(); 2629} 2630 2631VisibleDeclsRecord::ShadowMapEntry::iterator 2632VisibleDeclsRecord::ShadowMapEntry::end() { 2633 if (DeclOrVector.isNull()) 2634 return 0; 2635 2636 if (DeclOrVector.is<NamedDecl *>()) 2637 return DeclOrVector.getAddrOf<NamedDecl *>() + 1; 2638 2639 return DeclOrVector.get<DeclVector *>()->end(); 2640} 2641 2642NamedDecl *VisibleDeclsRecord::checkHidden(NamedDecl *ND) { 2643 // Look through using declarations. 2644 ND = ND->getUnderlyingDecl(); 2645 2646 unsigned IDNS = ND->getIdentifierNamespace(); 2647 std::list<ShadowMap>::reverse_iterator SM = ShadowMaps.rbegin(); 2648 for (std::list<ShadowMap>::reverse_iterator SMEnd = ShadowMaps.rend(); 2649 SM != SMEnd; ++SM) { 2650 ShadowMap::iterator Pos = SM->find(ND->getDeclName()); 2651 if (Pos == SM->end()) 2652 continue; 2653 2654 for (ShadowMapEntry::iterator I = Pos->second.begin(), 2655 IEnd = Pos->second.end(); 2656 I != IEnd; ++I) { 2657 // A tag declaration does not hide a non-tag declaration. 2658 if ((*I)->hasTagIdentifierNamespace() && 2659 (IDNS & (Decl::IDNS_Member | Decl::IDNS_Ordinary | 2660 Decl::IDNS_ObjCProtocol))) 2661 continue; 2662 2663 // Protocols are in distinct namespaces from everything else. 2664 if ((((*I)->getIdentifierNamespace() & Decl::IDNS_ObjCProtocol) 2665 || (IDNS & Decl::IDNS_ObjCProtocol)) && 2666 (*I)->getIdentifierNamespace() != IDNS) 2667 continue; 2668 2669 // Functions and function templates in the same scope overload 2670 // rather than hide. FIXME: Look for hiding based on function 2671 // signatures! 2672 if ((*I)->isFunctionOrFunctionTemplate() && 2673 ND->isFunctionOrFunctionTemplate() && 2674 SM == ShadowMaps.rbegin()) 2675 continue; 2676 2677 // We've found a declaration that hides this one. 2678 return *I; 2679 } 2680 } 2681 2682 return 0; 2683} 2684 2685static void LookupVisibleDecls(DeclContext *Ctx, LookupResult &Result, 2686 bool QualifiedNameLookup, 2687 bool InBaseClass, 2688 VisibleDeclConsumer &Consumer, 2689 VisibleDeclsRecord &Visited) { 2690 if (!Ctx) 2691 return; 2692 2693 // Make sure we don't visit the same context twice. 2694 if (Visited.visitedContext(Ctx->getPrimaryContext())) 2695 return; 2696 2697 if (CXXRecordDecl *Class = dyn_cast<CXXRecordDecl>(Ctx)) 2698 Result.getSema().ForceDeclarationOfImplicitMembers(Class); 2699 2700 // Enumerate all of the results in this context. 2701 for (DeclContext *CurCtx = Ctx->getPrimaryContext(); CurCtx; 2702 CurCtx = CurCtx->getNextContext()) { 2703 for (DeclContext::decl_iterator D = CurCtx->decls_begin(), 2704 DEnd = CurCtx->decls_end(); 2705 D != DEnd; ++D) { 2706 if (NamedDecl *ND = dyn_cast<NamedDecl>(*D)) { 2707 if (Result.isAcceptableDecl(ND)) { 2708 Consumer.FoundDecl(ND, Visited.checkHidden(ND), InBaseClass); 2709 Visited.add(ND); 2710 } 2711 } else if (ObjCForwardProtocolDecl *ForwardProto 2712 = dyn_cast<ObjCForwardProtocolDecl>(*D)) { 2713 for (ObjCForwardProtocolDecl::protocol_iterator 2714 P = ForwardProto->protocol_begin(), 2715 PEnd = ForwardProto->protocol_end(); 2716 P != PEnd; 2717 ++P) { 2718 if (Result.isAcceptableDecl(*P)) { 2719 Consumer.FoundDecl(*P, Visited.checkHidden(*P), InBaseClass); 2720 Visited.add(*P); 2721 } 2722 } 2723 } else if (ObjCClassDecl *Class = dyn_cast<ObjCClassDecl>(*D)) { 2724 for (ObjCClassDecl::iterator I = Class->begin(), IEnd = Class->end(); 2725 I != IEnd; ++I) { 2726 ObjCInterfaceDecl *IFace = I->getInterface(); 2727 if (Result.isAcceptableDecl(IFace)) { 2728 Consumer.FoundDecl(IFace, Visited.checkHidden(IFace), InBaseClass); 2729 Visited.add(IFace); 2730 } 2731 } 2732 } 2733 2734 // Visit transparent contexts and inline namespaces inside this context. 2735 if (DeclContext *InnerCtx = dyn_cast<DeclContext>(*D)) { 2736 if (InnerCtx->isTransparentContext() || InnerCtx->isInlineNamespace()) 2737 LookupVisibleDecls(InnerCtx, Result, QualifiedNameLookup, InBaseClass, 2738 Consumer, Visited); 2739 } 2740 } 2741 } 2742 2743 // Traverse using directives for qualified name lookup. 2744 if (QualifiedNameLookup) { 2745 ShadowContextRAII Shadow(Visited); 2746 DeclContext::udir_iterator I, E; 2747 for (llvm::tie(I, E) = Ctx->getUsingDirectives(); I != E; ++I) { 2748 LookupVisibleDecls((*I)->getNominatedNamespace(), Result, 2749 QualifiedNameLookup, InBaseClass, Consumer, Visited); 2750 } 2751 } 2752 2753 // Traverse the contexts of inherited C++ classes. 2754 if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(Ctx)) { 2755 if (!Record->hasDefinition()) 2756 return; 2757 2758 for (CXXRecordDecl::base_class_iterator B = Record->bases_begin(), 2759 BEnd = Record->bases_end(); 2760 B != BEnd; ++B) { 2761 QualType BaseType = B->getType(); 2762 2763 // Don't look into dependent bases, because name lookup can't look 2764 // there anyway. 2765 if (BaseType->isDependentType()) 2766 continue; 2767 2768 const RecordType *Record = BaseType->getAs<RecordType>(); 2769 if (!Record) 2770 continue; 2771 2772 // FIXME: It would be nice to be able to determine whether referencing 2773 // a particular member would be ambiguous. For example, given 2774 // 2775 // struct A { int member; }; 2776 // struct B { int member; }; 2777 // struct C : A, B { }; 2778 // 2779 // void f(C *c) { c->### } 2780 // 2781 // accessing 'member' would result in an ambiguity. However, we 2782 // could be smart enough to qualify the member with the base 2783 // class, e.g., 2784 // 2785 // c->B::member 2786 // 2787 // or 2788 // 2789 // c->A::member 2790 2791 // Find results in this base class (and its bases). 2792 ShadowContextRAII Shadow(Visited); 2793 LookupVisibleDecls(Record->getDecl(), Result, QualifiedNameLookup, 2794 true, Consumer, Visited); 2795 } 2796 } 2797 2798 // Traverse the contexts of Objective-C classes. 2799 if (ObjCInterfaceDecl *IFace = dyn_cast<ObjCInterfaceDecl>(Ctx)) { 2800 // Traverse categories. 2801 for (ObjCCategoryDecl *Category = IFace->getCategoryList(); 2802 Category; Category = Category->getNextClassCategory()) { 2803 ShadowContextRAII Shadow(Visited); 2804 LookupVisibleDecls(Category, Result, QualifiedNameLookup, false, 2805 Consumer, Visited); 2806 } 2807 2808 // Traverse protocols. 2809 for (ObjCInterfaceDecl::all_protocol_iterator 2810 I = IFace->all_referenced_protocol_begin(), 2811 E = IFace->all_referenced_protocol_end(); I != E; ++I) { 2812 ShadowContextRAII Shadow(Visited); 2813 LookupVisibleDecls(*I, Result, QualifiedNameLookup, false, Consumer, 2814 Visited); 2815 } 2816 2817 // Traverse the superclass. 2818 if (IFace->getSuperClass()) { 2819 ShadowContextRAII Shadow(Visited); 2820 LookupVisibleDecls(IFace->getSuperClass(), Result, QualifiedNameLookup, 2821 true, Consumer, Visited); 2822 } 2823 2824 // If there is an implementation, traverse it. We do this to find 2825 // synthesized ivars. 2826 if (IFace->getImplementation()) { 2827 ShadowContextRAII Shadow(Visited); 2828 LookupVisibleDecls(IFace->getImplementation(), Result, 2829 QualifiedNameLookup, true, Consumer, Visited); 2830 } 2831 } else if (ObjCProtocolDecl *Protocol = dyn_cast<ObjCProtocolDecl>(Ctx)) { 2832 for (ObjCProtocolDecl::protocol_iterator I = Protocol->protocol_begin(), 2833 E = Protocol->protocol_end(); I != E; ++I) { 2834 ShadowContextRAII Shadow(Visited); 2835 LookupVisibleDecls(*I, Result, QualifiedNameLookup, false, Consumer, 2836 Visited); 2837 } 2838 } else if (ObjCCategoryDecl *Category = dyn_cast<ObjCCategoryDecl>(Ctx)) { 2839 for (ObjCCategoryDecl::protocol_iterator I = Category->protocol_begin(), 2840 E = Category->protocol_end(); I != E; ++I) { 2841 ShadowContextRAII Shadow(Visited); 2842 LookupVisibleDecls(*I, Result, QualifiedNameLookup, false, Consumer, 2843 Visited); 2844 } 2845 2846 // If there is an implementation, traverse it. 2847 if (Category->getImplementation()) { 2848 ShadowContextRAII Shadow(Visited); 2849 LookupVisibleDecls(Category->getImplementation(), Result, 2850 QualifiedNameLookup, true, Consumer, Visited); 2851 } 2852 } 2853} 2854 2855static void LookupVisibleDecls(Scope *S, LookupResult &Result, 2856 UnqualUsingDirectiveSet &UDirs, 2857 VisibleDeclConsumer &Consumer, 2858 VisibleDeclsRecord &Visited) { 2859 if (!S) 2860 return; 2861 2862 if (!S->getEntity() || 2863 (!S->getParent() && 2864 !Visited.alreadyVisitedContext((DeclContext *)S->getEntity())) || 2865 ((DeclContext *)S->getEntity())->isFunctionOrMethod()) { 2866 // Walk through the declarations in this Scope. 2867 for (Scope::decl_iterator D = S->decl_begin(), DEnd = S->decl_end(); 2868 D != DEnd; ++D) { 2869 if (NamedDecl *ND = dyn_cast<NamedDecl>(*D)) 2870 if (Result.isAcceptableDecl(ND)) { 2871 Consumer.FoundDecl(ND, Visited.checkHidden(ND), false); 2872 Visited.add(ND); 2873 } 2874 } 2875 } 2876 2877 // FIXME: C++ [temp.local]p8 2878 DeclContext *Entity = 0; 2879 if (S->getEntity()) { 2880 // Look into this scope's declaration context, along with any of its 2881 // parent lookup contexts (e.g., enclosing classes), up to the point 2882 // where we hit the context stored in the next outer scope. 2883 Entity = (DeclContext *)S->getEntity(); 2884 DeclContext *OuterCtx = findOuterContext(S).first; // FIXME 2885 2886 for (DeclContext *Ctx = Entity; Ctx && !Ctx->Equals(OuterCtx); 2887 Ctx = Ctx->getLookupParent()) { 2888 if (ObjCMethodDecl *Method = dyn_cast<ObjCMethodDecl>(Ctx)) { 2889 if (Method->isInstanceMethod()) { 2890 // For instance methods, look for ivars in the method's interface. 2891 LookupResult IvarResult(Result.getSema(), Result.getLookupName(), 2892 Result.getNameLoc(), Sema::LookupMemberName); 2893 if (ObjCInterfaceDecl *IFace = Method->getClassInterface()) { 2894 LookupVisibleDecls(IFace, IvarResult, /*QualifiedNameLookup=*/false, 2895 /*InBaseClass=*/false, Consumer, Visited); 2896 2897 // Look for properties from which we can synthesize ivars, if 2898 // permitted. 2899 if (Result.getSema().getLangOptions().ObjCNonFragileABI2 && 2900 IFace->getImplementation() && 2901 Result.getLookupKind() == Sema::LookupOrdinaryName) { 2902 for (ObjCInterfaceDecl::prop_iterator 2903 P = IFace->prop_begin(), 2904 PEnd = IFace->prop_end(); 2905 P != PEnd; ++P) { 2906 if (Result.getSema().canSynthesizeProvisionalIvar(*P) && 2907 !IFace->lookupInstanceVariable((*P)->getIdentifier())) { 2908 Consumer.FoundDecl(*P, Visited.checkHidden(*P), false); 2909 Visited.add(*P); 2910 } 2911 } 2912 } 2913 } 2914 } 2915 2916 // We've already performed all of the name lookup that we need 2917 // to for Objective-C methods; the next context will be the 2918 // outer scope. 2919 break; 2920 } 2921 2922 if (Ctx->isFunctionOrMethod()) 2923 continue; 2924 2925 LookupVisibleDecls(Ctx, Result, /*QualifiedNameLookup=*/false, 2926 /*InBaseClass=*/false, Consumer, Visited); 2927 } 2928 } else if (!S->getParent()) { 2929 // Look into the translation unit scope. We walk through the translation 2930 // unit's declaration context, because the Scope itself won't have all of 2931 // the declarations if we loaded a precompiled header. 2932 // FIXME: We would like the translation unit's Scope object to point to the 2933 // translation unit, so we don't need this special "if" branch. However, 2934 // doing so would force the normal C++ name-lookup code to look into the 2935 // translation unit decl when the IdentifierInfo chains would suffice. 2936 // Once we fix that problem (which is part of a more general "don't look 2937 // in DeclContexts unless we have to" optimization), we can eliminate this. 2938 Entity = Result.getSema().Context.getTranslationUnitDecl(); 2939 LookupVisibleDecls(Entity, Result, /*QualifiedNameLookup=*/false, 2940 /*InBaseClass=*/false, Consumer, Visited); 2941 } 2942 2943 if (Entity) { 2944 // Lookup visible declarations in any namespaces found by using 2945 // directives. 2946 UnqualUsingDirectiveSet::const_iterator UI, UEnd; 2947 llvm::tie(UI, UEnd) = UDirs.getNamespacesFor(Entity); 2948 for (; UI != UEnd; ++UI) 2949 LookupVisibleDecls(const_cast<DeclContext *>(UI->getNominatedNamespace()), 2950 Result, /*QualifiedNameLookup=*/false, 2951 /*InBaseClass=*/false, Consumer, Visited); 2952 } 2953 2954 // Lookup names in the parent scope. 2955 ShadowContextRAII Shadow(Visited); 2956 LookupVisibleDecls(S->getParent(), Result, UDirs, Consumer, Visited); 2957} 2958 2959void Sema::LookupVisibleDecls(Scope *S, LookupNameKind Kind, 2960 VisibleDeclConsumer &Consumer, 2961 bool IncludeGlobalScope) { 2962 // Determine the set of using directives available during 2963 // unqualified name lookup. 2964 Scope *Initial = S; 2965 UnqualUsingDirectiveSet UDirs; 2966 if (getLangOptions().CPlusPlus) { 2967 // Find the first namespace or translation-unit scope. 2968 while (S && !isNamespaceOrTranslationUnitScope(S)) 2969 S = S->getParent(); 2970 2971 UDirs.visitScopeChain(Initial, S); 2972 } 2973 UDirs.done(); 2974 2975 // Look for visible declarations. 2976 LookupResult Result(*this, DeclarationName(), SourceLocation(), Kind); 2977 VisibleDeclsRecord Visited; 2978 if (!IncludeGlobalScope) 2979 Visited.visitedContext(Context.getTranslationUnitDecl()); 2980 ShadowContextRAII Shadow(Visited); 2981 ::LookupVisibleDecls(Initial, Result, UDirs, Consumer, Visited); 2982} 2983 2984void Sema::LookupVisibleDecls(DeclContext *Ctx, LookupNameKind Kind, 2985 VisibleDeclConsumer &Consumer, 2986 bool IncludeGlobalScope) { 2987 LookupResult Result(*this, DeclarationName(), SourceLocation(), Kind); 2988 VisibleDeclsRecord Visited; 2989 if (!IncludeGlobalScope) 2990 Visited.visitedContext(Context.getTranslationUnitDecl()); 2991 ShadowContextRAII Shadow(Visited); 2992 ::LookupVisibleDecls(Ctx, Result, /*QualifiedNameLookup=*/true, 2993 /*InBaseClass=*/false, Consumer, Visited); 2994} 2995 2996/// LookupOrCreateLabel - Do a name lookup of a label with the specified name. 2997/// If GnuLabelLoc is a valid source location, then this is a definition 2998/// of an __label__ label name, otherwise it is a normal label definition 2999/// or use. 3000LabelDecl *Sema::LookupOrCreateLabel(IdentifierInfo *II, SourceLocation Loc, 3001 SourceLocation GnuLabelLoc) { 3002 // Do a lookup to see if we have a label with this name already. 3003 NamedDecl *Res = 0; 3004 3005 if (GnuLabelLoc.isValid()) { 3006 // Local label definitions always shadow existing labels. 3007 Res = LabelDecl::Create(Context, CurContext, Loc, II, GnuLabelLoc); 3008 Scope *S = CurScope; 3009 PushOnScopeChains(Res, S, true); 3010 return cast<LabelDecl>(Res); 3011 } 3012 3013 // Not a GNU local label. 3014 Res = LookupSingleName(CurScope, II, Loc, LookupLabel, NotForRedeclaration); 3015 // If we found a label, check to see if it is in the same context as us. 3016 // When in a Block, we don't want to reuse a label in an enclosing function. 3017 if (Res && Res->getDeclContext() != CurContext) 3018 Res = 0; 3019 if (Res == 0) { 3020 // If not forward referenced or defined already, create the backing decl. 3021 Res = LabelDecl::Create(Context, CurContext, Loc, II); 3022 Scope *S = CurScope->getFnParent(); 3023 assert(S && "Not in a function?"); 3024 PushOnScopeChains(Res, S, true); 3025 } 3026 return cast<LabelDecl>(Res); 3027} 3028 3029//===----------------------------------------------------------------------===// 3030// Typo correction 3031//===----------------------------------------------------------------------===// 3032 3033namespace { 3034class TypoCorrectionConsumer : public VisibleDeclConsumer { 3035 /// \brief The name written that is a typo in the source. 3036 llvm::StringRef Typo; 3037 3038 /// \brief The results found that have the smallest edit distance 3039 /// found (so far) with the typo name. 3040 /// 3041 /// The boolean value indicates whether there is a keyword with this name. 3042 llvm::StringMap<bool, llvm::BumpPtrAllocator> BestResults; 3043 3044 /// \brief The best edit distance found so far. 3045 unsigned BestEditDistance; 3046 3047public: 3048 explicit TypoCorrectionConsumer(IdentifierInfo *Typo) 3049 : Typo(Typo->getName()), 3050 BestEditDistance((std::numeric_limits<unsigned>::max)()) { } 3051 3052 virtual void FoundDecl(NamedDecl *ND, NamedDecl *Hiding, bool InBaseClass); 3053 void FoundName(llvm::StringRef Name); 3054 void addKeywordResult(ASTContext &Context, llvm::StringRef Keyword); 3055 3056 typedef llvm::StringMap<bool, llvm::BumpPtrAllocator>::iterator iterator; 3057 iterator begin() { return BestResults.begin(); } 3058 iterator end() { return BestResults.end(); } 3059 void erase(iterator I) { BestResults.erase(I); } 3060 unsigned size() const { return BestResults.size(); } 3061 bool empty() const { return BestResults.empty(); } 3062 3063 bool &operator[](llvm::StringRef Name) { 3064 return BestResults[Name]; 3065 } 3066 3067 unsigned getBestEditDistance() const { return BestEditDistance; } 3068}; 3069 3070} 3071 3072void TypoCorrectionConsumer::FoundDecl(NamedDecl *ND, NamedDecl *Hiding, 3073 bool InBaseClass) { 3074 // Don't consider hidden names for typo correction. 3075 if (Hiding) 3076 return; 3077 3078 // Only consider entities with identifiers for names, ignoring 3079 // special names (constructors, overloaded operators, selectors, 3080 // etc.). 3081 IdentifierInfo *Name = ND->getIdentifier(); 3082 if (!Name) 3083 return; 3084 3085 FoundName(Name->getName()); 3086} 3087 3088void TypoCorrectionConsumer::FoundName(llvm::StringRef Name) { 3089 // Use a simple length-based heuristic to determine the minimum possible 3090 // edit distance. If the minimum isn't good enough, bail out early. 3091 unsigned MinED = abs((int)Name.size() - (int)Typo.size()); 3092 if (MinED > BestEditDistance || (MinED && Typo.size() / MinED < 3)) 3093 return; 3094 3095 // Compute an upper bound on the allowable edit distance, so that the 3096 // edit-distance algorithm can short-circuit. 3097 unsigned UpperBound = 3098 std::min(unsigned((Typo.size() + 2) / 3), BestEditDistance); 3099 3100 // Compute the edit distance between the typo and the name of this 3101 // entity. If this edit distance is not worse than the best edit 3102 // distance we've seen so far, add it to the list of results. 3103 unsigned ED = Typo.edit_distance(Name, true, UpperBound); 3104 if (ED == 0) 3105 return; 3106 3107 if (ED < BestEditDistance) { 3108 // This result is better than any we've seen before; clear out 3109 // the previous results. 3110 BestResults.clear(); 3111 BestEditDistance = ED; 3112 } else if (ED > BestEditDistance) { 3113 // This result is worse than the best results we've seen so far; 3114 // ignore it. 3115 return; 3116 } 3117 3118 // Add this name to the list of results. By not assigning a value, we 3119 // keep the current value if we've seen this name before (either as a 3120 // keyword or as a declaration), or get the default value (not a keyword) 3121 // if we haven't seen it before. 3122 (void)BestResults[Name]; 3123} 3124 3125void TypoCorrectionConsumer::addKeywordResult(ASTContext &Context, 3126 llvm::StringRef Keyword) { 3127 // Compute the edit distance between the typo and this keyword. 3128 // If this edit distance is not worse than the best edit 3129 // distance we've seen so far, add it to the list of results. 3130 unsigned ED = Typo.edit_distance(Keyword); 3131 if (ED < BestEditDistance) { 3132 BestResults.clear(); 3133 BestEditDistance = ED; 3134 } else if (ED > BestEditDistance) { 3135 // This result is worse than the best results we've seen so far; 3136 // ignore it. 3137 return; 3138 } 3139 3140 BestResults[Keyword] = true; 3141} 3142 3143/// \brief Perform name lookup for a possible result for typo correction. 3144static void LookupPotentialTypoResult(Sema &SemaRef, 3145 LookupResult &Res, 3146 IdentifierInfo *Name, 3147 Scope *S, CXXScopeSpec *SS, 3148 DeclContext *MemberContext, 3149 bool EnteringContext, 3150 Sema::CorrectTypoContext CTC) { 3151 Res.suppressDiagnostics(); 3152 Res.clear(); 3153 Res.setLookupName(Name); 3154 if (MemberContext) { 3155 if (ObjCInterfaceDecl *Class = dyn_cast<ObjCInterfaceDecl>(MemberContext)) { 3156 if (CTC == Sema::CTC_ObjCIvarLookup) { 3157 if (ObjCIvarDecl *Ivar = Class->lookupInstanceVariable(Name)) { 3158 Res.addDecl(Ivar); 3159 Res.resolveKind(); 3160 return; 3161 } 3162 } 3163 3164 if (ObjCPropertyDecl *Prop = Class->FindPropertyDeclaration(Name)) { 3165 Res.addDecl(Prop); 3166 Res.resolveKind(); 3167 return; 3168 } 3169 } 3170 3171 SemaRef.LookupQualifiedName(Res, MemberContext); 3172 return; 3173 } 3174 3175 SemaRef.LookupParsedName(Res, S, SS, /*AllowBuiltinCreation=*/false, 3176 EnteringContext); 3177 3178 // Fake ivar lookup; this should really be part of 3179 // LookupParsedName. 3180 if (ObjCMethodDecl *Method = SemaRef.getCurMethodDecl()) { 3181 if (Method->isInstanceMethod() && Method->getClassInterface() && 3182 (Res.empty() || 3183 (Res.isSingleResult() && 3184 Res.getFoundDecl()->isDefinedOutsideFunctionOrMethod()))) { 3185 if (ObjCIvarDecl *IV 3186 = Method->getClassInterface()->lookupInstanceVariable(Name)) { 3187 Res.addDecl(IV); 3188 Res.resolveKind(); 3189 } 3190 } 3191 } 3192} 3193 3194/// \brief Try to "correct" a typo in the source code by finding 3195/// visible declarations whose names are similar to the name that was 3196/// present in the source code. 3197/// 3198/// \param Res the \c LookupResult structure that contains the name 3199/// that was present in the source code along with the name-lookup 3200/// criteria used to search for the name. On success, this structure 3201/// will contain the results of name lookup. 3202/// 3203/// \param S the scope in which name lookup occurs. 3204/// 3205/// \param SS the nested-name-specifier that precedes the name we're 3206/// looking for, if present. 3207/// 3208/// \param MemberContext if non-NULL, the context in which to look for 3209/// a member access expression. 3210/// 3211/// \param EnteringContext whether we're entering the context described by 3212/// the nested-name-specifier SS. 3213/// 3214/// \param CTC The context in which typo correction occurs, which impacts the 3215/// set of keywords permitted. 3216/// 3217/// \param OPT when non-NULL, the search for visible declarations will 3218/// also walk the protocols in the qualified interfaces of \p OPT. 3219/// 3220/// \returns the corrected name if the typo was corrected, otherwise returns an 3221/// empty \c DeclarationName. When a typo was corrected, the result structure 3222/// may contain the results of name lookup for the correct name or it may be 3223/// empty. 3224DeclarationName Sema::CorrectTypo(LookupResult &Res, Scope *S, CXXScopeSpec *SS, 3225 DeclContext *MemberContext, 3226 bool EnteringContext, 3227 CorrectTypoContext CTC, 3228 const ObjCObjectPointerType *OPT) { 3229 if (Diags.hasFatalErrorOccurred() || !getLangOptions().SpellChecking) 3230 return DeclarationName(); 3231 3232 // We only attempt to correct typos for identifiers. 3233 IdentifierInfo *Typo = Res.getLookupName().getAsIdentifierInfo(); 3234 if (!Typo) 3235 return DeclarationName(); 3236 3237 // If the scope specifier itself was invalid, don't try to correct 3238 // typos. 3239 if (SS && SS->isInvalid()) 3240 return DeclarationName(); 3241 3242 // Never try to correct typos during template deduction or 3243 // instantiation. 3244 if (!ActiveTemplateInstantiations.empty()) 3245 return DeclarationName(); 3246 3247 TypoCorrectionConsumer Consumer(Typo); 3248 3249 // Perform name lookup to find visible, similarly-named entities. 3250 bool IsUnqualifiedLookup = false; 3251 if (MemberContext) { 3252 LookupVisibleDecls(MemberContext, Res.getLookupKind(), Consumer); 3253 3254 // Look in qualified interfaces. 3255 if (OPT) { 3256 for (ObjCObjectPointerType::qual_iterator 3257 I = OPT->qual_begin(), E = OPT->qual_end(); 3258 I != E; ++I) 3259 LookupVisibleDecls(*I, Res.getLookupKind(), Consumer); 3260 } 3261 } else if (SS && SS->isSet()) { 3262 DeclContext *DC = computeDeclContext(*SS, EnteringContext); 3263 if (!DC) 3264 return DeclarationName(); 3265 3266 // Provide a stop gap for files that are just seriously broken. Trying 3267 // to correct all typos can turn into a HUGE performance penalty, causing 3268 // some files to take minutes to get rejected by the parser. 3269 if (TyposCorrected + UnqualifiedTyposCorrected.size() >= 20) 3270 return DeclarationName(); 3271 ++TyposCorrected; 3272 3273 LookupVisibleDecls(DC, Res.getLookupKind(), Consumer); 3274 } else { 3275 IsUnqualifiedLookup = true; 3276 UnqualifiedTyposCorrectedMap::iterator Cached 3277 = UnqualifiedTyposCorrected.find(Typo); 3278 if (Cached == UnqualifiedTyposCorrected.end()) { 3279 // Provide a stop gap for files that are just seriously broken. Trying 3280 // to correct all typos can turn into a HUGE performance penalty, causing 3281 // some files to take minutes to get rejected by the parser. 3282 if (TyposCorrected + UnqualifiedTyposCorrected.size() >= 20) 3283 return DeclarationName(); 3284 3285 // For unqualified lookup, look through all of the names that we have 3286 // seen in this translation unit. 3287 for (IdentifierTable::iterator I = Context.Idents.begin(), 3288 IEnd = Context.Idents.end(); 3289 I != IEnd; ++I) 3290 Consumer.FoundName(I->getKey()); 3291 3292 // Walk through identifiers in external identifier sources. 3293 if (IdentifierInfoLookup *External 3294 = Context.Idents.getExternalIdentifierLookup()) { 3295 llvm::OwningPtr<IdentifierIterator> Iter(External->getIdentifiers()); 3296 do { 3297 llvm::StringRef Name = Iter->Next(); 3298 if (Name.empty()) 3299 break; 3300 3301 Consumer.FoundName(Name); 3302 } while (true); 3303 } 3304 } else { 3305 // Use the cached value, unless it's a keyword. In the keyword case, we'll 3306 // end up adding the keyword below. 3307 if (Cached->second.first.empty()) 3308 return DeclarationName(); 3309 3310 if (!Cached->second.second) 3311 Consumer.FoundName(Cached->second.first); 3312 } 3313 } 3314 3315 // Add context-dependent keywords. 3316 bool WantTypeSpecifiers = false; 3317 bool WantExpressionKeywords = false; 3318 bool WantCXXNamedCasts = false; 3319 bool WantRemainingKeywords = false; 3320 switch (CTC) { 3321 case CTC_Unknown: 3322 WantTypeSpecifiers = true; 3323 WantExpressionKeywords = true; 3324 WantCXXNamedCasts = true; 3325 WantRemainingKeywords = true; 3326 3327 if (ObjCMethodDecl *Method = getCurMethodDecl()) 3328 if (Method->getClassInterface() && 3329 Method->getClassInterface()->getSuperClass()) 3330 Consumer.addKeywordResult(Context, "super"); 3331 3332 break; 3333 3334 case CTC_NoKeywords: 3335 break; 3336 3337 case CTC_Type: 3338 WantTypeSpecifiers = true; 3339 break; 3340 3341 case CTC_ObjCMessageReceiver: 3342 Consumer.addKeywordResult(Context, "super"); 3343 // Fall through to handle message receivers like expressions. 3344 3345 case CTC_Expression: 3346 if (getLangOptions().CPlusPlus) 3347 WantTypeSpecifiers = true; 3348 WantExpressionKeywords = true; 3349 // Fall through to get C++ named casts. 3350 3351 case CTC_CXXCasts: 3352 WantCXXNamedCasts = true; 3353 break; 3354 3355 case CTC_ObjCPropertyLookup: 3356 // FIXME: Add "isa"? 3357 break; 3358 3359 case CTC_MemberLookup: 3360 if (getLangOptions().CPlusPlus) 3361 Consumer.addKeywordResult(Context, "template"); 3362 break; 3363 3364 case CTC_ObjCIvarLookup: 3365 break; 3366 } 3367 3368 if (WantTypeSpecifiers) { 3369 // Add type-specifier keywords to the set of results. 3370 const char *CTypeSpecs[] = { 3371 "char", "const", "double", "enum", "float", "int", "long", "short", 3372 "signed", "struct", "union", "unsigned", "void", "volatile", "_Bool", 3373 "_Complex", "_Imaginary", 3374 // storage-specifiers as well 3375 "extern", "inline", "static", "typedef" 3376 }; 3377 3378 const unsigned NumCTypeSpecs = sizeof(CTypeSpecs) / sizeof(CTypeSpecs[0]); 3379 for (unsigned I = 0; I != NumCTypeSpecs; ++I) 3380 Consumer.addKeywordResult(Context, CTypeSpecs[I]); 3381 3382 if (getLangOptions().C99) 3383 Consumer.addKeywordResult(Context, "restrict"); 3384 if (getLangOptions().Bool || getLangOptions().CPlusPlus) 3385 Consumer.addKeywordResult(Context, "bool"); 3386 3387 if (getLangOptions().CPlusPlus) { 3388 Consumer.addKeywordResult(Context, "class"); 3389 Consumer.addKeywordResult(Context, "typename"); 3390 Consumer.addKeywordResult(Context, "wchar_t"); 3391 3392 if (getLangOptions().CPlusPlus0x) { 3393 Consumer.addKeywordResult(Context, "char16_t"); 3394 Consumer.addKeywordResult(Context, "char32_t"); 3395 Consumer.addKeywordResult(Context, "constexpr"); 3396 Consumer.addKeywordResult(Context, "decltype"); 3397 Consumer.addKeywordResult(Context, "thread_local"); 3398 } 3399 } 3400 3401 if (getLangOptions().GNUMode) 3402 Consumer.addKeywordResult(Context, "typeof"); 3403 } 3404 3405 if (WantCXXNamedCasts && getLangOptions().CPlusPlus) { 3406 Consumer.addKeywordResult(Context, "const_cast"); 3407 Consumer.addKeywordResult(Context, "dynamic_cast"); 3408 Consumer.addKeywordResult(Context, "reinterpret_cast"); 3409 Consumer.addKeywordResult(Context, "static_cast"); 3410 } 3411 3412 if (WantExpressionKeywords) { 3413 Consumer.addKeywordResult(Context, "sizeof"); 3414 if (getLangOptions().Bool || getLangOptions().CPlusPlus) { 3415 Consumer.addKeywordResult(Context, "false"); 3416 Consumer.addKeywordResult(Context, "true"); 3417 } 3418 3419 if (getLangOptions().CPlusPlus) { 3420 const char *CXXExprs[] = { 3421 "delete", "new", "operator", "throw", "typeid" 3422 }; 3423 const unsigned NumCXXExprs = sizeof(CXXExprs) / sizeof(CXXExprs[0]); 3424 for (unsigned I = 0; I != NumCXXExprs; ++I) 3425 Consumer.addKeywordResult(Context, CXXExprs[I]); 3426 3427 if (isa<CXXMethodDecl>(CurContext) && 3428 cast<CXXMethodDecl>(CurContext)->isInstance()) 3429 Consumer.addKeywordResult(Context, "this"); 3430 3431 if (getLangOptions().CPlusPlus0x) { 3432 Consumer.addKeywordResult(Context, "alignof"); 3433 Consumer.addKeywordResult(Context, "nullptr"); 3434 } 3435 } 3436 } 3437 3438 if (WantRemainingKeywords) { 3439 if (getCurFunctionOrMethodDecl() || getCurBlock()) { 3440 // Statements. 3441 const char *CStmts[] = { 3442 "do", "else", "for", "goto", "if", "return", "switch", "while" }; 3443 const unsigned NumCStmts = sizeof(CStmts) / sizeof(CStmts[0]); 3444 for (unsigned I = 0; I != NumCStmts; ++I) 3445 Consumer.addKeywordResult(Context, CStmts[I]); 3446 3447 if (getLangOptions().CPlusPlus) { 3448 Consumer.addKeywordResult(Context, "catch"); 3449 Consumer.addKeywordResult(Context, "try"); 3450 } 3451 3452 if (S && S->getBreakParent()) 3453 Consumer.addKeywordResult(Context, "break"); 3454 3455 if (S && S->getContinueParent()) 3456 Consumer.addKeywordResult(Context, "continue"); 3457 3458 if (!getCurFunction()->SwitchStack.empty()) { 3459 Consumer.addKeywordResult(Context, "case"); 3460 Consumer.addKeywordResult(Context, "default"); 3461 } 3462 } else { 3463 if (getLangOptions().CPlusPlus) { 3464 Consumer.addKeywordResult(Context, "namespace"); 3465 Consumer.addKeywordResult(Context, "template"); 3466 } 3467 3468 if (S && S->isClassScope()) { 3469 Consumer.addKeywordResult(Context, "explicit"); 3470 Consumer.addKeywordResult(Context, "friend"); 3471 Consumer.addKeywordResult(Context, "mutable"); 3472 Consumer.addKeywordResult(Context, "private"); 3473 Consumer.addKeywordResult(Context, "protected"); 3474 Consumer.addKeywordResult(Context, "public"); 3475 Consumer.addKeywordResult(Context, "virtual"); 3476 } 3477 } 3478 3479 if (getLangOptions().CPlusPlus) { 3480 Consumer.addKeywordResult(Context, "using"); 3481 3482 if (getLangOptions().CPlusPlus0x) 3483 Consumer.addKeywordResult(Context, "static_assert"); 3484 } 3485 } 3486 3487 // If we haven't found anything, we're done. 3488 if (Consumer.empty()) { 3489 // If this was an unqualified lookup, note that no correction was found. 3490 if (IsUnqualifiedLookup) 3491 (void)UnqualifiedTyposCorrected[Typo]; 3492 3493 return DeclarationName(); 3494 } 3495 3496 // Make sure that the user typed at least 3 characters for each correction 3497 // made. Otherwise, we don't even both looking at the results. 3498 3499 // We also suppress exact matches; those should be handled by a 3500 // different mechanism (e.g., one that introduces qualification in 3501 // C++). 3502 unsigned ED = Consumer.getBestEditDistance(); 3503 if (ED > 0 && Typo->getName().size() / ED < 3) { 3504 // If this was an unqualified lookup, note that no correction was found. 3505 if (IsUnqualifiedLookup) 3506 (void)UnqualifiedTyposCorrected[Typo]; 3507 3508 return DeclarationName(); 3509 } 3510 3511 // Weed out any names that could not be found by name lookup. 3512 bool LastLookupWasAccepted = false; 3513 for (TypoCorrectionConsumer::iterator I = Consumer.begin(), 3514 IEnd = Consumer.end(); 3515 I != IEnd; /* Increment in loop. */) { 3516 // Keywords are always found. 3517 if (I->second) { 3518 ++I; 3519 continue; 3520 } 3521 3522 // Perform name lookup on this name. 3523 IdentifierInfo *Name = &Context.Idents.get(I->getKey()); 3524 LookupPotentialTypoResult(*this, Res, Name, S, SS, MemberContext, 3525 EnteringContext, CTC); 3526 3527 switch (Res.getResultKind()) { 3528 case LookupResult::NotFound: 3529 case LookupResult::NotFoundInCurrentInstantiation: 3530 case LookupResult::Ambiguous: 3531 // We didn't find this name in our scope, or didn't like what we found; 3532 // ignore it. 3533 Res.suppressDiagnostics(); 3534 { 3535 TypoCorrectionConsumer::iterator Next = I; 3536 ++Next; 3537 Consumer.erase(I); 3538 I = Next; 3539 } 3540 LastLookupWasAccepted = false; 3541 break; 3542 3543 case LookupResult::Found: 3544 case LookupResult::FoundOverloaded: 3545 case LookupResult::FoundUnresolvedValue: 3546 ++I; 3547 LastLookupWasAccepted = true; 3548 break; 3549 } 3550 3551 if (Res.isAmbiguous()) { 3552 // We don't deal with ambiguities. 3553 Res.suppressDiagnostics(); 3554 Res.clear(); 3555 return DeclarationName(); 3556 } 3557 } 3558 3559 // If only a single name remains, return that result. 3560 if (Consumer.size() == 1) { 3561 IdentifierInfo *Name = &Context.Idents.get(Consumer.begin()->getKey()); 3562 if (Consumer.begin()->second) { 3563 Res.suppressDiagnostics(); 3564 Res.clear(); 3565 3566 // Don't correct to a keyword that's the same as the typo; the keyword 3567 // wasn't actually in scope. 3568 if (ED == 0) { 3569 Res.setLookupName(Typo); 3570 return DeclarationName(); 3571 } 3572 3573 } else if (!LastLookupWasAccepted) { 3574 // Perform name lookup on this name. 3575 LookupPotentialTypoResult(*this, Res, Name, S, SS, MemberContext, 3576 EnteringContext, CTC); 3577 } 3578 3579 // Record the correction for unqualified lookup. 3580 if (IsUnqualifiedLookup) 3581 UnqualifiedTyposCorrected[Typo] 3582 = std::make_pair(Name->getName(), Consumer.begin()->second); 3583 3584 return &Context.Idents.get(Consumer.begin()->getKey()); 3585 } 3586 else if (Consumer.size() > 1 && CTC == CTC_ObjCMessageReceiver 3587 && Consumer["super"]) { 3588 // Prefix 'super' when we're completing in a message-receiver 3589 // context. 3590 Res.suppressDiagnostics(); 3591 Res.clear(); 3592 3593 // Don't correct to a keyword that's the same as the typo; the keyword 3594 // wasn't actually in scope. 3595 if (ED == 0) { 3596 Res.setLookupName(Typo); 3597 return DeclarationName(); 3598 } 3599 3600 // Record the correction for unqualified lookup. 3601 if (IsUnqualifiedLookup) 3602 UnqualifiedTyposCorrected[Typo] 3603 = std::make_pair("super", Consumer.begin()->second); 3604 3605 return &Context.Idents.get("super"); 3606 } 3607 3608 Res.suppressDiagnostics(); 3609 Res.setLookupName(Typo); 3610 Res.clear(); 3611 // Record the correction for unqualified lookup. 3612 if (IsUnqualifiedLookup) 3613 (void)UnqualifiedTyposCorrected[Typo]; 3614 3615 return DeclarationName(); 3616} 3617