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