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() const {
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) const {
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().CPlusPlus20 ? 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(
918         OS, ArgsAsWritten->arguments(), Policy,
919         getSpecializedTemplate()->getTemplateParameters());
920   } else {
921     const TemplateArgumentList &TemplateArgs = getTemplateArgs();
922     printTemplateArgumentList(
923         OS, TemplateArgs.asArray(), Policy,
924         getSpecializedTemplate()->getTemplateParameters());
925   }
926 }
927 
928 ClassTemplateDecl *
929 ClassTemplateSpecializationDecl::getSpecializedTemplate() const {
930   if (const auto *PartialSpec =
931           SpecializedTemplate.dyn_cast<SpecializedPartialSpecialization*>())
932     return PartialSpec->PartialSpecialization->getSpecializedTemplate();
933   return SpecializedTemplate.get<ClassTemplateDecl*>();
934 }
935 
936 SourceRange
937 ClassTemplateSpecializationDecl::getSourceRange() const {
938   if (ExplicitInfo) {
939     SourceLocation Begin = getTemplateKeywordLoc();
940     if (Begin.isValid()) {
941       // Here we have an explicit (partial) specialization or instantiation.
942       assert(getSpecializationKind() == TSK_ExplicitSpecialization ||
943              getSpecializationKind() == TSK_ExplicitInstantiationDeclaration ||
944              getSpecializationKind() == TSK_ExplicitInstantiationDefinition);
945       if (getExternLoc().isValid())
946         Begin = getExternLoc();
947       SourceLocation End = getBraceRange().getEnd();
948       if (End.isInvalid())
949         End = getTypeAsWritten()->getTypeLoc().getEndLoc();
950       return SourceRange(Begin, End);
951     }
952     // An implicit instantiation of a class template partial specialization
953     // uses ExplicitInfo to record the TypeAsWritten, but the source
954     // locations should be retrieved from the instantiation pattern.
955     using CTPSDecl = ClassTemplatePartialSpecializationDecl;
956     auto *ctpsd = const_cast<CTPSDecl *>(cast<CTPSDecl>(this));
957     CTPSDecl *inst_from = ctpsd->getInstantiatedFromMember();
958     assert(inst_from != nullptr);
959     return inst_from->getSourceRange();
960   }
961   else {
962     // No explicit info available.
963     llvm::PointerUnion<ClassTemplateDecl *,
964                        ClassTemplatePartialSpecializationDecl *>
965       inst_from = getInstantiatedFrom();
966     if (inst_from.isNull())
967       return getSpecializedTemplate()->getSourceRange();
968     if (const auto *ctd = inst_from.dyn_cast<ClassTemplateDecl *>())
969       return ctd->getSourceRange();
970     return inst_from.get<ClassTemplatePartialSpecializationDecl *>()
971       ->getSourceRange();
972   }
973 }
974 
975 //===----------------------------------------------------------------------===//
976 // ConceptDecl Implementation
977 //===----------------------------------------------------------------------===//
978 ConceptDecl *ConceptDecl::Create(ASTContext &C, DeclContext *DC,
979                                  SourceLocation L, DeclarationName Name,
980                                  TemplateParameterList *Params,
981                                  Expr *ConstraintExpr) {
982   AdoptTemplateParameterList(Params, DC);
983   return new (C, DC) ConceptDecl(DC, L, Name, Params, ConstraintExpr);
984 }
985 
986 ConceptDecl *ConceptDecl::CreateDeserialized(ASTContext &C,
987                                              unsigned ID) {
988   ConceptDecl *Result = new (C, ID) ConceptDecl(nullptr, SourceLocation(),
989                                                 DeclarationName(),
990                                                 nullptr, nullptr);
991 
992   return Result;
993 }
994 
995 //===----------------------------------------------------------------------===//
996 // ClassTemplatePartialSpecializationDecl Implementation
997 //===----------------------------------------------------------------------===//
998 void ClassTemplatePartialSpecializationDecl::anchor() {}
999 
1000 ClassTemplatePartialSpecializationDecl::
1001 ClassTemplatePartialSpecializationDecl(ASTContext &Context, TagKind TK,
1002                                        DeclContext *DC,
1003                                        SourceLocation StartLoc,
1004                                        SourceLocation IdLoc,
1005                                        TemplateParameterList *Params,
1006                                        ClassTemplateDecl *SpecializedTemplate,
1007                                        ArrayRef<TemplateArgument> Args,
1008                                const ASTTemplateArgumentListInfo *ArgInfos,
1009                                ClassTemplatePartialSpecializationDecl *PrevDecl)
1010     : ClassTemplateSpecializationDecl(Context,
1011                                       ClassTemplatePartialSpecialization,
1012                                       TK, DC, StartLoc, IdLoc,
1013                                       SpecializedTemplate, Args, PrevDecl),
1014       TemplateParams(Params), ArgsAsWritten(ArgInfos),
1015       InstantiatedFromMember(nullptr, false) {
1016   AdoptTemplateParameterList(Params, this);
1017 }
1018 
1019 ClassTemplatePartialSpecializationDecl *
1020 ClassTemplatePartialSpecializationDecl::
1021 Create(ASTContext &Context, TagKind TK,DeclContext *DC,
1022        SourceLocation StartLoc, SourceLocation IdLoc,
1023        TemplateParameterList *Params,
1024        ClassTemplateDecl *SpecializedTemplate,
1025        ArrayRef<TemplateArgument> Args,
1026        const TemplateArgumentListInfo &ArgInfos,
1027        QualType CanonInjectedType,
1028        ClassTemplatePartialSpecializationDecl *PrevDecl) {
1029   const ASTTemplateArgumentListInfo *ASTArgInfos =
1030     ASTTemplateArgumentListInfo::Create(Context, ArgInfos);
1031 
1032   auto *Result = new (Context, DC)
1033       ClassTemplatePartialSpecializationDecl(Context, TK, DC, StartLoc, IdLoc,
1034                                              Params, SpecializedTemplate, Args,
1035                                              ASTArgInfos, PrevDecl);
1036   Result->setSpecializationKind(TSK_ExplicitSpecialization);
1037   Result->setMayHaveOutOfDateDef(false);
1038 
1039   Context.getInjectedClassNameType(Result, CanonInjectedType);
1040   return Result;
1041 }
1042 
1043 ClassTemplatePartialSpecializationDecl *
1044 ClassTemplatePartialSpecializationDecl::CreateDeserialized(ASTContext &C,
1045                                                            unsigned ID) {
1046   auto *Result = new (C, ID) ClassTemplatePartialSpecializationDecl(C);
1047   Result->setMayHaveOutOfDateDef(false);
1048   return Result;
1049 }
1050 
1051 //===----------------------------------------------------------------------===//
1052 // FriendTemplateDecl Implementation
1053 //===----------------------------------------------------------------------===//
1054 
1055 void FriendTemplateDecl::anchor() {}
1056 
1057 FriendTemplateDecl *
1058 FriendTemplateDecl::Create(ASTContext &Context, DeclContext *DC,
1059                            SourceLocation L,
1060                            MutableArrayRef<TemplateParameterList *> Params,
1061                            FriendUnion Friend, SourceLocation FLoc) {
1062   return new (Context, DC) FriendTemplateDecl(DC, L, Params, Friend, FLoc);
1063 }
1064 
1065 FriendTemplateDecl *FriendTemplateDecl::CreateDeserialized(ASTContext &C,
1066                                                            unsigned ID) {
1067   return new (C, ID) FriendTemplateDecl(EmptyShell());
1068 }
1069 
1070 //===----------------------------------------------------------------------===//
1071 // TypeAliasTemplateDecl Implementation
1072 //===----------------------------------------------------------------------===//
1073 
1074 TypeAliasTemplateDecl *TypeAliasTemplateDecl::Create(ASTContext &C,
1075                                                      DeclContext *DC,
1076                                                      SourceLocation L,
1077                                                      DeclarationName Name,
1078                                                   TemplateParameterList *Params,
1079                                                      NamedDecl *Decl) {
1080   AdoptTemplateParameterList(Params, DC);
1081   return new (C, DC) TypeAliasTemplateDecl(C, DC, L, Name, Params, Decl);
1082 }
1083 
1084 TypeAliasTemplateDecl *TypeAliasTemplateDecl::CreateDeserialized(ASTContext &C,
1085                                                                  unsigned ID) {
1086   return new (C, ID) TypeAliasTemplateDecl(C, nullptr, SourceLocation(),
1087                                            DeclarationName(), nullptr, nullptr);
1088 }
1089 
1090 RedeclarableTemplateDecl::CommonBase *
1091 TypeAliasTemplateDecl::newCommon(ASTContext &C) const {
1092   auto *CommonPtr = new (C) Common;
1093   C.addDestruction(CommonPtr);
1094   return CommonPtr;
1095 }
1096 
1097 //===----------------------------------------------------------------------===//
1098 // ClassScopeFunctionSpecializationDecl Implementation
1099 //===----------------------------------------------------------------------===//
1100 
1101 void ClassScopeFunctionSpecializationDecl::anchor() {}
1102 
1103 ClassScopeFunctionSpecializationDecl *
1104 ClassScopeFunctionSpecializationDecl::CreateDeserialized(ASTContext &C,
1105                                                          unsigned ID) {
1106   return new (C, ID) ClassScopeFunctionSpecializationDecl(
1107       nullptr, SourceLocation(), nullptr, nullptr);
1108 }
1109 
1110 //===----------------------------------------------------------------------===//
1111 // VarTemplateDecl Implementation
1112 //===----------------------------------------------------------------------===//
1113 
1114 VarTemplateDecl *VarTemplateDecl::getDefinition() {
1115   VarTemplateDecl *CurD = this;
1116   while (CurD) {
1117     if (CurD->isThisDeclarationADefinition())
1118       return CurD;
1119     CurD = CurD->getPreviousDecl();
1120   }
1121   return nullptr;
1122 }
1123 
1124 VarTemplateDecl *VarTemplateDecl::Create(ASTContext &C, DeclContext *DC,
1125                                          SourceLocation L, DeclarationName Name,
1126                                          TemplateParameterList *Params,
1127                                          VarDecl *Decl) {
1128   AdoptTemplateParameterList(Params, DC);
1129   return new (C, DC) VarTemplateDecl(C, DC, L, Name, Params, Decl);
1130 }
1131 
1132 VarTemplateDecl *VarTemplateDecl::CreateDeserialized(ASTContext &C,
1133                                                      unsigned ID) {
1134   return new (C, ID) VarTemplateDecl(C, nullptr, SourceLocation(),
1135                                      DeclarationName(), nullptr, nullptr);
1136 }
1137 
1138 void VarTemplateDecl::LoadLazySpecializations() const {
1139   loadLazySpecializationsImpl();
1140 }
1141 
1142 llvm::FoldingSetVector<VarTemplateSpecializationDecl> &
1143 VarTemplateDecl::getSpecializations() const {
1144   LoadLazySpecializations();
1145   return getCommonPtr()->Specializations;
1146 }
1147 
1148 llvm::FoldingSetVector<VarTemplatePartialSpecializationDecl> &
1149 VarTemplateDecl::getPartialSpecializations() const {
1150   LoadLazySpecializations();
1151   return getCommonPtr()->PartialSpecializations;
1152 }
1153 
1154 RedeclarableTemplateDecl::CommonBase *
1155 VarTemplateDecl::newCommon(ASTContext &C) const {
1156   auto *CommonPtr = new (C) Common;
1157   C.addDestruction(CommonPtr);
1158   return CommonPtr;
1159 }
1160 
1161 VarTemplateSpecializationDecl *
1162 VarTemplateDecl::findSpecialization(ArrayRef<TemplateArgument> Args,
1163                                     void *&InsertPos) {
1164   return findSpecializationImpl(getSpecializations(), InsertPos, Args);
1165 }
1166 
1167 void VarTemplateDecl::AddSpecialization(VarTemplateSpecializationDecl *D,
1168                                         void *InsertPos) {
1169   addSpecializationImpl<VarTemplateDecl>(getSpecializations(), D, InsertPos);
1170 }
1171 
1172 VarTemplatePartialSpecializationDecl *
1173 VarTemplateDecl::findPartialSpecialization(ArrayRef<TemplateArgument> Args,
1174      TemplateParameterList *TPL, void *&InsertPos) {
1175   return findSpecializationImpl(getPartialSpecializations(), InsertPos, Args,
1176                                 TPL);
1177 }
1178 
1179 void
1180 VarTemplatePartialSpecializationDecl::Profile(llvm::FoldingSetNodeID &ID,
1181     ArrayRef<TemplateArgument> TemplateArgs, TemplateParameterList *TPL,
1182     ASTContext &Context) {
1183   ID.AddInteger(TemplateArgs.size());
1184   for (const TemplateArgument &TemplateArg : TemplateArgs)
1185     TemplateArg.Profile(ID, Context);
1186   ProfileTemplateParameterList(Context, ID, TPL);
1187 }
1188 
1189 void VarTemplateDecl::AddPartialSpecialization(
1190     VarTemplatePartialSpecializationDecl *D, void *InsertPos) {
1191   if (InsertPos)
1192     getPartialSpecializations().InsertNode(D, InsertPos);
1193   else {
1194     VarTemplatePartialSpecializationDecl *Existing =
1195         getPartialSpecializations().GetOrInsertNode(D);
1196     (void)Existing;
1197     assert(Existing->isCanonicalDecl() && "Non-canonical specialization?");
1198   }
1199 
1200   if (ASTMutationListener *L = getASTMutationListener())
1201     L->AddedCXXTemplateSpecialization(this, D);
1202 }
1203 
1204 void VarTemplateDecl::getPartialSpecializations(
1205     SmallVectorImpl<VarTemplatePartialSpecializationDecl *> &PS) const {
1206   llvm::FoldingSetVector<VarTemplatePartialSpecializationDecl> &PartialSpecs =
1207       getPartialSpecializations();
1208   PS.clear();
1209   PS.reserve(PartialSpecs.size());
1210   for (VarTemplatePartialSpecializationDecl &P : PartialSpecs)
1211     PS.push_back(P.getMostRecentDecl());
1212 }
1213 
1214 VarTemplatePartialSpecializationDecl *
1215 VarTemplateDecl::findPartialSpecInstantiatedFromMember(
1216     VarTemplatePartialSpecializationDecl *D) {
1217   Decl *DCanon = D->getCanonicalDecl();
1218   for (VarTemplatePartialSpecializationDecl &P : getPartialSpecializations()) {
1219     if (P.getInstantiatedFromMember()->getCanonicalDecl() == DCanon)
1220       return P.getMostRecentDecl();
1221   }
1222 
1223   return nullptr;
1224 }
1225 
1226 //===----------------------------------------------------------------------===//
1227 // VarTemplateSpecializationDecl Implementation
1228 //===----------------------------------------------------------------------===//
1229 
1230 VarTemplateSpecializationDecl::VarTemplateSpecializationDecl(
1231     Kind DK, ASTContext &Context, DeclContext *DC, SourceLocation StartLoc,
1232     SourceLocation IdLoc, VarTemplateDecl *SpecializedTemplate, QualType T,
1233     TypeSourceInfo *TInfo, StorageClass S, ArrayRef<TemplateArgument> Args)
1234     : VarDecl(DK, Context, DC, StartLoc, IdLoc,
1235               SpecializedTemplate->getIdentifier(), T, TInfo, S),
1236       SpecializedTemplate(SpecializedTemplate),
1237       TemplateArgs(TemplateArgumentList::CreateCopy(Context, Args)),
1238       SpecializationKind(TSK_Undeclared), IsCompleteDefinition(false) {}
1239 
1240 VarTemplateSpecializationDecl::VarTemplateSpecializationDecl(Kind DK,
1241                                                              ASTContext &C)
1242     : VarDecl(DK, C, nullptr, SourceLocation(), SourceLocation(), nullptr,
1243               QualType(), nullptr, SC_None),
1244       SpecializationKind(TSK_Undeclared), IsCompleteDefinition(false) {}
1245 
1246 VarTemplateSpecializationDecl *VarTemplateSpecializationDecl::Create(
1247     ASTContext &Context, DeclContext *DC, SourceLocation StartLoc,
1248     SourceLocation IdLoc, VarTemplateDecl *SpecializedTemplate, QualType T,
1249     TypeSourceInfo *TInfo, StorageClass S, ArrayRef<TemplateArgument> Args) {
1250   return new (Context, DC) VarTemplateSpecializationDecl(
1251       VarTemplateSpecialization, Context, DC, StartLoc, IdLoc,
1252       SpecializedTemplate, T, TInfo, S, Args);
1253 }
1254 
1255 VarTemplateSpecializationDecl *
1256 VarTemplateSpecializationDecl::CreateDeserialized(ASTContext &C, unsigned ID) {
1257   return new (C, ID)
1258       VarTemplateSpecializationDecl(VarTemplateSpecialization, C);
1259 }
1260 
1261 void VarTemplateSpecializationDecl::getNameForDiagnostic(
1262     raw_ostream &OS, const PrintingPolicy &Policy, bool Qualified) const {
1263   NamedDecl::getNameForDiagnostic(OS, Policy, Qualified);
1264 
1265   const auto *PS = dyn_cast<VarTemplatePartialSpecializationDecl>(this);
1266   if (const ASTTemplateArgumentListInfo *ArgsAsWritten =
1267           PS ? PS->getTemplateArgsAsWritten() : nullptr) {
1268     printTemplateArgumentList(
1269         OS, ArgsAsWritten->arguments(), Policy,
1270         getSpecializedTemplate()->getTemplateParameters());
1271   } else {
1272     const TemplateArgumentList &TemplateArgs = getTemplateArgs();
1273     printTemplateArgumentList(
1274         OS, TemplateArgs.asArray(), Policy,
1275         getSpecializedTemplate()->getTemplateParameters());
1276   }
1277 }
1278 
1279 VarTemplateDecl *VarTemplateSpecializationDecl::getSpecializedTemplate() const {
1280   if (const auto *PartialSpec =
1281           SpecializedTemplate.dyn_cast<SpecializedPartialSpecialization *>())
1282     return PartialSpec->PartialSpecialization->getSpecializedTemplate();
1283   return SpecializedTemplate.get<VarTemplateDecl *>();
1284 }
1285 
1286 void VarTemplateSpecializationDecl::setTemplateArgsInfo(
1287     const TemplateArgumentListInfo &ArgsInfo) {
1288   TemplateArgsInfo.setLAngleLoc(ArgsInfo.getLAngleLoc());
1289   TemplateArgsInfo.setRAngleLoc(ArgsInfo.getRAngleLoc());
1290   for (const TemplateArgumentLoc &Loc : ArgsInfo.arguments())
1291     TemplateArgsInfo.addArgument(Loc);
1292 }
1293 
1294 //===----------------------------------------------------------------------===//
1295 // VarTemplatePartialSpecializationDecl Implementation
1296 //===----------------------------------------------------------------------===//
1297 
1298 void VarTemplatePartialSpecializationDecl::anchor() {}
1299 
1300 VarTemplatePartialSpecializationDecl::VarTemplatePartialSpecializationDecl(
1301     ASTContext &Context, DeclContext *DC, SourceLocation StartLoc,
1302     SourceLocation IdLoc, TemplateParameterList *Params,
1303     VarTemplateDecl *SpecializedTemplate, QualType T, TypeSourceInfo *TInfo,
1304     StorageClass S, ArrayRef<TemplateArgument> Args,
1305     const ASTTemplateArgumentListInfo *ArgInfos)
1306     : VarTemplateSpecializationDecl(VarTemplatePartialSpecialization, Context,
1307                                     DC, StartLoc, IdLoc, SpecializedTemplate, T,
1308                                     TInfo, S, Args),
1309       TemplateParams(Params), ArgsAsWritten(ArgInfos),
1310       InstantiatedFromMember(nullptr, false) {
1311   // TODO: The template parameters should be in DC by now. Verify.
1312   // AdoptTemplateParameterList(Params, DC);
1313 }
1314 
1315 VarTemplatePartialSpecializationDecl *
1316 VarTemplatePartialSpecializationDecl::Create(
1317     ASTContext &Context, DeclContext *DC, SourceLocation StartLoc,
1318     SourceLocation IdLoc, TemplateParameterList *Params,
1319     VarTemplateDecl *SpecializedTemplate, QualType T, TypeSourceInfo *TInfo,
1320     StorageClass S, ArrayRef<TemplateArgument> Args,
1321     const TemplateArgumentListInfo &ArgInfos) {
1322   const ASTTemplateArgumentListInfo *ASTArgInfos
1323     = ASTTemplateArgumentListInfo::Create(Context, ArgInfos);
1324 
1325   auto *Result =
1326       new (Context, DC) VarTemplatePartialSpecializationDecl(
1327           Context, DC, StartLoc, IdLoc, Params, SpecializedTemplate, T, TInfo,
1328           S, Args, ASTArgInfos);
1329   Result->setSpecializationKind(TSK_ExplicitSpecialization);
1330   return Result;
1331 }
1332 
1333 VarTemplatePartialSpecializationDecl *
1334 VarTemplatePartialSpecializationDecl::CreateDeserialized(ASTContext &C,
1335                                                          unsigned ID) {
1336   return new (C, ID) VarTemplatePartialSpecializationDecl(C);
1337 }
1338 
1339 static TemplateParameterList *
1340 createMakeIntegerSeqParameterList(const ASTContext &C, DeclContext *DC) {
1341   // typename T
1342   auto *T = TemplateTypeParmDecl::Create(
1343       C, DC, SourceLocation(), SourceLocation(), /*Depth=*/1, /*Position=*/0,
1344       /*Id=*/nullptr, /*Typename=*/true, /*ParameterPack=*/false,
1345       /*HasTypeConstraint=*/false);
1346   T->setImplicit(true);
1347 
1348   // T ...Ints
1349   TypeSourceInfo *TI =
1350       C.getTrivialTypeSourceInfo(QualType(T->getTypeForDecl(), 0));
1351   auto *N = NonTypeTemplateParmDecl::Create(
1352       C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/1,
1353       /*Id=*/nullptr, TI->getType(), /*ParameterPack=*/true, TI);
1354   N->setImplicit(true);
1355 
1356   // <typename T, T ...Ints>
1357   NamedDecl *P[2] = {T, N};
1358   auto *TPL = TemplateParameterList::Create(
1359       C, SourceLocation(), SourceLocation(), P, SourceLocation(), nullptr);
1360 
1361   // template <typename T, ...Ints> class IntSeq
1362   auto *TemplateTemplateParm = TemplateTemplateParmDecl::Create(
1363       C, DC, SourceLocation(), /*Depth=*/0, /*Position=*/0,
1364       /*ParameterPack=*/false, /*Id=*/nullptr, TPL);
1365   TemplateTemplateParm->setImplicit(true);
1366 
1367   // typename T
1368   auto *TemplateTypeParm = TemplateTypeParmDecl::Create(
1369       C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/1,
1370       /*Id=*/nullptr, /*Typename=*/true, /*ParameterPack=*/false,
1371       /*HasTypeConstraint=*/false);
1372   TemplateTypeParm->setImplicit(true);
1373 
1374   // T N
1375   TypeSourceInfo *TInfo = C.getTrivialTypeSourceInfo(
1376       QualType(TemplateTypeParm->getTypeForDecl(), 0));
1377   auto *NonTypeTemplateParm = NonTypeTemplateParmDecl::Create(
1378       C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/2,
1379       /*Id=*/nullptr, TInfo->getType(), /*ParameterPack=*/false, TInfo);
1380   NamedDecl *Params[] = {TemplateTemplateParm, TemplateTypeParm,
1381                          NonTypeTemplateParm};
1382 
1383   // template <template <typename T, T ...Ints> class IntSeq, typename T, T N>
1384   return TemplateParameterList::Create(C, SourceLocation(), SourceLocation(),
1385                                        Params, SourceLocation(), nullptr);
1386 }
1387 
1388 static TemplateParameterList *
1389 createTypePackElementParameterList(const ASTContext &C, DeclContext *DC) {
1390   // std::size_t Index
1391   TypeSourceInfo *TInfo = C.getTrivialTypeSourceInfo(C.getSizeType());
1392   auto *Index = NonTypeTemplateParmDecl::Create(
1393       C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/0,
1394       /*Id=*/nullptr, TInfo->getType(), /*ParameterPack=*/false, TInfo);
1395 
1396   // typename ...T
1397   auto *Ts = TemplateTypeParmDecl::Create(
1398       C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/1,
1399       /*Id=*/nullptr, /*Typename=*/true, /*ParameterPack=*/true,
1400       /*HasTypeConstraint=*/false);
1401   Ts->setImplicit(true);
1402 
1403   // template <std::size_t Index, typename ...T>
1404   NamedDecl *Params[] = {Index, Ts};
1405   return TemplateParameterList::Create(C, SourceLocation(), SourceLocation(),
1406                                        llvm::makeArrayRef(Params),
1407                                        SourceLocation(), nullptr);
1408 }
1409 
1410 static TemplateParameterList *createBuiltinTemplateParameterList(
1411     const ASTContext &C, DeclContext *DC, BuiltinTemplateKind BTK) {
1412   switch (BTK) {
1413   case BTK__make_integer_seq:
1414     return createMakeIntegerSeqParameterList(C, DC);
1415   case BTK__type_pack_element:
1416     return createTypePackElementParameterList(C, DC);
1417   }
1418 
1419   llvm_unreachable("unhandled BuiltinTemplateKind!");
1420 }
1421 
1422 void BuiltinTemplateDecl::anchor() {}
1423 
1424 BuiltinTemplateDecl::BuiltinTemplateDecl(const ASTContext &C, DeclContext *DC,
1425                                          DeclarationName Name,
1426                                          BuiltinTemplateKind BTK)
1427     : TemplateDecl(BuiltinTemplate, DC, SourceLocation(), Name,
1428                    createBuiltinTemplateParameterList(C, DC, BTK)),
1429       BTK(BTK) {}
1430 
1431 void TypeConstraint::print(llvm::raw_ostream &OS, PrintingPolicy Policy) const {
1432   if (NestedNameSpec)
1433     NestedNameSpec.getNestedNameSpecifier()->print(OS, Policy);
1434   ConceptName.printName(OS, Policy);
1435   if (hasExplicitTemplateArgs()) {
1436     OS << "<";
1437     for (auto &ArgLoc : ArgsAsWritten->arguments())
1438       ArgLoc.getArgument().print(Policy, OS);
1439     OS << ">";
1440   }
1441 }
1442 
1443 TemplateParamObjectDecl *TemplateParamObjectDecl::Create(const ASTContext &C,
1444                                                          QualType T,
1445                                                          const APValue &V) {
1446   DeclContext *DC = C.getTranslationUnitDecl();
1447   auto *TPOD = new (C, DC) TemplateParamObjectDecl(DC, T, V);
1448   C.addDestruction(&TPOD->Value);
1449   return TPOD;
1450 }
1451 
1452 TemplateParamObjectDecl *
1453 TemplateParamObjectDecl::CreateDeserialized(ASTContext &C, unsigned ID) {
1454   auto *TPOD = new (C, ID) TemplateParamObjectDecl(nullptr, QualType(), APValue());
1455   C.addDestruction(&TPOD->Value);
1456   return TPOD;
1457 }
1458 
1459 void TemplateParamObjectDecl::printName(llvm::raw_ostream &OS) const {
1460   OS << "<template param ";
1461   printAsExpr(OS);
1462   OS << ">";
1463 }
1464 
1465 void TemplateParamObjectDecl::printAsExpr(llvm::raw_ostream &OS) const {
1466   const ASTContext &Ctx = getASTContext();
1467   getType().getUnqualifiedType().print(OS, Ctx.getPrintingPolicy());
1468   printAsInit(OS);
1469 }
1470 
1471 void TemplateParamObjectDecl::printAsInit(llvm::raw_ostream &OS) const {
1472   const ASTContext &Ctx = getASTContext();
1473   getValue().printPretty(OS, Ctx, getType());
1474 }
1475