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