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