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