1 //===------- SemaTemplate.h - C++ Templates ---------------------*- C++ -*-===/
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //===----------------------------------------------------------------------===/
9 // This file provides types used in the semantic analysis of C++ templates.
11 //===----------------------------------------------------------------------===/
12 #ifndef LLVM_CLANG_SEMA_TEMPLATE_H
13 #define LLVM_CLANG_SEMA_TEMPLATE_H
15 #include "clang/AST/DeclTemplate.h"
16 #include "clang/AST/DeclVisitor.h"
17 #include "clang/Sema/Sema.h"
18 #include "llvm/ADT/SmallVector.h"
23 /// \brief Data structure that captures multiple levels of template argument
24 /// lists for use in template instantiation.
26 /// Multiple levels of template arguments occur when instantiating the
27 /// definitions of member templates. For example:
30 /// template<typename T>
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;
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;
50 /// \brief The number of outer levels of template arguments that are not
51 /// being substituted.
52 unsigned NumRetainedOuterLevels = 0;
55 /// \brief Construct an empty set of template argument lists.
56 MultiLevelTemplateArgumentList() { }
58 /// \brief Construct a single-level template argument list.
60 MultiLevelTemplateArgumentList(const TemplateArgumentList &TemplateArgs) {
61 addOuterTemplateArguments(&TemplateArgs);
64 /// \brief Determine the number of levels in this template argument
66 unsigned getNumLevels() const {
67 return TemplateArgumentLists.size() + NumRetainedOuterLevels;
70 /// \brief Determine the number of substituted levels in this template
72 unsigned getNumSubstitutedLevels() const {
73 return TemplateArgumentLists.size();
76 /// \brief Retrieve the template argument at a given depth and index.
77 const TemplateArgument &operator()(unsigned Depth, unsigned Index) const {
78 assert(NumRetainedOuterLevels <= Depth && Depth < getNumLevels());
79 assert(Index < TemplateArgumentLists[getNumLevels() - Depth - 1].size());
80 return TemplateArgumentLists[getNumLevels() - Depth - 1][Index];
83 /// \brief Determine whether there is a non-NULL template argument at the
84 /// given depth and index.
86 /// There must exist a template argument list at the given depth.
87 bool hasTemplateArgument(unsigned Depth, unsigned Index) const {
88 assert(Depth < getNumLevels());
90 if (Depth < NumRetainedOuterLevels)
93 if (Index >= TemplateArgumentLists[getNumLevels() - Depth - 1].size())
96 return !(*this)(Depth, Index).isNull();
99 /// \brief Clear out a specific template argument.
100 void setArgument(unsigned Depth, unsigned Index,
101 TemplateArgument Arg) {
102 assert(NumRetainedOuterLevels <= Depth && Depth < getNumLevels());
103 assert(Index < TemplateArgumentLists[getNumLevels() - Depth - 1].size());
104 const_cast<TemplateArgument&>(
105 TemplateArgumentLists[getNumLevels() - Depth - 1][Index])
109 /// \brief Add a new outermost level to the multi-level template argument
111 void addOuterTemplateArguments(const TemplateArgumentList *TemplateArgs) {
112 addOuterTemplateArguments(ArgList(TemplateArgs->data(),
113 TemplateArgs->size()));
116 /// \brief Add a new outmost level to the multi-level template argument
118 void addOuterTemplateArguments(ArgList Args) {
119 assert(!NumRetainedOuterLevels &&
120 "substituted args outside retained args?");
121 TemplateArgumentLists.push_back(Args);
124 /// \brief Add an outermost level that we are not substituting. We have no
125 /// arguments at this level, and do not remove it from the depth of inner
126 /// template parameters that we instantiate.
127 void addOuterRetainedLevel() {
128 ++NumRetainedOuterLevels;
131 /// \brief Retrieve the innermost template argument list.
132 const ArgList &getInnermost() const {
133 return TemplateArgumentLists.front();
137 /// \brief The context in which partial ordering of function templates occurs.
139 /// \brief Partial ordering of function templates for a function call.
141 /// \brief Partial ordering of function templates for a call to a
142 /// conversion function.
144 /// \brief Partial ordering of function templates in other contexts, e.g.,
145 /// taking the address of a function template or matching a function
146 /// template specialization to a function template.
150 // This is lame but unavoidable in a world without forward
151 // declarations of enums. The alternatives are to either pollute
152 // Sema.h (by including this file) or sacrifice type safety (by
153 // making Sema.h declare things as enums).
154 class TemplatePartialOrderingContext {
157 TemplatePartialOrderingContext(TPOC Value) : Value(Value) {}
158 operator TPOC() const { return Value; }
161 /// \brief Captures a template argument whose value has been deduced
162 /// via c++ template argument deduction.
163 class DeducedTemplateArgument : public TemplateArgument {
164 /// \brief For a non-type template argument, whether the value was
165 /// deduced from an array bound.
166 bool DeducedFromArrayBound;
169 DeducedTemplateArgument()
170 : TemplateArgument(), DeducedFromArrayBound(false) { }
172 DeducedTemplateArgument(const TemplateArgument &Arg,
173 bool DeducedFromArrayBound = false)
174 : TemplateArgument(Arg), DeducedFromArrayBound(DeducedFromArrayBound) { }
176 /// \brief Construct an integral non-type template argument that
177 /// has been deduced, possibly from an array bound.
178 DeducedTemplateArgument(ASTContext &Ctx,
179 const llvm::APSInt &Value,
181 bool DeducedFromArrayBound)
182 : TemplateArgument(Ctx, Value, ValueType),
183 DeducedFromArrayBound(DeducedFromArrayBound) { }
185 /// \brief For a non-type template argument, determine whether the
186 /// template argument was deduced from an array bound.
187 bool wasDeducedFromArrayBound() const { return DeducedFromArrayBound; }
189 /// \brief Specify whether the given non-type template argument
190 /// was deduced from an array bound.
191 void setDeducedFromArrayBound(bool Deduced) {
192 DeducedFromArrayBound = Deduced;
196 /// \brief A stack-allocated class that identifies which local
197 /// variable declaration instantiations are present in this scope.
199 /// A new instance of this class type will be created whenever we
200 /// instantiate a new function declaration, which will have its own
201 /// set of parameter declarations.
202 class LocalInstantiationScope {
204 /// \brief A set of declarations.
205 typedef SmallVector<ParmVarDecl *, 4> DeclArgumentPack;
208 /// \brief Reference to the semantic analysis that is performing
209 /// this template instantiation.
212 typedef llvm::SmallDenseMap<
213 const Decl *, llvm::PointerUnion<Decl *, DeclArgumentPack *>, 4>
216 /// \brief A mapping from local declarations that occur
217 /// within a template to their instantiations.
219 /// This mapping is used during instantiation to keep track of,
220 /// e.g., function parameter and variable declarations. For example,
224 /// template<typename T> T add(T x, T y) { return x + y; }
227 /// when we instantiate add<int>, we will introduce a mapping from
228 /// the ParmVarDecl for 'x' that occurs in the template to the
229 /// instantiated ParmVarDecl for 'x'.
231 /// For a parameter pack, the local instantiation scope may contain a
232 /// set of instantiated parameters. This is stored as a DeclArgumentPack
234 LocalDeclsMap LocalDecls;
236 /// \brief The set of argument packs we've allocated.
237 SmallVector<DeclArgumentPack *, 1> ArgumentPacks;
239 /// \brief The outer scope, which contains local variable
240 /// definitions from some other instantiation (that may not be
241 /// relevant to this particular scope).
242 LocalInstantiationScope *Outer;
244 /// \brief Whether we have already exited this scope.
247 /// \brief Whether to combine this scope with the outer scope, such that
248 /// lookup will search our outer scope.
249 bool CombineWithOuterScope;
251 /// \brief If non-NULL, the template parameter pack that has been
252 /// partially substituted per C++0x [temp.arg.explicit]p9.
253 NamedDecl *PartiallySubstitutedPack;
255 /// \brief If \c PartiallySubstitutedPack is non-null, the set of
256 /// explicitly-specified template arguments in that pack.
257 const TemplateArgument *ArgsInPartiallySubstitutedPack;
259 /// \brief If \c PartiallySubstitutedPack, the number of
260 /// explicitly-specified template arguments in
261 /// ArgsInPartiallySubstitutedPack.
262 unsigned NumArgsInPartiallySubstitutedPack;
264 // This class is non-copyable
265 LocalInstantiationScope(
266 const LocalInstantiationScope &) = delete;
267 void operator=(const LocalInstantiationScope &) = delete;
270 LocalInstantiationScope(Sema &SemaRef, bool CombineWithOuterScope = false)
271 : SemaRef(SemaRef), Outer(SemaRef.CurrentInstantiationScope),
272 Exited(false), CombineWithOuterScope(CombineWithOuterScope),
273 PartiallySubstitutedPack(nullptr)
275 SemaRef.CurrentInstantiationScope = this;
278 ~LocalInstantiationScope() {
282 const Sema &getSema() const { return SemaRef; }
284 /// \brief Exit this local instantiation scope early.
289 for (unsigned I = 0, N = ArgumentPacks.size(); I != N; ++I)
290 delete ArgumentPacks[I];
292 SemaRef.CurrentInstantiationScope = Outer;
296 /// \brief Clone this scope, and all outer scopes, down to the given
298 LocalInstantiationScope *cloneScopes(LocalInstantiationScope *Outermost) {
299 if (this == Outermost) return this;
301 // Save the current scope from SemaRef since the LocalInstantiationScope
302 // will overwrite it on construction
303 LocalInstantiationScope *oldScope = SemaRef.CurrentInstantiationScope;
305 LocalInstantiationScope *newScope =
306 new LocalInstantiationScope(SemaRef, CombineWithOuterScope);
308 newScope->Outer = nullptr;
310 newScope->Outer = Outer->cloneScopes(Outermost);
312 newScope->PartiallySubstitutedPack = PartiallySubstitutedPack;
313 newScope->ArgsInPartiallySubstitutedPack = ArgsInPartiallySubstitutedPack;
314 newScope->NumArgsInPartiallySubstitutedPack =
315 NumArgsInPartiallySubstitutedPack;
317 for (LocalDeclsMap::iterator I = LocalDecls.begin(), E = LocalDecls.end();
319 const Decl *D = I->first;
320 llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored =
321 newScope->LocalDecls[D];
322 if (I->second.is<Decl *>()) {
323 Stored = I->second.get<Decl *>();
325 DeclArgumentPack *OldPack = I->second.get<DeclArgumentPack *>();
326 DeclArgumentPack *NewPack = new DeclArgumentPack(*OldPack);
328 newScope->ArgumentPacks.push_back(NewPack);
331 // Restore the saved scope to SemaRef
332 SemaRef.CurrentInstantiationScope = oldScope;
336 /// \brief deletes the given scope, and all otuer scopes, down to the
337 /// given outermost scope.
338 static void deleteScopes(LocalInstantiationScope *Scope,
339 LocalInstantiationScope *Outermost) {
340 while (Scope && Scope != Outermost) {
341 LocalInstantiationScope *Out = Scope->Outer;
347 /// \brief Find the instantiation of the declaration D within the current
348 /// instantiation scope.
350 /// \param D The declaration whose instantiation we are searching for.
352 /// \returns A pointer to the declaration or argument pack of declarations
353 /// to which the declaration \c D is instantiated, if found. Otherwise,
355 llvm::PointerUnion<Decl *, DeclArgumentPack *> *
356 findInstantiationOf(const Decl *D);
358 void InstantiatedLocal(const Decl *D, Decl *Inst);
359 void InstantiatedLocalPackArg(const Decl *D, ParmVarDecl *Inst);
360 void MakeInstantiatedLocalArgPack(const Decl *D);
362 /// \brief Note that the given parameter pack has been partially substituted
363 /// via explicit specification of template arguments
364 /// (C++0x [temp.arg.explicit]p9).
366 /// \param Pack The parameter pack, which will always be a template
369 /// \param ExplicitArgs The explicitly-specified template arguments provided
370 /// for this parameter pack.
372 /// \param NumExplicitArgs The number of explicitly-specified template
373 /// arguments provided for this parameter pack.
374 void SetPartiallySubstitutedPack(NamedDecl *Pack,
375 const TemplateArgument *ExplicitArgs,
376 unsigned NumExplicitArgs);
378 /// \brief Reset the partially-substituted pack when it is no longer of
380 void ResetPartiallySubstitutedPack() {
381 assert(PartiallySubstitutedPack && "No partially-substituted pack");
382 PartiallySubstitutedPack = nullptr;
383 ArgsInPartiallySubstitutedPack = nullptr;
384 NumArgsInPartiallySubstitutedPack = 0;
387 /// \brief Retrieve the partially-substitued template parameter pack.
389 /// If there is no partially-substituted parameter pack, returns NULL.
391 getPartiallySubstitutedPack(const TemplateArgument **ExplicitArgs = nullptr,
392 unsigned *NumExplicitArgs = nullptr) const;
395 class TemplateDeclInstantiator
396 : public DeclVisitor<TemplateDeclInstantiator, Decl *>
399 Sema::ArgumentPackSubstitutionIndexRAII SubstIndex;
401 const MultiLevelTemplateArgumentList &TemplateArgs;
402 Sema::LateInstantiatedAttrVec* LateAttrs;
403 LocalInstantiationScope *StartingScope;
405 /// \brief A list of out-of-line class template partial
406 /// specializations that will need to be instantiated after the
407 /// enclosing class's instantiation is complete.
408 SmallVector<std::pair<ClassTemplateDecl *,
409 ClassTemplatePartialSpecializationDecl *>, 4>
410 OutOfLinePartialSpecs;
412 /// \brief A list of out-of-line variable template partial
413 /// specializations that will need to be instantiated after the
414 /// enclosing variable's instantiation is complete.
415 /// FIXME: Verify that this is needed.
417 std::pair<VarTemplateDecl *, VarTemplatePartialSpecializationDecl *>, 4>
418 OutOfLineVarPartialSpecs;
421 TemplateDeclInstantiator(Sema &SemaRef, DeclContext *Owner,
422 const MultiLevelTemplateArgumentList &TemplateArgs)
424 SubstIndex(SemaRef, SemaRef.ArgumentPackSubstitutionIndex),
425 Owner(Owner), TemplateArgs(TemplateArgs), LateAttrs(nullptr),
426 StartingScope(nullptr) {}
428 // Define all the decl visitors using DeclNodes.inc
429 #define DECL(DERIVED, BASE) \
430 Decl *Visit ## DERIVED ## Decl(DERIVED ## Decl *D);
431 #define ABSTRACT_DECL(DECL)
433 // Decls which never appear inside a class or function.
434 #define OBJCCONTAINER(DERIVED, BASE)
435 #define FILESCOPEASM(DERIVED, BASE)
436 #define IMPORT(DERIVED, BASE)
437 #define EXPORT(DERIVED, BASE)
438 #define LINKAGESPEC(DERIVED, BASE)
439 #define OBJCCOMPATIBLEALIAS(DERIVED, BASE)
440 #define OBJCMETHOD(DERIVED, BASE)
441 #define OBJCTYPEPARAM(DERIVED, BASE)
442 #define OBJCIVAR(DERIVED, BASE)
443 #define OBJCPROPERTY(DERIVED, BASE)
444 #define OBJCPROPERTYIMPL(DERIVED, BASE)
445 #define EMPTY(DERIVED, BASE)
447 // Decls which use special-case instantiation code.
448 #define BLOCK(DERIVED, BASE)
449 #define CAPTURED(DERIVED, BASE)
450 #define IMPLICITPARAM(DERIVED, BASE)
452 #include "clang/AST/DeclNodes.inc"
454 // A few supplemental visitor functions.
455 Decl *VisitCXXMethodDecl(CXXMethodDecl *D,
456 TemplateParameterList *TemplateParams,
457 bool IsClassScopeSpecialization = false);
458 Decl *VisitFunctionDecl(FunctionDecl *D,
459 TemplateParameterList *TemplateParams);
460 Decl *VisitDecl(Decl *D);
461 Decl *VisitVarDecl(VarDecl *D, bool InstantiatingVarTemplate,
462 ArrayRef<BindingDecl *> *Bindings = nullptr);
464 // Enable late instantiation of attributes. Late instantiated attributes
465 // will be stored in LA.
466 void enableLateAttributeInstantiation(Sema::LateInstantiatedAttrVec *LA) {
468 StartingScope = SemaRef.CurrentInstantiationScope;
471 // Disable late instantiation of attributes.
472 void disableLateAttributeInstantiation() {
474 StartingScope = nullptr;
477 LocalInstantiationScope *getStartingScope() const { return StartingScope; }
480 SmallVectorImpl<std::pair<ClassTemplateDecl *,
481 ClassTemplatePartialSpecializationDecl *> >
483 delayed_partial_spec_iterator;
485 typedef SmallVectorImpl<std::pair<
486 VarTemplateDecl *, VarTemplatePartialSpecializationDecl *> >::iterator
487 delayed_var_partial_spec_iterator;
489 /// \brief Return an iterator to the beginning of the set of
490 /// "delayed" partial specializations, which must be passed to
491 /// InstantiateClassTemplatePartialSpecialization once the class
492 /// definition has been completed.
493 delayed_partial_spec_iterator delayed_partial_spec_begin() {
494 return OutOfLinePartialSpecs.begin();
497 delayed_var_partial_spec_iterator delayed_var_partial_spec_begin() {
498 return OutOfLineVarPartialSpecs.begin();
501 /// \brief Return an iterator to the end of the set of
502 /// "delayed" partial specializations, which must be passed to
503 /// InstantiateClassTemplatePartialSpecialization once the class
504 /// definition has been completed.
505 delayed_partial_spec_iterator delayed_partial_spec_end() {
506 return OutOfLinePartialSpecs.end();
509 delayed_var_partial_spec_iterator delayed_var_partial_spec_end() {
510 return OutOfLineVarPartialSpecs.end();
513 // Helper functions for instantiating methods.
514 TypeSourceInfo *SubstFunctionType(FunctionDecl *D,
515 SmallVectorImpl<ParmVarDecl *> &Params);
516 bool InitFunctionInstantiation(FunctionDecl *New, FunctionDecl *Tmpl);
517 bool InitMethodInstantiation(CXXMethodDecl *New, CXXMethodDecl *Tmpl);
519 TemplateParameterList *
520 SubstTemplateParams(TemplateParameterList *List);
522 bool SubstQualifier(const DeclaratorDecl *OldDecl,
523 DeclaratorDecl *NewDecl);
524 bool SubstQualifier(const TagDecl *OldDecl,
527 Decl *VisitVarTemplateSpecializationDecl(
528 VarTemplateDecl *VarTemplate, VarDecl *FromVar, void *InsertPos,
529 const TemplateArgumentListInfo &TemplateArgsInfo,
530 ArrayRef<TemplateArgument> Converted);
532 Decl *InstantiateTypedefNameDecl(TypedefNameDecl *D, bool IsTypeAlias);
533 ClassTemplatePartialSpecializationDecl *
534 InstantiateClassTemplatePartialSpecialization(
535 ClassTemplateDecl *ClassTemplate,
536 ClassTemplatePartialSpecializationDecl *PartialSpec);
537 VarTemplatePartialSpecializationDecl *
538 InstantiateVarTemplatePartialSpecialization(
539 VarTemplateDecl *VarTemplate,
540 VarTemplatePartialSpecializationDecl *PartialSpec);
541 void InstantiateEnumDefinition(EnumDecl *Enum, EnumDecl *Pattern);
545 Decl *instantiateUnresolvedUsingDecl(T *D,
546 bool InstantiatingPackElement = false);
550 #endif // LLVM_CLANG_SEMA_TEMPLATE_H