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(const TemplateArgument *Args,
 104                                    unsigned NumArgs) {
 105       addOuterTemplateArguments(ArgList(Args, NumArgs));
 106     }
 107
 108     /// \brief Add a new outmost level to the multi-level template argument
 109     /// list.
 110     void addOuterTemplateArguments(ArgList Args) {
 111       TemplateArgumentLists.push_back(Args);
 112     }
 113
 114     /// \brief Retrieve the innermost template argument list.
 115     const ArgList &getInnermost() const {
 116       return TemplateArgumentLists.front();
 117     }
 118   };
 119
 120   /// \brief The context in which partial ordering of function templates occurs.
 121   enum TPOC {
 122     /// \brief Partial ordering of function templates for a function call.
 123     TPOC_Call,
 124     /// \brief Partial ordering of function templates for a call to a
 125     /// conversion function.
 126     TPOC_Conversion,
 127     /// \brief Partial ordering of function templates in other contexts, e.g.,
 128     /// taking the address of a function template or matching a function
 129     /// template specialization to a function template.
 130     TPOC_Other
 131   };
 132
 133   // This is lame but unavoidable in a world without forward
 134   // declarations of enums.  The alternatives are to either pollute
 135   // Sema.h (by including this file) or sacrifice type safety (by
 136   // making Sema.h declare things as enums).
 137   class TemplatePartialOrderingContext {
 138     TPOC Value;
 139   public:
 140     TemplatePartialOrderingContext(TPOC Value) : Value(Value) {}
 141     operator TPOC() const { return Value; }
 142   };
 143
 144   /// \brief Captures a template argument whose value has been deduced
 145   /// via c++ template argument deduction.
 146   class DeducedTemplateArgument : public TemplateArgument {
 147     /// \brief For a non-type template argument, whether the value was
 148     /// deduced from an array bound.
 149     bool DeducedFromArrayBound;
 150
 151   public:
 152     DeducedTemplateArgument()
 153       : TemplateArgument(), DeducedFromArrayBound(false) { }
 154
 155     DeducedTemplateArgument(const TemplateArgument &Arg,
 156                             bool DeducedFromArrayBound = false)
 157       : TemplateArgument(Arg), DeducedFromArrayBound(DeducedFromArrayBound) { }
 158
 159     /// \brief Construct an integral non-type template argument that
 160     /// has been deduced, possibly from an array bound.
 161     DeducedTemplateArgument(ASTContext &Ctx,
 162                             const llvm::APSInt &Value,
 163                             QualType ValueType,
 164                             bool DeducedFromArrayBound)
 165       : TemplateArgument(Ctx, Value, ValueType),
 166         DeducedFromArrayBound(DeducedFromArrayBound) { }
 167
 168     /// \brief For a non-type template argument, determine whether the
 169     /// template argument was deduced from an array bound.
 170     bool wasDeducedFromArrayBound() const { return DeducedFromArrayBound; }
 171
 172     /// \brief Specify whether the given non-type template argument
 173     /// was deduced from an array bound.
 174     void setDeducedFromArrayBound(bool Deduced) {
 175       DeducedFromArrayBound = Deduced;
 176     }
 177   };
 178
 179   /// \brief A stack-allocated class that identifies which local
 180   /// variable declaration instantiations are present in this scope.
 181   ///
 182   /// A new instance of this class type will be created whenever we
 183   /// instantiate a new function declaration, which will have its own
 184   /// set of parameter declarations.
 185   class LocalInstantiationScope {
 186   public:
 187     /// \brief A set of declarations.
 188     typedef SmallVector<Decl *, 4> DeclArgumentPack;
 189
 190   private:
 191     /// \brief Reference to the semantic analysis that is performing
 192     /// this template instantiation.
 193     Sema &SemaRef;
 194
 195     typedef llvm::SmallDenseMap<
 196         const Decl *, llvm::PointerUnion<Decl *, DeclArgumentPack *>, 4>
 197     LocalDeclsMap;
 198
 199     /// \brief A mapping from local declarations that occur
 200     /// within a template to their instantiations.
 201     ///
 202     /// This mapping is used during instantiation to keep track of,
 203     /// e.g., function parameter and variable declarations. For example,
 204     /// given:
 205     ///
 206     /// \code
 207     ///   template<typename T> T add(T x, T y) { return x + y; }
 208     /// \endcode
 209     ///
 210     /// when we instantiate add<int>, we will introduce a mapping from
 211     /// the ParmVarDecl for 'x' that occurs in the template to the
 212     /// instantiated ParmVarDecl for 'x'.
 213     ///
 214     /// For a parameter pack, the local instantiation scope may contain a
 215     /// set of instantiated parameters. This is stored as a DeclArgumentPack
 216     /// pointer.
 217     LocalDeclsMap LocalDecls;
 218
 219     /// \brief The set of argument packs we've allocated.
 220     SmallVector<DeclArgumentPack *, 1> ArgumentPacks;
 221
 222     /// \brief The outer scope, which contains local variable
 223     /// definitions from some other instantiation (that may not be
 224     /// relevant to this particular scope).
 225     LocalInstantiationScope *Outer;
 226
 227     /// \brief Whether we have already exited this scope.
 228     bool Exited;
 229
 230     /// \brief Whether to combine this scope with the outer scope, such that
 231     /// lookup will search our outer scope.
 232     bool CombineWithOuterScope;
 233
 234     /// \brief If non-NULL, the template parameter pack that has been
 235     /// partially substituted per C++0x [temp.arg.explicit]p9.
 236     NamedDecl *PartiallySubstitutedPack;
 237
 238     /// \brief If \c PartiallySubstitutedPack is non-null, the set of
 239     /// explicitly-specified template arguments in that pack.
 240     const TemplateArgument *ArgsInPartiallySubstitutedPack;
 241
 242     /// \brief If \c PartiallySubstitutedPack, the number of
 243     /// explicitly-specified template arguments in
 244     /// ArgsInPartiallySubstitutedPack.
 245     unsigned NumArgsInPartiallySubstitutedPack;
 246
 247     // This class is non-copyable
 248     LocalInstantiationScope(
 249       const LocalInstantiationScope &) LLVM_DELETED_FUNCTION;
 250     void operator=(const LocalInstantiationScope &) LLVM_DELETED_FUNCTION;
 251
 252   public:
 253     LocalInstantiationScope(Sema &SemaRef, bool CombineWithOuterScope = false)
 254       : SemaRef(SemaRef), Outer(SemaRef.CurrentInstantiationScope),
 255         Exited(false), CombineWithOuterScope(CombineWithOuterScope),
 256         PartiallySubstitutedPack(0)
 257     {
 258       SemaRef.CurrentInstantiationScope = this;
 259     }
 260
 261     ~LocalInstantiationScope() {
 262       Exit();
 263     }
 264
 265     const Sema &getSema() const { return SemaRef; }
 266
 267     /// \brief Exit this local instantiation scope early.
 268     void Exit() {
 269       if (Exited)
 270         return;
 271
 272       for (unsigned I = 0, N = ArgumentPacks.size(); I != N; ++I)
 273         delete ArgumentPacks[I];
 274
 275       SemaRef.CurrentInstantiationScope = Outer;
 276       Exited = true;
 277     }
 278
 279     /// \brief Clone this scope, and all outer scopes, down to the given
 280     /// outermost scope.
 281     LocalInstantiationScope *cloneScopes(LocalInstantiationScope *Outermost) {
 282       if (this == Outermost) return this;
 283       LocalInstantiationScope *newScope =
 284         new LocalInstantiationScope(SemaRef, CombineWithOuterScope);
 285
 286       newScope->Outer = 0;
 287       if (Outer)
 288         newScope->Outer = Outer->cloneScopes(Outermost);
 289
 290       newScope->PartiallySubstitutedPack = PartiallySubstitutedPack;
 291       newScope->ArgsInPartiallySubstitutedPack = ArgsInPartiallySubstitutedPack;
 292       newScope->NumArgsInPartiallySubstitutedPack =
 293         NumArgsInPartiallySubstitutedPack;
 294
 295       for (LocalDeclsMap::iterator I = LocalDecls.begin(), E = LocalDecls.end();
 296            I != E; ++I) {
 297         const Decl *D = I->first;
 298         llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored =
 299           newScope->LocalDecls[D];
 300         if (I->second.is<Decl *>()) {
 301           Stored = I->second.get<Decl *>();
 302         } else {
 303           DeclArgumentPack *OldPack = I->second.get<DeclArgumentPack *>();
 304           DeclArgumentPack *NewPack = new DeclArgumentPack(*OldPack);
 305           Stored = NewPack;
 306           newScope->ArgumentPacks.push_back(NewPack);
 307         }
 308       }
 309       return newScope;
 310     }
 311
 312     /// \brief deletes the given scope, and all otuer scopes, down to the
 313     /// given outermost scope.
 314     static void deleteScopes(LocalInstantiationScope *Scope,
 315                              LocalInstantiationScope *Outermost) {
 316       while (Scope && Scope != Outermost) {
 317         LocalInstantiationScope *Out = Scope->Outer;
 318         delete Scope;
 319         Scope = Out;
 320       }
 321     }
 322
 323     /// \brief Find the instantiation of the declaration D within the current
 324     /// instantiation scope.
 325     ///
 326     /// \param D The declaration whose instantiation we are searching for.
 327     ///
 328     /// \returns A pointer to the declaration or argument pack of declarations
 329     /// to which the declaration \c D is instantiataed, if found. Otherwise,
 330     /// returns NULL.
 331     llvm::PointerUnion<Decl *, DeclArgumentPack *> *
 332     findInstantiationOf(const Decl *D);
 333
 334     void InstantiatedLocal(const Decl *D, Decl *Inst);
 335     void InstantiatedLocalPackArg(const Decl *D, Decl *Inst);
 336     void MakeInstantiatedLocalArgPack(const Decl *D);
 337
 338     /// \brief Note that the given parameter pack has been partially substituted
 339     /// via explicit specification of template arguments
 340     /// (C++0x [temp.arg.explicit]p9).
 341     ///
 342     /// \param Pack The parameter pack, which will always be a template
 343     /// parameter pack.
 344     ///
 345     /// \param ExplicitArgs The explicitly-specified template arguments provided
 346     /// for this parameter pack.
 347     ///
 348     /// \param NumExplicitArgs The number of explicitly-specified template
 349     /// arguments provided for this parameter pack.
 350     void SetPartiallySubstitutedPack(NamedDecl *Pack,
 351                                      const TemplateArgument *ExplicitArgs,
 352                                      unsigned NumExplicitArgs);
 353
 354     /// \brief Reset the partially-substituted pack when it is no longer of
 355     /// interest.
 356     void ResetPartiallySubstitutedPack() {
 357       assert(PartiallySubstitutedPack && "No partially-substituted pack");
 358       PartiallySubstitutedPack = 0;
 359       ArgsInPartiallySubstitutedPack = 0;
 360       NumArgsInPartiallySubstitutedPack = 0;
 361     }
 362
 363     /// \brief Retrieve the partially-substitued template parameter pack.
 364     ///
 365     /// If there is no partially-substituted parameter pack, returns NULL.
 366     NamedDecl *getPartiallySubstitutedPack(
 367                                       const TemplateArgument **ExplicitArgs = 0,
 368                                            unsigned *NumExplicitArgs = 0) const;
 369   };
 370
 371   class TemplateDeclInstantiator
 372     : public DeclVisitor<TemplateDeclInstantiator, Decl *>
 373   {
 374     Sema &SemaRef;
 375     Sema::ArgumentPackSubstitutionIndexRAII SubstIndex;
 376     DeclContext *Owner;
 377     const MultiLevelTemplateArgumentList &TemplateArgs;
 378     Sema::LateInstantiatedAttrVec* LateAttrs;
 379     LocalInstantiationScope *StartingScope;
 380
 381     /// \brief A list of out-of-line class template partial
 382     /// specializations that will need to be instantiated after the
 383     /// enclosing class's instantiation is complete.
 384     SmallVector<std::pair<ClassTemplateDecl *,
 385                                 ClassTemplatePartialSpecializationDecl *>, 4>
 386       OutOfLinePartialSpecs;
 387
 388   public:
 389     TemplateDeclInstantiator(Sema &SemaRef, DeclContext *Owner,
 390                              const MultiLevelTemplateArgumentList &TemplateArgs)
 391       : SemaRef(SemaRef),
 392         SubstIndex(SemaRef, SemaRef.ArgumentPackSubstitutionIndex),
 393         Owner(Owner), TemplateArgs(TemplateArgs), LateAttrs(0), StartingScope(0)
 394     { }
 395
 396     // FIXME: Once we get closer to completion, replace these manually-written
 397     // declarations with automatically-generated ones from
 398     // clang/AST/DeclNodes.inc.
 399     Decl *VisitTranslationUnitDecl(TranslationUnitDecl *D);
 400     Decl *VisitLabelDecl(LabelDecl *D);
 401     Decl *VisitNamespaceDecl(NamespaceDecl *D);
 402     Decl *VisitNamespaceAliasDecl(NamespaceAliasDecl *D);
 403     Decl *VisitTypedefDecl(TypedefDecl *D);
 404     Decl *VisitTypeAliasDecl(TypeAliasDecl *D);
 405     Decl *VisitTypeAliasTemplateDecl(TypeAliasTemplateDecl *D);
 406     Decl *VisitVarDecl(VarDecl *D);
 407     Decl *VisitAccessSpecDecl(AccessSpecDecl *D);
 408     Decl *VisitFieldDecl(FieldDecl *D);
 409     Decl *VisitMSPropertyDecl(MSPropertyDecl *D);
 410     Decl *VisitIndirectFieldDecl(IndirectFieldDecl *D);
 411     Decl *VisitStaticAssertDecl(StaticAssertDecl *D);
 412     Decl *VisitEnumDecl(EnumDecl *D);
 413     Decl *VisitEnumConstantDecl(EnumConstantDecl *D);
 414     Decl *VisitFriendDecl(FriendDecl *D);
 415     Decl *VisitFunctionDecl(FunctionDecl *D,
 416                             TemplateParameterList *TemplateParams = 0);
 417     Decl *VisitCXXRecordDecl(CXXRecordDecl *D);
 418     Decl *VisitCXXMethodDecl(CXXMethodDecl *D,
 419                              TemplateParameterList *TemplateParams = 0,
 420                              bool IsClassScopeSpecialization = false);
 421     Decl *VisitCXXConstructorDecl(CXXConstructorDecl *D);
 422     Decl *VisitCXXDestructorDecl(CXXDestructorDecl *D);
 423     Decl *VisitCXXConversionDecl(CXXConversionDecl *D);
 424     ParmVarDecl *VisitParmVarDecl(ParmVarDecl *D);
 425     Decl *VisitClassTemplateDecl(ClassTemplateDecl *D);
 426     Decl *VisitClassTemplatePartialSpecializationDecl(
 427                                     ClassTemplatePartialSpecializationDecl *D);
 428     Decl *VisitFunctionTemplateDecl(FunctionTemplateDecl *D);
 429     Decl *VisitTemplateTypeParmDecl(TemplateTypeParmDecl *D);
 430     Decl *VisitNonTypeTemplateParmDecl(NonTypeTemplateParmDecl *D);
 431     Decl *VisitTemplateTemplateParmDecl(TemplateTemplateParmDecl *D);
 432     Decl *VisitUsingDirectiveDecl(UsingDirectiveDecl *D);
 433     Decl *VisitUsingDecl(UsingDecl *D);
 434     Decl *VisitUsingShadowDecl(UsingShadowDecl *D);
 435     Decl *VisitUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *D);
 436     Decl *VisitUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *D);
 437     Decl *VisitClassScopeFunctionSpecializationDecl(
 438                                       ClassScopeFunctionSpecializationDecl *D);
 439     Decl *VisitOMPThreadPrivateDecl(OMPThreadPrivateDecl *D);
 440
 441     // Base case. FIXME: Remove once we can instantiate everything.
 442     Decl *VisitDecl(Decl *D) {
 443       unsigned DiagID = SemaRef.getDiagnostics().getCustomDiagID(
 444                                                    DiagnosticsEngine::Error,
 445                                                    "cannot instantiate %0 yet");
 446       SemaRef.Diag(D->getLocation(), DiagID)
 447         << D->getDeclKindName();
 448
 449       return 0;
 450     }
 451
 452     // Enable late instantiation of attributes.  Late instantiated attributes
 453     // will be stored in LA.
 454     void enableLateAttributeInstantiation(Sema::LateInstantiatedAttrVec *LA) {
 455       LateAttrs = LA;
 456       StartingScope = SemaRef.CurrentInstantiationScope;
 457     }
 458
 459     // Disable late instantiation of attributes.
 460     void disableLateAttributeInstantiation() {
 461       LateAttrs = 0;
 462       StartingScope = 0;
 463     }
 464
 465     LocalInstantiationScope *getStartingScope() const { return StartingScope; }
 466
 467     typedef
 468       SmallVectorImpl<std::pair<ClassTemplateDecl *,
 469                                      ClassTemplatePartialSpecializationDecl *> >
 470         ::iterator
 471       delayed_partial_spec_iterator;
 472
 473     /// \brief Return an iterator to the beginning of the set of
 474     /// "delayed" partial specializations, which must be passed to
 475     /// InstantiateClassTemplatePartialSpecialization once the class
 476     /// definition has been completed.
 477     delayed_partial_spec_iterator delayed_partial_spec_begin() {
 478       return OutOfLinePartialSpecs.begin();
 479     }
 480
 481     /// \brief Return an iterator to the end of the set of
 482     /// "delayed" partial specializations, which must be passed to
 483     /// InstantiateClassTemplatePartialSpecialization once the class
 484     /// definition has been completed.
 485     delayed_partial_spec_iterator delayed_partial_spec_end() {
 486       return OutOfLinePartialSpecs.end();
 487     }
 488
 489     // Helper functions for instantiating methods.
 490     TypeSourceInfo *SubstFunctionType(FunctionDecl *D,
 491                              SmallVectorImpl<ParmVarDecl *> &Params);
 492     bool InitFunctionInstantiation(FunctionDecl *New, FunctionDecl *Tmpl);
 493     bool InitMethodInstantiation(CXXMethodDecl *New, CXXMethodDecl *Tmpl);
 494
 495     TemplateParameterList *
 496       SubstTemplateParams(TemplateParameterList *List);
 497
 498     bool SubstQualifier(const DeclaratorDecl *OldDecl,
 499                         DeclaratorDecl *NewDecl);
 500     bool SubstQualifier(const TagDecl *OldDecl,
 501                         TagDecl *NewDecl);
 502
 503     Decl *InstantiateTypedefNameDecl(TypedefNameDecl *D, bool IsTypeAlias);
 504     ClassTemplatePartialSpecializationDecl *
 505     InstantiateClassTemplatePartialSpecialization(
 506                                               ClassTemplateDecl *ClassTemplate,
 507                            ClassTemplatePartialSpecializationDecl *PartialSpec);
 508     void InstantiateEnumDefinition(EnumDecl *Enum, EnumDecl *Pattern);
 509   };
 510 }
 511
 512 #endif // LLVM_CLANG_SEMA_TEMPLATE_H