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