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