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