contrib/llvm/tools/clang/include/clang/Sema/Template.h

   1 //===------- SemaTemplate.h - 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 //  This file provides types used in the semantic analysis of C++ templates.
  10 //
  11 //===----------------------------------------------------------------------===/
  12 #ifndef LLVM_CLANG_SEMA_TEMPLATE_H
  13 #define LLVM_CLANG_SEMA_TEMPLATE_H
  14
  15 #include "clang/AST/DeclTemplate.h"
  16 #include "clang/AST/DeclVisitor.h"
  17 #include "clang/Sema/Sema.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include <cassert>
  20 #include <utility>
  21
  22 namespace clang {
  23   /// \brief Data structure that captures multiple levels of template argument
  24   /// lists for use in template instantiation.
  25   ///
  26   /// Multiple levels of template arguments occur when instantiating the
  27   /// definitions of member templates. For example:
  28   ///
  29   /// \code
  30   /// template<typename T>
  31   /// struct X {
  32   ///   template<T Value>
  33   ///   struct Y {
  34   ///     void f();
  35   ///   };
  36   /// };
  37   /// \endcode
  38   ///
  39   /// When instantiating X<int>::Y<17>::f, the multi-level template argument
  40   /// list will contain a template argument list (int) at depth 0 and a
  41   /// template argument list (17) at depth 1.
  42   class MultiLevelTemplateArgumentList {
  43     /// \brief The template argument list at a certain template depth
  44     typedef ArrayRef<TemplateArgument> ArgList;
  45
  46     /// \brief The template argument lists, stored from the innermost template
  47     /// argument list (first) to the outermost template argument list (last).
  48     SmallVector<ArgList, 4> TemplateArgumentLists;
  49
  50     /// \brief The number of outer levels of template arguments that are not
  51     /// being substituted.
  52     unsigned NumRetainedOuterLevels = 0;
  53
  54   public:
  55     /// \brief Construct an empty set of template argument lists.
  56     MultiLevelTemplateArgumentList() { }
  57
  58     /// \brief Construct a single-level template argument list.
  59     explicit
  60     MultiLevelTemplateArgumentList(const TemplateArgumentList &TemplateArgs) {
  61       addOuterTemplateArguments(&TemplateArgs);
  62     }
  63
  64     /// \brief Determine the number of levels in this template argument
  65     /// list.
  66     unsigned getNumLevels() const {
  67       return TemplateArgumentLists.size() + NumRetainedOuterLevels;
  68     }
  69
  70     /// \brief Determine the number of substituted levels in this template
  71     /// argument list.
  72     unsigned getNumSubstitutedLevels() const {
  73       return TemplateArgumentLists.size();
  74     }
  75
  76     /// \brief Retrieve the template argument at a given depth and index.
  77     const TemplateArgument &operator()(unsigned Depth, unsigned Index) const {
  78       assert(NumRetainedOuterLevels <= Depth && Depth < getNumLevels());
  79       assert(Index < TemplateArgumentLists[getNumLevels() - Depth - 1].size());
  80       return TemplateArgumentLists[getNumLevels() - Depth - 1][Index];
  81     }
  82
  83     /// \brief Determine whether there is a non-NULL template argument at the
  84     /// given depth and index.
  85     ///
  86     /// There must exist a template argument list at the given depth.
  87     bool hasTemplateArgument(unsigned Depth, unsigned Index) const {
  88       assert(Depth < getNumLevels());
  89
  90       if (Depth < NumRetainedOuterLevels)
  91         return false;
  92
  93       if (Index >= TemplateArgumentLists[getNumLevels() - Depth - 1].size())
  94         return false;
  95
  96       return !(*this)(Depth, Index).isNull();
  97     }
  98
  99     /// \brief Clear out a specific template argument.
 100     void setArgument(unsigned Depth, unsigned Index,
 101                      TemplateArgument Arg) {
 102       assert(NumRetainedOuterLevels <= Depth && Depth < getNumLevels());
 103       assert(Index < TemplateArgumentLists[getNumLevels() - Depth - 1].size());
 104       const_cast<TemplateArgument&>(
 105                 TemplateArgumentLists[getNumLevels() - Depth - 1][Index])
 106         = Arg;
 107     }
 108
 109     /// \brief Add a new outermost level to the multi-level template argument
 110     /// list.
 111     void addOuterTemplateArguments(const TemplateArgumentList *TemplateArgs) {
 112       addOuterTemplateArguments(ArgList(TemplateArgs->data(),
 113                                         TemplateArgs->size()));
 114     }
 115
 116     /// \brief Add a new outmost level to the multi-level template argument
 117     /// list.
 118     void addOuterTemplateArguments(ArgList Args) {
 119       assert(!NumRetainedOuterLevels &&
 120              "substituted args outside retained args?");
 121       TemplateArgumentLists.push_back(Args);
 122     }
 123
 124     /// \brief Add an outermost level that we are not substituting. We have no
 125     /// arguments at this level, and do not remove it from the depth of inner
 126     /// template parameters that we instantiate.
 127     void addOuterRetainedLevel() {
 128       ++NumRetainedOuterLevels;
 129     }
 130
 131     /// \brief Retrieve the innermost template argument list.
 132     const ArgList &getInnermost() const {
 133       return TemplateArgumentLists.front();
 134     }
 135   };
 136
 137   /// \brief The context in which partial ordering of function templates occurs.
 138   enum TPOC {
 139     /// \brief Partial ordering of function templates for a function call.
 140     TPOC_Call,
 141     /// \brief Partial ordering of function templates for a call to a
 142     /// conversion function.
 143     TPOC_Conversion,
 144     /// \brief Partial ordering of function templates in other contexts, e.g.,
 145     /// taking the address of a function template or matching a function
 146     /// template specialization to a function template.
 147     TPOC_Other
 148   };
 149
 150   // This is lame but unavoidable in a world without forward
 151   // declarations of enums.  The alternatives are to either pollute
 152   // Sema.h (by including this file) or sacrifice type safety (by
 153   // making Sema.h declare things as enums).
 154   class TemplatePartialOrderingContext {
 155     TPOC Value;
 156   public:
 157     TemplatePartialOrderingContext(TPOC Value) : Value(Value) {}
 158     operator TPOC() const { return Value; }
 159   };
 160
 161   /// \brief Captures a template argument whose value has been deduced
 162   /// via c++ template argument deduction.
 163   class DeducedTemplateArgument : public TemplateArgument {
 164     /// \brief For a non-type template argument, whether the value was
 165     /// deduced from an array bound.
 166     bool DeducedFromArrayBound;
 167
 168   public:
 169     DeducedTemplateArgument()
 170       : TemplateArgument(), DeducedFromArrayBound(false) { }
 171
 172     DeducedTemplateArgument(const TemplateArgument &Arg,
 173                             bool DeducedFromArrayBound = false)
 174       : TemplateArgument(Arg), DeducedFromArrayBound(DeducedFromArrayBound) { }
 175
 176     /// \brief Construct an integral non-type template argument that
 177     /// has been deduced, possibly from an array bound.
 178     DeducedTemplateArgument(ASTContext &Ctx,
 179                             const llvm::APSInt &Value,
 180                             QualType ValueType,
 181                             bool DeducedFromArrayBound)
 182       : TemplateArgument(Ctx, Value, ValueType),
 183         DeducedFromArrayBound(DeducedFromArrayBound) { }
 184
 185     /// \brief For a non-type template argument, determine whether the
 186     /// template argument was deduced from an array bound.
 187     bool wasDeducedFromArrayBound() const { return DeducedFromArrayBound; }
 188
 189     /// \brief Specify whether the given non-type template argument
 190     /// was deduced from an array bound.
 191     void setDeducedFromArrayBound(bool Deduced) {
 192       DeducedFromArrayBound = Deduced;
 193     }
 194   };
 195
 196   /// \brief A stack-allocated class that identifies which local
 197   /// variable declaration instantiations are present in this scope.
 198   ///
 199   /// A new instance of this class type will be created whenever we
 200   /// instantiate a new function declaration, which will have its own
 201   /// set of parameter declarations.
 202   class LocalInstantiationScope {
 203   public:
 204     /// \brief A set of declarations.
 205     typedef SmallVector<ParmVarDecl *, 4> DeclArgumentPack;
 206
 207   private:
 208     /// \brief Reference to the semantic analysis that is performing
 209     /// this template instantiation.
 210     Sema &SemaRef;
 211
 212     typedef llvm::SmallDenseMap<
 213         const Decl *, llvm::PointerUnion<Decl *, DeclArgumentPack *>, 4>
 214     LocalDeclsMap;
 215
 216     /// \brief A mapping from local declarations that occur
 217     /// within a template to their instantiations.
 218     ///
 219     /// This mapping is used during instantiation to keep track of,
 220     /// e.g., function parameter and variable declarations. For example,
 221     /// given:
 222     ///
 223     /// \code
 224     ///   template<typename T> T add(T x, T y) { return x + y; }
 225     /// \endcode
 226     ///
 227     /// when we instantiate add<int>, we will introduce a mapping from
 228     /// the ParmVarDecl for 'x' that occurs in the template to the
 229     /// instantiated ParmVarDecl for 'x'.
 230     ///
 231     /// For a parameter pack, the local instantiation scope may contain a
 232     /// set of instantiated parameters. This is stored as a DeclArgumentPack
 233     /// pointer.
 234     LocalDeclsMap LocalDecls;
 235
 236     /// \brief The set of argument packs we've allocated.
 237     SmallVector<DeclArgumentPack *, 1> ArgumentPacks;
 238
 239     /// \brief The outer scope, which contains local variable
 240     /// definitions from some other instantiation (that may not be
 241     /// relevant to this particular scope).
 242     LocalInstantiationScope *Outer;
 243
 244     /// \brief Whether we have already exited this scope.
 245     bool Exited;
 246
 247     /// \brief Whether to combine this scope with the outer scope, such that
 248     /// lookup will search our outer scope.
 249     bool CombineWithOuterScope;
 250
 251     /// \brief If non-NULL, the template parameter pack that has been
 252     /// partially substituted per C++0x [temp.arg.explicit]p9.
 253     NamedDecl *PartiallySubstitutedPack;
 254
 255     /// \brief If \c PartiallySubstitutedPack is non-null, the set of
 256     /// explicitly-specified template arguments in that pack.
 257     const TemplateArgument *ArgsInPartiallySubstitutedPack;
 258
 259     /// \brief If \c PartiallySubstitutedPack, the number of
 260     /// explicitly-specified template arguments in
 261     /// ArgsInPartiallySubstitutedPack.
 262     unsigned NumArgsInPartiallySubstitutedPack;
 263
 264     // This class is non-copyable
 265     LocalInstantiationScope(
 266       const LocalInstantiationScope &) = delete;
 267     void operator=(const LocalInstantiationScope &) = delete;
 268
 269   public:
 270     LocalInstantiationScope(Sema &SemaRef, bool CombineWithOuterScope = false)
 271       : SemaRef(SemaRef), Outer(SemaRef.CurrentInstantiationScope),
 272         Exited(false), CombineWithOuterScope(CombineWithOuterScope),
 273         PartiallySubstitutedPack(nullptr)
 274     {
 275       SemaRef.CurrentInstantiationScope = this;
 276     }
 277
 278     ~LocalInstantiationScope() {
 279       Exit();
 280     }
 281
 282     const Sema &getSema() const { return SemaRef; }
 283
 284     /// \brief Exit this local instantiation scope early.
 285     void Exit() {
 286       if (Exited)
 287         return;
 288
 289       for (unsigned I = 0, N = ArgumentPacks.size(); I != N; ++I)
 290         delete ArgumentPacks[I];
 291
 292       SemaRef.CurrentInstantiationScope = Outer;
 293       Exited = true;
 294     }
 295
 296     /// \brief Clone this scope, and all outer scopes, down to the given
 297     /// outermost scope.
 298     LocalInstantiationScope *cloneScopes(LocalInstantiationScope *Outermost) {
 299       if (this == Outermost) return this;
 300
 301       // Save the current scope from SemaRef since the LocalInstantiationScope
 302       // will overwrite it on construction
 303       LocalInstantiationScope *oldScope = SemaRef.CurrentInstantiationScope;
 304
 305       LocalInstantiationScope *newScope =
 306         new LocalInstantiationScope(SemaRef, CombineWithOuterScope);
 307
 308       newScope->Outer = nullptr;
 309       if (Outer)
 310         newScope->Outer = Outer->cloneScopes(Outermost);
 311
 312       newScope->PartiallySubstitutedPack = PartiallySubstitutedPack;
 313       newScope->ArgsInPartiallySubstitutedPack = ArgsInPartiallySubstitutedPack;
 314       newScope->NumArgsInPartiallySubstitutedPack =
 315         NumArgsInPartiallySubstitutedPack;
 316
 317       for (LocalDeclsMap::iterator I = LocalDecls.begin(), E = LocalDecls.end();
 318            I != E; ++I) {
 319         const Decl *D = I->first;
 320         llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored =
 321           newScope->LocalDecls[D];
 322         if (I->second.is<Decl *>()) {
 323           Stored = I->second.get<Decl *>();
 324         } else {
 325           DeclArgumentPack *OldPack = I->second.get<DeclArgumentPack *>();
 326           DeclArgumentPack *NewPack = new DeclArgumentPack(*OldPack);
 327           Stored = NewPack;
 328           newScope->ArgumentPacks.push_back(NewPack);
 329         }
 330       }
 331       // Restore the saved scope to SemaRef
 332       SemaRef.CurrentInstantiationScope = oldScope;
 333       return newScope;
 334     }
 335
 336     /// \brief deletes the given scope, and all otuer scopes, down to the
 337     /// given outermost scope.
 338     static void deleteScopes(LocalInstantiationScope *Scope,
 339                              LocalInstantiationScope *Outermost) {
 340       while (Scope && Scope != Outermost) {
 341         LocalInstantiationScope *Out = Scope->Outer;
 342         delete Scope;
 343         Scope = Out;
 344       }
 345     }
 346
 347     /// \brief Find the instantiation of the declaration D within the current
 348     /// instantiation scope.
 349     ///
 350     /// \param D The declaration whose instantiation we are searching for.
 351     ///
 352     /// \returns A pointer to the declaration or argument pack of declarations
 353     /// to which the declaration \c D is instantiated, if found. Otherwise,
 354     /// returns NULL.
 355     llvm::PointerUnion<Decl *, DeclArgumentPack *> *
 356     findInstantiationOf(const Decl *D);
 357
 358     void InstantiatedLocal(const Decl *D, Decl *Inst);
 359     void InstantiatedLocalPackArg(const Decl *D, ParmVarDecl *Inst);
 360     void MakeInstantiatedLocalArgPack(const Decl *D);
 361
 362     /// \brief Note that the given parameter pack has been partially substituted
 363     /// via explicit specification of template arguments
 364     /// (C++0x [temp.arg.explicit]p9).
 365     ///
 366     /// \param Pack The parameter pack, which will always be a template
 367     /// parameter pack.
 368     ///
 369     /// \param ExplicitArgs The explicitly-specified template arguments provided
 370     /// for this parameter pack.
 371     ///
 372     /// \param NumExplicitArgs The number of explicitly-specified template
 373     /// arguments provided for this parameter pack.
 374     void SetPartiallySubstitutedPack(NamedDecl *Pack,
 375                                      const TemplateArgument *ExplicitArgs,
 376                                      unsigned NumExplicitArgs);
 377
 378     /// \brief Reset the partially-substituted pack when it is no longer of
 379     /// interest.
 380     void ResetPartiallySubstitutedPack() {
 381       assert(PartiallySubstitutedPack && "No partially-substituted pack");
 382       PartiallySubstitutedPack = nullptr;
 383       ArgsInPartiallySubstitutedPack = nullptr;
 384       NumArgsInPartiallySubstitutedPack = 0;
 385     }
 386
 387     /// \brief Retrieve the partially-substitued template parameter pack.
 388     ///
 389     /// If there is no partially-substituted parameter pack, returns NULL.
 390     NamedDecl *
 391     getPartiallySubstitutedPack(const TemplateArgument **ExplicitArgs = nullptr,
 392                                 unsigned *NumExplicitArgs = nullptr) const;
 393   };
 394
 395   class TemplateDeclInstantiator
 396     : public DeclVisitor<TemplateDeclInstantiator, Decl *>
 397   {
 398     Sema &SemaRef;
 399     Sema::ArgumentPackSubstitutionIndexRAII SubstIndex;
 400     DeclContext *Owner;
 401     const MultiLevelTemplateArgumentList &TemplateArgs;
 402     Sema::LateInstantiatedAttrVec* LateAttrs;
 403     LocalInstantiationScope *StartingScope;
 404
 405     /// \brief A list of out-of-line class template partial
 406     /// specializations that will need to be instantiated after the
 407     /// enclosing class's instantiation is complete.
 408     SmallVector<std::pair<ClassTemplateDecl *,
 409                                 ClassTemplatePartialSpecializationDecl *>, 4>
 410       OutOfLinePartialSpecs;
 411
 412     /// \brief A list of out-of-line variable template partial
 413     /// specializations that will need to be instantiated after the
 414     /// enclosing variable's instantiation is complete.
 415     /// FIXME: Verify that this is needed.
 416     SmallVector<
 417         std::pair<VarTemplateDecl *, VarTemplatePartialSpecializationDecl *>, 4>
 418     OutOfLineVarPartialSpecs;
 419
 420   public:
 421     TemplateDeclInstantiator(Sema &SemaRef, DeclContext *Owner,
 422                              const MultiLevelTemplateArgumentList &TemplateArgs)
 423       : SemaRef(SemaRef),
 424         SubstIndex(SemaRef, SemaRef.ArgumentPackSubstitutionIndex),
 425         Owner(Owner), TemplateArgs(TemplateArgs), LateAttrs(nullptr),
 426         StartingScope(nullptr) {}
 427
 428 // Define all the decl visitors using DeclNodes.inc
 429 #define DECL(DERIVED, BASE) \
 430     Decl *Visit ## DERIVED ## Decl(DERIVED ## Decl *D);
 431 #define ABSTRACT_DECL(DECL)
 432
 433 // Decls which never appear inside a class or function.
 434 #define OBJCCONTAINER(DERIVED, BASE)
 435 #define FILESCOPEASM(DERIVED, BASE)
 436 #define IMPORT(DERIVED, BASE)
 437 #define EXPORT(DERIVED, BASE)
 438 #define LINKAGESPEC(DERIVED, BASE)
 439 #define OBJCCOMPATIBLEALIAS(DERIVED, BASE)
 440 #define OBJCMETHOD(DERIVED, BASE)
 441 #define OBJCTYPEPARAM(DERIVED, BASE)
 442 #define OBJCIVAR(DERIVED, BASE)
 443 #define OBJCPROPERTY(DERIVED, BASE)
 444 #define OBJCPROPERTYIMPL(DERIVED, BASE)
 445 #define EMPTY(DERIVED, BASE)
 446
 447 // Decls which use special-case instantiation code.
 448 #define BLOCK(DERIVED, BASE)
 449 #define CAPTURED(DERIVED, BASE)
 450 #define IMPLICITPARAM(DERIVED, BASE)
 451
 452 #include "clang/AST/DeclNodes.inc"
 453
 454     // A few supplemental visitor functions.
 455     Decl *VisitCXXMethodDecl(CXXMethodDecl *D,
 456                              TemplateParameterList *TemplateParams,
 457                              bool IsClassScopeSpecialization = false);
 458     Decl *VisitFunctionDecl(FunctionDecl *D,
 459                             TemplateParameterList *TemplateParams);
 460     Decl *VisitDecl(Decl *D);
 461     Decl *VisitVarDecl(VarDecl *D, bool InstantiatingVarTemplate,
 462                        ArrayRef<BindingDecl *> *Bindings = nullptr);
 463
 464     // Enable late instantiation of attributes.  Late instantiated attributes
 465     // will be stored in LA.
 466     void enableLateAttributeInstantiation(Sema::LateInstantiatedAttrVec *LA) {
 467       LateAttrs = LA;
 468       StartingScope = SemaRef.CurrentInstantiationScope;
 469     }
 470
 471     // Disable late instantiation of attributes.
 472     void disableLateAttributeInstantiation() {
 473       LateAttrs = nullptr;
 474       StartingScope = nullptr;
 475     }
 476
 477     LocalInstantiationScope *getStartingScope() const { return StartingScope; }
 478
 479     typedef
 480       SmallVectorImpl<std::pair<ClassTemplateDecl *,
 481                                      ClassTemplatePartialSpecializationDecl *> >
 482         ::iterator
 483       delayed_partial_spec_iterator;
 484
 485     typedef SmallVectorImpl<std::pair<
 486         VarTemplateDecl *, VarTemplatePartialSpecializationDecl *> >::iterator
 487     delayed_var_partial_spec_iterator;
 488
 489     /// \brief Return an iterator to the beginning of the set of
 490     /// "delayed" partial specializations, which must be passed to
 491     /// InstantiateClassTemplatePartialSpecialization once the class
 492     /// definition has been completed.
 493     delayed_partial_spec_iterator delayed_partial_spec_begin() {
 494       return OutOfLinePartialSpecs.begin();
 495     }
 496
 497     delayed_var_partial_spec_iterator delayed_var_partial_spec_begin() {
 498       return OutOfLineVarPartialSpecs.begin();
 499     }
 500
 501     /// \brief Return an iterator to the end of the set of
 502     /// "delayed" partial specializations, which must be passed to
 503     /// InstantiateClassTemplatePartialSpecialization once the class
 504     /// definition has been completed.
 505     delayed_partial_spec_iterator delayed_partial_spec_end() {
 506       return OutOfLinePartialSpecs.end();
 507     }
 508
 509     delayed_var_partial_spec_iterator delayed_var_partial_spec_end() {
 510       return OutOfLineVarPartialSpecs.end();
 511     }
 512
 513     // Helper functions for instantiating methods.
 514     TypeSourceInfo *SubstFunctionType(FunctionDecl *D,
 515                              SmallVectorImpl<ParmVarDecl *> &Params);
 516     bool InitFunctionInstantiation(FunctionDecl *New, FunctionDecl *Tmpl);
 517     bool InitMethodInstantiation(CXXMethodDecl *New, CXXMethodDecl *Tmpl);
 518
 519     TemplateParameterList *
 520       SubstTemplateParams(TemplateParameterList *List);
 521
 522     bool SubstQualifier(const DeclaratorDecl *OldDecl,
 523                         DeclaratorDecl *NewDecl);
 524     bool SubstQualifier(const TagDecl *OldDecl,
 525                         TagDecl *NewDecl);
 526
 527     Decl *VisitVarTemplateSpecializationDecl(
 528         VarTemplateDecl *VarTemplate, VarDecl *FromVar, void *InsertPos,
 529         const TemplateArgumentListInfo &TemplateArgsInfo,
 530         ArrayRef<TemplateArgument> Converted);
 531
 532     Decl *InstantiateTypedefNameDecl(TypedefNameDecl *D, bool IsTypeAlias);
 533     ClassTemplatePartialSpecializationDecl *
 534     InstantiateClassTemplatePartialSpecialization(
 535                                               ClassTemplateDecl *ClassTemplate,
 536                            ClassTemplatePartialSpecializationDecl *PartialSpec);
 537     VarTemplatePartialSpecializationDecl *
 538     InstantiateVarTemplatePartialSpecialization(
 539         VarTemplateDecl *VarTemplate,
 540         VarTemplatePartialSpecializationDecl *PartialSpec);
 541     void InstantiateEnumDefinition(EnumDecl *Enum, EnumDecl *Pattern);
 542
 543   private:
 544     template<typename T>
 545     Decl *instantiateUnresolvedUsingDecl(T *D,
 546                                          bool InstantiatingPackElement = false);
 547   };
 548 }
 549
 550 #endif // LLVM_CLANG_SEMA_TEMPLATE_H