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