1 //===- TemplateBase.cpp - Common template AST class implementation --------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements common classes used throughout C++ template
10 // representations.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "clang/AST/TemplateBase.h"
15 #include "clang/AST/ASTContext.h"
16 #include "clang/AST/Decl.h"
17 #include "clang/AST/DeclBase.h"
18 #include "clang/AST/DeclTemplate.h"
19 #include "clang/AST/DependenceFlags.h"
20 #include "clang/AST/Expr.h"
21 #include "clang/AST/ExprCXX.h"
22 #include "clang/AST/PrettyPrinter.h"
23 #include "clang/AST/TemplateName.h"
24 #include "clang/AST/Type.h"
25 #include "clang/AST/TypeLoc.h"
26 #include "clang/Basic/Diagnostic.h"
27 #include "clang/Basic/LLVM.h"
28 #include "clang/Basic/LangOptions.h"
29 #include "clang/Basic/SourceLocation.h"
30 #include "llvm/ADT/APSInt.h"
31 #include "llvm/ADT/FoldingSet.h"
32 #include "llvm/ADT/None.h"
33 #include "llvm/ADT/SmallString.h"
34 #include "llvm/ADT/StringExtras.h"
35 #include "llvm/ADT/StringRef.h"
36 #include "llvm/Support/Casting.h"
37 #include "llvm/Support/Compiler.h"
38 #include "llvm/Support/ErrorHandling.h"
39 #include "llvm/Support/raw_ostream.h"
40 #include <cassert>
41 #include <cstddef>
42 #include <cstdint>
43 #include <cstring>
44 
45 using namespace clang;
46 
47 /// Print a template integral argument value.
48 ///
49 /// \param TemplArg the TemplateArgument instance to print.
50 ///
51 /// \param Out the raw_ostream instance to use for printing.
52 ///
53 /// \param Policy the printing policy for EnumConstantDecl printing.
54 ///
55 /// \param IncludeType If set, ensure that the type of the expression printed
56 /// matches the type of the template argument.
57 static void printIntegral(const TemplateArgument &TemplArg, raw_ostream &Out,
58                           const PrintingPolicy &Policy, bool IncludeType) {
59   const Type *T = TemplArg.getIntegralType().getTypePtr();
60   const llvm::APSInt &Val = TemplArg.getAsIntegral();
61 
62   if (const EnumType *ET = T->getAs<EnumType>()) {
63     for (const EnumConstantDecl* ECD : ET->getDecl()->enumerators()) {
64       // In Sema::CheckTemplateArugment, enum template arguments value are
65       // extended to the size of the integer underlying the enum type.  This
66       // may create a size difference between the enum value and template
67       // argument value, requiring isSameValue here instead of operator==.
68       if (llvm::APSInt::isSameValue(ECD->getInitVal(), Val)) {
69         ECD->printQualifiedName(Out, Policy);
70         return;
71       }
72     }
73   }
74 
75   if (Policy.MSVCFormatting)
76     IncludeType = false;
77 
78   if (T->isBooleanType()) {
79     if (!Policy.MSVCFormatting)
80       Out << (Val.getBoolValue() ? "true" : "false");
81     else
82       Out << Val;
83   } else if (T->isCharType()) {
84     if (IncludeType) {
85       if (T->isSpecificBuiltinType(BuiltinType::SChar))
86         Out << "(signed char)";
87       else if (T->isSpecificBuiltinType(BuiltinType::UChar))
88         Out << "(unsigned char)";
89     }
90     CharacterLiteral::print(Val.getZExtValue(), CharacterLiteral::Ascii, Out);
91   } else if (T->isAnyCharacterType() && !Policy.MSVCFormatting) {
92     CharacterLiteral::CharacterKind Kind;
93     if (T->isWideCharType())
94       Kind = CharacterLiteral::Wide;
95     else if (T->isChar8Type())
96       Kind = CharacterLiteral::UTF8;
97     else if (T->isChar16Type())
98       Kind = CharacterLiteral::UTF16;
99     else if (T->isChar32Type())
100       Kind = CharacterLiteral::UTF32;
101     else
102       Kind = CharacterLiteral::Ascii;
103     CharacterLiteral::print(Val.getExtValue(), Kind, Out);
104   } else if (IncludeType) {
105     if (const auto *BT = T->getAs<BuiltinType>()) {
106       switch (BT->getKind()) {
107       case BuiltinType::ULongLong:
108         Out << Val << "ULL";
109         break;
110       case BuiltinType::LongLong:
111         Out << Val << "LL";
112         break;
113       case BuiltinType::ULong:
114         Out << Val << "UL";
115         break;
116       case BuiltinType::Long:
117         Out << Val << "L";
118         break;
119       case BuiltinType::UInt:
120         Out << Val << "U";
121         break;
122       case BuiltinType::Int:
123         Out << Val;
124         break;
125       default:
126         Out << "(" << T->getCanonicalTypeInternal().getAsString(Policy) << ")"
127             << Val;
128         break;
129       }
130     } else
131       Out << "(" << T->getCanonicalTypeInternal().getAsString(Policy) << ")"
132           << Val;
133   } else
134     Out << Val;
135 }
136 
137 static unsigned getArrayDepth(QualType type) {
138   unsigned count = 0;
139   while (const auto *arrayType = type->getAsArrayTypeUnsafe()) {
140     count++;
141     type = arrayType->getElementType();
142   }
143   return count;
144 }
145 
146 static bool needsAmpersandOnTemplateArg(QualType paramType, QualType argType) {
147   // Generally, if the parameter type is a pointer, we must be taking the
148   // address of something and need a &.  However, if the argument is an array,
149   // this could be implicit via array-to-pointer decay.
150   if (!paramType->isPointerType())
151     return paramType->isMemberPointerType();
152   if (argType->isArrayType())
153     return getArrayDepth(argType) == getArrayDepth(paramType->getPointeeType());
154   return true;
155 }
156 
157 //===----------------------------------------------------------------------===//
158 // TemplateArgument Implementation
159 //===----------------------------------------------------------------------===//
160 
161 TemplateArgument::TemplateArgument(ASTContext &Ctx, const llvm::APSInt &Value,
162                                    QualType Type) {
163   Integer.Kind = Integral;
164   // Copy the APSInt value into our decomposed form.
165   Integer.BitWidth = Value.getBitWidth();
166   Integer.IsUnsigned = Value.isUnsigned();
167   // If the value is large, we have to get additional memory from the ASTContext
168   unsigned NumWords = Value.getNumWords();
169   if (NumWords > 1) {
170     void *Mem = Ctx.Allocate(NumWords * sizeof(uint64_t));
171     std::memcpy(Mem, Value.getRawData(), NumWords * sizeof(uint64_t));
172     Integer.pVal = static_cast<uint64_t *>(Mem);
173   } else {
174     Integer.VAL = Value.getZExtValue();
175   }
176 
177   Integer.Type = Type.getAsOpaquePtr();
178 }
179 
180 TemplateArgument
181 TemplateArgument::CreatePackCopy(ASTContext &Context,
182                                  ArrayRef<TemplateArgument> Args) {
183   if (Args.empty())
184     return getEmptyPack();
185 
186   return TemplateArgument(Args.copy(Context));
187 }
188 
189 TemplateArgumentDependence TemplateArgument::getDependence() const {
190   auto Deps = TemplateArgumentDependence::None;
191   switch (getKind()) {
192   case Null:
193     llvm_unreachable("Should not have a NULL template argument");
194 
195   case Type:
196     Deps = toTemplateArgumentDependence(getAsType()->getDependence());
197     if (isa<PackExpansionType>(getAsType()))
198       Deps |= TemplateArgumentDependence::Dependent;
199     return Deps;
200 
201   case Template:
202     return toTemplateArgumentDependence(getAsTemplate().getDependence());
203 
204   case TemplateExpansion:
205     return TemplateArgumentDependence::Dependent |
206            TemplateArgumentDependence::Instantiation;
207 
208   case Declaration: {
209     auto *DC = dyn_cast<DeclContext>(getAsDecl());
210     if (!DC)
211       DC = getAsDecl()->getDeclContext();
212     if (DC->isDependentContext())
213       Deps = TemplateArgumentDependence::Dependent |
214              TemplateArgumentDependence::Instantiation;
215     return Deps;
216   }
217 
218   case NullPtr:
219   case Integral:
220     return TemplateArgumentDependence::None;
221 
222   case Expression:
223     Deps = toTemplateArgumentDependence(getAsExpr()->getDependence());
224     if (isa<PackExpansionExpr>(getAsExpr()))
225       Deps |= TemplateArgumentDependence::Dependent |
226               TemplateArgumentDependence::Instantiation;
227     return Deps;
228 
229   case Pack:
230     for (const auto &P : pack_elements())
231       Deps |= P.getDependence();
232     return Deps;
233   }
234   llvm_unreachable("unhandled ArgKind");
235 }
236 
237 bool TemplateArgument::isDependent() const {
238   return getDependence() & TemplateArgumentDependence::Dependent;
239 }
240 
241 bool TemplateArgument::isInstantiationDependent() const {
242   return getDependence() & TemplateArgumentDependence::Instantiation;
243 }
244 
245 bool TemplateArgument::isPackExpansion() const {
246   switch (getKind()) {
247   case Null:
248   case Declaration:
249   case Integral:
250   case Pack:
251   case Template:
252   case NullPtr:
253     return false;
254 
255   case TemplateExpansion:
256     return true;
257 
258   case Type:
259     return isa<PackExpansionType>(getAsType());
260 
261   case Expression:
262     return isa<PackExpansionExpr>(getAsExpr());
263   }
264 
265   llvm_unreachable("Invalid TemplateArgument Kind!");
266 }
267 
268 bool TemplateArgument::containsUnexpandedParameterPack() const {
269   return getDependence() & TemplateArgumentDependence::UnexpandedPack;
270 }
271 
272 Optional<unsigned> TemplateArgument::getNumTemplateExpansions() const {
273   assert(getKind() == TemplateExpansion);
274   if (TemplateArg.NumExpansions)
275     return TemplateArg.NumExpansions - 1;
276 
277   return None;
278 }
279 
280 QualType TemplateArgument::getNonTypeTemplateArgumentType() const {
281   switch (getKind()) {
282   case TemplateArgument::Null:
283   case TemplateArgument::Type:
284   case TemplateArgument::Template:
285   case TemplateArgument::TemplateExpansion:
286   case TemplateArgument::Pack:
287     return QualType();
288 
289   case TemplateArgument::Integral:
290     return getIntegralType();
291 
292   case TemplateArgument::Expression:
293     return getAsExpr()->getType();
294 
295   case TemplateArgument::Declaration:
296     return getParamTypeForDecl();
297 
298   case TemplateArgument::NullPtr:
299     return getNullPtrType();
300   }
301 
302   llvm_unreachable("Invalid TemplateArgument Kind!");
303 }
304 
305 void TemplateArgument::Profile(llvm::FoldingSetNodeID &ID,
306                                const ASTContext &Context) const {
307   ID.AddInteger(getKind());
308   switch (getKind()) {
309   case Null:
310     break;
311 
312   case Type:
313     getAsType().Profile(ID);
314     break;
315 
316   case NullPtr:
317     getNullPtrType().Profile(ID);
318     break;
319 
320   case Declaration:
321     getParamTypeForDecl().Profile(ID);
322     ID.AddPointer(getAsDecl()? getAsDecl()->getCanonicalDecl() : nullptr);
323     break;
324 
325   case Template:
326   case TemplateExpansion: {
327     TemplateName Template = getAsTemplateOrTemplatePattern();
328     if (TemplateTemplateParmDecl *TTP
329           = dyn_cast_or_null<TemplateTemplateParmDecl>(
330                                                 Template.getAsTemplateDecl())) {
331       ID.AddBoolean(true);
332       ID.AddInteger(TTP->getDepth());
333       ID.AddInteger(TTP->getPosition());
334       ID.AddBoolean(TTP->isParameterPack());
335     } else {
336       ID.AddBoolean(false);
337       ID.AddPointer(Context.getCanonicalTemplateName(Template)
338                                                           .getAsVoidPointer());
339     }
340     break;
341   }
342 
343   case Integral:
344     getAsIntegral().Profile(ID);
345     getIntegralType().Profile(ID);
346     break;
347 
348   case Expression:
349     getAsExpr()->Profile(ID, Context, true);
350     break;
351 
352   case Pack:
353     ID.AddInteger(Args.NumArgs);
354     for (unsigned I = 0; I != Args.NumArgs; ++I)
355       Args.Args[I].Profile(ID, Context);
356   }
357 }
358 
359 bool TemplateArgument::structurallyEquals(const TemplateArgument &Other) const {
360   if (getKind() != Other.getKind()) return false;
361 
362   switch (getKind()) {
363   case Null:
364   case Type:
365   case Expression:
366   case NullPtr:
367     return TypeOrValue.V == Other.TypeOrValue.V;
368 
369   case Template:
370   case TemplateExpansion:
371     return TemplateArg.Name == Other.TemplateArg.Name &&
372            TemplateArg.NumExpansions == Other.TemplateArg.NumExpansions;
373 
374   case Declaration:
375     return getAsDecl() == Other.getAsDecl();
376 
377   case Integral:
378     return getIntegralType() == Other.getIntegralType() &&
379            getAsIntegral() == Other.getAsIntegral();
380 
381   case Pack:
382     if (Args.NumArgs != Other.Args.NumArgs) return false;
383     for (unsigned I = 0, E = Args.NumArgs; I != E; ++I)
384       if (!Args.Args[I].structurallyEquals(Other.Args.Args[I]))
385         return false;
386     return true;
387   }
388 
389   llvm_unreachable("Invalid TemplateArgument Kind!");
390 }
391 
392 TemplateArgument TemplateArgument::getPackExpansionPattern() const {
393   assert(isPackExpansion());
394 
395   switch (getKind()) {
396   case Type:
397     return getAsType()->castAs<PackExpansionType>()->getPattern();
398 
399   case Expression:
400     return cast<PackExpansionExpr>(getAsExpr())->getPattern();
401 
402   case TemplateExpansion:
403     return TemplateArgument(getAsTemplateOrTemplatePattern());
404 
405   case Declaration:
406   case Integral:
407   case Pack:
408   case Null:
409   case Template:
410   case NullPtr:
411     return TemplateArgument();
412   }
413 
414   llvm_unreachable("Invalid TemplateArgument Kind!");
415 }
416 
417 void TemplateArgument::print(const PrintingPolicy &Policy, raw_ostream &Out,
418                              bool IncludeType) const {
419 
420   switch (getKind()) {
421   case Null:
422     Out << "(no value)";
423     break;
424 
425   case Type: {
426     PrintingPolicy SubPolicy(Policy);
427     SubPolicy.SuppressStrongLifetime = true;
428     getAsType().print(Out, SubPolicy);
429     break;
430   }
431 
432   case Declaration: {
433     // FIXME: Include the type if it's not obvious from the context.
434     NamedDecl *ND = getAsDecl();
435     if (getParamTypeForDecl()->isRecordType()) {
436       if (auto *TPO = dyn_cast<TemplateParamObjectDecl>(ND)) {
437         TPO->printAsInit(Out);
438         break;
439       }
440     }
441     if (auto *VD = dyn_cast<ValueDecl>(ND)) {
442       if (needsAmpersandOnTemplateArg(getParamTypeForDecl(), VD->getType()))
443         Out << "&";
444     }
445     ND->printQualifiedName(Out);
446     break;
447   }
448 
449   case NullPtr:
450     // FIXME: Include the type if it's not obvious from the context.
451     Out << "nullptr";
452     break;
453 
454   case Template:
455     getAsTemplate().print(Out, Policy);
456     break;
457 
458   case TemplateExpansion:
459     getAsTemplateOrTemplatePattern().print(Out, Policy);
460     Out << "...";
461     break;
462 
463   case Integral:
464     printIntegral(*this, Out, Policy, IncludeType);
465     break;
466 
467   case Expression:
468     getAsExpr()->printPretty(Out, nullptr, Policy);
469     break;
470 
471   case Pack:
472     Out << "<";
473     bool First = true;
474     for (const auto &P : pack_elements()) {
475       if (First)
476         First = false;
477       else
478         Out << ", ";
479 
480       P.print(Policy, Out, IncludeType);
481     }
482     Out << ">";
483     break;
484   }
485 }
486 
487 void TemplateArgument::dump(raw_ostream &Out) const {
488   LangOptions LO; // FIXME! see also TemplateName::dump().
489   LO.CPlusPlus = true;
490   LO.Bool = true;
491   print(PrintingPolicy(LO), Out, /*IncludeType*/ true);
492 }
493 
494 LLVM_DUMP_METHOD void TemplateArgument::dump() const { dump(llvm::errs()); }
495 
496 //===----------------------------------------------------------------------===//
497 // TemplateArgumentLoc Implementation
498 //===----------------------------------------------------------------------===//
499 
500 SourceRange TemplateArgumentLoc::getSourceRange() const {
501   switch (Argument.getKind()) {
502   case TemplateArgument::Expression:
503     return getSourceExpression()->getSourceRange();
504 
505   case TemplateArgument::Declaration:
506     return getSourceDeclExpression()->getSourceRange();
507 
508   case TemplateArgument::NullPtr:
509     return getSourceNullPtrExpression()->getSourceRange();
510 
511   case TemplateArgument::Type:
512     if (TypeSourceInfo *TSI = getTypeSourceInfo())
513       return TSI->getTypeLoc().getSourceRange();
514     else
515       return SourceRange();
516 
517   case TemplateArgument::Template:
518     if (getTemplateQualifierLoc())
519       return SourceRange(getTemplateQualifierLoc().getBeginLoc(),
520                          getTemplateNameLoc());
521     return SourceRange(getTemplateNameLoc());
522 
523   case TemplateArgument::TemplateExpansion:
524     if (getTemplateQualifierLoc())
525       return SourceRange(getTemplateQualifierLoc().getBeginLoc(),
526                          getTemplateEllipsisLoc());
527     return SourceRange(getTemplateNameLoc(), getTemplateEllipsisLoc());
528 
529   case TemplateArgument::Integral:
530     return getSourceIntegralExpression()->getSourceRange();
531 
532   case TemplateArgument::Pack:
533   case TemplateArgument::Null:
534     return SourceRange();
535   }
536 
537   llvm_unreachable("Invalid TemplateArgument Kind!");
538 }
539 
540 template <typename T>
541 static const T &DiagTemplateArg(const T &DB, const TemplateArgument &Arg) {
542   switch (Arg.getKind()) {
543   case TemplateArgument::Null:
544     // This is bad, but not as bad as crashing because of argument
545     // count mismatches.
546     return DB << "(null template argument)";
547 
548   case TemplateArgument::Type:
549     return DB << Arg.getAsType();
550 
551   case TemplateArgument::Declaration:
552     return DB << Arg.getAsDecl();
553 
554   case TemplateArgument::NullPtr:
555     return DB << "nullptr";
556 
557   case TemplateArgument::Integral:
558     return DB << toString(Arg.getAsIntegral(), 10);
559 
560   case TemplateArgument::Template:
561     return DB << Arg.getAsTemplate();
562 
563   case TemplateArgument::TemplateExpansion:
564     return DB << Arg.getAsTemplateOrTemplatePattern() << "...";
565 
566   case TemplateArgument::Expression: {
567     // This shouldn't actually ever happen, so it's okay that we're
568     // regurgitating an expression here.
569     // FIXME: We're guessing at LangOptions!
570     SmallString<32> Str;
571     llvm::raw_svector_ostream OS(Str);
572     LangOptions LangOpts;
573     LangOpts.CPlusPlus = true;
574     PrintingPolicy Policy(LangOpts);
575     Arg.getAsExpr()->printPretty(OS, nullptr, Policy);
576     return DB << OS.str();
577   }
578 
579   case TemplateArgument::Pack: {
580     // FIXME: We're guessing at LangOptions!
581     SmallString<32> Str;
582     llvm::raw_svector_ostream OS(Str);
583     LangOptions LangOpts;
584     LangOpts.CPlusPlus = true;
585     PrintingPolicy Policy(LangOpts);
586     Arg.print(Policy, OS, /*IncludeType*/ true);
587     return DB << OS.str();
588   }
589   }
590 
591   llvm_unreachable("Invalid TemplateArgument Kind!");
592 }
593 
594 const StreamingDiagnostic &clang::operator<<(const StreamingDiagnostic &DB,
595                                              const TemplateArgument &Arg) {
596   return DiagTemplateArg(DB, Arg);
597 }
598 
599 clang::TemplateArgumentLocInfo::TemplateArgumentLocInfo(
600     ASTContext &Ctx, NestedNameSpecifierLoc QualifierLoc,
601     SourceLocation TemplateNameLoc, SourceLocation EllipsisLoc) {
602   TemplateTemplateArgLocInfo *Template = new (Ctx) TemplateTemplateArgLocInfo;
603   Template->Qualifier = QualifierLoc.getNestedNameSpecifier();
604   Template->QualifierLocData = QualifierLoc.getOpaqueData();
605   Template->TemplateNameLoc = TemplateNameLoc;
606   Template->EllipsisLoc = EllipsisLoc;
607   Pointer = Template;
608 }
609 
610 const ASTTemplateArgumentListInfo *
611 ASTTemplateArgumentListInfo::Create(const ASTContext &C,
612                                     const TemplateArgumentListInfo &List) {
613   std::size_t size = totalSizeToAlloc<TemplateArgumentLoc>(List.size());
614   void *Mem = C.Allocate(size, alignof(ASTTemplateArgumentListInfo));
615   return new (Mem) ASTTemplateArgumentListInfo(List);
616 }
617 
618 ASTTemplateArgumentListInfo::ASTTemplateArgumentListInfo(
619     const TemplateArgumentListInfo &Info) {
620   LAngleLoc = Info.getLAngleLoc();
621   RAngleLoc = Info.getRAngleLoc();
622   NumTemplateArgs = Info.size();
623 
624   TemplateArgumentLoc *ArgBuffer = getTrailingObjects<TemplateArgumentLoc>();
625   for (unsigned i = 0; i != NumTemplateArgs; ++i)
626     new (&ArgBuffer[i]) TemplateArgumentLoc(Info[i]);
627 }
628 
629 void ASTTemplateKWAndArgsInfo::initializeFrom(
630     SourceLocation TemplateKWLoc, const TemplateArgumentListInfo &Info,
631     TemplateArgumentLoc *OutArgArray) {
632   this->TemplateKWLoc = TemplateKWLoc;
633   LAngleLoc = Info.getLAngleLoc();
634   RAngleLoc = Info.getRAngleLoc();
635   NumTemplateArgs = Info.size();
636 
637   for (unsigned i = 0; i != NumTemplateArgs; ++i)
638     new (&OutArgArray[i]) TemplateArgumentLoc(Info[i]);
639 }
640 
641 void ASTTemplateKWAndArgsInfo::initializeFrom(SourceLocation TemplateKWLoc) {
642   assert(TemplateKWLoc.isValid());
643   LAngleLoc = SourceLocation();
644   RAngleLoc = SourceLocation();
645   this->TemplateKWLoc = TemplateKWLoc;
646   NumTemplateArgs = 0;
647 }
648 
649 void ASTTemplateKWAndArgsInfo::initializeFrom(
650     SourceLocation TemplateKWLoc, const TemplateArgumentListInfo &Info,
651     TemplateArgumentLoc *OutArgArray, TemplateArgumentDependence &Deps) {
652   this->TemplateKWLoc = TemplateKWLoc;
653   LAngleLoc = Info.getLAngleLoc();
654   RAngleLoc = Info.getRAngleLoc();
655   NumTemplateArgs = Info.size();
656 
657   for (unsigned i = 0; i != NumTemplateArgs; ++i) {
658     Deps |= Info[i].getArgument().getDependence();
659 
660     new (&OutArgArray[i]) TemplateArgumentLoc(Info[i]);
661   }
662 }
663 
664 void ASTTemplateKWAndArgsInfo::copyInto(const TemplateArgumentLoc *ArgArray,
665                                         TemplateArgumentListInfo &Info) const {
666   Info.setLAngleLoc(LAngleLoc);
667   Info.setRAngleLoc(RAngleLoc);
668   for (unsigned I = 0; I != NumTemplateArgs; ++I)
669     Info.addArgument(ArgArray[I]);
670 }
671