contrib/llvm-project/clang/lib/AST/DeclTemplate.cpp

   1 //===- DeclTemplate.cpp - Template Declaration AST Node Implementation ----===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements the C++ related Decl classes for templates.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "clang/AST/DeclTemplate.h"
  14 #include "clang/AST/ASTContext.h"
  15 #include "clang/AST/ASTMutationListener.h"
  16 #include "clang/AST/DeclCXX.h"
  17 #include "clang/AST/DeclarationName.h"
  18 #include "clang/AST/Expr.h"
  19 #include "clang/AST/ExternalASTSource.h"
  20 #include "clang/AST/TemplateBase.h"
  21 #include "clang/AST/TemplateName.h"
  22 #include "clang/AST/Type.h"
  23 #include "clang/AST/TypeLoc.h"
  24 #include "clang/Basic/Builtins.h"
  25 #include "clang/Basic/LLVM.h"
  26 #include "clang/Basic/SourceLocation.h"
  27 #include "llvm/ADT/ArrayRef.h"
  28 #include "llvm/ADT/FoldingSet.h"
  29 #include "llvm/ADT/None.h"
  30 #include "llvm/ADT/PointerUnion.h"
  31 #include "llvm/ADT/SmallVector.h"
  32 #include "llvm/Support/Casting.h"
  33 #include "llvm/Support/ErrorHandling.h"
  34 #include <algorithm>
  35 #include <cassert>
  36 #include <cstdint>
  37 #include <memory>
  38 #include <utility>
  39
  40 using namespace clang;
  41
  42 //===----------------------------------------------------------------------===//
  43 // TemplateParameterList Implementation
  44 //===----------------------------------------------------------------------===//
  45
  46
  47 TemplateParameterList::TemplateParameterList(const ASTContext& C,
  48                                              SourceLocation TemplateLoc,
  49                                              SourceLocation LAngleLoc,
  50                                              ArrayRef<NamedDecl *> Params,
  51                                              SourceLocation RAngleLoc,
  52                                              Expr *RequiresClause)
  53     : TemplateLoc(TemplateLoc), LAngleLoc(LAngleLoc), RAngleLoc(RAngleLoc),
  54       NumParams(Params.size()), ContainsUnexpandedParameterPack(false),
  55       HasRequiresClause(RequiresClause != nullptr),
  56       HasConstrainedParameters(false) {
  57   for (unsigned Idx = 0; Idx < NumParams; ++Idx) {
  58     NamedDecl *P = Params[Idx];
  59     begin()[Idx] = P;
  60
  61     bool IsPack = P->isTemplateParameterPack();
  62     if (const auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(P)) {
  63       if (!IsPack && NTTP->getType()->containsUnexpandedParameterPack())
  64         ContainsUnexpandedParameterPack = true;
  65       if (NTTP->hasPlaceholderTypeConstraint())
  66         HasConstrainedParameters = true;
  67     } else if (const auto *TTP = dyn_cast<TemplateTemplateParmDecl>(P)) {
  68       if (!IsPack &&
  69           TTP->getTemplateParameters()->containsUnexpandedParameterPack())
  70         ContainsUnexpandedParameterPack = true;
  71     } else if (const TypeConstraint *TC =
  72         cast<TemplateTypeParmDecl>(P)->getTypeConstraint()) {
  73       if (TC->getImmediatelyDeclaredConstraint()
  74           ->containsUnexpandedParameterPack())
  75         ContainsUnexpandedParameterPack = true;
  76       HasConstrainedParameters = true;
  77     }
  78     // FIXME: If a default argument contains an unexpanded parameter pack, the
  79     // template parameter list does too.
  80   }
  81
  82   if (HasRequiresClause) {
  83     if (RequiresClause->containsUnexpandedParameterPack())
  84       ContainsUnexpandedParameterPack = true;
  85     *getTrailingObjects<Expr *>() = RequiresClause;
  86   }
  87 }
  88
  89 TemplateParameterList *
  90 TemplateParameterList::Create(const ASTContext &C, SourceLocation TemplateLoc,
  91                               SourceLocation LAngleLoc,
  92                               ArrayRef<NamedDecl *> Params,
  93                               SourceLocation RAngleLoc, Expr *RequiresClause) {
  94   void *Mem = C.Allocate(totalSizeToAlloc<NamedDecl *, Expr *>(
  95                              Params.size(), RequiresClause ? 1u : 0u),
  96                          alignof(TemplateParameterList));
  97   return new (Mem) TemplateParameterList(C, TemplateLoc, LAngleLoc, Params,
  98                                          RAngleLoc, RequiresClause);
  99 }
 100
 101 unsigned TemplateParameterList::getMinRequiredArguments() const {
 102   unsigned NumRequiredArgs = 0;
 103   for (const NamedDecl *P : asArray()) {
 104     if (P->isTemplateParameterPack()) {
 105       if (const auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(P)) {
 106         if (NTTP->isExpandedParameterPack()) {
 107           NumRequiredArgs += NTTP->getNumExpansionTypes();
 108           continue;
 109         }
 110       } else if (const auto *TTP = dyn_cast<TemplateTypeParmDecl>(P)) {
 111         if (TTP->isExpandedParameterPack()) {
 112           NumRequiredArgs += TTP->getNumExpansionParameters();
 113           continue;
 114         }
 115       } else {
 116         const auto *TP = cast<TemplateTemplateParmDecl>(P);
 117         if (TP->isExpandedParameterPack()) {
 118           NumRequiredArgs += TP->getNumExpansionTemplateParameters();
 119           continue;
 120         }
 121       }
 122
 123       break;
 124     }
 125
 126     if (const auto *TTP = dyn_cast<TemplateTypeParmDecl>(P)) {
 127       if (TTP->hasDefaultArgument())
 128         break;
 129     } else if (const auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(P)) {
 130       if (NTTP->hasDefaultArgument())
 131         break;
 132     } else if (cast<TemplateTemplateParmDecl>(P)->hasDefaultArgument())
 133       break;
 134
 135     ++NumRequiredArgs;
 136   }
 137
 138   return NumRequiredArgs;
 139 }
 140
 141 unsigned TemplateParameterList::getDepth() const {
 142   if (size() == 0)
 143     return 0;
 144
 145   const NamedDecl *FirstParm = getParam(0);
 146   if (const auto *TTP = dyn_cast<TemplateTypeParmDecl>(FirstParm))
 147     return TTP->getDepth();
 148   else if (const auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(FirstParm))
 149     return NTTP->getDepth();
 150   else
 151     return cast<TemplateTemplateParmDecl>(FirstParm)->getDepth();
 152 }
 153
 154 static void AdoptTemplateParameterList(TemplateParameterList *Params,
 155                                        DeclContext *Owner) {
 156   for (NamedDecl *P : *Params) {
 157     P->setDeclContext(Owner);
 158
 159     if (const auto *TTP = dyn_cast<TemplateTemplateParmDecl>(P))
 160       AdoptTemplateParameterList(TTP->getTemplateParameters(), Owner);
 161   }
 162 }
 163
 164 void TemplateParameterList::
 165 getAssociatedConstraints(llvm::SmallVectorImpl<const Expr *> &AC) const {
 166   if (HasConstrainedParameters)
 167     for (const NamedDecl *Param : *this) {
 168       if (const auto *TTP = dyn_cast<TemplateTypeParmDecl>(Param)) {
 169         if (const auto *TC = TTP->getTypeConstraint())
 170           AC.push_back(TC->getImmediatelyDeclaredConstraint());
 171       } else if (const auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
 172         if (const Expr *E = NTTP->getPlaceholderTypeConstraint())
 173           AC.push_back(E);
 174       }
 175     }
 176   if (HasRequiresClause)
 177     AC.push_back(getRequiresClause());
 178 }
 179
 180 bool TemplateParameterList::hasAssociatedConstraints() const {
 181   return HasRequiresClause || HasConstrainedParameters;
 182 }
 183
 184 namespace clang {
 185
 186 void *allocateDefaultArgStorageChain(const ASTContext &C) {
 187   return new (C) char[sizeof(void*) * 2];
 188 }
 189
 190 } // namespace clang
 191
 192 //===----------------------------------------------------------------------===//
 193 // TemplateDecl Implementation
 194 //===----------------------------------------------------------------------===//
 195
 196 TemplateDecl::TemplateDecl(Kind DK, DeclContext *DC, SourceLocation L,
 197                            DeclarationName Name, TemplateParameterList *Params,
 198                            NamedDecl *Decl)
 199     : NamedDecl(DK, DC, L, Name), TemplatedDecl(Decl), TemplateParams(Params) {}
 200
 201 void TemplateDecl::anchor() {}
 202
 203 void TemplateDecl::
 204 getAssociatedConstraints(llvm::SmallVectorImpl<const Expr *> &AC) const {
 205   TemplateParams->getAssociatedConstraints(AC);
 206   if (auto *FD = dyn_cast_or_null<FunctionDecl>(getTemplatedDecl()))
 207     if (const Expr *TRC = FD->getTrailingRequiresClause())
 208       AC.push_back(TRC);
 209 }
 210
 211 bool TemplateDecl::hasAssociatedConstraints() const {
 212   if (TemplateParams->hasAssociatedConstraints())
 213     return true;
 214   if (auto *FD = dyn_cast_or_null<FunctionDecl>(getTemplatedDecl()))
 215     return FD->getTrailingRequiresClause();
 216   return false;
 217 }
 218
 219 //===----------------------------------------------------------------------===//
 220 // RedeclarableTemplateDecl Implementation
 221 //===----------------------------------------------------------------------===//
 222
 223 void RedeclarableTemplateDecl::anchor() {}
 224
 225 RedeclarableTemplateDecl::CommonBase *RedeclarableTemplateDecl::getCommonPtr() const {
 226   if (Common)
 227     return Common;
 228
 229   // Walk the previous-declaration chain until we either find a declaration
 230   // with a common pointer or we run out of previous declarations.
 231   SmallVector<const RedeclarableTemplateDecl *, 2> PrevDecls;
 232   for (const RedeclarableTemplateDecl *Prev = getPreviousDecl(); Prev;
 233        Prev = Prev->getPreviousDecl()) {
 234     if (Prev->Common) {
 235       Common = Prev->Common;
 236       break;
 237     }
 238
 239     PrevDecls.push_back(Prev);
 240   }
 241
 242   // If we never found a common pointer, allocate one now.
 243   if (!Common) {
 244     // FIXME: If any of the declarations is from an AST file, we probably
 245     // need an update record to add the common data.
 246
 247     Common = newCommon(getASTContext());
 248   }
 249
 250   // Update any previous declarations we saw with the common pointer.
 251   for (const RedeclarableTemplateDecl *Prev : PrevDecls)
 252     Prev->Common = Common;
 253
 254   return Common;
 255 }
 256
 257 void RedeclarableTemplateDecl::loadLazySpecializationsImpl() const {
 258   // Grab the most recent declaration to ensure we've loaded any lazy
 259   // redeclarations of this template.
 260   CommonBase *CommonBasePtr = getMostRecentDecl()->getCommonPtr();
 261   if (CommonBasePtr->LazySpecializations) {
 262     ASTContext &Context = getASTContext();
 263     uint32_t *Specs = CommonBasePtr->LazySpecializations;
 264     CommonBasePtr->LazySpecializations = nullptr;
 265     for (uint32_t I = 0, N = *Specs++; I != N; ++I)
 266       (void)Context.getExternalSource()->GetExternalDecl(Specs[I]);
 267   }
 268 }
 269
 270 template<class EntryType, typename... ProfileArguments>
 271 typename RedeclarableTemplateDecl::SpecEntryTraits<EntryType>::DeclType *
 272 RedeclarableTemplateDecl::findSpecializationImpl(
 273     llvm::FoldingSetVector<EntryType> &Specs, void *&InsertPos,
 274     ProfileArguments&&... ProfileArgs) {
 275   using SETraits = SpecEntryTraits<EntryType>;
 276
 277   llvm::FoldingSetNodeID ID;
 278   EntryType::Profile(ID, std::forward<ProfileArguments>(ProfileArgs)...,
 279                      getASTContext());
 280   EntryType *Entry = Specs.FindNodeOrInsertPos(ID, InsertPos);
 281   return Entry ? SETraits::getDecl(Entry)->getMostRecentDecl() : nullptr;
 282 }
 283
 284 template<class Derived, class EntryType>
 285 void RedeclarableTemplateDecl::addSpecializationImpl(
 286     llvm::FoldingSetVector<EntryType> &Specializations, EntryType *Entry,
 287     void *InsertPos) {
 288   using SETraits = SpecEntryTraits<EntryType>;
 289
 290   if (InsertPos) {
 291 #ifndef NDEBUG
 292     void *CorrectInsertPos;
 293     assert(!findSpecializationImpl(Specializations,
 294                                    CorrectInsertPos,
 295                                    SETraits::getTemplateArgs(Entry)) &&
 296            InsertPos == CorrectInsertPos &&
 297            "given incorrect InsertPos for specialization");
 298 #endif
 299     Specializations.InsertNode(Entry, InsertPos);
 300   } else {
 301     EntryType *Existing = Specializations.GetOrInsertNode(Entry);
 302     (void)Existing;
 303     assert(SETraits::getDecl(Existing)->isCanonicalDecl() &&
 304            "non-canonical specialization?");
 305   }
 306
 307   if (ASTMutationListener *L = getASTMutationListener())
 308     L->AddedCXXTemplateSpecialization(cast<Derived>(this),
 309                                       SETraits::getDecl(Entry));
 310 }
 311
 312 //===----------------------------------------------------------------------===//
 313 // FunctionTemplateDecl Implementation
 314 //===----------------------------------------------------------------------===//
 315
 316 FunctionTemplateDecl *FunctionTemplateDecl::Create(ASTContext &C,
 317                                                    DeclContext *DC,
 318                                                    SourceLocation L,
 319                                                    DeclarationName Name,
 320                                                TemplateParameterList *Params,
 321                                                    NamedDecl *Decl) {
 322   AdoptTemplateParameterList(Params, cast<DeclContext>(Decl));
 323   return new (C, DC) FunctionTemplateDecl(C, DC, L, Name, Params, Decl);
 324 }
 325
 326 FunctionTemplateDecl *FunctionTemplateDecl::CreateDeserialized(ASTContext &C,
 327                                                                unsigned ID) {
 328   return new (C, ID) FunctionTemplateDecl(C, nullptr, SourceLocation(),
 329                                           DeclarationName(), nullptr, nullptr);
 330 }
 331
 332 RedeclarableTemplateDecl::CommonBase *
 333 FunctionTemplateDecl::newCommon(ASTContext &C) const {
 334   auto *CommonPtr = new (C) Common;
 335   C.addDestruction(CommonPtr);
 336   return CommonPtr;
 337 }
 338
 339 void FunctionTemplateDecl::LoadLazySpecializations() const {
 340   loadLazySpecializationsImpl();
 341 }
 342
 343 llvm::FoldingSetVector<FunctionTemplateSpecializationInfo> &
 344 FunctionTemplateDecl::getSpecializations() const {
 345   LoadLazySpecializations();
 346   return getCommonPtr()->Specializations;
 347 }
 348
 349 FunctionDecl *
 350 FunctionTemplateDecl::findSpecialization(ArrayRef<TemplateArgument> Args,
 351                                          void *&InsertPos) {
 352   return findSpecializationImpl(getSpecializations(), InsertPos, Args);
 353 }
 354
 355 void FunctionTemplateDecl::addSpecialization(
 356       FunctionTemplateSpecializationInfo *Info, void *InsertPos) {
 357   addSpecializationImpl<FunctionTemplateDecl>(getSpecializations(), Info,
 358                                               InsertPos);
 359 }
 360
 361 ArrayRef<TemplateArgument> FunctionTemplateDecl::getInjectedTemplateArgs() {
 362   TemplateParameterList *Params = getTemplateParameters();
 363   Common *CommonPtr = getCommonPtr();
 364   if (!CommonPtr->InjectedArgs) {
 365     auto &Context = getASTContext();
 366     SmallVector<TemplateArgument, 16> TemplateArgs;
 367     Context.getInjectedTemplateArgs(Params, TemplateArgs);
 368     CommonPtr->InjectedArgs =
 369         new (Context) TemplateArgument[TemplateArgs.size()];
 370     std::copy(TemplateArgs.begin(), TemplateArgs.end(),
 371               CommonPtr->InjectedArgs);
 372   }
 373
 374   return llvm::makeArrayRef(CommonPtr->InjectedArgs, Params->size());
 375 }
 376
 377 void FunctionTemplateDecl::mergePrevDecl(FunctionTemplateDecl *Prev) {
 378   using Base = RedeclarableTemplateDecl;
 379
 380   // If we haven't created a common pointer yet, then it can just be created
 381   // with the usual method.
 382   if (!Base::Common)
 383     return;
 384
 385   Common *ThisCommon = static_cast<Common *>(Base::Common);
 386   Common *PrevCommon = nullptr;
 387   SmallVector<FunctionTemplateDecl *, 8> PreviousDecls;
 388   for (; Prev; Prev = Prev->getPreviousDecl()) {
 389     if (Prev->Base::Common) {
 390       PrevCommon = static_cast<Common *>(Prev->Base::Common);
 391       break;
 392     }
 393     PreviousDecls.push_back(Prev);
 394   }
 395
 396   // If the previous redecl chain hasn't created a common pointer yet, then just
 397   // use this common pointer.
 398   if (!PrevCommon) {
 399     for (auto *D : PreviousDecls)
 400       D->Base::Common = ThisCommon;
 401     return;
 402   }
 403
 404   // Ensure we don't leak any important state.
 405   assert(ThisCommon->Specializations.size() == 0 &&
 406          "Can't merge incompatible declarations!");
 407
 408   Base::Common = PrevCommon;
 409 }
 410
 411 //===----------------------------------------------------------------------===//
 412 // ClassTemplateDecl Implementation
 413 //===----------------------------------------------------------------------===//
 414
 415 ClassTemplateDecl *ClassTemplateDecl::Create(ASTContext &C,
 416                                              DeclContext *DC,
 417                                              SourceLocation L,
 418                                              DeclarationName Name,
 419                                              TemplateParameterList *Params,
 420                                              NamedDecl *Decl) {
 421   AdoptTemplateParameterList(Params, cast<DeclContext>(Decl));
 422
 423   return new (C, DC) ClassTemplateDecl(C, DC, L, Name, Params, Decl);
 424 }
 425
 426 ClassTemplateDecl *ClassTemplateDecl::CreateDeserialized(ASTContext &C,
 427                                                          unsigned ID) {
 428   return new (C, ID) ClassTemplateDecl(C, nullptr, SourceLocation(),
 429                                        DeclarationName(), nullptr, nullptr);
 430 }
 431
 432 void ClassTemplateDecl::LoadLazySpecializations() const {
 433   loadLazySpecializationsImpl();
 434 }
 435
 436 llvm::FoldingSetVector<ClassTemplateSpecializationDecl> &
 437 ClassTemplateDecl::getSpecializations() const {
 438   LoadLazySpecializations();
 439   return getCommonPtr()->Specializations;
 440 }
 441
 442 llvm::FoldingSetVector<ClassTemplatePartialSpecializationDecl> &
 443 ClassTemplateDecl::getPartialSpecializations() {
 444   LoadLazySpecializations();
 445   return getCommonPtr()->PartialSpecializations;
 446 }
 447
 448 RedeclarableTemplateDecl::CommonBase *
 449 ClassTemplateDecl::newCommon(ASTContext &C) const {
 450   auto *CommonPtr = new (C) Common;
 451   C.addDestruction(CommonPtr);
 452   return CommonPtr;
 453 }
 454
 455 ClassTemplateSpecializationDecl *
 456 ClassTemplateDecl::findSpecialization(ArrayRef<TemplateArgument> Args,
 457                                       void *&InsertPos) {
 458   return findSpecializationImpl(getSpecializations(), InsertPos, Args);
 459 }
 460
 461 void ClassTemplateDecl::AddSpecialization(ClassTemplateSpecializationDecl *D,
 462                                           void *InsertPos) {
 463   addSpecializationImpl<ClassTemplateDecl>(getSpecializations(), D, InsertPos);
 464 }
 465
 466 ClassTemplatePartialSpecializationDecl *
 467 ClassTemplateDecl::findPartialSpecialization(
 468     ArrayRef<TemplateArgument> Args,
 469     TemplateParameterList *TPL, void *&InsertPos) {
 470   return findSpecializationImpl(getPartialSpecializations(), InsertPos, Args,
 471                                 TPL);
 472 }
 473
 474 static void ProfileTemplateParameterList(ASTContext &C,
 475     llvm::FoldingSetNodeID &ID, const TemplateParameterList *TPL) {
 476   const Expr *RC = TPL->getRequiresClause();
 477   ID.AddBoolean(RC != nullptr);
 478   if (RC)
 479     RC->Profile(ID, C, /*Canonical=*/true);
 480   ID.AddInteger(TPL->size());
 481   for (NamedDecl *D : *TPL) {
 482     if (const auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) {
 483       ID.AddInteger(0);
 484       ID.AddBoolean(NTTP->isParameterPack());
 485       NTTP->getType().getCanonicalType().Profile(ID);
 486       continue;
 487     }
 488     if (const auto *TTP = dyn_cast<TemplateTypeParmDecl>(D)) {
 489       ID.AddInteger(1);
 490       ID.AddBoolean(TTP->isParameterPack());
 491       ID.AddBoolean(TTP->hasTypeConstraint());
 492       if (const TypeConstraint *TC = TTP->getTypeConstraint())
 493         TC->getImmediatelyDeclaredConstraint()->Profile(ID, C,
 494                                                         /*Canonical=*/true);
 495       continue;
 496     }
 497     const auto *TTP = cast<TemplateTemplateParmDecl>(D);
 498     ID.AddInteger(2);
 499     ID.AddBoolean(TTP->isParameterPack());
 500     ProfileTemplateParameterList(C, ID, TTP->getTemplateParameters());
 501   }
 502 }
 503
 504 void
 505 ClassTemplatePartialSpecializationDecl::Profile(llvm::FoldingSetNodeID &ID,
 506     ArrayRef<TemplateArgument> TemplateArgs, TemplateParameterList *TPL,
 507     ASTContext &Context) {
 508   ID.AddInteger(TemplateArgs.size());
 509   for (const TemplateArgument &TemplateArg : TemplateArgs)
 510     TemplateArg.Profile(ID, Context);
 511   ProfileTemplateParameterList(Context, ID, TPL);
 512 }
 513
 514 void ClassTemplateDecl::AddPartialSpecialization(
 515                                       ClassTemplatePartialSpecializationDecl *D,
 516                                       void *InsertPos) {
 517   if (InsertPos)
 518     getPartialSpecializations().InsertNode(D, InsertPos);
 519   else {
 520     ClassTemplatePartialSpecializationDecl *Existing
 521       = getPartialSpecializations().GetOrInsertNode(D);
 522     (void)Existing;
 523     assert(Existing->isCanonicalDecl() && "Non-canonical specialization?");
 524   }
 525
 526   if (ASTMutationListener *L = getASTMutationListener())
 527     L->AddedCXXTemplateSpecialization(this, D);
 528 }
 529
 530 void ClassTemplateDecl::getPartialSpecializations(
 531           SmallVectorImpl<ClassTemplatePartialSpecializationDecl *> &PS) {
 532   llvm::FoldingSetVector<ClassTemplatePartialSpecializationDecl> &PartialSpecs
 533     = getPartialSpecializations();
 534   PS.clear();
 535   PS.reserve(PartialSpecs.size());
 536   for (ClassTemplatePartialSpecializationDecl &P : PartialSpecs)
 537     PS.push_back(P.getMostRecentDecl());
 538 }
 539
 540 ClassTemplatePartialSpecializationDecl *
 541 ClassTemplateDecl::findPartialSpecialization(QualType T) {
 542   ASTContext &Context = getASTContext();
 543   for (ClassTemplatePartialSpecializationDecl &P :
 544        getPartialSpecializations()) {
 545     if (Context.hasSameType(P.getInjectedSpecializationType(), T))
 546       return P.getMostRecentDecl();
 547   }
 548
 549   return nullptr;
 550 }
 551
 552 ClassTemplatePartialSpecializationDecl *
 553 ClassTemplateDecl::findPartialSpecInstantiatedFromMember(
 554                                     ClassTemplatePartialSpecializationDecl *D) {
 555   Decl *DCanon = D->getCanonicalDecl();
 556   for (ClassTemplatePartialSpecializationDecl &P : getPartialSpecializations()) {
 557     if (P.getInstantiatedFromMember()->getCanonicalDecl() == DCanon)
 558       return P.getMostRecentDecl();
 559   }
 560
 561   return nullptr;
 562 }
 563
 564 QualType
 565 ClassTemplateDecl::getInjectedClassNameSpecialization() {
 566   Common *CommonPtr = getCommonPtr();
 567   if (!CommonPtr->InjectedClassNameType.isNull())
 568     return CommonPtr->InjectedClassNameType;
 569
 570   // C++0x [temp.dep.type]p2:
 571   //  The template argument list of a primary template is a template argument
 572   //  list in which the nth template argument has the value of the nth template
 573   //  parameter of the class template. If the nth template parameter is a
 574   //  template parameter pack (14.5.3), the nth template argument is a pack
 575   //  expansion (14.5.3) whose pattern is the name of the template parameter
 576   //  pack.
 577   ASTContext &Context = getASTContext();
 578   TemplateParameterList *Params = getTemplateParameters();
 579   SmallVector<TemplateArgument, 16> TemplateArgs;
 580   Context.getInjectedTemplateArgs(Params, TemplateArgs);
 581   CommonPtr->InjectedClassNameType
 582     = Context.getTemplateSpecializationType(TemplateName(this),
 583                                             TemplateArgs);
 584   return CommonPtr->InjectedClassNameType;
 585 }
 586
 587 //===----------------------------------------------------------------------===//
 588 // TemplateTypeParm Allocation/Deallocation Method Implementations
 589 //===----------------------------------------------------------------------===//
 590
 591 TemplateTypeParmDecl *
 592 TemplateTypeParmDecl::Create(const ASTContext &C, DeclContext *DC,
 593                              SourceLocation KeyLoc, SourceLocation NameLoc,
 594                              unsigned D, unsigned P, IdentifierInfo *Id,
 595                              bool Typename, bool ParameterPack,
 596                              bool HasTypeConstraint,
 597                              Optional<unsigned> NumExpanded) {
 598   auto *TTPDecl =
 599       new (C, DC,
 600            additionalSizeToAlloc<TypeConstraint>(HasTypeConstraint ? 1 : 0))
 601       TemplateTypeParmDecl(DC, KeyLoc, NameLoc, Id, Typename,
 602                            HasTypeConstraint, NumExpanded);
 603   QualType TTPType = C.getTemplateTypeParmType(D, P, ParameterPack, TTPDecl);
 604   TTPDecl->setTypeForDecl(TTPType.getTypePtr());
 605   return TTPDecl;
 606 }
 607
 608 TemplateTypeParmDecl *
 609 TemplateTypeParmDecl::CreateDeserialized(const ASTContext &C, unsigned ID) {
 610   return new (C, ID) TemplateTypeParmDecl(nullptr, SourceLocation(),
 611                                           SourceLocation(), nullptr, false,
 612                                           false, None);
 613 }
 614
 615 TemplateTypeParmDecl *
 616 TemplateTypeParmDecl::CreateDeserialized(const ASTContext &C, unsigned ID,
 617                                          bool HasTypeConstraint) {
 618   return new (C, ID,
 619               additionalSizeToAlloc<TypeConstraint>(HasTypeConstraint ? 1 : 0))
 620          TemplateTypeParmDecl(nullptr, SourceLocation(), SourceLocation(),
 621                               nullptr, false, HasTypeConstraint, None);
 622 }
 623
 624 SourceLocation TemplateTypeParmDecl::getDefaultArgumentLoc() const {
 625   return hasDefaultArgument()
 626              ? getDefaultArgumentInfo()->getTypeLoc().getBeginLoc()
 627              : SourceLocation();
 628 }
 629
 630 SourceRange TemplateTypeParmDecl::getSourceRange() const {
 631   if (hasDefaultArgument() && !defaultArgumentWasInherited())
 632     return SourceRange(getBeginLoc(),
 633                        getDefaultArgumentInfo()->getTypeLoc().getEndLoc());
 634   // TypeDecl::getSourceRange returns a range containing name location, which is
 635   // wrong for unnamed template parameters. e.g:
 636   // it will return <[[typename>]] instead of <[[typename]]>
 637   else if (getDeclName().isEmpty())
 638     return SourceRange(getBeginLoc());
 639   return TypeDecl::getSourceRange();
 640 }
 641
 642 unsigned TemplateTypeParmDecl::getDepth() const {
 643   return getTypeForDecl()->castAs<TemplateTypeParmType>()->getDepth();
 644 }
 645
 646 unsigned TemplateTypeParmDecl::getIndex() const {
 647   return getTypeForDecl()->castAs<TemplateTypeParmType>()->getIndex();
 648 }
 649
 650 bool TemplateTypeParmDecl::isParameterPack() const {
 651   return getTypeForDecl()->castAs<TemplateTypeParmType>()->isParameterPack();
 652 }
 653
 654 void TemplateTypeParmDecl::setTypeConstraint(NestedNameSpecifierLoc NNS,
 655     DeclarationNameInfo NameInfo, NamedDecl *FoundDecl, ConceptDecl *CD,
 656     const ASTTemplateArgumentListInfo *ArgsAsWritten,
 657     Expr *ImmediatelyDeclaredConstraint) {
 658   assert(HasTypeConstraint &&
 659          "HasTypeConstraint=true must be passed at construction in order to "
 660          "call setTypeConstraint");
 661   assert(!TypeConstraintInitialized &&
 662          "TypeConstraint was already initialized!");
 663   new (getTrailingObjects<TypeConstraint>()) TypeConstraint(NNS, NameInfo,
 664       FoundDecl, CD, ArgsAsWritten, ImmediatelyDeclaredConstraint);
 665   TypeConstraintInitialized = true;
 666 }
 667
 668 //===----------------------------------------------------------------------===//
 669 // NonTypeTemplateParmDecl Method Implementations
 670 //===----------------------------------------------------------------------===//
 671
 672 NonTypeTemplateParmDecl::NonTypeTemplateParmDecl(
 673     DeclContext *DC, SourceLocation StartLoc, SourceLocation IdLoc, unsigned D,
 674     unsigned P, IdentifierInfo *Id, QualType T, TypeSourceInfo *TInfo,
 675     ArrayRef<QualType> ExpandedTypes, ArrayRef<TypeSourceInfo *> ExpandedTInfos)
 676     : DeclaratorDecl(NonTypeTemplateParm, DC, IdLoc, Id, T, TInfo, StartLoc),
 677       TemplateParmPosition(D, P), ParameterPack(true),
 678       ExpandedParameterPack(true), NumExpandedTypes(ExpandedTypes.size()) {
 679   if (!ExpandedTypes.empty() && !ExpandedTInfos.empty()) {
 680     auto TypesAndInfos =
 681         getTrailingObjects<std::pair<QualType, TypeSourceInfo *>>();
 682     for (unsigned I = 0; I != NumExpandedTypes; ++I) {
 683       new (&TypesAndInfos[I].first) QualType(ExpandedTypes[I]);
 684       TypesAndInfos[I].second = ExpandedTInfos[I];
 685     }
 686   }
 687 }
 688
 689 NonTypeTemplateParmDecl *
 690 NonTypeTemplateParmDecl::Create(const ASTContext &C, DeclContext *DC,
 691                                 SourceLocation StartLoc, SourceLocation IdLoc,
 692                                 unsigned D, unsigned P, IdentifierInfo *Id,
 693                                 QualType T, bool ParameterPack,
 694                                 TypeSourceInfo *TInfo) {
 695   AutoType *AT =
 696       C.getLangOpts().CPlusPlus2a ? T->getContainedAutoType() : nullptr;
 697   return new (C, DC,
 698               additionalSizeToAlloc<std::pair<QualType, TypeSourceInfo *>,
 699                                     Expr *>(0,
 700                                             AT && AT->isConstrained() ? 1 : 0))
 701       NonTypeTemplateParmDecl(DC, StartLoc, IdLoc, D, P, Id, T, ParameterPack,
 702                               TInfo);
 703 }
 704
 705 NonTypeTemplateParmDecl *NonTypeTemplateParmDecl::Create(
 706     const ASTContext &C, DeclContext *DC, SourceLocation StartLoc,
 707     SourceLocation IdLoc, unsigned D, unsigned P, IdentifierInfo *Id,
 708     QualType T, TypeSourceInfo *TInfo, ArrayRef<QualType> ExpandedTypes,
 709     ArrayRef<TypeSourceInfo *> ExpandedTInfos) {
 710   AutoType *AT = TInfo->getType()->getContainedAutoType();
 711   return new (C, DC,
 712               additionalSizeToAlloc<std::pair<QualType, TypeSourceInfo *>,
 713                                     Expr *>(
 714                   ExpandedTypes.size(), AT && AT->isConstrained() ? 1 : 0))
 715       NonTypeTemplateParmDecl(DC, StartLoc, IdLoc, D, P, Id, T, TInfo,
 716                               ExpandedTypes, ExpandedTInfos);
 717 }
 718
 719 NonTypeTemplateParmDecl *
 720 NonTypeTemplateParmDecl::CreateDeserialized(ASTContext &C, unsigned ID,
 721                                             bool HasTypeConstraint) {
 722   return new (C, ID, additionalSizeToAlloc<std::pair<QualType,
 723                                                      TypeSourceInfo *>,
 724                                            Expr *>(0,
 725                                                    HasTypeConstraint ? 1 : 0))
 726           NonTypeTemplateParmDecl(nullptr, SourceLocation(), SourceLocation(),
 727                                   0, 0, nullptr, QualType(), false, nullptr);
 728 }
 729
 730 NonTypeTemplateParmDecl *
 731 NonTypeTemplateParmDecl::CreateDeserialized(ASTContext &C, unsigned ID,
 732                                             unsigned NumExpandedTypes,
 733                                             bool HasTypeConstraint) {
 734   auto *NTTP =
 735       new (C, ID, additionalSizeToAlloc<std::pair<QualType, TypeSourceInfo *>,
 736                                         Expr *>(
 737                       NumExpandedTypes, HasTypeConstraint ? 1 : 0))
 738           NonTypeTemplateParmDecl(nullptr, SourceLocation(), SourceLocation(),
 739                                   0, 0, nullptr, QualType(), nullptr, None,
 740                                   None);
 741   NTTP->NumExpandedTypes = NumExpandedTypes;
 742   return NTTP;
 743 }
 744
 745 SourceRange NonTypeTemplateParmDecl::getSourceRange() const {
 746   if (hasDefaultArgument() && !defaultArgumentWasInherited())
 747     return SourceRange(getOuterLocStart(),
 748                        getDefaultArgument()->getSourceRange().getEnd());
 749   return DeclaratorDecl::getSourceRange();
 750 }
 751
 752 SourceLocation NonTypeTemplateParmDecl::getDefaultArgumentLoc() const {
 753   return hasDefaultArgument()
 754     ? getDefaultArgument()->getSourceRange().getBegin()
 755     : SourceLocation();
 756 }
 757
 758 //===----------------------------------------------------------------------===//
 759 // TemplateTemplateParmDecl Method Implementations
 760 //===----------------------------------------------------------------------===//
 761
 762 void TemplateTemplateParmDecl::anchor() {}
 763
 764 TemplateTemplateParmDecl::TemplateTemplateParmDecl(
 765     DeclContext *DC, SourceLocation L, unsigned D, unsigned P,
 766     IdentifierInfo *Id, TemplateParameterList *Params,
 767     ArrayRef<TemplateParameterList *> Expansions)
 768     : TemplateDecl(TemplateTemplateParm, DC, L, Id, Params),
 769       TemplateParmPosition(D, P), ParameterPack(true),
 770       ExpandedParameterPack(true), NumExpandedParams(Expansions.size()) {
 771   if (!Expansions.empty())
 772     std::uninitialized_copy(Expansions.begin(), Expansions.end(),
 773                             getTrailingObjects<TemplateParameterList *>());
 774 }
 775
 776 TemplateTemplateParmDecl *
 777 TemplateTemplateParmDecl::Create(const ASTContext &C, DeclContext *DC,
 778                                  SourceLocation L, unsigned D, unsigned P,
 779                                  bool ParameterPack, IdentifierInfo *Id,
 780                                  TemplateParameterList *Params) {
 781   return new (C, DC) TemplateTemplateParmDecl(DC, L, D, P, ParameterPack, Id,
 782                                               Params);
 783 }
 784
 785 TemplateTemplateParmDecl *
 786 TemplateTemplateParmDecl::Create(const ASTContext &C, DeclContext *DC,
 787                                  SourceLocation L, unsigned D, unsigned P,
 788                                  IdentifierInfo *Id,
 789                                  TemplateParameterList *Params,
 790                                  ArrayRef<TemplateParameterList *> Expansions) {
 791   return new (C, DC,
 792               additionalSizeToAlloc<TemplateParameterList *>(Expansions.size()))
 793       TemplateTemplateParmDecl(DC, L, D, P, Id, Params, Expansions);
 794 }
 795
 796 TemplateTemplateParmDecl *
 797 TemplateTemplateParmDecl::CreateDeserialized(ASTContext &C, unsigned ID) {
 798   return new (C, ID) TemplateTemplateParmDecl(nullptr, SourceLocation(), 0, 0,
 799                                               false, nullptr, nullptr);
 800 }
 801
 802 TemplateTemplateParmDecl *
 803 TemplateTemplateParmDecl::CreateDeserialized(ASTContext &C, unsigned ID,
 804                                              unsigned NumExpansions) {
 805   auto *TTP =
 806       new (C, ID, additionalSizeToAlloc<TemplateParameterList *>(NumExpansions))
 807           TemplateTemplateParmDecl(nullptr, SourceLocation(), 0, 0, nullptr,
 808                                    nullptr, None);
 809   TTP->NumExpandedParams = NumExpansions;
 810   return TTP;
 811 }
 812
 813 SourceLocation TemplateTemplateParmDecl::getDefaultArgumentLoc() const {
 814   return hasDefaultArgument() ? getDefaultArgument().getLocation()
 815                               : SourceLocation();
 816 }
 817
 818 void TemplateTemplateParmDecl::setDefaultArgument(
 819     const ASTContext &C, const TemplateArgumentLoc &DefArg) {
 820   if (DefArg.getArgument().isNull())
 821     DefaultArgument.set(nullptr);
 822   else
 823     DefaultArgument.set(new (C) TemplateArgumentLoc(DefArg));
 824 }
 825
 826 //===----------------------------------------------------------------------===//
 827 // TemplateArgumentList Implementation
 828 //===----------------------------------------------------------------------===//
 829 TemplateArgumentList::TemplateArgumentList(ArrayRef<TemplateArgument> Args)
 830     : Arguments(getTrailingObjects<TemplateArgument>()),
 831       NumArguments(Args.size()) {
 832   std::uninitialized_copy(Args.begin(), Args.end(),
 833                           getTrailingObjects<TemplateArgument>());
 834 }
 835
 836 TemplateArgumentList *
 837 TemplateArgumentList::CreateCopy(ASTContext &Context,
 838                                  ArrayRef<TemplateArgument> Args) {
 839   void *Mem = Context.Allocate(totalSizeToAlloc<TemplateArgument>(Args.size()));
 840   return new (Mem) TemplateArgumentList(Args);
 841 }
 842
 843 FunctionTemplateSpecializationInfo *FunctionTemplateSpecializationInfo::Create(
 844     ASTContext &C, FunctionDecl *FD, FunctionTemplateDecl *Template,
 845     TemplateSpecializationKind TSK, const TemplateArgumentList *TemplateArgs,
 846     const TemplateArgumentListInfo *TemplateArgsAsWritten, SourceLocation POI,
 847     MemberSpecializationInfo *MSInfo) {
 848   const ASTTemplateArgumentListInfo *ArgsAsWritten = nullptr;
 849   if (TemplateArgsAsWritten)
 850     ArgsAsWritten = ASTTemplateArgumentListInfo::Create(C,
 851                                                         *TemplateArgsAsWritten);
 852
 853   void *Mem =
 854       C.Allocate(totalSizeToAlloc<MemberSpecializationInfo *>(MSInfo ? 1 : 0));
 855   return new (Mem) FunctionTemplateSpecializationInfo(
 856       FD, Template, TSK, TemplateArgs, ArgsAsWritten, POI, MSInfo);
 857 }
 858
 859 //===----------------------------------------------------------------------===//
 860 // ClassTemplateSpecializationDecl Implementation
 861 //===----------------------------------------------------------------------===//
 862
 863 ClassTemplateSpecializationDecl::
 864 ClassTemplateSpecializationDecl(ASTContext &Context, Kind DK, TagKind TK,
 865                                 DeclContext *DC, SourceLocation StartLoc,
 866                                 SourceLocation IdLoc,
 867                                 ClassTemplateDecl *SpecializedTemplate,
 868                                 ArrayRef<TemplateArgument> Args,
 869                                 ClassTemplateSpecializationDecl *PrevDecl)
 870     : CXXRecordDecl(DK, TK, Context, DC, StartLoc, IdLoc,
 871                     SpecializedTemplate->getIdentifier(), PrevDecl),
 872     SpecializedTemplate(SpecializedTemplate),
 873     TemplateArgs(TemplateArgumentList::CreateCopy(Context, Args)),
 874     SpecializationKind(TSK_Undeclared) {
 875 }
 876
 877 ClassTemplateSpecializationDecl::ClassTemplateSpecializationDecl(ASTContext &C,
 878                                                                  Kind DK)
 879     : CXXRecordDecl(DK, TTK_Struct, C, nullptr, SourceLocation(),
 880                     SourceLocation(), nullptr, nullptr),
 881       SpecializationKind(TSK_Undeclared) {}
 882
 883 ClassTemplateSpecializationDecl *
 884 ClassTemplateSpecializationDecl::Create(ASTContext &Context, TagKind TK,
 885                                         DeclContext *DC,
 886                                         SourceLocation StartLoc,
 887                                         SourceLocation IdLoc,
 888                                         ClassTemplateDecl *SpecializedTemplate,
 889                                         ArrayRef<TemplateArgument> Args,
 890                                    ClassTemplateSpecializationDecl *PrevDecl) {
 891   auto *Result =
 892       new (Context, DC) ClassTemplateSpecializationDecl(
 893           Context, ClassTemplateSpecialization, TK, DC, StartLoc, IdLoc,
 894           SpecializedTemplate, Args, PrevDecl);
 895   Result->setMayHaveOutOfDateDef(false);
 896
 897   Context.getTypeDeclType(Result, PrevDecl);
 898   return Result;
 899 }
 900
 901 ClassTemplateSpecializationDecl *
 902 ClassTemplateSpecializationDecl::CreateDeserialized(ASTContext &C,
 903                                                     unsigned ID) {
 904   auto *Result =
 905     new (C, ID) ClassTemplateSpecializationDecl(C, ClassTemplateSpecialization);
 906   Result->setMayHaveOutOfDateDef(false);
 907   return Result;
 908 }
 909
 910 void ClassTemplateSpecializationDecl::getNameForDiagnostic(
 911     raw_ostream &OS, const PrintingPolicy &Policy, bool Qualified) const {
 912   NamedDecl::getNameForDiagnostic(OS, Policy, Qualified);
 913
 914   const auto *PS = dyn_cast<ClassTemplatePartialSpecializationDecl>(this);
 915   if (const ASTTemplateArgumentListInfo *ArgsAsWritten =
 916           PS ? PS->getTemplateArgsAsWritten() : nullptr) {
 917     printTemplateArgumentList(OS, ArgsAsWritten->arguments(), Policy);
 918   } else {
 919     const TemplateArgumentList &TemplateArgs = getTemplateArgs();
 920     printTemplateArgumentList(OS, TemplateArgs.asArray(), Policy);
 921   }
 922 }
 923
 924 ClassTemplateDecl *
 925 ClassTemplateSpecializationDecl::getSpecializedTemplate() const {
 926   if (const auto *PartialSpec =
 927           SpecializedTemplate.dyn_cast<SpecializedPartialSpecialization*>())
 928     return PartialSpec->PartialSpecialization->getSpecializedTemplate();
 929   return SpecializedTemplate.get<ClassTemplateDecl*>();
 930 }
 931
 932 SourceRange
 933 ClassTemplateSpecializationDecl::getSourceRange() const {
 934   if (ExplicitInfo) {
 935     SourceLocation Begin = getTemplateKeywordLoc();
 936     if (Begin.isValid()) {
 937       // Here we have an explicit (partial) specialization or instantiation.
 938       assert(getSpecializationKind() == TSK_ExplicitSpecialization ||
 939              getSpecializationKind() == TSK_ExplicitInstantiationDeclaration ||
 940              getSpecializationKind() == TSK_ExplicitInstantiationDefinition);
 941       if (getExternLoc().isValid())
 942         Begin = getExternLoc();
 943       SourceLocation End = getBraceRange().getEnd();
 944       if (End.isInvalid())
 945         End = getTypeAsWritten()->getTypeLoc().getEndLoc();
 946       return SourceRange(Begin, End);
 947     }
 948     // An implicit instantiation of a class template partial specialization
 949     // uses ExplicitInfo to record the TypeAsWritten, but the source
 950     // locations should be retrieved from the instantiation pattern.
 951     using CTPSDecl = ClassTemplatePartialSpecializationDecl;
 952     auto *ctpsd = const_cast<CTPSDecl *>(cast<CTPSDecl>(this));
 953     CTPSDecl *inst_from = ctpsd->getInstantiatedFromMember();
 954     assert(inst_from != nullptr);
 955     return inst_from->getSourceRange();
 956   }
 957   else {
 958     // No explicit info available.
 959     llvm::PointerUnion<ClassTemplateDecl *,
 960                        ClassTemplatePartialSpecializationDecl *>
 961       inst_from = getInstantiatedFrom();
 962     if (inst_from.isNull())
 963       return getSpecializedTemplate()->getSourceRange();
 964     if (const auto *ctd = inst_from.dyn_cast<ClassTemplateDecl *>())
 965       return ctd->getSourceRange();
 966     return inst_from.get<ClassTemplatePartialSpecializationDecl *>()
 967       ->getSourceRange();
 968   }
 969 }
 970
 971 //===----------------------------------------------------------------------===//
 972 // ConceptDecl Implementation
 973 //===----------------------------------------------------------------------===//
 974 ConceptDecl *ConceptDecl::Create(ASTContext &C, DeclContext *DC,
 975                                  SourceLocation L, DeclarationName Name,
 976                                  TemplateParameterList *Params,
 977                                  Expr *ConstraintExpr) {
 978   AdoptTemplateParameterList(Params, DC);
 979   return new (C, DC) ConceptDecl(DC, L, Name, Params, ConstraintExpr);
 980 }
 981
 982 ConceptDecl *ConceptDecl::CreateDeserialized(ASTContext &C,
 983                                              unsigned ID) {
 984   ConceptDecl *Result = new (C, ID) ConceptDecl(nullptr, SourceLocation(),
 985                                                 DeclarationName(),
 986                                                 nullptr, nullptr);
 987
 988   return Result;
 989 }
 990
 991 //===----------------------------------------------------------------------===//
 992 // ClassTemplatePartialSpecializationDecl Implementation
 993 //===----------------------------------------------------------------------===//
 994 void ClassTemplatePartialSpecializationDecl::anchor() {}
 995
 996 ClassTemplatePartialSpecializationDecl::
 997 ClassTemplatePartialSpecializationDecl(ASTContext &Context, TagKind TK,
 998                                        DeclContext *DC,
 999                                        SourceLocation StartLoc,
1000                                        SourceLocation IdLoc,
1001                                        TemplateParameterList *Params,
1002                                        ClassTemplateDecl *SpecializedTemplate,
1003                                        ArrayRef<TemplateArgument> Args,
1004                                const ASTTemplateArgumentListInfo *ArgInfos,
1005                                ClassTemplatePartialSpecializationDecl *PrevDecl)
1006     : ClassTemplateSpecializationDecl(Context,
1007                                       ClassTemplatePartialSpecialization,
1008                                       TK, DC, StartLoc, IdLoc,
1009                                       SpecializedTemplate, Args, PrevDecl),
1010       TemplateParams(Params), ArgsAsWritten(ArgInfos),
1011       InstantiatedFromMember(nullptr, false) {
1012   AdoptTemplateParameterList(Params, this);
1013 }
1014
1015 ClassTemplatePartialSpecializationDecl *
1016 ClassTemplatePartialSpecializationDecl::
1017 Create(ASTContext &Context, TagKind TK,DeclContext *DC,
1018        SourceLocation StartLoc, SourceLocation IdLoc,
1019        TemplateParameterList *Params,
1020        ClassTemplateDecl *SpecializedTemplate,
1021        ArrayRef<TemplateArgument> Args,
1022        const TemplateArgumentListInfo &ArgInfos,
1023        QualType CanonInjectedType,
1024        ClassTemplatePartialSpecializationDecl *PrevDecl) {
1025   const ASTTemplateArgumentListInfo *ASTArgInfos =
1026     ASTTemplateArgumentListInfo::Create(Context, ArgInfos);
1027
1028   auto *Result = new (Context, DC)
1029       ClassTemplatePartialSpecializationDecl(Context, TK, DC, StartLoc, IdLoc,
1030                                              Params, SpecializedTemplate, Args,
1031                                              ASTArgInfos, PrevDecl);
1032   Result->setSpecializationKind(TSK_ExplicitSpecialization);
1033   Result->setMayHaveOutOfDateDef(false);
1034
1035   Context.getInjectedClassNameType(Result, CanonInjectedType);
1036   return Result;
1037 }
1038
1039 ClassTemplatePartialSpecializationDecl *
1040 ClassTemplatePartialSpecializationDecl::CreateDeserialized(ASTContext &C,
1041                                                            unsigned ID) {
1042   auto *Result = new (C, ID) ClassTemplatePartialSpecializationDecl(C);
1043   Result->setMayHaveOutOfDateDef(false);
1044   return Result;
1045 }
1046
1047 //===----------------------------------------------------------------------===//
1048 // FriendTemplateDecl Implementation
1049 //===----------------------------------------------------------------------===//
1050
1051 void FriendTemplateDecl::anchor() {}
1052
1053 FriendTemplateDecl *
1054 FriendTemplateDecl::Create(ASTContext &Context, DeclContext *DC,
1055                            SourceLocation L,
1056                            MutableArrayRef<TemplateParameterList *> Params,
1057                            FriendUnion Friend, SourceLocation FLoc) {
1058   return new (Context, DC) FriendTemplateDecl(DC, L, Params, Friend, FLoc);
1059 }
1060
1061 FriendTemplateDecl *FriendTemplateDecl::CreateDeserialized(ASTContext &C,
1062                                                            unsigned ID) {
1063   return new (C, ID) FriendTemplateDecl(EmptyShell());
1064 }
1065
1066 //===----------------------------------------------------------------------===//
1067 // TypeAliasTemplateDecl Implementation
1068 //===----------------------------------------------------------------------===//
1069
1070 TypeAliasTemplateDecl *TypeAliasTemplateDecl::Create(ASTContext &C,
1071                                                      DeclContext *DC,
1072                                                      SourceLocation L,
1073                                                      DeclarationName Name,
1074                                                   TemplateParameterList *Params,
1075                                                      NamedDecl *Decl) {
1076   AdoptTemplateParameterList(Params, DC);
1077   return new (C, DC) TypeAliasTemplateDecl(C, DC, L, Name, Params, Decl);
1078 }
1079
1080 TypeAliasTemplateDecl *TypeAliasTemplateDecl::CreateDeserialized(ASTContext &C,
1081                                                                  unsigned ID) {
1082   return new (C, ID) TypeAliasTemplateDecl(C, nullptr, SourceLocation(),
1083                                            DeclarationName(), nullptr, nullptr);
1084 }
1085
1086 RedeclarableTemplateDecl::CommonBase *
1087 TypeAliasTemplateDecl::newCommon(ASTContext &C) const {
1088   auto *CommonPtr = new (C) Common;
1089   C.addDestruction(CommonPtr);
1090   return CommonPtr;
1091 }
1092
1093 //===----------------------------------------------------------------------===//
1094 // ClassScopeFunctionSpecializationDecl Implementation
1095 //===----------------------------------------------------------------------===//
1096
1097 void ClassScopeFunctionSpecializationDecl::anchor() {}
1098
1099 ClassScopeFunctionSpecializationDecl *
1100 ClassScopeFunctionSpecializationDecl::CreateDeserialized(ASTContext &C,
1101                                                          unsigned ID) {
1102   return new (C, ID) ClassScopeFunctionSpecializationDecl(
1103       nullptr, SourceLocation(), nullptr, nullptr);
1104 }
1105
1106 //===----------------------------------------------------------------------===//
1107 // VarTemplateDecl Implementation
1108 //===----------------------------------------------------------------------===//
1109
1110 VarTemplateDecl *VarTemplateDecl::getDefinition() {
1111   VarTemplateDecl *CurD = this;
1112   while (CurD) {
1113     if (CurD->isThisDeclarationADefinition())
1114       return CurD;
1115     CurD = CurD->getPreviousDecl();
1116   }
1117   return nullptr;
1118 }
1119
1120 VarTemplateDecl *VarTemplateDecl::Create(ASTContext &C, DeclContext *DC,
1121                                          SourceLocation L, DeclarationName Name,
1122                                          TemplateParameterList *Params,
1123                                          VarDecl *Decl) {
1124   AdoptTemplateParameterList(Params, DC);
1125   return new (C, DC) VarTemplateDecl(C, DC, L, Name, Params, Decl);
1126 }
1127
1128 VarTemplateDecl *VarTemplateDecl::CreateDeserialized(ASTContext &C,
1129                                                      unsigned ID) {
1130   return new (C, ID) VarTemplateDecl(C, nullptr, SourceLocation(),
1131                                      DeclarationName(), nullptr, nullptr);
1132 }
1133
1134 void VarTemplateDecl::LoadLazySpecializations() const {
1135   loadLazySpecializationsImpl();
1136 }
1137
1138 llvm::FoldingSetVector<VarTemplateSpecializationDecl> &
1139 VarTemplateDecl::getSpecializations() const {
1140   LoadLazySpecializations();
1141   return getCommonPtr()->Specializations;
1142 }
1143
1144 llvm::FoldingSetVector<VarTemplatePartialSpecializationDecl> &
1145 VarTemplateDecl::getPartialSpecializations() {
1146   LoadLazySpecializations();
1147   return getCommonPtr()->PartialSpecializations;
1148 }
1149
1150 RedeclarableTemplateDecl::CommonBase *
1151 VarTemplateDecl::newCommon(ASTContext &C) const {
1152   auto *CommonPtr = new (C) Common;
1153   C.addDestruction(CommonPtr);
1154   return CommonPtr;
1155 }
1156
1157 VarTemplateSpecializationDecl *
1158 VarTemplateDecl::findSpecialization(ArrayRef<TemplateArgument> Args,
1159                                     void *&InsertPos) {
1160   return findSpecializationImpl(getSpecializations(), InsertPos, Args);
1161 }
1162
1163 void VarTemplateDecl::AddSpecialization(VarTemplateSpecializationDecl *D,
1164                                         void *InsertPos) {
1165   addSpecializationImpl<VarTemplateDecl>(getSpecializations(), D, InsertPos);
1166 }
1167
1168 VarTemplatePartialSpecializationDecl *
1169 VarTemplateDecl::findPartialSpecialization(ArrayRef<TemplateArgument> Args,
1170      TemplateParameterList *TPL, void *&InsertPos) {
1171   return findSpecializationImpl(getPartialSpecializations(), InsertPos, Args,
1172                                 TPL);
1173 }
1174
1175 void
1176 VarTemplatePartialSpecializationDecl::Profile(llvm::FoldingSetNodeID &ID,
1177     ArrayRef<TemplateArgument> TemplateArgs, TemplateParameterList *TPL,
1178     ASTContext &Context) {
1179   ID.AddInteger(TemplateArgs.size());
1180   for (const TemplateArgument &TemplateArg : TemplateArgs)
1181     TemplateArg.Profile(ID, Context);
1182   ProfileTemplateParameterList(Context, ID, TPL);
1183 }
1184
1185 void VarTemplateDecl::AddPartialSpecialization(
1186     VarTemplatePartialSpecializationDecl *D, void *InsertPos) {
1187   if (InsertPos)
1188     getPartialSpecializations().InsertNode(D, InsertPos);
1189   else {
1190     VarTemplatePartialSpecializationDecl *Existing =
1191         getPartialSpecializations().GetOrInsertNode(D);
1192     (void)Existing;
1193     assert(Existing->isCanonicalDecl() && "Non-canonical specialization?");
1194   }
1195
1196   if (ASTMutationListener *L = getASTMutationListener())
1197     L->AddedCXXTemplateSpecialization(this, D);
1198 }
1199
1200 void VarTemplateDecl::getPartialSpecializations(
1201     SmallVectorImpl<VarTemplatePartialSpecializationDecl *> &PS) {
1202   llvm::FoldingSetVector<VarTemplatePartialSpecializationDecl> &PartialSpecs =
1203       getPartialSpecializations();
1204   PS.clear();
1205   PS.reserve(PartialSpecs.size());
1206   for (VarTemplatePartialSpecializationDecl &P : PartialSpecs)
1207     PS.push_back(P.getMostRecentDecl());
1208 }
1209
1210 VarTemplatePartialSpecializationDecl *
1211 VarTemplateDecl::findPartialSpecInstantiatedFromMember(
1212     VarTemplatePartialSpecializationDecl *D) {
1213   Decl *DCanon = D->getCanonicalDecl();
1214   for (VarTemplatePartialSpecializationDecl &P : getPartialSpecializations()) {
1215     if (P.getInstantiatedFromMember()->getCanonicalDecl() == DCanon)
1216       return P.getMostRecentDecl();
1217   }
1218
1219   return nullptr;
1220 }
1221
1222 //===----------------------------------------------------------------------===//
1223 // VarTemplateSpecializationDecl Implementation
1224 //===----------------------------------------------------------------------===//
1225
1226 VarTemplateSpecializationDecl::VarTemplateSpecializationDecl(
1227     Kind DK, ASTContext &Context, DeclContext *DC, SourceLocation StartLoc,
1228     SourceLocation IdLoc, VarTemplateDecl *SpecializedTemplate, QualType T,
1229     TypeSourceInfo *TInfo, StorageClass S, ArrayRef<TemplateArgument> Args)
1230     : VarDecl(DK, Context, DC, StartLoc, IdLoc,
1231               SpecializedTemplate->getIdentifier(), T, TInfo, S),
1232       SpecializedTemplate(SpecializedTemplate),
1233       TemplateArgs(TemplateArgumentList::CreateCopy(Context, Args)),
1234       SpecializationKind(TSK_Undeclared), IsCompleteDefinition(false) {}
1235
1236 VarTemplateSpecializationDecl::VarTemplateSpecializationDecl(Kind DK,
1237                                                              ASTContext &C)
1238     : VarDecl(DK, C, nullptr, SourceLocation(), SourceLocation(), nullptr,
1239               QualType(), nullptr, SC_None),
1240       SpecializationKind(TSK_Undeclared), IsCompleteDefinition(false) {}
1241
1242 VarTemplateSpecializationDecl *VarTemplateSpecializationDecl::Create(
1243     ASTContext &Context, DeclContext *DC, SourceLocation StartLoc,
1244     SourceLocation IdLoc, VarTemplateDecl *SpecializedTemplate, QualType T,
1245     TypeSourceInfo *TInfo, StorageClass S, ArrayRef<TemplateArgument> Args) {
1246   return new (Context, DC) VarTemplateSpecializationDecl(
1247       VarTemplateSpecialization, Context, DC, StartLoc, IdLoc,
1248       SpecializedTemplate, T, TInfo, S, Args);
1249 }
1250
1251 VarTemplateSpecializationDecl *
1252 VarTemplateSpecializationDecl::CreateDeserialized(ASTContext &C, unsigned ID) {
1253   return new (C, ID)
1254       VarTemplateSpecializationDecl(VarTemplateSpecialization, C);
1255 }
1256
1257 void VarTemplateSpecializationDecl::getNameForDiagnostic(
1258     raw_ostream &OS, const PrintingPolicy &Policy, bool Qualified) const {
1259   NamedDecl::getNameForDiagnostic(OS, Policy, Qualified);
1260
1261   const auto *PS = dyn_cast<VarTemplatePartialSpecializationDecl>(this);
1262   if (const ASTTemplateArgumentListInfo *ArgsAsWritten =
1263           PS ? PS->getTemplateArgsAsWritten() : nullptr) {
1264     printTemplateArgumentList(OS, ArgsAsWritten->arguments(), Policy);
1265   } else {
1266     const TemplateArgumentList &TemplateArgs = getTemplateArgs();
1267     printTemplateArgumentList(OS, TemplateArgs.asArray(), Policy);
1268   }
1269 }
1270
1271 VarTemplateDecl *VarTemplateSpecializationDecl::getSpecializedTemplate() const {
1272   if (const auto *PartialSpec =
1273           SpecializedTemplate.dyn_cast<SpecializedPartialSpecialization *>())
1274     return PartialSpec->PartialSpecialization->getSpecializedTemplate();
1275   return SpecializedTemplate.get<VarTemplateDecl *>();
1276 }
1277
1278 void VarTemplateSpecializationDecl::setTemplateArgsInfo(
1279     const TemplateArgumentListInfo &ArgsInfo) {
1280   TemplateArgsInfo.setLAngleLoc(ArgsInfo.getLAngleLoc());
1281   TemplateArgsInfo.setRAngleLoc(ArgsInfo.getRAngleLoc());
1282   for (const TemplateArgumentLoc &Loc : ArgsInfo.arguments())
1283     TemplateArgsInfo.addArgument(Loc);
1284 }
1285
1286 //===----------------------------------------------------------------------===//
1287 // VarTemplatePartialSpecializationDecl Implementation
1288 //===----------------------------------------------------------------------===//
1289
1290 void VarTemplatePartialSpecializationDecl::anchor() {}
1291
1292 VarTemplatePartialSpecializationDecl::VarTemplatePartialSpecializationDecl(
1293     ASTContext &Context, DeclContext *DC, SourceLocation StartLoc,
1294     SourceLocation IdLoc, TemplateParameterList *Params,
1295     VarTemplateDecl *SpecializedTemplate, QualType T, TypeSourceInfo *TInfo,
1296     StorageClass S, ArrayRef<TemplateArgument> Args,
1297     const ASTTemplateArgumentListInfo *ArgInfos)
1298     : VarTemplateSpecializationDecl(VarTemplatePartialSpecialization, Context,
1299                                     DC, StartLoc, IdLoc, SpecializedTemplate, T,
1300                                     TInfo, S, Args),
1301       TemplateParams(Params), ArgsAsWritten(ArgInfos),
1302       InstantiatedFromMember(nullptr, false) {
1303   // TODO: The template parameters should be in DC by now. Verify.
1304   // AdoptTemplateParameterList(Params, DC);
1305 }
1306
1307 VarTemplatePartialSpecializationDecl *
1308 VarTemplatePartialSpecializationDecl::Create(
1309     ASTContext &Context, DeclContext *DC, SourceLocation StartLoc,
1310     SourceLocation IdLoc, TemplateParameterList *Params,
1311     VarTemplateDecl *SpecializedTemplate, QualType T, TypeSourceInfo *TInfo,
1312     StorageClass S, ArrayRef<TemplateArgument> Args,
1313     const TemplateArgumentListInfo &ArgInfos) {
1314   const ASTTemplateArgumentListInfo *ASTArgInfos
1315     = ASTTemplateArgumentListInfo::Create(Context, ArgInfos);
1316
1317   auto *Result =
1318       new (Context, DC) VarTemplatePartialSpecializationDecl(
1319           Context, DC, StartLoc, IdLoc, Params, SpecializedTemplate, T, TInfo,
1320           S, Args, ASTArgInfos);
1321   Result->setSpecializationKind(TSK_ExplicitSpecialization);
1322   return Result;
1323 }
1324
1325 VarTemplatePartialSpecializationDecl *
1326 VarTemplatePartialSpecializationDecl::CreateDeserialized(ASTContext &C,
1327                                                          unsigned ID) {
1328   return new (C, ID) VarTemplatePartialSpecializationDecl(C);
1329 }
1330
1331 static TemplateParameterList *
1332 createMakeIntegerSeqParameterList(const ASTContext &C, DeclContext *DC) {
1333   // typename T
1334   auto *T = TemplateTypeParmDecl::Create(
1335       C, DC, SourceLocation(), SourceLocation(), /*Depth=*/1, /*Position=*/0,
1336       /*Id=*/nullptr, /*Typename=*/true, /*ParameterPack=*/false,
1337       /*HasTypeConstraint=*/false);
1338   T->setImplicit(true);
1339
1340   // T ...Ints
1341   TypeSourceInfo *TI =
1342       C.getTrivialTypeSourceInfo(QualType(T->getTypeForDecl(), 0));
1343   auto *N = NonTypeTemplateParmDecl::Create(
1344       C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/1,
1345       /*Id=*/nullptr, TI->getType(), /*ParameterPack=*/true, TI);
1346   N->setImplicit(true);
1347
1348   // <typename T, T ...Ints>
1349   NamedDecl *P[2] = {T, N};
1350   auto *TPL = TemplateParameterList::Create(
1351       C, SourceLocation(), SourceLocation(), P, SourceLocation(), nullptr);
1352
1353   // template <typename T, ...Ints> class IntSeq
1354   auto *TemplateTemplateParm = TemplateTemplateParmDecl::Create(
1355       C, DC, SourceLocation(), /*Depth=*/0, /*Position=*/0,
1356       /*ParameterPack=*/false, /*Id=*/nullptr, TPL);
1357   TemplateTemplateParm->setImplicit(true);
1358
1359   // typename T
1360   auto *TemplateTypeParm = TemplateTypeParmDecl::Create(
1361       C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/1,
1362       /*Id=*/nullptr, /*Typename=*/true, /*ParameterPack=*/false,
1363       /*HasTypeConstraint=*/false);
1364   TemplateTypeParm->setImplicit(true);
1365
1366   // T N
1367   TypeSourceInfo *TInfo = C.getTrivialTypeSourceInfo(
1368       QualType(TemplateTypeParm->getTypeForDecl(), 0));
1369   auto *NonTypeTemplateParm = NonTypeTemplateParmDecl::Create(
1370       C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/2,
1371       /*Id=*/nullptr, TInfo->getType(), /*ParameterPack=*/false, TInfo);
1372   NamedDecl *Params[] = {TemplateTemplateParm, TemplateTypeParm,
1373                          NonTypeTemplateParm};
1374
1375   // template <template <typename T, T ...Ints> class IntSeq, typename T, T N>
1376   return TemplateParameterList::Create(C, SourceLocation(), SourceLocation(),
1377                                        Params, SourceLocation(), nullptr);
1378 }
1379
1380 static TemplateParameterList *
1381 createTypePackElementParameterList(const ASTContext &C, DeclContext *DC) {
1382   // std::size_t Index
1383   TypeSourceInfo *TInfo = C.getTrivialTypeSourceInfo(C.getSizeType());
1384   auto *Index = NonTypeTemplateParmDecl::Create(
1385       C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/0,
1386       /*Id=*/nullptr, TInfo->getType(), /*ParameterPack=*/false, TInfo);
1387
1388   // typename ...T
1389   auto *Ts = TemplateTypeParmDecl::Create(
1390       C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/1,
1391       /*Id=*/nullptr, /*Typename=*/true, /*ParameterPack=*/true,
1392       /*HasTypeConstraint=*/false);
1393   Ts->setImplicit(true);
1394
1395   // template <std::size_t Index, typename ...T>
1396   NamedDecl *Params[] = {Index, Ts};
1397   return TemplateParameterList::Create(C, SourceLocation(), SourceLocation(),
1398                                        llvm::makeArrayRef(Params),
1399                                        SourceLocation(), nullptr);
1400 }
1401
1402 static TemplateParameterList *createBuiltinTemplateParameterList(
1403     const ASTContext &C, DeclContext *DC, BuiltinTemplateKind BTK) {
1404   switch (BTK) {
1405   case BTK__make_integer_seq:
1406     return createMakeIntegerSeqParameterList(C, DC);
1407   case BTK__type_pack_element:
1408     return createTypePackElementParameterList(C, DC);
1409   }
1410
1411   llvm_unreachable("unhandled BuiltinTemplateKind!");
1412 }
1413
1414 void BuiltinTemplateDecl::anchor() {}
1415
1416 BuiltinTemplateDecl::BuiltinTemplateDecl(const ASTContext &C, DeclContext *DC,
1417                                          DeclarationName Name,
1418                                          BuiltinTemplateKind BTK)
1419     : TemplateDecl(BuiltinTemplate, DC, SourceLocation(), Name,
1420                    createBuiltinTemplateParameterList(C, DC, BTK)),
1421       BTK(BTK) {}
1422
1423 void TypeConstraint::print(llvm::raw_ostream &OS, PrintingPolicy Policy) const {
1424   if (NestedNameSpec)
1425     NestedNameSpec.getNestedNameSpecifier()->print(OS, Policy);
1426   ConceptName.printName(OS, Policy);
1427   if (hasExplicitTemplateArgs()) {
1428     OS << "<";
1429     for (auto &ArgLoc : ArgsAsWritten->arguments())
1430       ArgLoc.getArgument().print(Policy, OS);
1431     OS << ">";
1432   }
1433 }