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