Home | History | Annotate | Download | only in Sema 
      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 Clone this scope, and all outer scopes, down to the given
    272     /// outermost scope.
    273     LocalInstantiationScope *cloneScopes(LocalInstantiationScope *Outermost) {
    274       if (this == Outermost) return this;
    275       LocalInstantiationScope *newScope =
    276         new LocalInstantiationScope(SemaRef, CombineWithOuterScope);
    277 
    278       newScope->Outer = 0;
    279       if (Outer)
    280         newScope->Outer = Outer->cloneScopes(Outermost);
    281 
    282       newScope->PartiallySubstitutedPack = PartiallySubstitutedPack;
    283       newScope->ArgsInPartiallySubstitutedPack = ArgsInPartiallySubstitutedPack;
    284       newScope->NumArgsInPartiallySubstitutedPack =
    285         NumArgsInPartiallySubstitutedPack;
    286 
    287       for (LocalDeclsMap::iterator I = LocalDecls.begin(), E = LocalDecls.end();
    288            I != E; ++I) {
    289         const Decl *D = I->first;
    290         llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored =
    291           newScope->LocalDecls[D];
    292         if (I->second.is<Decl *>()) {
    293           Stored = I->second.get<Decl *>();
    294         } else {
    295           DeclArgumentPack *OldPack = I->second.get<DeclArgumentPack *>();
    296           DeclArgumentPack *NewPack = new DeclArgumentPack(*OldPack);
    297           Stored = NewPack;
    298           newScope->ArgumentPacks.push_back(NewPack);
    299         }
    300       }
    301       return newScope;
    302     }
    303 
    304     /// \brief deletes the given scope, and all otuer scopes, down to the
    305     /// given outermost scope.
    306     static void deleteScopes(LocalInstantiationScope *Scope,
    307                              LocalInstantiationScope *Outermost) {
    308       while (Scope && Scope != Outermost) {
    309         LocalInstantiationScope *Out = Scope->Outer;
    310         delete Scope;
    311         Scope = Out;
    312       }
    313     }
    314 
    315     /// \brief Find the instantiation of the declaration D within the current
    316     /// instantiation scope.
    317     ///
    318     /// \param D The declaration whose instantiation we are searching for.
    319     ///
    320     /// \returns A pointer to the declaration or argument pack of declarations
    321     /// to which the declaration \c D is instantiataed, if found. Otherwise,
    322     /// returns NULL.
    323     llvm::PointerUnion<Decl *, DeclArgumentPack *> *
    324     findInstantiationOf(const Decl *D);
    325 
    326     void InstantiatedLocal(const Decl *D, Decl *Inst);
    327     void InstantiatedLocalPackArg(const Decl *D, Decl *Inst);
    328     void MakeInstantiatedLocalArgPack(const Decl *D);
    329 
    330     /// \brief Note that the given parameter pack has been partially substituted
    331     /// via explicit specification of template arguments
    332     /// (C++0x [temp.arg.explicit]p9).
    333     ///
    334     /// \param Pack The parameter pack, which will always be a template
    335     /// parameter pack.
    336     ///
    337     /// \param ExplicitArgs The explicitly-specified template arguments provided
    338     /// for this parameter pack.
    339     ///
    340     /// \param NumExplicitArgs The number of explicitly-specified template
    341     /// arguments provided for this parameter pack.
    342     void SetPartiallySubstitutedPack(NamedDecl *Pack,
    343                                      const TemplateArgument *ExplicitArgs,
    344                                      unsigned NumExplicitArgs);
    345 
    346     /// \brief Retrieve the partially-substitued template parameter pack.
    347     ///
    348     /// If there is no partially-substituted parameter pack, returns NULL.
    349     NamedDecl *getPartiallySubstitutedPack(
    350                                       const TemplateArgument **ExplicitArgs = 0,
    351                                            unsigned *NumExplicitArgs = 0) const;
    352   };
    353 
    354   class TemplateDeclInstantiator
    355     : public DeclVisitor<TemplateDeclInstantiator, Decl *>
    356   {
    357     Sema &SemaRef;
    358     Sema::ArgumentPackSubstitutionIndexRAII SubstIndex;
    359     DeclContext *Owner;
    360     const MultiLevelTemplateArgumentList &TemplateArgs;
    361     Sema::LateInstantiatedAttrVec* LateAttrs;
    362     LocalInstantiationScope *StartingScope;
    363 
    364     /// \brief A list of out-of-line class template partial
    365     /// specializations that will need to be instantiated after the
    366     /// enclosing class's instantiation is complete.
    367     SmallVector<std::pair<ClassTemplateDecl *,
    368                                 ClassTemplatePartialSpecializationDecl *>, 4>
    369       OutOfLinePartialSpecs;
    370 
    371   public:
    372     TemplateDeclInstantiator(Sema &SemaRef, DeclContext *Owner,
    373                              const MultiLevelTemplateArgumentList &TemplateArgs)
    374       : SemaRef(SemaRef), SubstIndex(SemaRef, -1), Owner(Owner),
    375         TemplateArgs(TemplateArgs), LateAttrs(0), StartingScope(0) { }
    376 
    377     // FIXME: Once we get closer to completion, replace these manually-written
    378     // declarations with automatically-generated ones from
    379     // clang/AST/DeclNodes.inc.
    380     Decl *VisitTranslationUnitDecl(TranslationUnitDecl *D);
    381     Decl *VisitLabelDecl(LabelDecl *D);
    382     Decl *VisitNamespaceDecl(NamespaceDecl *D);
    383     Decl *VisitNamespaceAliasDecl(NamespaceAliasDecl *D);
    384     Decl *VisitTypedefDecl(TypedefDecl *D);
    385     Decl *VisitTypeAliasDecl(TypeAliasDecl *D);
    386     Decl *VisitTypeAliasTemplateDecl(TypeAliasTemplateDecl *D);
    387     Decl *VisitVarDecl(VarDecl *D);
    388     Decl *VisitAccessSpecDecl(AccessSpecDecl *D);
    389     Decl *VisitFieldDecl(FieldDecl *D);
    390     Decl *VisitIndirectFieldDecl(IndirectFieldDecl *D);
    391     Decl *VisitStaticAssertDecl(StaticAssertDecl *D);
    392     Decl *VisitEnumDecl(EnumDecl *D);
    393     Decl *VisitEnumConstantDecl(EnumConstantDecl *D);
    394     Decl *VisitFriendDecl(FriendDecl *D);
    395     Decl *VisitFunctionDecl(FunctionDecl *D,
    396                             TemplateParameterList *TemplateParams = 0);
    397     Decl *VisitCXXRecordDecl(CXXRecordDecl *D);
    398     Decl *VisitCXXMethodDecl(CXXMethodDecl *D,
    399                              TemplateParameterList *TemplateParams = 0,
    400                              bool IsClassScopeSpecialization = false);
    401     Decl *VisitCXXConstructorDecl(CXXConstructorDecl *D);
    402     Decl *VisitCXXDestructorDecl(CXXDestructorDecl *D);
    403     Decl *VisitCXXConversionDecl(CXXConversionDecl *D);
    404     ParmVarDecl *VisitParmVarDecl(ParmVarDecl *D);
    405     Decl *VisitClassTemplateDecl(ClassTemplateDecl *D);
    406     Decl *VisitClassTemplatePartialSpecializationDecl(
    407                                     ClassTemplatePartialSpecializationDecl *D);
    408     Decl *VisitFunctionTemplateDecl(FunctionTemplateDecl *D);
    409     Decl *VisitTemplateTypeParmDecl(TemplateTypeParmDecl *D);
    410     Decl *VisitNonTypeTemplateParmDecl(NonTypeTemplateParmDecl *D);
    411     Decl *VisitTemplateTemplateParmDecl(TemplateTemplateParmDecl *D);
    412     Decl *VisitUsingDirectiveDecl(UsingDirectiveDecl *D);
    413     Decl *VisitUsingDecl(UsingDecl *D);
    414     Decl *VisitUsingShadowDecl(UsingShadowDecl *D);
    415     Decl *VisitUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *D);
    416     Decl *VisitUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *D);
    417     Decl *VisitClassScopeFunctionSpecializationDecl(
    418                                       ClassScopeFunctionSpecializationDecl *D);
    419 
    420     // Base case. FIXME: Remove once we can instantiate everything.
    421     Decl *VisitDecl(Decl *D) {
    422       unsigned DiagID = SemaRef.getDiagnostics().getCustomDiagID(
    423                                                    DiagnosticsEngine::Error,
    424                                                    "cannot instantiate %0 yet");
    425       SemaRef.Diag(D->getLocation(), DiagID)
    426         << D->getDeclKindName();
    427 
    428       return 0;
    429     }
    430 
    431     // Enable late instantiation of attributes.  Late instantiated attributes
    432     // will be stored in LA.
    433     void enableLateAttributeInstantiation(Sema::LateInstantiatedAttrVec *LA) {
    434       LateAttrs = LA;
    435       StartingScope = SemaRef.CurrentInstantiationScope;
    436     }
    437 
    438     // Disable late instantiation of attributes.
    439     void disableLateAttributeInstantiation() {
    440       LateAttrs = 0;
    441       StartingScope = 0;
    442     }
    443 
    444     LocalInstantiationScope *getStartingScope() const { return StartingScope; }
    445 
    446     typedef
    447       SmallVectorImpl<std::pair<ClassTemplateDecl *,
    448                                      ClassTemplatePartialSpecializationDecl *> >
    449         ::iterator
    450       delayed_partial_spec_iterator;
    451 
    452     /// \brief Return an iterator to the beginning of the set of
    453     /// "delayed" partial specializations, which must be passed to
    454     /// InstantiateClassTemplatePartialSpecialization once the class
    455     /// definition has been completed.
    456     delayed_partial_spec_iterator delayed_partial_spec_begin() {
    457       return OutOfLinePartialSpecs.begin();
    458     }
    459 
    460     /// \brief Return an iterator to the end of the set of
    461     /// "delayed" partial specializations, which must be passed to
    462     /// InstantiateClassTemplatePartialSpecialization once the class
    463     /// definition has been completed.
    464     delayed_partial_spec_iterator delayed_partial_spec_end() {
    465       return OutOfLinePartialSpecs.end();
    466     }
    467 
    468     // Helper functions for instantiating methods.
    469     TypeSourceInfo *SubstFunctionType(FunctionDecl *D,
    470                              SmallVectorImpl<ParmVarDecl *> &Params);
    471     bool InitFunctionInstantiation(FunctionDecl *New, FunctionDecl *Tmpl);
    472     bool InitMethodInstantiation(CXXMethodDecl *New, CXXMethodDecl *Tmpl);
    473 
    474     TemplateParameterList *
    475       SubstTemplateParams(TemplateParameterList *List);
    476 
    477     bool SubstQualifier(const DeclaratorDecl *OldDecl,
    478                         DeclaratorDecl *NewDecl);
    479     bool SubstQualifier(const TagDecl *OldDecl,
    480                         TagDecl *NewDecl);
    481 
    482     Decl *InstantiateTypedefNameDecl(TypedefNameDecl *D, bool IsTypeAlias);
    483     ClassTemplatePartialSpecializationDecl *
    484     InstantiateClassTemplatePartialSpecialization(
    485                                               ClassTemplateDecl *ClassTemplate,
    486                            ClassTemplatePartialSpecializationDecl *PartialSpec);
    487     void InstantiateEnumDefinition(EnumDecl *Enum, EnumDecl *Pattern);
    488   };
    489 }
    490 
    491 #endif // LLVM_CLANG_SEMA_TEMPLATE_H
    492