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