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