Template.h source code [clang_source_code/include/clang/Sema/Template.h]

1	//===- SemaTemplate.h - C++ Templates ---------------------------- C++ --===//
2	//
3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4	// See https://llvm.org/LICENSE.txt for license information.
5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6	//===----------------------------------------------------------------------===//
7	//
8	// This file provides types used in the semantic analysis of C++ templates.
9	//
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/AST/TemplateBase.h"
18	#include "clang/AST/Type.h"
19	#include "clang/Basic/LLVM.h"
20	#include "clang/Sema/Sema.h"
21	#include "llvm/ADT/ArrayRef.h"
22	#include "llvm/ADT/DenseMap.h"
23	#include "llvm/ADT/PointerUnion.h"
24	#include "llvm/ADT/SmallVector.h"
25	#include <cassert>
26	#include <utility>
27
28	namespace clang {
29
30	class ASTContext;
31	class BindingDecl;
32	class CXXMethodDecl;
33	class Decl;
34	class DeclaratorDecl;
35	class DeclContext;
36	class EnumDecl;
37	class FunctionDecl;
38	class NamedDecl;
39	class ParmVarDecl;
40	class TagDecl;
41	class TypedefNameDecl;
42	class TypeSourceInfo;
43	class VarDecl;
44
45	/// Data structure that captures multiple levels of template argument
46	/// lists for use in template instantiation.
47	///
48	/// Multiple levels of template arguments occur when instantiating the
49	/// definitions of member templates. For example:
50	///
51	/// \code
52	/// template<typename T>
53	/// struct X {
54	/// template<T Value>
55	/// struct Y {
56	/// void f();
57	/// };
58	/// };
59	/// \endcode
60	///
61	/// When instantiating X<int>::Y<17>::f, the multi-level template argument
62	/// list will contain a template argument list (int) at depth 0 and a
63	/// template argument list (17) at depth 1.
64	class MultiLevelTemplateArgumentList {
65	/// The template argument list at a certain template depth
66	using ArgList = ArrayRef<TemplateArgument>;
67
68	/// The template argument lists, stored from the innermost template
69	/// argument list (first) to the outermost template argument list (last).
70	SmallVector<ArgList, 4> TemplateArgumentLists;
71
72	/// The number of outer levels of template arguments that are not
73	/// being substituted.
74	unsigned NumRetainedOuterLevels = 0;
75
76	public:
77	/// Construct an empty set of template argument lists.
78	MultiLevelTemplateArgumentList() = default;
79
80	/// Construct a single-level template argument list.
81	explicit
82	MultiLevelTemplateArgumentList(const TemplateArgumentList &TemplateArgs) {
83	addOuterTemplateArguments(&TemplateArgs);
84	}
85
86	/// Determine the number of levels in this template argument
87	/// list.
88	unsigned getNumLevels() const {
89	return TemplateArgumentLists.size() + NumRetainedOuterLevels;
90	}
91
92	/// Determine the number of substituted levels in this template
93	/// argument list.
94	unsigned getNumSubstitutedLevels() const {
95	return TemplateArgumentLists.size();
96	}
97
98	/// Retrieve the template argument at a given depth and index.
99	const TemplateArgument &operator()(unsigned Depth, unsigned Index) const {
100	assert(NumRetainedOuterLevels <= Depth && Depth < getNumLevels());
101	assert(Index < TemplateArgumentLists[getNumLevels() - Depth - 1].size());
102	return TemplateArgumentLists[getNumLevels() - Depth - 1][Index];
103	}
104
105	/// Determine whether there is a non-NULL template argument at the
106	/// given depth and index.
107	///
108	/// There must exist a template argument list at the given depth.
109	bool hasTemplateArgument(unsigned Depth, unsigned Index) const {
110	assert(Depth < getNumLevels());
111
112	if (Depth < NumRetainedOuterLevels)
113	return false;
114
115	if (Index >= TemplateArgumentLists[getNumLevels() - Depth - 1].size())
116	return false;
117
118	return !(*this)(Depth, Index).isNull();
119	}
120
121	/// Clear out a specific template argument.
122	void setArgument(unsigned Depth, unsigned Index,
123	TemplateArgument Arg) {
124	assert(NumRetainedOuterLevels <= Depth && Depth < getNumLevels());
125	assert(Index < TemplateArgumentLists[getNumLevels() - Depth - 1].size());
126	const_cast<TemplateArgument&>(
127	TemplateArgumentLists[getNumLevels() - Depth - 1][Index])
128	= Arg;
129	}
130
131	/// Add a new outermost level to the multi-level template argument
132	/// list.
133	void addOuterTemplateArguments(const TemplateArgumentList *TemplateArgs) {
134	addOuterTemplateArguments(ArgList(TemplateArgs->data(),
135	TemplateArgs->size()));
136	}
137
138	/// Add a new outmost level to the multi-level template argument
139	/// list.
140	void addOuterTemplateArguments(ArgList Args) {
141	(0) . __assert_fail ("!NumRetainedOuterLevels && \"substituted args outside retained args?\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Sema/Template.h", 142, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(!NumRetainedOuterLevels &&
142	(0) . __assert_fail ("!NumRetainedOuterLevels && \"substituted args outside retained args?\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Sema/Template.h", 142, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> "substituted args outside retained args?");
143	TemplateArgumentLists.push_back(Args);
144	}
145
146	/// Add an outermost level that we are not substituting. We have no
147	/// arguments at this level, and do not remove it from the depth of inner
148	/// template parameters that we instantiate.
149	void addOuterRetainedLevel() {
150	++NumRetainedOuterLevels;
151	}
152
153	/// Retrieve the innermost template argument list.
154	const ArgList &getInnermost() const {
155	return TemplateArgumentLists.front();
156	}
157	};
158
159	/// The context in which partial ordering of function templates occurs.
160	enum TPOC {
161	/// Partial ordering of function templates for a function call.
162	TPOC_Call,
163
164	/// Partial ordering of function templates for a call to a
165	/// conversion function.
166	TPOC_Conversion,
167
168	/// Partial ordering of function templates in other contexts, e.g.,
169	/// taking the address of a function template or matching a function
170	/// template specialization to a function template.
171	TPOC_Other
172	};
173
174	// This is lame but unavoidable in a world without forward
175	// declarations of enums. The alternatives are to either pollute
176	// Sema.h (by including this file) or sacrifice type safety (by
177	// making Sema.h declare things as enums).
178	class TemplatePartialOrderingContext {
179	TPOC Value;
180
181	public:
182	TemplatePartialOrderingContext(TPOC Value) : Value(Value) {}
183
184	operator TPOC() const { return Value; }
185	};
186
187	/// Captures a template argument whose value has been deduced
188	/// via c++ template argument deduction.
189	class DeducedTemplateArgument : public TemplateArgument {
190	/// For a non-type template argument, whether the value was
191	/// deduced from an array bound.
192	bool DeducedFromArrayBound = false;
193
194	public:
195	DeducedTemplateArgument() = default;
196
197	DeducedTemplateArgument(const TemplateArgument &Arg,
198	bool DeducedFromArrayBound = false)
199	: TemplateArgument(Arg), DeducedFromArrayBound(DeducedFromArrayBound) {}
200
201	/// Construct an integral non-type template argument that
202	/// has been deduced, possibly from an array bound.
203	DeducedTemplateArgument(ASTContext &Ctx,
204	const llvm::APSInt &Value,
205	QualType ValueType,
206	bool DeducedFromArrayBound)
207	: TemplateArgument(Ctx, Value, ValueType),
208	DeducedFromArrayBound(DeducedFromArrayBound) {}
209
210	/// For a non-type template argument, determine whether the
211	/// template argument was deduced from an array bound.
212	bool wasDeducedFromArrayBound() const { return DeducedFromArrayBound; }
213
214	/// Specify whether the given non-type template argument
215	/// was deduced from an array bound.
216	void setDeducedFromArrayBound(bool Deduced) {
217	DeducedFromArrayBound = Deduced;
218	}
219	};
220
221	/// A stack-allocated class that identifies which local
222	/// variable declaration instantiations are present in this scope.
223	///
224	/// A new instance of this class type will be created whenever we
225	/// instantiate a new function declaration, which will have its own
226	/// set of parameter declarations.
227	class LocalInstantiationScope {
228	public:
229	/// A set of declarations.
230	using DeclArgumentPack = SmallVector<ParmVarDecl *, 4>;
231
232	private:
233	/// Reference to the semantic analysis that is performing
234	/// this template instantiation.
235	Sema &SemaRef;
236
237	using LocalDeclsMap =
238	llvm::SmallDenseMap<const Decl *,
239	llvm::PointerUnion<Decl , DeclArgumentPack >, 4>;
240
241	/// A mapping from local declarations that occur
242	/// within a template to their instantiations.
243	///
244	/// This mapping is used during instantiation to keep track of,
245	/// e.g., function parameter and variable declarations. For example,
246	/// given:
247	///
248	/// \code
249	/// template<typename T> T add(T x, T y) { return x + y; }
250	/// \endcode
251	///
252	/// when we instantiate add<int>, we will introduce a mapping from
253	/// the ParmVarDecl for 'x' that occurs in the template to the
254	/// instantiated ParmVarDecl for 'x'.
255	///
256	/// For a parameter pack, the local instantiation scope may contain a
257	/// set of instantiated parameters. This is stored as a DeclArgumentPack
258	/// pointer.
259	LocalDeclsMap LocalDecls;
260
261	/// The set of argument packs we've allocated.
262	SmallVector<DeclArgumentPack *, 1> ArgumentPacks;
263
264	/// The outer scope, which contains local variable
265	/// definitions from some other instantiation (that may not be
266	/// relevant to this particular scope).
267	LocalInstantiationScope *Outer;
268
269	/// Whether we have already exited this scope.
270	bool Exited = false;
271
272	/// Whether to combine this scope with the outer scope, such that
273	/// lookup will search our outer scope.
274	bool CombineWithOuterScope;
275
276	/// If non-NULL, the template parameter pack that has been
277	/// partially substituted per C++0x [temp.arg.explicit]p9.
278	NamedDecl *PartiallySubstitutedPack = nullptr;
279
280	/// If \c PartiallySubstitutedPack is non-null, the set of
281	/// explicitly-specified template arguments in that pack.
282	const TemplateArgument *ArgsInPartiallySubstitutedPack;
283
284	/// If \c PartiallySubstitutedPack, the number of
285	/// explicitly-specified template arguments in
286	/// ArgsInPartiallySubstitutedPack.
287	unsigned NumArgsInPartiallySubstitutedPack;
288
289	public:
290	LocalInstantiationScope(Sema &SemaRef, bool CombineWithOuterScope = false)
291	: SemaRef(SemaRef), Outer(SemaRef.CurrentInstantiationScope),
292	CombineWithOuterScope(CombineWithOuterScope) {
293	SemaRef.CurrentInstantiationScope = this;
294	}
295
296	LocalInstantiationScope(const LocalInstantiationScope &) = delete;
297	LocalInstantiationScope &
298	operator=(const LocalInstantiationScope &) = delete;
299
300	~LocalInstantiationScope() {
301	Exit();
302	}
303
304	const Sema &getSema() const { return SemaRef; }
305
306	/// Exit this local instantiation scope early.
307	void Exit() {
308	if (Exited)
309	return;
310
311	for (unsigned I = 0, N = ArgumentPacks.size(); I != N; ++I)
312	delete ArgumentPacks[I];
313
314	SemaRef.CurrentInstantiationScope = Outer;
315	Exited = true;
316	}
317
318	/// Clone this scope, and all outer scopes, down to the given
319	/// outermost scope.
320	LocalInstantiationScope cloneScopes(LocalInstantiationScope Outermost) {
321	if (this == Outermost) return this;
322
323	// Save the current scope from SemaRef since the LocalInstantiationScope
324	// will overwrite it on construction
325	LocalInstantiationScope *oldScope = SemaRef.CurrentInstantiationScope;
326
327	LocalInstantiationScope *newScope =
328	new LocalInstantiationScope(SemaRef, CombineWithOuterScope);
329
330	newScope->Outer = nullptr;
331	if (Outer)
332	newScope->Outer = Outer->cloneScopes(Outermost);
333
334	newScope->PartiallySubstitutedPack = PartiallySubstitutedPack;
335	newScope->ArgsInPartiallySubstitutedPack = ArgsInPartiallySubstitutedPack;
336	newScope->NumArgsInPartiallySubstitutedPack =
337	NumArgsInPartiallySubstitutedPack;
338
339	for (LocalDeclsMap::iterator I = LocalDecls.begin(), E = LocalDecls.end();
340	I != E; ++I) {
341	const Decl *D = I->first;
342	llvm::PointerUnion<Decl , DeclArgumentPack > &Stored =
343	newScope->LocalDecls[D];
344	if (I->second.is<Decl *>()) {
345	Stored = I->second.get<Decl *>();
346	} else {
347	DeclArgumentPack OldPack = I->second.get<DeclArgumentPack >();
348	DeclArgumentPack NewPack = new DeclArgumentPack(OldPack);
349	Stored = NewPack;
350	newScope->ArgumentPacks.push_back(NewPack);
351	}
352	}
353	// Restore the saved scope to SemaRef
354	SemaRef.CurrentInstantiationScope = oldScope;
355	return newScope;
356	}
357
358	/// deletes the given scope, and all otuer scopes, down to the
359	/// given outermost scope.
360	static void deleteScopes(LocalInstantiationScope *Scope,
361	LocalInstantiationScope *Outermost) {
362	while (Scope && Scope != Outermost) {
363	LocalInstantiationScope *Out = Scope->Outer;
364	delete Scope;
365	Scope = Out;
366	}
367	}
368
369	/// Find the instantiation of the declaration D within the current
370	/// instantiation scope.
371	///
372	/// \param D The declaration whose instantiation we are searching for.
373	///
374	/// \returns A pointer to the declaration or argument pack of declarations
375	/// to which the declaration \c D is instantiated, if found. Otherwise,
376	/// returns NULL.
377	llvm::PointerUnion<Decl , DeclArgumentPack > *
378	findInstantiationOf(const Decl *D);
379
380	void InstantiatedLocal(const Decl D, Decl Inst);
381	void InstantiatedLocalPackArg(const Decl D, ParmVarDecl Inst);
382	void MakeInstantiatedLocalArgPack(const Decl *D);
383
384	/// Note that the given parameter pack has been partially substituted
385	/// via explicit specification of template arguments
386	/// (C++0x [temp.arg.explicit]p9).
387	///
388	/// \param Pack The parameter pack, which will always be a template
389	/// parameter pack.
390	///
391	/// \param ExplicitArgs The explicitly-specified template arguments provided
392	/// for this parameter pack.
393	///
394	/// \param NumExplicitArgs The number of explicitly-specified template
395	/// arguments provided for this parameter pack.
396	void SetPartiallySubstitutedPack(NamedDecl *Pack,
397	const TemplateArgument *ExplicitArgs,
398	unsigned NumExplicitArgs);
399
400	/// Reset the partially-substituted pack when it is no longer of
401	/// interest.
402	void ResetPartiallySubstitutedPack() {
403	(0) . __assert_fail ("PartiallySubstitutedPack && \"No partially-substituted pack\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Sema/Template.h", 403, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(PartiallySubstitutedPack && "No partially-substituted pack");
404	PartiallySubstitutedPack = nullptr;
405	ArgsInPartiallySubstitutedPack = nullptr;
406	NumArgsInPartiallySubstitutedPack = 0;
407	}
408
409	/// Retrieve the partially-substitued template parameter pack.
410	///
411	/// If there is no partially-substituted parameter pack, returns NULL.
412	NamedDecl *
413	getPartiallySubstitutedPack(const TemplateArgument **ExplicitArgs = nullptr,
414	unsigned *NumExplicitArgs = nullptr) const;
415	};
416
417	class TemplateDeclInstantiator
418	: public DeclVisitor<TemplateDeclInstantiator, Decl *>
419	{
420	Sema &SemaRef;
421	Sema::ArgumentPackSubstitutionIndexRAII SubstIndex;
422	DeclContext *Owner;
423	const MultiLevelTemplateArgumentList &TemplateArgs;
424	Sema::LateInstantiatedAttrVec* LateAttrs = nullptr;
425	LocalInstantiationScope *StartingScope = nullptr;
426
427	/// A list of out-of-line class template partial
428	/// specializations that will need to be instantiated after the
429	/// enclosing class's instantiation is complete.
430	SmallVector<std::pair<ClassTemplateDecl *,
431	ClassTemplatePartialSpecializationDecl *>, 4>
432	OutOfLinePartialSpecs;
433
434	/// A list of out-of-line variable template partial
435	/// specializations that will need to be instantiated after the
436	/// enclosing variable's instantiation is complete.
437	/// FIXME: Verify that this is needed.
438	SmallVector<
439	std::pair<VarTemplateDecl , VarTemplatePartialSpecializationDecl >, 4>
440	OutOfLineVarPartialSpecs;
441
442	public:
443	TemplateDeclInstantiator(Sema &SemaRef, DeclContext *Owner,
444	const MultiLevelTemplateArgumentList &TemplateArgs)
445	: SemaRef(SemaRef),
446	SubstIndex(SemaRef, SemaRef.ArgumentPackSubstitutionIndex),
447	Owner(Owner), TemplateArgs(TemplateArgs) {}
448
449	// Define all the decl visitors using DeclNodes.inc
450	#define DECL(DERIVED, BASE) \
451	Decl Visit ## DERIVED ## Decl(DERIVED ## Decl D);
452	#define ABSTRACT_DECL(DECL)
453
454	// Decls which never appear inside a class or function.
455	#define OBJCCONTAINER(DERIVED, BASE)
456	#define FILESCOPEASM(DERIVED, BASE)
457	#define IMPORT(DERIVED, BASE)
458	#define EXPORT(DERIVED, BASE)
459	#define LINKAGESPEC(DERIVED, BASE)
460	#define OBJCCOMPATIBLEALIAS(DERIVED, BASE)
461	#define OBJCMETHOD(DERIVED, BASE)
462	#define OBJCTYPEPARAM(DERIVED, BASE)
463	#define OBJCIVAR(DERIVED, BASE)
464	#define OBJCPROPERTY(DERIVED, BASE)
465	#define OBJCPROPERTYIMPL(DERIVED, BASE)
466	#define EMPTY(DERIVED, BASE)
467
468	// Decls which use special-case instantiation code.
469	#define BLOCK(DERIVED, BASE)
470	#define CAPTURED(DERIVED, BASE)
471	#define IMPLICITPARAM(DERIVED, BASE)
472
473	#include "clang/AST/DeclNodes.inc"
474
475	// A few supplemental visitor functions.
476	Decl VisitCXXMethodDecl(CXXMethodDecl D,
477	TemplateParameterList *TemplateParams,
478	bool IsClassScopeSpecialization = false);
479	Decl VisitFunctionDecl(FunctionDecl D,
480	TemplateParameterList *TemplateParams);
481	Decl VisitDecl(Decl D);
482	Decl VisitVarDecl(VarDecl D, bool InstantiatingVarTemplate,
483	ArrayRef<BindingDecl > Bindings = nullptr);
484
485	// Enable late instantiation of attributes. Late instantiated attributes
486	// will be stored in LA.
487	void enableLateAttributeInstantiation(Sema::LateInstantiatedAttrVec *LA) {
488	LateAttrs = LA;
489	StartingScope = SemaRef.CurrentInstantiationScope;
490	}
491
492	// Disable late instantiation of attributes.
493	void disableLateAttributeInstantiation() {
494	LateAttrs = nullptr;
495	StartingScope = nullptr;
496	}
497
498	LocalInstantiationScope *getStartingScope() const { return StartingScope; }
499
500	using delayed_partial_spec_iterator = SmallVectorImpl<std::pair<
501	ClassTemplateDecl , ClassTemplatePartialSpecializationDecl >>::iterator;
502
503	using delayed_var_partial_spec_iterator = SmallVectorImpl<std::pair<
504	VarTemplateDecl , VarTemplatePartialSpecializationDecl >>::iterator;
505
506	/// Return an iterator to the beginning of the set of
507	/// "delayed" partial specializations, which must be passed to
508	/// InstantiateClassTemplatePartialSpecialization once the class
509	/// definition has been completed.
510	delayed_partial_spec_iterator delayed_partial_spec_begin() {
511	return OutOfLinePartialSpecs.begin();
512	}
513
514	delayed_var_partial_spec_iterator delayed_var_partial_spec_begin() {
515	return OutOfLineVarPartialSpecs.begin();
516	}
517
518	/// Return an iterator to the end of the set of
519	/// "delayed" partial specializations, which must be passed to
520	/// InstantiateClassTemplatePartialSpecialization once the class
521	/// definition has been completed.
522	delayed_partial_spec_iterator delayed_partial_spec_end() {
523	return OutOfLinePartialSpecs.end();
524	}
525
526	delayed_var_partial_spec_iterator delayed_var_partial_spec_end() {
527	return OutOfLineVarPartialSpecs.end();
528	}
529
530	// Helper functions for instantiating methods.
531	TypeSourceInfo SubstFunctionType(FunctionDecl D,
532	SmallVectorImpl<ParmVarDecl *> &Params);
533	bool InitFunctionInstantiation(FunctionDecl New, FunctionDecl Tmpl);
534	bool InitMethodInstantiation(CXXMethodDecl New, CXXMethodDecl Tmpl);
535
536	TemplateParameterList *
537	SubstTemplateParams(TemplateParameterList *List);
538
539	bool SubstQualifier(const DeclaratorDecl *OldDecl,
540	DeclaratorDecl *NewDecl);
541	bool SubstQualifier(const TagDecl *OldDecl,
542	TagDecl *NewDecl);
543
544	Decl *VisitVarTemplateSpecializationDecl(
545	VarTemplateDecl VarTemplate, VarDecl FromVar, void *InsertPos,
546	const TemplateArgumentListInfo &TemplateArgsInfo,
547	ArrayRef<TemplateArgument> Converted);
548
549	Decl InstantiateTypedefNameDecl(TypedefNameDecl D, bool IsTypeAlias);
550	ClassTemplatePartialSpecializationDecl *
551	InstantiateClassTemplatePartialSpecialization(
552	ClassTemplateDecl *ClassTemplate,
553	ClassTemplatePartialSpecializationDecl *PartialSpec);
554	VarTemplatePartialSpecializationDecl *
555	InstantiateVarTemplatePartialSpecialization(
556	VarTemplateDecl *VarTemplate,
557	VarTemplatePartialSpecializationDecl *PartialSpec);
558	void InstantiateEnumDefinition(EnumDecl Enum, EnumDecl Pattern);
559
560	private:
561	template<typename T>
562	Decl instantiateUnresolvedUsingDecl(T D,
563	bool InstantiatingPackElement = false);
564	};
565
566	} // namespace clang
567
568	#endif // LLVM_CLANG_SEMA_TEMPLATE_H
569