contrib/llvm/tools/clang/lib/AST/DeclBase.cpp

   1 //===--- DeclBase.cpp - Declaration AST Node Implementation ---------------===//
   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 the Decl and DeclContext classes.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/AST/DeclBase.h"
  15 #include "clang/AST/ASTContext.h"
  16 #include "clang/AST/ASTMutationListener.h"
  17 #include "clang/AST/Attr.h"
  18 #include "clang/AST/Decl.h"
  19 #include "clang/AST/DeclCXX.h"
  20 #include "clang/AST/DeclContextInternals.h"
  21 #include "clang/AST/DeclFriend.h"
  22 #include "clang/AST/DeclObjC.h"
  23 #include "clang/AST/DeclOpenMP.h"
  24 #include "clang/AST/DeclTemplate.h"
  25 #include "clang/AST/DependentDiagnostic.h"
  26 #include "clang/AST/ExternalASTSource.h"
  27 #include "clang/AST/Stmt.h"
  28 #include "clang/AST/StmtCXX.h"
  29 #include "clang/AST/Type.h"
  30 #include "clang/Basic/TargetInfo.h"
  31 #include "llvm/Support/raw_ostream.h"
  32 #include <algorithm>
  33 using namespace clang;
  34
  35 //===----------------------------------------------------------------------===//
  36 //  Statistics
  37 //===----------------------------------------------------------------------===//
  38
  39 #define DECL(DERIVED, BASE) static int n##DERIVED##s = 0;
  40 #define ABSTRACT_DECL(DECL)
  41 #include "clang/AST/DeclNodes.inc"
  42
  43 void Decl::updateOutOfDate(IdentifierInfo &II) const {
  44   getASTContext().getExternalSource()->updateOutOfDateIdentifier(II);
  45 }
  46
  47 #define DECL(DERIVED, BASE)                                                    \
  48   static_assert(alignof(Decl) >= alignof(DERIVED##Decl),                       \
  49                 "Alignment sufficient after objects prepended to " #DERIVED);
  50 #define ABSTRACT_DECL(DECL)
  51 #include "clang/AST/DeclNodes.inc"
  52
  53 void *Decl::operator new(std::size_t Size, const ASTContext &Context,
  54                          unsigned ID, std::size_t Extra) {
  55   // Allocate an extra 8 bytes worth of storage, which ensures that the
  56   // resulting pointer will still be 8-byte aligned.
  57   static_assert(sizeof(unsigned) * 2 >= alignof(Decl),
  58                 "Decl won't be misaligned");
  59   void *Start = Context.Allocate(Size + Extra + 8);
  60   void *Result = (char*)Start + 8;
  61
  62   unsigned *PrefixPtr = (unsigned *)Result - 2;
  63
  64   // Zero out the first 4 bytes; this is used to store the owning module ID.
  65   PrefixPtr[0] = 0;
  66
  67   // Store the global declaration ID in the second 4 bytes.
  68   PrefixPtr[1] = ID;
  69
  70   return Result;
  71 }
  72
  73 void *Decl::operator new(std::size_t Size, const ASTContext &Ctx,
  74                          DeclContext *Parent, std::size_t Extra) {
  75   assert(!Parent || &Parent->getParentASTContext() == &Ctx);
  76   // With local visibility enabled, we track the owning module even for local
  77   // declarations.
  78   if (Ctx.getLangOpts().ModulesLocalVisibility) {
  79     // Ensure required alignment of the resulting object by adding extra
  80     // padding at the start if required.
  81     size_t ExtraAlign =
  82         llvm::OffsetToAlignment(sizeof(Module *), alignof(Decl));
  83     char *Buffer = reinterpret_cast<char *>(
  84         ::operator new(ExtraAlign + sizeof(Module *) + Size + Extra, Ctx));
  85     Buffer += ExtraAlign;
  86     return new (Buffer) Module*(nullptr) + 1;
  87   }
  88   return ::operator new(Size + Extra, Ctx);
  89 }
  90
  91 Module *Decl::getOwningModuleSlow() const {
  92   assert(isFromASTFile() && "Not from AST file?");
  93   return getASTContext().getExternalSource()->getModule(getOwningModuleID());
  94 }
  95
  96 bool Decl::hasLocalOwningModuleStorage() const {
  97   return getASTContext().getLangOpts().ModulesLocalVisibility;
  98 }
  99
 100 const char *Decl::getDeclKindName() const {
 101   switch (DeclKind) {
 102   default: llvm_unreachable("Declaration not in DeclNodes.inc!");
 103 #define DECL(DERIVED, BASE) case DERIVED: return #DERIVED;
 104 #define ABSTRACT_DECL(DECL)
 105 #include "clang/AST/DeclNodes.inc"
 106   }
 107 }
 108
 109 void Decl::setInvalidDecl(bool Invalid) {
 110   InvalidDecl = Invalid;
 111   assert(!isa<TagDecl>(this) || !cast<TagDecl>(this)->isCompleteDefinition());
 112   if (!Invalid) {
 113     return;
 114   }
 115
 116   if (!isa<ParmVarDecl>(this)) {
 117     // Defensive maneuver for ill-formed code: we're likely not to make it to
 118     // a point where we set the access specifier, so default it to "public"
 119     // to avoid triggering asserts elsewhere in the front end.
 120     setAccess(AS_public);
 121   }
 122
 123   // Marking a DecompositionDecl as invalid implies all the child BindingDecl's
 124   // are invalid too.
 125   if (DecompositionDecl *DD = dyn_cast<DecompositionDecl>(this)) {
 126     for (BindingDecl *Binding : DD->bindings()) {
 127       Binding->setInvalidDecl();
 128     }
 129   }
 130 }
 131
 132 const char *DeclContext::getDeclKindName() const {
 133   switch (DeclKind) {
 134   default: llvm_unreachable("Declaration context not in DeclNodes.inc!");
 135 #define DECL(DERIVED, BASE) case Decl::DERIVED: return #DERIVED;
 136 #define ABSTRACT_DECL(DECL)
 137 #include "clang/AST/DeclNodes.inc"
 138   }
 139 }
 140
 141 bool Decl::StatisticsEnabled = false;
 142 void Decl::EnableStatistics() {
 143   StatisticsEnabled = true;
 144 }
 145
 146 void Decl::PrintStats() {
 147   llvm::errs() << "\n*** Decl Stats:\n";
 148
 149   int totalDecls = 0;
 150 #define DECL(DERIVED, BASE) totalDecls += n##DERIVED##s;
 151 #define ABSTRACT_DECL(DECL)
 152 #include "clang/AST/DeclNodes.inc"
 153   llvm::errs() << "  " << totalDecls << " decls total.\n";
 154
 155   int totalBytes = 0;
 156 #define DECL(DERIVED, BASE)                                             \
 157   if (n##DERIVED##s > 0) {                                              \
 158     totalBytes += (int)(n##DERIVED##s * sizeof(DERIVED##Decl));         \
 159     llvm::errs() << "    " << n##DERIVED##s << " " #DERIVED " decls, "  \
 160                  << sizeof(DERIVED##Decl) << " each ("                  \
 161                  << n##DERIVED##s * sizeof(DERIVED##Decl)               \
 162                  << " bytes)\n";                                        \
 163   }
 164 #define ABSTRACT_DECL(DECL)
 165 #include "clang/AST/DeclNodes.inc"
 166
 167   llvm::errs() << "Total bytes = " << totalBytes << "\n";
 168 }
 169
 170 void Decl::add(Kind k) {
 171   switch (k) {
 172 #define DECL(DERIVED, BASE) case DERIVED: ++n##DERIVED##s; break;
 173 #define ABSTRACT_DECL(DECL)
 174 #include "clang/AST/DeclNodes.inc"
 175   }
 176 }
 177
 178 bool Decl::isTemplateParameterPack() const {
 179   if (const TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(this))
 180     return TTP->isParameterPack();
 181   if (const NonTypeTemplateParmDecl *NTTP
 182                                 = dyn_cast<NonTypeTemplateParmDecl>(this))
 183     return NTTP->isParameterPack();
 184   if (const TemplateTemplateParmDecl *TTP
 185                                     = dyn_cast<TemplateTemplateParmDecl>(this))
 186     return TTP->isParameterPack();
 187   return false;
 188 }
 189
 190 bool Decl::isParameterPack() const {
 191   if (const ParmVarDecl *Parm = dyn_cast<ParmVarDecl>(this))
 192     return Parm->isParameterPack();
 193
 194   return isTemplateParameterPack();
 195 }
 196
 197 FunctionDecl *Decl::getAsFunction() {
 198   if (FunctionDecl *FD = dyn_cast<FunctionDecl>(this))
 199     return FD;
 200   if (const FunctionTemplateDecl *FTD = dyn_cast<FunctionTemplateDecl>(this))
 201     return FTD->getTemplatedDecl();
 202   return nullptr;
 203 }
 204
 205 bool Decl::isTemplateDecl() const {
 206   return isa<TemplateDecl>(this);
 207 }
 208
 209 TemplateDecl *Decl::getDescribedTemplate() const {
 210   if (auto *FD = dyn_cast<FunctionDecl>(this))
 211     return FD->getDescribedFunctionTemplate();
 212   else if (auto *RD = dyn_cast<CXXRecordDecl>(this))
 213     return RD->getDescribedClassTemplate();
 214   else if (auto *VD = dyn_cast<VarDecl>(this))
 215     return VD->getDescribedVarTemplate();
 216
 217   return nullptr;
 218 }
 219
 220 const DeclContext *Decl::getParentFunctionOrMethod() const {
 221   for (const DeclContext *DC = getDeclContext();
 222        DC && !DC->isTranslationUnit() && !DC->isNamespace();
 223        DC = DC->getParent())
 224     if (DC->isFunctionOrMethod())
 225       return DC;
 226
 227   return nullptr;
 228 }
 229
 230
 231 //===----------------------------------------------------------------------===//
 232 // PrettyStackTraceDecl Implementation
 233 //===----------------------------------------------------------------------===//
 234
 235 void PrettyStackTraceDecl::print(raw_ostream &OS) const {
 236   SourceLocation TheLoc = Loc;
 237   if (TheLoc.isInvalid() && TheDecl)
 238     TheLoc = TheDecl->getLocation();
 239
 240   if (TheLoc.isValid()) {
 241     TheLoc.print(OS, SM);
 242     OS << ": ";
 243   }
 244
 245   OS << Message;
 246
 247   if (const NamedDecl *DN = dyn_cast_or_null<NamedDecl>(TheDecl)) {
 248     OS << " '";
 249     DN->printQualifiedName(OS);
 250     OS << '\'';
 251   }
 252   OS << '\n';
 253 }
 254
 255 //===----------------------------------------------------------------------===//
 256 // Decl Implementation
 257 //===----------------------------------------------------------------------===//
 258
 259 // Out-of-line virtual method providing a home for Decl.
 260 Decl::~Decl() { }
 261
 262 void Decl::setDeclContext(DeclContext *DC) {
 263   DeclCtx = DC;
 264 }
 265
 266 void Decl::setLexicalDeclContext(DeclContext *DC) {
 267   if (DC == getLexicalDeclContext())
 268     return;
 269
 270   if (isInSemaDC()) {
 271     setDeclContextsImpl(getDeclContext(), DC, getASTContext());
 272   } else {
 273     getMultipleDC()->LexicalDC = DC;
 274   }
 275   Hidden = cast<Decl>(DC)->Hidden;
 276 }
 277
 278 void Decl::setDeclContextsImpl(DeclContext *SemaDC, DeclContext *LexicalDC,
 279                                ASTContext &Ctx) {
 280   if (SemaDC == LexicalDC) {
 281     DeclCtx = SemaDC;
 282   } else {
 283     Decl::MultipleDC *MDC = new (Ctx) Decl::MultipleDC();
 284     MDC->SemanticDC = SemaDC;
 285     MDC->LexicalDC = LexicalDC;
 286     DeclCtx = MDC;
 287   }
 288 }
 289
 290 bool Decl::isLexicallyWithinFunctionOrMethod() const {
 291   const DeclContext *LDC = getLexicalDeclContext();
 292   while (true) {
 293     if (LDC->isFunctionOrMethod())
 294       return true;
 295     if (!isa<TagDecl>(LDC))
 296       return false;
 297     LDC = LDC->getLexicalParent();
 298   }
 299   return false;
 300 }
 301
 302 bool Decl::isInAnonymousNamespace() const {
 303   const DeclContext *DC = getDeclContext();
 304   do {
 305     if (const NamespaceDecl *ND = dyn_cast<NamespaceDecl>(DC))
 306       if (ND->isAnonymousNamespace())
 307         return true;
 308   } while ((DC = DC->getParent()));
 309
 310   return false;
 311 }
 312
 313 bool Decl::isInStdNamespace() const {
 314   return getDeclContext()->isStdNamespace();
 315 }
 316
 317 TranslationUnitDecl *Decl::getTranslationUnitDecl() {
 318   if (TranslationUnitDecl *TUD = dyn_cast<TranslationUnitDecl>(this))
 319     return TUD;
 320
 321   DeclContext *DC = getDeclContext();
 322   assert(DC && "This decl is not contained in a translation unit!");
 323
 324   while (!DC->isTranslationUnit()) {
 325     DC = DC->getParent();
 326     assert(DC && "This decl is not contained in a translation unit!");
 327   }
 328
 329   return cast<TranslationUnitDecl>(DC);
 330 }
 331
 332 ASTContext &Decl::getASTContext() const {
 333   return getTranslationUnitDecl()->getASTContext();
 334 }
 335
 336 ASTMutationListener *Decl::getASTMutationListener() const {
 337   return getASTContext().getASTMutationListener();
 338 }
 339
 340 unsigned Decl::getMaxAlignment() const {
 341   if (!hasAttrs())
 342     return 0;
 343
 344   unsigned Align = 0;
 345   const AttrVec &V = getAttrs();
 346   ASTContext &Ctx = getASTContext();
 347   specific_attr_iterator<AlignedAttr> I(V.begin()), E(V.end());
 348   for (; I != E; ++I)
 349     Align = std::max(Align, I->getAlignment(Ctx));
 350   return Align;
 351 }
 352
 353 bool Decl::isUsed(bool CheckUsedAttr) const {
 354   const Decl *CanonD = getCanonicalDecl();
 355   if (CanonD->Used)
 356     return true;
 357
 358   // Check for used attribute.
 359   // Ask the most recent decl, since attributes accumulate in the redecl chain.
 360   if (CheckUsedAttr && getMostRecentDecl()->hasAttr<UsedAttr>())
 361     return true;
 362
 363   // The information may have not been deserialized yet. Force deserialization
 364   // to complete the needed information.
 365   return getMostRecentDecl()->getCanonicalDecl()->Used;
 366 }
 367
 368 void Decl::markUsed(ASTContext &C) {
 369   if (isUsed(false))
 370     return;
 371
 372   if (C.getASTMutationListener())
 373     C.getASTMutationListener()->DeclarationMarkedUsed(this);
 374
 375   setIsUsed();
 376 }
 377
 378 bool Decl::isReferenced() const {
 379   if (Referenced)
 380     return true;
 381
 382   // Check redeclarations.
 383   for (auto I : redecls())
 384     if (I->Referenced)
 385       return true;
 386
 387   return false;
 388 }
 389
 390 bool Decl::isExported() const {
 391   if (isModulePrivate())
 392     return false;
 393   // Namespaces are always exported.
 394   if (isa<TranslationUnitDecl>(this) || isa<NamespaceDecl>(this))
 395     return true;
 396   // Otherwise, this is a strictly lexical check.
 397   for (auto *DC = getLexicalDeclContext(); DC; DC = DC->getLexicalParent()) {
 398     if (cast<Decl>(DC)->isModulePrivate())
 399       return false;
 400     if (isa<ExportDecl>(DC))
 401       return true;
 402   }
 403   return false;
 404 }
 405
 406 bool Decl::hasDefiningAttr() const {
 407   return hasAttr<AliasAttr>() || hasAttr<IFuncAttr>();
 408 }
 409
 410 const Attr *Decl::getDefiningAttr() const {
 411   if (AliasAttr *AA = getAttr<AliasAttr>())
 412     return AA;
 413   if (IFuncAttr *IFA = getAttr<IFuncAttr>())
 414     return IFA;
 415   return nullptr;
 416 }
 417
 418 /// \brief Determine the availability of the given declaration based on
 419 /// the target platform.
 420 ///
 421 /// When it returns an availability result other than \c AR_Available,
 422 /// if the \p Message parameter is non-NULL, it will be set to a
 423 /// string describing why the entity is unavailable.
 424 ///
 425 /// FIXME: Make these strings localizable, since they end up in
 426 /// diagnostics.
 427 static AvailabilityResult CheckAvailability(ASTContext &Context,
 428                                             const AvailabilityAttr *A,
 429                                             std::string *Message,
 430                                             VersionTuple EnclosingVersion) {
 431   if (EnclosingVersion.empty())
 432     EnclosingVersion = Context.getTargetInfo().getPlatformMinVersion();
 433
 434   if (EnclosingVersion.empty())
 435     return AR_Available;
 436
 437   // Check if this is an App Extension "platform", and if so chop off
 438   // the suffix for matching with the actual platform.
 439   StringRef ActualPlatform = A->getPlatform()->getName();
 440   StringRef RealizedPlatform = ActualPlatform;
 441   if (Context.getLangOpts().AppExt) {
 442     size_t suffix = RealizedPlatform.rfind("_app_extension");
 443     if (suffix != StringRef::npos)
 444       RealizedPlatform = RealizedPlatform.slice(0, suffix);
 445   }
 446
 447   StringRef TargetPlatform = Context.getTargetInfo().getPlatformName();
 448
 449   // Match the platform name.
 450   if (RealizedPlatform != TargetPlatform)
 451     return AR_Available;
 452
 453   StringRef PrettyPlatformName
 454     = AvailabilityAttr::getPrettyPlatformName(ActualPlatform);
 455
 456   if (PrettyPlatformName.empty())
 457     PrettyPlatformName = ActualPlatform;
 458
 459   std::string HintMessage;
 460   if (!A->getMessage().empty()) {
 461     HintMessage = " - ";
 462     HintMessage += A->getMessage();
 463   }
 464
 465   // Make sure that this declaration has not been marked 'unavailable'.
 466   if (A->getUnavailable()) {
 467     if (Message) {
 468       Message->clear();
 469       llvm::raw_string_ostream Out(*Message);
 470       Out << "not available on " << PrettyPlatformName
 471           << HintMessage;
 472     }
 473
 474     return AR_Unavailable;
 475   }
 476
 477   // Make sure that this declaration has already been introduced.
 478   if (!A->getIntroduced().empty() &&
 479       EnclosingVersion < A->getIntroduced()) {
 480     if (Message) {
 481       Message->clear();
 482       llvm::raw_string_ostream Out(*Message);
 483       VersionTuple VTI(A->getIntroduced());
 484       VTI.UseDotAsSeparator();
 485       Out << "introduced in " << PrettyPlatformName << ' '
 486           << VTI << HintMessage;
 487     }
 488
 489     return A->getStrict() ? AR_Unavailable : AR_NotYetIntroduced;
 490   }
 491
 492   // Make sure that this declaration hasn't been obsoleted.
 493   if (!A->getObsoleted().empty() && EnclosingVersion >= A->getObsoleted()) {
 494     if (Message) {
 495       Message->clear();
 496       llvm::raw_string_ostream Out(*Message);
 497       VersionTuple VTO(A->getObsoleted());
 498       VTO.UseDotAsSeparator();
 499       Out << "obsoleted in " << PrettyPlatformName << ' '
 500           << VTO << HintMessage;
 501     }
 502
 503     return AR_Unavailable;
 504   }
 505
 506   // Make sure that this declaration hasn't been deprecated.
 507   if (!A->getDeprecated().empty() && EnclosingVersion >= A->getDeprecated()) {
 508     if (Message) {
 509       Message->clear();
 510       llvm::raw_string_ostream Out(*Message);
 511       VersionTuple VTD(A->getDeprecated());
 512       VTD.UseDotAsSeparator();
 513       Out << "first deprecated in " << PrettyPlatformName << ' '
 514           << VTD << HintMessage;
 515     }
 516
 517     return AR_Deprecated;
 518   }
 519
 520   return AR_Available;
 521 }
 522
 523 AvailabilityResult Decl::getAvailability(std::string *Message,
 524                                          VersionTuple EnclosingVersion) const {
 525   if (auto *FTD = dyn_cast<FunctionTemplateDecl>(this))
 526     return FTD->getTemplatedDecl()->getAvailability(Message, EnclosingVersion);
 527
 528   AvailabilityResult Result = AR_Available;
 529   std::string ResultMessage;
 530
 531   for (const auto *A : attrs()) {
 532     if (const auto *Deprecated = dyn_cast<DeprecatedAttr>(A)) {
 533       if (Result >= AR_Deprecated)
 534         continue;
 535
 536       if (Message)
 537         ResultMessage = Deprecated->getMessage();
 538
 539       Result = AR_Deprecated;
 540       continue;
 541     }
 542
 543     if (const auto *Unavailable = dyn_cast<UnavailableAttr>(A)) {
 544       if (Message)
 545         *Message = Unavailable->getMessage();
 546       return AR_Unavailable;
 547     }
 548
 549     if (const auto *Availability = dyn_cast<AvailabilityAttr>(A)) {
 550       AvailabilityResult AR = CheckAvailability(getASTContext(), Availability,
 551                                                 Message, EnclosingVersion);
 552
 553       if (AR == AR_Unavailable)
 554         return AR_Unavailable;
 555
 556       if (AR > Result) {
 557         Result = AR;
 558         if (Message)
 559           ResultMessage.swap(*Message);
 560       }
 561       continue;
 562     }
 563   }
 564
 565   if (Message)
 566     Message->swap(ResultMessage);
 567   return Result;
 568 }
 569
 570 bool Decl::canBeWeakImported(bool &IsDefinition) const {
 571   IsDefinition = false;
 572
 573   // Variables, if they aren't definitions.
 574   if (const VarDecl *Var = dyn_cast<VarDecl>(this)) {
 575     if (Var->isThisDeclarationADefinition()) {
 576       IsDefinition = true;
 577       return false;
 578     }
 579     return true;
 580
 581   // Functions, if they aren't definitions.
 582   } else if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(this)) {
 583     if (FD->hasBody()) {
 584       IsDefinition = true;
 585       return false;
 586     }
 587     return true;
 588
 589   // Objective-C classes, if this is the non-fragile runtime.
 590   } else if (isa<ObjCInterfaceDecl>(this) &&
 591              getASTContext().getLangOpts().ObjCRuntime.hasWeakClassImport()) {
 592     return true;
 593
 594   // Nothing else.
 595   } else {
 596     return false;
 597   }
 598 }
 599
 600 bool Decl::isWeakImported() const {
 601   bool IsDefinition;
 602   if (!canBeWeakImported(IsDefinition))
 603     return false;
 604
 605   for (const auto *A : attrs()) {
 606     if (isa<WeakImportAttr>(A))
 607       return true;
 608
 609     if (const auto *Availability = dyn_cast<AvailabilityAttr>(A)) {
 610       if (CheckAvailability(getASTContext(), Availability, nullptr,
 611                             VersionTuple()) == AR_NotYetIntroduced)
 612         return true;
 613     }
 614   }
 615
 616   return false;
 617 }
 618
 619 unsigned Decl::getIdentifierNamespaceForKind(Kind DeclKind) {
 620   switch (DeclKind) {
 621     case Function:
 622     case CXXMethod:
 623     case CXXConstructor:
 624     case ConstructorUsingShadow:
 625     case CXXDestructor:
 626     case CXXConversion:
 627     case EnumConstant:
 628     case Var:
 629     case Binding:
 630     case ImplicitParam:
 631     case ParmVar:
 632     case ObjCMethod:
 633     case ObjCProperty:
 634     case MSProperty:
 635       return IDNS_Ordinary;
 636     case Label:
 637       return IDNS_Label;
 638     case IndirectField:
 639       return IDNS_Ordinary | IDNS_Member;
 640
 641     case NonTypeTemplateParm:
 642       // Non-type template parameters are not found by lookups that ignore
 643       // non-types, but they are found by redeclaration lookups for tag types,
 644       // so we include them in the tag namespace.
 645       return IDNS_Ordinary | IDNS_Tag;
 646
 647     case ObjCCompatibleAlias:
 648     case ObjCInterface:
 649       return IDNS_Ordinary | IDNS_Type;
 650
 651     case Typedef:
 652     case TypeAlias:
 653     case TypeAliasTemplate:
 654     case TemplateTypeParm:
 655     case ObjCTypeParam:
 656       return IDNS_Ordinary | IDNS_Type;
 657
 658     case UnresolvedUsingTypename:
 659       return IDNS_Ordinary | IDNS_Type | IDNS_Using;
 660
 661     case UsingShadow:
 662       return 0; // we'll actually overwrite this later
 663
 664     case UnresolvedUsingValue:
 665       return IDNS_Ordinary | IDNS_Using;
 666
 667     case Using:
 668     case UsingPack:
 669       return IDNS_Using;
 670
 671     case ObjCProtocol:
 672       return IDNS_ObjCProtocol;
 673
 674     case Field:
 675     case ObjCAtDefsField:
 676     case ObjCIvar:
 677       return IDNS_Member;
 678
 679     case Record:
 680     case CXXRecord:
 681     case Enum:
 682       return IDNS_Tag | IDNS_Type;
 683
 684     case Namespace:
 685     case NamespaceAlias:
 686       return IDNS_Namespace;
 687
 688     case FunctionTemplate:
 689     case VarTemplate:
 690       return IDNS_Ordinary;
 691
 692     case ClassTemplate:
 693     case TemplateTemplateParm:
 694       return IDNS_Ordinary | IDNS_Tag | IDNS_Type;
 695
 696     case OMPDeclareReduction:
 697       return IDNS_OMPReduction;
 698
 699     // Never have names.
 700     case Friend:
 701     case FriendTemplate:
 702     case AccessSpec:
 703     case LinkageSpec:
 704     case Export:
 705     case FileScopeAsm:
 706     case StaticAssert:
 707     case ObjCPropertyImpl:
 708     case PragmaComment:
 709     case PragmaDetectMismatch:
 710     case Block:
 711     case Captured:
 712     case TranslationUnit:
 713     case ExternCContext:
 714     case Decomposition:
 715
 716     case UsingDirective:
 717     case BuiltinTemplate:
 718     case ClassTemplateSpecialization:
 719     case ClassTemplatePartialSpecialization:
 720     case ClassScopeFunctionSpecialization:
 721     case VarTemplateSpecialization:
 722     case VarTemplatePartialSpecialization:
 723     case ObjCImplementation:
 724     case ObjCCategory:
 725     case ObjCCategoryImpl:
 726     case Import:
 727     case OMPThreadPrivate:
 728     case OMPCapturedExpr:
 729     case Empty:
 730       // Never looked up by name.
 731       return 0;
 732   }
 733
 734   llvm_unreachable("Invalid DeclKind!");
 735 }
 736
 737 void Decl::setAttrsImpl(const AttrVec &attrs, ASTContext &Ctx) {
 738   assert(!HasAttrs && "Decl already contains attrs.");
 739
 740   AttrVec &AttrBlank = Ctx.getDeclAttrs(this);
 741   assert(AttrBlank.empty() && "HasAttrs was wrong?");
 742
 743   AttrBlank = attrs;
 744   HasAttrs = true;
 745 }
 746
 747 void Decl::dropAttrs() {
 748   if (!HasAttrs) return;
 749
 750   HasAttrs = false;
 751   getASTContext().eraseDeclAttrs(this);
 752 }
 753
 754 const AttrVec &Decl::getAttrs() const {
 755   assert(HasAttrs && "No attrs to get!");
 756   return getASTContext().getDeclAttrs(this);
 757 }
 758
 759 Decl *Decl::castFromDeclContext (const DeclContext *D) {
 760   Decl::Kind DK = D->getDeclKind();
 761   switch(DK) {
 762 #define DECL(NAME, BASE)
 763 #define DECL_CONTEXT(NAME) \
 764     case Decl::NAME:       \
 765       return static_cast<NAME##Decl*>(const_cast<DeclContext*>(D));
 766 #define DECL_CONTEXT_BASE(NAME)
 767 #include "clang/AST/DeclNodes.inc"
 768     default:
 769 #define DECL(NAME, BASE)
 770 #define DECL_CONTEXT_BASE(NAME)                  \
 771       if (DK >= first##NAME && DK <= last##NAME) \
 772         return static_cast<NAME##Decl*>(const_cast<DeclContext*>(D));
 773 #include "clang/AST/DeclNodes.inc"
 774       llvm_unreachable("a decl that inherits DeclContext isn't handled");
 775   }
 776 }
 777
 778 DeclContext *Decl::castToDeclContext(const Decl *D) {
 779   Decl::Kind DK = D->getKind();
 780   switch(DK) {
 781 #define DECL(NAME, BASE)
 782 #define DECL_CONTEXT(NAME) \
 783     case Decl::NAME:       \
 784       return static_cast<NAME##Decl*>(const_cast<Decl*>(D));
 785 #define DECL_CONTEXT_BASE(NAME)
 786 #include "clang/AST/DeclNodes.inc"
 787     default:
 788 #define DECL(NAME, BASE)
 789 #define DECL_CONTEXT_BASE(NAME)                                   \
 790       if (DK >= first##NAME && DK <= last##NAME)                  \
 791         return static_cast<NAME##Decl*>(const_cast<Decl*>(D));
 792 #include "clang/AST/DeclNodes.inc"
 793       llvm_unreachable("a decl that inherits DeclContext isn't handled");
 794   }
 795 }
 796
 797 SourceLocation Decl::getBodyRBrace() const {
 798   // Special handling of FunctionDecl to avoid de-serializing the body from PCH.
 799   // FunctionDecl stores EndRangeLoc for this purpose.
 800   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(this)) {
 801     const FunctionDecl *Definition;
 802     if (FD->hasBody(Definition))
 803       return Definition->getSourceRange().getEnd();
 804     return SourceLocation();
 805   }
 806
 807   if (Stmt *Body = getBody())
 808     return Body->getSourceRange().getEnd();
 809
 810   return SourceLocation();
 811 }
 812
 813 bool Decl::AccessDeclContextSanity() const {
 814 #ifndef NDEBUG
 815   // Suppress this check if any of the following hold:
 816   // 1. this is the translation unit (and thus has no parent)
 817   // 2. this is a template parameter (and thus doesn't belong to its context)
 818   // 3. this is a non-type template parameter
 819   // 4. the context is not a record
 820   // 5. it's invalid
 821   // 6. it's a C++0x static_assert.
 822   if (isa<TranslationUnitDecl>(this) ||
 823       isa<TemplateTypeParmDecl>(this) ||
 824       isa<NonTypeTemplateParmDecl>(this) ||
 825       !isa<CXXRecordDecl>(getDeclContext()) ||
 826       isInvalidDecl() ||
 827       isa<StaticAssertDecl>(this) ||
 828       // FIXME: a ParmVarDecl can have ClassTemplateSpecialization
 829       // as DeclContext (?).
 830       isa<ParmVarDecl>(this) ||
 831       // FIXME: a ClassTemplateSpecialization or CXXRecordDecl can have
 832       // AS_none as access specifier.
 833       isa<CXXRecordDecl>(this) ||
 834       isa<ClassScopeFunctionSpecializationDecl>(this))
 835     return true;
 836
 837   assert(Access != AS_none &&
 838          "Access specifier is AS_none inside a record decl");
 839 #endif
 840   return true;
 841 }
 842
 843 static Decl::Kind getKind(const Decl *D) { return D->getKind(); }
 844 static Decl::Kind getKind(const DeclContext *DC) { return DC->getDeclKind(); }
 845
 846 const FunctionType *Decl::getFunctionType(bool BlocksToo) const {
 847   QualType Ty;
 848   if (const ValueDecl *D = dyn_cast<ValueDecl>(this))
 849     Ty = D->getType();
 850   else if (const TypedefNameDecl *D = dyn_cast<TypedefNameDecl>(this))
 851     Ty = D->getUnderlyingType();
 852   else
 853     return nullptr;
 854
 855   if (Ty->isFunctionPointerType())
 856     Ty = Ty->getAs<PointerType>()->getPointeeType();
 857   else if (BlocksToo && Ty->isBlockPointerType())
 858     Ty = Ty->getAs<BlockPointerType>()->getPointeeType();
 859
 860   return Ty->getAs<FunctionType>();
 861 }
 862
 863
 864 /// Starting at a given context (a Decl or DeclContext), look for a
 865 /// code context that is not a closure (a lambda, block, etc.).
 866 template <class T> static Decl *getNonClosureContext(T *D) {
 867   if (getKind(D) == Decl::CXXMethod) {
 868     CXXMethodDecl *MD = cast<CXXMethodDecl>(D);
 869     if (MD->getOverloadedOperator() == OO_Call &&
 870         MD->getParent()->isLambda())
 871       return getNonClosureContext(MD->getParent()->getParent());
 872     return MD;
 873   } else if (FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
 874     return FD;
 875   } else if (ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
 876     return MD;
 877   } else if (BlockDecl *BD = dyn_cast<BlockDecl>(D)) {
 878     return getNonClosureContext(BD->getParent());
 879   } else if (CapturedDecl *CD = dyn_cast<CapturedDecl>(D)) {
 880     return getNonClosureContext(CD->getParent());
 881   } else {
 882     return nullptr;
 883   }
 884 }
 885
 886 Decl *Decl::getNonClosureContext() {
 887   return ::getNonClosureContext(this);
 888 }
 889
 890 Decl *DeclContext::getNonClosureAncestor() {
 891   return ::getNonClosureContext(this);
 892 }
 893
 894 //===----------------------------------------------------------------------===//
 895 // DeclContext Implementation
 896 //===----------------------------------------------------------------------===//
 897
 898 bool DeclContext::classof(const Decl *D) {
 899   switch (D->getKind()) {
 900 #define DECL(NAME, BASE)
 901 #define DECL_CONTEXT(NAME) case Decl::NAME:
 902 #define DECL_CONTEXT_BASE(NAME)
 903 #include "clang/AST/DeclNodes.inc"
 904       return true;
 905     default:
 906 #define DECL(NAME, BASE)
 907 #define DECL_CONTEXT_BASE(NAME)                 \
 908       if (D->getKind() >= Decl::first##NAME &&  \
 909           D->getKind() <= Decl::last##NAME)     \
 910         return true;
 911 #include "clang/AST/DeclNodes.inc"
 912       return false;
 913   }
 914 }
 915
 916 DeclContext::~DeclContext() { }
 917
 918 /// \brief Find the parent context of this context that will be
 919 /// used for unqualified name lookup.
 920 ///
 921 /// Generally, the parent lookup context is the semantic context. However, for
 922 /// a friend function the parent lookup context is the lexical context, which
 923 /// is the class in which the friend is declared.
 924 DeclContext *DeclContext::getLookupParent() {
 925   // FIXME: Find a better way to identify friends
 926   if (isa<FunctionDecl>(this))
 927     if (getParent()->getRedeclContext()->isFileContext() &&
 928         getLexicalParent()->getRedeclContext()->isRecord())
 929       return getLexicalParent();
 930
 931   return getParent();
 932 }
 933
 934 bool DeclContext::isInlineNamespace() const {
 935   return isNamespace() &&
 936          cast<NamespaceDecl>(this)->isInline();
 937 }
 938
 939 bool DeclContext::isStdNamespace() const {
 940   if (!isNamespace())
 941     return false;
 942
 943   const NamespaceDecl *ND = cast<NamespaceDecl>(this);
 944   if (ND->isInline()) {
 945     return ND->getParent()->isStdNamespace();
 946   }
 947
 948   if (!getParent()->getRedeclContext()->isTranslationUnit())
 949     return false;
 950
 951   const IdentifierInfo *II = ND->getIdentifier();
 952   return II && II->isStr("std");
 953 }
 954
 955 bool DeclContext::isDependentContext() const {
 956   if (isFileContext())
 957     return false;
 958
 959   if (isa<ClassTemplatePartialSpecializationDecl>(this))
 960     return true;
 961
 962   if (const CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(this)) {
 963     if (Record->getDescribedClassTemplate())
 964       return true;
 965
 966     if (Record->isDependentLambda())
 967       return true;
 968   }
 969
 970   if (const FunctionDecl *Function = dyn_cast<FunctionDecl>(this)) {
 971     if (Function->getDescribedFunctionTemplate())
 972       return true;
 973
 974     // Friend function declarations are dependent if their *lexical*
 975     // context is dependent.
 976     if (cast<Decl>(this)->getFriendObjectKind())
 977       return getLexicalParent()->isDependentContext();
 978   }
 979
 980   // FIXME: A variable template is a dependent context, but is not a
 981   // DeclContext. A context within it (such as a lambda-expression)
 982   // should be considered dependent.
 983
 984   return getParent() && getParent()->isDependentContext();
 985 }
 986
 987 bool DeclContext::isTransparentContext() const {
 988   if (DeclKind == Decl::Enum)
 989     return !cast<EnumDecl>(this)->isScoped();
 990   else if (DeclKind == Decl::LinkageSpec || DeclKind == Decl::Export)
 991     return true;
 992
 993   return false;
 994 }
 995
 996 static bool isLinkageSpecContext(const DeclContext *DC,
 997                                  LinkageSpecDecl::LanguageIDs ID) {
 998   while (DC->getDeclKind() != Decl::TranslationUnit) {
 999     if (DC->getDeclKind() == Decl::LinkageSpec)
1000       return cast<LinkageSpecDecl>(DC)->getLanguage() == ID;
1001     DC = DC->getLexicalParent();
1002   }
1003   return false;
1004 }
1005
1006 bool DeclContext::isExternCContext() const {
1007   return isLinkageSpecContext(this, clang::LinkageSpecDecl::lang_c);
1008 }
1009
1010 const LinkageSpecDecl *DeclContext::getExternCContext() const {
1011   const DeclContext *DC = this;
1012   while (DC->getDeclKind() != Decl::TranslationUnit) {
1013     if (DC->getDeclKind() == Decl::LinkageSpec &&
1014         cast<LinkageSpecDecl>(DC)->getLanguage() ==
1015             clang::LinkageSpecDecl::lang_c)
1016       return cast<LinkageSpecDecl>(DC);
1017     DC = DC->getLexicalParent();
1018   }
1019   return nullptr;
1020 }
1021
1022 bool DeclContext::isExternCXXContext() const {
1023   return isLinkageSpecContext(this, clang::LinkageSpecDecl::lang_cxx);
1024 }
1025
1026 bool DeclContext::Encloses(const DeclContext *DC) const {
1027   if (getPrimaryContext() != this)
1028     return getPrimaryContext()->Encloses(DC);
1029
1030   for (; DC; DC = DC->getParent())
1031     if (DC->getPrimaryContext() == this)
1032       return true;
1033   return false;
1034 }
1035
1036 DeclContext *DeclContext::getPrimaryContext() {
1037   switch (DeclKind) {
1038   case Decl::TranslationUnit:
1039   case Decl::ExternCContext:
1040   case Decl::LinkageSpec:
1041   case Decl::Export:
1042   case Decl::Block:
1043   case Decl::Captured:
1044   case Decl::OMPDeclareReduction:
1045     // There is only one DeclContext for these entities.
1046     return this;
1047
1048   case Decl::Namespace:
1049     // The original namespace is our primary context.
1050     return static_cast<NamespaceDecl*>(this)->getOriginalNamespace();
1051
1052   case Decl::ObjCMethod:
1053     return this;
1054
1055   case Decl::ObjCInterface:
1056     if (ObjCInterfaceDecl *Def = cast<ObjCInterfaceDecl>(this)->getDefinition())
1057       return Def;
1058
1059     return this;
1060
1061   case Decl::ObjCProtocol:
1062     if (ObjCProtocolDecl *Def = cast<ObjCProtocolDecl>(this)->getDefinition())
1063       return Def;
1064
1065     return this;
1066
1067   case Decl::ObjCCategory:
1068     return this;
1069
1070   case Decl::ObjCImplementation:
1071   case Decl::ObjCCategoryImpl:
1072     return this;
1073
1074   default:
1075     if (DeclKind >= Decl::firstTag && DeclKind <= Decl::lastTag) {
1076       // If this is a tag type that has a definition or is currently
1077       // being defined, that definition is our primary context.
1078       TagDecl *Tag = cast<TagDecl>(this);
1079
1080       if (TagDecl *Def = Tag->getDefinition())
1081         return Def;
1082
1083       if (const TagType *TagTy = dyn_cast<TagType>(Tag->getTypeForDecl())) {
1084         // Note, TagType::getDecl returns the (partial) definition one exists.
1085         TagDecl *PossiblePartialDef = TagTy->getDecl();
1086         if (PossiblePartialDef->isBeingDefined())
1087           return PossiblePartialDef;
1088       } else {
1089         assert(isa<InjectedClassNameType>(Tag->getTypeForDecl()));
1090       }
1091
1092       return Tag;
1093     }
1094
1095     assert(DeclKind >= Decl::firstFunction && DeclKind <= Decl::lastFunction &&
1096           "Unknown DeclContext kind");
1097     return this;
1098   }
1099 }
1100
1101 void
1102 DeclContext::collectAllContexts(SmallVectorImpl<DeclContext *> &Contexts){
1103   Contexts.clear();
1104
1105   if (DeclKind != Decl::Namespace) {
1106     Contexts.push_back(this);
1107     return;
1108   }
1109
1110   NamespaceDecl *Self = static_cast<NamespaceDecl *>(this);
1111   for (NamespaceDecl *N = Self->getMostRecentDecl(); N;
1112        N = N->getPreviousDecl())
1113     Contexts.push_back(N);
1114
1115   std::reverse(Contexts.begin(), Contexts.end());
1116 }
1117
1118 std::pair<Decl *, Decl *>
1119 DeclContext::BuildDeclChain(ArrayRef<Decl*> Decls,
1120                             bool FieldsAlreadyLoaded) {
1121   // Build up a chain of declarations via the Decl::NextInContextAndBits field.
1122   Decl *FirstNewDecl = nullptr;
1123   Decl *PrevDecl = nullptr;
1124   for (unsigned I = 0, N = Decls.size(); I != N; ++I) {
1125     if (FieldsAlreadyLoaded && isa<FieldDecl>(Decls[I]))
1126       continue;
1127
1128     Decl *D = Decls[I];
1129     if (PrevDecl)
1130       PrevDecl->NextInContextAndBits.setPointer(D);
1131     else
1132       FirstNewDecl = D;
1133
1134     PrevDecl = D;
1135   }
1136
1137   return std::make_pair(FirstNewDecl, PrevDecl);
1138 }
1139
1140 /// \brief We have just acquired external visible storage, and we already have
1141 /// built a lookup map. For every name in the map, pull in the new names from
1142 /// the external storage.
1143 void DeclContext::reconcileExternalVisibleStorage() const {
1144   assert(NeedToReconcileExternalVisibleStorage && LookupPtr);
1145   NeedToReconcileExternalVisibleStorage = false;
1146
1147   for (auto &Lookup : *LookupPtr)
1148     Lookup.second.setHasExternalDecls();
1149 }
1150
1151 /// \brief Load the declarations within this lexical storage from an
1152 /// external source.
1153 /// \return \c true if any declarations were added.
1154 bool
1155 DeclContext::LoadLexicalDeclsFromExternalStorage() const {
1156   ExternalASTSource *Source = getParentASTContext().getExternalSource();
1157   assert(hasExternalLexicalStorage() && Source && "No external storage?");
1158
1159   // Notify that we have a DeclContext that is initializing.
1160   ExternalASTSource::Deserializing ADeclContext(Source);
1161
1162   // Load the external declarations, if any.
1163   SmallVector<Decl*, 64> Decls;
1164   ExternalLexicalStorage = false;
1165   Source->FindExternalLexicalDecls(this, Decls);
1166
1167   if (Decls.empty())
1168     return false;
1169
1170   // We may have already loaded just the fields of this record, in which case
1171   // we need to ignore them.
1172   bool FieldsAlreadyLoaded = false;
1173   if (const RecordDecl *RD = dyn_cast<RecordDecl>(this))
1174     FieldsAlreadyLoaded = RD->LoadedFieldsFromExternalStorage;
1175
1176   // Splice the newly-read declarations into the beginning of the list
1177   // of declarations.
1178   Decl *ExternalFirst, *ExternalLast;
1179   std::tie(ExternalFirst, ExternalLast) =
1180       BuildDeclChain(Decls, FieldsAlreadyLoaded);
1181   ExternalLast->NextInContextAndBits.setPointer(FirstDecl);
1182   FirstDecl = ExternalFirst;
1183   if (!LastDecl)
1184     LastDecl = ExternalLast;
1185   return true;
1186 }
1187
1188 DeclContext::lookup_result
1189 ExternalASTSource::SetNoExternalVisibleDeclsForName(const DeclContext *DC,
1190                                                     DeclarationName Name) {
1191   ASTContext &Context = DC->getParentASTContext();
1192   StoredDeclsMap *Map;
1193   if (!(Map = DC->LookupPtr))
1194     Map = DC->CreateStoredDeclsMap(Context);
1195   if (DC->NeedToReconcileExternalVisibleStorage)
1196     DC->reconcileExternalVisibleStorage();
1197
1198   (*Map)[Name].removeExternalDecls();
1199
1200   return DeclContext::lookup_result();
1201 }
1202
1203 DeclContext::lookup_result
1204 ExternalASTSource::SetExternalVisibleDeclsForName(const DeclContext *DC,
1205                                                   DeclarationName Name,
1206                                                   ArrayRef<NamedDecl*> Decls) {
1207   ASTContext &Context = DC->getParentASTContext();
1208   StoredDeclsMap *Map;
1209   if (!(Map = DC->LookupPtr))
1210     Map = DC->CreateStoredDeclsMap(Context);
1211   if (DC->NeedToReconcileExternalVisibleStorage)
1212     DC->reconcileExternalVisibleStorage();
1213
1214   StoredDeclsList &List = (*Map)[Name];
1215
1216   // Clear out any old external visible declarations, to avoid quadratic
1217   // performance in the redeclaration checks below.
1218   List.removeExternalDecls();
1219
1220   if (!List.isNull()) {
1221     // We have both existing declarations and new declarations for this name.
1222     // Some of the declarations may simply replace existing ones. Handle those
1223     // first.
1224     llvm::SmallVector<unsigned, 8> Skip;
1225     for (unsigned I = 0, N = Decls.size(); I != N; ++I)
1226       if (List.HandleRedeclaration(Decls[I], /*IsKnownNewer*/false))
1227         Skip.push_back(I);
1228     Skip.push_back(Decls.size());
1229
1230     // Add in any new declarations.
1231     unsigned SkipPos = 0;
1232     for (unsigned I = 0, N = Decls.size(); I != N; ++I) {
1233       if (I == Skip[SkipPos])
1234         ++SkipPos;
1235       else
1236         List.AddSubsequentDecl(Decls[I]);
1237     }
1238   } else {
1239     // Convert the array to a StoredDeclsList.
1240     for (ArrayRef<NamedDecl*>::iterator
1241            I = Decls.begin(), E = Decls.end(); I != E; ++I) {
1242       if (List.isNull())
1243         List.setOnlyValue(*I);
1244       else
1245         List.AddSubsequentDecl(*I);
1246     }
1247   }
1248
1249   return List.getLookupResult();
1250 }
1251
1252 DeclContext::decl_iterator DeclContext::decls_begin() const {
1253   if (hasExternalLexicalStorage())
1254     LoadLexicalDeclsFromExternalStorage();
1255   return decl_iterator(FirstDecl);
1256 }
1257
1258 bool DeclContext::decls_empty() const {
1259   if (hasExternalLexicalStorage())
1260     LoadLexicalDeclsFromExternalStorage();
1261
1262   return !FirstDecl;
1263 }
1264
1265 bool DeclContext::containsDecl(Decl *D) const {
1266   return (D->getLexicalDeclContext() == this &&
1267           (D->NextInContextAndBits.getPointer() || D == LastDecl));
1268 }
1269
1270 void DeclContext::removeDecl(Decl *D) {
1271   assert(D->getLexicalDeclContext() == this &&
1272          "decl being removed from non-lexical context");
1273   assert((D->NextInContextAndBits.getPointer() || D == LastDecl) &&
1274          "decl is not in decls list");
1275
1276   // Remove D from the decl chain.  This is O(n) but hopefully rare.
1277   if (D == FirstDecl) {
1278     if (D == LastDecl)
1279       FirstDecl = LastDecl = nullptr;
1280     else
1281       FirstDecl = D->NextInContextAndBits.getPointer();
1282   } else {
1283     for (Decl *I = FirstDecl; true; I = I->NextInContextAndBits.getPointer()) {
1284       assert(I && "decl not found in linked list");
1285       if (I->NextInContextAndBits.getPointer() == D) {
1286         I->NextInContextAndBits.setPointer(D->NextInContextAndBits.getPointer());
1287         if (D == LastDecl) LastDecl = I;
1288         break;
1289       }
1290     }
1291   }
1292
1293   // Mark that D is no longer in the decl chain.
1294   D->NextInContextAndBits.setPointer(nullptr);
1295
1296   // Remove D from the lookup table if necessary.
1297   if (isa<NamedDecl>(D)) {
1298     NamedDecl *ND = cast<NamedDecl>(D);
1299
1300     // Remove only decls that have a name
1301     if (!ND->getDeclName()) return;
1302
1303     auto *DC = this;
1304     do {
1305       StoredDeclsMap *Map = DC->getPrimaryContext()->LookupPtr;
1306       if (Map) {
1307         StoredDeclsMap::iterator Pos = Map->find(ND->getDeclName());
1308         assert(Pos != Map->end() && "no lookup entry for decl");
1309         if (Pos->second.getAsVector() || Pos->second.getAsDecl() == ND)
1310           Pos->second.remove(ND);
1311       }
1312     } while (DC->isTransparentContext() && (DC = DC->getParent()));
1313   }
1314 }
1315
1316 void DeclContext::addHiddenDecl(Decl *D) {
1317   assert(D->getLexicalDeclContext() == this &&
1318          "Decl inserted into wrong lexical context");
1319   assert(!D->getNextDeclInContext() && D != LastDecl &&
1320          "Decl already inserted into a DeclContext");
1321
1322   if (FirstDecl) {
1323     LastDecl->NextInContextAndBits.setPointer(D);
1324     LastDecl = D;
1325   } else {
1326     FirstDecl = LastDecl = D;
1327   }
1328
1329   // Notify a C++ record declaration that we've added a member, so it can
1330   // update its class-specific state.
1331   if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(this))
1332     Record->addedMember(D);
1333
1334   // If this is a newly-created (not de-serialized) import declaration, wire
1335   // it in to the list of local import declarations.
1336   if (!D->isFromASTFile()) {
1337     if (ImportDecl *Import = dyn_cast<ImportDecl>(D))
1338       D->getASTContext().addedLocalImportDecl(Import);
1339   }
1340 }
1341
1342 void DeclContext::addDecl(Decl *D) {
1343   addHiddenDecl(D);
1344
1345   if (NamedDecl *ND = dyn_cast<NamedDecl>(D))
1346     ND->getDeclContext()->getPrimaryContext()->
1347         makeDeclVisibleInContextWithFlags(ND, false, true);
1348 }
1349
1350 void DeclContext::addDeclInternal(Decl *D) {
1351   addHiddenDecl(D);
1352
1353   if (NamedDecl *ND = dyn_cast<NamedDecl>(D))
1354     ND->getDeclContext()->getPrimaryContext()->
1355         makeDeclVisibleInContextWithFlags(ND, true, true);
1356 }
1357
1358 /// shouldBeHidden - Determine whether a declaration which was declared
1359 /// within its semantic context should be invisible to qualified name lookup.
1360 static bool shouldBeHidden(NamedDecl *D) {
1361   // Skip unnamed declarations.
1362   if (!D->getDeclName())
1363     return true;
1364
1365   // Skip entities that can't be found by name lookup into a particular
1366   // context.
1367   if ((D->getIdentifierNamespace() == 0 && !isa<UsingDirectiveDecl>(D)) ||
1368       D->isTemplateParameter())
1369     return true;
1370
1371   // Skip template specializations.
1372   // FIXME: This feels like a hack. Should DeclarationName support
1373   // template-ids, or is there a better way to keep specializations
1374   // from being visible?
1375   if (isa<ClassTemplateSpecializationDecl>(D))
1376     return true;
1377   if (FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
1378     if (FD->isFunctionTemplateSpecialization())
1379       return true;
1380
1381   return false;
1382 }
1383
1384 /// buildLookup - Build the lookup data structure with all of the
1385 /// declarations in this DeclContext (and any other contexts linked
1386 /// to it or transparent contexts nested within it) and return it.
1387 ///
1388 /// Note that the produced map may miss out declarations from an
1389 /// external source. If it does, those entries will be marked with
1390 /// the 'hasExternalDecls' flag.
1391 StoredDeclsMap *DeclContext::buildLookup() {
1392   assert(this == getPrimaryContext() && "buildLookup called on non-primary DC");
1393
1394   if (!HasLazyLocalLexicalLookups && !HasLazyExternalLexicalLookups)
1395     return LookupPtr;
1396
1397   SmallVector<DeclContext *, 2> Contexts;
1398   collectAllContexts(Contexts);
1399
1400   if (HasLazyExternalLexicalLookups) {
1401     HasLazyExternalLexicalLookups = false;
1402     for (auto *DC : Contexts) {
1403       if (DC->hasExternalLexicalStorage())
1404         HasLazyLocalLexicalLookups |=
1405             DC->LoadLexicalDeclsFromExternalStorage();
1406     }
1407
1408     if (!HasLazyLocalLexicalLookups)
1409       return LookupPtr;
1410   }
1411
1412   for (auto *DC : Contexts)
1413     buildLookupImpl(DC, hasExternalVisibleStorage());
1414
1415   // We no longer have any lazy decls.
1416   HasLazyLocalLexicalLookups = false;
1417   return LookupPtr;
1418 }
1419
1420 /// buildLookupImpl - Build part of the lookup data structure for the
1421 /// declarations contained within DCtx, which will either be this
1422 /// DeclContext, a DeclContext linked to it, or a transparent context
1423 /// nested within it.
1424 void DeclContext::buildLookupImpl(DeclContext *DCtx, bool Internal) {
1425   for (Decl *D : DCtx->noload_decls()) {
1426     // Insert this declaration into the lookup structure, but only if
1427     // it's semantically within its decl context. Any other decls which
1428     // should be found in this context are added eagerly.
1429     //
1430     // If it's from an AST file, don't add it now. It'll get handled by
1431     // FindExternalVisibleDeclsByName if needed. Exception: if we're not
1432     // in C++, we do not track external visible decls for the TU, so in
1433     // that case we need to collect them all here.
1434     if (NamedDecl *ND = dyn_cast<NamedDecl>(D))
1435       if (ND->getDeclContext() == DCtx && !shouldBeHidden(ND) &&
1436           (!ND->isFromASTFile() ||
1437            (isTranslationUnit() &&
1438             !getParentASTContext().getLangOpts().CPlusPlus)))
1439         makeDeclVisibleInContextImpl(ND, Internal);
1440
1441     // If this declaration is itself a transparent declaration context
1442     // or inline namespace, add the members of this declaration of that
1443     // context (recursively).
1444     if (DeclContext *InnerCtx = dyn_cast<DeclContext>(D))
1445       if (InnerCtx->isTransparentContext() || InnerCtx->isInlineNamespace())
1446         buildLookupImpl(InnerCtx, Internal);
1447   }
1448 }
1449
1450 NamedDecl *const DeclContextLookupResult::SingleElementDummyList = nullptr;
1451
1452 DeclContext::lookup_result
1453 DeclContext::lookup(DeclarationName Name) const {
1454   assert(DeclKind != Decl::LinkageSpec && DeclKind != Decl::Export &&
1455          "should not perform lookups into transparent contexts");
1456
1457   const DeclContext *PrimaryContext = getPrimaryContext();
1458   if (PrimaryContext != this)
1459     return PrimaryContext->lookup(Name);
1460
1461   // If we have an external source, ensure that any later redeclarations of this
1462   // context have been loaded, since they may add names to the result of this
1463   // lookup (or add external visible storage).
1464   ExternalASTSource *Source = getParentASTContext().getExternalSource();
1465   if (Source)
1466     (void)cast<Decl>(this)->getMostRecentDecl();
1467
1468   if (hasExternalVisibleStorage()) {
1469     assert(Source && "external visible storage but no external source?");
1470
1471     if (NeedToReconcileExternalVisibleStorage)
1472       reconcileExternalVisibleStorage();
1473
1474     StoredDeclsMap *Map = LookupPtr;
1475
1476     if (HasLazyLocalLexicalLookups || HasLazyExternalLexicalLookups)
1477       // FIXME: Make buildLookup const?
1478       Map = const_cast<DeclContext*>(this)->buildLookup();
1479
1480     if (!Map)
1481       Map = CreateStoredDeclsMap(getParentASTContext());
1482
1483     // If we have a lookup result with no external decls, we are done.
1484     std::pair<StoredDeclsMap::iterator, bool> R =
1485         Map->insert(std::make_pair(Name, StoredDeclsList()));
1486     if (!R.second && !R.first->second.hasExternalDecls())
1487       return R.first->second.getLookupResult();
1488
1489     if (Source->FindExternalVisibleDeclsByName(this, Name) || !R.second) {
1490       if (StoredDeclsMap *Map = LookupPtr) {
1491         StoredDeclsMap::iterator I = Map->find(Name);
1492         if (I != Map->end())
1493           return I->second.getLookupResult();
1494       }
1495     }
1496
1497     return lookup_result();
1498   }
1499
1500   StoredDeclsMap *Map = LookupPtr;
1501   if (HasLazyLocalLexicalLookups || HasLazyExternalLexicalLookups)
1502     Map = const_cast<DeclContext*>(this)->buildLookup();
1503
1504   if (!Map)
1505     return lookup_result();
1506
1507   StoredDeclsMap::iterator I = Map->find(Name);
1508   if (I == Map->end())
1509     return lookup_result();
1510
1511   return I->second.getLookupResult();
1512 }
1513
1514 DeclContext::lookup_result
1515 DeclContext::noload_lookup(DeclarationName Name) {
1516   assert(DeclKind != Decl::LinkageSpec && DeclKind != Decl::Export &&
1517          "should not perform lookups into transparent contexts");
1518
1519   DeclContext *PrimaryContext = getPrimaryContext();
1520   if (PrimaryContext != this)
1521     return PrimaryContext->noload_lookup(Name);
1522
1523   // If we have any lazy lexical declarations not in our lookup map, add them
1524   // now. Don't import any external declarations, not even if we know we have
1525   // some missing from the external visible lookups.
1526   if (HasLazyLocalLexicalLookups) {
1527     SmallVector<DeclContext *, 2> Contexts;
1528     collectAllContexts(Contexts);
1529     for (unsigned I = 0, N = Contexts.size(); I != N; ++I)
1530       buildLookupImpl(Contexts[I], hasExternalVisibleStorage());
1531     HasLazyLocalLexicalLookups = false;
1532   }
1533
1534   StoredDeclsMap *Map = LookupPtr;
1535   if (!Map)
1536     return lookup_result();
1537
1538   StoredDeclsMap::iterator I = Map->find(Name);
1539   return I != Map->end() ? I->second.getLookupResult()
1540                          : lookup_result();
1541 }
1542
1543 void DeclContext::localUncachedLookup(DeclarationName Name,
1544                                       SmallVectorImpl<NamedDecl *> &Results) {
1545   Results.clear();
1546
1547   // If there's no external storage, just perform a normal lookup and copy
1548   // the results.
1549   if (!hasExternalVisibleStorage() && !hasExternalLexicalStorage() && Name) {
1550     lookup_result LookupResults = lookup(Name);
1551     Results.insert(Results.end(), LookupResults.begin(), LookupResults.end());
1552     return;
1553   }
1554
1555   // If we have a lookup table, check there first. Maybe we'll get lucky.
1556   // FIXME: Should we be checking these flags on the primary context?
1557   if (Name && !HasLazyLocalLexicalLookups && !HasLazyExternalLexicalLookups) {
1558     if (StoredDeclsMap *Map = LookupPtr) {
1559       StoredDeclsMap::iterator Pos = Map->find(Name);
1560       if (Pos != Map->end()) {
1561         Results.insert(Results.end(),
1562                        Pos->second.getLookupResult().begin(),
1563                        Pos->second.getLookupResult().end());
1564         return;
1565       }
1566     }
1567   }
1568
1569   // Slow case: grovel through the declarations in our chain looking for
1570   // matches.
1571   // FIXME: If we have lazy external declarations, this will not find them!
1572   // FIXME: Should we CollectAllContexts and walk them all here?
1573   for (Decl *D = FirstDecl; D; D = D->getNextDeclInContext()) {
1574     if (NamedDecl *ND = dyn_cast<NamedDecl>(D))
1575       if (ND->getDeclName() == Name)
1576         Results.push_back(ND);
1577   }
1578 }
1579
1580 DeclContext *DeclContext::getRedeclContext() {
1581   DeclContext *Ctx = this;
1582   // Skip through transparent contexts.
1583   while (Ctx->isTransparentContext())
1584     Ctx = Ctx->getParent();
1585   return Ctx;
1586 }
1587
1588 DeclContext *DeclContext::getEnclosingNamespaceContext() {
1589   DeclContext *Ctx = this;
1590   // Skip through non-namespace, non-translation-unit contexts.
1591   while (!Ctx->isFileContext())
1592     Ctx = Ctx->getParent();
1593   return Ctx->getPrimaryContext();
1594 }
1595
1596 RecordDecl *DeclContext::getOuterLexicalRecordContext() {
1597   // Loop until we find a non-record context.
1598   RecordDecl *OutermostRD = nullptr;
1599   DeclContext *DC = this;
1600   while (DC->isRecord()) {
1601     OutermostRD = cast<RecordDecl>(DC);
1602     DC = DC->getLexicalParent();
1603   }
1604   return OutermostRD;
1605 }
1606
1607 bool DeclContext::InEnclosingNamespaceSetOf(const DeclContext *O) const {
1608   // For non-file contexts, this is equivalent to Equals.
1609   if (!isFileContext())
1610     return O->Equals(this);
1611
1612   do {
1613     if (O->Equals(this))
1614       return true;
1615
1616     const NamespaceDecl *NS = dyn_cast<NamespaceDecl>(O);
1617     if (!NS || !NS->isInline())
1618       break;
1619     O = NS->getParent();
1620   } while (O);
1621
1622   return false;
1623 }
1624
1625 void DeclContext::makeDeclVisibleInContext(NamedDecl *D) {
1626   DeclContext *PrimaryDC = this->getPrimaryContext();
1627   DeclContext *DeclDC = D->getDeclContext()->getPrimaryContext();
1628   // If the decl is being added outside of its semantic decl context, we
1629   // need to ensure that we eagerly build the lookup information for it.
1630   PrimaryDC->makeDeclVisibleInContextWithFlags(D, false, PrimaryDC == DeclDC);
1631 }
1632
1633 void DeclContext::makeDeclVisibleInContextWithFlags(NamedDecl *D, bool Internal,
1634                                                     bool Recoverable) {
1635   assert(this == getPrimaryContext() && "expected a primary DC");
1636
1637   if (!isLookupContext()) {
1638     if (isTransparentContext())
1639       getParent()->getPrimaryContext()
1640         ->makeDeclVisibleInContextWithFlags(D, Internal, Recoverable);
1641     return;
1642   }
1643
1644   // Skip declarations which should be invisible to name lookup.
1645   if (shouldBeHidden(D))
1646     return;
1647
1648   // If we already have a lookup data structure, perform the insertion into
1649   // it. If we might have externally-stored decls with this name, look them
1650   // up and perform the insertion. If this decl was declared outside its
1651   // semantic context, buildLookup won't add it, so add it now.
1652   //
1653   // FIXME: As a performance hack, don't add such decls into the translation
1654   // unit unless we're in C++, since qualified lookup into the TU is never
1655   // performed.
1656   if (LookupPtr || hasExternalVisibleStorage() ||
1657       ((!Recoverable || D->getDeclContext() != D->getLexicalDeclContext()) &&
1658        (getParentASTContext().getLangOpts().CPlusPlus ||
1659         !isTranslationUnit()))) {
1660     // If we have lazily omitted any decls, they might have the same name as
1661     // the decl which we are adding, so build a full lookup table before adding
1662     // this decl.
1663     buildLookup();
1664     makeDeclVisibleInContextImpl(D, Internal);
1665   } else {
1666     HasLazyLocalLexicalLookups = true;
1667   }
1668
1669   // If we are a transparent context or inline namespace, insert into our
1670   // parent context, too. This operation is recursive.
1671   if (isTransparentContext() || isInlineNamespace())
1672     getParent()->getPrimaryContext()->
1673         makeDeclVisibleInContextWithFlags(D, Internal, Recoverable);
1674
1675   Decl *DCAsDecl = cast<Decl>(this);
1676   // Notify that a decl was made visible unless we are a Tag being defined.
1677   if (!(isa<TagDecl>(DCAsDecl) && cast<TagDecl>(DCAsDecl)->isBeingDefined()))
1678     if (ASTMutationListener *L = DCAsDecl->getASTMutationListener())
1679       L->AddedVisibleDecl(this, D);
1680 }
1681
1682 void DeclContext::makeDeclVisibleInContextImpl(NamedDecl *D, bool Internal) {
1683   // Find or create the stored declaration map.
1684   StoredDeclsMap *Map = LookupPtr;
1685   if (!Map) {
1686     ASTContext *C = &getParentASTContext();
1687     Map = CreateStoredDeclsMap(*C);
1688   }
1689
1690   // If there is an external AST source, load any declarations it knows about
1691   // with this declaration's name.
1692   // If the lookup table contains an entry about this name it means that we
1693   // have already checked the external source.
1694   if (!Internal)
1695     if (ExternalASTSource *Source = getParentASTContext().getExternalSource())
1696       if (hasExternalVisibleStorage() &&
1697           Map->find(D->getDeclName()) == Map->end())
1698         Source->FindExternalVisibleDeclsByName(this, D->getDeclName());
1699
1700   // Insert this declaration into the map.
1701   StoredDeclsList &DeclNameEntries = (*Map)[D->getDeclName()];
1702
1703   if (Internal) {
1704     // If this is being added as part of loading an external declaration,
1705     // this may not be the only external declaration with this name.
1706     // In this case, we never try to replace an existing declaration; we'll
1707     // handle that when we finalize the list of declarations for this name.
1708     DeclNameEntries.setHasExternalDecls();
1709     DeclNameEntries.AddSubsequentDecl(D);
1710     return;
1711   }
1712
1713   if (DeclNameEntries.isNull()) {
1714     DeclNameEntries.setOnlyValue(D);
1715     return;
1716   }
1717
1718   if (DeclNameEntries.HandleRedeclaration(D, /*IsKnownNewer*/!Internal)) {
1719     // This declaration has replaced an existing one for which
1720     // declarationReplaces returns true.
1721     return;
1722   }
1723
1724   // Put this declaration into the appropriate slot.
1725   DeclNameEntries.AddSubsequentDecl(D);
1726 }
1727
1728 UsingDirectiveDecl *DeclContext::udir_iterator::operator*() const {
1729   return cast<UsingDirectiveDecl>(*I);
1730 }
1731
1732 /// Returns iterator range [First, Last) of UsingDirectiveDecls stored within
1733 /// this context.
1734 DeclContext::udir_range DeclContext::using_directives() const {
1735   // FIXME: Use something more efficient than normal lookup for using
1736   // directives. In C++, using directives are looked up more than anything else.
1737   lookup_result Result = lookup(UsingDirectiveDecl::getName());
1738   return udir_range(Result.begin(), Result.end());
1739 }
1740
1741 //===----------------------------------------------------------------------===//
1742 // Creation and Destruction of StoredDeclsMaps.                               //
1743 //===----------------------------------------------------------------------===//
1744
1745 StoredDeclsMap *DeclContext::CreateStoredDeclsMap(ASTContext &C) const {
1746   assert(!LookupPtr && "context already has a decls map");
1747   assert(getPrimaryContext() == this &&
1748          "creating decls map on non-primary context");
1749
1750   StoredDeclsMap *M;
1751   bool Dependent = isDependentContext();
1752   if (Dependent)
1753     M = new DependentStoredDeclsMap();
1754   else
1755     M = new StoredDeclsMap();
1756   M->Previous = C.LastSDM;
1757   C.LastSDM = llvm::PointerIntPair<StoredDeclsMap*,1>(M, Dependent);
1758   LookupPtr = M;
1759   return M;
1760 }
1761
1762 void ASTContext::ReleaseDeclContextMaps() {
1763   // It's okay to delete DependentStoredDeclsMaps via a StoredDeclsMap
1764   // pointer because the subclass doesn't add anything that needs to
1765   // be deleted.
1766   StoredDeclsMap::DestroyAll(LastSDM.getPointer(), LastSDM.getInt());
1767 }
1768
1769 void StoredDeclsMap::DestroyAll(StoredDeclsMap *Map, bool Dependent) {
1770   while (Map) {
1771     // Advance the iteration before we invalidate memory.
1772     llvm::PointerIntPair<StoredDeclsMap*,1> Next = Map->Previous;
1773
1774     if (Dependent)
1775       delete static_cast<DependentStoredDeclsMap*>(Map);
1776     else
1777       delete Map;
1778
1779     Map = Next.getPointer();
1780     Dependent = Next.getInt();
1781   }
1782 }
1783
1784 DependentDiagnostic *DependentDiagnostic::Create(ASTContext &C,
1785                                                  DeclContext *Parent,
1786                                            const PartialDiagnostic &PDiag) {
1787   assert(Parent->isDependentContext()
1788          && "cannot iterate dependent diagnostics of non-dependent context");
1789   Parent = Parent->getPrimaryContext();
1790   if (!Parent->LookupPtr)
1791     Parent->CreateStoredDeclsMap(C);
1792
1793   DependentStoredDeclsMap *Map =
1794       static_cast<DependentStoredDeclsMap *>(Parent->LookupPtr);
1795
1796   // Allocate the copy of the PartialDiagnostic via the ASTContext's
1797   // BumpPtrAllocator, rather than the ASTContext itself.
1798   PartialDiagnostic::Storage *DiagStorage = nullptr;
1799   if (PDiag.hasStorage())
1800     DiagStorage = new (C) PartialDiagnostic::Storage;
1801
1802   DependentDiagnostic *DD = new (C) DependentDiagnostic(PDiag, DiagStorage);
1803
1804   // TODO: Maybe we shouldn't reverse the order during insertion.
1805   DD->NextDiagnostic = Map->FirstDiagnostic;
1806   Map->FirstDiagnostic = DD;
1807
1808   return DD;
1809 }