1 //===--- TemplateBase.cpp - Common template AST class 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 common classes used throughout C++ template
11 // representations.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "clang/AST/TemplateBase.h"
16 #include "clang/AST/ASTContext.h"
17 #include "clang/AST/DeclBase.h"
18 #include "clang/AST/DeclTemplate.h"
19 #include "clang/AST/Expr.h"
20 #include "clang/AST/ExprCXX.h"
21 #include "clang/AST/Type.h"
22 #include "clang/AST/TypeLoc.h"
23 #include "clang/Basic/Diagnostic.h"
24 #include "llvm/ADT/FoldingSet.h"
25 #include "llvm/ADT/SmallString.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include <algorithm>
28 #include <cctype>
29 
30 using namespace clang;
31 
32 /// \brief Print a template integral argument value.
33 ///
34 /// \param TemplArg the TemplateArgument instance to print.
35 ///
36 /// \param Out the raw_ostream instance to use for printing.
37 static void printIntegral(const TemplateArgument &TemplArg,
38                           raw_ostream &Out) {
39   const ::clang::Type *T = TemplArg.getIntegralType().getTypePtr();
40   const llvm::APSInt &Val = TemplArg.getAsIntegral();
41 
42   if (T->isBooleanType()) {
43     Out << (Val.getBoolValue() ? "true" : "false");
44   } else if (T->isCharType()) {
45     const char Ch = Val.getZExtValue();
46     Out << ((Ch == '\'') ? "'\\" : "'");
47     Out.write_escaped(StringRef(&Ch, 1), /*UseHexEscapes=*/ true);
48     Out << "'";
49   } else {
50     Out << Val;
51   }
52 }
53 
54 //===----------------------------------------------------------------------===//
55 // TemplateArgument Implementation
56 //===----------------------------------------------------------------------===//
57 
58 TemplateArgument::TemplateArgument(ASTContext &Ctx, const llvm::APSInt &Value,
59                                    QualType Type)
60   : Kind(Integral) {
61   // Copy the APSInt value into our decomposed form.
62   Integer.BitWidth = Value.getBitWidth();
63   Integer.IsUnsigned = Value.isUnsigned();
64   // If the value is large, we have to get additional memory from the ASTContext
65   unsigned NumWords = Value.getNumWords();
66   if (NumWords > 1) {
67     void *Mem = Ctx.Allocate(NumWords * sizeof(uint64_t));
68     std::memcpy(Mem, Value.getRawData(), NumWords * sizeof(uint64_t));
69     Integer.pVal = static_cast<uint64_t *>(Mem);
70   } else {
71     Integer.VAL = Value.getZExtValue();
72   }
73 
74   Integer.Type = Type.getAsOpaquePtr();
75 }
76 
77 TemplateArgument TemplateArgument::CreatePackCopy(ASTContext &Context,
78                                                   const TemplateArgument *Args,
79                                                   unsigned NumArgs) {
80   if (NumArgs == 0)
81     return getEmptyPack();
82 
83   TemplateArgument *Storage = new (Context) TemplateArgument [NumArgs];
84   std::copy(Args, Args + NumArgs, Storage);
85   return TemplateArgument(Storage, NumArgs);
86 }
87 
88 bool TemplateArgument::isDependent() const {
89   switch (getKind()) {
90   case Null:
91     llvm_unreachable("Should not have a NULL template argument");
92 
93   case Type:
94     return getAsType()->isDependentType();
95 
96   case Template:
97     return getAsTemplate().isDependent();
98 
99   case TemplateExpansion:
100     return true;
101 
102   case Declaration:
103     if (DeclContext *DC = dyn_cast<DeclContext>(getAsDecl()))
104       return DC->isDependentContext();
105     return getAsDecl()->getDeclContext()->isDependentContext();
106 
107   case NullPtr:
108     return false;
109 
110   case Integral:
111     // Never dependent
112     return false;
113 
114   case Expression:
115     return (getAsExpr()->isTypeDependent() || getAsExpr()->isValueDependent());
116 
117   case Pack:
118     for (pack_iterator P = pack_begin(), PEnd = pack_end(); P != PEnd; ++P) {
119       if (P->isDependent())
120         return true;
121     }
122 
123     return false;
124   }
125 
126   llvm_unreachable("Invalid TemplateArgument Kind!");
127 }
128 
129 bool TemplateArgument::isInstantiationDependent() const {
130   switch (getKind()) {
131   case Null:
132     llvm_unreachable("Should not have a NULL template argument");
133 
134   case Type:
135     return getAsType()->isInstantiationDependentType();
136 
137   case Template:
138     return getAsTemplate().isInstantiationDependent();
139 
140   case TemplateExpansion:
141     return true;
142 
143   case Declaration:
144     if (DeclContext *DC = dyn_cast<DeclContext>(getAsDecl()))
145       return DC->isDependentContext();
146     return getAsDecl()->getDeclContext()->isDependentContext();
147 
148   case NullPtr:
149     return false;
150 
151   case Integral:
152     // Never dependent
153     return false;
154 
155   case Expression:
156     return getAsExpr()->isInstantiationDependent();
157 
158   case Pack:
159     for (pack_iterator P = pack_begin(), PEnd = pack_end(); P != PEnd; ++P) {
160       if (P->isInstantiationDependent())
161         return true;
162     }
163 
164     return false;
165   }
166 
167   llvm_unreachable("Invalid TemplateArgument Kind!");
168 }
169 
170 bool TemplateArgument::isPackExpansion() const {
171   switch (getKind()) {
172   case Null:
173   case Declaration:
174   case Integral:
175   case Pack:
176   case Template:
177   case NullPtr:
178     return false;
179 
180   case TemplateExpansion:
181     return true;
182 
183   case Type:
184     return isa<PackExpansionType>(getAsType());
185 
186   case Expression:
187     return isa<PackExpansionExpr>(getAsExpr());
188   }
189 
190   llvm_unreachable("Invalid TemplateArgument Kind!");
191 }
192 
193 bool TemplateArgument::containsUnexpandedParameterPack() const {
194   switch (getKind()) {
195   case Null:
196   case Declaration:
197   case Integral:
198   case TemplateExpansion:
199   case NullPtr:
200     break;
201 
202   case Type:
203     if (getAsType()->containsUnexpandedParameterPack())
204       return true;
205     break;
206 
207   case Template:
208     if (getAsTemplate().containsUnexpandedParameterPack())
209       return true;
210     break;
211 
212   case Expression:
213     if (getAsExpr()->containsUnexpandedParameterPack())
214       return true;
215     break;
216 
217   case Pack:
218     for (pack_iterator P = pack_begin(), PEnd = pack_end(); P != PEnd; ++P)
219       if (P->containsUnexpandedParameterPack())
220         return true;
221 
222     break;
223   }
224 
225   return false;
226 }
227 
228 llvm::Optional<unsigned> TemplateArgument::getNumTemplateExpansions() const {
229   assert(Kind == TemplateExpansion);
230   if (TemplateArg.NumExpansions)
231     return TemplateArg.NumExpansions - 1;
232 
233   return llvm::Optional<unsigned>();
234 }
235 
236 void TemplateArgument::Profile(llvm::FoldingSetNodeID &ID,
237                                const ASTContext &Context) const {
238   ID.AddInteger(Kind);
239   switch (Kind) {
240   case Null:
241     break;
242 
243   case Type:
244     getAsType().Profile(ID);
245     break;
246 
247   case Declaration:
248     ID.AddPointer(getAsDecl()? getAsDecl()->getCanonicalDecl() : 0);
249     break;
250 
251   case Template:
252   case TemplateExpansion: {
253     TemplateName Template = getAsTemplateOrTemplatePattern();
254     if (TemplateTemplateParmDecl *TTP
255           = dyn_cast_or_null<TemplateTemplateParmDecl>(
256                                                 Template.getAsTemplateDecl())) {
257       ID.AddBoolean(true);
258       ID.AddInteger(TTP->getDepth());
259       ID.AddInteger(TTP->getPosition());
260       ID.AddBoolean(TTP->isParameterPack());
261     } else {
262       ID.AddBoolean(false);
263       ID.AddPointer(Context.getCanonicalTemplateName(Template)
264                                                           .getAsVoidPointer());
265     }
266     break;
267   }
268 
269   case Integral:
270     getAsIntegral().Profile(ID);
271     getIntegralType().Profile(ID);
272     break;
273 
274   case Expression:
275     getAsExpr()->Profile(ID, Context, true);
276     break;
277 
278   case Pack:
279     ID.AddInteger(Args.NumArgs);
280     for (unsigned I = 0; I != Args.NumArgs; ++I)
281       Args.Args[I].Profile(ID, Context);
282   }
283 }
284 
285 bool TemplateArgument::structurallyEquals(const TemplateArgument &Other) const {
286   if (getKind() != Other.getKind()) return false;
287 
288   switch (getKind()) {
289   case Null:
290   case Type:
291   case Expression:
292   case Template:
293   case TemplateExpansion:
294   case NullPtr:
295     return TypeOrValue == Other.TypeOrValue;
296 
297   case Declaration:
298     return getAsDecl() == Other.getAsDecl() &&
299            isDeclForReferenceParam() && Other.isDeclForReferenceParam();
300 
301   case Integral:
302     return getIntegralType() == Other.getIntegralType() &&
303            getAsIntegral() == Other.getAsIntegral();
304 
305   case Pack:
306     if (Args.NumArgs != Other.Args.NumArgs) return false;
307     for (unsigned I = 0, E = Args.NumArgs; I != E; ++I)
308       if (!Args.Args[I].structurallyEquals(Other.Args.Args[I]))
309         return false;
310     return true;
311   }
312 
313   llvm_unreachable("Invalid TemplateArgument Kind!");
314 }
315 
316 TemplateArgument TemplateArgument::getPackExpansionPattern() const {
317   assert(isPackExpansion());
318 
319   switch (getKind()) {
320   case Type:
321     return getAsType()->getAs<PackExpansionType>()->getPattern();
322 
323   case Expression:
324     return cast<PackExpansionExpr>(getAsExpr())->getPattern();
325 
326   case TemplateExpansion:
327     return TemplateArgument(getAsTemplateOrTemplatePattern());
328 
329   case Declaration:
330   case Integral:
331   case Pack:
332   case Null:
333   case Template:
334   case NullPtr:
335     return TemplateArgument();
336   }
337 
338   llvm_unreachable("Invalid TemplateArgument Kind!");
339 }
340 
341 void TemplateArgument::print(const PrintingPolicy &Policy,
342                              raw_ostream &Out) const {
343   switch (getKind()) {
344   case Null:
345     Out << "<no value>";
346     break;
347 
348   case Type: {
349     PrintingPolicy SubPolicy(Policy);
350     SubPolicy.SuppressStrongLifetime = true;
351     std::string TypeStr;
352     getAsType().getAsStringInternal(TypeStr, SubPolicy);
353     Out << TypeStr;
354     break;
355   }
356 
357   case Declaration: {
358     NamedDecl *ND = cast<NamedDecl>(getAsDecl());
359     if (ND->getDeclName()) {
360       // FIXME: distinguish between pointer and reference args?
361       Out << *ND;
362     } else {
363       Out << "<anonymous>";
364     }
365     break;
366   }
367 
368   case NullPtr:
369     Out << "nullptr";
370     break;
371 
372   case Template:
373     getAsTemplate().print(Out, Policy);
374     break;
375 
376   case TemplateExpansion:
377     getAsTemplateOrTemplatePattern().print(Out, Policy);
378     Out << "...";
379     break;
380 
381   case Integral: {
382     printIntegral(*this, Out);
383     break;
384   }
385 
386   case Expression:
387     getAsExpr()->printPretty(Out, 0, Policy);
388     break;
389 
390   case Pack:
391     Out << "<";
392     bool First = true;
393     for (TemplateArgument::pack_iterator P = pack_begin(), PEnd = pack_end();
394          P != PEnd; ++P) {
395       if (First)
396         First = false;
397       else
398         Out << ", ";
399 
400       P->print(Policy, Out);
401     }
402     Out << ">";
403     break;
404   }
405 }
406 
407 //===----------------------------------------------------------------------===//
408 // TemplateArgumentLoc Implementation
409 //===----------------------------------------------------------------------===//
410 
411 TemplateArgumentLocInfo::TemplateArgumentLocInfo() {
412   memset((void*)this, 0, sizeof(TemplateArgumentLocInfo));
413 }
414 
415 SourceRange TemplateArgumentLoc::getSourceRange() const {
416   switch (Argument.getKind()) {
417   case TemplateArgument::Expression:
418     return getSourceExpression()->getSourceRange();
419 
420   case TemplateArgument::Declaration:
421     return getSourceDeclExpression()->getSourceRange();
422 
423   case TemplateArgument::NullPtr:
424     return getSourceNullPtrExpression()->getSourceRange();
425 
426   case TemplateArgument::Type:
427     if (TypeSourceInfo *TSI = getTypeSourceInfo())
428       return TSI->getTypeLoc().getSourceRange();
429     else
430       return SourceRange();
431 
432   case TemplateArgument::Template:
433     if (getTemplateQualifierLoc())
434       return SourceRange(getTemplateQualifierLoc().getBeginLoc(),
435                          getTemplateNameLoc());
436     return SourceRange(getTemplateNameLoc());
437 
438   case TemplateArgument::TemplateExpansion:
439     if (getTemplateQualifierLoc())
440       return SourceRange(getTemplateQualifierLoc().getBeginLoc(),
441                          getTemplateEllipsisLoc());
442     return SourceRange(getTemplateNameLoc(), getTemplateEllipsisLoc());
443 
444   case TemplateArgument::Integral:
445     return getSourceIntegralExpression()->getSourceRange();
446 
447   case TemplateArgument::Pack:
448   case TemplateArgument::Null:
449     return SourceRange();
450   }
451 
452   llvm_unreachable("Invalid TemplateArgument Kind!");
453 }
454 
455 TemplateArgumentLoc
456 TemplateArgumentLoc::getPackExpansionPattern(SourceLocation &Ellipsis,
457                                        llvm::Optional<unsigned> &NumExpansions,
458                                              ASTContext &Context) const {
459   assert(Argument.isPackExpansion());
460 
461   switch (Argument.getKind()) {
462   case TemplateArgument::Type: {
463     // FIXME: We shouldn't ever have to worry about missing
464     // type-source info!
465     TypeSourceInfo *ExpansionTSInfo = getTypeSourceInfo();
466     if (!ExpansionTSInfo)
467       ExpansionTSInfo = Context.getTrivialTypeSourceInfo(
468                                                      getArgument().getAsType(),
469                                                          Ellipsis);
470     PackExpansionTypeLoc Expansion
471       = cast<PackExpansionTypeLoc>(ExpansionTSInfo->getTypeLoc());
472     Ellipsis = Expansion.getEllipsisLoc();
473 
474     TypeLoc Pattern = Expansion.getPatternLoc();
475     NumExpansions = Expansion.getTypePtr()->getNumExpansions();
476 
477     // FIXME: This is horrible. We know where the source location data is for
478     // the pattern, and we have the pattern's type, but we are forced to copy
479     // them into an ASTContext because TypeSourceInfo bundles them together
480     // and TemplateArgumentLoc traffics in TypeSourceInfo pointers.
481     TypeSourceInfo *PatternTSInfo
482       = Context.CreateTypeSourceInfo(Pattern.getType(),
483                                      Pattern.getFullDataSize());
484     memcpy(PatternTSInfo->getTypeLoc().getOpaqueData(),
485            Pattern.getOpaqueData(), Pattern.getFullDataSize());
486     return TemplateArgumentLoc(TemplateArgument(Pattern.getType()),
487                                PatternTSInfo);
488   }
489 
490   case TemplateArgument::Expression: {
491     PackExpansionExpr *Expansion
492       = cast<PackExpansionExpr>(Argument.getAsExpr());
493     Expr *Pattern = Expansion->getPattern();
494     Ellipsis = Expansion->getEllipsisLoc();
495     NumExpansions = Expansion->getNumExpansions();
496     return TemplateArgumentLoc(Pattern, Pattern);
497   }
498 
499   case TemplateArgument::TemplateExpansion:
500     Ellipsis = getTemplateEllipsisLoc();
501     NumExpansions = Argument.getNumTemplateExpansions();
502     return TemplateArgumentLoc(Argument.getPackExpansionPattern(),
503                                getTemplateQualifierLoc(),
504                                getTemplateNameLoc());
505 
506   case TemplateArgument::Declaration:
507   case TemplateArgument::NullPtr:
508   case TemplateArgument::Template:
509   case TemplateArgument::Integral:
510   case TemplateArgument::Pack:
511   case TemplateArgument::Null:
512     return TemplateArgumentLoc();
513   }
514 
515   llvm_unreachable("Invalid TemplateArgument Kind!");
516 }
517 
518 const DiagnosticBuilder &clang::operator<<(const DiagnosticBuilder &DB,
519                                            const TemplateArgument &Arg) {
520   switch (Arg.getKind()) {
521   case TemplateArgument::Null:
522     // This is bad, but not as bad as crashing because of argument
523     // count mismatches.
524     return DB << "(null template argument)";
525 
526   case TemplateArgument::Type:
527     return DB << Arg.getAsType();
528 
529   case TemplateArgument::Declaration:
530     return DB << Arg.getAsDecl();
531 
532   case TemplateArgument::NullPtr:
533     return DB << "nullptr";
534 
535   case TemplateArgument::Integral:
536     return DB << Arg.getAsIntegral().toString(10);
537 
538   case TemplateArgument::Template:
539     return DB << Arg.getAsTemplate();
540 
541   case TemplateArgument::TemplateExpansion:
542     return DB << Arg.getAsTemplateOrTemplatePattern() << "...";
543 
544   case TemplateArgument::Expression: {
545     // This shouldn't actually ever happen, so it's okay that we're
546     // regurgitating an expression here.
547     // FIXME: We're guessing at LangOptions!
548     SmallString<32> Str;
549     llvm::raw_svector_ostream OS(Str);
550     LangOptions LangOpts;
551     LangOpts.CPlusPlus = true;
552     PrintingPolicy Policy(LangOpts);
553     Arg.getAsExpr()->printPretty(OS, 0, Policy);
554     return DB << OS.str();
555   }
556 
557   case TemplateArgument::Pack: {
558     // FIXME: We're guessing at LangOptions!
559     SmallString<32> Str;
560     llvm::raw_svector_ostream OS(Str);
561     LangOptions LangOpts;
562     LangOpts.CPlusPlus = true;
563     PrintingPolicy Policy(LangOpts);
564     Arg.print(Policy, OS);
565     return DB << OS.str();
566   }
567   }
568 
569   llvm_unreachable("Invalid TemplateArgument Kind!");
570 }
571 
572 const ASTTemplateArgumentListInfo *
573 ASTTemplateArgumentListInfo::Create(ASTContext &C,
574                                     const TemplateArgumentListInfo &List) {
575   std::size_t size = ASTTemplateArgumentListInfo::sizeFor(List.size());
576   void *Mem = C.Allocate(size, llvm::alignOf<ASTTemplateArgumentListInfo>());
577   ASTTemplateArgumentListInfo *TAI = new (Mem) ASTTemplateArgumentListInfo();
578   TAI->initializeFrom(List);
579   return TAI;
580 }
581 
582 void ASTTemplateArgumentListInfo::initializeFrom(
583                                       const TemplateArgumentListInfo &Info) {
584   LAngleLoc = Info.getLAngleLoc();
585   RAngleLoc = Info.getRAngleLoc();
586   NumTemplateArgs = Info.size();
587 
588   TemplateArgumentLoc *ArgBuffer = getTemplateArgs();
589   for (unsigned i = 0; i != NumTemplateArgs; ++i)
590     new (&ArgBuffer[i]) TemplateArgumentLoc(Info[i]);
591 }
592 
593 void ASTTemplateArgumentListInfo::initializeFrom(
594                                           const TemplateArgumentListInfo &Info,
595                                                   bool &Dependent,
596                                                   bool &InstantiationDependent,
597                                        bool &ContainsUnexpandedParameterPack) {
598   LAngleLoc = Info.getLAngleLoc();
599   RAngleLoc = Info.getRAngleLoc();
600   NumTemplateArgs = Info.size();
601 
602   TemplateArgumentLoc *ArgBuffer = getTemplateArgs();
603   for (unsigned i = 0; i != NumTemplateArgs; ++i) {
604     Dependent = Dependent || Info[i].getArgument().isDependent();
605     InstantiationDependent = InstantiationDependent ||
606                              Info[i].getArgument().isInstantiationDependent();
607     ContainsUnexpandedParameterPack
608       = ContainsUnexpandedParameterPack ||
609         Info[i].getArgument().containsUnexpandedParameterPack();
610 
611     new (&ArgBuffer[i]) TemplateArgumentLoc(Info[i]);
612   }
613 }
614 
615 void ASTTemplateArgumentListInfo::copyInto(
616                                       TemplateArgumentListInfo &Info) const {
617   Info.setLAngleLoc(LAngleLoc);
618   Info.setRAngleLoc(RAngleLoc);
619   for (unsigned I = 0; I != NumTemplateArgs; ++I)
620     Info.addArgument(getTemplateArgs()[I]);
621 }
622 
623 std::size_t ASTTemplateArgumentListInfo::sizeFor(unsigned NumTemplateArgs) {
624   return sizeof(ASTTemplateArgumentListInfo) +
625          sizeof(TemplateArgumentLoc) * NumTemplateArgs;
626 }
627 
628 void
629 ASTTemplateKWAndArgsInfo::initializeFrom(SourceLocation TemplateKWLoc,
630                                          const TemplateArgumentListInfo &Info) {
631   Base::initializeFrom(Info);
632   setTemplateKeywordLoc(TemplateKWLoc);
633 }
634 
635 void
636 ASTTemplateKWAndArgsInfo
637 ::initializeFrom(SourceLocation TemplateKWLoc,
638                  const TemplateArgumentListInfo &Info,
639                  bool &Dependent,
640                  bool &InstantiationDependent,
641                  bool &ContainsUnexpandedParameterPack) {
642   Base::initializeFrom(Info, Dependent, InstantiationDependent,
643                        ContainsUnexpandedParameterPack);
644   setTemplateKeywordLoc(TemplateKWLoc);
645 }
646 
647 void
648 ASTTemplateKWAndArgsInfo::initializeFrom(SourceLocation TemplateKWLoc) {
649   // No explicit template arguments, but template keyword loc is valid.
650   assert(TemplateKWLoc.isValid());
651   LAngleLoc = SourceLocation();
652   RAngleLoc = SourceLocation();
653   NumTemplateArgs = 0;
654   setTemplateKeywordLoc(TemplateKWLoc);
655 }
656 
657 std::size_t
658 ASTTemplateKWAndArgsInfo::sizeFor(unsigned NumTemplateArgs) {
659   // Add space for the template keyword location.
660   // FIXME: There's room for this in the padding before the template args in
661   //        64-bit builds.
662   return Base::sizeFor(NumTemplateArgs) + sizeof(SourceLocation);
663 }
664