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 "llvm/ADT/SmallVector.h"
  18 #include <cassert>
  19 #include <utility>
  20
  21 namespace clang {
  22   /// \brief Data structure that captures multiple levels of template argument
  23   /// lists for use in template instantiation.
  24   ///
  25   /// Multiple levels of template arguments occur when instantiating the
  26   /// definitions of member templates. For example:
  27   ///
  28   /// \code
  29   /// template<typename T>
  30   /// struct X {
  31   ///   template<T Value>
  32   ///   struct Y {
  33   ///     void f();
  34   ///   };
  35   /// };
  36   /// \endcode
  37   ///
  38   /// When instantiating X<int>::Y<17>::f, the multi-level template argument
  39   /// list will contain a template argument list (int) at depth 0 and a
  40   /// template argument list (17) at depth 1.
  41   class MultiLevelTemplateArgumentList {
  42   public:
  43     typedef std::pair<const TemplateArgument *, unsigned> ArgList;
  44
  45   private:
  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].second);
  68       return TemplateArgumentLists[getNumLevels() - Depth - 1].first[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].second)
  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].second);
  89       const_cast<TemplateArgument&>(
  90                 TemplateArgumentLists[getNumLevels() - Depth - 1].first[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       TemplateArgumentLists.push_back(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       TemplateArgumentLists.push_back(ArgList(Args, NumArgs));
 106     }
 107
 108     /// \brief Retrieve the innermost template argument list.
 109     const ArgList &getInnermost() const {
 110       return TemplateArgumentLists.front();
 111     }
 112   };
 113
 114   /// \brief The context in which partial ordering of function templates occurs.
 115   enum TPOC {
 116     /// \brief Partial ordering of function templates for a function call.
 117     TPOC_Call,
 118     /// \brief Partial ordering of function templates for a call to a
 119     /// conversion function.
 120     TPOC_Conversion,
 121     /// \brief Partial ordering of function templates in other contexts, e.g.,
 122     /// taking the address of a function template or matching a function
 123     /// template specialization to a function template.
 124     TPOC_Other
 125   };
 126
 127   // This is lame but unavoidable in a world without forward
 128   // declarations of enums.  The alternatives are to either pollute
 129   // Sema.h (by including this file) or sacrifice type safety (by
 130   // making Sema.h declare things as enums).
 131   class TemplatePartialOrderingContext {
 132     TPOC Value;
 133   public:
 134     TemplatePartialOrderingContext(TPOC Value) : Value(Value) {}
 135     operator TPOC() const { return Value; }
 136   };
 137
 138   /// \brief Captures a template argument whose value has been deduced
 139   /// via c++ template argument deduction.
 140   class DeducedTemplateArgument : public TemplateArgument {
 141     /// \brief For a non-type template argument, whether the value was
 142     /// deduced from an array bound.
 143     bool DeducedFromArrayBound;
 144
 145   public:
 146     DeducedTemplateArgument()
 147       : TemplateArgument(), DeducedFromArrayBound(false) { }
 148
 149     DeducedTemplateArgument(const TemplateArgument &Arg,
 150                             bool DeducedFromArrayBound = false)
 151       : TemplateArgument(Arg), DeducedFromArrayBound(DeducedFromArrayBound) { }
 152
 153     /// \brief Construct an integral non-type template argument that
 154     /// has been deduced, possibly from an array bound.
 155     DeducedTemplateArgument(const llvm::APSInt &Value,
 156                             QualType ValueType,
 157                             bool DeducedFromArrayBound)
 158       : TemplateArgument(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::DenseMap<const Decl *,
 189                            llvm::PointerUnion<Decl *, DeclArgumentPack *> >
 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(const LocalInstantiationScope &);
 242     LocalInstantiationScope &operator=(const LocalInstantiationScope &);
 243
 244   public:
 245     LocalInstantiationScope(Sema &SemaRef, bool CombineWithOuterScope = false)
 246       : SemaRef(SemaRef), Outer(SemaRef.CurrentInstantiationScope),
 247         Exited(false), CombineWithOuterScope(CombineWithOuterScope),
 248         PartiallySubstitutedPack(0)
 249     {
 250       SemaRef.CurrentInstantiationScope = this;
 251     }
 252
 253     ~LocalInstantiationScope() {
 254       Exit();
 255     }
 256
 257     const Sema &getSema() const { return SemaRef; }
 258
 259     /// \brief Exit this local instantiation scope early.
 260     void Exit() {
 261       if (Exited)
 262         return;
 263
 264       for (unsigned I = 0, N = ArgumentPacks.size(); I != N; ++I)
 265         delete ArgumentPacks[I];
 266
 267       SemaRef.CurrentInstantiationScope = Outer;
 268       Exited = true;
 269     }
 270
 271     /// \brief Find the instantiation of the declaration D within the current
 272     /// instantiation scope.
 273     ///
 274     /// \param D The declaration whose instantiation we are searching for.
 275     ///
 276     /// \returns A pointer to the declaration or argument pack of declarations
 277     /// to which the declaration \c D is instantiataed, if found. Otherwise,
 278     /// returns NULL.
 279     llvm::PointerUnion<Decl *, DeclArgumentPack *> *
 280     findInstantiationOf(const Decl *D);
 281
 282     void InstantiatedLocal(const Decl *D, Decl *Inst);
 283     void InstantiatedLocalPackArg(const Decl *D, Decl *Inst);
 284     void MakeInstantiatedLocalArgPack(const Decl *D);
 285
 286     /// \brief Note that the given parameter pack has been partially substituted
 287     /// via explicit specification of template arguments
 288     /// (C++0x [temp.arg.explicit]p9).
 289     ///
 290     /// \param Pack The parameter pack, which will always be a template
 291     /// parameter pack.
 292     ///
 293     /// \param ExplicitArgs The explicitly-specified template arguments provided
 294     /// for this parameter pack.
 295     ///
 296     /// \param NumExplicitArgs The number of explicitly-specified template
 297     /// arguments provided for this parameter pack.
 298     void SetPartiallySubstitutedPack(NamedDecl *Pack,
 299                                      const TemplateArgument *ExplicitArgs,
 300                                      unsigned NumExplicitArgs);
 301
 302     /// \brief Retrieve the partially-substitued template parameter pack.
 303     ///
 304     /// If there is no partially-substituted parameter pack, returns NULL.
 305     NamedDecl *getPartiallySubstitutedPack(
 306                                       const TemplateArgument **ExplicitArgs = 0,
 307                                            unsigned *NumExplicitArgs = 0) const;
 308   };
 309
 310   class TemplateDeclInstantiator
 311     : public DeclVisitor<TemplateDeclInstantiator, Decl *>
 312   {
 313     Sema &SemaRef;
 314     Sema::ArgumentPackSubstitutionIndexRAII SubstIndex;
 315     DeclContext *Owner;
 316     const MultiLevelTemplateArgumentList &TemplateArgs;
 317
 318     /// \brief A list of out-of-line class template partial
 319     /// specializations that will need to be instantiated after the
 320     /// enclosing class's instantiation is complete.
 321     SmallVector<std::pair<ClassTemplateDecl *,
 322                                 ClassTemplatePartialSpecializationDecl *>, 4>
 323       OutOfLinePartialSpecs;
 324
 325   public:
 326     TemplateDeclInstantiator(Sema &SemaRef, DeclContext *Owner,
 327                              const MultiLevelTemplateArgumentList &TemplateArgs)
 328       : SemaRef(SemaRef), SubstIndex(SemaRef, -1), Owner(Owner),
 329         TemplateArgs(TemplateArgs) { }
 330
 331     // FIXME: Once we get closer to completion, replace these manually-written
 332     // declarations with automatically-generated ones from
 333     // clang/AST/DeclNodes.inc.
 334     Decl *VisitTranslationUnitDecl(TranslationUnitDecl *D);
 335     Decl *VisitLabelDecl(LabelDecl *D);
 336     Decl *VisitNamespaceDecl(NamespaceDecl *D);
 337     Decl *VisitNamespaceAliasDecl(NamespaceAliasDecl *D);
 338     Decl *VisitTypedefDecl(TypedefDecl *D);
 339     Decl *VisitTypeAliasDecl(TypeAliasDecl *D);
 340     Decl *VisitTypeAliasTemplateDecl(TypeAliasTemplateDecl *D);
 341     Decl *VisitVarDecl(VarDecl *D);
 342     Decl *VisitAccessSpecDecl(AccessSpecDecl *D);
 343     Decl *VisitFieldDecl(FieldDecl *D);
 344     Decl *VisitIndirectFieldDecl(IndirectFieldDecl *D);
 345     Decl *VisitStaticAssertDecl(StaticAssertDecl *D);
 346     Decl *VisitEnumDecl(EnumDecl *D);
 347     Decl *VisitEnumConstantDecl(EnumConstantDecl *D);
 348     Decl *VisitFriendDecl(FriendDecl *D);
 349     Decl *VisitFunctionDecl(FunctionDecl *D,
 350                             TemplateParameterList *TemplateParams = 0);
 351     Decl *VisitCXXRecordDecl(CXXRecordDecl *D);
 352     Decl *VisitCXXMethodDecl(CXXMethodDecl *D,
 353                              TemplateParameterList *TemplateParams = 0,
 354                              bool IsClassScopeSpecialization = false);
 355     Decl *VisitCXXConstructorDecl(CXXConstructorDecl *D);
 356     Decl *VisitCXXDestructorDecl(CXXDestructorDecl *D);
 357     Decl *VisitCXXConversionDecl(CXXConversionDecl *D);
 358     ParmVarDecl *VisitParmVarDecl(ParmVarDecl *D);
 359     Decl *VisitClassTemplateDecl(ClassTemplateDecl *D);
 360     Decl *VisitClassTemplatePartialSpecializationDecl(
 361                                     ClassTemplatePartialSpecializationDecl *D);
 362     Decl *VisitFunctionTemplateDecl(FunctionTemplateDecl *D);
 363     Decl *VisitTemplateTypeParmDecl(TemplateTypeParmDecl *D);
 364     Decl *VisitNonTypeTemplateParmDecl(NonTypeTemplateParmDecl *D);
 365     Decl *VisitTemplateTemplateParmDecl(TemplateTemplateParmDecl *D);
 366     Decl *VisitUsingDirectiveDecl(UsingDirectiveDecl *D);
 367     Decl *VisitUsingDecl(UsingDecl *D);
 368     Decl *VisitUsingShadowDecl(UsingShadowDecl *D);
 369     Decl *VisitUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *D);
 370     Decl *VisitUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *D);
 371     Decl *VisitClassScopeFunctionSpecializationDecl(
 372                                       ClassScopeFunctionSpecializationDecl *D);
 373
 374     // Base case. FIXME: Remove once we can instantiate everything.
 375     Decl *VisitDecl(Decl *D) {
 376       unsigned DiagID = SemaRef.getDiagnostics().getCustomDiagID(
 377                                                    DiagnosticsEngine::Error,
 378                                                    "cannot instantiate %0 yet");
 379       SemaRef.Diag(D->getLocation(), DiagID)
 380         << D->getDeclKindName();
 381
 382       return 0;
 383     }
 384
 385     typedef
 386       SmallVectorImpl<std::pair<ClassTemplateDecl *,
 387                                      ClassTemplatePartialSpecializationDecl *> >
 388         ::iterator
 389       delayed_partial_spec_iterator;
 390
 391     /// \brief Return an iterator to the beginning of the set of
 392     /// "delayed" partial specializations, which must be passed to
 393     /// InstantiateClassTemplatePartialSpecialization once the class
 394     /// definition has been completed.
 395     delayed_partial_spec_iterator delayed_partial_spec_begin() {
 396       return OutOfLinePartialSpecs.begin();
 397     }
 398
 399     /// \brief Return an iterator to the end of the set of
 400     /// "delayed" partial specializations, which must be passed to
 401     /// InstantiateClassTemplatePartialSpecialization once the class
 402     /// definition has been completed.
 403     delayed_partial_spec_iterator delayed_partial_spec_end() {
 404       return OutOfLinePartialSpecs.end();
 405     }
 406
 407     // Helper functions for instantiating methods.
 408     TypeSourceInfo *SubstFunctionType(FunctionDecl *D,
 409                              SmallVectorImpl<ParmVarDecl *> &Params);
 410     bool InitFunctionInstantiation(FunctionDecl *New, FunctionDecl *Tmpl);
 411     bool InitMethodInstantiation(CXXMethodDecl *New, CXXMethodDecl *Tmpl);
 412
 413     TemplateParameterList *
 414       SubstTemplateParams(TemplateParameterList *List);
 415
 416     bool SubstQualifier(const DeclaratorDecl *OldDecl,
 417                         DeclaratorDecl *NewDecl);
 418     bool SubstQualifier(const TagDecl *OldDecl,
 419                         TagDecl *NewDecl);
 420
 421     Decl *InstantiateTypedefNameDecl(TypedefNameDecl *D, bool IsTypeAlias);
 422     ClassTemplatePartialSpecializationDecl *
 423     InstantiateClassTemplatePartialSpecialization(
 424                                               ClassTemplateDecl *ClassTemplate,
 425                            ClassTemplatePartialSpecializationDecl *PartialSpec);
 426   };
 427 }
 428
 429 #endif // LLVM_CLANG_SEMA_TEMPLATE_H