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