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 CXXDeductionGuide:
 623     case CXXMethod:
 624     case CXXConstructor:
 625     case ConstructorUsingShadow:
 626     case CXXDestructor:
 627     case CXXConversion:
 628     case EnumConstant:
 629     case Var:
 630     case Binding:
 631     case ImplicitParam:
 632     case ParmVar:
 633     case ObjCMethod:
 634     case ObjCProperty:
 635     case MSProperty:
 636       return IDNS_Ordinary;
 637     case Label:
 638       return IDNS_Label;
 639     case IndirectField:
 640       return IDNS_Ordinary | IDNS_Member;
 641
 642     case NonTypeTemplateParm:
 643       // Non-type template parameters are not found by lookups that ignore
 644       // non-types, but they are found by redeclaration lookups for tag types,
 645       // so we include them in the tag namespace.
 646       return IDNS_Ordinary | IDNS_Tag;
 647
 648     case ObjCCompatibleAlias:
 649     case ObjCInterface:
 650       return IDNS_Ordinary | IDNS_Type;
 651
 652     case Typedef:
 653     case TypeAlias:
 654     case TypeAliasTemplate:
 655     case TemplateTypeParm:
 656     case ObjCTypeParam:
 657       return IDNS_Ordinary | IDNS_Type;
 658
 659     case UnresolvedUsingTypename:
 660       return IDNS_Ordinary | IDNS_Type | IDNS_Using;
 661
 662     case UsingShadow:
 663       return 0; // we'll actually overwrite this later
 664
 665     case UnresolvedUsingValue:
 666       return IDNS_Ordinary | IDNS_Using;
 667
 668     case Using:
 669     case UsingPack:
 670       return IDNS_Using;
 671
 672     case ObjCProtocol:
 673       return IDNS_ObjCProtocol;
 674
 675     case Field:
 676     case ObjCAtDefsField:
 677     case ObjCIvar:
 678       return IDNS_Member;
 679
 680     case Record:
 681     case CXXRecord:
 682     case Enum:
 683       return IDNS_Tag | IDNS_Type;
 684
 685     case Namespace:
 686     case NamespaceAlias:
 687       return IDNS_Namespace;
 688
 689     case FunctionTemplate:
 690     case VarTemplate:
 691       return IDNS_Ordinary;
 692
 693     case ClassTemplate:
 694     case TemplateTemplateParm:
 695       return IDNS_Ordinary | IDNS_Tag | IDNS_Type;
 696
 697     case OMPDeclareReduction:
 698       return IDNS_OMPReduction;
 699
 700     // Never have names.
 701     case Friend:
 702     case FriendTemplate:
 703     case AccessSpec:
 704     case LinkageSpec:
 705     case Export:
 706     case FileScopeAsm:
 707     case StaticAssert:
 708     case ObjCPropertyImpl:
 709     case PragmaComment:
 710     case PragmaDetectMismatch:
 711     case Block:
 712     case Captured:
 713     case TranslationUnit:
 714     case ExternCContext:
 715     case Decomposition:
 716
 717     case UsingDirective:
 718     case BuiltinTemplate:
 719     case ClassTemplateSpecialization:
 720     case ClassTemplatePartialSpecialization:
 721     case ClassScopeFunctionSpecialization:
 722     case VarTemplateSpecialization:
 723     case VarTemplatePartialSpecialization:
 724     case ObjCImplementation:
 725     case ObjCCategory:
 726     case ObjCCategoryImpl:
 727     case Import:
 728     case OMPThreadPrivate:
 729     case OMPCapturedExpr:
 730     case Empty:
 731       // Never looked up by name.
 732       return 0;
 733   }
 734
 735   llvm_unreachable("Invalid DeclKind!");
 736 }
 737
 738 void Decl::setAttrsImpl(const AttrVec &attrs, ASTContext &Ctx) {
 739   assert(!HasAttrs && "Decl already contains attrs.");
 740
 741   AttrVec &AttrBlank = Ctx.getDeclAttrs(this);
 742   assert(AttrBlank.empty() && "HasAttrs was wrong?");
 743
 744   AttrBlank = attrs;
 745   HasAttrs = true;
 746 }
 747
 748 void Decl::dropAttrs() {
 749   if (!HasAttrs) return;
 750
 751   HasAttrs = false;
 752   getASTContext().eraseDeclAttrs(this);
 753 }
 754
 755 const AttrVec &Decl::getAttrs() const {
 756   assert(HasAttrs && "No attrs to get!");
 757   return getASTContext().getDeclAttrs(this);
 758 }
 759
 760 Decl *Decl::castFromDeclContext (const DeclContext *D) {
 761   Decl::Kind DK = D->getDeclKind();
 762   switch(DK) {
 763 #define DECL(NAME, BASE)
 764 #define DECL_CONTEXT(NAME) \
 765     case Decl::NAME:       \
 766       return static_cast<NAME##Decl*>(const_cast<DeclContext*>(D));
 767 #define DECL_CONTEXT_BASE(NAME)
 768 #include "clang/AST/DeclNodes.inc"
 769     default:
 770 #define DECL(NAME, BASE)
 771 #define DECL_CONTEXT_BASE(NAME)                  \
 772       if (DK >= first##NAME && DK <= last##NAME) \
 773         return static_cast<NAME##Decl*>(const_cast<DeclContext*>(D));
 774 #include "clang/AST/DeclNodes.inc"
 775       llvm_unreachable("a decl that inherits DeclContext isn't handled");
 776   }
 777 }
 778
 779 DeclContext *Decl::castToDeclContext(const Decl *D) {
 780   Decl::Kind DK = D->getKind();
 781   switch(DK) {
 782 #define DECL(NAME, BASE)
 783 #define DECL_CONTEXT(NAME) \
 784     case Decl::NAME:       \
 785       return static_cast<NAME##Decl*>(const_cast<Decl*>(D));
 786 #define DECL_CONTEXT_BASE(NAME)
 787 #include "clang/AST/DeclNodes.inc"
 788     default:
 789 #define DECL(NAME, BASE)
 790 #define DECL_CONTEXT_BASE(NAME)                                   \
 791       if (DK >= first##NAME && DK <= last##NAME)                  \
 792         return static_cast<NAME##Decl*>(const_cast<Decl*>(D));
 793 #include "clang/AST/DeclNodes.inc"
 794       llvm_unreachable("a decl that inherits DeclContext isn't handled");
 795   }
 796 }
 797
 798 SourceLocation Decl::getBodyRBrace() const {
 799   // Special handling of FunctionDecl to avoid de-serializing the body from PCH.
 800   // FunctionDecl stores EndRangeLoc for this purpose.
 801   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(this)) {
 802     const FunctionDecl *Definition;
 803     if (FD->hasBody(Definition))
 804       return Definition->getSourceRange().getEnd();
 805     return SourceLocation();
 806   }
 807
 808   if (Stmt *Body = getBody())
 809     return Body->getSourceRange().getEnd();
 810
 811   return SourceLocation();
 812 }
 813
 814 bool Decl::AccessDeclContextSanity() const {
 815 #ifndef NDEBUG
 816   // Suppress this check if any of the following hold:
 817   // 1. this is the translation unit (and thus has no parent)
 818   // 2. this is a template parameter (and thus doesn't belong to its context)
 819   // 3. this is a non-type template parameter
 820   // 4. the context is not a record
 821   // 5. it's invalid
 822   // 6. it's a C++0x static_assert.
 823   if (isa<TranslationUnitDecl>(this) ||
 824       isa<TemplateTypeParmDecl>(this) ||
 825       isa<NonTypeTemplateParmDecl>(this) ||
 826       !isa<CXXRecordDecl>(getDeclContext()) ||
 827       isInvalidDecl() ||
 828       isa<StaticAssertDecl>(this) ||
 829       // FIXME: a ParmVarDecl can have ClassTemplateSpecialization
 830       // as DeclContext (?).
 831       isa<ParmVarDecl>(this) ||
 832       // FIXME: a ClassTemplateSpecialization or CXXRecordDecl can have
 833       // AS_none as access specifier.
 834       isa<CXXRecordDecl>(this) ||
 835       isa<ClassScopeFunctionSpecializationDecl>(this))
 836     return true;
 837
 838   assert(Access != AS_none &&
 839          "Access specifier is AS_none inside a record decl");
 840 #endif
 841   return true;
 842 }
 843
 844 static Decl::Kind getKind(const Decl *D) { return D->getKind(); }
 845 static Decl::Kind getKind(const DeclContext *DC) { return DC->getDeclKind(); }
 846
 847 const FunctionType *Decl::getFunctionType(bool BlocksToo) const {
 848   QualType Ty;
 849   if (const ValueDecl *D = dyn_cast<ValueDecl>(this))
 850     Ty = D->getType();
 851   else if (const TypedefNameDecl *D = dyn_cast<TypedefNameDecl>(this))
 852     Ty = D->getUnderlyingType();
 853   else
 854     return nullptr;
 855
 856   if (Ty->isFunctionPointerType())
 857     Ty = Ty->getAs<PointerType>()->getPointeeType();
 858   else if (BlocksToo && Ty->isBlockPointerType())
 859     Ty = Ty->getAs<BlockPointerType>()->getPointeeType();
 860
 861   return Ty->getAs<FunctionType>();
 862 }
 863
 864
 865 /// Starting at a given context (a Decl or DeclContext), look for a
 866 /// code context that is not a closure (a lambda, block, etc.).
 867 template <class T> static Decl *getNonClosureContext(T *D) {
 868   if (getKind(D) == Decl::CXXMethod) {
 869     CXXMethodDecl *MD = cast<CXXMethodDecl>(D);
 870     if (MD->getOverloadedOperator() == OO_Call &&
 871         MD->getParent()->isLambda())
 872       return getNonClosureContext(MD->getParent()->getParent());
 873     return MD;
 874   } else if (FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
 875     return FD;
 876   } else if (ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
 877     return MD;
 878   } else if (BlockDecl *BD = dyn_cast<BlockDecl>(D)) {
 879     return getNonClosureContext(BD->getParent());
 880   } else if (CapturedDecl *CD = dyn_cast<CapturedDecl>(D)) {
 881     return getNonClosureContext(CD->getParent());
 882   } else {
 883     return nullptr;
 884   }
 885 }
 886
 887 Decl *Decl::getNonClosureContext() {
 888   return ::getNonClosureContext(this);
 889 }
 890
 891 Decl *DeclContext::getNonClosureAncestor() {
 892   return ::getNonClosureContext(this);
 893 }
 894
 895 //===----------------------------------------------------------------------===//
 896 // DeclContext Implementation
 897 //===----------------------------------------------------------------------===//
 898
 899 bool DeclContext::classof(const Decl *D) {
 900   switch (D->getKind()) {
 901 #define DECL(NAME, BASE)
 902 #define DECL_CONTEXT(NAME) case Decl::NAME:
 903 #define DECL_CONTEXT_BASE(NAME)
 904 #include "clang/AST/DeclNodes.inc"
 905       return true;
 906     default:
 907 #define DECL(NAME, BASE)
 908 #define DECL_CONTEXT_BASE(NAME)                 \
 909       if (D->getKind() >= Decl::first##NAME &&  \
 910           D->getKind() <= Decl::last##NAME)     \
 911         return true;
 912 #include "clang/AST/DeclNodes.inc"
 913       return false;
 914   }
 915 }
 916
 917 DeclContext::~DeclContext() { }
 918
 919 /// \brief Find the parent context of this context that will be
 920 /// used for unqualified name lookup.
 921 ///
 922 /// Generally, the parent lookup context is the semantic context. However, for
 923 /// a friend function the parent lookup context is the lexical context, which
 924 /// is the class in which the friend is declared.
 925 DeclContext *DeclContext::getLookupParent() {
 926   // FIXME: Find a better way to identify friends
 927   if (isa<FunctionDecl>(this))
 928     if (getParent()->getRedeclContext()->isFileContext() &&
 929         getLexicalParent()->getRedeclContext()->isRecord())
 930       return getLexicalParent();
 931
 932   return getParent();
 933 }
 934
 935 bool DeclContext::isInlineNamespace() const {
 936   return isNamespace() &&
 937          cast<NamespaceDecl>(this)->isInline();
 938 }
 939
 940 bool DeclContext::isStdNamespace() const {
 941   if (!isNamespace())
 942     return false;
 943
 944   const NamespaceDecl *ND = cast<NamespaceDecl>(this);
 945   if (ND->isInline()) {
 946     return ND->getParent()->isStdNamespace();
 947   }
 948
 949   if (!getParent()->getRedeclContext()->isTranslationUnit())
 950     return false;
 951
 952   const IdentifierInfo *II = ND->getIdentifier();
 953   return II && II->isStr("std");
 954 }
 955
 956 bool DeclContext::isDependentContext() const {
 957   if (isFileContext())
 958     return false;
 959
 960   if (isa<ClassTemplatePartialSpecializationDecl>(this))
 961     return true;
 962
 963   if (const CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(this)) {
 964     if (Record->getDescribedClassTemplate())
 965       return true;
 966
 967     if (Record->isDependentLambda())
 968       return true;
 969   }
 970
 971   if (const FunctionDecl *Function = dyn_cast<FunctionDecl>(this)) {
 972     if (Function->getDescribedFunctionTemplate())
 973       return true;
 974
 975     // Friend function declarations are dependent if their *lexical*
 976     // context is dependent.
 977     if (cast<Decl>(this)->getFriendObjectKind())
 978       return getLexicalParent()->isDependentContext();
 979   }
 980
 981   // FIXME: A variable template is a dependent context, but is not a
 982   // DeclContext. A context within it (such as a lambda-expression)
 983   // should be considered dependent.
 984
 985   return getParent() && getParent()->isDependentContext();
 986 }
 987
 988 bool DeclContext::isTransparentContext() const {
 989   if (DeclKind == Decl::Enum)
 990     return !cast<EnumDecl>(this)->isScoped();
 991   else if (DeclKind == Decl::LinkageSpec || DeclKind == Decl::Export)
 992     return true;
 993
 994   return false;
 995 }
 996
 997 static bool isLinkageSpecContext(const DeclContext *DC,
 998                                  LinkageSpecDecl::LanguageIDs ID) {
 999   while (DC->getDeclKind() != Decl::TranslationUnit) {
1000     if (DC->getDeclKind() == Decl::LinkageSpec)
1001       return cast<LinkageSpecDecl>(DC)->getLanguage() == ID;
1002     DC = DC->getLexicalParent();
1003   }
1004   return false;
1005 }
1006
1007 bool DeclContext::isExternCContext() const {
1008   return isLinkageSpecContext(this, clang::LinkageSpecDecl::lang_c);
1009 }
1010
1011 const LinkageSpecDecl *DeclContext::getExternCContext() const {
1012   const DeclContext *DC = this;
1013   while (DC->getDeclKind() != Decl::TranslationUnit) {
1014     if (DC->getDeclKind() == Decl::LinkageSpec &&
1015         cast<LinkageSpecDecl>(DC)->getLanguage() ==
1016             clang::LinkageSpecDecl::lang_c)
1017       return cast<LinkageSpecDecl>(DC);
1018     DC = DC->getLexicalParent();
1019   }
1020   return nullptr;
1021 }
1022
1023 bool DeclContext::isExternCXXContext() const {
1024   return isLinkageSpecContext(this, clang::LinkageSpecDecl::lang_cxx);
1025 }
1026
1027 bool DeclContext::Encloses(const DeclContext *DC) const {
1028   if (getPrimaryContext() != this)
1029     return getPrimaryContext()->Encloses(DC);
1030
1031   for (; DC; DC = DC->getParent())
1032     if (DC->getPrimaryContext() == this)
1033       return true;
1034   return false;
1035 }
1036
1037 DeclContext *DeclContext::getPrimaryContext() {
1038   switch (DeclKind) {
1039   case Decl::TranslationUnit:
1040   case Decl::ExternCContext:
1041   case Decl::LinkageSpec:
1042   case Decl::Export:
1043   case Decl::Block:
1044   case Decl::Captured:
1045   case Decl::OMPDeclareReduction:
1046     // There is only one DeclContext for these entities.
1047     return this;
1048
1049   case Decl::Namespace:
1050     // The original namespace is our primary context.
1051     return static_cast<NamespaceDecl*>(this)->getOriginalNamespace();
1052
1053   case Decl::ObjCMethod:
1054     return this;
1055
1056   case Decl::ObjCInterface:
1057     if (ObjCInterfaceDecl *Def = cast<ObjCInterfaceDecl>(this)->getDefinition())
1058       return Def;
1059
1060     return this;
1061
1062   case Decl::ObjCProtocol:
1063     if (ObjCProtocolDecl *Def = cast<ObjCProtocolDecl>(this)->getDefinition())
1064       return Def;
1065
1066     return this;
1067
1068   case Decl::ObjCCategory:
1069     return this;
1070
1071   case Decl::ObjCImplementation:
1072   case Decl::ObjCCategoryImpl:
1073     return this;
1074
1075   default:
1076     if (DeclKind >= Decl::firstTag && DeclKind <= Decl::lastTag) {
1077       // If this is a tag type that has a definition or is currently
1078       // being defined, that definition is our primary context.
1079       TagDecl *Tag = cast<TagDecl>(this);
1080
1081       if (TagDecl *Def = Tag->getDefinition())
1082         return Def;
1083
1084       if (const TagType *TagTy = dyn_cast<TagType>(Tag->getTypeForDecl())) {
1085         // Note, TagType::getDecl returns the (partial) definition one exists.
1086         TagDecl *PossiblePartialDef = TagTy->getDecl();
1087         if (PossiblePartialDef->isBeingDefined())
1088           return PossiblePartialDef;
1089       } else {
1090         assert(isa<InjectedClassNameType>(Tag->getTypeForDecl()));
1091       }
1092
1093       return Tag;
1094     }
1095
1096     assert(DeclKind >= Decl::firstFunction && DeclKind <= Decl::lastFunction &&
1097           "Unknown DeclContext kind");
1098     return this;
1099   }
1100 }
1101
1102 void
1103 DeclContext::collectAllContexts(SmallVectorImpl<DeclContext *> &Contexts){
1104   Contexts.clear();
1105
1106   if (DeclKind != Decl::Namespace) {
1107     Contexts.push_back(this);
1108     return;
1109   }
1110
1111   NamespaceDecl *Self = static_cast<NamespaceDecl *>(this);
1112   for (NamespaceDecl *N = Self->getMostRecentDecl(); N;
1113        N = N->getPreviousDecl())
1114     Contexts.push_back(N);
1115
1116   std::reverse(Contexts.begin(), Contexts.end());
1117 }
1118
1119 std::pair<Decl *, Decl *>
1120 DeclContext::BuildDeclChain(ArrayRef<Decl*> Decls,
1121                             bool FieldsAlreadyLoaded) {
1122   // Build up a chain of declarations via the Decl::NextInContextAndBits field.
1123   Decl *FirstNewDecl = nullptr;
1124   Decl *PrevDecl = nullptr;
1125   for (unsigned I = 0, N = Decls.size(); I != N; ++I) {
1126     if (FieldsAlreadyLoaded && isa<FieldDecl>(Decls[I]))
1127       continue;
1128
1129     Decl *D = Decls[I];
1130     if (PrevDecl)
1131       PrevDecl->NextInContextAndBits.setPointer(D);
1132     else
1133       FirstNewDecl = D;
1134
1135     PrevDecl = D;
1136   }
1137
1138   return std::make_pair(FirstNewDecl, PrevDecl);
1139 }
1140
1141 /// \brief We have just acquired external visible storage, and we already have
1142 /// built a lookup map. For every name in the map, pull in the new names from
1143 /// the external storage.
1144 void DeclContext::reconcileExternalVisibleStorage() const {
1145   assert(NeedToReconcileExternalVisibleStorage && LookupPtr);
1146   NeedToReconcileExternalVisibleStorage = false;
1147
1148   for (auto &Lookup : *LookupPtr)
1149     Lookup.second.setHasExternalDecls();
1150 }
1151
1152 /// \brief Load the declarations within this lexical storage from an
1153 /// external source.
1154 /// \return \c true if any declarations were added.
1155 bool
1156 DeclContext::LoadLexicalDeclsFromExternalStorage() const {
1157   ExternalASTSource *Source = getParentASTContext().getExternalSource();
1158   assert(hasExternalLexicalStorage() && Source && "No external storage?");
1159
1160   // Notify that we have a DeclContext that is initializing.
1161   ExternalASTSource::Deserializing ADeclContext(Source);
1162
1163   // Load the external declarations, if any.
1164   SmallVector<Decl*, 64> Decls;
1165   ExternalLexicalStorage = false;
1166   Source->FindExternalLexicalDecls(this, Decls);
1167
1168   if (Decls.empty())
1169     return false;
1170
1171   // We may have already loaded just the fields of this record, in which case
1172   // we need to ignore them.
1173   bool FieldsAlreadyLoaded = false;
1174   if (const RecordDecl *RD = dyn_cast<RecordDecl>(this))
1175     FieldsAlreadyLoaded = RD->LoadedFieldsFromExternalStorage;
1176
1177   // Splice the newly-read declarations into the beginning of the list
1178   // of declarations.
1179   Decl *ExternalFirst, *ExternalLast;
1180   std::tie(ExternalFirst, ExternalLast) =
1181       BuildDeclChain(Decls, FieldsAlreadyLoaded);
1182   ExternalLast->NextInContextAndBits.setPointer(FirstDecl);
1183   FirstDecl = ExternalFirst;
1184   if (!LastDecl)
1185     LastDecl = ExternalLast;
1186   return true;
1187 }
1188
1189 DeclContext::lookup_result
1190 ExternalASTSource::SetNoExternalVisibleDeclsForName(const DeclContext *DC,
1191                                                     DeclarationName Name) {
1192   ASTContext &Context = DC->getParentASTContext();
1193   StoredDeclsMap *Map;
1194   if (!(Map = DC->LookupPtr))
1195     Map = DC->CreateStoredDeclsMap(Context);
1196   if (DC->NeedToReconcileExternalVisibleStorage)
1197     DC->reconcileExternalVisibleStorage();
1198
1199   (*Map)[Name].removeExternalDecls();
1200
1201   return DeclContext::lookup_result();
1202 }
1203
1204 DeclContext::lookup_result
1205 ExternalASTSource::SetExternalVisibleDeclsForName(const DeclContext *DC,
1206                                                   DeclarationName Name,
1207                                                   ArrayRef<NamedDecl*> Decls) {
1208   ASTContext &Context = DC->getParentASTContext();
1209   StoredDeclsMap *Map;
1210   if (!(Map = DC->LookupPtr))
1211     Map = DC->CreateStoredDeclsMap(Context);
1212   if (DC->NeedToReconcileExternalVisibleStorage)
1213     DC->reconcileExternalVisibleStorage();
1214
1215   StoredDeclsList &List = (*Map)[Name];
1216
1217   // Clear out any old external visible declarations, to avoid quadratic
1218   // performance in the redeclaration checks below.
1219   List.removeExternalDecls();
1220
1221   if (!List.isNull()) {
1222     // We have both existing declarations and new declarations for this name.
1223     // Some of the declarations may simply replace existing ones. Handle those
1224     // first.
1225     llvm::SmallVector<unsigned, 8> Skip;
1226     for (unsigned I = 0, N = Decls.size(); I != N; ++I)
1227       if (List.HandleRedeclaration(Decls[I], /*IsKnownNewer*/false))
1228         Skip.push_back(I);
1229     Skip.push_back(Decls.size());
1230
1231     // Add in any new declarations.
1232     unsigned SkipPos = 0;
1233     for (unsigned I = 0, N = Decls.size(); I != N; ++I) {
1234       if (I == Skip[SkipPos])
1235         ++SkipPos;
1236       else
1237         List.AddSubsequentDecl(Decls[I]);
1238     }
1239   } else {
1240     // Convert the array to a StoredDeclsList.
1241     for (ArrayRef<NamedDecl*>::iterator
1242            I = Decls.begin(), E = Decls.end(); I != E; ++I) {
1243       if (List.isNull())
1244         List.setOnlyValue(*I);
1245       else
1246         List.AddSubsequentDecl(*I);
1247     }
1248   }
1249
1250   return List.getLookupResult();
1251 }
1252
1253 DeclContext::decl_iterator DeclContext::decls_begin() const {
1254   if (hasExternalLexicalStorage())
1255     LoadLexicalDeclsFromExternalStorage();
1256   return decl_iterator(FirstDecl);
1257 }
1258
1259 bool DeclContext::decls_empty() const {
1260   if (hasExternalLexicalStorage())
1261     LoadLexicalDeclsFromExternalStorage();
1262
1263   return !FirstDecl;
1264 }
1265
1266 bool DeclContext::containsDecl(Decl *D) const {
1267   return (D->getLexicalDeclContext() == this &&
1268           (D->NextInContextAndBits.getPointer() || D == LastDecl));
1269 }
1270
1271 void DeclContext::removeDecl(Decl *D) {
1272   assert(D->getLexicalDeclContext() == this &&
1273          "decl being removed from non-lexical context");
1274   assert((D->NextInContextAndBits.getPointer() || D == LastDecl) &&
1275          "decl is not in decls list");
1276
1277   // Remove D from the decl chain.  This is O(n) but hopefully rare.
1278   if (D == FirstDecl) {
1279     if (D == LastDecl)
1280       FirstDecl = LastDecl = nullptr;
1281     else
1282       FirstDecl = D->NextInContextAndBits.getPointer();
1283   } else {
1284     for (Decl *I = FirstDecl; true; I = I->NextInContextAndBits.getPointer()) {
1285       assert(I && "decl not found in linked list");
1286       if (I->NextInContextAndBits.getPointer() == D) {
1287         I->NextInContextAndBits.setPointer(D->NextInContextAndBits.getPointer());
1288         if (D == LastDecl) LastDecl = I;
1289         break;
1290       }
1291     }
1292   }
1293
1294   // Mark that D is no longer in the decl chain.
1295   D->NextInContextAndBits.setPointer(nullptr);
1296
1297   // Remove D from the lookup table if necessary.
1298   if (isa<NamedDecl>(D)) {
1299     NamedDecl *ND = cast<NamedDecl>(D);
1300
1301     // Remove only decls that have a name
1302     if (!ND->getDeclName()) return;
1303
1304     auto *DC = this;
1305     do {
1306       StoredDeclsMap *Map = DC->getPrimaryContext()->LookupPtr;
1307       if (Map) {
1308         StoredDeclsMap::iterator Pos = Map->find(ND->getDeclName());
1309         assert(Pos != Map->end() && "no lookup entry for decl");
1310         if (Pos->second.getAsVector() || Pos->second.getAsDecl() == ND)
1311           Pos->second.remove(ND);
1312       }
1313     } while (DC->isTransparentContext() && (DC = DC->getParent()));
1314   }
1315 }
1316
1317 void DeclContext::addHiddenDecl(Decl *D) {
1318   assert(D->getLexicalDeclContext() == this &&
1319          "Decl inserted into wrong lexical context");
1320   assert(!D->getNextDeclInContext() && D != LastDecl &&
1321          "Decl already inserted into a DeclContext");
1322
1323   if (FirstDecl) {
1324     LastDecl->NextInContextAndBits.setPointer(D);
1325     LastDecl = D;
1326   } else {
1327     FirstDecl = LastDecl = D;
1328   }
1329
1330   // Notify a C++ record declaration that we've added a member, so it can
1331   // update its class-specific state.
1332   if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(this))
1333     Record->addedMember(D);
1334
1335   // If this is a newly-created (not de-serialized) import declaration, wire
1336   // it in to the list of local import declarations.
1337   if (!D->isFromASTFile()) {
1338     if (ImportDecl *Import = dyn_cast<ImportDecl>(D))
1339       D->getASTContext().addedLocalImportDecl(Import);
1340   }
1341 }
1342
1343 void DeclContext::addDecl(Decl *D) {
1344   addHiddenDecl(D);
1345
1346   if (NamedDecl *ND = dyn_cast<NamedDecl>(D))
1347     ND->getDeclContext()->getPrimaryContext()->
1348         makeDeclVisibleInContextWithFlags(ND, false, true);
1349 }
1350
1351 void DeclContext::addDeclInternal(Decl *D) {
1352   addHiddenDecl(D);
1353
1354   if (NamedDecl *ND = dyn_cast<NamedDecl>(D))
1355     ND->getDeclContext()->getPrimaryContext()->
1356         makeDeclVisibleInContextWithFlags(ND, true, true);
1357 }
1358
1359 /// shouldBeHidden - Determine whether a declaration which was declared
1360 /// within its semantic context should be invisible to qualified name lookup.
1361 static bool shouldBeHidden(NamedDecl *D) {
1362   // Skip unnamed declarations.
1363   if (!D->getDeclName())
1364     return true;
1365
1366   // Skip entities that can't be found by name lookup into a particular
1367   // context.
1368   if ((D->getIdentifierNamespace() == 0 && !isa<UsingDirectiveDecl>(D)) ||
1369       D->isTemplateParameter())
1370     return true;
1371
1372   // Skip template specializations.
1373   // FIXME: This feels like a hack. Should DeclarationName support
1374   // template-ids, or is there a better way to keep specializations
1375   // from being visible?
1376   if (isa<ClassTemplateSpecializationDecl>(D))
1377     return true;
1378   if (FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
1379     if (FD->isFunctionTemplateSpecialization())
1380       return true;
1381
1382   return false;
1383 }
1384
1385 /// buildLookup - Build the lookup data structure with all of the
1386 /// declarations in this DeclContext (and any other contexts linked
1387 /// to it or transparent contexts nested within it) and return it.
1388 ///
1389 /// Note that the produced map may miss out declarations from an
1390 /// external source. If it does, those entries will be marked with
1391 /// the 'hasExternalDecls' flag.
1392 StoredDeclsMap *DeclContext::buildLookup() {
1393   assert(this == getPrimaryContext() && "buildLookup called on non-primary DC");
1394
1395   if (!HasLazyLocalLexicalLookups && !HasLazyExternalLexicalLookups)
1396     return LookupPtr;
1397
1398   SmallVector<DeclContext *, 2> Contexts;
1399   collectAllContexts(Contexts);
1400
1401   if (HasLazyExternalLexicalLookups) {
1402     HasLazyExternalLexicalLookups = false;
1403     for (auto *DC : Contexts) {
1404       if (DC->hasExternalLexicalStorage())
1405         HasLazyLocalLexicalLookups |=
1406             DC->LoadLexicalDeclsFromExternalStorage();
1407     }
1408
1409     if (!HasLazyLocalLexicalLookups)
1410       return LookupPtr;
1411   }
1412
1413   for (auto *DC : Contexts)
1414     buildLookupImpl(DC, hasExternalVisibleStorage());
1415
1416   // We no longer have any lazy decls.
1417   HasLazyLocalLexicalLookups = false;
1418   return LookupPtr;
1419 }
1420
1421 /// buildLookupImpl - Build part of the lookup data structure for the
1422 /// declarations contained within DCtx, which will either be this
1423 /// DeclContext, a DeclContext linked to it, or a transparent context
1424 /// nested within it.
1425 void DeclContext::buildLookupImpl(DeclContext *DCtx, bool Internal) {
1426   for (Decl *D : DCtx->noload_decls()) {
1427     // Insert this declaration into the lookup structure, but only if
1428     // it's semantically within its decl context. Any other decls which
1429     // should be found in this context are added eagerly.
1430     //
1431     // If it's from an AST file, don't add it now. It'll get handled by
1432     // FindExternalVisibleDeclsByName if needed. Exception: if we're not
1433     // in C++, we do not track external visible decls for the TU, so in
1434     // that case we need to collect them all here.
1435     if (NamedDecl *ND = dyn_cast<NamedDecl>(D))
1436       if (ND->getDeclContext() == DCtx && !shouldBeHidden(ND) &&
1437           (!ND->isFromASTFile() ||
1438            (isTranslationUnit() &&
1439             !getParentASTContext().getLangOpts().CPlusPlus)))
1440         makeDeclVisibleInContextImpl(ND, Internal);
1441
1442     // If this declaration is itself a transparent declaration context
1443     // or inline namespace, add the members of this declaration of that
1444     // context (recursively).
1445     if (DeclContext *InnerCtx = dyn_cast<DeclContext>(D))
1446       if (InnerCtx->isTransparentContext() || InnerCtx->isInlineNamespace())
1447         buildLookupImpl(InnerCtx, Internal);
1448   }
1449 }
1450
1451 NamedDecl *const DeclContextLookupResult::SingleElementDummyList = nullptr;
1452
1453 DeclContext::lookup_result
1454 DeclContext::lookup(DeclarationName Name) const {
1455   assert(DeclKind != Decl::LinkageSpec && DeclKind != Decl::Export &&
1456          "should not perform lookups into transparent contexts");
1457
1458   const DeclContext *PrimaryContext = getPrimaryContext();
1459   if (PrimaryContext != this)
1460     return PrimaryContext->lookup(Name);
1461
1462   // If we have an external source, ensure that any later redeclarations of this
1463   // context have been loaded, since they may add names to the result of this
1464   // lookup (or add external visible storage).
1465   ExternalASTSource *Source = getParentASTContext().getExternalSource();
1466   if (Source)
1467     (void)cast<Decl>(this)->getMostRecentDecl();
1468
1469   if (hasExternalVisibleStorage()) {
1470     assert(Source && "external visible storage but no external source?");
1471
1472     if (NeedToReconcileExternalVisibleStorage)
1473       reconcileExternalVisibleStorage();
1474
1475     StoredDeclsMap *Map = LookupPtr;
1476
1477     if (HasLazyLocalLexicalLookups || HasLazyExternalLexicalLookups)
1478       // FIXME: Make buildLookup const?
1479       Map = const_cast<DeclContext*>(this)->buildLookup();
1480
1481     if (!Map)
1482       Map = CreateStoredDeclsMap(getParentASTContext());
1483
1484     // If we have a lookup result with no external decls, we are done.
1485     std::pair<StoredDeclsMap::iterator, bool> R =
1486         Map->insert(std::make_pair(Name, StoredDeclsList()));
1487     if (!R.second && !R.first->second.hasExternalDecls())
1488       return R.first->second.getLookupResult();
1489
1490     if (Source->FindExternalVisibleDeclsByName(this, Name) || !R.second) {
1491       if (StoredDeclsMap *Map = LookupPtr) {
1492         StoredDeclsMap::iterator I = Map->find(Name);
1493         if (I != Map->end())
1494           return I->second.getLookupResult();
1495       }
1496     }
1497
1498     return lookup_result();
1499   }
1500
1501   StoredDeclsMap *Map = LookupPtr;
1502   if (HasLazyLocalLexicalLookups || HasLazyExternalLexicalLookups)
1503     Map = const_cast<DeclContext*>(this)->buildLookup();
1504
1505   if (!Map)
1506     return lookup_result();
1507
1508   StoredDeclsMap::iterator I = Map->find(Name);
1509   if (I == Map->end())
1510     return lookup_result();
1511
1512   return I->second.getLookupResult();
1513 }
1514
1515 DeclContext::lookup_result
1516 DeclContext::noload_lookup(DeclarationName Name) {
1517   assert(DeclKind != Decl::LinkageSpec && DeclKind != Decl::Export &&
1518          "should not perform lookups into transparent contexts");
1519
1520   DeclContext *PrimaryContext = getPrimaryContext();
1521   if (PrimaryContext != this)
1522     return PrimaryContext->noload_lookup(Name);
1523
1524   // If we have any lazy lexical declarations not in our lookup map, add them
1525   // now. Don't import any external declarations, not even if we know we have
1526   // some missing from the external visible lookups.
1527   if (HasLazyLocalLexicalLookups) {
1528     SmallVector<DeclContext *, 2> Contexts;
1529     collectAllContexts(Contexts);
1530     for (unsigned I = 0, N = Contexts.size(); I != N; ++I)
1531       buildLookupImpl(Contexts[I], hasExternalVisibleStorage());
1532     HasLazyLocalLexicalLookups = false;
1533   }
1534
1535   StoredDeclsMap *Map = LookupPtr;
1536   if (!Map)
1537     return lookup_result();
1538
1539   StoredDeclsMap::iterator I = Map->find(Name);
1540   return I != Map->end() ? I->second.getLookupResult()
1541                          : lookup_result();
1542 }
1543
1544 void DeclContext::localUncachedLookup(DeclarationName Name,
1545                                       SmallVectorImpl<NamedDecl *> &Results) {
1546   Results.clear();
1547
1548   // If there's no external storage, just perform a normal lookup and copy
1549   // the results.
1550   if (!hasExternalVisibleStorage() && !hasExternalLexicalStorage() && Name) {
1551     lookup_result LookupResults = lookup(Name);
1552     Results.insert(Results.end(), LookupResults.begin(), LookupResults.end());
1553     return;
1554   }
1555
1556   // If we have a lookup table, check there first. Maybe we'll get lucky.
1557   // FIXME: Should we be checking these flags on the primary context?
1558   if (Name && !HasLazyLocalLexicalLookups && !HasLazyExternalLexicalLookups) {
1559     if (StoredDeclsMap *Map = LookupPtr) {
1560       StoredDeclsMap::iterator Pos = Map->find(Name);
1561       if (Pos != Map->end()) {
1562         Results.insert(Results.end(),
1563                        Pos->second.getLookupResult().begin(),
1564                        Pos->second.getLookupResult().end());
1565         return;
1566       }
1567     }
1568   }
1569
1570   // Slow case: grovel through the declarations in our chain looking for
1571   // matches.
1572   // FIXME: If we have lazy external declarations, this will not find them!
1573   // FIXME: Should we CollectAllContexts and walk them all here?
1574   for (Decl *D = FirstDecl; D; D = D->getNextDeclInContext()) {
1575     if (NamedDecl *ND = dyn_cast<NamedDecl>(D))
1576       if (ND->getDeclName() == Name)
1577         Results.push_back(ND);
1578   }
1579 }
1580
1581 DeclContext *DeclContext::getRedeclContext() {
1582   DeclContext *Ctx = this;
1583   // Skip through transparent contexts.
1584   while (Ctx->isTransparentContext())
1585     Ctx = Ctx->getParent();
1586   return Ctx;
1587 }
1588
1589 DeclContext *DeclContext::getEnclosingNamespaceContext() {
1590   DeclContext *Ctx = this;
1591   // Skip through non-namespace, non-translation-unit contexts.
1592   while (!Ctx->isFileContext())
1593     Ctx = Ctx->getParent();
1594   return Ctx->getPrimaryContext();
1595 }
1596
1597 RecordDecl *DeclContext::getOuterLexicalRecordContext() {
1598   // Loop until we find a non-record context.
1599   RecordDecl *OutermostRD = nullptr;
1600   DeclContext *DC = this;
1601   while (DC->isRecord()) {
1602     OutermostRD = cast<RecordDecl>(DC);
1603     DC = DC->getLexicalParent();
1604   }
1605   return OutermostRD;
1606 }
1607
1608 bool DeclContext::InEnclosingNamespaceSetOf(const DeclContext *O) const {
1609   // For non-file contexts, this is equivalent to Equals.
1610   if (!isFileContext())
1611     return O->Equals(this);
1612
1613   do {
1614     if (O->Equals(this))
1615       return true;
1616
1617     const NamespaceDecl *NS = dyn_cast<NamespaceDecl>(O);
1618     if (!NS || !NS->isInline())
1619       break;
1620     O = NS->getParent();
1621   } while (O);
1622
1623   return false;
1624 }
1625
1626 void DeclContext::makeDeclVisibleInContext(NamedDecl *D) {
1627   DeclContext *PrimaryDC = this->getPrimaryContext();
1628   DeclContext *DeclDC = D->getDeclContext()->getPrimaryContext();
1629   // If the decl is being added outside of its semantic decl context, we
1630   // need to ensure that we eagerly build the lookup information for it.
1631   PrimaryDC->makeDeclVisibleInContextWithFlags(D, false, PrimaryDC == DeclDC);
1632 }
1633
1634 void DeclContext::makeDeclVisibleInContextWithFlags(NamedDecl *D, bool Internal,
1635                                                     bool Recoverable) {
1636   assert(this == getPrimaryContext() && "expected a primary DC");
1637
1638   if (!isLookupContext()) {
1639     if (isTransparentContext())
1640       getParent()->getPrimaryContext()
1641         ->makeDeclVisibleInContextWithFlags(D, Internal, Recoverable);
1642     return;
1643   }
1644
1645   // Skip declarations which should be invisible to name lookup.
1646   if (shouldBeHidden(D))
1647     return;
1648
1649   // If we already have a lookup data structure, perform the insertion into
1650   // it. If we might have externally-stored decls with this name, look them
1651   // up and perform the insertion. If this decl was declared outside its
1652   // semantic context, buildLookup won't add it, so add it now.
1653   //
1654   // FIXME: As a performance hack, don't add such decls into the translation
1655   // unit unless we're in C++, since qualified lookup into the TU is never
1656   // performed.
1657   if (LookupPtr || hasExternalVisibleStorage() ||
1658       ((!Recoverable || D->getDeclContext() != D->getLexicalDeclContext()) &&
1659        (getParentASTContext().getLangOpts().CPlusPlus ||
1660         !isTranslationUnit()))) {
1661     // If we have lazily omitted any decls, they might have the same name as
1662     // the decl which we are adding, so build a full lookup table before adding
1663     // this decl.
1664     buildLookup();
1665     makeDeclVisibleInContextImpl(D, Internal);
1666   } else {
1667     HasLazyLocalLexicalLookups = true;
1668   }
1669
1670   // If we are a transparent context or inline namespace, insert into our
1671   // parent context, too. This operation is recursive.
1672   if (isTransparentContext() || isInlineNamespace())
1673     getParent()->getPrimaryContext()->
1674         makeDeclVisibleInContextWithFlags(D, Internal, Recoverable);
1675
1676   Decl *DCAsDecl = cast<Decl>(this);
1677   // Notify that a decl was made visible unless we are a Tag being defined.
1678   if (!(isa<TagDecl>(DCAsDecl) && cast<TagDecl>(DCAsDecl)->isBeingDefined()))
1679     if (ASTMutationListener *L = DCAsDecl->getASTMutationListener())
1680       L->AddedVisibleDecl(this, D);
1681 }
1682
1683 void DeclContext::makeDeclVisibleInContextImpl(NamedDecl *D, bool Internal) {
1684   // Find or create the stored declaration map.
1685   StoredDeclsMap *Map = LookupPtr;
1686   if (!Map) {
1687     ASTContext *C = &getParentASTContext();
1688     Map = CreateStoredDeclsMap(*C);
1689   }
1690
1691   // If there is an external AST source, load any declarations it knows about
1692   // with this declaration's name.
1693   // If the lookup table contains an entry about this name it means that we
1694   // have already checked the external source.
1695   if (!Internal)
1696     if (ExternalASTSource *Source = getParentASTContext().getExternalSource())
1697       if (hasExternalVisibleStorage() &&
1698           Map->find(D->getDeclName()) == Map->end())
1699         Source->FindExternalVisibleDeclsByName(this, D->getDeclName());
1700
1701   // Insert this declaration into the map.
1702   StoredDeclsList &DeclNameEntries = (*Map)[D->getDeclName()];
1703
1704   if (Internal) {
1705     // If this is being added as part of loading an external declaration,
1706     // this may not be the only external declaration with this name.
1707     // In this case, we never try to replace an existing declaration; we'll
1708     // handle that when we finalize the list of declarations for this name.
1709     DeclNameEntries.setHasExternalDecls();
1710     DeclNameEntries.AddSubsequentDecl(D);
1711     return;
1712   }
1713
1714   if (DeclNameEntries.isNull()) {
1715     DeclNameEntries.setOnlyValue(D);
1716     return;
1717   }
1718
1719   if (DeclNameEntries.HandleRedeclaration(D, /*IsKnownNewer*/!Internal)) {
1720     // This declaration has replaced an existing one for which
1721     // declarationReplaces returns true.
1722     return;
1723   }
1724
1725   // Put this declaration into the appropriate slot.
1726   DeclNameEntries.AddSubsequentDecl(D);
1727 }
1728
1729 UsingDirectiveDecl *DeclContext::udir_iterator::operator*() const {
1730   return cast<UsingDirectiveDecl>(*I);
1731 }
1732
1733 /// Returns iterator range [First, Last) of UsingDirectiveDecls stored within
1734 /// this context.
1735 DeclContext::udir_range DeclContext::using_directives() const {
1736   // FIXME: Use something more efficient than normal lookup for using
1737   // directives. In C++, using directives are looked up more than anything else.
1738   lookup_result Result = lookup(UsingDirectiveDecl::getName());
1739   return udir_range(Result.begin(), Result.end());
1740 }
1741
1742 //===----------------------------------------------------------------------===//
1743 // Creation and Destruction of StoredDeclsMaps.                               //
1744 //===----------------------------------------------------------------------===//
1745
1746 StoredDeclsMap *DeclContext::CreateStoredDeclsMap(ASTContext &C) const {
1747   assert(!LookupPtr && "context already has a decls map");
1748   assert(getPrimaryContext() == this &&
1749          "creating decls map on non-primary context");
1750
1751   StoredDeclsMap *M;
1752   bool Dependent = isDependentContext();
1753   if (Dependent)
1754     M = new DependentStoredDeclsMap();
1755   else
1756     M = new StoredDeclsMap();
1757   M->Previous = C.LastSDM;
1758   C.LastSDM = llvm::PointerIntPair<StoredDeclsMap*,1>(M, Dependent);
1759   LookupPtr = M;
1760   return M;
1761 }
1762
1763 void ASTContext::ReleaseDeclContextMaps() {
1764   // It's okay to delete DependentStoredDeclsMaps via a StoredDeclsMap
1765   // pointer because the subclass doesn't add anything that needs to
1766   // be deleted.
1767   StoredDeclsMap::DestroyAll(LastSDM.getPointer(), LastSDM.getInt());
1768 }
1769
1770 void StoredDeclsMap::DestroyAll(StoredDeclsMap *Map, bool Dependent) {
1771   while (Map) {
1772     // Advance the iteration before we invalidate memory.
1773     llvm::PointerIntPair<StoredDeclsMap*,1> Next = Map->Previous;
1774
1775     if (Dependent)
1776       delete static_cast<DependentStoredDeclsMap*>(Map);
1777     else
1778       delete Map;
1779
1780     Map = Next.getPointer();
1781     Dependent = Next.getInt();
1782   }
1783 }
1784
1785 DependentDiagnostic *DependentDiagnostic::Create(ASTContext &C,
1786                                                  DeclContext *Parent,
1787                                            const PartialDiagnostic &PDiag) {
1788   assert(Parent->isDependentContext()
1789          && "cannot iterate dependent diagnostics of non-dependent context");
1790   Parent = Parent->getPrimaryContext();
1791   if (!Parent->LookupPtr)
1792     Parent->CreateStoredDeclsMap(C);
1793
1794   DependentStoredDeclsMap *Map =
1795       static_cast<DependentStoredDeclsMap *>(Parent->LookupPtr);
1796
1797   // Allocate the copy of the PartialDiagnostic via the ASTContext's
1798   // BumpPtrAllocator, rather than the ASTContext itself.
1799   PartialDiagnostic::Storage *DiagStorage = nullptr;
1800   if (PDiag.hasStorage())
1801     DiagStorage = new (C) PartialDiagnostic::Storage;
1802
1803   DependentDiagnostic *DD = new (C) DependentDiagnostic(PDiag, DiagStorage);
1804
1805   // TODO: Maybe we shouldn't reverse the order during insertion.
1806   DD->NextDiagnostic = Map->FirstDiagnostic;
1807   Map->FirstDiagnostic = DD;
1808
1809   return DD;
1810 }