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