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/IdentifierTable.h"
22 #include "llvm/ADT/STLExtras.h"
23 #include <memory>
24 using namespace clang;
25 
26 //===----------------------------------------------------------------------===//
27 // TemplateParameterList Implementation
28 //===----------------------------------------------------------------------===//
29 
30 TemplateParameterList::TemplateParameterList(SourceLocation TemplateLoc,
31                                              SourceLocation LAngleLoc,
32                                              NamedDecl **Params, unsigned NumParams,
33                                              SourceLocation RAngleLoc)
34   : TemplateLoc(TemplateLoc), LAngleLoc(LAngleLoc), RAngleLoc(RAngleLoc),
35     NumParams(NumParams), ContainsUnexpandedParameterPack(false) {
36   assert(this->NumParams == NumParams && "Too many template parameters");
37   for (unsigned Idx = 0; Idx < NumParams; ++Idx) {
38     NamedDecl *P = Params[Idx];
39     begin()[Idx] = P;
40 
41     if (!P->isTemplateParameterPack()) {
42       if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(P))
43         if (NTTP->getType()->containsUnexpandedParameterPack())
44           ContainsUnexpandedParameterPack = true;
45 
46       if (TemplateTemplateParmDecl *TTP = dyn_cast<TemplateTemplateParmDecl>(P))
47         if (TTP->getTemplateParameters()->containsUnexpandedParameterPack())
48           ContainsUnexpandedParameterPack = true;
49 
50       // FIXME: If a default argument contains an unexpanded parameter pack, the
51       // template parameter list does too.
52     }
53   }
54 }
55 
56 TemplateParameterList *
57 TemplateParameterList::Create(const ASTContext &C, SourceLocation TemplateLoc,
58                               SourceLocation LAngleLoc, NamedDecl **Params,
59                               unsigned NumParams, SourceLocation RAngleLoc) {
60   unsigned Size = sizeof(TemplateParameterList)
61                 + sizeof(NamedDecl *) * NumParams;
62   unsigned Align = std::max(llvm::alignOf<TemplateParameterList>(),
63                             llvm::alignOf<NamedDecl*>());
64   void *Mem = C.Allocate(Size, Align);
65   return new (Mem) TemplateParameterList(TemplateLoc, LAngleLoc, Params,
66                                          NumParams, RAngleLoc);
67 }
68 
69 unsigned TemplateParameterList::getMinRequiredArguments() const {
70   unsigned NumRequiredArgs = 0;
71   for (iterator P = const_cast<TemplateParameterList *>(this)->begin(),
72              PEnd = const_cast<TemplateParameterList *>(this)->end();
73        P != PEnd; ++P) {
74     if ((*P)->isTemplateParameterPack()) {
75       if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(*P))
76         if (NTTP->isExpandedParameterPack()) {
77           NumRequiredArgs += NTTP->getNumExpansionTypes();
78           continue;
79         }
80 
81       break;
82     }
83 
84     if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(*P)) {
85       if (TTP->hasDefaultArgument())
86         break;
87     } else if (NonTypeTemplateParmDecl *NTTP
88                                     = dyn_cast<NonTypeTemplateParmDecl>(*P)) {
89       if (NTTP->hasDefaultArgument())
90         break;
91     } else if (cast<TemplateTemplateParmDecl>(*P)->hasDefaultArgument())
92       break;
93 
94     ++NumRequiredArgs;
95   }
96 
97   return NumRequiredArgs;
98 }
99 
100 unsigned TemplateParameterList::getDepth() const {
101   if (size() == 0)
102     return 0;
103 
104   const NamedDecl *FirstParm = getParam(0);
105   if (const TemplateTypeParmDecl *TTP
106         = dyn_cast<TemplateTypeParmDecl>(FirstParm))
107     return TTP->getDepth();
108   else if (const NonTypeTemplateParmDecl *NTTP
109              = dyn_cast<NonTypeTemplateParmDecl>(FirstParm))
110     return NTTP->getDepth();
111   else
112     return cast<TemplateTemplateParmDecl>(FirstParm)->getDepth();
113 }
114 
115 static void AdoptTemplateParameterList(TemplateParameterList *Params,
116                                        DeclContext *Owner) {
117   for (TemplateParameterList::iterator P = Params->begin(),
118                                     PEnd = Params->end();
119        P != PEnd; ++P) {
120     (*P)->setDeclContext(Owner);
121 
122     if (TemplateTemplateParmDecl *TTP = dyn_cast<TemplateTemplateParmDecl>(*P))
123       AdoptTemplateParameterList(TTP->getTemplateParameters(), Owner);
124   }
125 }
126 
127 //===----------------------------------------------------------------------===//
128 // RedeclarableTemplateDecl Implementation
129 //===----------------------------------------------------------------------===//
130 
131 RedeclarableTemplateDecl::CommonBase *RedeclarableTemplateDecl::getCommonPtr() const {
132   if (!Common) {
133     // Walk the previous-declaration chain until we either find a declaration
134     // with a common pointer or we run out of previous declarations.
135     SmallVector<const RedeclarableTemplateDecl *, 2> PrevDecls;
136     for (const RedeclarableTemplateDecl *Prev = getPreviousDecl(); Prev;
137          Prev = Prev->getPreviousDecl()) {
138       if (Prev->Common) {
139         Common = Prev->Common;
140         break;
141       }
142 
143       PrevDecls.push_back(Prev);
144     }
145 
146     // If we never found a common pointer, allocate one now.
147     if (!Common) {
148       // FIXME: If any of the declarations is from an AST file, we probably
149       // need an update record to add the common data.
150 
151       Common = newCommon(getASTContext());
152     }
153 
154     // Update any previous declarations we saw with the common pointer.
155     for (unsigned I = 0, N = PrevDecls.size(); I != N; ++I)
156       PrevDecls[I]->Common = Common;
157   }
158 
159   return Common;
160 }
161 
162 template <class EntryType>
163 typename RedeclarableTemplateDecl::SpecEntryTraits<EntryType>::DeclType*
164 RedeclarableTemplateDecl::findSpecializationImpl(
165                                  llvm::FoldingSetVector<EntryType> &Specs,
166                                  const TemplateArgument *Args, unsigned NumArgs,
167                                  void *&InsertPos) {
168   typedef SpecEntryTraits<EntryType> SETraits;
169   llvm::FoldingSetNodeID ID;
170   EntryType::Profile(ID,Args,NumArgs, getASTContext());
171   EntryType *Entry = Specs.FindNodeOrInsertPos(ID, InsertPos);
172   return Entry ? SETraits::getMostRecentDecl(Entry) : 0;
173 }
174 
175 /// \brief Generate the injected template arguments for the given template
176 /// parameter list, e.g., for the injected-class-name of a class template.
177 static void GenerateInjectedTemplateArgs(ASTContext &Context,
178                                         TemplateParameterList *Params,
179                                          TemplateArgument *Args) {
180   for (TemplateParameterList::iterator Param = Params->begin(),
181                                     ParamEnd = Params->end();
182        Param != ParamEnd; ++Param) {
183     TemplateArgument Arg;
184     if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(*Param)) {
185       QualType ArgType = Context.getTypeDeclType(TTP);
186       if (TTP->isParameterPack())
187         ArgType = Context.getPackExpansionType(ArgType, None);
188 
189       Arg = TemplateArgument(ArgType);
190     } else if (NonTypeTemplateParmDecl *NTTP =
191                dyn_cast<NonTypeTemplateParmDecl>(*Param)) {
192       Expr *E = new (Context) DeclRefExpr(NTTP, /*enclosing*/ false,
193                                   NTTP->getType().getNonLValueExprType(Context),
194                                   Expr::getValueKindForType(NTTP->getType()),
195                                           NTTP->getLocation());
196 
197       if (NTTP->isParameterPack())
198         E = new (Context) PackExpansionExpr(Context.DependentTy, E,
199                                             NTTP->getLocation(), None);
200       Arg = TemplateArgument(E);
201     } else {
202       TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(*Param);
203       if (TTP->isParameterPack())
204         Arg = TemplateArgument(TemplateName(TTP), Optional<unsigned>());
205       else
206         Arg = TemplateArgument(TemplateName(TTP));
207     }
208 
209     if ((*Param)->isTemplateParameterPack())
210       Arg = TemplateArgument::CreatePackCopy(Context, &Arg, 1);
211 
212     *Args++ = Arg;
213   }
214 }
215 
216 //===----------------------------------------------------------------------===//
217 // FunctionTemplateDecl Implementation
218 //===----------------------------------------------------------------------===//
219 
220 void FunctionTemplateDecl::DeallocateCommon(void *Ptr) {
221   static_cast<Common *>(Ptr)->~Common();
222 }
223 
224 FunctionTemplateDecl *FunctionTemplateDecl::Create(ASTContext &C,
225                                                    DeclContext *DC,
226                                                    SourceLocation L,
227                                                    DeclarationName Name,
228                                                TemplateParameterList *Params,
229                                                    NamedDecl *Decl) {
230   AdoptTemplateParameterList(Params, cast<DeclContext>(Decl));
231   return new (C) FunctionTemplateDecl(DC, L, Name, Params, Decl);
232 }
233 
234 FunctionTemplateDecl *FunctionTemplateDecl::CreateDeserialized(ASTContext &C,
235                                                                unsigned ID) {
236   void *Mem = AllocateDeserializedDecl(C, ID, sizeof(FunctionTemplateDecl));
237   return new (Mem) FunctionTemplateDecl(0, SourceLocation(), DeclarationName(),
238                                         0, 0);
239 }
240 
241 RedeclarableTemplateDecl::CommonBase *
242 FunctionTemplateDecl::newCommon(ASTContext &C) const {
243   Common *CommonPtr = new (C) Common;
244   C.AddDeallocation(DeallocateCommon, CommonPtr);
245   return CommonPtr;
246 }
247 
248 FunctionDecl *
249 FunctionTemplateDecl::findSpecialization(const TemplateArgument *Args,
250                                          unsigned NumArgs, void *&InsertPos) {
251   return findSpecializationImpl(getSpecializations(), Args, NumArgs, InsertPos);
252 }
253 
254 void FunctionTemplateDecl::addSpecialization(
255       FunctionTemplateSpecializationInfo *Info, void *InsertPos) {
256   if (InsertPos)
257     getSpecializations().InsertNode(Info, InsertPos);
258   else
259     getSpecializations().GetOrInsertNode(Info);
260   if (ASTMutationListener *L = getASTMutationListener())
261     L->AddedCXXTemplateSpecialization(this, Info->Function);
262 }
263 
264 ArrayRef<TemplateArgument> FunctionTemplateDecl::getInjectedTemplateArgs() {
265   TemplateParameterList *Params = getTemplateParameters();
266   Common *CommonPtr = getCommonPtr();
267   if (!CommonPtr->InjectedArgs) {
268     CommonPtr->InjectedArgs
269       = new (getASTContext()) TemplateArgument[Params->size()];
270     GenerateInjectedTemplateArgs(getASTContext(), Params,
271                                  CommonPtr->InjectedArgs);
272   }
273 
274   return llvm::makeArrayRef(CommonPtr->InjectedArgs, Params->size());
275 }
276 
277 //===----------------------------------------------------------------------===//
278 // ClassTemplateDecl Implementation
279 //===----------------------------------------------------------------------===//
280 
281 void ClassTemplateDecl::DeallocateCommon(void *Ptr) {
282   static_cast<Common *>(Ptr)->~Common();
283 }
284 
285 ClassTemplateDecl *ClassTemplateDecl::Create(ASTContext &C,
286                                              DeclContext *DC,
287                                              SourceLocation L,
288                                              DeclarationName Name,
289                                              TemplateParameterList *Params,
290                                              NamedDecl *Decl,
291                                              ClassTemplateDecl *PrevDecl) {
292   AdoptTemplateParameterList(Params, cast<DeclContext>(Decl));
293   ClassTemplateDecl *New = new (C) ClassTemplateDecl(DC, L, Name, Params, Decl);
294   New->setPreviousDeclaration(PrevDecl);
295   return New;
296 }
297 
298 ClassTemplateDecl *ClassTemplateDecl::CreateDeserialized(ASTContext &C,
299                                                          unsigned ID) {
300   void *Mem = AllocateDeserializedDecl(C, ID, sizeof(ClassTemplateDecl));
301   return new (Mem) ClassTemplateDecl(EmptyShell());
302 }
303 
304 void ClassTemplateDecl::LoadLazySpecializations() const {
305   Common *CommonPtr = getCommonPtr();
306   if (CommonPtr->LazySpecializations) {
307     ASTContext &Context = getASTContext();
308     uint32_t *Specs = CommonPtr->LazySpecializations;
309     CommonPtr->LazySpecializations = 0;
310     for (uint32_t I = 0, N = *Specs++; I != N; ++I)
311       (void)Context.getExternalSource()->GetExternalDecl(Specs[I]);
312   }
313 }
314 
315 llvm::FoldingSetVector<ClassTemplateSpecializationDecl> &
316 ClassTemplateDecl::getSpecializations() const {
317   LoadLazySpecializations();
318   return getCommonPtr()->Specializations;
319 }
320 
321 llvm::FoldingSetVector<ClassTemplatePartialSpecializationDecl> &
322 ClassTemplateDecl::getPartialSpecializations() {
323   LoadLazySpecializations();
324   return getCommonPtr()->PartialSpecializations;
325 }
326 
327 RedeclarableTemplateDecl::CommonBase *
328 ClassTemplateDecl::newCommon(ASTContext &C) const {
329   Common *CommonPtr = new (C) Common;
330   C.AddDeallocation(DeallocateCommon, CommonPtr);
331   return CommonPtr;
332 }
333 
334 ClassTemplateSpecializationDecl *
335 ClassTemplateDecl::findSpecialization(const TemplateArgument *Args,
336                                       unsigned NumArgs, void *&InsertPos) {
337   return findSpecializationImpl(getSpecializations(), Args, NumArgs, InsertPos);
338 }
339 
340 void ClassTemplateDecl::AddSpecialization(ClassTemplateSpecializationDecl *D,
341                                           void *InsertPos) {
342   if (InsertPos)
343     getSpecializations().InsertNode(D, InsertPos);
344   else {
345     ClassTemplateSpecializationDecl *Existing
346       = getSpecializations().GetOrInsertNode(D);
347     (void)Existing;
348     assert(Existing->isCanonicalDecl() && "Non-canonical specialization?");
349   }
350   if (ASTMutationListener *L = getASTMutationListener())
351     L->AddedCXXTemplateSpecialization(this, D);
352 }
353 
354 ClassTemplatePartialSpecializationDecl *
355 ClassTemplateDecl::findPartialSpecialization(const TemplateArgument *Args,
356                                              unsigned NumArgs,
357                                              void *&InsertPos) {
358   return findSpecializationImpl(getPartialSpecializations(), Args, NumArgs,
359                                 InsertPos);
360 }
361 
362 void ClassTemplateDecl::AddPartialSpecialization(
363                                       ClassTemplatePartialSpecializationDecl *D,
364                                       void *InsertPos) {
365   if (InsertPos)
366     getPartialSpecializations().InsertNode(D, InsertPos);
367   else {
368     ClassTemplatePartialSpecializationDecl *Existing
369       = getPartialSpecializations().GetOrInsertNode(D);
370     (void)Existing;
371     assert(Existing->isCanonicalDecl() && "Non-canonical specialization?");
372   }
373 
374   if (ASTMutationListener *L = getASTMutationListener())
375     L->AddedCXXTemplateSpecialization(this, D);
376 }
377 
378 void ClassTemplateDecl::getPartialSpecializations(
379           SmallVectorImpl<ClassTemplatePartialSpecializationDecl *> &PS) {
380   llvm::FoldingSetVector<ClassTemplatePartialSpecializationDecl> &PartialSpecs
381     = getPartialSpecializations();
382   PS.clear();
383   PS.resize(PartialSpecs.size());
384   for (llvm::FoldingSetVector<ClassTemplatePartialSpecializationDecl>::iterator
385        P = PartialSpecs.begin(), PEnd = PartialSpecs.end();
386        P != PEnd; ++P) {
387     assert(!PS[P->getSequenceNumber()]);
388     PS[P->getSequenceNumber()] = P->getMostRecentDecl();
389   }
390 }
391 
392 ClassTemplatePartialSpecializationDecl *
393 ClassTemplateDecl::findPartialSpecialization(QualType T) {
394   ASTContext &Context = getASTContext();
395   using llvm::FoldingSetVector;
396   typedef FoldingSetVector<ClassTemplatePartialSpecializationDecl>::iterator
397     partial_spec_iterator;
398   for (partial_spec_iterator P = getPartialSpecializations().begin(),
399                           PEnd = getPartialSpecializations().end();
400        P != PEnd; ++P) {
401     if (Context.hasSameType(P->getInjectedSpecializationType(), T))
402       return P->getMostRecentDecl();
403   }
404 
405   return 0;
406 }
407 
408 ClassTemplatePartialSpecializationDecl *
409 ClassTemplateDecl::findPartialSpecInstantiatedFromMember(
410                                     ClassTemplatePartialSpecializationDecl *D) {
411   Decl *DCanon = D->getCanonicalDecl();
412   for (llvm::FoldingSetVector<ClassTemplatePartialSpecializationDecl>::iterator
413             P = getPartialSpecializations().begin(),
414          PEnd = getPartialSpecializations().end();
415        P != PEnd; ++P) {
416     if (P->getInstantiatedFromMember()->getCanonicalDecl() == DCanon)
417       return P->getMostRecentDecl();
418   }
419 
420   return 0;
421 }
422 
423 QualType
424 ClassTemplateDecl::getInjectedClassNameSpecialization() {
425   Common *CommonPtr = getCommonPtr();
426   if (!CommonPtr->InjectedClassNameType.isNull())
427     return CommonPtr->InjectedClassNameType;
428 
429   // C++0x [temp.dep.type]p2:
430   //  The template argument list of a primary template is a template argument
431   //  list in which the nth template argument has the value of the nth template
432   //  parameter of the class template. If the nth template parameter is a
433   //  template parameter pack (14.5.3), the nth template argument is a pack
434   //  expansion (14.5.3) whose pattern is the name of the template parameter
435   //  pack.
436   ASTContext &Context = getASTContext();
437   TemplateParameterList *Params = getTemplateParameters();
438   SmallVector<TemplateArgument, 16> TemplateArgs;
439   TemplateArgs.resize(Params->size());
440   GenerateInjectedTemplateArgs(getASTContext(), Params, TemplateArgs.data());
441   CommonPtr->InjectedClassNameType
442     = Context.getTemplateSpecializationType(TemplateName(this),
443                                             &TemplateArgs[0],
444                                             TemplateArgs.size());
445   return CommonPtr->InjectedClassNameType;
446 }
447 
448 //===----------------------------------------------------------------------===//
449 // TemplateTypeParm Allocation/Deallocation Method Implementations
450 //===----------------------------------------------------------------------===//
451 
452 TemplateTypeParmDecl *
453 TemplateTypeParmDecl::Create(const ASTContext &C, DeclContext *DC,
454                              SourceLocation KeyLoc, SourceLocation NameLoc,
455                              unsigned D, unsigned P, IdentifierInfo *Id,
456                              bool Typename, bool ParameterPack) {
457   TemplateTypeParmDecl *TTPDecl =
458     new (C) TemplateTypeParmDecl(DC, KeyLoc, NameLoc, Id, Typename);
459   QualType TTPType = C.getTemplateTypeParmType(D, P, ParameterPack, TTPDecl);
460   TTPDecl->TypeForDecl = TTPType.getTypePtr();
461   return TTPDecl;
462 }
463 
464 TemplateTypeParmDecl *
465 TemplateTypeParmDecl::CreateDeserialized(const ASTContext &C, unsigned ID) {
466   void *Mem = AllocateDeserializedDecl(C, ID, sizeof(TemplateTypeParmDecl));
467   return new (Mem) TemplateTypeParmDecl(0, SourceLocation(), SourceLocation(),
468                                         0, false);
469 }
470 
471 SourceLocation TemplateTypeParmDecl::getDefaultArgumentLoc() const {
472   return hasDefaultArgument()
473     ? DefaultArgument->getTypeLoc().getBeginLoc()
474     : SourceLocation();
475 }
476 
477 SourceRange TemplateTypeParmDecl::getSourceRange() const {
478   if (hasDefaultArgument() && !defaultArgumentWasInherited())
479     return SourceRange(getLocStart(),
480                        DefaultArgument->getTypeLoc().getEndLoc());
481   else
482     return TypeDecl::getSourceRange();
483 }
484 
485 unsigned TemplateTypeParmDecl::getDepth() const {
486   return TypeForDecl->getAs<TemplateTypeParmType>()->getDepth();
487 }
488 
489 unsigned TemplateTypeParmDecl::getIndex() const {
490   return TypeForDecl->getAs<TemplateTypeParmType>()->getIndex();
491 }
492 
493 bool TemplateTypeParmDecl::isParameterPack() const {
494   return TypeForDecl->getAs<TemplateTypeParmType>()->isParameterPack();
495 }
496 
497 //===----------------------------------------------------------------------===//
498 // NonTypeTemplateParmDecl Method Implementations
499 //===----------------------------------------------------------------------===//
500 
501 NonTypeTemplateParmDecl::NonTypeTemplateParmDecl(DeclContext *DC,
502                                                  SourceLocation StartLoc,
503                                                  SourceLocation IdLoc,
504                                                  unsigned D, unsigned P,
505                                                  IdentifierInfo *Id,
506                                                  QualType T,
507                                                  TypeSourceInfo *TInfo,
508                                                  const QualType *ExpandedTypes,
509                                                  unsigned NumExpandedTypes,
510                                                 TypeSourceInfo **ExpandedTInfos)
511   : DeclaratorDecl(NonTypeTemplateParm, DC, IdLoc, Id, T, TInfo, StartLoc),
512     TemplateParmPosition(D, P), DefaultArgumentAndInherited(0, false),
513     ParameterPack(true), ExpandedParameterPack(true),
514     NumExpandedTypes(NumExpandedTypes)
515 {
516   if (ExpandedTypes && ExpandedTInfos) {
517     void **TypesAndInfos = reinterpret_cast<void **>(this + 1);
518     for (unsigned I = 0; I != NumExpandedTypes; ++I) {
519       TypesAndInfos[2*I] = ExpandedTypes[I].getAsOpaquePtr();
520       TypesAndInfos[2*I + 1] = ExpandedTInfos[I];
521     }
522   }
523 }
524 
525 NonTypeTemplateParmDecl *
526 NonTypeTemplateParmDecl::Create(const ASTContext &C, DeclContext *DC,
527                                 SourceLocation StartLoc, SourceLocation IdLoc,
528                                 unsigned D, unsigned P, IdentifierInfo *Id,
529                                 QualType T, bool ParameterPack,
530                                 TypeSourceInfo *TInfo) {
531   return new (C) NonTypeTemplateParmDecl(DC, StartLoc, IdLoc, D, P, Id,
532                                          T, ParameterPack, TInfo);
533 }
534 
535 NonTypeTemplateParmDecl *
536 NonTypeTemplateParmDecl::Create(const ASTContext &C, DeclContext *DC,
537                                 SourceLocation StartLoc, SourceLocation IdLoc,
538                                 unsigned D, unsigned P,
539                                 IdentifierInfo *Id, QualType T,
540                                 TypeSourceInfo *TInfo,
541                                 const QualType *ExpandedTypes,
542                                 unsigned NumExpandedTypes,
543                                 TypeSourceInfo **ExpandedTInfos) {
544   unsigned Size = sizeof(NonTypeTemplateParmDecl)
545                 + NumExpandedTypes * 2 * sizeof(void*);
546   void *Mem = C.Allocate(Size);
547   return new (Mem) NonTypeTemplateParmDecl(DC, StartLoc, IdLoc,
548                                            D, P, Id, T, TInfo,
549                                            ExpandedTypes, NumExpandedTypes,
550                                            ExpandedTInfos);
551 }
552 
553 NonTypeTemplateParmDecl *
554 NonTypeTemplateParmDecl::CreateDeserialized(ASTContext &C, unsigned ID) {
555   void *Mem = AllocateDeserializedDecl(C, ID, sizeof(NonTypeTemplateParmDecl));
556   return new (Mem) NonTypeTemplateParmDecl(0, SourceLocation(),
557                                            SourceLocation(), 0, 0, 0,
558                                            QualType(), false, 0);
559 }
560 
561 NonTypeTemplateParmDecl *
562 NonTypeTemplateParmDecl::CreateDeserialized(ASTContext &C, unsigned ID,
563                                             unsigned NumExpandedTypes) {
564   unsigned Size = sizeof(NonTypeTemplateParmDecl)
565                 + NumExpandedTypes * 2 * sizeof(void*);
566 
567   void *Mem = AllocateDeserializedDecl(C, ID, Size);
568   return new (Mem) NonTypeTemplateParmDecl(0, SourceLocation(),
569                                            SourceLocation(), 0, 0, 0,
570                                            QualType(), 0, 0, NumExpandedTypes,
571                                            0);
572 }
573 
574 SourceRange NonTypeTemplateParmDecl::getSourceRange() const {
575   if (hasDefaultArgument() && !defaultArgumentWasInherited())
576     return SourceRange(getOuterLocStart(),
577                        getDefaultArgument()->getSourceRange().getEnd());
578   return DeclaratorDecl::getSourceRange();
579 }
580 
581 SourceLocation NonTypeTemplateParmDecl::getDefaultArgumentLoc() const {
582   return hasDefaultArgument()
583     ? getDefaultArgument()->getSourceRange().getBegin()
584     : SourceLocation();
585 }
586 
587 //===----------------------------------------------------------------------===//
588 // TemplateTemplateParmDecl Method Implementations
589 //===----------------------------------------------------------------------===//
590 
591 void TemplateTemplateParmDecl::anchor() { }
592 
593 TemplateTemplateParmDecl::TemplateTemplateParmDecl(
594     DeclContext *DC, SourceLocation L, unsigned D, unsigned P,
595     IdentifierInfo *Id, TemplateParameterList *Params,
596     unsigned NumExpansions, TemplateParameterList * const *Expansions)
597   : TemplateDecl(TemplateTemplateParm, DC, L, Id, Params),
598     TemplateParmPosition(D, P), DefaultArgument(),
599     DefaultArgumentWasInherited(false), ParameterPack(true),
600     ExpandedParameterPack(true), NumExpandedParams(NumExpansions) {
601   if (Expansions)
602     std::memcpy(reinterpret_cast<void*>(this + 1), Expansions,
603                 sizeof(TemplateParameterList*) * NumExpandedParams);
604 }
605 
606 TemplateTemplateParmDecl *
607 TemplateTemplateParmDecl::Create(const ASTContext &C, DeclContext *DC,
608                                  SourceLocation L, unsigned D, unsigned P,
609                                  bool ParameterPack, IdentifierInfo *Id,
610                                  TemplateParameterList *Params) {
611   return new (C) TemplateTemplateParmDecl(DC, L, D, P, ParameterPack, Id,
612                                           Params);
613 }
614 
615 TemplateTemplateParmDecl *
616 TemplateTemplateParmDecl::Create(const ASTContext &C, DeclContext *DC,
617                                  SourceLocation L, unsigned D, unsigned P,
618                                  IdentifierInfo *Id,
619                                  TemplateParameterList *Params,
620                                  ArrayRef<TemplateParameterList *> Expansions) {
621   void *Mem = C.Allocate(sizeof(TemplateTemplateParmDecl) +
622                          sizeof(TemplateParameterList*) * Expansions.size());
623   return new (Mem) TemplateTemplateParmDecl(DC, L, D, P, Id, Params,
624                                             Expansions.size(),
625                                             Expansions.data());
626 }
627 
628 TemplateTemplateParmDecl *
629 TemplateTemplateParmDecl::CreateDeserialized(ASTContext &C, unsigned ID) {
630   void *Mem = AllocateDeserializedDecl(C, ID, sizeof(TemplateTemplateParmDecl));
631   return new (Mem) TemplateTemplateParmDecl(0, SourceLocation(), 0, 0, false,
632                                             0, 0);
633 }
634 
635 TemplateTemplateParmDecl *
636 TemplateTemplateParmDecl::CreateDeserialized(ASTContext &C, unsigned ID,
637                                              unsigned NumExpansions) {
638   unsigned Size = sizeof(TemplateTemplateParmDecl) +
639                   sizeof(TemplateParameterList*) * NumExpansions;
640   void *Mem = AllocateDeserializedDecl(C, ID, Size);
641   return new (Mem) TemplateTemplateParmDecl(0, SourceLocation(), 0, 0, 0, 0,
642                                             NumExpansions, 0);
643 }
644 
645 //===----------------------------------------------------------------------===//
646 // TemplateArgumentList Implementation
647 //===----------------------------------------------------------------------===//
648 TemplateArgumentList *
649 TemplateArgumentList::CreateCopy(ASTContext &Context,
650                                  const TemplateArgument *Args,
651                                  unsigned NumArgs) {
652   std::size_t Size = sizeof(TemplateArgumentList)
653                    + NumArgs * sizeof(TemplateArgument);
654   void *Mem = Context.Allocate(Size);
655   TemplateArgument *StoredArgs
656     = reinterpret_cast<TemplateArgument *>(
657                                 static_cast<TemplateArgumentList *>(Mem) + 1);
658   std::uninitialized_copy(Args, Args + NumArgs, StoredArgs);
659   return new (Mem) TemplateArgumentList(StoredArgs, NumArgs, true);
660 }
661 
662 FunctionTemplateSpecializationInfo *
663 FunctionTemplateSpecializationInfo::Create(ASTContext &C, FunctionDecl *FD,
664                                            FunctionTemplateDecl *Template,
665                                            TemplateSpecializationKind TSK,
666                                        const TemplateArgumentList *TemplateArgs,
667                           const TemplateArgumentListInfo *TemplateArgsAsWritten,
668                                            SourceLocation POI) {
669   const ASTTemplateArgumentListInfo *ArgsAsWritten = 0;
670   if (TemplateArgsAsWritten)
671     ArgsAsWritten = ASTTemplateArgumentListInfo::Create(C,
672                                                         *TemplateArgsAsWritten);
673 
674   return new (C) FunctionTemplateSpecializationInfo(FD, Template, TSK,
675                                                     TemplateArgs,
676                                                     ArgsAsWritten,
677                                                     POI);
678 }
679 
680 //===----------------------------------------------------------------------===//
681 // TemplateDecl Implementation
682 //===----------------------------------------------------------------------===//
683 
684 void TemplateDecl::anchor() { }
685 
686 //===----------------------------------------------------------------------===//
687 // ClassTemplateSpecializationDecl Implementation
688 //===----------------------------------------------------------------------===//
689 ClassTemplateSpecializationDecl::
690 ClassTemplateSpecializationDecl(ASTContext &Context, Kind DK, TagKind TK,
691                                 DeclContext *DC, SourceLocation StartLoc,
692                                 SourceLocation IdLoc,
693                                 ClassTemplateDecl *SpecializedTemplate,
694                                 const TemplateArgument *Args,
695                                 unsigned NumArgs,
696                                 ClassTemplateSpecializationDecl *PrevDecl)
697   : CXXRecordDecl(DK, TK, DC, StartLoc, IdLoc,
698                   SpecializedTemplate->getIdentifier(),
699                   PrevDecl),
700     SpecializedTemplate(SpecializedTemplate),
701     ExplicitInfo(0),
702     TemplateArgs(TemplateArgumentList::CreateCopy(Context, Args, NumArgs)),
703     SpecializationKind(TSK_Undeclared) {
704 }
705 
706 ClassTemplateSpecializationDecl::ClassTemplateSpecializationDecl(Kind DK)
707   : CXXRecordDecl(DK, TTK_Struct, 0, SourceLocation(), SourceLocation(), 0, 0),
708     ExplicitInfo(0),
709     SpecializationKind(TSK_Undeclared) {
710 }
711 
712 ClassTemplateSpecializationDecl *
713 ClassTemplateSpecializationDecl::Create(ASTContext &Context, TagKind TK,
714                                         DeclContext *DC,
715                                         SourceLocation StartLoc,
716                                         SourceLocation IdLoc,
717                                         ClassTemplateDecl *SpecializedTemplate,
718                                         const TemplateArgument *Args,
719                                         unsigned NumArgs,
720                                    ClassTemplateSpecializationDecl *PrevDecl) {
721   ClassTemplateSpecializationDecl *Result
722     = new (Context)ClassTemplateSpecializationDecl(Context,
723                                                    ClassTemplateSpecialization,
724                                                    TK, DC, StartLoc, IdLoc,
725                                                    SpecializedTemplate,
726                                                    Args, NumArgs,
727                                                    PrevDecl);
728   Result->MayHaveOutOfDateDef = false;
729 
730   Context.getTypeDeclType(Result, PrevDecl);
731   return Result;
732 }
733 
734 ClassTemplateSpecializationDecl *
735 ClassTemplateSpecializationDecl::CreateDeserialized(ASTContext &C,
736                                                     unsigned ID) {
737   void *Mem = AllocateDeserializedDecl(C, ID,
738                                        sizeof(ClassTemplateSpecializationDecl));
739   ClassTemplateSpecializationDecl *Result =
740     new (Mem) ClassTemplateSpecializationDecl(ClassTemplateSpecialization);
741   Result->MayHaveOutOfDateDef = false;
742   return Result;
743 }
744 
745 void ClassTemplateSpecializationDecl::getNameForDiagnostic(
746     raw_ostream &OS, const PrintingPolicy &Policy, bool Qualified) const {
747   NamedDecl::getNameForDiagnostic(OS, Policy, Qualified);
748 
749   const TemplateArgumentList &TemplateArgs = getTemplateArgs();
750   TemplateSpecializationType::PrintTemplateArgumentList(
751       OS, TemplateArgs.data(), TemplateArgs.size(), Policy);
752 }
753 
754 ClassTemplateDecl *
755 ClassTemplateSpecializationDecl::getSpecializedTemplate() const {
756   if (SpecializedPartialSpecialization *PartialSpec
757       = SpecializedTemplate.dyn_cast<SpecializedPartialSpecialization*>())
758     return PartialSpec->PartialSpecialization->getSpecializedTemplate();
759   return SpecializedTemplate.get<ClassTemplateDecl*>();
760 }
761 
762 SourceRange
763 ClassTemplateSpecializationDecl::getSourceRange() const {
764   if (ExplicitInfo) {
765     SourceLocation Begin = getTemplateKeywordLoc();
766     if (Begin.isValid()) {
767       // Here we have an explicit (partial) specialization or instantiation.
768       assert(getSpecializationKind() == TSK_ExplicitSpecialization ||
769              getSpecializationKind() == TSK_ExplicitInstantiationDeclaration ||
770              getSpecializationKind() == TSK_ExplicitInstantiationDefinition);
771       if (getExternLoc().isValid())
772         Begin = getExternLoc();
773       SourceLocation End = getRBraceLoc();
774       if (End.isInvalid())
775         End = getTypeAsWritten()->getTypeLoc().getEndLoc();
776       return SourceRange(Begin, End);
777     }
778     // An implicit instantiation of a class template partial specialization
779     // uses ExplicitInfo to record the TypeAsWritten, but the source
780     // locations should be retrieved from the instantiation pattern.
781     typedef ClassTemplatePartialSpecializationDecl CTPSDecl;
782     CTPSDecl *ctpsd = const_cast<CTPSDecl*>(cast<CTPSDecl>(this));
783     CTPSDecl *inst_from = ctpsd->getInstantiatedFromMember();
784     assert(inst_from != 0);
785     return inst_from->getSourceRange();
786   }
787   else {
788     // No explicit info available.
789     llvm::PointerUnion<ClassTemplateDecl *,
790                        ClassTemplatePartialSpecializationDecl *>
791       inst_from = getInstantiatedFrom();
792     if (inst_from.isNull())
793       return getSpecializedTemplate()->getSourceRange();
794     if (ClassTemplateDecl *ctd = inst_from.dyn_cast<ClassTemplateDecl*>())
795       return ctd->getSourceRange();
796     return inst_from.get<ClassTemplatePartialSpecializationDecl*>()
797       ->getSourceRange();
798   }
799 }
800 
801 //===----------------------------------------------------------------------===//
802 // ClassTemplatePartialSpecializationDecl Implementation
803 //===----------------------------------------------------------------------===//
804 void ClassTemplatePartialSpecializationDecl::anchor() { }
805 
806 ClassTemplatePartialSpecializationDecl::
807 ClassTemplatePartialSpecializationDecl(ASTContext &Context, TagKind TK,
808                                        DeclContext *DC,
809                                        SourceLocation StartLoc,
810                                        SourceLocation IdLoc,
811                                        TemplateParameterList *Params,
812                                        ClassTemplateDecl *SpecializedTemplate,
813                                        const TemplateArgument *Args,
814                                        unsigned NumArgs,
815                                        TemplateArgumentLoc *ArgInfos,
816                                        unsigned NumArgInfos,
817                                ClassTemplatePartialSpecializationDecl *PrevDecl,
818                                        unsigned SequenceNumber)
819   : ClassTemplateSpecializationDecl(Context,
820                                     ClassTemplatePartialSpecialization,
821                                     TK, DC, StartLoc, IdLoc,
822                                     SpecializedTemplate,
823                                     Args, NumArgs, PrevDecl),
824     TemplateParams(Params), ArgsAsWritten(ArgInfos),
825     NumArgsAsWritten(NumArgInfos), SequenceNumber(SequenceNumber),
826     InstantiatedFromMember(0, false)
827 {
828   AdoptTemplateParameterList(Params, this);
829 }
830 
831 ClassTemplatePartialSpecializationDecl *
832 ClassTemplatePartialSpecializationDecl::
833 Create(ASTContext &Context, TagKind TK,DeclContext *DC,
834        SourceLocation StartLoc, SourceLocation IdLoc,
835        TemplateParameterList *Params,
836        ClassTemplateDecl *SpecializedTemplate,
837        const TemplateArgument *Args,
838        unsigned NumArgs,
839        const TemplateArgumentListInfo &ArgInfos,
840        QualType CanonInjectedType,
841        ClassTemplatePartialSpecializationDecl *PrevDecl,
842        unsigned SequenceNumber) {
843   unsigned N = ArgInfos.size();
844   TemplateArgumentLoc *ClonedArgs = new (Context) TemplateArgumentLoc[N];
845   for (unsigned I = 0; I != N; ++I)
846     ClonedArgs[I] = ArgInfos[I];
847 
848   ClassTemplatePartialSpecializationDecl *Result
849     = new (Context)ClassTemplatePartialSpecializationDecl(Context, TK, DC,
850                                                           StartLoc, IdLoc,
851                                                           Params,
852                                                           SpecializedTemplate,
853                                                           Args, NumArgs,
854                                                           ClonedArgs, N,
855                                                           PrevDecl,
856                                                           SequenceNumber);
857   Result->setSpecializationKind(TSK_ExplicitSpecialization);
858   Result->MayHaveOutOfDateDef = false;
859 
860   Context.getInjectedClassNameType(Result, CanonInjectedType);
861   return Result;
862 }
863 
864 ClassTemplatePartialSpecializationDecl *
865 ClassTemplatePartialSpecializationDecl::CreateDeserialized(ASTContext &C,
866                                                            unsigned ID) {
867   void *Mem = AllocateDeserializedDecl(C, ID,
868                 sizeof(ClassTemplatePartialSpecializationDecl));
869   ClassTemplatePartialSpecializationDecl *Result
870     = new (Mem) ClassTemplatePartialSpecializationDecl();
871   Result->MayHaveOutOfDateDef = false;
872   return Result;
873 }
874 
875 //===----------------------------------------------------------------------===//
876 // FriendTemplateDecl Implementation
877 //===----------------------------------------------------------------------===//
878 
879 void FriendTemplateDecl::anchor() { }
880 
881 FriendTemplateDecl *FriendTemplateDecl::Create(ASTContext &Context,
882                                                DeclContext *DC,
883                                                SourceLocation L,
884                                                unsigned NParams,
885                                                TemplateParameterList **Params,
886                                                FriendUnion Friend,
887                                                SourceLocation FLoc) {
888   FriendTemplateDecl *Result
889     = new (Context) FriendTemplateDecl(DC, L, NParams, Params, Friend, FLoc);
890   return Result;
891 }
892 
893 FriendTemplateDecl *FriendTemplateDecl::CreateDeserialized(ASTContext &C,
894                                                            unsigned ID) {
895   void *Mem = AllocateDeserializedDecl(C, ID, sizeof(FriendTemplateDecl));
896   return new (Mem) FriendTemplateDecl(EmptyShell());
897 }
898 
899 //===----------------------------------------------------------------------===//
900 // TypeAliasTemplateDecl Implementation
901 //===----------------------------------------------------------------------===//
902 
903 TypeAliasTemplateDecl *TypeAliasTemplateDecl::Create(ASTContext &C,
904                                                      DeclContext *DC,
905                                                      SourceLocation L,
906                                                      DeclarationName Name,
907                                                   TemplateParameterList *Params,
908                                                      NamedDecl *Decl) {
909   AdoptTemplateParameterList(Params, DC);
910   return new (C) TypeAliasTemplateDecl(DC, L, Name, Params, Decl);
911 }
912 
913 TypeAliasTemplateDecl *TypeAliasTemplateDecl::CreateDeserialized(ASTContext &C,
914                                                                  unsigned ID) {
915   void *Mem = AllocateDeserializedDecl(C, ID, sizeof(TypeAliasTemplateDecl));
916   return new (Mem) TypeAliasTemplateDecl(0, SourceLocation(), DeclarationName(),
917                                          0, 0);
918 }
919 
920 void TypeAliasTemplateDecl::DeallocateCommon(void *Ptr) {
921   static_cast<Common *>(Ptr)->~Common();
922 }
923 RedeclarableTemplateDecl::CommonBase *
924 TypeAliasTemplateDecl::newCommon(ASTContext &C) const {
925   Common *CommonPtr = new (C) Common;
926   C.AddDeallocation(DeallocateCommon, CommonPtr);
927   return CommonPtr;
928 }
929 
930 //===----------------------------------------------------------------------===//
931 // ClassScopeFunctionSpecializationDecl Implementation
932 //===----------------------------------------------------------------------===//
933 
934 void ClassScopeFunctionSpecializationDecl::anchor() { }
935 
936 ClassScopeFunctionSpecializationDecl *
937 ClassScopeFunctionSpecializationDecl::CreateDeserialized(ASTContext &C,
938                                                          unsigned ID) {
939   void *Mem = AllocateDeserializedDecl(C, ID,
940                 sizeof(ClassScopeFunctionSpecializationDecl));
941   return new (Mem) ClassScopeFunctionSpecializationDecl(0, SourceLocation(), 0,
942                                              false, TemplateArgumentListInfo());
943 }
944