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;
51 /// \brief Construct an empty set of template argument lists.
52 MultiLevelTemplateArgumentList() { }
54 /// \brief Construct a single-level template argument list.
56 MultiLevelTemplateArgumentList(const TemplateArgumentList &TemplateArgs) {
57 addOuterTemplateArguments(&TemplateArgs);
60 /// \brief Determine the number of levels in this template argument
62 unsigned getNumLevels() const { return TemplateArgumentLists.size(); }
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];
71 /// \brief Determine whether there is a non-NULL template argument at the
72 /// given depth and index.
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());
78 if (Index >= TemplateArgumentLists[getNumLevels() - Depth - 1].size())
81 return !(*this)(Depth, Index).isNull();
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])
94 /// \brief Add a new outermost level to the multi-level template argument
96 void addOuterTemplateArguments(const TemplateArgumentList *TemplateArgs) {
97 addOuterTemplateArguments(ArgList(TemplateArgs->data(),
98 TemplateArgs->size()));
101 /// \brief Add a new outmost level to the multi-level template argument
103 void addOuterTemplateArguments(ArgList Args) {
104 TemplateArgumentLists.push_back(Args);
107 /// \brief Retrieve the innermost template argument list.
108 const ArgList &getInnermost() const {
109 return TemplateArgumentLists.front();
113 /// \brief The context in which partial ordering of function templates occurs.
115 /// \brief Partial ordering of function templates for a function call.
117 /// \brief Partial ordering of function templates for a call to a
118 /// conversion function.
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.
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 {
133 TemplatePartialOrderingContext(TPOC Value) : Value(Value) {}
134 operator TPOC() const { return Value; }
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;
145 DeducedTemplateArgument()
146 : TemplateArgument(), DeducedFromArrayBound(false) { }
148 DeducedTemplateArgument(const TemplateArgument &Arg,
149 bool DeducedFromArrayBound = false)
150 : TemplateArgument(Arg), DeducedFromArrayBound(DeducedFromArrayBound) { }
152 /// \brief Construct an integral non-type template argument that
153 /// has been deduced, possibly from an array bound.
154 DeducedTemplateArgument(ASTContext &Ctx,
155 const llvm::APSInt &Value,
157 bool DeducedFromArrayBound)
158 : TemplateArgument(Ctx, Value, ValueType),
159 DeducedFromArrayBound(DeducedFromArrayBound) { }
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; }
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;
172 /// \brief A stack-allocated class that identifies which local
173 /// variable declaration instantiations are present in this scope.
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 {
180 /// \brief A set of declarations.
181 typedef SmallVector<Decl *, 4> DeclArgumentPack;
184 /// \brief Reference to the semantic analysis that is performing
185 /// this template instantiation.
188 typedef llvm::SmallDenseMap<
189 const Decl *, llvm::PointerUnion<Decl *, DeclArgumentPack *>, 4>
192 /// \brief A mapping from local declarations that occur
193 /// within a template to their instantiations.
195 /// This mapping is used during instantiation to keep track of,
196 /// e.g., function parameter and variable declarations. For example,
200 /// template<typename T> T add(T x, T y) { return x + y; }
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'.
207 /// For a parameter pack, the local instantiation scope may contain a
208 /// set of instantiated parameters. This is stored as a DeclArgumentPack
210 LocalDeclsMap LocalDecls;
212 /// \brief The set of argument packs we've allocated.
213 SmallVector<DeclArgumentPack *, 1> ArgumentPacks;
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;
220 /// \brief Whether we have already exited this scope.
223 /// \brief Whether to combine this scope with the outer scope, such that
224 /// lookup will search our outer scope.
225 bool CombineWithOuterScope;
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;
231 /// \brief If \c PartiallySubstitutedPack is non-null, the set of
232 /// explicitly-specified template arguments in that pack.
233 const TemplateArgument *ArgsInPartiallySubstitutedPack;
235 /// \brief If \c PartiallySubstitutedPack, the number of
236 /// explicitly-specified template arguments in
237 /// ArgsInPartiallySubstitutedPack.
238 unsigned NumArgsInPartiallySubstitutedPack;
240 // This class is non-copyable
241 LocalInstantiationScope(
242 const LocalInstantiationScope &) LLVM_DELETED_FUNCTION;
243 void operator=(const LocalInstantiationScope &) LLVM_DELETED_FUNCTION;
246 LocalInstantiationScope(Sema &SemaRef, bool CombineWithOuterScope = false)
247 : SemaRef(SemaRef), Outer(SemaRef.CurrentInstantiationScope),
248 Exited(false), CombineWithOuterScope(CombineWithOuterScope),
249 PartiallySubstitutedPack(nullptr)
251 SemaRef.CurrentInstantiationScope = this;
254 ~LocalInstantiationScope() {
258 const Sema &getSema() const { return SemaRef; }
260 /// \brief Exit this local instantiation scope early.
265 for (unsigned I = 0, N = ArgumentPacks.size(); I != N; ++I)
266 delete ArgumentPacks[I];
268 SemaRef.CurrentInstantiationScope = Outer;
272 /// \brief Clone this scope, and all outer scopes, down to the given
274 LocalInstantiationScope *cloneScopes(LocalInstantiationScope *Outermost) {
275 if (this == Outermost) return this;
277 // Save the current scope from SemaRef since the LocalInstantiationScope
278 // will overwrite it on construction
279 LocalInstantiationScope *oldScope = SemaRef.CurrentInstantiationScope;
281 LocalInstantiationScope *newScope =
282 new LocalInstantiationScope(SemaRef, CombineWithOuterScope);
284 newScope->Outer = nullptr;
286 newScope->Outer = Outer->cloneScopes(Outermost);
288 newScope->PartiallySubstitutedPack = PartiallySubstitutedPack;
289 newScope->ArgsInPartiallySubstitutedPack = ArgsInPartiallySubstitutedPack;
290 newScope->NumArgsInPartiallySubstitutedPack =
291 NumArgsInPartiallySubstitutedPack;
293 for (LocalDeclsMap::iterator I = LocalDecls.begin(), E = LocalDecls.end();
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 *>();
301 DeclArgumentPack *OldPack = I->second.get<DeclArgumentPack *>();
302 DeclArgumentPack *NewPack = new DeclArgumentPack(*OldPack);
304 newScope->ArgumentPacks.push_back(NewPack);
307 // Restore the saved scope to SemaRef
308 SemaRef.CurrentInstantiationScope = oldScope;
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;
323 /// \brief Find the instantiation of the declaration D within the current
324 /// instantiation scope.
326 /// \param D The declaration whose instantiation we are searching for.
328 /// \returns A pointer to the declaration or argument pack of declarations
329 /// to which the declaration \c D is instantiated, if found. Otherwise,
331 llvm::PointerUnion<Decl *, DeclArgumentPack *> *
332 findInstantiationOf(const Decl *D);
334 void InstantiatedLocal(const Decl *D, Decl *Inst);
335 void InstantiatedLocalPackArg(const Decl *D, Decl *Inst);
336 void MakeInstantiatedLocalArgPack(const Decl *D);
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).
342 /// \param Pack The parameter pack, which will always be a template
345 /// \param ExplicitArgs The explicitly-specified template arguments provided
346 /// for this parameter pack.
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);
354 /// \brief Reset the partially-substituted pack when it is no longer of
356 void ResetPartiallySubstitutedPack() {
357 assert(PartiallySubstitutedPack && "No partially-substituted pack");
358 PartiallySubstitutedPack = nullptr;
359 ArgsInPartiallySubstitutedPack = nullptr;
360 NumArgsInPartiallySubstitutedPack = 0;
363 /// \brief Retrieve the partially-substitued template parameter pack.
365 /// If there is no partially-substituted parameter pack, returns NULL.
367 getPartiallySubstitutedPack(const TemplateArgument **ExplicitArgs = nullptr,
368 unsigned *NumExplicitArgs = nullptr) const;
371 class TemplateDeclInstantiator
372 : public DeclVisitor<TemplateDeclInstantiator, Decl *>
375 Sema::ArgumentPackSubstitutionIndexRAII SubstIndex;
377 const MultiLevelTemplateArgumentList &TemplateArgs;
378 Sema::LateInstantiatedAttrVec* LateAttrs;
379 LocalInstantiationScope *StartingScope;
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;
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.
393 std::pair<VarTemplateDecl *, VarTemplatePartialSpecializationDecl *>, 4>
394 OutOfLineVarPartialSpecs;
397 TemplateDeclInstantiator(Sema &SemaRef, DeclContext *Owner,
398 const MultiLevelTemplateArgumentList &TemplateArgs)
400 SubstIndex(SemaRef, SemaRef.ArgumentPackSubstitutionIndex),
401 Owner(Owner), TemplateArgs(TemplateArgs), LateAttrs(nullptr),
402 StartingScope(nullptr) {}
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)
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 OBJCIVAR(DERIVED, BASE)
417 #define OBJCPROPERTY(DERIVED, BASE)
418 #define OBJCPROPERTYIMPL(DERIVED, BASE)
419 #define EMPTY(DERIVED, BASE)
421 // Decls which use special-case instantiation code.
422 #define BLOCK(DERIVED, BASE)
423 #define CAPTURED(DERIVED, BASE)
424 #define IMPLICITPARAM(DERIVED, BASE)
426 #include "clang/AST/DeclNodes.inc"
428 // A few supplemental visitor functions.
429 Decl *VisitCXXMethodDecl(CXXMethodDecl *D,
430 TemplateParameterList *TemplateParams,
431 bool IsClassScopeSpecialization = false);
432 Decl *VisitFunctionDecl(FunctionDecl *D,
433 TemplateParameterList *TemplateParams);
434 Decl *VisitDecl(Decl *D);
435 Decl *VisitVarDecl(VarDecl *D, bool InstantiatingVarTemplate);
437 // Enable late instantiation of attributes. Late instantiated attributes
438 // will be stored in LA.
439 void enableLateAttributeInstantiation(Sema::LateInstantiatedAttrVec *LA) {
441 StartingScope = SemaRef.CurrentInstantiationScope;
444 // Disable late instantiation of attributes.
445 void disableLateAttributeInstantiation() {
447 StartingScope = nullptr;
450 LocalInstantiationScope *getStartingScope() const { return StartingScope; }
453 SmallVectorImpl<std::pair<ClassTemplateDecl *,
454 ClassTemplatePartialSpecializationDecl *> >
456 delayed_partial_spec_iterator;
458 typedef SmallVectorImpl<std::pair<
459 VarTemplateDecl *, VarTemplatePartialSpecializationDecl *> >::iterator
460 delayed_var_partial_spec_iterator;
462 /// \brief Return an iterator to the beginning of the set of
463 /// "delayed" partial specializations, which must be passed to
464 /// InstantiateClassTemplatePartialSpecialization once the class
465 /// definition has been completed.
466 delayed_partial_spec_iterator delayed_partial_spec_begin() {
467 return OutOfLinePartialSpecs.begin();
470 delayed_var_partial_spec_iterator delayed_var_partial_spec_begin() {
471 return OutOfLineVarPartialSpecs.begin();
474 /// \brief Return an iterator to the end of the set of
475 /// "delayed" partial specializations, which must be passed to
476 /// InstantiateClassTemplatePartialSpecialization once the class
477 /// definition has been completed.
478 delayed_partial_spec_iterator delayed_partial_spec_end() {
479 return OutOfLinePartialSpecs.end();
482 delayed_var_partial_spec_iterator delayed_var_partial_spec_end() {
483 return OutOfLineVarPartialSpecs.end();
486 // Helper functions for instantiating methods.
487 TypeSourceInfo *SubstFunctionType(FunctionDecl *D,
488 SmallVectorImpl<ParmVarDecl *> &Params);
489 bool InitFunctionInstantiation(FunctionDecl *New, FunctionDecl *Tmpl);
490 bool InitMethodInstantiation(CXXMethodDecl *New, CXXMethodDecl *Tmpl);
492 TemplateParameterList *
493 SubstTemplateParams(TemplateParameterList *List);
495 bool SubstQualifier(const DeclaratorDecl *OldDecl,
496 DeclaratorDecl *NewDecl);
497 bool SubstQualifier(const TagDecl *OldDecl,
500 Decl *VisitVarTemplateSpecializationDecl(
501 VarTemplateDecl *VarTemplate, VarDecl *FromVar, void *InsertPos,
502 const TemplateArgumentListInfo &TemplateArgsInfo,
503 ArrayRef<TemplateArgument> Converted);
505 Decl *InstantiateTypedefNameDecl(TypedefNameDecl *D, bool IsTypeAlias);
506 ClassTemplatePartialSpecializationDecl *
507 InstantiateClassTemplatePartialSpecialization(
508 ClassTemplateDecl *ClassTemplate,
509 ClassTemplatePartialSpecializationDecl *PartialSpec);
510 VarTemplatePartialSpecializationDecl *
511 InstantiateVarTemplatePartialSpecialization(
512 VarTemplateDecl *VarTemplate,
513 VarTemplatePartialSpecializationDecl *PartialSpec);
514 void InstantiateEnumDefinition(EnumDecl *Enum, EnumDecl *Pattern);
518 #endif // LLVM_CLANG_SEMA_TEMPLATE_H