• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.
MultiLevelTemplateArgumentList()52     MultiLevelTemplateArgumentList() { }
53 
54     /// \brief Construct a single-level template argument list.
55     explicit
MultiLevelTemplateArgumentList(const TemplateArgumentList & TemplateArgs)56     MultiLevelTemplateArgumentList(const TemplateArgumentList &TemplateArgs) {
57       addOuterTemplateArguments(&TemplateArgs);
58     }
59 
60     /// \brief Determine the number of levels in this template argument
61     /// list.
getNumLevels()62     unsigned getNumLevels() const { return TemplateArgumentLists.size(); }
63 
64     /// \brief Retrieve the template argument at a given depth and index.
operator()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.
hasTemplateArgument(unsigned Depth,unsigned Index)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.
setArgument(unsigned Depth,unsigned Index,TemplateArgument Arg)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.
addOuterTemplateArguments(const TemplateArgumentList * TemplateArgs)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.
addOuterTemplateArguments(ArgList Args)103     void addOuterTemplateArguments(ArgList Args) {
104       TemplateArgumentLists.push_back(Args);
105     }
106 
107     /// \brief Retrieve the innermost template argument list.
getInnermost()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:
TemplatePartialOrderingContext(TPOC Value)133     TemplatePartialOrderingContext(TPOC Value) : Value(Value) {}
TPOC()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:
DeducedTemplateArgument()145     DeducedTemplateArgument()
146       : TemplateArgument(), DeducedFromArrayBound(false) { }
147 
148     DeducedTemplateArgument(const TemplateArgument &Arg,
149                             bool DeducedFromArrayBound = false)
TemplateArgument(Arg)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.
DeducedTemplateArgument(ASTContext & Ctx,const llvm::APSInt & Value,QualType ValueType,bool DeducedFromArrayBound)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.
wasDeducedFromArrayBound()163     bool wasDeducedFromArrayBound() const { return DeducedFromArrayBound; }
164 
165     /// \brief Specify whether the given non-type template argument
166     /// was deduced from an array bound.
setDeducedFromArrayBound(bool Deduced)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<ParmVarDecl *, 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 &) = delete;
243     void operator=(const LocalInstantiationScope &) = delete;
244 
245   public:
246     LocalInstantiationScope(Sema &SemaRef, bool CombineWithOuterScope = false)
SemaRef(SemaRef)247       : SemaRef(SemaRef), Outer(SemaRef.CurrentInstantiationScope),
248         Exited(false), CombineWithOuterScope(CombineWithOuterScope),
249         PartiallySubstitutedPack(nullptr)
250     {
251       SemaRef.CurrentInstantiationScope = this;
252     }
253 
~LocalInstantiationScope()254     ~LocalInstantiationScope() {
255       Exit();
256     }
257 
getSema()258     const Sema &getSema() const { return SemaRef; }
259 
260     /// \brief Exit this local instantiation scope early.
Exit()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.
cloneScopes(LocalInstantiationScope * Outermost)274     LocalInstantiationScope *cloneScopes(LocalInstantiationScope *Outermost) {
275       if (this == Outermost) return this;
276 
277       // Save the current scope from SemaRef since the LocalInstantiationScope
278       // will overwrite it on construction
279       LocalInstantiationScope *oldScope = SemaRef.CurrentInstantiationScope;
280 
281       LocalInstantiationScope *newScope =
282         new LocalInstantiationScope(SemaRef, CombineWithOuterScope);
283 
284       newScope->Outer = nullptr;
285       if (Outer)
286         newScope->Outer = Outer->cloneScopes(Outermost);
287 
288       newScope->PartiallySubstitutedPack = PartiallySubstitutedPack;
289       newScope->ArgsInPartiallySubstitutedPack = ArgsInPartiallySubstitutedPack;
290       newScope->NumArgsInPartiallySubstitutedPack =
291         NumArgsInPartiallySubstitutedPack;
292 
293       for (LocalDeclsMap::iterator I = LocalDecls.begin(), E = LocalDecls.end();
294            I != E; ++I) {
295         const Decl *D = I->first;
296         llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored =
297           newScope->LocalDecls[D];
298         if (I->second.is<Decl *>()) {
299           Stored = I->second.get<Decl *>();
300         } else {
301           DeclArgumentPack *OldPack = I->second.get<DeclArgumentPack *>();
302           DeclArgumentPack *NewPack = new DeclArgumentPack(*OldPack);
303           Stored = NewPack;
304           newScope->ArgumentPacks.push_back(NewPack);
305         }
306       }
307       // Restore the saved scope to SemaRef
308       SemaRef.CurrentInstantiationScope = oldScope;
309       return newScope;
310     }
311 
312     /// \brief deletes the given scope, and all otuer scopes, down to the
313     /// given outermost scope.
deleteScopes(LocalInstantiationScope * Scope,LocalInstantiationScope * Outermost)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 instantiated, 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, ParmVarDecl *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.
ResetPartiallySubstitutedPack()356     void ResetPartiallySubstitutedPack() {
357       assert(PartiallySubstitutedPack && "No partially-substituted pack");
358       PartiallySubstitutedPack = nullptr;
359       ArgsInPartiallySubstitutedPack = nullptr;
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 *
367     getPartiallySubstitutedPack(const TemplateArgument **ExplicitArgs = nullptr,
368                                 unsigned *NumExplicitArgs = nullptr) 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     /// \brief A list of out-of-line variable template partial
389     /// specializations that will need to be instantiated after the
390     /// enclosing variable's instantiation is complete.
391     /// FIXME: Verify that this is needed.
392     SmallVector<
393         std::pair<VarTemplateDecl *, VarTemplatePartialSpecializationDecl *>, 4>
394     OutOfLineVarPartialSpecs;
395 
396   public:
TemplateDeclInstantiator(Sema & SemaRef,DeclContext * Owner,const MultiLevelTemplateArgumentList & TemplateArgs)397     TemplateDeclInstantiator(Sema &SemaRef, DeclContext *Owner,
398                              const MultiLevelTemplateArgumentList &TemplateArgs)
399       : SemaRef(SemaRef),
400         SubstIndex(SemaRef, SemaRef.ArgumentPackSubstitutionIndex),
401         Owner(Owner), TemplateArgs(TemplateArgs), LateAttrs(nullptr),
402         StartingScope(nullptr) {}
403 
404 // Define all the decl visitors using DeclNodes.inc
405 #define DECL(DERIVED, BASE) \
406     Decl *Visit ## DERIVED ## Decl(DERIVED ## Decl *D);
407 #define ABSTRACT_DECL(DECL)
408 
409 // Decls which never appear inside a class or function.
410 #define OBJCCONTAINER(DERIVED, BASE)
411 #define FILESCOPEASM(DERIVED, BASE)
412 #define IMPORT(DERIVED, BASE)
413 #define LINKAGESPEC(DERIVED, BASE)
414 #define OBJCCOMPATIBLEALIAS(DERIVED, BASE)
415 #define OBJCMETHOD(DERIVED, BASE)
416 #define OBJCTYPEPARAM(DERIVED, BASE)
417 #define OBJCIVAR(DERIVED, BASE)
418 #define OBJCPROPERTY(DERIVED, BASE)
419 #define OBJCPROPERTYIMPL(DERIVED, BASE)
420 #define EMPTY(DERIVED, BASE)
421 
422 // Decls which use special-case instantiation code.
423 #define BLOCK(DERIVED, BASE)
424 #define CAPTURED(DERIVED, BASE)
425 #define IMPLICITPARAM(DERIVED, BASE)
426 
427 #include "clang/AST/DeclNodes.inc"
428 
429     // A few supplemental visitor functions.
430     Decl *VisitCXXMethodDecl(CXXMethodDecl *D,
431                              TemplateParameterList *TemplateParams,
432                              bool IsClassScopeSpecialization = false);
433     Decl *VisitFunctionDecl(FunctionDecl *D,
434                             TemplateParameterList *TemplateParams);
435     Decl *VisitDecl(Decl *D);
436     Decl *VisitVarDecl(VarDecl *D, bool InstantiatingVarTemplate);
437 
438     // Enable late instantiation of attributes.  Late instantiated attributes
439     // will be stored in LA.
enableLateAttributeInstantiation(Sema::LateInstantiatedAttrVec * LA)440     void enableLateAttributeInstantiation(Sema::LateInstantiatedAttrVec *LA) {
441       LateAttrs = LA;
442       StartingScope = SemaRef.CurrentInstantiationScope;
443     }
444 
445     // Disable late instantiation of attributes.
disableLateAttributeInstantiation()446     void disableLateAttributeInstantiation() {
447       LateAttrs = nullptr;
448       StartingScope = nullptr;
449     }
450 
getStartingScope()451     LocalInstantiationScope *getStartingScope() const { return StartingScope; }
452 
453     typedef
454       SmallVectorImpl<std::pair<ClassTemplateDecl *,
455                                      ClassTemplatePartialSpecializationDecl *> >
456         ::iterator
457       delayed_partial_spec_iterator;
458 
459     typedef SmallVectorImpl<std::pair<
460         VarTemplateDecl *, VarTemplatePartialSpecializationDecl *> >::iterator
461     delayed_var_partial_spec_iterator;
462 
463     /// \brief Return an iterator to the beginning of the set of
464     /// "delayed" partial specializations, which must be passed to
465     /// InstantiateClassTemplatePartialSpecialization once the class
466     /// definition has been completed.
delayed_partial_spec_begin()467     delayed_partial_spec_iterator delayed_partial_spec_begin() {
468       return OutOfLinePartialSpecs.begin();
469     }
470 
delayed_var_partial_spec_begin()471     delayed_var_partial_spec_iterator delayed_var_partial_spec_begin() {
472       return OutOfLineVarPartialSpecs.begin();
473     }
474 
475     /// \brief Return an iterator to the end of the set of
476     /// "delayed" partial specializations, which must be passed to
477     /// InstantiateClassTemplatePartialSpecialization once the class
478     /// definition has been completed.
delayed_partial_spec_end()479     delayed_partial_spec_iterator delayed_partial_spec_end() {
480       return OutOfLinePartialSpecs.end();
481     }
482 
delayed_var_partial_spec_end()483     delayed_var_partial_spec_iterator delayed_var_partial_spec_end() {
484       return OutOfLineVarPartialSpecs.end();
485     }
486 
487     // Helper functions for instantiating methods.
488     TypeSourceInfo *SubstFunctionType(FunctionDecl *D,
489                              SmallVectorImpl<ParmVarDecl *> &Params);
490     bool InitFunctionInstantiation(FunctionDecl *New, FunctionDecl *Tmpl);
491     bool InitMethodInstantiation(CXXMethodDecl *New, CXXMethodDecl *Tmpl);
492 
493     TemplateParameterList *
494       SubstTemplateParams(TemplateParameterList *List);
495 
496     bool SubstQualifier(const DeclaratorDecl *OldDecl,
497                         DeclaratorDecl *NewDecl);
498     bool SubstQualifier(const TagDecl *OldDecl,
499                         TagDecl *NewDecl);
500 
501     Decl *VisitVarTemplateSpecializationDecl(
502         VarTemplateDecl *VarTemplate, VarDecl *FromVar, void *InsertPos,
503         const TemplateArgumentListInfo &TemplateArgsInfo,
504         ArrayRef<TemplateArgument> Converted);
505 
506     Decl *InstantiateTypedefNameDecl(TypedefNameDecl *D, bool IsTypeAlias);
507     ClassTemplatePartialSpecializationDecl *
508     InstantiateClassTemplatePartialSpecialization(
509                                               ClassTemplateDecl *ClassTemplate,
510                            ClassTemplatePartialSpecializationDecl *PartialSpec);
511     VarTemplatePartialSpecializationDecl *
512     InstantiateVarTemplatePartialSpecialization(
513         VarTemplateDecl *VarTemplate,
514         VarTemplatePartialSpecializationDecl *PartialSpec);
515     void InstantiateEnumDefinition(EnumDecl *Enum, EnumDecl *Pattern);
516   };
517 }
518 
519 #endif // LLVM_CLANG_SEMA_TEMPLATE_H
520