lib/Sema/SemaLookup.cpp

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