1//===-- TemplateBase.h - Core classes for C++ templates ---------*- C++ -*-===//
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 provides definitions which are common for all kinds of
11//  template representation.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CLANG_AST_TEMPLATEBASE_H
16#define LLVM_CLANG_AST_TEMPLATEBASE_H
17
18#include "clang/AST/TemplateName.h"
19#include "clang/AST/Type.h"
20#include "llvm/ADT/APSInt.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/iterator_range.h"
23#include "llvm/Support/Compiler.h"
24#include "llvm/Support/ErrorHandling.h"
25#include "llvm/Support/TrailingObjects.h"
26
27namespace llvm {
28  class FoldingSetNodeID;
29}
30
31namespace clang {
32
33class DiagnosticBuilder;
34class Expr;
35struct PrintingPolicy;
36class TypeSourceInfo;
37class ValueDecl;
38
39/// \brief Represents a template argument.
40class TemplateArgument {
41public:
42  /// \brief The kind of template argument we're storing.
43  enum ArgKind {
44    /// \brief Represents an empty template argument, e.g., one that has not
45    /// been deduced.
46    Null = 0,
47    /// The template argument is a type.
48    Type,
49    /// The template argument is a declaration that was provided for a pointer,
50    /// reference, or pointer to member non-type template parameter.
51    Declaration,
52    /// The template argument is a null pointer or null pointer to member that
53    /// was provided for a non-type template parameter.
54    NullPtr,
55    /// The template argument is an integral value stored in an llvm::APSInt
56    /// that was provided for an integral non-type template parameter.
57    Integral,
58    /// The template argument is a template name that was provided for a
59    /// template template parameter.
60    Template,
61    /// The template argument is a pack expansion of a template name that was
62    /// provided for a template template parameter.
63    TemplateExpansion,
64    /// The template argument is an expression, and we've not resolved it to one
65    /// of the other forms yet, either because it's dependent or because we're
66    /// representing a non-canonical template argument (for instance, in a
67    /// TemplateSpecializationType). Also used to represent a non-dependent
68    /// __uuidof expression (a Microsoft extension).
69    Expression,
70    /// The template argument is actually a parameter pack. Arguments are stored
71    /// in the Args struct.
72    Pack
73  };
74
75private:
76  /// \brief The kind of template argument we're storing.
77
78  struct DA {
79    unsigned Kind;
80    void *QT;
81    ValueDecl *D;
82  };
83  struct I {
84    unsigned Kind;
85    // We store a decomposed APSInt with the data allocated by ASTContext if
86    // BitWidth > 64. The memory may be shared between multiple
87    // TemplateArgument instances.
88    unsigned BitWidth : 31;
89    unsigned IsUnsigned : 1;
90    union {
91      uint64_t VAL;          ///< Used to store the <= 64 bits integer value.
92      const uint64_t *pVal;  ///< Used to store the >64 bits integer value.
93    };
94    void *Type;
95  };
96  struct A {
97    unsigned Kind;
98    unsigned NumArgs;
99    const TemplateArgument *Args;
100  };
101  struct TA {
102    unsigned Kind;
103    unsigned NumExpansions;
104    void *Name;
105  };
106  struct TV {
107    unsigned Kind;
108    uintptr_t V;
109  };
110  union {
111    struct DA DeclArg;
112    struct I Integer;
113    struct A Args;
114    struct TA TemplateArg;
115    struct TV TypeOrValue;
116  };
117
118  TemplateArgument(TemplateName, bool) = delete;
119
120public:
121  /// \brief Construct an empty, invalid template argument.
122  constexpr TemplateArgument() : TypeOrValue({Null, 0}) {}
123
124  /// \brief Construct a template type argument.
125  TemplateArgument(QualType T, bool isNullPtr = false) {
126    TypeOrValue.Kind = isNullPtr ? NullPtr : Type;
127    TypeOrValue.V = reinterpret_cast<uintptr_t>(T.getAsOpaquePtr());
128  }
129
130  /// \brief Construct a template argument that refers to a
131  /// declaration, which is either an external declaration or a
132  /// template declaration.
133  TemplateArgument(ValueDecl *D, QualType QT) {
134    assert(D && "Expected decl");
135    DeclArg.Kind = Declaration;
136    DeclArg.QT = QT.getAsOpaquePtr();
137    DeclArg.D = D;
138  }
139
140  /// \brief Construct an integral constant template argument. The memory to
141  /// store the value is allocated with Ctx.
142  TemplateArgument(ASTContext &Ctx, const llvm::APSInt &Value, QualType Type);
143
144  /// \brief Construct an integral constant template argument with the same
145  /// value as Other but a different type.
146  TemplateArgument(const TemplateArgument &Other, QualType Type) {
147    Integer = Other.Integer;
148    Integer.Type = Type.getAsOpaquePtr();
149  }
150
151  /// \brief Construct a template argument that is a template.
152  ///
153  /// This form of template argument is generally used for template template
154  /// parameters. However, the template name could be a dependent template
155  /// name that ends up being instantiated to a function template whose address
156  /// is taken.
157  ///
158  /// \param Name The template name.
159  TemplateArgument(TemplateName Name) {
160    TemplateArg.Kind = Template;
161    TemplateArg.Name = Name.getAsVoidPointer();
162    TemplateArg.NumExpansions = 0;
163  }
164
165  /// \brief Construct a template argument that is a template pack expansion.
166  ///
167  /// This form of template argument is generally used for template template
168  /// parameters. However, the template name could be a dependent template
169  /// name that ends up being instantiated to a function template whose address
170  /// is taken.
171  ///
172  /// \param Name The template name.
173  ///
174  /// \param NumExpansions The number of expansions that will be generated by
175  /// instantiating
176  TemplateArgument(TemplateName Name, Optional<unsigned> NumExpansions) {
177    TemplateArg.Kind = TemplateExpansion;
178    TemplateArg.Name = Name.getAsVoidPointer();
179    if (NumExpansions)
180      TemplateArg.NumExpansions = *NumExpansions + 1;
181    else
182      TemplateArg.NumExpansions = 0;
183  }
184
185  /// \brief Construct a template argument that is an expression.
186  ///
187  /// This form of template argument only occurs in template argument
188  /// lists used for dependent types and for expression; it will not
189  /// occur in a non-dependent, canonical template argument list.
190  TemplateArgument(Expr *E) {
191    TypeOrValue.Kind = Expression;
192    TypeOrValue.V = reinterpret_cast<uintptr_t>(E);
193  }
194
195  /// \brief Construct a template argument that is a template argument pack.
196  ///
197  /// We assume that storage for the template arguments provided
198  /// outlives the TemplateArgument itself.
199  explicit TemplateArgument(ArrayRef<TemplateArgument> Args) {
200    this->Args.Kind = Pack;
201    this->Args.Args = Args.data();
202    this->Args.NumArgs = Args.size();
203  }
204
205  static TemplateArgument getEmptyPack() { return TemplateArgument(None); }
206
207  /// \brief Create a new template argument pack by copying the given set of
208  /// template arguments.
209  static TemplateArgument CreatePackCopy(ASTContext &Context,
210                                         ArrayRef<TemplateArgument> Args);
211
212  /// \brief Return the kind of stored template argument.
213  ArgKind getKind() const { return (ArgKind)TypeOrValue.Kind; }
214
215  /// \brief Determine whether this template argument has no value.
216  bool isNull() const { return getKind() == Null; }
217
218  /// \brief Whether this template argument is dependent on a template
219  /// parameter such that its result can change from one instantiation to
220  /// another.
221  bool isDependent() const;
222
223  /// \brief Whether this template argument is dependent on a template
224  /// parameter.
225  bool isInstantiationDependent() const;
226
227  /// \brief Whether this template argument contains an unexpanded
228  /// parameter pack.
229  bool containsUnexpandedParameterPack() const;
230
231  /// \brief Determine whether this template argument is a pack expansion.
232  bool isPackExpansion() const;
233
234  /// \brief Retrieve the type for a type template argument.
235  QualType getAsType() const {
236    assert(getKind() == Type && "Unexpected kind");
237    return QualType::getFromOpaquePtr(reinterpret_cast<void*>(TypeOrValue.V));
238  }
239
240  /// \brief Retrieve the declaration for a declaration non-type
241  /// template argument.
242  ValueDecl *getAsDecl() const {
243    assert(getKind() == Declaration && "Unexpected kind");
244    return DeclArg.D;
245  }
246
247  QualType getParamTypeForDecl() const {
248    assert(getKind() == Declaration && "Unexpected kind");
249    return QualType::getFromOpaquePtr(DeclArg.QT);
250  }
251
252  /// \brief Retrieve the type for null non-type template argument.
253  QualType getNullPtrType() const {
254    assert(getKind() == NullPtr && "Unexpected kind");
255    return QualType::getFromOpaquePtr(reinterpret_cast<void*>(TypeOrValue.V));
256  }
257
258  /// \brief Retrieve the template name for a template name argument.
259  TemplateName getAsTemplate() const {
260    assert(getKind() == Template && "Unexpected kind");
261    return TemplateName::getFromVoidPointer(TemplateArg.Name);
262  }
263
264  /// \brief Retrieve the template argument as a template name; if the argument
265  /// is a pack expansion, return the pattern as a template name.
266  TemplateName getAsTemplateOrTemplatePattern() const {
267    assert((getKind() == Template || getKind() == TemplateExpansion) &&
268           "Unexpected kind");
269
270    return TemplateName::getFromVoidPointer(TemplateArg.Name);
271  }
272
273  /// \brief Retrieve the number of expansions that a template template argument
274  /// expansion will produce, if known.
275  Optional<unsigned> getNumTemplateExpansions() const;
276
277  /// \brief Retrieve the template argument as an integral value.
278  // FIXME: Provide a way to read the integral data without copying the value.
279  llvm::APSInt getAsIntegral() const {
280    assert(getKind() == Integral && "Unexpected kind");
281    using namespace llvm;
282    if (Integer.BitWidth <= 64)
283      return APSInt(APInt(Integer.BitWidth, Integer.VAL), Integer.IsUnsigned);
284
285    unsigned NumWords = APInt::getNumWords(Integer.BitWidth);
286    return APSInt(APInt(Integer.BitWidth, makeArrayRef(Integer.pVal, NumWords)),
287                  Integer.IsUnsigned);
288  }
289
290  /// \brief Retrieve the type of the integral value.
291  QualType getIntegralType() const {
292    assert(getKind() == Integral && "Unexpected kind");
293    return QualType::getFromOpaquePtr(Integer.Type);
294  }
295
296  void setIntegralType(QualType T) {
297    assert(getKind() == Integral && "Unexpected kind");
298    Integer.Type = T.getAsOpaquePtr();
299  }
300
301  /// \brief If this is a non-type template argument, get its type. Otherwise,
302  /// returns a null QualType.
303  QualType getNonTypeTemplateArgumentType() const;
304
305  /// \brief Retrieve the template argument as an expression.
306  Expr *getAsExpr() const {
307    assert(getKind() == Expression && "Unexpected kind");
308    return reinterpret_cast<Expr *>(TypeOrValue.V);
309  }
310
311  /// \brief Iterator that traverses the elements of a template argument pack.
312  typedef const TemplateArgument * pack_iterator;
313
314  /// \brief Iterator referencing the first argument of a template argument
315  /// pack.
316  pack_iterator pack_begin() const {
317    assert(getKind() == Pack);
318    return Args.Args;
319  }
320
321  /// \brief Iterator referencing one past the last argument of a template
322  /// argument pack.
323  pack_iterator pack_end() const {
324    assert(getKind() == Pack);
325    return Args.Args + Args.NumArgs;
326  }
327
328  /// \brief Iterator range referencing all of the elements of a template
329  /// argument pack.
330  ArrayRef<TemplateArgument> pack_elements() const {
331    return llvm::makeArrayRef(pack_begin(), pack_end());
332  }
333
334  /// \brief The number of template arguments in the given template argument
335  /// pack.
336  unsigned pack_size() const {
337    assert(getKind() == Pack);
338    return Args.NumArgs;
339  }
340
341  /// \brief Return the array of arguments in this template argument pack.
342  ArrayRef<TemplateArgument> getPackAsArray() const {
343    assert(getKind() == Pack);
344    return llvm::makeArrayRef(Args.Args, Args.NumArgs);
345  }
346
347  /// \brief Determines whether two template arguments are superficially the
348  /// same.
349  bool structurallyEquals(const TemplateArgument &Other) const;
350
351  /// \brief When the template argument is a pack expansion, returns
352  /// the pattern of the pack expansion.
353  TemplateArgument getPackExpansionPattern() const;
354
355  /// \brief Print this template argument to the given output stream.
356  void print(const PrintingPolicy &Policy, raw_ostream &Out) const;
357
358  /// \brief Debugging aid that dumps the template argument.
359  void dump(raw_ostream &Out) const;
360
361  /// \brief Debugging aid that dumps the template argument to standard error.
362  void dump() const;
363
364  /// \brief Used to insert TemplateArguments into FoldingSets.
365  void Profile(llvm::FoldingSetNodeID &ID, const ASTContext &Context) const;
366};
367
368/// Location information for a TemplateArgument.
369struct TemplateArgumentLocInfo {
370private:
371
372  struct T {
373    // FIXME: We'd like to just use the qualifier in the TemplateName,
374    // but template arguments get canonicalized too quickly.
375    NestedNameSpecifier *Qualifier;
376    void *QualifierLocData;
377    unsigned TemplateNameLoc;
378    unsigned EllipsisLoc;
379  };
380
381  union {
382    struct T Template;
383    Expr *Expression;
384    TypeSourceInfo *Declarator;
385  };
386
387public:
388  constexpr TemplateArgumentLocInfo() : Template({nullptr, nullptr, 0, 0}) {}
389
390  TemplateArgumentLocInfo(TypeSourceInfo *TInfo) : Declarator(TInfo) {}
391
392  TemplateArgumentLocInfo(Expr *E) : Expression(E) {}
393
394  TemplateArgumentLocInfo(NestedNameSpecifierLoc QualifierLoc,
395                          SourceLocation TemplateNameLoc,
396                          SourceLocation EllipsisLoc)
397  {
398    Template.Qualifier = QualifierLoc.getNestedNameSpecifier();
399    Template.QualifierLocData = QualifierLoc.getOpaqueData();
400    Template.TemplateNameLoc = TemplateNameLoc.getRawEncoding();
401    Template.EllipsisLoc = EllipsisLoc.getRawEncoding();
402  }
403
404  TypeSourceInfo *getAsTypeSourceInfo() const {
405    return Declarator;
406  }
407
408  Expr *getAsExpr() const {
409    return Expression;
410  }
411
412  NestedNameSpecifierLoc getTemplateQualifierLoc() const {
413    return NestedNameSpecifierLoc(Template.Qualifier,
414                                  Template.QualifierLocData);
415  }
416
417  SourceLocation getTemplateNameLoc() const {
418    return SourceLocation::getFromRawEncoding(Template.TemplateNameLoc);
419  }
420
421  SourceLocation getTemplateEllipsisLoc() const {
422    return SourceLocation::getFromRawEncoding(Template.EllipsisLoc);
423  }
424};
425
426/// Location wrapper for a TemplateArgument.  TemplateArgument is to
427/// TemplateArgumentLoc as Type is to TypeLoc.
428class TemplateArgumentLoc {
429  TemplateArgument Argument;
430  TemplateArgumentLocInfo LocInfo;
431
432public:
433  constexpr TemplateArgumentLoc() {}
434
435  TemplateArgumentLoc(const TemplateArgument &Argument,
436                      TemplateArgumentLocInfo Opaque)
437    : Argument(Argument), LocInfo(Opaque) {
438  }
439
440  TemplateArgumentLoc(const TemplateArgument &Argument, TypeSourceInfo *TInfo)
441    : Argument(Argument), LocInfo(TInfo) {
442    assert(Argument.getKind() == TemplateArgument::Type);
443  }
444
445  TemplateArgumentLoc(const TemplateArgument &Argument, Expr *E)
446    : Argument(Argument), LocInfo(E) {
447    assert(Argument.getKind() == TemplateArgument::Expression);
448  }
449
450  TemplateArgumentLoc(const TemplateArgument &Argument,
451                      NestedNameSpecifierLoc QualifierLoc,
452                      SourceLocation TemplateNameLoc,
453                      SourceLocation EllipsisLoc = SourceLocation())
454    : Argument(Argument), LocInfo(QualifierLoc, TemplateNameLoc, EllipsisLoc) {
455    assert(Argument.getKind() == TemplateArgument::Template ||
456           Argument.getKind() == TemplateArgument::TemplateExpansion);
457  }
458
459  /// \brief - Fetches the primary location of the argument.
460  SourceLocation getLocation() const {
461    if (Argument.getKind() == TemplateArgument::Template ||
462        Argument.getKind() == TemplateArgument::TemplateExpansion)
463      return getTemplateNameLoc();
464
465    return getSourceRange().getBegin();
466  }
467
468  /// \brief - Fetches the full source range of the argument.
469  SourceRange getSourceRange() const LLVM_READONLY;
470
471  const TemplateArgument &getArgument() const {
472    return Argument;
473  }
474
475  TemplateArgumentLocInfo getLocInfo() const {
476    return LocInfo;
477  }
478
479  TypeSourceInfo *getTypeSourceInfo() const {
480    assert(Argument.getKind() == TemplateArgument::Type);
481    return LocInfo.getAsTypeSourceInfo();
482  }
483
484  Expr *getSourceExpression() const {
485    assert(Argument.getKind() == TemplateArgument::Expression);
486    return LocInfo.getAsExpr();
487  }
488
489  Expr *getSourceDeclExpression() const {
490    assert(Argument.getKind() == TemplateArgument::Declaration);
491    return LocInfo.getAsExpr();
492  }
493
494  Expr *getSourceNullPtrExpression() const {
495    assert(Argument.getKind() == TemplateArgument::NullPtr);
496    return LocInfo.getAsExpr();
497  }
498
499  Expr *getSourceIntegralExpression() const {
500    assert(Argument.getKind() == TemplateArgument::Integral);
501    return LocInfo.getAsExpr();
502  }
503
504  NestedNameSpecifierLoc getTemplateQualifierLoc() const {
505    assert(Argument.getKind() == TemplateArgument::Template ||
506           Argument.getKind() == TemplateArgument::TemplateExpansion);
507    return LocInfo.getTemplateQualifierLoc();
508  }
509
510  SourceLocation getTemplateNameLoc() const {
511    assert(Argument.getKind() == TemplateArgument::Template ||
512           Argument.getKind() == TemplateArgument::TemplateExpansion);
513    return LocInfo.getTemplateNameLoc();
514  }
515
516  SourceLocation getTemplateEllipsisLoc() const {
517    assert(Argument.getKind() == TemplateArgument::TemplateExpansion);
518    return LocInfo.getTemplateEllipsisLoc();
519  }
520};
521
522/// A convenient class for passing around template argument
523/// information.  Designed to be passed by reference.
524class TemplateArgumentListInfo {
525  SmallVector<TemplateArgumentLoc, 8> Arguments;
526  SourceLocation LAngleLoc;
527  SourceLocation RAngleLoc;
528
529  // This can leak if used in an AST node, use ASTTemplateArgumentListInfo
530  // instead.
531  void *operator new(size_t bytes, ASTContext &C) = delete;
532
533public:
534  TemplateArgumentListInfo() {}
535
536  TemplateArgumentListInfo(SourceLocation LAngleLoc,
537                           SourceLocation RAngleLoc)
538    : LAngleLoc(LAngleLoc), RAngleLoc(RAngleLoc) {}
539
540  SourceLocation getLAngleLoc() const { return LAngleLoc; }
541  SourceLocation getRAngleLoc() const { return RAngleLoc; }
542
543  void setLAngleLoc(SourceLocation Loc) { LAngleLoc = Loc; }
544  void setRAngleLoc(SourceLocation Loc) { RAngleLoc = Loc; }
545
546  unsigned size() const { return Arguments.size(); }
547
548  const TemplateArgumentLoc *getArgumentArray() const {
549    return Arguments.data();
550  }
551
552  llvm::ArrayRef<TemplateArgumentLoc> arguments() const {
553    return Arguments;
554  }
555
556  const TemplateArgumentLoc &operator[](unsigned I) const {
557    return Arguments[I];
558  }
559
560  TemplateArgumentLoc &operator[](unsigned I) {
561    return Arguments[I];
562  }
563
564  void addArgument(const TemplateArgumentLoc &Loc) {
565    Arguments.push_back(Loc);
566  }
567};
568
569/// \brief Represents an explicit template argument list in C++, e.g.,
570/// the "<int>" in "sort<int>".
571/// This is safe to be used inside an AST node, in contrast with
572/// TemplateArgumentListInfo.
573struct ASTTemplateArgumentListInfo final
574    : private llvm::TrailingObjects<ASTTemplateArgumentListInfo,
575                                    TemplateArgumentLoc> {
576private:
577  friend TrailingObjects;
578  friend class ASTNodeImporter;
579
580  ASTTemplateArgumentListInfo(const TemplateArgumentListInfo &List);
581
582public:
583  /// \brief The source location of the left angle bracket ('<').
584  SourceLocation LAngleLoc;
585
586  /// \brief The source location of the right angle bracket ('>').
587  SourceLocation RAngleLoc;
588
589  /// \brief The number of template arguments in TemplateArgs.
590  unsigned NumTemplateArgs;
591
592  /// \brief Retrieve the template arguments
593  const TemplateArgumentLoc *getTemplateArgs() const {
594    return getTrailingObjects<TemplateArgumentLoc>();
595  }
596
597  llvm::ArrayRef<TemplateArgumentLoc> arguments() const {
598    return llvm::makeArrayRef(getTemplateArgs(), NumTemplateArgs);
599  }
600
601  const TemplateArgumentLoc &operator[](unsigned I) const {
602    return getTemplateArgs()[I];
603  }
604
605  static const ASTTemplateArgumentListInfo *
606  Create(ASTContext &C, const TemplateArgumentListInfo &List);
607};
608
609/// \brief Represents an explicit template argument list in C++, e.g.,
610/// the "<int>" in "sort<int>".
611///
612/// It is intended to be used as a trailing object on AST nodes, and
613/// as such, doesn't contain the array of TemplateArgumentLoc itself,
614/// but expects the containing object to also provide storage for
615/// that.
616struct alignas(void *) ASTTemplateKWAndArgsInfo {
617  /// \brief The source location of the left angle bracket ('<').
618  SourceLocation LAngleLoc;
619
620  /// \brief The source location of the right angle bracket ('>').
621  SourceLocation RAngleLoc;
622
623  /// \brief The source location of the template keyword; this is used
624  /// as part of the representation of qualified identifiers, such as
625  /// S<T>::template apply<T>.  Will be empty if this expression does
626  /// not have a template keyword.
627  SourceLocation TemplateKWLoc;
628
629  /// \brief The number of template arguments in TemplateArgs.
630  unsigned NumTemplateArgs;
631
632  void initializeFrom(SourceLocation TemplateKWLoc,
633                      const TemplateArgumentListInfo &List,
634                      TemplateArgumentLoc *OutArgArray);
635  void initializeFrom(SourceLocation TemplateKWLoc,
636                      const TemplateArgumentListInfo &List,
637                      TemplateArgumentLoc *OutArgArray, bool &Dependent,
638                      bool &InstantiationDependent,
639                      bool &ContainsUnexpandedParameterPack);
640  void initializeFrom(SourceLocation TemplateKWLoc);
641
642  void copyInto(const TemplateArgumentLoc *ArgArray,
643                TemplateArgumentListInfo &List) const;
644};
645
646const DiagnosticBuilder &operator<<(const DiagnosticBuilder &DB,
647                                    const TemplateArgument &Arg);
648
649inline TemplateSpecializationType::iterator
650    TemplateSpecializationType::end() const {
651  return getArgs() + getNumArgs();
652}
653
654inline DependentTemplateSpecializationType::iterator
655    DependentTemplateSpecializationType::end() const {
656  return getArgs() + getNumArgs();
657}
658
659inline const TemplateArgument &
660    TemplateSpecializationType::getArg(unsigned Idx) const {
661  assert(Idx < getNumArgs() && "Template argument out of range");
662  return getArgs()[Idx];
663}
664
665inline const TemplateArgument &
666    DependentTemplateSpecializationType::getArg(unsigned Idx) const {
667  assert(Idx < getNumArgs() && "Template argument out of range");
668  return getArgs()[Idx];
669}
670
671} // end namespace clang
672
673#endif
674