SemaTemplateDeduction.cpp source code [clang_source_code/lib/Sema/SemaTemplateDeduction.cpp]

1	//===- SemaTemplateDeduction.cpp - Template Argument Deduction ------------===//
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	//
9	// This file implements C++ template argument deduction.
10	//
11	//===----------------------------------------------------------------------===//
12
13	#include "clang/Sema/TemplateDeduction.h"
14	#include "TreeTransform.h"
15	#include "TypeLocBuilder.h"
16	#include "clang/AST/ASTContext.h"
17	#include "clang/AST/ASTLambda.h"
18	#include "clang/AST/Decl.h"
19	#include "clang/AST/DeclAccessPair.h"
20	#include "clang/AST/DeclBase.h"
21	#include "clang/AST/DeclCXX.h"
22	#include "clang/AST/DeclTemplate.h"
23	#include "clang/AST/DeclarationName.h"
24	#include "clang/AST/Expr.h"
25	#include "clang/AST/ExprCXX.h"
26	#include "clang/AST/NestedNameSpecifier.h"
27	#include "clang/AST/TemplateBase.h"
28	#include "clang/AST/TemplateName.h"
29	#include "clang/AST/Type.h"
30	#include "clang/AST/TypeLoc.h"
31	#include "clang/AST/UnresolvedSet.h"
32	#include "clang/Basic/AddressSpaces.h"
33	#include "clang/Basic/ExceptionSpecificationType.h"
34	#include "clang/Basic/LLVM.h"
35	#include "clang/Basic/LangOptions.h"
36	#include "clang/Basic/PartialDiagnostic.h"
37	#include "clang/Basic/SourceLocation.h"
38	#include "clang/Basic/Specifiers.h"
39	#include "clang/Sema/Ownership.h"
40	#include "clang/Sema/Sema.h"
41	#include "clang/Sema/Template.h"
42	#include "llvm/ADT/APInt.h"
43	#include "llvm/ADT/APSInt.h"
44	#include "llvm/ADT/ArrayRef.h"
45	#include "llvm/ADT/DenseMap.h"
46	#include "llvm/ADT/FoldingSet.h"
47	#include "llvm/ADT/Optional.h"
48	#include "llvm/ADT/SmallBitVector.h"
49	#include "llvm/ADT/SmallPtrSet.h"
50	#include "llvm/ADT/SmallVector.h"
51	#include "llvm/Support/Casting.h"
52	#include "llvm/Support/Compiler.h"
53	#include "llvm/Support/ErrorHandling.h"
54	#include <algorithm>
55	#include <cassert>
56	#include <tuple>
57	#include <utility>
58
59	namespace clang {
60
61	/// Various flags that control template argument deduction.
62	///
63	/// These flags can be bitwise-OR'd together.
64	enum TemplateDeductionFlags {
65	/// No template argument deduction flags, which indicates the
66	/// strictest results for template argument deduction (as used for, e.g.,
67	/// matching class template partial specializations).
68	TDF_None = 0,
69
70	/// Within template argument deduction from a function call, we are
71	/// matching with a parameter type for which the original parameter was
72	/// a reference.
73	TDF_ParamWithReferenceType = 0x1,
74
75	/// Within template argument deduction from a function call, we
76	/// are matching in a case where we ignore cv-qualifiers.
77	TDF_IgnoreQualifiers = 0x02,
78
79	/// Within template argument deduction from a function call,
80	/// we are matching in a case where we can perform template argument
81	/// deduction from a template-id of a derived class of the argument type.
82	TDF_DerivedClass = 0x04,
83
84	/// Allow non-dependent types to differ, e.g., when performing
85	/// template argument deduction from a function call where conversions
86	/// may apply.
87	TDF_SkipNonDependent = 0x08,
88
89	/// Whether we are performing template argument deduction for
90	/// parameters and arguments in a top-level template argument
91	TDF_TopLevelParameterTypeList = 0x10,
92
93	/// Within template argument deduction from overload resolution per
94	/// C++ [over.over] allow matching function types that are compatible in
95	/// terms of noreturn and default calling convention adjustments, or
96	/// similarly matching a declared template specialization against a
97	/// possible template, per C++ [temp.deduct.decl]. In either case, permit
98	/// deduction where the parameter is a function type that can be converted
99	/// to the argument type.
100	TDF_AllowCompatibleFunctionType = 0x20,
101
102	/// Within template argument deduction for a conversion function, we are
103	/// matching with an argument type for which the original argument was
104	/// a reference.
105	TDF_ArgWithReferenceType = 0x40,
106	};
107	}
108
109	using namespace clang;
110	using namespace sema;
111
112	/// Compare two APSInts, extending and switching the sign as
113	/// necessary to compare their values regardless of underlying type.
114	static bool hasSameExtendedValue(llvm::APSInt X, llvm::APSInt Y) {
115	if (Y.getBitWidth() > X.getBitWidth())
116	X = X.extend(Y.getBitWidth());
117	else if (Y.getBitWidth() < X.getBitWidth())
118	Y = Y.extend(X.getBitWidth());
119
120	// If there is a signedness mismatch, correct it.
121	if (X.isSigned() != Y.isSigned()) {
122	// If the signed value is negative, then the values cannot be the same.
123	if ((Y.isSigned() && Y.isNegative()) \|\| (X.isSigned() && X.isNegative()))
124	return false;
125
126	Y.setIsSigned(true);
127	X.setIsSigned(true);
128	}
129
130	return X == Y;
131	}
132
133	static Sema::TemplateDeductionResult
134	DeduceTemplateArguments(Sema &S,
135	TemplateParameterList *TemplateParams,
136	const TemplateArgument &Param,
137	TemplateArgument Arg,
138	TemplateDeductionInfo &Info,
139	SmallVectorImpl<DeducedTemplateArgument> &Deduced);
140
141	static Sema::TemplateDeductionResult
142	DeduceTemplateArgumentsByTypeMatch(Sema &S,
143	TemplateParameterList *TemplateParams,
144	QualType Param,
145	QualType Arg,
146	TemplateDeductionInfo &Info,
147	SmallVectorImpl<DeducedTemplateArgument> &
148	Deduced,
149	unsigned TDF,
150	bool PartialOrdering = false,
151	bool DeducedFromArrayBound = false);
152
153	static Sema::TemplateDeductionResult
154	DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams,
155	ArrayRef<TemplateArgument> Params,
156	ArrayRef<TemplateArgument> Args,
157	TemplateDeductionInfo &Info,
158	SmallVectorImpl<DeducedTemplateArgument> &Deduced,
159	bool NumberOfArgumentsMustMatch);
160
161	static void MarkUsedTemplateParameters(ASTContext &Ctx,
162	const TemplateArgument &TemplateArg,
163	bool OnlyDeduced, unsigned Depth,
164	llvm::SmallBitVector &Used);
165
166	static void MarkUsedTemplateParameters(ASTContext &Ctx, QualType T,
167	bool OnlyDeduced, unsigned Level,
168	llvm::SmallBitVector &Deduced);
169
170	/// If the given expression is of a form that permits the deduction
171	/// of a non-type template parameter, return the declaration of that
172	/// non-type template parameter.
173	static NonTypeTemplateParmDecl *
174	getDeducedParameterFromExpr(TemplateDeductionInfo &Info, Expr *E) {
175	// If we are within an alias template, the expression may have undergone
176	// any number of parameter substitutions already.
177	while (true) {
178	if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E))
179	E = IC->getSubExpr();
180	else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(E))
181	E = CE->getSubExpr();
182	else if (SubstNonTypeTemplateParmExpr *Subst =
183	dyn_cast<SubstNonTypeTemplateParmExpr>(E))
184	E = Subst->getReplacement();
185	else
186	break;
187	}
188
189	if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
190	if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()))
191	if (NTTP->getDepth() == Info.getDeducedDepth())
192	return NTTP;
193
194	return nullptr;
195	}
196
197	/// Determine whether two declaration pointers refer to the same
198	/// declaration.
199	static bool isSameDeclaration(Decl X, Decl Y) {
200	if (NamedDecl *NX = dyn_cast<NamedDecl>(X))
201	X = NX->getUnderlyingDecl();
202	if (NamedDecl *NY = dyn_cast<NamedDecl>(Y))
203	Y = NY->getUnderlyingDecl();
204
205	return X->getCanonicalDecl() == Y->getCanonicalDecl();
206	}
207
208	/// Verify that the given, deduced template arguments are compatible.
209	///
210	/// \returns The deduced template argument, or a NULL template argument if
211	/// the deduced template arguments were incompatible.
212	static DeducedTemplateArgument
213	checkDeducedTemplateArguments(ASTContext &Context,
214	const DeducedTemplateArgument &X,
215	const DeducedTemplateArgument &Y) {
216	// We have no deduction for one or both of the arguments; they're compatible.
217	if (X.isNull())
218	return Y;
219	if (Y.isNull())
220	return X;
221
222	// If we have two non-type template argument values deduced for the same
223	// parameter, they must both match the type of the parameter, and thus must
224	// match each other's type. As we're only keeping one of them, we must check
225	// for that now. The exception is that if either was deduced from an array
226	// bound, the type is permitted to differ.
227	if (!X.wasDeducedFromArrayBound() && !Y.wasDeducedFromArrayBound()) {
228	QualType XType = X.getNonTypeTemplateArgumentType();
229	if (!XType.isNull()) {
230	QualType YType = Y.getNonTypeTemplateArgumentType();
231	if (YType.isNull() \|\| !Context.hasSameType(XType, YType))
232	return DeducedTemplateArgument();
233	}
234	}
235
236	switch (X.getKind()) {
237	case TemplateArgument::Null:
238	llvm_unreachable("Non-deduced template arguments handled above");
239
240	case TemplateArgument::Type:
241	// If two template type arguments have the same type, they're compatible.
242	if (Y.getKind() == TemplateArgument::Type &&
243	Context.hasSameType(X.getAsType(), Y.getAsType()))
244	return X;
245
246	// If one of the two arguments was deduced from an array bound, the other
247	// supersedes it.
248	if (X.wasDeducedFromArrayBound() != Y.wasDeducedFromArrayBound())
249	return X.wasDeducedFromArrayBound() ? Y : X;
250
251	// The arguments are not compatible.
252	return DeducedTemplateArgument();
253
254	case TemplateArgument::Integral:
255	// If we deduced a constant in one case and either a dependent expression or
256	// declaration in another case, keep the integral constant.
257	// If both are integral constants with the same value, keep that value.
258	if (Y.getKind() == TemplateArgument::Expression \|\|
259	Y.getKind() == TemplateArgument::Declaration \|\|
260	(Y.getKind() == TemplateArgument::Integral &&
261	hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral())))
262	return X.wasDeducedFromArrayBound() ? Y : X;
263
264	// All other combinations are incompatible.
265	return DeducedTemplateArgument();
266
267	case TemplateArgument::Template:
268	if (Y.getKind() == TemplateArgument::Template &&
269	Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate()))
270	return X;
271
272	// All other combinations are incompatible.
273	return DeducedTemplateArgument();
274
275	case TemplateArgument::TemplateExpansion:
276	if (Y.getKind() == TemplateArgument::TemplateExpansion &&
277	Context.hasSameTemplateName(X.getAsTemplateOrTemplatePattern(),
278	Y.getAsTemplateOrTemplatePattern()))
279	return X;
280
281	// All other combinations are incompatible.
282	return DeducedTemplateArgument();
283
284	case TemplateArgument::Expression: {
285	if (Y.getKind() != TemplateArgument::Expression)
286	return checkDeducedTemplateArguments(Context, Y, X);
287
288	// Compare the expressions for equality
289	llvm::FoldingSetNodeID ID1, ID2;
290	X.getAsExpr()->Profile(ID1, Context, true);
291	Y.getAsExpr()->Profile(ID2, Context, true);
292	if (ID1 == ID2)
293	return X.wasDeducedFromArrayBound() ? Y : X;
294
295	// Differing dependent expressions are incompatible.
296	return DeducedTemplateArgument();
297	}
298
299	case TemplateArgument::Declaration:
300	assert(!X.wasDeducedFromArrayBound());
301
302	// If we deduced a declaration and a dependent expression, keep the
303	// declaration.
304	if (Y.getKind() == TemplateArgument::Expression)
305	return X;
306
307	// If we deduced a declaration and an integral constant, keep the
308	// integral constant and whichever type did not come from an array
309	// bound.
310	if (Y.getKind() == TemplateArgument::Integral) {
311	if (Y.wasDeducedFromArrayBound())
312	return TemplateArgument(Context, Y.getAsIntegral(),
313	X.getParamTypeForDecl());
314	return Y;
315	}
316
317	// If we deduced two declarations, make sure that they refer to the
318	// same declaration.
319	if (Y.getKind() == TemplateArgument::Declaration &&
320	isSameDeclaration(X.getAsDecl(), Y.getAsDecl()))
321	return X;
322
323	// All other combinations are incompatible.
324	return DeducedTemplateArgument();
325
326	case TemplateArgument::NullPtr:
327	// If we deduced a null pointer and a dependent expression, keep the
328	// null pointer.
329	if (Y.getKind() == TemplateArgument::Expression)
330	return X;
331
332	// If we deduced a null pointer and an integral constant, keep the
333	// integral constant.
334	if (Y.getKind() == TemplateArgument::Integral)
335	return Y;
336
337	// If we deduced two null pointers, they are the same.
338	if (Y.getKind() == TemplateArgument::NullPtr)
339	return X;
340
341	// All other combinations are incompatible.
342	return DeducedTemplateArgument();
343
344	case TemplateArgument::Pack: {
345	if (Y.getKind() != TemplateArgument::Pack \|\|
346	X.pack_size() != Y.pack_size())
347	return DeducedTemplateArgument();
348
349	llvm::SmallVector<TemplateArgument, 8> NewPack;
350	for (TemplateArgument::pack_iterator XA = X.pack_begin(),
351	XAEnd = X.pack_end(),
352	YA = Y.pack_begin();
353	XA != XAEnd; ++XA, ++YA) {
354	TemplateArgument Merged = checkDeducedTemplateArguments(
355	Context, DeducedTemplateArgument(*XA, X.wasDeducedFromArrayBound()),
356	DeducedTemplateArgument(*YA, Y.wasDeducedFromArrayBound()));
357	if (Merged.isNull())
358	return DeducedTemplateArgument();
359	NewPack.push_back(Merged);
360	}
361
362	return DeducedTemplateArgument(
363	TemplateArgument::CreatePackCopy(Context, NewPack),
364	X.wasDeducedFromArrayBound() && Y.wasDeducedFromArrayBound());
365	}
366	}
367
368	llvm_unreachable("Invalid TemplateArgument Kind!");
369	}
370
371	/// Deduce the value of the given non-type template parameter
372	/// as the given deduced template argument. All non-type template parameter
373	/// deduction is funneled through here.
374	static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(
375	Sema &S, TemplateParameterList *TemplateParams,
376	NonTypeTemplateParmDecl *NTTP, const DeducedTemplateArgument &NewDeduced,
377	QualType ValueType, TemplateDeductionInfo &Info,
378	SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
379	(0) . __assert_fail ("NTTP->getDepth() == Info.getDeducedDepth() && \"deducing non-type template argument with wrong depth\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 380, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(NTTP->getDepth() == Info.getDeducedDepth() &&
380	(0) . __assert_fail ("NTTP->getDepth() == Info.getDeducedDepth() && \"deducing non-type template argument with wrong depth\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 380, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "deducing non-type template argument with wrong depth");
381
382	DeducedTemplateArgument Result = checkDeducedTemplateArguments(
383	S.Context, Deduced[NTTP->getIndex()], NewDeduced);
384	if (Result.isNull()) {
385	Info.Param = NTTP;
386	Info.FirstArg = Deduced[NTTP->getIndex()];
387	Info.SecondArg = NewDeduced;
388	return Sema::TDK_Inconsistent;
389	}
390
391	Deduced[NTTP->getIndex()] = Result;
392	if (!S.getLangOpts().CPlusPlus17)
393	return Sema::TDK_Success;
394
395	if (NTTP->isExpandedParameterPack())
396	// FIXME: We may still need to deduce parts of the type here! But we
397	// don't have any way to find which slice of the type to use, and the
398	// type stored on the NTTP itself is nonsense. Perhaps the type of an
399	// expanded NTTP should be a pack expansion type?
400	return Sema::TDK_Success;
401
402	// Get the type of the parameter for deduction. If it's a (dependent) array
403	// or function type, we will not have decayed it yet, so do that now.
404	QualType ParamType = S.Context.getAdjustedParameterType(NTTP->getType());
405	if (auto *Expansion = dyn_cast<PackExpansionType>(ParamType))
406	ParamType = Expansion->getPattern();
407
408	// FIXME: It's not clear how deduction of a parameter of reference
409	// type from an argument (of non-reference type) should be performed.
410	// For now, we just remove reference types from both sides and let
411	// the final check for matching types sort out the mess.
412	return DeduceTemplateArgumentsByTypeMatch(
413	S, TemplateParams, ParamType.getNonReferenceType(),
414	ValueType.getNonReferenceType(), Info, Deduced, TDF_SkipNonDependent,
415	/PartialOrdering=/false,
416	/ArrayBound=/NewDeduced.wasDeducedFromArrayBound());
417	}
418
419	/// Deduce the value of the given non-type template parameter
420	/// from the given integral constant.
421	static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(
422	Sema &S, TemplateParameterList *TemplateParams,
423	NonTypeTemplateParmDecl *NTTP, const llvm::APSInt &Value,
424	QualType ValueType, bool DeducedFromArrayBound, TemplateDeductionInfo &Info,
425	SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
426	return DeduceNonTypeTemplateArgument(
427	S, TemplateParams, NTTP,
428	DeducedTemplateArgument(S.Context, Value, ValueType,
429	DeducedFromArrayBound),
430	ValueType, Info, Deduced);
431	}
432
433	/// Deduce the value of the given non-type template parameter
434	/// from the given null pointer template argument type.
435	static Sema::TemplateDeductionResult DeduceNullPtrTemplateArgument(
436	Sema &S, TemplateParameterList *TemplateParams,
437	NonTypeTemplateParmDecl *NTTP, QualType NullPtrType,
438	TemplateDeductionInfo &Info,
439	SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
440	Expr *Value =
441	S.ImpCastExprToType(new (S.Context) CXXNullPtrLiteralExpr(
442	S.Context.NullPtrTy, NTTP->getLocation()),
443	NullPtrType, CK_NullToPointer)
444	.get();
445	return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
446	DeducedTemplateArgument(Value),
447	Value->getType(), Info, Deduced);
448	}
449
450	/// Deduce the value of the given non-type template parameter
451	/// from the given type- or value-dependent expression.
452	///
453	/// \returns true if deduction succeeded, false otherwise.
454	static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(
455	Sema &S, TemplateParameterList *TemplateParams,
456	NonTypeTemplateParmDecl NTTP, Expr Value, TemplateDeductionInfo &Info,
457	SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
458	return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
459	DeducedTemplateArgument(Value),
460	Value->getType(), Info, Deduced);
461	}
462
463	/// Deduce the value of the given non-type template parameter
464	/// from the given declaration.
465	///
466	/// \returns true if deduction succeeded, false otherwise.
467	static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(
468	Sema &S, TemplateParameterList *TemplateParams,
469	NonTypeTemplateParmDecl NTTP, ValueDecl D, QualType T,
470	TemplateDeductionInfo &Info,
471	SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
472	D = D ? cast<ValueDecl>(D->getCanonicalDecl()) : nullptr;
473	TemplateArgument New(D, T);
474	return DeduceNonTypeTemplateArgument(
475	S, TemplateParams, NTTP, DeducedTemplateArgument(New), T, Info, Deduced);
476	}
477
478	static Sema::TemplateDeductionResult
479	DeduceTemplateArguments(Sema &S,
480	TemplateParameterList *TemplateParams,
481	TemplateName Param,
482	TemplateName Arg,
483	TemplateDeductionInfo &Info,
484	SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
485	TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
486	if (!ParamDecl) {
487	// The parameter type is dependent and is not a template template parameter,
488	// so there is nothing that we can deduce.
489	return Sema::TDK_Success;
490	}
491
492	if (TemplateTemplateParmDecl *TempParam
493	= dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) {
494	// If we're not deducing at this depth, there's nothing to deduce.
495	if (TempParam->getDepth() != Info.getDeducedDepth())
496	return Sema::TDK_Success;
497
498	DeducedTemplateArgument NewDeduced(S.Context.getCanonicalTemplateName(Arg));
499	DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
500	Deduced[TempParam->getIndex()],
501	NewDeduced);
502	if (Result.isNull()) {
503	Info.Param = TempParam;
504	Info.FirstArg = Deduced[TempParam->getIndex()];
505	Info.SecondArg = NewDeduced;
506	return Sema::TDK_Inconsistent;
507	}
508
509	Deduced[TempParam->getIndex()] = Result;
510	return Sema::TDK_Success;
511	}
512
513	// Verify that the two template names are equivalent.
514	if (S.Context.hasSameTemplateName(Param, Arg))
515	return Sema::TDK_Success;
516
517	// Mismatch of non-dependent template parameter to argument.
518	Info.FirstArg = TemplateArgument(Param);
519	Info.SecondArg = TemplateArgument(Arg);
520	return Sema::TDK_NonDeducedMismatch;
521	}
522
523	/// Deduce the template arguments by comparing the template parameter
524	/// type (which is a template-id) with the template argument type.
525	///
526	/// \param S the Sema
527	///
528	/// \param TemplateParams the template parameters that we are deducing
529	///
530	/// \param Param the parameter type
531	///
532	/// \param Arg the argument type
533	///
534	/// \param Info information about the template argument deduction itself
535	///
536	/// \param Deduced the deduced template arguments
537	///
538	/// \returns the result of template argument deduction so far. Note that a
539	/// "success" result means that template argument deduction has not yet failed,
540	/// but it may still fail, later, for other reasons.
541	static Sema::TemplateDeductionResult
542	DeduceTemplateArguments(Sema &S,
543	TemplateParameterList *TemplateParams,
544	const TemplateSpecializationType *Param,
545	QualType Arg,
546	TemplateDeductionInfo &Info,
547	SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
548	(0) . __assert_fail ("Arg.isCanonical() && \"Argument type must be canonical\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 548, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(Arg.isCanonical() && "Argument type must be canonical");
549
550	// Treat an injected-class-name as its underlying template-id.
551	if (auto *Injected = dyn_cast<InjectedClassNameType>(Arg))
552	Arg = Injected->getInjectedSpecializationType();
553
554	// Check whether the template argument is a dependent template-id.
555	if (const TemplateSpecializationType *SpecArg
556	= dyn_cast<TemplateSpecializationType>(Arg)) {
557	// Perform template argument deduction for the template name.
558	if (Sema::TemplateDeductionResult Result
559	= DeduceTemplateArguments(S, TemplateParams,
560	Param->getTemplateName(),
561	SpecArg->getTemplateName(),
562	Info, Deduced))
563	return Result;
564
565
566	// Perform template argument deduction on each template
567	// argument. Ignore any missing/extra arguments, since they could be
568	// filled in by default arguments.
569	return DeduceTemplateArguments(S, TemplateParams,
570	Param->template_arguments(),
571	SpecArg->template_arguments(), Info, Deduced,
572	/NumberOfArgumentsMustMatch=/false);
573	}
574
575	// If the argument type is a class template specialization, we
576	// perform template argument deduction using its template
577	// arguments.
578	const RecordType *RecordArg = dyn_cast<RecordType>(Arg);
579	if (!RecordArg) {
580	Info.FirstArg = TemplateArgument(QualType(Param, 0));
581	Info.SecondArg = TemplateArgument(Arg);
582	return Sema::TDK_NonDeducedMismatch;
583	}
584
585	ClassTemplateSpecializationDecl *SpecArg
586	= dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl());
587	if (!SpecArg) {
588	Info.FirstArg = TemplateArgument(QualType(Param, 0));
589	Info.SecondArg = TemplateArgument(Arg);
590	return Sema::TDK_NonDeducedMismatch;
591	}
592
593	// Perform template argument deduction for the template name.
594	if (Sema::TemplateDeductionResult Result
595	= DeduceTemplateArguments(S,
596	TemplateParams,
597	Param->getTemplateName(),
598	TemplateName(SpecArg->getSpecializedTemplate()),
599	Info, Deduced))
600	return Result;
601
602	// Perform template argument deduction for the template arguments.
603	return DeduceTemplateArguments(S, TemplateParams, Param->template_arguments(),
604	SpecArg->getTemplateArgs().asArray(), Info,
605	Deduced, /NumberOfArgumentsMustMatch=/true);
606	}
607
608	/// Determines whether the given type is an opaque type that
609	/// might be more qualified when instantiated.
610	static bool IsPossiblyOpaquelyQualifiedType(QualType T) {
611	switch (T->getTypeClass()) {
612	case Type::TypeOfExpr:
613	case Type::TypeOf:
614	case Type::DependentName:
615	case Type::Decltype:
616	case Type::UnresolvedUsing:
617	case Type::TemplateTypeParm:
618	return true;
619
620	case Type::ConstantArray:
621	case Type::IncompleteArray:
622	case Type::VariableArray:
623	case Type::DependentSizedArray:
624	return IsPossiblyOpaquelyQualifiedType(
625	cast<ArrayType>(T)->getElementType());
626
627	default:
628	return false;
629	}
630	}
631
632	/// Helper function to build a TemplateParameter when we don't
633	/// know its type statically.
634	static TemplateParameter makeTemplateParameter(Decl *D) {
635	if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D))
636	return TemplateParameter(TTP);
637	if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D))
638	return TemplateParameter(NTTP);
639
640	return TemplateParameter(cast<TemplateTemplateParmDecl>(D));
641	}
642
643	/// If \p Param is an expanded parameter pack, get the number of expansions.
644	static Optional<unsigned> getExpandedPackSize(NamedDecl *Param) {
645	if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(Param))
646	if (NTTP->isExpandedParameterPack())
647	return NTTP->getNumExpansionTypes();
648
649	if (auto *TTP = dyn_cast<TemplateTemplateParmDecl>(Param))
650	if (TTP->isExpandedParameterPack())
651	return TTP->getNumExpansionTemplateParameters();
652
653	return None;
654	}
655
656	/// A pack that we're currently deducing.
657	struct clang::DeducedPack {
658	// The index of the pack.
659	unsigned Index;
660
661	// The old value of the pack before we started deducing it.
662	DeducedTemplateArgument Saved;
663
664	// A deferred value of this pack from an inner deduction, that couldn't be
665	// deduced because this deduction hadn't happened yet.
666	DeducedTemplateArgument DeferredDeduction;
667
668	// The new value of the pack.
669	SmallVector<DeducedTemplateArgument, 4> New;
670
671	// The outer deduction for this pack, if any.
672	DeducedPack *Outer = nullptr;
673
674	DeducedPack(unsigned Index) : Index(Index) {}
675	};
676
677	namespace {
678
679	/// A scope in which we're performing pack deduction.
680	class PackDeductionScope {
681	public:
682	/// Prepare to deduce the packs named within Pattern.
683	PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams,
684	SmallVectorImpl<DeducedTemplateArgument> &Deduced,
685	TemplateDeductionInfo &Info, TemplateArgument Pattern)
686	: S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info) {
687	unsigned NumNamedPacks = addPacks(Pattern);
688	finishConstruction(NumNamedPacks);
689	}
690
691	/// Prepare to directly deduce arguments of the parameter with index \p Index.
692	PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams,
693	SmallVectorImpl<DeducedTemplateArgument> &Deduced,
694	TemplateDeductionInfo &Info, unsigned Index)
695	: S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info) {
696	addPack(Index);
697	finishConstruction(1);
698	}
699
700	private:
701	void addPack(unsigned Index) {
702	// Save the deduced template argument for the parameter pack expanded
703	// by this pack expansion, then clear out the deduction.
704	DeducedPack Pack(Index);
705	Pack.Saved = Deduced[Index];
706	Deduced[Index] = TemplateArgument();
707
708	// FIXME: What if we encounter multiple packs with different numbers of
709	// pre-expanded expansions? (This should already have been diagnosed
710	// during substitution.)
711	if (Optional<unsigned> ExpandedPackExpansions =
712	getExpandedPackSize(TemplateParams->getParam(Index)))
713	FixedNumExpansions = ExpandedPackExpansions;
714
715	Packs.push_back(Pack);
716	}
717
718	unsigned addPacks(TemplateArgument Pattern) {
719	// Compute the set of template parameter indices that correspond to
720	// parameter packs expanded by the pack expansion.
721	llvm::SmallBitVector SawIndices(TemplateParams->size());
722
723	auto AddPack = [&](unsigned Index) {
724	if (SawIndices[Index])
725	return;
726	SawIndices[Index] = true;
727	addPack(Index);
728	};
729
730	// First look for unexpanded packs in the pattern.
731	SmallVector<UnexpandedParameterPack, 2> Unexpanded;
732	S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
733	for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
734	unsigned Depth, Index;
735	std::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
736	if (Depth == Info.getDeducedDepth())
737	AddPack(Index);
738	}
739	(0) . __assert_fail ("!Packs.empty() && \"Pack expansion without unexpanded packs?\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 739, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(!Packs.empty() && "Pack expansion without unexpanded packs?");
740
741	unsigned NumNamedPacks = Packs.size();
742
743	// We can also have deduced template parameters that do not actually
744	// appear in the pattern, but can be deduced by it (the type of a non-type
745	// template parameter pack, in particular). These won't have prevented us
746	// from partially expanding the pack.
747	llvm::SmallBitVector Used(TemplateParams->size());
748	MarkUsedTemplateParameters(S.Context, Pattern, /OnlyDeduced/true,
749	Info.getDeducedDepth(), Used);
750	for (int Index = Used.find_first(); Index != -1;
751	Index = Used.find_next(Index))
752	if (TemplateParams->getParam(Index)->isParameterPack())
753	AddPack(Index);
754
755	return NumNamedPacks;
756	}
757
758	void finishConstruction(unsigned NumNamedPacks) {
759	// Dig out the partially-substituted pack, if there is one.
760	const TemplateArgument *PartialPackArgs = nullptr;
761	unsigned NumPartialPackArgs = 0;
762	std::pair<unsigned, unsigned> PartialPackDepthIndex(-1u, -1u);
763	if (auto *Scope = S.CurrentInstantiationScope)
764	if (auto *Partial = Scope->getPartiallySubstitutedPack(
765	&PartialPackArgs, &NumPartialPackArgs))
766	PartialPackDepthIndex = getDepthAndIndex(Partial);
767
768	// This pack expansion will have been partially or fully expanded if
769	// it only names explicitly-specified parameter packs (including the
770	// partially-substituted one, if any).
771	bool IsExpanded = true;
772	for (unsigned I = 0; I != NumNamedPacks; ++I) {
773	if (Packs[I].Index >= Info.getNumExplicitArgs()) {
774	IsExpanded = false;
775	IsPartiallyExpanded = false;
776	break;
777	}
778	if (PartialPackDepthIndex ==
779	std::make_pair(Info.getDeducedDepth(), Packs[I].Index)) {
780	IsPartiallyExpanded = true;
781	}
782	}
783
784	// Skip over the pack elements that were expanded into separate arguments.
785	// If we partially expanded, this is the number of partial arguments.
786	if (IsPartiallyExpanded)
787	PackElements += NumPartialPackArgs;
788	else if (IsExpanded)
789	PackElements += *FixedNumExpansions;
790
791	for (auto &Pack : Packs) {
792	if (Info.PendingDeducedPacks.size() > Pack.Index)
793	Pack.Outer = Info.PendingDeducedPacks[Pack.Index];
794	else
795	Info.PendingDeducedPacks.resize(Pack.Index + 1);
796	Info.PendingDeducedPacks[Pack.Index] = &Pack;
797
798	if (PartialPackDepthIndex ==
799	std::make_pair(Info.getDeducedDepth(), Pack.Index)) {
800	Pack.New.append(PartialPackArgs, PartialPackArgs + NumPartialPackArgs);
801	// We pre-populate the deduced value of the partially-substituted
802	// pack with the specified value. This is not entirely correct: the
803	// value is supposed to have been substituted, not deduced, but the
804	// cases where this is observable require an exact type match anyway.
805	//
806	// FIXME: If we could represent a "depth i, index j, pack elem k"
807	// parameter, we could substitute the partially-substituted pack
808	// everywhere and avoid this.
809	if (!IsPartiallyExpanded)
810	Deduced[Pack.Index] = Pack.New[PackElements];
811	}
812	}
813	}
814
815	public:
816	~PackDeductionScope() {
817	for (auto &Pack : Packs)
818	Info.PendingDeducedPacks[Pack.Index] = Pack.Outer;
819	}
820
821	/// Determine whether this pack has already been partially expanded into a
822	/// sequence of (prior) function parameters / template arguments.
823	bool isPartiallyExpanded() { return IsPartiallyExpanded; }
824
825	/// Determine whether this pack expansion scope has a known, fixed arity.
826	/// This happens if it involves a pack from an outer template that has
827	/// (notionally) already been expanded.
828	bool hasFixedArity() { return FixedNumExpansions.hasValue(); }
829
830	/// Determine whether the next element of the argument is still part of this
831	/// pack. This is the case unless the pack is already expanded to a fixed
832	/// length.
833	bool hasNextElement() {
834	return !FixedNumExpansions \|\| *FixedNumExpansions > PackElements;
835	}
836
837	/// Move to deducing the next element in each pack that is being deduced.
838	void nextPackElement() {
839	// Capture the deduced template arguments for each parameter pack expanded
840	// by this pack expansion, add them to the list of arguments we've deduced
841	// for that pack, then clear out the deduced argument.
842	for (auto &Pack : Packs) {
843	DeducedTemplateArgument &DeducedArg = Deduced[Pack.Index];
844	if (!Pack.New.empty() \|\| !DeducedArg.isNull()) {
845	while (Pack.New.size() < PackElements)
846	Pack.New.push_back(DeducedTemplateArgument());
847	if (Pack.New.size() == PackElements)
848	Pack.New.push_back(DeducedArg);
849	else
850	Pack.New[PackElements] = DeducedArg;
851	DeducedArg = Pack.New.size() > PackElements + 1
852	? Pack.New[PackElements + 1]
853	: DeducedTemplateArgument();
854	}
855	}
856	++PackElements;
857	}
858
859	/// Finish template argument deduction for a set of argument packs,
860	/// producing the argument packs and checking for consistency with prior
861	/// deductions.
862	Sema::TemplateDeductionResult
863	finish(bool TreatNoDeductionsAsNonDeduced = true) {
864	// Build argument packs for each of the parameter packs expanded by this
865	// pack expansion.
866	for (auto &Pack : Packs) {
867	// Put back the old value for this pack.
868	Deduced[Pack.Index] = Pack.Saved;
869
870	// If we are deducing the size of this pack even if we didn't deduce any
871	// values for it, then make sure we build a pack of the right size.
872	// FIXME: Should we always deduce the size, even if the pack appears in
873	// a non-deduced context?
874	if (!TreatNoDeductionsAsNonDeduced)
875	Pack.New.resize(PackElements);
876
877	// Build or find a new value for this pack.
878	DeducedTemplateArgument NewPack;
879	if (PackElements && Pack.New.empty()) {
880	if (Pack.DeferredDeduction.isNull()) {
881	// We were not able to deduce anything for this parameter pack
882	// (because it only appeared in non-deduced contexts), so just
883	// restore the saved argument pack.
884	continue;
885	}
886
887	NewPack = Pack.DeferredDeduction;
888	Pack.DeferredDeduction = TemplateArgument();
889	} else if (Pack.New.empty()) {
890	// If we deduced an empty argument pack, create it now.
891	NewPack = DeducedTemplateArgument(TemplateArgument::getEmptyPack());
892	} else {
893	TemplateArgument *ArgumentPack =
894	new (S.Context) TemplateArgument[Pack.New.size()];
895	std::copy(Pack.New.begin(), Pack.New.end(), ArgumentPack);
896	NewPack = DeducedTemplateArgument(
897	TemplateArgument(llvm::makeArrayRef(ArgumentPack, Pack.New.size())),
898	// FIXME: This is wrong, it's possible that some pack elements are
899	// deduced from an array bound and others are not:
900	// template<typename ...T, T ...V> void g(const T (&...p)[V]);
901	// g({1, 2, 3}, {{}, {}});
902	// ... should deduce T = {int, size_t (from array bound)}.
903	Pack.New[0].wasDeducedFromArrayBound());
904	}
905
906	// Pick where we're going to put the merged pack.
907	DeducedTemplateArgument *Loc;
908	if (Pack.Outer) {
909	if (Pack.Outer->DeferredDeduction.isNull()) {
910	// Defer checking this pack until we have a complete pack to compare
911	// it against.
912	Pack.Outer->DeferredDeduction = NewPack;
913	continue;
914	}
915	Loc = &Pack.Outer->DeferredDeduction;
916	} else {
917	Loc = &Deduced[Pack.Index];
918	}
919
920	// Check the new pack matches any previous value.
921	DeducedTemplateArgument OldPack = *Loc;
922	DeducedTemplateArgument Result =
923	checkDeducedTemplateArguments(S.Context, OldPack, NewPack);
924
925	// If we deferred a deduction of this pack, check that one now too.
926	if (!Result.isNull() && !Pack.DeferredDeduction.isNull()) {
927	OldPack = Result;
928	NewPack = Pack.DeferredDeduction;
929	Result = checkDeducedTemplateArguments(S.Context, OldPack, NewPack);
930	}
931
932	NamedDecl *Param = TemplateParams->getParam(Pack.Index);
933	if (Result.isNull()) {
934	Info.Param = makeTemplateParameter(Param);
935	Info.FirstArg = OldPack;
936	Info.SecondArg = NewPack;
937	return Sema::TDK_Inconsistent;
938	}
939
940	// If we have a pre-expanded pack and we didn't deduce enough elements
941	// for it, fail deduction.
942	if (Optional<unsigned> Expansions = getExpandedPackSize(Param)) {
943	if (*Expansions != PackElements) {
944	Info.Param = makeTemplateParameter(Param);
945	Info.FirstArg = Result;
946	return Sema::TDK_IncompletePack;
947	}
948	}
949
950	*Loc = Result;
951	}
952
953	return Sema::TDK_Success;
954	}
955
956	private:
957	Sema &S;
958	TemplateParameterList *TemplateParams;
959	SmallVectorImpl<DeducedTemplateArgument> &Deduced;
960	TemplateDeductionInfo &Info;
961	unsigned PackElements = 0;
962	bool IsPartiallyExpanded = false;
963	/// The number of expansions, if we have a fully-expanded pack in this scope.
964	Optional<unsigned> FixedNumExpansions;
965
966	SmallVector<DeducedPack, 2> Packs;
967	};
968
969	} // namespace
970
971	/// Deduce the template arguments by comparing the list of parameter
972	/// types to the list of argument types, as in the parameter-type-lists of
973	/// function types (C++ [temp.deduct.type]p10).
974	///
975	/// \param S The semantic analysis object within which we are deducing
976	///
977	/// \param TemplateParams The template parameters that we are deducing
978	///
979	/// \param Params The list of parameter types
980	///
981	/// \param NumParams The number of types in \c Params
982	///
983	/// \param Args The list of argument types
984	///
985	/// \param NumArgs The number of types in \c Args
986	///
987	/// \param Info information about the template argument deduction itself
988	///
989	/// \param Deduced the deduced template arguments
990	///
991	/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
992	/// how template argument deduction is performed.
993	///
994	/// \param PartialOrdering If true, we are performing template argument
995	/// deduction for during partial ordering for a call
996	/// (C++0x [temp.deduct.partial]).
997	///
998	/// \returns the result of template argument deduction so far. Note that a
999	/// "success" result means that template argument deduction has not yet failed,
1000	/// but it may still fail, later, for other reasons.
1001	static Sema::TemplateDeductionResult
1002	DeduceTemplateArguments(Sema &S,
1003	TemplateParameterList *TemplateParams,
1004	const QualType *Params, unsigned NumParams,
1005	const QualType *Args, unsigned NumArgs,
1006	TemplateDeductionInfo &Info,
1007	SmallVectorImpl<DeducedTemplateArgument> &Deduced,
1008	unsigned TDF,
1009	bool PartialOrdering = false) {
1010	// C++0x [temp.deduct.type]p10:
1011	// Similarly, if P has a form that contains (T), then each parameter type
1012	// Pi of the respective parameter-type- list of P is compared with the
1013	// corresponding parameter type Ai of the corresponding parameter-type-list
1014	// of A. [...]
1015	unsigned ArgIdx = 0, ParamIdx = 0;
1016	for (; ParamIdx != NumParams; ++ParamIdx) {
1017	// Check argument types.
1018	const PackExpansionType *Expansion
1019	= dyn_cast<PackExpansionType>(Params[ParamIdx]);
1020	if (!Expansion) {
1021	// Simple case: compare the parameter and argument types at this point.
1022
1023	// Make sure we have an argument.
1024	if (ArgIdx >= NumArgs)
1025	return Sema::TDK_MiscellaneousDeductionFailure;
1026
1027	if (isa<PackExpansionType>(Args[ArgIdx])) {
1028	// C++0x [temp.deduct.type]p22:
1029	// If the original function parameter associated with A is a function
1030	// parameter pack and the function parameter associated with P is not
1031	// a function parameter pack, then template argument deduction fails.
1032	return Sema::TDK_MiscellaneousDeductionFailure;
1033	}
1034
1035	if (Sema::TemplateDeductionResult Result
1036	= DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1037	Params[ParamIdx], Args[ArgIdx],
1038	Info, Deduced, TDF,
1039	PartialOrdering))
1040	return Result;
1041
1042	++ArgIdx;
1043	continue;
1044	}
1045
1046	// C++0x [temp.deduct.type]p10:
1047	// If the parameter-declaration corresponding to Pi is a function
1048	// parameter pack, then the type of its declarator- id is compared with
1049	// each remaining parameter type in the parameter-type-list of A. Each
1050	// comparison deduces template arguments for subsequent positions in the
1051	// template parameter packs expanded by the function parameter pack.
1052
1053	QualType Pattern = Expansion->getPattern();
1054	PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
1055
1056	// A pack scope with fixed arity is not really a pack any more, so is not
1057	// a non-deduced context.
1058	if (ParamIdx + 1 == NumParams \|\| PackScope.hasFixedArity()) {
1059	for (; ArgIdx < NumArgs && PackScope.hasNextElement(); ++ArgIdx) {
1060	// Deduce template arguments from the pattern.
1061	if (Sema::TemplateDeductionResult Result
1062	= DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, Pattern,
1063	Args[ArgIdx], Info, Deduced,
1064	TDF, PartialOrdering))
1065	return Result;
1066
1067	PackScope.nextPackElement();
1068	}
1069	} else {
1070	// C++0x [temp.deduct.type]p5:
1071	// The non-deduced contexts are:
1072	// - A function parameter pack that does not occur at the end of the
1073	// parameter-declaration-clause.
1074	//
1075	// FIXME: There is no wording to say what we should do in this case. We
1076	// choose to resolve this by applying the same rule that is applied for a
1077	// function call: that is, deduce all contained packs to their
1078	// explicitly-specified values (or to <> if there is no such value).
1079	//
1080	// This is seemingly-arbitrarily different from the case of a template-id
1081	// with a non-trailing pack-expansion in its arguments, which renders the
1082	// entire template-argument-list a non-deduced context.
1083
1084	// If the parameter type contains an explicitly-specified pack that we
1085	// could not expand, skip the number of parameters notionally created
1086	// by the expansion.
1087	Optional<unsigned> NumExpansions = Expansion->getNumExpansions();
1088	if (NumExpansions && !PackScope.isPartiallyExpanded()) {
1089	for (unsigned I = 0; I != *NumExpansions && ArgIdx < NumArgs;
1090	++I, ++ArgIdx)
1091	PackScope.nextPackElement();
1092	}
1093	}
1094
1095	// Build argument packs for each of the parameter packs expanded by this
1096	// pack expansion.
1097	if (auto Result = PackScope.finish())
1098	return Result;
1099	}
1100
1101	// Make sure we don't have any extra arguments.
1102	if (ArgIdx < NumArgs)
1103	return Sema::TDK_MiscellaneousDeductionFailure;
1104
1105	return Sema::TDK_Success;
1106	}
1107
1108	/// Determine whether the parameter has qualifiers that the argument
1109	/// lacks. Put another way, determine whether there is no way to add
1110	/// a deduced set of qualifiers to the ParamType that would result in
1111	/// its qualifiers matching those of the ArgType.
1112	static bool hasInconsistentOrSupersetQualifiersOf(QualType ParamType,
1113	QualType ArgType) {
1114	Qualifiers ParamQs = ParamType.getQualifiers();
1115	Qualifiers ArgQs = ArgType.getQualifiers();
1116
1117	if (ParamQs == ArgQs)
1118	return false;
1119
1120	// Mismatched (but not missing) Objective-C GC attributes.
1121	if (ParamQs.getObjCGCAttr() != ArgQs.getObjCGCAttr() &&
1122	ParamQs.hasObjCGCAttr())
1123	return true;
1124
1125	// Mismatched (but not missing) address spaces.
1126	if (ParamQs.getAddressSpace() != ArgQs.getAddressSpace() &&
1127	ParamQs.hasAddressSpace())
1128	return true;
1129
1130	// Mismatched (but not missing) Objective-C lifetime qualifiers.
1131	if (ParamQs.getObjCLifetime() != ArgQs.getObjCLifetime() &&
1132	ParamQs.hasObjCLifetime())
1133	return true;
1134
1135	// CVR qualifiers inconsistent or a superset.
1136	return (ParamQs.getCVRQualifiers() & ~ArgQs.getCVRQualifiers()) != 0;
1137	}
1138
1139	/// Compare types for equality with respect to possibly compatible
1140	/// function types (noreturn adjustment, implicit calling conventions). If any
1141	/// of parameter and argument is not a function, just perform type comparison.
1142	///
1143	/// \param Param the template parameter type.
1144	///
1145	/// \param Arg the argument type.
1146	bool Sema::isSameOrCompatibleFunctionType(CanQualType Param,
1147	CanQualType Arg) {
1148	const FunctionType *ParamFunction = Param->getAs<FunctionType>(),
1149	*ArgFunction = Arg->getAs<FunctionType>();
1150
1151	// Just compare if not functions.
1152	if (!ParamFunction \|\| !ArgFunction)
1153	return Param == Arg;
1154
1155	// Noreturn and noexcept adjustment.
1156	QualType AdjustedParam;
1157	if (IsFunctionConversion(Param, Arg, AdjustedParam))
1158	return Arg == Context.getCanonicalType(AdjustedParam);
1159
1160	// FIXME: Compatible calling conventions.
1161
1162	return Param == Arg;
1163	}
1164
1165	/// Get the index of the first template parameter that was originally from the
1166	/// innermost template-parameter-list. This is 0 except when we concatenate
1167	/// the template parameter lists of a class template and a constructor template
1168	/// when forming an implicit deduction guide.
1169	static unsigned getFirstInnerIndex(FunctionTemplateDecl *FTD) {
1170	auto *Guide = dyn_cast<CXXDeductionGuideDecl>(FTD->getTemplatedDecl());
1171	if (!Guide \|\| !Guide->isImplicit())
1172	return 0;
1173	return Guide->getDeducedTemplate()->getTemplateParameters()->size();
1174	}
1175
1176	/// Determine whether a type denotes a forwarding reference.
1177	static bool isForwardingReference(QualType Param, unsigned FirstInnerIndex) {
1178	// C++1z [temp.deduct.call]p3:
1179	// A forwarding reference is an rvalue reference to a cv-unqualified
1180	// template parameter that does not represent a template parameter of a
1181	// class template.
1182	if (auto *ParamRef = Param->getAs<RValueReferenceType>()) {
1183	if (ParamRef->getPointeeType().getQualifiers())
1184	return false;
1185	auto *TypeParm = ParamRef->getPointeeType()->getAs<TemplateTypeParmType>();
1186	return TypeParm && TypeParm->getIndex() >= FirstInnerIndex;
1187	}
1188	return false;
1189	}
1190
1191	/// Deduce the template arguments by comparing the parameter type and
1192	/// the argument type (C++ [temp.deduct.type]).
1193	///
1194	/// \param S the semantic analysis object within which we are deducing
1195	///
1196	/// \param TemplateParams the template parameters that we are deducing
1197	///
1198	/// \param ParamIn the parameter type
1199	///
1200	/// \param ArgIn the argument type
1201	///
1202	/// \param Info information about the template argument deduction itself
1203	///
1204	/// \param Deduced the deduced template arguments
1205	///
1206	/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
1207	/// how template argument deduction is performed.
1208	///
1209	/// \param PartialOrdering Whether we're performing template argument deduction
1210	/// in the context of partial ordering (C++0x [temp.deduct.partial]).
1211	///
1212	/// \returns the result of template argument deduction so far. Note that a
1213	/// "success" result means that template argument deduction has not yet failed,
1214	/// but it may still fail, later, for other reasons.
1215	static Sema::TemplateDeductionResult
1216	DeduceTemplateArgumentsByTypeMatch(Sema &S,
1217	TemplateParameterList *TemplateParams,
1218	QualType ParamIn, QualType ArgIn,
1219	TemplateDeductionInfo &Info,
1220	SmallVectorImpl<DeducedTemplateArgument> &Deduced,
1221	unsigned TDF,
1222	bool PartialOrdering,
1223	bool DeducedFromArrayBound) {
1224	// We only want to look at the canonical types, since typedefs and
1225	// sugar are not part of template argument deduction.
1226	QualType Param = S.Context.getCanonicalType(ParamIn);
1227	QualType Arg = S.Context.getCanonicalType(ArgIn);
1228
1229	// If the argument type is a pack expansion, look at its pattern.
1230	// This isn't explicitly called out
1231	if (const PackExpansionType *ArgExpansion
1232	= dyn_cast<PackExpansionType>(Arg))
1233	Arg = ArgExpansion->getPattern();
1234
1235	if (PartialOrdering) {
1236	// C++11 [temp.deduct.partial]p5:
1237	// Before the partial ordering is done, certain transformations are
1238	// performed on the types used for partial ordering:
1239	// - If P is a reference type, P is replaced by the type referred to.
1240	const ReferenceType *ParamRef = Param->getAs<ReferenceType>();
1241	if (ParamRef)
1242	Param = ParamRef->getPointeeType();
1243
1244	// - If A is a reference type, A is replaced by the type referred to.
1245	const ReferenceType *ArgRef = Arg->getAs<ReferenceType>();
1246	if (ArgRef)
1247	Arg = ArgRef->getPointeeType();
1248
1249	if (ParamRef && ArgRef && S.Context.hasSameUnqualifiedType(Param, Arg)) {
1250	// C++11 [temp.deduct.partial]p9:
1251	// If, for a given type, deduction succeeds in both directions (i.e.,
1252	// the types are identical after the transformations above) and both
1253	// P and A were reference types [...]:
1254	// - if [one type] was an lvalue reference and [the other type] was
1255	// not, [the other type] is not considered to be at least as
1256	// specialized as [the first type]
1257	// - if [one type] is more cv-qualified than [the other type],
1258	// [the other type] is not considered to be at least as specialized
1259	// as [the first type]
1260	// Objective-C ARC adds:
1261	// - [one type] has non-trivial lifetime, [the other type] has
1262	// __unsafe_unretained lifetime, and the types are otherwise
1263	// identical
1264	//
1265	// A is "considered to be at least as specialized" as P iff deduction
1266	// succeeds, so we model this as a deduction failure. Note that
1267	// [the first type] is P and [the other type] is A here; the standard
1268	// gets this backwards.
1269	Qualifiers ParamQuals = Param.getQualifiers();
1270	Qualifiers ArgQuals = Arg.getQualifiers();
1271	if ((ParamRef->isLValueReferenceType() &&
1272	!ArgRef->isLValueReferenceType()) \|\|
1273	ParamQuals.isStrictSupersetOf(ArgQuals) \|\|
1274	(ParamQuals.hasNonTrivialObjCLifetime() &&
1275	ArgQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone &&
1276	ParamQuals.withoutObjCLifetime() ==
1277	ArgQuals.withoutObjCLifetime())) {
1278	Info.FirstArg = TemplateArgument(ParamIn);
1279	Info.SecondArg = TemplateArgument(ArgIn);
1280	return Sema::TDK_NonDeducedMismatch;
1281	}
1282	}
1283
1284	// C++11 [temp.deduct.partial]p7:
1285	// Remove any top-level cv-qualifiers:
1286	// - If P is a cv-qualified type, P is replaced by the cv-unqualified
1287	// version of P.
1288	Param = Param.getUnqualifiedType();
1289	// - If A is a cv-qualified type, A is replaced by the cv-unqualified
1290	// version of A.
1291	Arg = Arg.getUnqualifiedType();
1292	} else {
1293	// C++0x [temp.deduct.call]p4 bullet 1:
1294	// - If the original P is a reference type, the deduced A (i.e., the type
1295	// referred to by the reference) can be more cv-qualified than the
1296	// transformed A.
1297	if (TDF & TDF_ParamWithReferenceType) {
1298	Qualifiers Quals;
1299	QualType UnqualParam = S.Context.getUnqualifiedArrayType(Param, Quals);
1300	Quals.setCVRQualifiers(Quals.getCVRQualifiers() &
1301	Arg.getCVRQualifiers());
1302	Param = S.Context.getQualifiedType(UnqualParam, Quals);
1303	}
1304
1305	if ((TDF & TDF_TopLevelParameterTypeList) && !Param->isFunctionType()) {
1306	// C++0x [temp.deduct.type]p10:
1307	// If P and A are function types that originated from deduction when
1308	// taking the address of a function template (14.8.2.2) or when deducing
1309	// template arguments from a function declaration (14.8.2.6) and Pi and
1310	// Ai are parameters of the top-level parameter-type-list of P and A,
1311	// respectively, Pi is adjusted if it is a forwarding reference and Ai
1312	// is an lvalue reference, in
1313	// which case the type of Pi is changed to be the template parameter
1314	// type (i.e., T&& is changed to simply T). [ Note: As a result, when
1315	// Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be
1316	// deduced as X&. - end note ]
1317	TDF &= ~TDF_TopLevelParameterTypeList;
1318	if (isForwardingReference(Param, 0) && Arg->isLValueReferenceType())
1319	Param = Param->getPointeeType();
1320	}
1321	}
1322
1323	// C++ [temp.deduct.type]p9:
1324	// A template type argument T, a template template argument TT or a
1325	// template non-type argument i can be deduced if P and A have one of
1326	// the following forms:
1327	//
1328	// T
1329	// cv-list T
1330	if (const TemplateTypeParmType *TemplateTypeParm
1331	= Param->getAs<TemplateTypeParmType>()) {
1332	// Just skip any attempts to deduce from a placeholder type or a parameter
1333	// at a different depth.
1334	if (Arg->isPlaceholderType() \|\|
1335	Info.getDeducedDepth() != TemplateTypeParm->getDepth())
1336	return Sema::TDK_Success;
1337
1338	unsigned Index = TemplateTypeParm->getIndex();
1339	bool RecanonicalizeArg = false;
1340
1341	// If the argument type is an array type, move the qualifiers up to the
1342	// top level, so they can be matched with the qualifiers on the parameter.
1343	if (isa<ArrayType>(Arg)) {
1344	Qualifiers Quals;
1345	Arg = S.Context.getUnqualifiedArrayType(Arg, Quals);
1346	if (Quals) {
1347	Arg = S.Context.getQualifiedType(Arg, Quals);
1348	RecanonicalizeArg = true;
1349	}
1350	}
1351
1352	// The argument type can not be less qualified than the parameter
1353	// type.
1354	if (!(TDF & TDF_IgnoreQualifiers) &&
1355	hasInconsistentOrSupersetQualifiersOf(Param, Arg)) {
1356	Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1357	Info.FirstArg = TemplateArgument(Param);
1358	Info.SecondArg = TemplateArgument(Arg);
1359	return Sema::TDK_Underqualified;
1360	}
1361
1362	// Do not match a function type with a cv-qualified type.
1363	// http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1584
1364	if (Arg->isFunctionType() && Param.hasQualifiers()) {
1365	return Sema::TDK_NonDeducedMismatch;
1366	}
1367
1368	(0) . __assert_fail ("TemplateTypeParm->getDepth() == Info.getDeducedDepth() && \"saw template type parameter with wrong depth\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 1369, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(TemplateTypeParm->getDepth() == Info.getDeducedDepth() &&
1369	(0) . __assert_fail ("TemplateTypeParm->getDepth() == Info.getDeducedDepth() && \"saw template type parameter with wrong depth\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 1369, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "saw template type parameter with wrong depth");
1370	(0) . __assert_fail ("Arg != S.Context.OverloadTy && \"Unresolved overloaded function\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 1370, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(Arg != S.Context.OverloadTy && "Unresolved overloaded function");
1371	QualType DeducedType = Arg;
1372
1373	// Remove any qualifiers on the parameter from the deduced type.
1374	// We checked the qualifiers for consistency above.
1375	Qualifiers DeducedQs = DeducedType.getQualifiers();
1376	Qualifiers ParamQs = Param.getQualifiers();
1377	DeducedQs.removeCVRQualifiers(ParamQs.getCVRQualifiers());
1378	if (ParamQs.hasObjCGCAttr())
1379	DeducedQs.removeObjCGCAttr();
1380	if (ParamQs.hasAddressSpace())
1381	DeducedQs.removeAddressSpace();
1382	if (ParamQs.hasObjCLifetime())
1383	DeducedQs.removeObjCLifetime();
1384
1385	// Objective-C ARC:
1386	// If template deduction would produce a lifetime qualifier on a type
1387	// that is not a lifetime type, template argument deduction fails.
1388	if (ParamQs.hasObjCLifetime() && !DeducedType->isObjCLifetimeType() &&
1389	!DeducedType->isDependentType()) {
1390	Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1391	Info.FirstArg = TemplateArgument(Param);
1392	Info.SecondArg = TemplateArgument(Arg);
1393	return Sema::TDK_Underqualified;
1394	}
1395
1396	// Objective-C ARC:
1397	// If template deduction would produce an argument type with lifetime type
1398	// but no lifetime qualifier, the __strong lifetime qualifier is inferred.
1399	if (S.getLangOpts().ObjCAutoRefCount &&
1400	DeducedType->isObjCLifetimeType() &&
1401	!DeducedQs.hasObjCLifetime())
1402	DeducedQs.setObjCLifetime(Qualifiers::OCL_Strong);
1403
1404	DeducedType = S.Context.getQualifiedType(DeducedType.getUnqualifiedType(),
1405	DeducedQs);
1406
1407	if (RecanonicalizeArg)
1408	DeducedType = S.Context.getCanonicalType(DeducedType);
1409
1410	DeducedTemplateArgument NewDeduced(DeducedType, DeducedFromArrayBound);
1411	DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
1412	Deduced[Index],
1413	NewDeduced);
1414	if (Result.isNull()) {
1415	Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1416	Info.FirstArg = Deduced[Index];
1417	Info.SecondArg = NewDeduced;
1418	return Sema::TDK_Inconsistent;
1419	}
1420
1421	Deduced[Index] = Result;
1422	return Sema::TDK_Success;
1423	}
1424
1425	// Set up the template argument deduction information for a failure.
1426	Info.FirstArg = TemplateArgument(ParamIn);
1427	Info.SecondArg = TemplateArgument(ArgIn);
1428
1429	// If the parameter is an already-substituted template parameter
1430	// pack, do nothing: we don't know which of its arguments to look
1431	// at, so we have to wait until all of the parameter packs in this
1432	// expansion have arguments.
1433	if (isa<SubstTemplateTypeParmPackType>(Param))
1434	return Sema::TDK_Success;
1435
1436	// Check the cv-qualifiers on the parameter and argument types.
1437	CanQualType CanParam = S.Context.getCanonicalType(Param);
1438	CanQualType CanArg = S.Context.getCanonicalType(Arg);
1439	if (!(TDF & TDF_IgnoreQualifiers)) {
1440	if (TDF & TDF_ParamWithReferenceType) {
1441	if (hasInconsistentOrSupersetQualifiersOf(Param, Arg))
1442	return Sema::TDK_NonDeducedMismatch;
1443	} else if (TDF & TDF_ArgWithReferenceType) {
1444	// C++ [temp.deduct.conv]p4:
1445	// If the original A is a reference type, A can be more cv-qualified
1446	// than the deduced A
1447	if (!Arg.getQualifiers().compatiblyIncludes(Param.getQualifiers()))
1448	return Sema::TDK_NonDeducedMismatch;
1449
1450	// Strip out all extra qualifiers from the argument to figure out the
1451	// type we're converting to, prior to the qualification conversion.
1452	Qualifiers Quals;
1453	Arg = S.Context.getUnqualifiedArrayType(Arg, Quals);
1454	Arg = S.Context.getQualifiedType(Arg, Param.getQualifiers());
1455	} else if (!IsPossiblyOpaquelyQualifiedType(Param)) {
1456	if (Param.getCVRQualifiers() != Arg.getCVRQualifiers())
1457	return Sema::TDK_NonDeducedMismatch;
1458	}
1459
1460	// If the parameter type is not dependent, there is nothing to deduce.
1461	if (!Param->isDependentType()) {
1462	if (!(TDF & TDF_SkipNonDependent)) {
1463	bool NonDeduced =
1464	(TDF & TDF_AllowCompatibleFunctionType)
1465	? !S.isSameOrCompatibleFunctionType(CanParam, CanArg)
1466	: Param != Arg;
1467	if (NonDeduced) {
1468	return Sema::TDK_NonDeducedMismatch;
1469	}
1470	}
1471	return Sema::TDK_Success;
1472	}
1473	} else if (!Param->isDependentType()) {
1474	CanQualType ParamUnqualType = CanParam.getUnqualifiedType(),
1475	ArgUnqualType = CanArg.getUnqualifiedType();
1476	bool Success =
1477	(TDF & TDF_AllowCompatibleFunctionType)
1478	? S.isSameOrCompatibleFunctionType(ParamUnqualType, ArgUnqualType)
1479	: ParamUnqualType == ArgUnqualType;
1480	if (Success)
1481	return Sema::TDK_Success;
1482	}
1483
1484	switch (Param->getTypeClass()) {
1485	// Non-canonical types cannot appear here.
1486	#define NON_CANONICAL_TYPE(Class, Base) \
1487	case Type::Class: llvm_unreachable("deducing non-canonical type: " #Class);
1488	#define TYPE(Class, Base)
1489	#include "clang/AST/TypeNodes.def"
1490
1491	case Type::TemplateTypeParm:
1492	case Type::SubstTemplateTypeParmPack:
1493	llvm_unreachable("Type nodes handled above");
1494
1495	// These types cannot be dependent, so simply check whether the types are
1496	// the same.
1497	case Type::Builtin:
1498	case Type::VariableArray:
1499	case Type::Vector:
1500	case Type::FunctionNoProto:
1501	case Type::Record:
1502	case Type::Enum:
1503	case Type::ObjCObject:
1504	case Type::ObjCInterface:
1505	case Type::ObjCObjectPointer:
1506	if (TDF & TDF_SkipNonDependent)
1507	return Sema::TDK_Success;
1508
1509	if (TDF & TDF_IgnoreQualifiers) {
1510	Param = Param.getUnqualifiedType();
1511	Arg = Arg.getUnqualifiedType();
1512	}
1513
1514	return Param == Arg? Sema::TDK_Success : Sema::TDK_NonDeducedMismatch;
1515
1516	// _Complex T [placeholder extension]
1517	case Type::Complex:
1518	if (const ComplexType *ComplexArg = Arg->getAs<ComplexType>())
1519	return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1520	cast<ComplexType>(Param)->getElementType(),
1521	ComplexArg->getElementType(),
1522	Info, Deduced, TDF);
1523
1524	return Sema::TDK_NonDeducedMismatch;
1525
1526	// _Atomic T [extension]
1527	case Type::Atomic:
1528	if (const AtomicType *AtomicArg = Arg->getAs<AtomicType>())
1529	return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1530	cast<AtomicType>(Param)->getValueType(),
1531	AtomicArg->getValueType(),
1532	Info, Deduced, TDF);
1533
1534	return Sema::TDK_NonDeducedMismatch;
1535
1536	// T *
1537	case Type::Pointer: {
1538	QualType PointeeType;
1539	if (const PointerType *PointerArg = Arg->getAs<PointerType>()) {
1540	PointeeType = PointerArg->getPointeeType();
1541	} else if (const ObjCObjectPointerType *PointerArg
1542	= Arg->getAs<ObjCObjectPointerType>()) {
1543	PointeeType = PointerArg->getPointeeType();
1544	} else {
1545	return Sema::TDK_NonDeducedMismatch;
1546	}
1547
1548	unsigned SubTDF = TDF & (TDF_IgnoreQualifiers \| TDF_DerivedClass);
1549	return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1550	cast<PointerType>(Param)->getPointeeType(),
1551	PointeeType,
1552	Info, Deduced, SubTDF);
1553	}
1554
1555	// T &
1556	case Type::LValueReference: {
1557	const LValueReferenceType *ReferenceArg =
1558	Arg->getAs<LValueReferenceType>();
1559	if (!ReferenceArg)
1560	return Sema::TDK_NonDeducedMismatch;
1561
1562	return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1563	cast<LValueReferenceType>(Param)->getPointeeType(),
1564	ReferenceArg->getPointeeType(), Info, Deduced, 0);
1565	}
1566
1567	// T && [C++0x]
1568	case Type::RValueReference: {
1569	const RValueReferenceType *ReferenceArg =
1570	Arg->getAs<RValueReferenceType>();
1571	if (!ReferenceArg)
1572	return Sema::TDK_NonDeducedMismatch;
1573
1574	return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1575	cast<RValueReferenceType>(Param)->getPointeeType(),
1576	ReferenceArg->getPointeeType(),
1577	Info, Deduced, 0);
1578	}
1579
1580	// T [] (implied, but not stated explicitly)
1581	case Type::IncompleteArray: {
1582	const IncompleteArrayType *IncompleteArrayArg =
1583	S.Context.getAsIncompleteArrayType(Arg);
1584	if (!IncompleteArrayArg)
1585	return Sema::TDK_NonDeducedMismatch;
1586
1587	unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1588	return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1589	S.Context.getAsIncompleteArrayType(Param)->getElementType(),
1590	IncompleteArrayArg->getElementType(),
1591	Info, Deduced, SubTDF);
1592	}
1593
1594	// T [integer-constant]
1595	case Type::ConstantArray: {
1596	const ConstantArrayType *ConstantArrayArg =
1597	S.Context.getAsConstantArrayType(Arg);
1598	if (!ConstantArrayArg)
1599	return Sema::TDK_NonDeducedMismatch;
1600
1601	const ConstantArrayType *ConstantArrayParm =
1602	S.Context.getAsConstantArrayType(Param);
1603	if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize())
1604	return Sema::TDK_NonDeducedMismatch;
1605
1606	unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1607	return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1608	ConstantArrayParm->getElementType(),
1609	ConstantArrayArg->getElementType(),
1610	Info, Deduced, SubTDF);
1611	}
1612
1613	// type [i]
1614	case Type::DependentSizedArray: {
1615	const ArrayType *ArrayArg = S.Context.getAsArrayType(Arg);
1616	if (!ArrayArg)
1617	return Sema::TDK_NonDeducedMismatch;
1618
1619	unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1620
1621	// Check the element type of the arrays
1622	const DependentSizedArrayType *DependentArrayParm
1623	= S.Context.getAsDependentSizedArrayType(Param);
1624	if (Sema::TemplateDeductionResult Result
1625	= DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1626	DependentArrayParm->getElementType(),
1627	ArrayArg->getElementType(),
1628	Info, Deduced, SubTDF))
1629	return Result;
1630
1631	// Determine the array bound is something we can deduce.
1632	NonTypeTemplateParmDecl *NTTP
1633	= getDeducedParameterFromExpr(Info, DependentArrayParm->getSizeExpr());
1634	if (!NTTP)
1635	return Sema::TDK_Success;
1636
1637	// We can perform template argument deduction for the given non-type
1638	// template parameter.
1639	(0) . __assert_fail ("NTTP->getDepth() == Info.getDeducedDepth() && \"saw non-type template parameter with wrong depth\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 1640, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(NTTP->getDepth() == Info.getDeducedDepth() &&
1640	(0) . __assert_fail ("NTTP->getDepth() == Info.getDeducedDepth() && \"saw non-type template parameter with wrong depth\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 1640, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "saw non-type template parameter with wrong depth");
1641	if (const ConstantArrayType *ConstantArrayArg
1642	= dyn_cast<ConstantArrayType>(ArrayArg)) {
1643	llvm::APSInt Size(ConstantArrayArg->getSize());
1644	return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, Size,
1645	S.Context.getSizeType(),
1646	/ArrayBound=/true,
1647	Info, Deduced);
1648	}
1649	if (const DependentSizedArrayType *DependentArrayArg
1650	= dyn_cast<DependentSizedArrayType>(ArrayArg))
1651	if (DependentArrayArg->getSizeExpr())
1652	return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
1653	DependentArrayArg->getSizeExpr(),
1654	Info, Deduced);
1655
1656	// Incomplete type does not match a dependently-sized array type
1657	return Sema::TDK_NonDeducedMismatch;
1658	}
1659
1660	// type(*)(T)
1661	// T(*)()
1662	// T(*)(T)
1663	case Type::FunctionProto: {
1664	unsigned SubTDF = TDF & TDF_TopLevelParameterTypeList;
1665	const FunctionProtoType *FunctionProtoArg =
1666	dyn_cast<FunctionProtoType>(Arg);
1667	if (!FunctionProtoArg)
1668	return Sema::TDK_NonDeducedMismatch;
1669
1670	const FunctionProtoType *FunctionProtoParam =
1671	cast<FunctionProtoType>(Param);
1672
1673	if (FunctionProtoParam->getMethodQuals()
1674	!= FunctionProtoArg->getMethodQuals() \|\|
1675	FunctionProtoParam->getRefQualifier()
1676	!= FunctionProtoArg->getRefQualifier() \|\|
1677	FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic())
1678	return Sema::TDK_NonDeducedMismatch;
1679
1680	// Check return types.
1681	if (auto Result = DeduceTemplateArgumentsByTypeMatch(
1682	S, TemplateParams, FunctionProtoParam->getReturnType(),
1683	FunctionProtoArg->getReturnType(), Info, Deduced, 0))
1684	return Result;
1685
1686	// Check parameter types.
1687	if (auto Result = DeduceTemplateArguments(
1688	S, TemplateParams, FunctionProtoParam->param_type_begin(),
1689	FunctionProtoParam->getNumParams(),
1690	FunctionProtoArg->param_type_begin(),
1691	FunctionProtoArg->getNumParams(), Info, Deduced, SubTDF))
1692	return Result;
1693
1694	if (TDF & TDF_AllowCompatibleFunctionType)
1695	return Sema::TDK_Success;
1696
1697	// FIXME: Per core-2016/10/1019 (no corresponding core issue yet), permit
1698	// deducing through the noexcept-specifier if it's part of the canonical
1699	// type. libstdc++ relies on this.
1700	Expr *NoexceptExpr = FunctionProtoParam->getNoexceptExpr();
1701	if (NonTypeTemplateParmDecl *NTTP =
1702	NoexceptExpr ? getDeducedParameterFromExpr(Info, NoexceptExpr)
1703	: nullptr) {
1704	(0) . __assert_fail ("NTTP->getDepth() == Info.getDeducedDepth() && \"saw non-type template parameter with wrong depth\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 1705, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(NTTP->getDepth() == Info.getDeducedDepth() &&
1705	(0) . __assert_fail ("NTTP->getDepth() == Info.getDeducedDepth() && \"saw non-type template parameter with wrong depth\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 1705, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "saw non-type template parameter with wrong depth");
1706
1707	llvm::APSInt Noexcept(1);
1708	switch (FunctionProtoArg->canThrow()) {
1709	case CT_Cannot:
1710	Noexcept = 1;
1711	LLVM_FALLTHROUGH;
1712
1713	case CT_Can:
1714	// We give E in noexcept(E) the "deduced from array bound" treatment.
1715	// FIXME: Should we?
1716	return DeduceNonTypeTemplateArgument(
1717	S, TemplateParams, NTTP, Noexcept, S.Context.BoolTy,
1718	/ArrayBound/true, Info, Deduced);
1719
1720	case CT_Dependent:
1721	if (Expr *ArgNoexceptExpr = FunctionProtoArg->getNoexceptExpr())
1722	return DeduceNonTypeTemplateArgument(
1723	S, TemplateParams, NTTP, ArgNoexceptExpr, Info, Deduced);
1724	// Can't deduce anything from throw(T...).
1725	break;
1726	}
1727	}
1728	// FIXME: Detect non-deduced exception specification mismatches?
1729	//
1730	// Careful about [temp.deduct.call] and [temp.deduct.conv], which allow
1731	// top-level differences in noexcept-specifications.
1732
1733	return Sema::TDK_Success;
1734	}
1735
1736	case Type::InjectedClassName:
1737	// Treat a template's injected-class-name as if the template
1738	// specialization type had been used.
1739	Param = cast<InjectedClassNameType>(Param)
1740	->getInjectedSpecializationType();
1741	(0) . __assert_fail ("isa(Param) && \"injected class name is not a template specialization type\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 1742, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(isa<TemplateSpecializationType>(Param) &&
1742	(0) . __assert_fail ("isa(Param) && \"injected class name is not a template specialization type\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 1742, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "injected class name is not a template specialization type");
1743	LLVM_FALLTHROUGH;
1744
1745	// template-name<T> (where template-name refers to a class template)
1746	// template-name<i>
1747	// TT<T>
1748	// TT<i>
1749	// TT<>
1750	case Type::TemplateSpecialization: {
1751	const TemplateSpecializationType *SpecParam =
1752	cast<TemplateSpecializationType>(Param);
1753
1754	// When Arg cannot be a derived class, we can just try to deduce template
1755	// arguments from the template-id.
1756	const RecordType *RecordT = Arg->getAs<RecordType>();
1757	if (!(TDF & TDF_DerivedClass) \|\| !RecordT)
1758	return DeduceTemplateArguments(S, TemplateParams, SpecParam, Arg, Info,
1759	Deduced);
1760
1761	SmallVector<DeducedTemplateArgument, 8> DeducedOrig(Deduced.begin(),
1762	Deduced.end());
1763
1764	Sema::TemplateDeductionResult Result = DeduceTemplateArguments(
1765	S, TemplateParams, SpecParam, Arg, Info, Deduced);
1766
1767	if (Result == Sema::TDK_Success)
1768	return Result;
1769
1770	// We cannot inspect base classes as part of deduction when the type
1771	// is incomplete, so either instantiate any templates necessary to
1772	// complete the type, or skip over it if it cannot be completed.
1773	if (!S.isCompleteType(Info.getLocation(), Arg))
1774	return Result;
1775
1776	// C++14 [temp.deduct.call] p4b3:
1777	// If P is a class and P has the form simple-template-id, then the
1778	// transformed A can be a derived class of the deduced A. Likewise if
1779	// P is a pointer to a class of the form simple-template-id, the
1780	// transformed A can be a pointer to a derived class pointed to by the
1781	// deduced A.
1782	//
1783	// These alternatives are considered only if type deduction would
1784	// otherwise fail. If they yield more than one possible deduced A, the
1785	// type deduction fails.
1786
1787	// Reset the incorrectly deduced argument from above.
1788	Deduced = DeducedOrig;
1789
1790	// Use data recursion to crawl through the list of base classes.
1791	// Visited contains the set of nodes we have already visited, while
1792	// ToVisit is our stack of records that we still need to visit.
1793	llvm::SmallPtrSet<const RecordType *, 8> Visited;
1794	SmallVector<const RecordType *, 8> ToVisit;
1795	ToVisit.push_back(RecordT);
1796	bool Successful = false;
1797	SmallVector<DeducedTemplateArgument, 8> SuccessfulDeduced;
1798	while (!ToVisit.empty()) {
1799	// Retrieve the next class in the inheritance hierarchy.
1800	const RecordType *NextT = ToVisit.pop_back_val();
1801
1802	// If we have already seen this type, skip it.
1803	if (!Visited.insert(NextT).second)
1804	continue;
1805
1806	// If this is a base class, try to perform template argument
1807	// deduction from it.
1808	if (NextT != RecordT) {
1809	TemplateDeductionInfo BaseInfo(Info.getLocation());
1810	Sema::TemplateDeductionResult BaseResult =
1811	DeduceTemplateArguments(S, TemplateParams, SpecParam,
1812	QualType(NextT, 0), BaseInfo, Deduced);
1813
1814	// If template argument deduction for this base was successful,
1815	// note that we had some success. Otherwise, ignore any deductions
1816	// from this base class.
1817	if (BaseResult == Sema::TDK_Success) {
1818	// If we've already seen some success, then deduction fails due to
1819	// an ambiguity (temp.deduct.call p5).
1820	if (Successful)
1821	return Sema::TDK_MiscellaneousDeductionFailure;
1822
1823	Successful = true;
1824	std::swap(SuccessfulDeduced, Deduced);
1825
1826	Info.Param = BaseInfo.Param;
1827	Info.FirstArg = BaseInfo.FirstArg;
1828	Info.SecondArg = BaseInfo.SecondArg;
1829	}
1830
1831	Deduced = DeducedOrig;
1832	}
1833
1834	// Visit base classes
1835	CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl());
1836	for (const auto &Base : Next->bases()) {
1837	(0) . __assert_fail ("Base.getType()->isRecordType() && \"Base class that isn't a record?\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 1838, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(Base.getType()->isRecordType() &&
1838	(0) . __assert_fail ("Base.getType()->isRecordType() && \"Base class that isn't a record?\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 1838, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "Base class that isn't a record?");
1839	ToVisit.push_back(Base.getType()->getAs<RecordType>());
1840	}
1841	}
1842
1843	if (Successful) {
1844	std::swap(SuccessfulDeduced, Deduced);
1845	return Sema::TDK_Success;
1846	}
1847
1848	return Result;
1849	}
1850
1851	// T type::*
1852	// T T::*
1853	// T (type::*)()
1854	// type (T::*)()
1855	// type (type::*)(T)
1856	// type (T::*)(T)
1857	// T (type::*)(T)
1858	// T (T::*)()
1859	// T (T::*)(T)
1860	case Type::MemberPointer: {
1861	const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param);
1862	const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg);
1863	if (!MemPtrArg)
1864	return Sema::TDK_NonDeducedMismatch;
1865
1866	QualType ParamPointeeType = MemPtrParam->getPointeeType();
1867	if (ParamPointeeType->isFunctionType())
1868	S.adjustMemberFunctionCC(ParamPointeeType, /IsStatic=/true,
1869	/IsCtorOrDtor=/false, Info.getLocation());
1870	QualType ArgPointeeType = MemPtrArg->getPointeeType();
1871	if (ArgPointeeType->isFunctionType())
1872	S.adjustMemberFunctionCC(ArgPointeeType, /IsStatic=/true,
1873	/IsCtorOrDtor=/false, Info.getLocation());
1874
1875	if (Sema::TemplateDeductionResult Result
1876	= DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1877	ParamPointeeType,
1878	ArgPointeeType,
1879	Info, Deduced,
1880	TDF & TDF_IgnoreQualifiers))
1881	return Result;
1882
1883	return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1884	QualType(MemPtrParam->getClass(), 0),
1885	QualType(MemPtrArg->getClass(), 0),
1886	Info, Deduced,
1887	TDF & TDF_IgnoreQualifiers);
1888	}
1889
1890	// (clang extension)
1891	//
1892	// type(^)(T)
1893	// T(^)()
1894	// T(^)(T)
1895	case Type::BlockPointer: {
1896	const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param);
1897	const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg);
1898
1899	if (!BlockPtrArg)
1900	return Sema::TDK_NonDeducedMismatch;
1901
1902	return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1903	BlockPtrParam->getPointeeType(),
1904	BlockPtrArg->getPointeeType(),
1905	Info, Deduced, 0);
1906	}
1907
1908	// (clang extension)
1909	//
1910	// T __attribute__(((ext_vector_type(<integral constant>))))
1911	case Type::ExtVector: {
1912	const ExtVectorType *VectorParam = cast<ExtVectorType>(Param);
1913	if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1914	// Make sure that the vectors have the same number of elements.
1915	if (VectorParam->getNumElements() != VectorArg->getNumElements())
1916	return Sema::TDK_NonDeducedMismatch;
1917
1918	// Perform deduction on the element types.
1919	return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1920	VectorParam->getElementType(),
1921	VectorArg->getElementType(),
1922	Info, Deduced, TDF);
1923	}
1924
1925	if (const DependentSizedExtVectorType *VectorArg
1926	= dyn_cast<DependentSizedExtVectorType>(Arg)) {
1927	// We can't check the number of elements, since the argument has a
1928	// dependent number of elements. This can only occur during partial
1929	// ordering.
1930
1931	// Perform deduction on the element types.
1932	return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1933	VectorParam->getElementType(),
1934	VectorArg->getElementType(),
1935	Info, Deduced, TDF);
1936	}
1937
1938	return Sema::TDK_NonDeducedMismatch;
1939	}
1940
1941	case Type::DependentVector: {
1942	const auto *VectorParam = cast<DependentVectorType>(Param);
1943
1944	if (const auto *VectorArg = dyn_cast<VectorType>(Arg)) {
1945	// Perform deduction on the element types.
1946	if (Sema::TemplateDeductionResult Result =
1947	DeduceTemplateArgumentsByTypeMatch(
1948	S, TemplateParams, VectorParam->getElementType(),
1949	VectorArg->getElementType(), Info, Deduced, TDF))
1950	return Result;
1951
1952	// Perform deduction on the vector size, if we can.
1953	NonTypeTemplateParmDecl *NTTP =
1954	getDeducedParameterFromExpr(Info, VectorParam->getSizeExpr());
1955	if (!NTTP)
1956	return Sema::TDK_Success;
1957
1958	llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
1959	ArgSize = VectorArg->getNumElements();
1960	// Note that we use the "array bound" rules here; just like in that
1961	// case, we don't have any particular type for the vector size, but
1962	// we can provide one if necessary.
1963	return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
1964	S.Context.UnsignedIntTy, true,
1965	Info, Deduced);
1966	}
1967
1968	if (const auto *VectorArg = dyn_cast<DependentVectorType>(Arg)) {
1969	// Perform deduction on the element types.
1970	if (Sema::TemplateDeductionResult Result =
1971	DeduceTemplateArgumentsByTypeMatch(
1972	S, TemplateParams, VectorParam->getElementType(),
1973	VectorArg->getElementType(), Info, Deduced, TDF))
1974	return Result;
1975
1976	// Perform deduction on the vector size, if we can.
1977	NonTypeTemplateParmDecl *NTTP = getDeducedParameterFromExpr(
1978	Info, VectorParam->getSizeExpr());
1979	if (!NTTP)
1980	return Sema::TDK_Success;
1981
1982	return DeduceNonTypeTemplateArgument(
1983	S, TemplateParams, NTTP, VectorArg->getSizeExpr(), Info, Deduced);
1984	}
1985
1986	return Sema::TDK_NonDeducedMismatch;
1987	}
1988
1989	// (clang extension)
1990	//
1991	// T __attribute__(((ext_vector_type(N))))
1992	case Type::DependentSizedExtVector: {
1993	const DependentSizedExtVectorType *VectorParam
1994	= cast<DependentSizedExtVectorType>(Param);
1995
1996	if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1997	// Perform deduction on the element types.
1998	if (Sema::TemplateDeductionResult Result
1999	= DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
2000	VectorParam->getElementType(),
2001	VectorArg->getElementType(),
2002	Info, Deduced, TDF))
2003	return Result;
2004
2005	// Perform deduction on the vector size, if we can.
2006	NonTypeTemplateParmDecl *NTTP
2007	= getDeducedParameterFromExpr(Info, VectorParam->getSizeExpr());
2008	if (!NTTP)
2009	return Sema::TDK_Success;
2010
2011	llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
2012	ArgSize = VectorArg->getNumElements();
2013	// Note that we use the "array bound" rules here; just like in that
2014	// case, we don't have any particular type for the vector size, but
2015	// we can provide one if necessary.
2016	return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
2017	S.Context.IntTy, true, Info,
2018	Deduced);
2019	}
2020
2021	if (const DependentSizedExtVectorType *VectorArg
2022	= dyn_cast<DependentSizedExtVectorType>(Arg)) {
2023	// Perform deduction on the element types.
2024	if (Sema::TemplateDeductionResult Result
2025	= DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
2026	VectorParam->getElementType(),
2027	VectorArg->getElementType(),
2028	Info, Deduced, TDF))
2029	return Result;
2030
2031	// Perform deduction on the vector size, if we can.
2032	NonTypeTemplateParmDecl *NTTP
2033	= getDeducedParameterFromExpr(Info, VectorParam->getSizeExpr());
2034	if (!NTTP)
2035	return Sema::TDK_Success;
2036
2037	return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2038	VectorArg->getSizeExpr(),
2039	Info, Deduced);
2040	}
2041
2042	return Sema::TDK_NonDeducedMismatch;
2043	}
2044
2045	// (clang extension)
2046	//
2047	// T __attribute__(((address_space(N))))
2048	case Type::DependentAddressSpace: {
2049	const DependentAddressSpaceType *AddressSpaceParam =
2050	cast<DependentAddressSpaceType>(Param);
2051
2052	if (const DependentAddressSpaceType *AddressSpaceArg =
2053	dyn_cast<DependentAddressSpaceType>(Arg)) {
2054	// Perform deduction on the pointer type.
2055	if (Sema::TemplateDeductionResult Result =
2056	DeduceTemplateArgumentsByTypeMatch(
2057	S, TemplateParams, AddressSpaceParam->getPointeeType(),
2058	AddressSpaceArg->getPointeeType(), Info, Deduced, TDF))
2059	return Result;
2060
2061	// Perform deduction on the address space, if we can.
2062	NonTypeTemplateParmDecl *NTTP = getDeducedParameterFromExpr(
2063	Info, AddressSpaceParam->getAddrSpaceExpr());
2064	if (!NTTP)
2065	return Sema::TDK_Success;
2066
2067	return DeduceNonTypeTemplateArgument(
2068	S, TemplateParams, NTTP, AddressSpaceArg->getAddrSpaceExpr(), Info,
2069	Deduced);
2070	}
2071
2072	if (isTargetAddressSpace(Arg.getAddressSpace())) {
2073	llvm::APSInt ArgAddressSpace(S.Context.getTypeSize(S.Context.IntTy),
2074	false);
2075	ArgAddressSpace = toTargetAddressSpace(Arg.getAddressSpace());
2076
2077	// Perform deduction on the pointer types.
2078	if (Sema::TemplateDeductionResult Result =
2079	DeduceTemplateArgumentsByTypeMatch(
2080	S, TemplateParams, AddressSpaceParam->getPointeeType(),
2081	S.Context.removeAddrSpaceQualType(Arg), Info, Deduced, TDF))
2082	return Result;
2083
2084	// Perform deduction on the address space, if we can.
2085	NonTypeTemplateParmDecl *NTTP = getDeducedParameterFromExpr(
2086	Info, AddressSpaceParam->getAddrSpaceExpr());
2087	if (!NTTP)
2088	return Sema::TDK_Success;
2089
2090	return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2091	ArgAddressSpace, S.Context.IntTy,
2092	true, Info, Deduced);
2093	}
2094
2095	return Sema::TDK_NonDeducedMismatch;
2096	}
2097
2098	case Type::TypeOfExpr:
2099	case Type::TypeOf:
2100	case Type::DependentName:
2101	case Type::UnresolvedUsing:
2102	case Type::Decltype:
2103	case Type::UnaryTransform:
2104	case Type::Auto:
2105	case Type::DeducedTemplateSpecialization:
2106	case Type::DependentTemplateSpecialization:
2107	case Type::PackExpansion:
2108	case Type::Pipe:
2109	// No template argument deduction for these types
2110	return Sema::TDK_Success;
2111	}
2112
2113	llvm_unreachable("Invalid Type Class!");
2114	}
2115
2116	static Sema::TemplateDeductionResult
2117	DeduceTemplateArguments(Sema &S,
2118	TemplateParameterList *TemplateParams,
2119	const TemplateArgument &Param,
2120	TemplateArgument Arg,
2121	TemplateDeductionInfo &Info,
2122	SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
2123	// If the template argument is a pack expansion, perform template argument
2124	// deduction against the pattern of that expansion. This only occurs during
2125	// partial ordering.
2126	if (Arg.isPackExpansion())
2127	Arg = Arg.getPackExpansionPattern();
2128
2129	switch (Param.getKind()) {
2130	case TemplateArgument::Null:
2131	llvm_unreachable("Null template argument in parameter list");
2132
2133	case TemplateArgument::Type:
2134	if (Arg.getKind() == TemplateArgument::Type)
2135	return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
2136	Param.getAsType(),
2137	Arg.getAsType(),
2138	Info, Deduced, 0);
2139	Info.FirstArg = Param;
2140	Info.SecondArg = Arg;
2141	return Sema::TDK_NonDeducedMismatch;
2142
2143	case TemplateArgument::Template:
2144	if (Arg.getKind() == TemplateArgument::Template)
2145	return DeduceTemplateArguments(S, TemplateParams,
2146	Param.getAsTemplate(),
2147	Arg.getAsTemplate(), Info, Deduced);
2148	Info.FirstArg = Param;
2149	Info.SecondArg = Arg;
2150	return Sema::TDK_NonDeducedMismatch;
2151
2152	case TemplateArgument::TemplateExpansion:
2153	llvm_unreachable("caller should handle pack expansions");
2154
2155	case TemplateArgument::Declaration:
2156	if (Arg.getKind() == TemplateArgument::Declaration &&
2157	isSameDeclaration(Param.getAsDecl(), Arg.getAsDecl()))
2158	return Sema::TDK_Success;
2159
2160	Info.FirstArg = Param;
2161	Info.SecondArg = Arg;
2162	return Sema::TDK_NonDeducedMismatch;
2163
2164	case TemplateArgument::NullPtr:
2165	if (Arg.getKind() == TemplateArgument::NullPtr &&
2166	S.Context.hasSameType(Param.getNullPtrType(), Arg.getNullPtrType()))
2167	return Sema::TDK_Success;
2168
2169	Info.FirstArg = Param;
2170	Info.SecondArg = Arg;
2171	return Sema::TDK_NonDeducedMismatch;
2172
2173	case TemplateArgument::Integral:
2174	if (Arg.getKind() == TemplateArgument::Integral) {
2175	if (hasSameExtendedValue(Param.getAsIntegral(), Arg.getAsIntegral()))
2176	return Sema::TDK_Success;
2177
2178	Info.FirstArg = Param;
2179	Info.SecondArg = Arg;
2180	return Sema::TDK_NonDeducedMismatch;
2181	}
2182
2183	if (Arg.getKind() == TemplateArgument::Expression) {
2184	Info.FirstArg = Param;
2185	Info.SecondArg = Arg;
2186	return Sema::TDK_NonDeducedMismatch;
2187	}
2188
2189	Info.FirstArg = Param;
2190	Info.SecondArg = Arg;
2191	return Sema::TDK_NonDeducedMismatch;
2192
2193	case TemplateArgument::Expression:
2194	if (NonTypeTemplateParmDecl *NTTP
2195	= getDeducedParameterFromExpr(Info, Param.getAsExpr())) {
2196	if (Arg.getKind() == TemplateArgument::Integral)
2197	return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2198	Arg.getAsIntegral(),
2199	Arg.getIntegralType(),
2200	/ArrayBound=/false,
2201	Info, Deduced);
2202	if (Arg.getKind() == TemplateArgument::NullPtr)
2203	return DeduceNullPtrTemplateArgument(S, TemplateParams, NTTP,
2204	Arg.getNullPtrType(),
2205	Info, Deduced);
2206	if (Arg.getKind() == TemplateArgument::Expression)
2207	return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2208	Arg.getAsExpr(), Info, Deduced);
2209	if (Arg.getKind() == TemplateArgument::Declaration)
2210	return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2211	Arg.getAsDecl(),
2212	Arg.getParamTypeForDecl(),
2213	Info, Deduced);
2214
2215	Info.FirstArg = Param;
2216	Info.SecondArg = Arg;
2217	return Sema::TDK_NonDeducedMismatch;
2218	}
2219
2220	// Can't deduce anything, but that's okay.
2221	return Sema::TDK_Success;
2222
2223	case TemplateArgument::Pack:
2224	llvm_unreachable("Argument packs should be expanded by the caller!");
2225	}
2226
2227	llvm_unreachable("Invalid TemplateArgument Kind!");
2228	}
2229
2230	/// Determine whether there is a template argument to be used for
2231	/// deduction.
2232	///
2233	/// This routine "expands" argument packs in-place, overriding its input
2234	/// parameters so that \c Args[ArgIdx] will be the available template argument.
2235	///
2236	/// \returns true if there is another template argument (which will be at
2237	/// \c Args[ArgIdx]), false otherwise.
2238	static bool hasTemplateArgumentForDeduction(ArrayRef<TemplateArgument> &Args,
2239	unsigned &ArgIdx) {
2240	if (ArgIdx == Args.size())
2241	return false;
2242
2243	const TemplateArgument &Arg = Args[ArgIdx];
2244	if (Arg.getKind() != TemplateArgument::Pack)
2245	return true;
2246
2247	(0) . __assert_fail ("ArgIdx == Args.size() - 1 && \"Pack not at the end of argument list?\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 2247, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(ArgIdx == Args.size() - 1 && "Pack not at the end of argument list?");
2248	Args = Arg.pack_elements();
2249	ArgIdx = 0;
2250	return ArgIdx < Args.size();
2251	}
2252
2253	/// Determine whether the given set of template arguments has a pack
2254	/// expansion that is not the last template argument.
2255	static bool hasPackExpansionBeforeEnd(ArrayRef<TemplateArgument> Args) {
2256	bool FoundPackExpansion = false;
2257	for (const auto &A : Args) {
2258	if (FoundPackExpansion)
2259	return true;
2260
2261	if (A.getKind() == TemplateArgument::Pack)
2262	return hasPackExpansionBeforeEnd(A.pack_elements());
2263
2264	// FIXME: If this is a fixed-arity pack expansion from an outer level of
2265	// templates, it should not be treated as a pack expansion.
2266	if (A.isPackExpansion())
2267	FoundPackExpansion = true;
2268	}
2269
2270	return false;
2271	}
2272
2273	static Sema::TemplateDeductionResult
2274	DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams,
2275	ArrayRef<TemplateArgument> Params,
2276	ArrayRef<TemplateArgument> Args,
2277	TemplateDeductionInfo &Info,
2278	SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2279	bool NumberOfArgumentsMustMatch) {
2280	// C++0x [temp.deduct.type]p9:
2281	// If the template argument list of P contains a pack expansion that is not
2282	// the last template argument, the entire template argument list is a
2283	// non-deduced context.
2284	if (hasPackExpansionBeforeEnd(Params))
2285	return Sema::TDK_Success;
2286
2287	// C++0x [temp.deduct.type]p9:
2288	// If P has a form that contains <T> or <i>, then each argument Pi of the
2289	// respective template argument list P is compared with the corresponding
2290	// argument Ai of the corresponding template argument list of A.
2291	unsigned ArgIdx = 0, ParamIdx = 0;
2292	for (; hasTemplateArgumentForDeduction(Params, ParamIdx); ++ParamIdx) {
2293	if (!Params[ParamIdx].isPackExpansion()) {
2294	// The simple case: deduce template arguments by matching Pi and Ai.
2295
2296	// Check whether we have enough arguments.
2297	if (!hasTemplateArgumentForDeduction(Args, ArgIdx))
2298	return NumberOfArgumentsMustMatch
2299	? Sema::TDK_MiscellaneousDeductionFailure
2300	: Sema::TDK_Success;
2301
2302	// C++1z [temp.deduct.type]p9:
2303	// During partial ordering, if Ai was originally a pack expansion [and]
2304	// Pi is not a pack expansion, template argument deduction fails.
2305	if (Args[ArgIdx].isPackExpansion())
2306	return Sema::TDK_MiscellaneousDeductionFailure;
2307
2308	// Perform deduction for this Pi/Ai pair.
2309	if (Sema::TemplateDeductionResult Result
2310	= DeduceTemplateArguments(S, TemplateParams,
2311	Params[ParamIdx], Args[ArgIdx],
2312	Info, Deduced))
2313	return Result;
2314
2315	// Move to the next argument.
2316	++ArgIdx;
2317	continue;
2318	}
2319
2320	// The parameter is a pack expansion.
2321
2322	// C++0x [temp.deduct.type]p9:
2323	// If Pi is a pack expansion, then the pattern of Pi is compared with
2324	// each remaining argument in the template argument list of A. Each
2325	// comparison deduces template arguments for subsequent positions in the
2326	// template parameter packs expanded by Pi.
2327	TemplateArgument Pattern = Params[ParamIdx].getPackExpansionPattern();
2328
2329	// Prepare to deduce the packs within the pattern.
2330	PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
2331
2332	// Keep track of the deduced template arguments for each parameter pack
2333	// expanded by this pack expansion (the outer index) and for each
2334	// template argument (the inner SmallVectors).
2335	for (; hasTemplateArgumentForDeduction(Args, ArgIdx) &&
2336	PackScope.hasNextElement();
2337	++ArgIdx) {
2338	// Deduce template arguments from the pattern.
2339	if (Sema::TemplateDeductionResult Result
2340	= DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx],
2341	Info, Deduced))
2342	return Result;
2343
2344	PackScope.nextPackElement();
2345	}
2346
2347	// Build argument packs for each of the parameter packs expanded by this
2348	// pack expansion.
2349	if (auto Result = PackScope.finish())
2350	return Result;
2351	}
2352
2353	return Sema::TDK_Success;
2354	}
2355
2356	static Sema::TemplateDeductionResult
2357	DeduceTemplateArguments(Sema &S,
2358	TemplateParameterList *TemplateParams,
2359	const TemplateArgumentList &ParamList,
2360	const TemplateArgumentList &ArgList,
2361	TemplateDeductionInfo &Info,
2362	SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
2363	return DeduceTemplateArguments(S, TemplateParams, ParamList.asArray(),
2364	ArgList.asArray(), Info, Deduced,
2365	/NumberOfArgumentsMustMatch/false);
2366	}
2367
2368	/// Determine whether two template arguments are the same.
2369	static bool isSameTemplateArg(ASTContext &Context,
2370	TemplateArgument X,
2371	const TemplateArgument &Y,
2372	bool PackExpansionMatchesPack = false) {
2373	// If we're checking deduced arguments (X) against original arguments (Y),
2374	// we will have flattened packs to non-expansions in X.
2375	if (PackExpansionMatchesPack && X.isPackExpansion() && !Y.isPackExpansion())
2376	X = X.getPackExpansionPattern();
2377
2378	if (X.getKind() != Y.getKind())
2379	return false;
2380
2381	switch (X.getKind()) {
2382	case TemplateArgument::Null:
2383	llvm_unreachable("Comparing NULL template argument");
2384
2385	case TemplateArgument::Type:
2386	return Context.getCanonicalType(X.getAsType()) ==
2387	Context.getCanonicalType(Y.getAsType());
2388
2389	case TemplateArgument::Declaration:
2390	return isSameDeclaration(X.getAsDecl(), Y.getAsDecl());
2391
2392	case TemplateArgument::NullPtr:
2393	return Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType());
2394
2395	case TemplateArgument::Template:
2396	case TemplateArgument::TemplateExpansion:
2397	return Context.getCanonicalTemplateName(
2398	X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() ==
2399	Context.getCanonicalTemplateName(
2400	Y.getAsTemplateOrTemplatePattern()).getAsVoidPointer();
2401
2402	case TemplateArgument::Integral:
2403	return hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral());
2404
2405	case TemplateArgument::Expression: {
2406	llvm::FoldingSetNodeID XID, YID;
2407	X.getAsExpr()->Profile(XID, Context, true);
2408	Y.getAsExpr()->Profile(YID, Context, true);
2409	return XID == YID;
2410	}
2411
2412	case TemplateArgument::Pack:
2413	if (X.pack_size() != Y.pack_size())
2414	return false;
2415
2416	for (TemplateArgument::pack_iterator XP = X.pack_begin(),
2417	XPEnd = X.pack_end(),
2418	YP = Y.pack_begin();
2419	XP != XPEnd; ++XP, ++YP)
2420	if (!isSameTemplateArg(Context, XP, YP, PackExpansionMatchesPack))
2421	return false;
2422
2423	return true;
2424	}
2425
2426	llvm_unreachable("Invalid TemplateArgument Kind!");
2427	}
2428
2429	/// Allocate a TemplateArgumentLoc where all locations have
2430	/// been initialized to the given location.
2431	///
2432	/// \param Arg The template argument we are producing template argument
2433	/// location information for.
2434	///
2435	/// \param NTTPType For a declaration template argument, the type of
2436	/// the non-type template parameter that corresponds to this template
2437	/// argument. Can be null if no type sugar is available to add to the
2438	/// type from the template argument.
2439	///
2440	/// \param Loc The source location to use for the resulting template
2441	/// argument.
2442	TemplateArgumentLoc
2443	Sema::getTrivialTemplateArgumentLoc(const TemplateArgument &Arg,
2444	QualType NTTPType, SourceLocation Loc) {
2445	switch (Arg.getKind()) {
2446	case TemplateArgument::Null:
2447	llvm_unreachable("Can't get a NULL template argument here");
2448
2449	case TemplateArgument::Type:
2450	return TemplateArgumentLoc(
2451	Arg, Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc));
2452
2453	case TemplateArgument::Declaration: {
2454	if (NTTPType.isNull())
2455	NTTPType = Arg.getParamTypeForDecl();
2456	Expr *E = BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2457	.getAs<Expr>();
2458	return TemplateArgumentLoc(TemplateArgument(E), E);
2459	}
2460
2461	case TemplateArgument::NullPtr: {
2462	if (NTTPType.isNull())
2463	NTTPType = Arg.getNullPtrType();
2464	Expr *E = BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2465	.getAs<Expr>();
2466	return TemplateArgumentLoc(TemplateArgument(NTTPType, /isNullPtr/true),
2467	E);
2468	}
2469
2470	case TemplateArgument::Integral: {
2471	Expr *E =
2472	BuildExpressionFromIntegralTemplateArgument(Arg, Loc).getAs<Expr>();
2473	return TemplateArgumentLoc(TemplateArgument(E), E);
2474	}
2475
2476	case TemplateArgument::Template:
2477	case TemplateArgument::TemplateExpansion: {
2478	NestedNameSpecifierLocBuilder Builder;
2479	TemplateName Template = Arg.getAsTemplate();
2480	if (DependentTemplateName *DTN = Template.getAsDependentTemplateName())
2481	Builder.MakeTrivial(Context, DTN->getQualifier(), Loc);
2482	else if (QualifiedTemplateName *QTN =
2483	Template.getAsQualifiedTemplateName())
2484	Builder.MakeTrivial(Context, QTN->getQualifier(), Loc);
2485
2486	if (Arg.getKind() == TemplateArgument::Template)
2487	return TemplateArgumentLoc(Arg, Builder.getWithLocInContext(Context),
2488	Loc);
2489
2490	return TemplateArgumentLoc(Arg, Builder.getWithLocInContext(Context),
2491	Loc, Loc);
2492	}
2493
2494	case TemplateArgument::Expression:
2495	return TemplateArgumentLoc(Arg, Arg.getAsExpr());
2496
2497	case TemplateArgument::Pack:
2498	return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo());
2499	}
2500
2501	llvm_unreachable("Invalid TemplateArgument Kind!");
2502	}
2503
2504	/// Convert the given deduced template argument and add it to the set of
2505	/// fully-converted template arguments.
2506	static bool
2507	ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param,
2508	DeducedTemplateArgument Arg,
2509	NamedDecl *Template,
2510	TemplateDeductionInfo &Info,
2511	bool IsDeduced,
2512	SmallVectorImpl<TemplateArgument> &Output) {
2513	auto ConvertArg = [&](DeducedTemplateArgument Arg,
2514	unsigned ArgumentPackIndex) {
2515	// Convert the deduced template argument into a template
2516	// argument that we can check, almost as if the user had written
2517	// the template argument explicitly.
2518	TemplateArgumentLoc ArgLoc =
2519	S.getTrivialTemplateArgumentLoc(Arg, QualType(), Info.getLocation());
2520
2521	// Check the template argument, converting it as necessary.
2522	return S.CheckTemplateArgument(
2523	Param, ArgLoc, Template, Template->getLocation(),
2524	Template->getSourceRange().getEnd(), ArgumentPackIndex, Output,
2525	IsDeduced
2526	? (Arg.wasDeducedFromArrayBound() ? Sema::CTAK_DeducedFromArrayBound
2527	: Sema::CTAK_Deduced)
2528	: Sema::CTAK_Specified);
2529	};
2530
2531	if (Arg.getKind() == TemplateArgument::Pack) {
2532	// This is a template argument pack, so check each of its arguments against
2533	// the template parameter.
2534	SmallVector<TemplateArgument, 2> PackedArgsBuilder;
2535	for (const auto &P : Arg.pack_elements()) {
2536	// When converting the deduced template argument, append it to the
2537	// general output list. We need to do this so that the template argument
2538	// checking logic has all of the prior template arguments available.
2539	DeducedTemplateArgument InnerArg(P);
2540	InnerArg.setDeducedFromArrayBound(Arg.wasDeducedFromArrayBound());
2541	(0) . __assert_fail ("InnerArg.getKind() != TemplateArgument..Pack && \"deduced nested pack\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 2542, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(InnerArg.getKind() != TemplateArgument::Pack &&
2542	(0) . __assert_fail ("InnerArg.getKind() != TemplateArgument..Pack && \"deduced nested pack\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 2542, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "deduced nested pack");
2543	if (P.isNull()) {
2544	// We deduced arguments for some elements of this pack, but not for
2545	// all of them. This happens if we get a conditionally-non-deduced
2546	// context in a pack expansion (such as an overload set in one of the
2547	// arguments).
2548	S.Diag(Param->getLocation(),
2549	diag::err_template_arg_deduced_incomplete_pack)
2550	<< Arg << Param;
2551	return true;
2552	}
2553	if (ConvertArg(InnerArg, PackedArgsBuilder.size()))
2554	return true;
2555
2556	// Move the converted template argument into our argument pack.
2557	PackedArgsBuilder.push_back(Output.pop_back_val());
2558	}
2559
2560	// If the pack is empty, we still need to substitute into the parameter
2561	// itself, in case that substitution fails.
2562	if (PackedArgsBuilder.empty()) {
2563	LocalInstantiationScope Scope(S);
2564	TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack, Output);
2565	MultiLevelTemplateArgumentList Args(TemplateArgs);
2566
2567	if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2568	Sema::InstantiatingTemplate Inst(S, Template->getLocation(), Template,
2569	NTTP, Output,
2570	Template->getSourceRange());
2571	if (Inst.isInvalid() \|\|
2572	S.SubstType(NTTP->getType(), Args, NTTP->getLocation(),
2573	NTTP->getDeclName()).isNull())
2574	return true;
2575	} else if (auto *TTP = dyn_cast<TemplateTemplateParmDecl>(Param)) {
2576	Sema::InstantiatingTemplate Inst(S, Template->getLocation(), Template,
2577	TTP, Output,
2578	Template->getSourceRange());
2579	if (Inst.isInvalid() \|\| !S.SubstDecl(TTP, S.CurContext, Args))
2580	return true;
2581	}
2582	// For type parameters, no substitution is ever required.
2583	}
2584
2585	// Create the resulting argument pack.
2586	Output.push_back(
2587	TemplateArgument::CreatePackCopy(S.Context, PackedArgsBuilder));
2588	return false;
2589	}
2590
2591	return ConvertArg(Arg, 0);
2592	}
2593
2594	// FIXME: This should not be a template, but
2595	// ClassTemplatePartialSpecializationDecl sadly does not derive from
2596	// TemplateDecl.
2597	template<typename TemplateDeclT>
2598	static Sema::TemplateDeductionResult ConvertDeducedTemplateArguments(
2599	Sema &S, TemplateDeclT *Template, bool IsDeduced,
2600	SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2601	TemplateDeductionInfo &Info, SmallVectorImpl<TemplateArgument> &Builder,
2602	LocalInstantiationScope *CurrentInstantiationScope = nullptr,
2603	unsigned NumAlreadyConverted = 0, bool PartialOverloading = false) {
2604	TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2605
2606	for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) {
2607	NamedDecl *Param = TemplateParams->getParam(I);
2608
2609	// C++0x [temp.arg.explicit]p3:
2610	// A trailing template parameter pack (14.5.3) not otherwise deduced will
2611	// be deduced to an empty sequence of template arguments.
2612	// FIXME: Where did the word "trailing" come from?
2613	if (Deduced[I].isNull() && Param->isTemplateParameterPack()) {
2614	if (auto Result = PackDeductionScope(S, TemplateParams, Deduced, Info, I)
2615	.finish(/TreatNoDeductionsAsNonDeduced/false))
2616	return Result;
2617	}
2618
2619	if (!Deduced[I].isNull()) {
2620	if (I < NumAlreadyConverted) {
2621	// We may have had explicitly-specified template arguments for a
2622	// template parameter pack (that may or may not have been extended
2623	// via additional deduced arguments).
2624	if (Param->isParameterPack() && CurrentInstantiationScope &&
2625	CurrentInstantiationScope->getPartiallySubstitutedPack() == Param) {
2626	// Forget the partially-substituted pack; its substitution is now
2627	// complete.
2628	CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2629	// We still need to check the argument in case it was extended by
2630	// deduction.
2631	} else {
2632	// We have already fully type-checked and converted this
2633	// argument, because it was explicitly-specified. Just record the
2634	// presence of this argument.
2635	Builder.push_back(Deduced[I]);
2636	continue;
2637	}
2638	}
2639
2640	// We may have deduced this argument, so it still needs to be
2641	// checked and converted.
2642	if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Template, Info,
2643	IsDeduced, Builder)) {
2644	Info.Param = makeTemplateParameter(Param);
2645	// FIXME: These template arguments are temporary. Free them!
2646	Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2647	return Sema::TDK_SubstitutionFailure;
2648	}
2649
2650	continue;
2651	}
2652
2653	// Substitute into the default template argument, if available.
2654	bool HasDefaultArg = false;
2655	TemplateDecl *TD = dyn_cast<TemplateDecl>(Template);
2656	if (!TD) {
2657	(Template) \|\| isa(Template)", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 2658, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(isa<ClassTemplatePartialSpecializationDecl>(Template) \|\|
2658	(Template) \|\| isa(Template)", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 2658, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> isa<VarTemplatePartialSpecializationDecl>(Template));
2659	return Sema::TDK_Incomplete;
2660	}
2661
2662	TemplateArgumentLoc DefArg = S.SubstDefaultTemplateArgumentIfAvailable(
2663	TD, TD->getLocation(), TD->getSourceRange().getEnd(), Param, Builder,
2664	HasDefaultArg);
2665
2666	// If there was no default argument, deduction is incomplete.
2667	if (DefArg.getArgument().isNull()) {
2668	Info.Param = makeTemplateParameter(
2669	const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2670	Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2671	if (PartialOverloading) break;
2672
2673	return HasDefaultArg ? Sema::TDK_SubstitutionFailure
2674	: Sema::TDK_Incomplete;
2675	}
2676
2677	// Check whether we can actually use the default argument.
2678	if (S.CheckTemplateArgument(Param, DefArg, TD, TD->getLocation(),
2679	TD->getSourceRange().getEnd(), 0, Builder,
2680	Sema::CTAK_Specified)) {
2681	Info.Param = makeTemplateParameter(
2682	const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2683	// FIXME: These template arguments are temporary. Free them!
2684	Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2685	return Sema::TDK_SubstitutionFailure;
2686	}
2687
2688	// If we get here, we successfully used the default template argument.
2689	}
2690
2691	return Sema::TDK_Success;
2692	}
2693
2694	static DeclContext getAsDeclContextOrEnclosing(Decl D) {
2695	if (auto *DC = dyn_cast<DeclContext>(D))
2696	return DC;
2697	return D->getDeclContext();
2698	}
2699
2700	template<typename T> struct IsPartialSpecialization {
2701	static constexpr bool value = false;
2702	};
2703	template<>
2704	struct IsPartialSpecialization<ClassTemplatePartialSpecializationDecl> {
2705	static constexpr bool value = true;
2706	};
2707	template<>
2708	struct IsPartialSpecialization<VarTemplatePartialSpecializationDecl> {
2709	static constexpr bool value = true;
2710	};
2711
2712	/// Complete template argument deduction for a partial specialization.
2713	template <typename T>
2714	static typename std::enable_if<IsPartialSpecialization<T>::value,
2715	Sema::TemplateDeductionResult>::type
2716	FinishTemplateArgumentDeduction(
2717	Sema &S, T *Partial, bool IsPartialOrdering,
2718	const TemplateArgumentList &TemplateArgs,
2719	SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2720	TemplateDeductionInfo &Info) {
2721	// Unevaluated SFINAE context.
2722	EnterExpressionEvaluationContext Unevaluated(
2723	S, Sema::ExpressionEvaluationContext::Unevaluated);
2724	Sema::SFINAETrap Trap(S);
2725
2726	Sema::ContextRAII SavedContext(S, getAsDeclContextOrEnclosing(Partial));
2727
2728	// C++ [temp.deduct.type]p2:
2729	// [...] or if any template argument remains neither deduced nor
2730	// explicitly specified, template argument deduction fails.
2731	SmallVector<TemplateArgument, 4> Builder;
2732	if (auto Result = ConvertDeducedTemplateArguments(
2733	S, Partial, IsPartialOrdering, Deduced, Info, Builder))
2734	return Result;
2735
2736	// Form the template argument list from the deduced template arguments.
2737	TemplateArgumentList *DeducedArgumentList
2738	= TemplateArgumentList::CreateCopy(S.Context, Builder);
2739
2740	Info.reset(DeducedArgumentList);
2741
2742	// Substitute the deduced template arguments into the template
2743	// arguments of the class template partial specialization, and
2744	// verify that the instantiated template arguments are both valid
2745	// and are equivalent to the template arguments originally provided
2746	// to the class template.
2747	LocalInstantiationScope InstScope(S);
2748	auto *Template = Partial->getSpecializedTemplate();
2749	const ASTTemplateArgumentListInfo *PartialTemplArgInfo =
2750	Partial->getTemplateArgsAsWritten();
2751	const TemplateArgumentLoc *PartialTemplateArgs =
2752	PartialTemplArgInfo->getTemplateArgs();
2753
2754	TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc,
2755	PartialTemplArgInfo->RAngleLoc);
2756
2757	if (S.Subst(PartialTemplateArgs, PartialTemplArgInfo->NumTemplateArgs,
2758	InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
2759	unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2760	if (ParamIdx >= Partial->getTemplateParameters()->size())
2761	ParamIdx = Partial->getTemplateParameters()->size() - 1;
2762
2763	Decl Param = const_cast<NamedDecl >(
2764	Partial->getTemplateParameters()->getParam(ParamIdx));
2765	Info.Param = makeTemplateParameter(Param);
2766	Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
2767	return Sema::TDK_SubstitutionFailure;
2768	}
2769
2770	SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2771	if (S.CheckTemplateArgumentList(Template, Partial->getLocation(), InstArgs,
2772	false, ConvertedInstArgs))
2773	return Sema::TDK_SubstitutionFailure;
2774
2775	TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2776	for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2777	TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2778	if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2779	Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2780	Info.FirstArg = TemplateArgs[I];
2781	Info.SecondArg = InstArg;
2782	return Sema::TDK_NonDeducedMismatch;
2783	}
2784	}
2785
2786	if (Trap.hasErrorOccurred())
2787	return Sema::TDK_SubstitutionFailure;
2788
2789	return Sema::TDK_Success;
2790	}
2791
2792	/// Complete template argument deduction for a class or variable template,
2793	/// when partial ordering against a partial specialization.
2794	// FIXME: Factor out duplication with partial specialization version above.
2795	static Sema::TemplateDeductionResult FinishTemplateArgumentDeduction(
2796	Sema &S, TemplateDecl *Template, bool PartialOrdering,
2797	const TemplateArgumentList &TemplateArgs,
2798	SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2799	TemplateDeductionInfo &Info) {
2800	// Unevaluated SFINAE context.
2801	EnterExpressionEvaluationContext Unevaluated(
2802	S, Sema::ExpressionEvaluationContext::Unevaluated);
2803	Sema::SFINAETrap Trap(S);
2804
2805	Sema::ContextRAII SavedContext(S, getAsDeclContextOrEnclosing(Template));
2806
2807	// C++ [temp.deduct.type]p2:
2808	// [...] or if any template argument remains neither deduced nor
2809	// explicitly specified, template argument deduction fails.
2810	SmallVector<TemplateArgument, 4> Builder;
2811	if (auto Result = ConvertDeducedTemplateArguments(
2812	S, Template, /IsDeduced/PartialOrdering, Deduced, Info, Builder))
2813	return Result;
2814
2815	// Check that we produced the correct argument list.
2816	TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2817	for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2818	TemplateArgument InstArg = Builder[I];
2819	if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg,
2820	/PackExpansionMatchesPack/true)) {
2821	Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2822	Info.FirstArg = TemplateArgs[I];
2823	Info.SecondArg = InstArg;
2824	return Sema::TDK_NonDeducedMismatch;
2825	}
2826	}
2827
2828	if (Trap.hasErrorOccurred())
2829	return Sema::TDK_SubstitutionFailure;
2830
2831	return Sema::TDK_Success;
2832	}
2833
2834
2835	/// Perform template argument deduction to determine whether
2836	/// the given template arguments match the given class template
2837	/// partial specialization per C++ [temp.class.spec.match].
2838	Sema::TemplateDeductionResult
2839	Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
2840	const TemplateArgumentList &TemplateArgs,
2841	TemplateDeductionInfo &Info) {
2842	if (Partial->isInvalidDecl())
2843	return TDK_Invalid;
2844
2845	// C++ [temp.class.spec.match]p2:
2846	// A partial specialization matches a given actual template
2847	// argument list if the template arguments of the partial
2848	// specialization can be deduced from the actual template argument
2849	// list (14.8.2).
2850
2851	// Unevaluated SFINAE context.
2852	EnterExpressionEvaluationContext Unevaluated(
2853	*this, Sema::ExpressionEvaluationContext::Unevaluated);
2854	SFINAETrap Trap(*this);
2855
2856	SmallVector<DeducedTemplateArgument, 4> Deduced;
2857	Deduced.resize(Partial->getTemplateParameters()->size());
2858	if (TemplateDeductionResult Result
2859	= ::DeduceTemplateArguments(*this,
2860	Partial->getTemplateParameters(),
2861	Partial->getTemplateArgs(),
2862	TemplateArgs, Info, Deduced))
2863	return Result;
2864
2865	SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2866	InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
2867	Info);
2868	if (Inst.isInvalid())
2869	return TDK_InstantiationDepth;
2870
2871	if (Trap.hasErrorOccurred())
2872	return Sema::TDK_SubstitutionFailure;
2873
2874	return ::FinishTemplateArgumentDeduction(
2875	this, Partial, /PartialOrdering=*/false, TemplateArgs, Deduced, Info);
2876	}
2877
2878	/// Perform template argument deduction to determine whether
2879	/// the given template arguments match the given variable template
2880	/// partial specialization per C++ [temp.class.spec.match].
2881	Sema::TemplateDeductionResult
2882	Sema::DeduceTemplateArguments(VarTemplatePartialSpecializationDecl *Partial,
2883	const TemplateArgumentList &TemplateArgs,
2884	TemplateDeductionInfo &Info) {
2885	if (Partial->isInvalidDecl())
2886	return TDK_Invalid;
2887
2888	// C++ [temp.class.spec.match]p2:
2889	// A partial specialization matches a given actual template
2890	// argument list if the template arguments of the partial
2891	// specialization can be deduced from the actual template argument
2892	// list (14.8.2).
2893
2894	// Unevaluated SFINAE context.
2895	EnterExpressionEvaluationContext Unevaluated(
2896	*this, Sema::ExpressionEvaluationContext::Unevaluated);
2897	SFINAETrap Trap(*this);
2898
2899	SmallVector<DeducedTemplateArgument, 4> Deduced;
2900	Deduced.resize(Partial->getTemplateParameters()->size());
2901	if (TemplateDeductionResult Result = ::DeduceTemplateArguments(
2902	*this, Partial->getTemplateParameters(), Partial->getTemplateArgs(),
2903	TemplateArgs, Info, Deduced))
2904	return Result;
2905
2906	SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2907	InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
2908	Info);
2909	if (Inst.isInvalid())
2910	return TDK_InstantiationDepth;
2911
2912	if (Trap.hasErrorOccurred())
2913	return Sema::TDK_SubstitutionFailure;
2914
2915	return ::FinishTemplateArgumentDeduction(
2916	this, Partial, /PartialOrdering=*/false, TemplateArgs, Deduced, Info);
2917	}
2918
2919	/// Determine whether the given type T is a simple-template-id type.
2920	static bool isSimpleTemplateIdType(QualType T) {
2921	if (const TemplateSpecializationType *Spec
2922	= T->getAs<TemplateSpecializationType>())
2923	return Spec->getTemplateName().getAsTemplateDecl() != nullptr;
2924
2925	// C++17 [temp.local]p2:
2926	// the injected-class-name [...] is equivalent to the template-name followed
2927	// by the template-arguments of the class template specialization or partial
2928	// specialization enclosed in <>
2929	// ... which means it's equivalent to a simple-template-id.
2930	//
2931	// This only arises during class template argument deduction for a copy
2932	// deduction candidate, where it permits slicing.
2933	if (T->getAs<InjectedClassNameType>())
2934	return true;
2935
2936	return false;
2937	}
2938
2939	/// Substitute the explicitly-provided template arguments into the
2940	/// given function template according to C++ [temp.arg.explicit].
2941	///
2942	/// \param FunctionTemplate the function template into which the explicit
2943	/// template arguments will be substituted.
2944	///
2945	/// \param ExplicitTemplateArgs the explicitly-specified template
2946	/// arguments.
2947	///
2948	/// \param Deduced the deduced template arguments, which will be populated
2949	/// with the converted and checked explicit template arguments.
2950	///
2951	/// \param ParamTypes will be populated with the instantiated function
2952	/// parameters.
2953	///
2954	/// \param FunctionType if non-NULL, the result type of the function template
2955	/// will also be instantiated and the pointed-to value will be updated with
2956	/// the instantiated function type.
2957	///
2958	/// \param Info if substitution fails for any reason, this object will be
2959	/// populated with more information about the failure.
2960	///
2961	/// \returns TDK_Success if substitution was successful, or some failure
2962	/// condition.
2963	Sema::TemplateDeductionResult
2964	Sema::SubstituteExplicitTemplateArguments(
2965	FunctionTemplateDecl *FunctionTemplate,
2966	TemplateArgumentListInfo &ExplicitTemplateArgs,
2967	SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2968	SmallVectorImpl<QualType> &ParamTypes,
2969	QualType *FunctionType,
2970	TemplateDeductionInfo &Info) {
2971	FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
2972	TemplateParameterList *TemplateParams
2973	= FunctionTemplate->getTemplateParameters();
2974
2975	if (ExplicitTemplateArgs.size() == 0) {
2976	// No arguments to substitute; just copy over the parameter types and
2977	// fill in the function type.
2978	for (auto P : Function->parameters())
2979	ParamTypes.push_back(P->getType());
2980
2981	if (FunctionType)
2982	*FunctionType = Function->getType();
2983	return TDK_Success;
2984	}
2985
2986	// Unevaluated SFINAE context.
2987	EnterExpressionEvaluationContext Unevaluated(
2988	*this, Sema::ExpressionEvaluationContext::Unevaluated);
2989	SFINAETrap Trap(*this);
2990
2991	// C++ [temp.arg.explicit]p3:
2992	// Template arguments that are present shall be specified in the
2993	// declaration order of their corresponding template-parameters. The
2994	// template argument list shall not specify more template-arguments than
2995	// there are corresponding template-parameters.
2996	SmallVector<TemplateArgument, 4> Builder;
2997
2998	// Enter a new template instantiation context where we check the
2999	// explicitly-specified template arguments against this function template,
3000	// and then substitute them into the function parameter types.
3001	SmallVector<TemplateArgument, 4> DeducedArgs;
3002	InstantiatingTemplate Inst(
3003	*this, Info.getLocation(), FunctionTemplate, DeducedArgs,
3004	CodeSynthesisContext::ExplicitTemplateArgumentSubstitution, Info);
3005	if (Inst.isInvalid())
3006	return TDK_InstantiationDepth;
3007
3008	if (CheckTemplateArgumentList(FunctionTemplate, SourceLocation(),
3009	ExplicitTemplateArgs, true, Builder, false) \|\|
3010	Trap.hasErrorOccurred()) {
3011	unsigned Index = Builder.size();
3012	if (Index >= TemplateParams->size())
3013	return TDK_SubstitutionFailure;
3014	Info.Param = makeTemplateParameter(TemplateParams->getParam(Index));
3015	return TDK_InvalidExplicitArguments;
3016	}
3017
3018	// Form the template argument list from the explicitly-specified
3019	// template arguments.
3020	TemplateArgumentList *ExplicitArgumentList
3021	= TemplateArgumentList::CreateCopy(Context, Builder);
3022	Info.setExplicitArgs(ExplicitArgumentList);
3023
3024	// Template argument deduction and the final substitution should be
3025	// done in the context of the templated declaration. Explicit
3026	// argument substitution, on the other hand, needs to happen in the
3027	// calling context.
3028	ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
3029
3030	// If we deduced template arguments for a template parameter pack,
3031	// note that the template argument pack is partially substituted and record
3032	// the explicit template arguments. They'll be used as part of deduction
3033	// for this template parameter pack.
3034	unsigned PartiallySubstitutedPackIndex = -1u;
3035	if (!Builder.empty()) {
3036	const TemplateArgument &Arg = Builder.back();
3037	if (Arg.getKind() == TemplateArgument::Pack) {
3038	auto *Param = TemplateParams->getParam(Builder.size() - 1);
3039	// If this is a fully-saturated fixed-size pack, it should be
3040	// fully-substituted, not partially-substituted.
3041	Optional<unsigned> Expansions = getExpandedPackSize(Param);
3042	if (!Expansions \|\| Arg.pack_size() < *Expansions) {
3043	PartiallySubstitutedPackIndex = Builder.size() - 1;
3044	CurrentInstantiationScope->SetPartiallySubstitutedPack(
3045	Param, Arg.pack_begin(), Arg.pack_size());
3046	}
3047	}
3048	}
3049
3050	const FunctionProtoType *Proto
3051	= Function->getType()->getAs<FunctionProtoType>();
3052	(0) . __assert_fail ("Proto && \"Function template does not have a prototype?\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 3052, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(Proto && "Function template does not have a prototype?");
3053
3054	// Isolate our substituted parameters from our caller.
3055	LocalInstantiationScope InstScope(this, /MergeWithOuterScope*/true);
3056
3057	ExtParameterInfoBuilder ExtParamInfos;
3058
3059	// Instantiate the types of each of the function parameters given the
3060	// explicitly-specified template arguments. If the function has a trailing
3061	// return type, substitute it after the arguments to ensure we substitute
3062	// in lexical order.
3063	if (Proto->hasTrailingReturn()) {
3064	if (SubstParmTypes(Function->getLocation(), Function->parameters(),
3065	Proto->getExtParameterInfosOrNull(),
3066	MultiLevelTemplateArgumentList(*ExplicitArgumentList),
3067	ParamTypes, /params/ nullptr, ExtParamInfos))
3068	return TDK_SubstitutionFailure;
3069	}
3070
3071	// Instantiate the return type.
3072	QualType ResultType;
3073	{
3074	// C++11 [expr.prim.general]p3:
3075	// If a declaration declares a member function or member function
3076	// template of a class X, the expression this is a prvalue of type
3077	// "pointer to cv-qualifier-seq X" between the optional cv-qualifer-seq
3078	// and the end of the function-definition, member-declarator, or
3079	// declarator.
3080	Qualifiers ThisTypeQuals;
3081	CXXRecordDecl *ThisContext = nullptr;
3082	if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Function)) {
3083	ThisContext = Method->getParent();
3084	ThisTypeQuals = Method->getMethodQualifiers();
3085	}
3086
3087	CXXThisScopeRAII ThisScope(*this, ThisContext, ThisTypeQuals,
3088	getLangOpts().CPlusPlus11);
3089
3090	ResultType =
3091	SubstType(Proto->getReturnType(),
3092	MultiLevelTemplateArgumentList(*ExplicitArgumentList),
3093	Function->getTypeSpecStartLoc(), Function->getDeclName());
3094	if (ResultType.isNull() \|\| Trap.hasErrorOccurred())
3095	return TDK_SubstitutionFailure;
3096	}
3097
3098	// Instantiate the types of each of the function parameters given the
3099	// explicitly-specified template arguments if we didn't do so earlier.
3100	if (!Proto->hasTrailingReturn() &&
3101	SubstParmTypes(Function->getLocation(), Function->parameters(),
3102	Proto->getExtParameterInfosOrNull(),
3103	MultiLevelTemplateArgumentList(*ExplicitArgumentList),
3104	ParamTypes, /params/ nullptr, ExtParamInfos))
3105	return TDK_SubstitutionFailure;
3106
3107	if (FunctionType) {
3108	auto EPI = Proto->getExtProtoInfo();
3109	EPI.ExtParameterInfos = ExtParamInfos.getPointerOrNull(ParamTypes.size());
3110
3111	// In C++1z onwards, exception specifications are part of the function type,
3112	// so substitution into the type must also substitute into the exception
3113	// specification.
3114	SmallVector<QualType, 4> ExceptionStorage;
3115	if (getLangOpts().CPlusPlus17 &&
3116	SubstExceptionSpec(
3117	Function->getLocation(), EPI.ExceptionSpec, ExceptionStorage,
3118	MultiLevelTemplateArgumentList(*ExplicitArgumentList)))
3119	return TDK_SubstitutionFailure;
3120
3121	*FunctionType = BuildFunctionType(ResultType, ParamTypes,
3122	Function->getLocation(),
3123	Function->getDeclName(),
3124	EPI);
3125	if (FunctionType->isNull() \|\| Trap.hasErrorOccurred())
3126	return TDK_SubstitutionFailure;
3127	}
3128
3129	// C++ [temp.arg.explicit]p2:
3130	// Trailing template arguments that can be deduced (14.8.2) may be
3131	// omitted from the list of explicit template-arguments. If all of the
3132	// template arguments can be deduced, they may all be omitted; in this
3133	// case, the empty template argument list <> itself may also be omitted.
3134	//
3135	// Take all of the explicitly-specified arguments and put them into
3136	// the set of deduced template arguments. The partially-substituted
3137	// parameter pack, however, will be set to NULL since the deduction
3138	// mechanism handles the partially-substituted argument pack directly.
3139	Deduced.reserve(TemplateParams->size());
3140	for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) {
3141	const TemplateArgument &Arg = ExplicitArgumentList->get(I);
3142	if (I == PartiallySubstitutedPackIndex)
3143	Deduced.push_back(DeducedTemplateArgument());
3144	else
3145	Deduced.push_back(Arg);
3146	}
3147
3148	return TDK_Success;
3149	}
3150
3151	/// Check whether the deduced argument type for a call to a function
3152	/// template matches the actual argument type per C++ [temp.deduct.call]p4.
3153	static Sema::TemplateDeductionResult
3154	CheckOriginalCallArgDeduction(Sema &S, TemplateDeductionInfo &Info,
3155	Sema::OriginalCallArg OriginalArg,
3156	QualType DeducedA) {
3157	ASTContext &Context = S.Context;
3158
3159	auto Failed = [&]() -> Sema::TemplateDeductionResult {
3160	Info.FirstArg = TemplateArgument(DeducedA);
3161	Info.SecondArg = TemplateArgument(OriginalArg.OriginalArgType);
3162	Info.CallArgIndex = OriginalArg.ArgIdx;
3163	return OriginalArg.DecomposedParam ? Sema::TDK_DeducedMismatchNested
3164	: Sema::TDK_DeducedMismatch;
3165	};
3166
3167	QualType A = OriginalArg.OriginalArgType;
3168	QualType OriginalParamType = OriginalArg.OriginalParamType;
3169
3170	// Check for type equality (top-level cv-qualifiers are ignored).
3171	if (Context.hasSameUnqualifiedType(A, DeducedA))
3172	return Sema::TDK_Success;
3173
3174	// Strip off references on the argument types; they aren't needed for
3175	// the following checks.
3176	if (const ReferenceType *DeducedARef = DeducedA->getAs<ReferenceType>())
3177	DeducedA = DeducedARef->getPointeeType();
3178	if (const ReferenceType *ARef = A->getAs<ReferenceType>())
3179	A = ARef->getPointeeType();
3180
3181	// C++ [temp.deduct.call]p4:
3182	// [...] However, there are three cases that allow a difference:
3183	// - If the original P is a reference type, the deduced A (i.e., the
3184	// type referred to by the reference) can be more cv-qualified than
3185	// the transformed A.
3186	if (const ReferenceType *OriginalParamRef
3187	= OriginalParamType->getAs<ReferenceType>()) {
3188	// We don't want to keep the reference around any more.
3189	OriginalParamType = OriginalParamRef->getPointeeType();
3190
3191	// FIXME: Resolve core issue (no number yet): if the original P is a
3192	// reference type and the transformed A is function type "noexcept F",
3193	// the deduced A can be F.
3194	QualType Tmp;
3195	if (A->isFunctionType() && S.IsFunctionConversion(A, DeducedA, Tmp))
3196	return Sema::TDK_Success;
3197
3198	Qualifiers AQuals = A.getQualifiers();
3199	Qualifiers DeducedAQuals = DeducedA.getQualifiers();
3200
3201	// Under Objective-C++ ARC, the deduced type may have implicitly
3202	// been given strong or (when dealing with a const reference)
3203	// unsafe_unretained lifetime. If so, update the original
3204	// qualifiers to include this lifetime.
3205	if (S.getLangOpts().ObjCAutoRefCount &&
3206	((DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_Strong &&
3207	AQuals.getObjCLifetime() == Qualifiers::OCL_None) \|\|
3208	(DeducedAQuals.hasConst() &&
3209	DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone))) {
3210	AQuals.setObjCLifetime(DeducedAQuals.getObjCLifetime());
3211	}
3212
3213	if (AQuals == DeducedAQuals) {
3214	// Qualifiers match; there's nothing to do.
3215	} else if (!DeducedAQuals.compatiblyIncludes(AQuals)) {
3216	return Failed();
3217	} else {
3218	// Qualifiers are compatible, so have the argument type adopt the
3219	// deduced argument type's qualifiers as if we had performed the
3220	// qualification conversion.
3221	A = Context.getQualifiedType(A.getUnqualifiedType(), DeducedAQuals);
3222	}
3223	}
3224
3225	// - The transformed A can be another pointer or pointer to member
3226	// type that can be converted to the deduced A via a function pointer
3227	// conversion and/or a qualification conversion.
3228	//
3229	// Also allow conversions which merely strip __attribute__((noreturn)) from
3230	// function types (recursively).
3231	bool ObjCLifetimeConversion = false;
3232	QualType ResultTy;
3233	if ((A->isAnyPointerType() \|\| A->isMemberPointerType()) &&
3234	(S.IsQualificationConversion(A, DeducedA, false,
3235	ObjCLifetimeConversion) \|\|
3236	S.IsFunctionConversion(A, DeducedA, ResultTy)))
3237	return Sema::TDK_Success;
3238
3239	// - If P is a class and P has the form simple-template-id, then the
3240	// transformed A can be a derived class of the deduced A. [...]
3241	// [...] Likewise, if P is a pointer to a class of the form
3242	// simple-template-id, the transformed A can be a pointer to a
3243	// derived class pointed to by the deduced A.
3244	if (const PointerType *OriginalParamPtr
3245	= OriginalParamType->getAs<PointerType>()) {
3246	if (const PointerType *DeducedAPtr = DeducedA->getAs<PointerType>()) {
3247	if (const PointerType *APtr = A->getAs<PointerType>()) {
3248	if (A->getPointeeType()->isRecordType()) {
3249	OriginalParamType = OriginalParamPtr->getPointeeType();
3250	DeducedA = DeducedAPtr->getPointeeType();
3251	A = APtr->getPointeeType();
3252	}
3253	}
3254	}
3255	}
3256
3257	if (Context.hasSameUnqualifiedType(A, DeducedA))
3258	return Sema::TDK_Success;
3259
3260	if (A->isRecordType() && isSimpleTemplateIdType(OriginalParamType) &&
3261	S.IsDerivedFrom(Info.getLocation(), A, DeducedA))
3262	return Sema::TDK_Success;
3263
3264	return Failed();
3265	}
3266
3267	/// Find the pack index for a particular parameter index in an instantiation of
3268	/// a function template with specific arguments.
3269	///
3270	/// \return The pack index for whichever pack produced this parameter, or -1
3271	/// if this was not produced by a parameter. Intended to be used as the
3272	/// ArgumentPackSubstitutionIndex for further substitutions.
3273	// FIXME: We should track this in OriginalCallArgs so we don't need to
3274	// reconstruct it here.
3275	static unsigned getPackIndexForParam(Sema &S,
3276	FunctionTemplateDecl *FunctionTemplate,
3277	const MultiLevelTemplateArgumentList &Args,
3278	unsigned ParamIdx) {
3279	unsigned Idx = 0;
3280	for (auto *PD : FunctionTemplate->getTemplatedDecl()->parameters()) {
3281	if (PD->isParameterPack()) {
3282	unsigned NumExpansions =
3283	S.getNumArgumentsInExpansion(PD->getType(), Args).getValueOr(1);
3284	if (Idx + NumExpansions > ParamIdx)
3285	return ParamIdx - Idx;
3286	Idx += NumExpansions;
3287	} else {
3288	if (Idx == ParamIdx)
3289	return -1; // Not a pack expansion
3290	++Idx;
3291	}
3292	}
3293
3294	llvm_unreachable("parameter index would not be produced from template");
3295	}
3296
3297	/// Finish template argument deduction for a function template,
3298	/// checking the deduced template arguments for completeness and forming
3299	/// the function template specialization.
3300	///
3301	/// \param OriginalCallArgs If non-NULL, the original call arguments against
3302	/// which the deduced argument types should be compared.
3303	Sema::TemplateDeductionResult Sema::FinishTemplateArgumentDeduction(
3304	FunctionTemplateDecl *FunctionTemplate,
3305	SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3306	unsigned NumExplicitlySpecified, FunctionDecl *&Specialization,
3307	TemplateDeductionInfo &Info,
3308	SmallVectorImpl<OriginalCallArg> const *OriginalCallArgs,
3309	bool PartialOverloading, llvm::function_ref<bool()> CheckNonDependent) {
3310	// Unevaluated SFINAE context.
3311	EnterExpressionEvaluationContext Unevaluated(
3312	*this, Sema::ExpressionEvaluationContext::Unevaluated);
3313	SFINAETrap Trap(*this);
3314
3315	// Enter a new template instantiation context while we instantiate the
3316	// actual function declaration.
3317	SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
3318	InstantiatingTemplate Inst(
3319	*this, Info.getLocation(), FunctionTemplate, DeducedArgs,
3320	CodeSynthesisContext::DeducedTemplateArgumentSubstitution, Info);
3321	if (Inst.isInvalid())
3322	return TDK_InstantiationDepth;
3323
3324	ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
3325
3326	// C++ [temp.deduct.type]p2:
3327	// [...] or if any template argument remains neither deduced nor
3328	// explicitly specified, template argument deduction fails.
3329	SmallVector<TemplateArgument, 4> Builder;
3330	if (auto Result = ConvertDeducedTemplateArguments(
3331	this, FunctionTemplate, /IsDeduced*/true, Deduced, Info, Builder,
3332	CurrentInstantiationScope, NumExplicitlySpecified,
3333	PartialOverloading))
3334	return Result;
3335
3336	// C++ [temp.deduct.call]p10: [DR1391]
3337	// If deduction succeeds for all parameters that contain
3338	// template-parameters that participate in template argument deduction,
3339	// and all template arguments are explicitly specified, deduced, or
3340	// obtained from default template arguments, remaining parameters are then
3341	// compared with the corresponding arguments. For each remaining parameter
3342	// P with a type that was non-dependent before substitution of any
3343	// explicitly-specified template arguments, if the corresponding argument
3344	// A cannot be implicitly converted to P, deduction fails.
3345	if (CheckNonDependent())
3346	return TDK_NonDependentConversionFailure;
3347
3348	// Form the template argument list from the deduced template arguments.
3349	TemplateArgumentList *DeducedArgumentList
3350	= TemplateArgumentList::CreateCopy(Context, Builder);
3351	Info.reset(DeducedArgumentList);
3352
3353	// Substitute the deduced template arguments into the function template
3354	// declaration to produce the function template specialization.
3355	DeclContext *Owner = FunctionTemplate->getDeclContext();
3356	if (FunctionTemplate->getFriendObjectKind())
3357	Owner = FunctionTemplate->getLexicalDeclContext();
3358	MultiLevelTemplateArgumentList SubstArgs(*DeducedArgumentList);
3359	Specialization = cast_or_null<FunctionDecl>(
3360	SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner, SubstArgs));
3361	if (!Specialization \|\| Specialization->isInvalidDecl())
3362	return TDK_SubstitutionFailure;
3363
3364	getPrimaryTemplate()->getCanonicalDecl() == FunctionTemplate->getCanonicalDecl()", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 3365, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() ==
3365	getPrimaryTemplate()->getCanonicalDecl() == FunctionTemplate->getCanonicalDecl()", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 3365, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> FunctionTemplate->getCanonicalDecl());
3366
3367	// If the template argument list is owned by the function template
3368	// specialization, release it.
3369	if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList &&
3370	!Trap.hasErrorOccurred())
3371	Info.take();
3372
3373	// There may have been an error that did not prevent us from constructing a
3374	// declaration. Mark the declaration invalid and return with a substitution
3375	// failure.
3376	if (Trap.hasErrorOccurred()) {
3377	Specialization->setInvalidDecl(true);
3378	return TDK_SubstitutionFailure;
3379	}
3380
3381	if (OriginalCallArgs) {
3382	// C++ [temp.deduct.call]p4:
3383	// In general, the deduction process attempts to find template argument
3384	// values that will make the deduced A identical to A (after the type A
3385	// is transformed as described above). [...]
3386	llvm::SmallDenseMap<std::pair<unsigned, QualType>, QualType> DeducedATypes;
3387	for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; ++I) {
3388	OriginalCallArg OriginalArg = (*OriginalCallArgs)[I];
3389
3390	auto ParamIdx = OriginalArg.ArgIdx;
3391	if (ParamIdx >= Specialization->getNumParams())
3392	// FIXME: This presumably means a pack ended up smaller than we
3393	// expected while deducing. Should this not result in deduction
3394	// failure? Can it even happen?
3395	continue;
3396
3397	QualType DeducedA;
3398	if (!OriginalArg.DecomposedParam) {
3399	// P is one of the function parameters, just look up its substituted
3400	// type.
3401	DeducedA = Specialization->getParamDecl(ParamIdx)->getType();
3402	} else {
3403	// P is a decomposed element of a parameter corresponding to a
3404	// braced-init-list argument. Substitute back into P to find the
3405	// deduced A.
3406	QualType &CacheEntry =
3407	DeducedATypes[{ParamIdx, OriginalArg.OriginalParamType}];
3408	if (CacheEntry.isNull()) {
3409	ArgumentPackSubstitutionIndexRAII PackIndex(
3410	this, getPackIndexForParam(this, FunctionTemplate, SubstArgs,
3411	ParamIdx));
3412	CacheEntry =
3413	SubstType(OriginalArg.OriginalParamType, SubstArgs,
3414	Specialization->getTypeSpecStartLoc(),
3415	Specialization->getDeclName());
3416	}
3417	DeducedA = CacheEntry;
3418	}
3419
3420	if (auto TDK =
3421	CheckOriginalCallArgDeduction(*this, Info, OriginalArg, DeducedA))
3422	return TDK;
3423	}
3424	}
3425
3426	// If we suppressed any diagnostics while performing template argument
3427	// deduction, and if we haven't already instantiated this declaration,
3428	// keep track of these diagnostics. They'll be emitted if this specialization
3429	// is actually used.
3430	if (Info.diag_begin() != Info.diag_end()) {
3431	SuppressedDiagnosticsMap::iterator
3432	Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl());
3433	if (Pos == SuppressedDiagnostics.end())
3434	SuppressedDiagnostics[Specialization->getCanonicalDecl()]
3435	.append(Info.diag_begin(), Info.diag_end());
3436	}
3437
3438	return TDK_Success;
3439	}
3440
3441	/// Gets the type of a function for template-argument-deducton
3442	/// purposes when it's considered as part of an overload set.
3443	static QualType GetTypeOfFunction(Sema &S, const OverloadExpr::FindResult &R,
3444	FunctionDecl *Fn) {
3445	// We may need to deduce the return type of the function now.
3446	if (S.getLangOpts().CPlusPlus14 && Fn->getReturnType()->isUndeducedType() &&
3447	S.DeduceReturnType(Fn, R.Expression->getExprLoc(), /Diagnose/ false))
3448	return {};
3449
3450	if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn))
3451	if (Method->isInstance()) {
3452	// An instance method that's referenced in a form that doesn't
3453	// look like a member pointer is just invalid.
3454	if (!R.HasFormOfMemberPointer)
3455	return {};
3456
3457	return S.Context.getMemberPointerType(Fn->getType(),
3458	S.Context.getTypeDeclType(Method->getParent()).getTypePtr());
3459	}
3460
3461	if (!R.IsAddressOfOperand) return Fn->getType();
3462	return S.Context.getPointerType(Fn->getType());
3463	}
3464
3465	/// Apply the deduction rules for overload sets.
3466	///
3467	/// \return the null type if this argument should be treated as an
3468	/// undeduced context
3469	static QualType
3470	ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams,
3471	Expr *Arg, QualType ParamType,
3472	bool ParamWasReference) {
3473
3474	OverloadExpr::FindResult R = OverloadExpr::find(Arg);
3475
3476	OverloadExpr *Ovl = R.Expression;
3477
3478	// C++0x [temp.deduct.call]p4
3479	unsigned TDF = 0;
3480	if (ParamWasReference)
3481	TDF \|= TDF_ParamWithReferenceType;
3482	if (R.IsAddressOfOperand)
3483	TDF \|= TDF_IgnoreQualifiers;
3484
3485	// C++0x [temp.deduct.call]p6:
3486	// When P is a function type, pointer to function type, or pointer
3487	// to member function type:
3488
3489	if (!ParamType->isFunctionType() &&
3490	!ParamType->isFunctionPointerType() &&
3491	!ParamType->isMemberFunctionPointerType()) {
3492	if (Ovl->hasExplicitTemplateArgs()) {
3493	// But we can still look for an explicit specialization.
3494	if (FunctionDecl *ExplicitSpec
3495	= S.ResolveSingleFunctionTemplateSpecialization(Ovl))
3496	return GetTypeOfFunction(S, R, ExplicitSpec);
3497	}
3498
3499	DeclAccessPair DAP;
3500	if (FunctionDecl *Viable =
3501	S.resolveAddressOfOnlyViableOverloadCandidate(Arg, DAP))
3502	return GetTypeOfFunction(S, R, Viable);
3503
3504	return {};
3505	}
3506
3507	// Gather the explicit template arguments, if any.
3508	TemplateArgumentListInfo ExplicitTemplateArgs;
3509	if (Ovl->hasExplicitTemplateArgs())
3510	Ovl->copyTemplateArgumentsInto(ExplicitTemplateArgs);
3511	QualType Match;
3512	for (UnresolvedSetIterator I = Ovl->decls_begin(),
3513	E = Ovl->decls_end(); I != E; ++I) {
3514	NamedDecl D = (I)->getUnderlyingDecl();
3515
3516	if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) {
3517	// - If the argument is an overload set containing one or more
3518	// function templates, the parameter is treated as a
3519	// non-deduced context.
3520	if (!Ovl->hasExplicitTemplateArgs())
3521	return {};
3522
3523	// Otherwise, see if we can resolve a function type
3524	FunctionDecl *Specialization = nullptr;
3525	TemplateDeductionInfo Info(Ovl->getNameLoc());
3526	if (S.DeduceTemplateArguments(FunTmpl, &ExplicitTemplateArgs,
3527	Specialization, Info))
3528	continue;
3529
3530	D = Specialization;
3531	}
3532
3533	FunctionDecl *Fn = cast<FunctionDecl>(D);
3534	QualType ArgType = GetTypeOfFunction(S, R, Fn);
3535	if (ArgType.isNull()) continue;
3536
3537	// Function-to-pointer conversion.
3538	if (!ParamWasReference && ParamType->isPointerType() &&
3539	ArgType->isFunctionType())
3540	ArgType = S.Context.getPointerType(ArgType);
3541
3542	// - If the argument is an overload set (not containing function
3543	// templates), trial argument deduction is attempted using each
3544	// of the members of the set. If deduction succeeds for only one
3545	// of the overload set members, that member is used as the
3546	// argument value for the deduction. If deduction succeeds for
3547	// more than one member of the overload set the parameter is
3548	// treated as a non-deduced context.
3549
3550	// We do all of this in a fresh context per C++0x [temp.deduct.type]p2:
3551	// Type deduction is done independently for each P/A pair, and
3552	// the deduced template argument values are then combined.
3553	// So we do not reject deductions which were made elsewhere.
3554	SmallVector<DeducedTemplateArgument, 8>
3555	Deduced(TemplateParams->size());
3556	TemplateDeductionInfo Info(Ovl->getNameLoc());
3557	Sema::TemplateDeductionResult Result
3558	= DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3559	ArgType, Info, Deduced, TDF);
3560	if (Result) continue;
3561	if (!Match.isNull())
3562	return {};
3563	Match = ArgType;
3564	}
3565
3566	return Match;
3567	}
3568
3569	/// Perform the adjustments to the parameter and argument types
3570	/// described in C++ [temp.deduct.call].
3571	///
3572	/// \returns true if the caller should not attempt to perform any template
3573	/// argument deduction based on this P/A pair because the argument is an
3574	/// overloaded function set that could not be resolved.
3575	static bool AdjustFunctionParmAndArgTypesForDeduction(
3576	Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
3577	QualType &ParamType, QualType &ArgType, Expr *Arg, unsigned &TDF) {
3578	// C++0x [temp.deduct.call]p3:
3579	// If P is a cv-qualified type, the top level cv-qualifiers of P's type
3580	// are ignored for type deduction.
3581	if (ParamType.hasQualifiers())
3582	ParamType = ParamType.getUnqualifiedType();
3583
3584	// [...] If P is a reference type, the type referred to by P is
3585	// used for type deduction.
3586	const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>();
3587	if (ParamRefType)
3588	ParamType = ParamRefType->getPointeeType();
3589
3590	// Overload sets usually make this parameter an undeduced context,
3591	// but there are sometimes special circumstances. Typically
3592	// involving a template-id-expr.
3593	if (ArgType == S.Context.OverloadTy) {
3594	ArgType = ResolveOverloadForDeduction(S, TemplateParams,
3595	Arg, ParamType,
3596	ParamRefType != nullptr);
3597	if (ArgType.isNull())
3598	return true;
3599	}
3600
3601	if (ParamRefType) {
3602	// If the argument has incomplete array type, try to complete its type.
3603	if (ArgType->isIncompleteArrayType()) {
3604	S.completeExprArrayBound(Arg);
3605	ArgType = Arg->getType();
3606	}
3607
3608	// C++1z [temp.deduct.call]p3:
3609	// If P is a forwarding reference and the argument is an lvalue, the type
3610	// "lvalue reference to A" is used in place of A for type deduction.
3611	if (isForwardingReference(QualType(ParamRefType, 0), FirstInnerIndex) &&
3612	Arg->isLValue())
3613	ArgType = S.Context.getLValueReferenceType(ArgType);
3614	} else {
3615	// C++ [temp.deduct.call]p2:
3616	// If P is not a reference type:
3617	// - If A is an array type, the pointer type produced by the
3618	// array-to-pointer standard conversion (4.2) is used in place of
3619	// A for type deduction; otherwise,
3620	if (ArgType->isArrayType())
3621	ArgType = S.Context.getArrayDecayedType(ArgType);
3622	// - If A is a function type, the pointer type produced by the
3623	// function-to-pointer standard conversion (4.3) is used in place
3624	// of A for type deduction; otherwise,
3625	else if (ArgType->isFunctionType())
3626	ArgType = S.Context.getPointerType(ArgType);
3627	else {
3628	// - If A is a cv-qualified type, the top level cv-qualifiers of A's
3629	// type are ignored for type deduction.
3630	ArgType = ArgType.getUnqualifiedType();
3631	}
3632	}
3633
3634	// C++0x [temp.deduct.call]p4:
3635	// In general, the deduction process attempts to find template argument
3636	// values that will make the deduced A identical to A (after the type A
3637	// is transformed as described above). [...]
3638	TDF = TDF_SkipNonDependent;
3639
3640	// - If the original P is a reference type, the deduced A (i.e., the
3641	// type referred to by the reference) can be more cv-qualified than
3642	// the transformed A.
3643	if (ParamRefType)
3644	TDF \|= TDF_ParamWithReferenceType;
3645	// - The transformed A can be another pointer or pointer to member
3646	// type that can be converted to the deduced A via a qualification
3647	// conversion (4.4).
3648	if (ArgType->isPointerType() \|\| ArgType->isMemberPointerType() \|\|
3649	ArgType->isObjCObjectPointerType())
3650	TDF \|= TDF_IgnoreQualifiers;
3651	// - If P is a class and P has the form simple-template-id, then the
3652	// transformed A can be a derived class of the deduced A. Likewise,
3653	// if P is a pointer to a class of the form simple-template-id, the
3654	// transformed A can be a pointer to a derived class pointed to by
3655	// the deduced A.
3656	if (isSimpleTemplateIdType(ParamType) \|\|
3657	(isa<PointerType>(ParamType) &&
3658	isSimpleTemplateIdType(
3659	ParamType->getAs<PointerType>()->getPointeeType())))
3660	TDF \|= TDF_DerivedClass;
3661
3662	return false;
3663	}
3664
3665	static bool
3666	hasDeducibleTemplateParameters(Sema &S, FunctionTemplateDecl *FunctionTemplate,
3667	QualType T);
3668
3669	static Sema::TemplateDeductionResult DeduceTemplateArgumentsFromCallArgument(
3670	Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
3671	QualType ParamType, Expr *Arg, TemplateDeductionInfo &Info,
3672	SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3673	SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs,
3674	bool DecomposedParam, unsigned ArgIdx, unsigned TDF);
3675
3676	/// Attempt template argument deduction from an initializer list
3677	/// deemed to be an argument in a function call.
3678	static Sema::TemplateDeductionResult DeduceFromInitializerList(
3679	Sema &S, TemplateParameterList *TemplateParams, QualType AdjustedParamType,
3680	InitListExpr *ILE, TemplateDeductionInfo &Info,
3681	SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3682	SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs, unsigned ArgIdx,
3683	unsigned TDF) {
3684	// C++ [temp.deduct.call]p1: (CWG 1591)
3685	// If removing references and cv-qualifiers from P gives
3686	// std::initializer_list<P0> or P0[N] for some P0 and N and the argument is
3687	// a non-empty initializer list, then deduction is performed instead for
3688	// each element of the initializer list, taking P0 as a function template
3689	// parameter type and the initializer element as its argument
3690	//
3691	// We've already removed references and cv-qualifiers here.
3692	if (!ILE->getNumInits())
3693	return Sema::TDK_Success;
3694
3695	QualType ElTy;
3696	auto *ArrTy = S.Context.getAsArrayType(AdjustedParamType);
3697	if (ArrTy)
3698	ElTy = ArrTy->getElementType();
3699	else if (!S.isStdInitializerList(AdjustedParamType, &ElTy)) {
3700	// Otherwise, an initializer list argument causes the parameter to be
3701	// considered a non-deduced context
3702	return Sema::TDK_Success;
3703	}
3704
3705	// Deduction only needs to be done for dependent types.
3706	if (ElTy->isDependentType()) {
3707	for (Expr *E : ILE->inits()) {
3708	if (auto Result = DeduceTemplateArgumentsFromCallArgument(
3709	S, TemplateParams, 0, ElTy, E, Info, Deduced, OriginalCallArgs, true,
3710	ArgIdx, TDF))
3711	return Result;
3712	}
3713	}
3714
3715	// in the P0[N] case, if N is a non-type template parameter, N is deduced
3716	// from the length of the initializer list.
3717	if (auto *DependentArrTy = dyn_cast_or_null<DependentSizedArrayType>(ArrTy)) {
3718	// Determine the array bound is something we can deduce.
3719	if (NonTypeTemplateParmDecl *NTTP =
3720	getDeducedParameterFromExpr(Info, DependentArrTy->getSizeExpr())) {
3721	// We can perform template argument deduction for the given non-type
3722	// template parameter.
3723	// C++ [temp.deduct.type]p13:
3724	// The type of N in the type T[N] is std::size_t.
3725	QualType T = S.Context.getSizeType();
3726	llvm::APInt Size(S.Context.getIntWidth(T), ILE->getNumInits());
3727	if (auto Result = DeduceNonTypeTemplateArgument(
3728	S, TemplateParams, NTTP, llvm::APSInt(Size), T,
3729	/ArrayBound=/true, Info, Deduced))
3730	return Result;
3731	}
3732	}
3733
3734	return Sema::TDK_Success;
3735	}
3736
3737	/// Perform template argument deduction per [temp.deduct.call] for a
3738	/// single parameter / argument pair.
3739	static Sema::TemplateDeductionResult DeduceTemplateArgumentsFromCallArgument(
3740	Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
3741	QualType ParamType, Expr *Arg, TemplateDeductionInfo &Info,
3742	SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3743	SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs,
3744	bool DecomposedParam, unsigned ArgIdx, unsigned TDF) {
3745	QualType ArgType = Arg->getType();
3746	QualType OrigParamType = ParamType;
3747
3748	// If P is a reference type [...]
3749	// If P is a cv-qualified type [...]
3750	if (AdjustFunctionParmAndArgTypesForDeduction(
3751	S, TemplateParams, FirstInnerIndex, ParamType, ArgType, Arg, TDF))
3752	return Sema::TDK_Success;
3753
3754	// If [...] the argument is a non-empty initializer list [...]
3755	if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg))
3756	return DeduceFromInitializerList(S, TemplateParams, ParamType, ILE, Info,
3757	Deduced, OriginalCallArgs, ArgIdx, TDF);
3758
3759	// [...] the deduction process attempts to find template argument values
3760	// that will make the deduced A identical to A
3761	//
3762	// Keep track of the argument type and corresponding parameter index,
3763	// so we can check for compatibility between the deduced A and A.
3764	OriginalCallArgs.push_back(
3765	Sema::OriginalCallArg(OrigParamType, DecomposedParam, ArgIdx, ArgType));
3766	return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3767	ArgType, Info, Deduced, TDF);
3768	}
3769
3770	/// Perform template argument deduction from a function call
3771	/// (C++ [temp.deduct.call]).
3772	///
3773	/// \param FunctionTemplate the function template for which we are performing
3774	/// template argument deduction.
3775	///
3776	/// \param ExplicitTemplateArgs the explicit template arguments provided
3777	/// for this call.
3778	///
3779	/// \param Args the function call arguments
3780	///
3781	/// \param Specialization if template argument deduction was successful,
3782	/// this will be set to the function template specialization produced by
3783	/// template argument deduction.
3784	///
3785	/// \param Info the argument will be updated to provide additional information
3786	/// about template argument deduction.
3787	///
3788	/// \param CheckNonDependent A callback to invoke to check conversions for
3789	/// non-dependent parameters, between deduction and substitution, per DR1391.
3790	/// If this returns true, substitution will be skipped and we return
3791	/// TDK_NonDependentConversionFailure. The callback is passed the parameter
3792	/// types (after substituting explicit template arguments).
3793	///
3794	/// \returns the result of template argument deduction.
3795	Sema::TemplateDeductionResult Sema::DeduceTemplateArguments(
3796	FunctionTemplateDecl *FunctionTemplate,
3797	TemplateArgumentListInfo ExplicitTemplateArgs, ArrayRef<Expr > Args,
3798	FunctionDecl *&Specialization, TemplateDeductionInfo &Info,
3799	bool PartialOverloading,
3800	llvm::function_ref<bool(ArrayRef<QualType>)> CheckNonDependent) {
3801	if (FunctionTemplate->isInvalidDecl())
3802	return TDK_Invalid;
3803
3804	FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3805	unsigned NumParams = Function->getNumParams();
3806
3807	unsigned FirstInnerIndex = getFirstInnerIndex(FunctionTemplate);
3808
3809	// C++ [temp.deduct.call]p1:
3810	// Template argument deduction is done by comparing each function template
3811	// parameter type (call it P) with the type of the corresponding argument
3812	// of the call (call it A) as described below.
3813	if (Args.size() < Function->getMinRequiredArguments() && !PartialOverloading)
3814	return TDK_TooFewArguments;
3815	else if (TooManyArguments(NumParams, Args.size(), PartialOverloading)) {
3816	const FunctionProtoType *Proto
3817	= Function->getType()->getAs<FunctionProtoType>();
3818	if (Proto->isTemplateVariadic())
3819	/* Do nothing */;
3820	else if (!Proto->isVariadic())
3821	return TDK_TooManyArguments;
3822	}
3823
3824	// The types of the parameters from which we will perform template argument
3825	// deduction.
3826	LocalInstantiationScope InstScope(*this);
3827	TemplateParameterList *TemplateParams
3828	= FunctionTemplate->getTemplateParameters();
3829	SmallVector<DeducedTemplateArgument, 4> Deduced;
3830	SmallVector<QualType, 8> ParamTypes;
3831	unsigned NumExplicitlySpecified = 0;
3832	if (ExplicitTemplateArgs) {
3833	TemplateDeductionResult Result =
3834	SubstituteExplicitTemplateArguments(FunctionTemplate,
3835	*ExplicitTemplateArgs,
3836	Deduced,
3837	ParamTypes,
3838	nullptr,
3839	Info);
3840	if (Result)
3841	return Result;
3842
3843	NumExplicitlySpecified = Deduced.size();
3844	} else {
3845	// Just fill in the parameter types from the function declaration.
3846	for (unsigned I = 0; I != NumParams; ++I)
3847	ParamTypes.push_back(Function->getParamDecl(I)->getType());
3848	}
3849
3850	SmallVector<OriginalCallArg, 8> OriginalCallArgs;
3851
3852	// Deduce an argument of type ParamType from an expression with index ArgIdx.
3853	auto DeduceCallArgument = [&](QualType ParamType, unsigned ArgIdx) {
3854	// C++ [demp.deduct.call]p1: (DR1391)
3855	// Template argument deduction is done by comparing each function template
3856	// parameter that contains template-parameters that participate in
3857	// template argument deduction ...
3858	if (!hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
3859	return Sema::TDK_Success;
3860
3861	// ... with the type of the corresponding argument
3862	return DeduceTemplateArgumentsFromCallArgument(
3863	*this, TemplateParams, FirstInnerIndex, ParamType, Args[ArgIdx], Info, Deduced,
3864	OriginalCallArgs, /Decomposed/false, ArgIdx, /TDF/ 0);
3865	};
3866
3867	// Deduce template arguments from the function parameters.
3868	Deduced.resize(TemplateParams->size());
3869	SmallVector<QualType, 8> ParamTypesForArgChecking;
3870	for (unsigned ParamIdx = 0, NumParamTypes = ParamTypes.size(), ArgIdx = 0;
3871	ParamIdx != NumParamTypes; ++ParamIdx) {
3872	QualType ParamType = ParamTypes[ParamIdx];
3873
3874	const PackExpansionType *ParamExpansion =
3875	dyn_cast<PackExpansionType>(ParamType);
3876	if (!ParamExpansion) {
3877	// Simple case: matching a function parameter to a function argument.
3878	if (ArgIdx >= Args.size())
3879	break;
3880
3881	ParamTypesForArgChecking.push_back(ParamType);
3882	if (auto Result = DeduceCallArgument(ParamType, ArgIdx++))
3883	return Result;
3884
3885	continue;
3886	}
3887
3888	QualType ParamPattern = ParamExpansion->getPattern();
3889	PackDeductionScope PackScope(*this, TemplateParams, Deduced, Info,
3890	ParamPattern);
3891
3892	// C++0x [temp.deduct.call]p1:
3893	// For a function parameter pack that occurs at the end of the
3894	// parameter-declaration-list, the type A of each remaining argument of
3895	// the call is compared with the type P of the declarator-id of the
3896	// function parameter pack. Each comparison deduces template arguments
3897	// for subsequent positions in the template parameter packs expanded by
3898	// the function parameter pack. When a function parameter pack appears
3899	// in a non-deduced context [not at the end of the list], the type of
3900	// that parameter pack is never deduced.
3901	//
3902	// FIXME: The above rule allows the size of the parameter pack to change
3903	// after we skip it (in the non-deduced case). That makes no sense, so
3904	// we instead notionally deduce the pack against N arguments, where N is
3905	// the length of the explicitly-specified pack if it's expanded by the
3906	// parameter pack and 0 otherwise, and we treat each deduction as a
3907	// non-deduced context.
3908	if (ParamIdx + 1 == NumParamTypes \|\| PackScope.hasFixedArity()) {
3909	for (; ArgIdx < Args.size() && PackScope.hasNextElement();
3910	PackScope.nextPackElement(), ++ArgIdx) {
3911	ParamTypesForArgChecking.push_back(ParamPattern);
3912	if (auto Result = DeduceCallArgument(ParamPattern, ArgIdx))
3913	return Result;
3914	}
3915	} else {
3916	// If the parameter type contains an explicitly-specified pack that we
3917	// could not expand, skip the number of parameters notionally created
3918	// by the expansion.
3919	Optional<unsigned> NumExpansions = ParamExpansion->getNumExpansions();
3920	if (NumExpansions && !PackScope.isPartiallyExpanded()) {
3921	for (unsigned I = 0; I != *NumExpansions && ArgIdx < Args.size();
3922	++I, ++ArgIdx) {
3923	ParamTypesForArgChecking.push_back(ParamPattern);
3924	// FIXME: Should we add OriginalCallArgs for these? What if the
3925	// corresponding argument is a list?
3926	PackScope.nextPackElement();
3927	}
3928	}
3929	}
3930
3931	// Build argument packs for each of the parameter packs expanded by this
3932	// pack expansion.
3933	if (auto Result = PackScope.finish())
3934	return Result;
3935	}
3936
3937	// Capture the context in which the function call is made. This is the context
3938	// that is needed when the accessibility of template arguments is checked.
3939	DeclContext *CallingCtx = CurContext;
3940
3941	return FinishTemplateArgumentDeduction(
3942	FunctionTemplate, Deduced, NumExplicitlySpecified, Specialization, Info,
3943	&OriginalCallArgs, PartialOverloading, [&, CallingCtx]() {
3944	ContextRAII SavedContext(*this, CallingCtx);
3945	return CheckNonDependent(ParamTypesForArgChecking);
3946	});
3947	}
3948
3949	QualType Sema::adjustCCAndNoReturn(QualType ArgFunctionType,
3950	QualType FunctionType,
3951	bool AdjustExceptionSpec) {
3952	if (ArgFunctionType.isNull())
3953	return ArgFunctionType;
3954
3955	const FunctionProtoType *FunctionTypeP =
3956	FunctionType->castAs<FunctionProtoType>();
3957	const FunctionProtoType *ArgFunctionTypeP =
3958	ArgFunctionType->getAs<FunctionProtoType>();
3959
3960	FunctionProtoType::ExtProtoInfo EPI = ArgFunctionTypeP->getExtProtoInfo();
3961	bool Rebuild = false;
3962
3963	CallingConv CC = FunctionTypeP->getCallConv();
3964	if (EPI.ExtInfo.getCC() != CC) {
3965	EPI.ExtInfo = EPI.ExtInfo.withCallingConv(CC);
3966	Rebuild = true;
3967	}
3968
3969	bool NoReturn = FunctionTypeP->getNoReturnAttr();
3970	if (EPI.ExtInfo.getNoReturn() != NoReturn) {
3971	EPI.ExtInfo = EPI.ExtInfo.withNoReturn(NoReturn);
3972	Rebuild = true;
3973	}
3974
3975	if (AdjustExceptionSpec && (FunctionTypeP->hasExceptionSpec() \|\|
3976	ArgFunctionTypeP->hasExceptionSpec())) {
3977	EPI.ExceptionSpec = FunctionTypeP->getExtProtoInfo().ExceptionSpec;
3978	Rebuild = true;
3979	}
3980
3981	if (!Rebuild)
3982	return ArgFunctionType;
3983
3984	return Context.getFunctionType(ArgFunctionTypeP->getReturnType(),
3985	ArgFunctionTypeP->getParamTypes(), EPI);
3986	}
3987
3988	/// Deduce template arguments when taking the address of a function
3989	/// template (C++ [temp.deduct.funcaddr]) or matching a specialization to
3990	/// a template.
3991	///
3992	/// \param FunctionTemplate the function template for which we are performing
3993	/// template argument deduction.
3994	///
3995	/// \param ExplicitTemplateArgs the explicitly-specified template
3996	/// arguments.
3997	///
3998	/// \param ArgFunctionType the function type that will be used as the
3999	/// "argument" type (A) when performing template argument deduction from the
4000	/// function template's function type. This type may be NULL, if there is no
4001	/// argument type to compare against, in C++0x [temp.arg.explicit]p3.
4002	///
4003	/// \param Specialization if template argument deduction was successful,
4004	/// this will be set to the function template specialization produced by
4005	/// template argument deduction.
4006	///
4007	/// \param Info the argument will be updated to provide additional information
4008	/// about template argument deduction.
4009	///
4010	/// \param IsAddressOfFunction If \c true, we are deducing as part of taking
4011	/// the address of a function template per [temp.deduct.funcaddr] and
4012	/// [over.over]. If \c false, we are looking up a function template
4013	/// specialization based on its signature, per [temp.deduct.decl].
4014	///
4015	/// \returns the result of template argument deduction.
4016	Sema::TemplateDeductionResult Sema::DeduceTemplateArguments(
4017	FunctionTemplateDecl *FunctionTemplate,
4018	TemplateArgumentListInfo *ExplicitTemplateArgs, QualType ArgFunctionType,
4019	FunctionDecl *&Specialization, TemplateDeductionInfo &Info,
4020	bool IsAddressOfFunction) {
4021	if (FunctionTemplate->isInvalidDecl())
4022	return TDK_Invalid;
4023
4024	FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
4025	TemplateParameterList *TemplateParams
4026	= FunctionTemplate->getTemplateParameters();
4027	QualType FunctionType = Function->getType();
4028
4029	// Substitute any explicit template arguments.
4030	LocalInstantiationScope InstScope(*this);
4031	SmallVector<DeducedTemplateArgument, 4> Deduced;
4032	unsigned NumExplicitlySpecified = 0;
4033	SmallVector<QualType, 4> ParamTypes;
4034	if (ExplicitTemplateArgs) {
4035	if (TemplateDeductionResult Result
4036	= SubstituteExplicitTemplateArguments(FunctionTemplate,
4037	*ExplicitTemplateArgs,
4038	Deduced, ParamTypes,
4039	&FunctionType, Info))
4040	return Result;
4041
4042	NumExplicitlySpecified = Deduced.size();
4043	}
4044
4045	// When taking the address of a function, we require convertibility of
4046	// the resulting function type. Otherwise, we allow arbitrary mismatches
4047	// of calling convention and noreturn.
4048	if (!IsAddressOfFunction)
4049	ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, FunctionType,
4050	/AdjustExceptionSpec/false);
4051
4052	// Unevaluated SFINAE context.
4053	EnterExpressionEvaluationContext Unevaluated(
4054	*this, Sema::ExpressionEvaluationContext::Unevaluated);
4055	SFINAETrap Trap(*this);
4056
4057	Deduced.resize(TemplateParams->size());
4058
4059	// If the function has a deduced return type, substitute it for a dependent
4060	// type so that we treat it as a non-deduced context in what follows. If we
4061	// are looking up by signature, the signature type should also have a deduced
4062	// return type, which we instead expect to exactly match.
4063	bool HasDeducedReturnType = false;
4064	if (getLangOpts().CPlusPlus14 && IsAddressOfFunction &&
4065	Function->getReturnType()->getContainedAutoType()) {
4066	FunctionType = SubstAutoType(FunctionType, Context.DependentTy);
4067	HasDeducedReturnType = true;
4068	}
4069
4070	if (!ArgFunctionType.isNull()) {
4071	unsigned TDF =
4072	TDF_TopLevelParameterTypeList \| TDF_AllowCompatibleFunctionType;
4073	// Deduce template arguments from the function type.
4074	if (TemplateDeductionResult Result
4075	= DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
4076	FunctionType, ArgFunctionType,
4077	Info, Deduced, TDF))
4078	return Result;
4079	}
4080
4081	if (TemplateDeductionResult Result
4082	= FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
4083	NumExplicitlySpecified,
4084	Specialization, Info))
4085	return Result;
4086
4087	// If the function has a deduced return type, deduce it now, so we can check
4088	// that the deduced function type matches the requested type.
4089	if (HasDeducedReturnType &&
4090	Specialization->getReturnType()->isUndeducedType() &&
4091	DeduceReturnType(Specialization, Info.getLocation(), false))
4092	return TDK_MiscellaneousDeductionFailure;
4093
4094	// If the function has a dependent exception specification, resolve it now,
4095	// so we can check that the exception specification matches.
4096	auto *SpecializationFPT =
4097	Specialization->getType()->castAs<FunctionProtoType>();
4098	if (getLangOpts().CPlusPlus17 &&
4099	isUnresolvedExceptionSpec(SpecializationFPT->getExceptionSpecType()) &&
4100	!ResolveExceptionSpec(Info.getLocation(), SpecializationFPT))
4101	return TDK_MiscellaneousDeductionFailure;
4102
4103	// Adjust the exception specification of the argument to match the
4104	// substituted and resolved type we just formed. (Calling convention and
4105	// noreturn can't be dependent, so we don't actually need this for them
4106	// right now.)
4107	QualType SpecializationType = Specialization->getType();
4108	if (!IsAddressOfFunction)
4109	ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, SpecializationType,
4110	/AdjustExceptionSpec/true);
4111
4112	// If the requested function type does not match the actual type of the
4113	// specialization with respect to arguments of compatible pointer to function
4114	// types, template argument deduction fails.
4115	if (!ArgFunctionType.isNull()) {
4116	if (IsAddressOfFunction &&
4117	!isSameOrCompatibleFunctionType(
4118	Context.getCanonicalType(SpecializationType),
4119	Context.getCanonicalType(ArgFunctionType)))
4120	return TDK_MiscellaneousDeductionFailure;
4121
4122	if (!IsAddressOfFunction &&
4123	!Context.hasSameType(SpecializationType, ArgFunctionType))
4124	return TDK_MiscellaneousDeductionFailure;
4125	}
4126
4127	return TDK_Success;
4128	}
4129
4130	/// Deduce template arguments for a templated conversion
4131	/// function (C++ [temp.deduct.conv]) and, if successful, produce a
4132	/// conversion function template specialization.
4133	Sema::TemplateDeductionResult
4134	Sema::DeduceTemplateArguments(FunctionTemplateDecl *ConversionTemplate,
4135	QualType ToType,
4136	CXXConversionDecl *&Specialization,
4137	TemplateDeductionInfo &Info) {
4138	if (ConversionTemplate->isInvalidDecl())
4139	return TDK_Invalid;
4140
4141	CXXConversionDecl *ConversionGeneric
4142	= cast<CXXConversionDecl>(ConversionTemplate->getTemplatedDecl());
4143
4144	QualType FromType = ConversionGeneric->getConversionType();
4145
4146	// Canonicalize the types for deduction.
4147	QualType P = Context.getCanonicalType(FromType);
4148	QualType A = Context.getCanonicalType(ToType);
4149
4150	// C++0x [temp.deduct.conv]p2:
4151	// If P is a reference type, the type referred to by P is used for
4152	// type deduction.
4153	if (const ReferenceType *PRef = P->getAs<ReferenceType>())
4154	P = PRef->getPointeeType();
4155
4156	// C++0x [temp.deduct.conv]p4:
4157	// [...] If A is a reference type, the type referred to by A is used
4158	// for type deduction.
4159	if (const ReferenceType *ARef = A->getAs<ReferenceType>()) {
4160	A = ARef->getPointeeType();
4161	// We work around a defect in the standard here: cv-qualifiers are also
4162	// removed from P and A in this case, unless P was a reference type. This
4163	// seems to mostly match what other compilers are doing.
4164	if (!FromType->getAs<ReferenceType>()) {
4165	A = A.getUnqualifiedType();
4166	P = P.getUnqualifiedType();
4167	}
4168
4169	// C++ [temp.deduct.conv]p3:
4170	//
4171	// If A is not a reference type:
4172	} else {
4173	(0) . __assert_fail ("!A->isReferenceType() && \"Reference types were handled above\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 4173, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(!A->isReferenceType() && "Reference types were handled above");
4174
4175	// - If P is an array type, the pointer type produced by the
4176	// array-to-pointer standard conversion (4.2) is used in place
4177	// of P for type deduction; otherwise,
4178	if (P->isArrayType())
4179	P = Context.getArrayDecayedType(P);
4180	// - If P is a function type, the pointer type produced by the
4181	// function-to-pointer standard conversion (4.3) is used in
4182	// place of P for type deduction; otherwise,
4183	else if (P->isFunctionType())
4184	P = Context.getPointerType(P);
4185	// - If P is a cv-qualified type, the top level cv-qualifiers of
4186	// P's type are ignored for type deduction.
4187	else
4188	P = P.getUnqualifiedType();
4189
4190	// C++0x [temp.deduct.conv]p4:
4191	// If A is a cv-qualified type, the top level cv-qualifiers of A's
4192	// type are ignored for type deduction. If A is a reference type, the type
4193	// referred to by A is used for type deduction.
4194	A = A.getUnqualifiedType();
4195	}
4196
4197	// Unevaluated SFINAE context.
4198	EnterExpressionEvaluationContext Unevaluated(
4199	*this, Sema::ExpressionEvaluationContext::Unevaluated);
4200	SFINAETrap Trap(*this);
4201
4202	// C++ [temp.deduct.conv]p1:
4203	// Template argument deduction is done by comparing the return
4204	// type of the template conversion function (call it P) with the
4205	// type that is required as the result of the conversion (call it
4206	// A) as described in 14.8.2.4.
4207	TemplateParameterList *TemplateParams
4208	= ConversionTemplate->getTemplateParameters();
4209	SmallVector<DeducedTemplateArgument, 4> Deduced;
4210	Deduced.resize(TemplateParams->size());
4211
4212	// C++0x [temp.deduct.conv]p4:
4213	// In general, the deduction process attempts to find template
4214	// argument values that will make the deduced A identical to
4215	// A. However, there are two cases that allow a difference:
4216	unsigned TDF = 0;
4217	// - If the original A is a reference type, A can be more
4218	// cv-qualified than the deduced A (i.e., the type referred to
4219	// by the reference)
4220	if (ToType->isReferenceType())
4221	TDF \|= TDF_ArgWithReferenceType;
4222	// - The deduced A can be another pointer or pointer to member
4223	// type that can be converted to A via a qualification
4224	// conversion.
4225	//
4226	// (C++0x [temp.deduct.conv]p6 clarifies that this only happens when
4227	// both P and A are pointers or member pointers. In this case, we
4228	// just ignore cv-qualifiers completely).
4229	if ((P->isPointerType() && A->isPointerType()) \|\|
4230	(P->isMemberPointerType() && A->isMemberPointerType()))
4231	TDF \|= TDF_IgnoreQualifiers;
4232	if (TemplateDeductionResult Result
4233	= DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
4234	P, A, Info, Deduced, TDF))
4235	return Result;
4236
4237	// Create an Instantiation Scope for finalizing the operator.
4238	LocalInstantiationScope InstScope(*this);
4239	// Finish template argument deduction.
4240	FunctionDecl *ConversionSpecialized = nullptr;
4241	TemplateDeductionResult Result
4242	= FinishTemplateArgumentDeduction(ConversionTemplate, Deduced, 0,
4243	ConversionSpecialized, Info);
4244	Specialization = cast_or_null<CXXConversionDecl>(ConversionSpecialized);
4245	return Result;
4246	}
4247
4248	/// Deduce template arguments for a function template when there is
4249	/// nothing to deduce against (C++0x [temp.arg.explicit]p3).
4250	///
4251	/// \param FunctionTemplate the function template for which we are performing
4252	/// template argument deduction.
4253	///
4254	/// \param ExplicitTemplateArgs the explicitly-specified template
4255	/// arguments.
4256	///
4257	/// \param Specialization if template argument deduction was successful,
4258	/// this will be set to the function template specialization produced by
4259	/// template argument deduction.
4260	///
4261	/// \param Info the argument will be updated to provide additional information
4262	/// about template argument deduction.
4263	///
4264	/// \param IsAddressOfFunction If \c true, we are deducing as part of taking
4265	/// the address of a function template in a context where we do not have a
4266	/// target type, per [over.over]. If \c false, we are looking up a function
4267	/// template specialization based on its signature, which only happens when
4268	/// deducing a function parameter type from an argument that is a template-id
4269	/// naming a function template specialization.
4270	///
4271	/// \returns the result of template argument deduction.
4272	Sema::TemplateDeductionResult Sema::DeduceTemplateArguments(
4273	FunctionTemplateDecl *FunctionTemplate,
4274	TemplateArgumentListInfo *ExplicitTemplateArgs,
4275	FunctionDecl *&Specialization, TemplateDeductionInfo &Info,
4276	bool IsAddressOfFunction) {
4277	return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs,
4278	QualType(), Specialization, Info,
4279	IsAddressOfFunction);
4280	}
4281
4282	namespace {
4283
4284	/// Substitute the 'auto' specifier or deduced template specialization type
4285	/// specifier within a type for a given replacement type.
4286	class SubstituteDeducedTypeTransform :
4287	public TreeTransform<SubstituteDeducedTypeTransform> {
4288	QualType Replacement;
4289	bool UseTypeSugar;
4290
4291	public:
4292	SubstituteDeducedTypeTransform(Sema &SemaRef, QualType Replacement,
4293	bool UseTypeSugar = true)
4294	: TreeTransform<SubstituteDeducedTypeTransform>(SemaRef),
4295	Replacement(Replacement), UseTypeSugar(UseTypeSugar) {}
4296
4297	QualType TransformDesugared(TypeLocBuilder &TLB, DeducedTypeLoc TL) {
4298	(0) . __assert_fail ("isa(Replacement) && \"unexpected unsugared replacement kind\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 4299, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(isa<TemplateTypeParmType>(Replacement) &&
4299	(0) . __assert_fail ("isa(Replacement) && \"unexpected unsugared replacement kind\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 4299, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "unexpected unsugared replacement kind");
4300	QualType Result = Replacement;
4301	TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
4302	NewTL.setNameLoc(TL.getNameLoc());
4303	return Result;
4304	}
4305
4306	QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) {
4307	// If we're building the type pattern to deduce against, don't wrap the
4308	// substituted type in an AutoType. Certain template deduction rules
4309	// apply only when a template type parameter appears directly (and not if
4310	// the parameter is found through desugaring). For instance:
4311	// auto &&lref = lvalue;
4312	// must transform into "rvalue reference to T" not "rvalue reference to
4313	// auto type deduced as T" in order for [temp.deduct.call]p3 to apply.
4314	//
4315	// FIXME: Is this still necessary?
4316	if (!UseTypeSugar)
4317	return TransformDesugared(TLB, TL);
4318
4319	QualType Result = SemaRef.Context.getAutoType(
4320	Replacement, TL.getTypePtr()->getKeyword(), Replacement.isNull());
4321	auto NewTL = TLB.push<AutoTypeLoc>(Result);
4322	NewTL.setNameLoc(TL.getNameLoc());
4323	return Result;
4324	}
4325
4326	QualType TransformDeducedTemplateSpecializationType(
4327	TypeLocBuilder &TLB, DeducedTemplateSpecializationTypeLoc TL) {
4328	if (!UseTypeSugar)
4329	return TransformDesugared(TLB, TL);
4330
4331	QualType Result = SemaRef.Context.getDeducedTemplateSpecializationType(
4332	TL.getTypePtr()->getTemplateName(),
4333	Replacement, Replacement.isNull());
4334	auto NewTL = TLB.push<DeducedTemplateSpecializationTypeLoc>(Result);
4335	NewTL.setNameLoc(TL.getNameLoc());
4336	return Result;
4337	}
4338
4339	ExprResult TransformLambdaExpr(LambdaExpr *E) {
4340	// Lambdas never need to be transformed.
4341	return E;
4342	}
4343
4344	QualType Apply(TypeLoc TL) {
4345	// Create some scratch storage for the transformed type locations.
4346	// FIXME: We're just going to throw this information away. Don't build it.
4347	TypeLocBuilder TLB;
4348	TLB.reserve(TL.getFullDataSize());
4349	return TransformType(TLB, TL);
4350	}
4351	};
4352
4353	} // namespace
4354
4355	Sema::DeduceAutoResult
4356	Sema::DeduceAutoType(TypeSourceInfo Type, Expr &Init, QualType &Result,
4357	Optional<unsigned> DependentDeductionDepth) {
4358	return DeduceAutoType(Type->getTypeLoc(), Init, Result,
4359	DependentDeductionDepth);
4360	}
4361
4362	/// Attempt to produce an informative diagostic explaining why auto deduction
4363	/// failed.
4364	/// \return \c true if diagnosed, \c false if not.
4365	static bool diagnoseAutoDeductionFailure(Sema &S,
4366	Sema::TemplateDeductionResult TDK,
4367	TemplateDeductionInfo &Info,
4368	ArrayRef<SourceRange> Ranges) {
4369	switch (TDK) {
4370	case Sema::TDK_Inconsistent: {
4371	// Inconsistent deduction means we were deducing from an initializer list.
4372	auto D = S.Diag(Info.getLocation(), diag::err_auto_inconsistent_deduction);
4373	D << Info.FirstArg << Info.SecondArg;
4374	for (auto R : Ranges)
4375	D << R;
4376	return true;
4377	}
4378
4379	// FIXME: Are there other cases for which a custom diagnostic is more useful
4380	// than the basic "types don't match" diagnostic?
4381
4382	default:
4383	return false;
4384	}
4385	}
4386
4387	/// Deduce the type for an auto type-specifier (C++11 [dcl.spec.auto]p6)
4388	///
4389	/// Note that this is done even if the initializer is dependent. (This is
4390	/// necessary to support partial ordering of templates using 'auto'.)
4391	/// A dependent type will be produced when deducing from a dependent type.
4392	///
4393	/// \param Type the type pattern using the auto type-specifier.
4394	/// \param Init the initializer for the variable whose type is to be deduced.
4395	/// \param Result if type deduction was successful, this will be set to the
4396	/// deduced type.
4397	/// \param DependentDeductionDepth Set if we should permit deduction in
4398	/// dependent cases. This is necessary for template partial ordering with
4399	/// 'auto' template parameters. The value specified is the template
4400	/// parameter depth at which we should perform 'auto' deduction.
4401	Sema::DeduceAutoResult
4402	Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result,
4403	Optional<unsigned> DependentDeductionDepth) {
4404	if (Init->getType()->isNonOverloadPlaceholderType()) {
4405	ExprResult NonPlaceholder = CheckPlaceholderExpr(Init);
4406	if (NonPlaceholder.isInvalid())
4407	return DAR_FailedAlreadyDiagnosed;
4408	Init = NonPlaceholder.get();
4409	}
4410
4411	if (!DependentDeductionDepth &&
4412	(Type.getType()->isDependentType() \|\| Init->isTypeDependent())) {
4413	Result = SubstituteDeducedTypeTransform(*this, QualType()).Apply(Type);
4414	(0) . __assert_fail ("!Result.isNull() && \"substituting DependentTy can't fail\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 4414, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(!Result.isNull() && "substituting DependentTy can't fail");
4415	return DAR_Succeeded;
4416	}
4417
4418	// Find the depth of template parameter to synthesize.
4419	unsigned Depth = DependentDeductionDepth.getValueOr(0);
4420
4421	// If this is a 'decltype(auto)' specifier, do the decltype dance.
4422	// Since 'decltype(auto)' can only occur at the top of the type, we
4423	// don't need to go digging for it.
4424	if (const AutoType *AT = Type.getType()->getAs<AutoType>()) {
4425	if (AT->isDecltypeAuto()) {
4426	if (isa<InitListExpr>(Init)) {
4427	Diag(Init->getBeginLoc(), diag::err_decltype_auto_initializer_list);
4428	return DAR_FailedAlreadyDiagnosed;
4429	}
4430
4431	ExprResult ER = CheckPlaceholderExpr(Init);
4432	if (ER.isInvalid())
4433	return DAR_FailedAlreadyDiagnosed;
4434	Init = ER.get();
4435	QualType Deduced = BuildDecltypeType(Init, Init->getBeginLoc(), false);
4436	if (Deduced.isNull())
4437	return DAR_FailedAlreadyDiagnosed;
4438	// FIXME: Support a non-canonical deduced type for 'auto'.
4439	Deduced = Context.getCanonicalType(Deduced);
4440	Result = SubstituteDeducedTypeTransform(*this, Deduced).Apply(Type);
4441	if (Result.isNull())
4442	return DAR_FailedAlreadyDiagnosed;
4443	return DAR_Succeeded;
4444	} else if (!getLangOpts().CPlusPlus) {
4445	if (isa<InitListExpr>(Init)) {
4446	Diag(Init->getBeginLoc(), diag::err_auto_init_list_from_c);
4447	return DAR_FailedAlreadyDiagnosed;
4448	}
4449	}
4450	}
4451
4452	SourceLocation Loc = Init->getExprLoc();
4453
4454	LocalInstantiationScope InstScope(*this);
4455
4456	// Build template<class TemplParam> void Func(FuncParam);
4457	TemplateTypeParmDecl *TemplParam = TemplateTypeParmDecl::Create(
4458	Context, nullptr, SourceLocation(), Loc, Depth, 0, nullptr, false, false);
4459	QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0);
4460	NamedDecl *TemplParamPtr = TemplParam;
4461	FixedSizeTemplateParameterListStorage<1, false> TemplateParamsSt(
4462	Loc, Loc, TemplParamPtr, Loc, nullptr);
4463
4464	QualType FuncParam =
4465	SubstituteDeducedTypeTransform(this, TemplArg, /UseTypeSugar*/false)
4466	.Apply(Type);
4467	(0) . __assert_fail ("!FuncParam.isNull() && \"substituting template parameter for 'auto' failed\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 4468, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(!FuncParam.isNull() &&
4468	(0) . __assert_fail ("!FuncParam.isNull() && \"substituting template parameter for 'auto' failed\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 4468, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "substituting template parameter for 'auto' failed");
4469
4470	// Deduce type of TemplParam in Func(Init)
4471	SmallVector<DeducedTemplateArgument, 1> Deduced;
4472	Deduced.resize(1);
4473
4474	TemplateDeductionInfo Info(Loc, Depth);
4475
4476	// If deduction failed, don't diagnose if the initializer is dependent; it
4477	// might acquire a matching type in the instantiation.
4478	auto DeductionFailed = [&](TemplateDeductionResult TDK,
4479	ArrayRef<SourceRange> Ranges) -> DeduceAutoResult {
4480	if (Init->isTypeDependent()) {
4481	Result = SubstituteDeducedTypeTransform(*this, QualType()).Apply(Type);
4482	(0) . __assert_fail ("!Result.isNull() && \"substituting DependentTy can't fail\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 4482, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(!Result.isNull() && "substituting DependentTy can't fail");
4483	return DAR_Succeeded;
4484	}
4485	if (diagnoseAutoDeductionFailure(*this, TDK, Info, Ranges))
4486	return DAR_FailedAlreadyDiagnosed;
4487	return DAR_Failed;
4488	};
4489
4490	SmallVector<OriginalCallArg, 4> OriginalCallArgs;
4491
4492	InitListExpr *InitList = dyn_cast<InitListExpr>(Init);
4493	if (InitList) {
4494	// Notionally, we substitute std::initializer_list<T> for 'auto' and deduce
4495	// against that. Such deduction only succeeds if removing cv-qualifiers and
4496	// references results in std::initializer_list<T>.
4497	if (!Type.getType().getNonReferenceType()->getAs<AutoType>())
4498	return DAR_Failed;
4499
4500	SourceRange DeducedFromInitRange;
4501	for (unsigned i = 0, e = InitList->getNumInits(); i < e; ++i) {
4502	Expr *Init = InitList->getInit(i);
4503
4504	if (auto TDK = DeduceTemplateArgumentsFromCallArgument(
4505	*this, TemplateParamsSt.get(), 0, TemplArg, Init,
4506	Info, Deduced, OriginalCallArgs, /Decomposed/ true,
4507	/ArgIdx/ 0, /TDF/ 0))
4508	return DeductionFailed(TDK, {DeducedFromInitRange,
4509	Init->getSourceRange()});
4510
4511	if (DeducedFromInitRange.isInvalid() &&
4512	Deduced[0].getKind() != TemplateArgument::Null)
4513	DeducedFromInitRange = Init->getSourceRange();
4514	}
4515	} else {
4516	if (!getLangOpts().CPlusPlus && Init->refersToBitField()) {
4517	Diag(Loc, diag::err_auto_bitfield);
4518	return DAR_FailedAlreadyDiagnosed;
4519	}
4520
4521	if (auto TDK = DeduceTemplateArgumentsFromCallArgument(
4522	*this, TemplateParamsSt.get(), 0, FuncParam, Init, Info, Deduced,
4523	OriginalCallArgs, /Decomposed/ false, /ArgIdx/ 0, /TDF/ 0))
4524	return DeductionFailed(TDK, {});
4525	}
4526
4527	// Could be null if somehow 'auto' appears in a non-deduced context.
4528	if (Deduced[0].getKind() != TemplateArgument::Type)
4529	return DeductionFailed(TDK_Incomplete, {});
4530
4531	QualType DeducedType = Deduced[0].getAsType();
4532
4533	if (InitList) {
4534	DeducedType = BuildStdInitializerList(DeducedType, Loc);
4535	if (DeducedType.isNull())
4536	return DAR_FailedAlreadyDiagnosed;
4537	}
4538
4539	Result = SubstituteDeducedTypeTransform(*this, DeducedType).Apply(Type);
4540	if (Result.isNull())
4541	return DAR_FailedAlreadyDiagnosed;
4542
4543	// Check that the deduced argument type is compatible with the original
4544	// argument type per C++ [temp.deduct.call]p4.
4545	QualType DeducedA = InitList ? Deduced[0].getAsType() : Result;
4546	for (const OriginalCallArg &OriginalArg : OriginalCallArgs) {
4547	(0) . __assert_fail ("(bool)InitList == OriginalArg.DecomposedParam && \"decomposed non-init-list in auto deduction?\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 4548, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert((bool)InitList == OriginalArg.DecomposedParam &&
4548	(0) . __assert_fail ("(bool)InitList == OriginalArg.DecomposedParam && \"decomposed non-init-list in auto deduction?\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 4548, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "decomposed non-init-list in auto deduction?");
4549	if (auto TDK =
4550	CheckOriginalCallArgDeduction(*this, Info, OriginalArg, DeducedA)) {
4551	Result = QualType();
4552	return DeductionFailed(TDK, {});
4553	}
4554	}
4555
4556	return DAR_Succeeded;
4557	}
4558
4559	QualType Sema::SubstAutoType(QualType TypeWithAuto,
4560	QualType TypeToReplaceAuto) {
4561	if (TypeToReplaceAuto->isDependentType())
4562	TypeToReplaceAuto = QualType();
4563	return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto)
4564	.TransformType(TypeWithAuto);
4565	}
4566
4567	TypeSourceInfo Sema::SubstAutoTypeSourceInfo(TypeSourceInfo TypeWithAuto,
4568	QualType TypeToReplaceAuto) {
4569	if (TypeToReplaceAuto->isDependentType())
4570	TypeToReplaceAuto = QualType();
4571	return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto)
4572	.TransformType(TypeWithAuto);
4573	}
4574
4575	QualType Sema::ReplaceAutoType(QualType TypeWithAuto,
4576	QualType TypeToReplaceAuto) {
4577	return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto,
4578	/UseTypeSugar/ false)
4579	.TransformType(TypeWithAuto);
4580	}
4581
4582	void Sema::DiagnoseAutoDeductionFailure(VarDecl VDecl, Expr Init) {
4583	if (isa<InitListExpr>(Init))
4584	Diag(VDecl->getLocation(),
4585	VDecl->isInitCapture()
4586	? diag::err_init_capture_deduction_failure_from_init_list
4587	: diag::err_auto_var_deduction_failure_from_init_list)
4588	<< VDecl->getDeclName() << VDecl->getType() << Init->getSourceRange();
4589	else
4590	Diag(VDecl->getLocation(),
4591	VDecl->isInitCapture() ? diag::err_init_capture_deduction_failure
4592	: diag::err_auto_var_deduction_failure)
4593	<< VDecl->getDeclName() << VDecl->getType() << Init->getType()
4594	<< Init->getSourceRange();
4595	}
4596
4597	bool Sema::DeduceReturnType(FunctionDecl *FD, SourceLocation Loc,
4598	bool Diagnose) {
4599	getReturnType()->isUndeducedType()", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 4599, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(FD->getReturnType()->isUndeducedType());
4600
4601	// For a lambda's conversion operator, deduce any 'auto' or 'decltype(auto)'
4602	// within the return type from the call operator's type.
4603	if (isLambdaConversionOperator(FD)) {
4604	CXXRecordDecl *Lambda = cast<CXXMethodDecl>(FD)->getParent();
4605	FunctionDecl *CallOp = Lambda->getLambdaCallOperator();
4606
4607	// For a generic lambda, instantiate the call operator if needed.
4608	if (auto *Args = FD->getTemplateSpecializationArgs()) {
4609	CallOp = InstantiateFunctionDeclaration(
4610	CallOp->getDescribedFunctionTemplate(), Args, Loc);
4611	if (!CallOp \|\| CallOp->isInvalidDecl())
4612	return true;
4613
4614	// We might need to deduce the return type by instantiating the definition
4615	// of the operator() function.
4616	if (CallOp->getReturnType()->isUndeducedType())
4617	InstantiateFunctionDefinition(Loc, CallOp);
4618	}
4619
4620	if (CallOp->isInvalidDecl())
4621	return true;
4622	(0) . __assert_fail ("!CallOp->getReturnType()->isUndeducedType() && \"failed to deduce lambda return type\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 4623, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(!CallOp->getReturnType()->isUndeducedType() &&
4623	(0) . __assert_fail ("!CallOp->getReturnType()->isUndeducedType() && \"failed to deduce lambda return type\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 4623, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "failed to deduce lambda return type");
4624
4625	// Build the new return type from scratch.
4626	QualType RetType = getLambdaConversionFunctionResultType(
4627	CallOp->getType()->castAs<FunctionProtoType>());
4628	if (FD->getReturnType()->getAs<PointerType>())
4629	RetType = Context.getPointerType(RetType);
4630	else {
4631	getReturnType()->getAs()", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 4631, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(FD->getReturnType()->getAs<BlockPointerType>());
4632	RetType = Context.getBlockPointerType(RetType);
4633	}
4634	Context.adjustDeducedFunctionResultType(FD, RetType);
4635	return false;
4636	}
4637
4638	if (FD->getTemplateInstantiationPattern())
4639	InstantiateFunctionDefinition(Loc, FD);
4640
4641	bool StillUndeduced = FD->getReturnType()->isUndeducedType();
4642	if (StillUndeduced && Diagnose && !FD->isInvalidDecl()) {
4643	Diag(Loc, diag::err_auto_fn_used_before_defined) << FD;
4644	Diag(FD->getLocation(), diag::note_callee_decl) << FD;
4645	}
4646
4647	return StillUndeduced;
4648	}
4649
4650	/// If this is a non-static member function,
4651	static void
4652	AddImplicitObjectParameterType(ASTContext &Context,
4653	CXXMethodDecl *Method,
4654	SmallVectorImpl<QualType> &ArgTypes) {
4655	// C++11 [temp.func.order]p3:
4656	// [...] The new parameter is of type "reference to cv A," where cv are
4657	// the cv-qualifiers of the function template (if any) and A is
4658	// the class of which the function template is a member.
4659	//
4660	// The standard doesn't say explicitly, but we pick the appropriate kind of
4661	// reference type based on [over.match.funcs]p4.
4662	QualType ArgTy = Context.getTypeDeclType(Method->getParent());
4663	ArgTy = Context.getQualifiedType(ArgTy, Method->getMethodQualifiers());
4664	if (Method->getRefQualifier() == RQ_RValue)
4665	ArgTy = Context.getRValueReferenceType(ArgTy);
4666	else
4667	ArgTy = Context.getLValueReferenceType(ArgTy);
4668	ArgTypes.push_back(ArgTy);
4669	}
4670
4671	/// Determine whether the function template \p FT1 is at least as
4672	/// specialized as \p FT2.
4673	static bool isAtLeastAsSpecializedAs(Sema &S,
4674	SourceLocation Loc,
4675	FunctionTemplateDecl *FT1,
4676	FunctionTemplateDecl *FT2,
4677	TemplatePartialOrderingContext TPOC,
4678	unsigned NumCallArguments1) {
4679	FunctionDecl *FD1 = FT1->getTemplatedDecl();
4680	FunctionDecl *FD2 = FT2->getTemplatedDecl();
4681	const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>();
4682	const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>();
4683
4684	(0) . __assert_fail ("Proto1 && Proto2 && \"Function templates must have prototypes\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 4684, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(Proto1 && Proto2 && "Function templates must have prototypes");
4685	TemplateParameterList *TemplateParams = FT2->getTemplateParameters();
4686	SmallVector<DeducedTemplateArgument, 4> Deduced;
4687	Deduced.resize(TemplateParams->size());
4688
4689	// C++0x [temp.deduct.partial]p3:
4690	// The types used to determine the ordering depend on the context in which
4691	// the partial ordering is done:
4692	TemplateDeductionInfo Info(Loc);
4693	SmallVector<QualType, 4> Args2;
4694	switch (TPOC) {
4695	case TPOC_Call: {
4696	// - In the context of a function call, the function parameter types are
4697	// used.
4698	CXXMethodDecl *Method1 = dyn_cast<CXXMethodDecl>(FD1);
4699	CXXMethodDecl *Method2 = dyn_cast<CXXMethodDecl>(FD2);
4700
4701	// C++11 [temp.func.order]p3:
4702	// [...] If only one of the function templates is a non-static
4703	// member, that function template is considered to have a new
4704	// first parameter inserted in its function parameter list. The
4705	// new parameter is of type "reference to cv A," where cv are
4706	// the cv-qualifiers of the function template (if any) and A is
4707	// the class of which the function template is a member.
4708	//
4709	// Note that we interpret this to mean "if one of the function
4710	// templates is a non-static member and the other is a non-member";
4711	// otherwise, the ordering rules for static functions against non-static
4712	// functions don't make any sense.
4713	//
4714	// C++98/03 doesn't have this provision but we've extended DR532 to cover
4715	// it as wording was broken prior to it.
4716	SmallVector<QualType, 4> Args1;
4717
4718	unsigned NumComparedArguments = NumCallArguments1;
4719
4720	if (!Method2 && Method1 && !Method1->isStatic()) {
4721	// Compare 'this' from Method1 against first parameter from Method2.
4722	AddImplicitObjectParameterType(S.Context, Method1, Args1);
4723	++NumComparedArguments;
4724	} else if (!Method1 && Method2 && !Method2->isStatic()) {
4725	// Compare 'this' from Method2 against first parameter from Method1.
4726	AddImplicitObjectParameterType(S.Context, Method2, Args2);
4727	}
4728
4729	Args1.insert(Args1.end(), Proto1->param_type_begin(),
4730	Proto1->param_type_end());
4731	Args2.insert(Args2.end(), Proto2->param_type_begin(),
4732	Proto2->param_type_end());
4733
4734	// C++ [temp.func.order]p5:
4735	// The presence of unused ellipsis and default arguments has no effect on
4736	// the partial ordering of function templates.
4737	if (Args1.size() > NumComparedArguments)
4738	Args1.resize(NumComparedArguments);
4739	if (Args2.size() > NumComparedArguments)
4740	Args2.resize(NumComparedArguments);
4741	if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(),
4742	Args1.data(), Args1.size(), Info, Deduced,
4743	TDF_None, /PartialOrdering=/true))
4744	return false;
4745
4746	break;
4747	}
4748
4749	case TPOC_Conversion:
4750	// - In the context of a call to a conversion operator, the return types
4751	// of the conversion function templates are used.
4752	if (DeduceTemplateArgumentsByTypeMatch(
4753	S, TemplateParams, Proto2->getReturnType(), Proto1->getReturnType(),
4754	Info, Deduced, TDF_None,
4755	/PartialOrdering=/true))
4756	return false;
4757	break;
4758
4759	case TPOC_Other:
4760	// - In other contexts (14.6.6.2) the function template's function type
4761	// is used.
4762	if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
4763	FD2->getType(), FD1->getType(),
4764	Info, Deduced, TDF_None,
4765	/PartialOrdering=/true))
4766	return false;
4767	break;
4768	}
4769
4770	// C++0x [temp.deduct.partial]p11:
4771	// In most cases, all template parameters must have values in order for
4772	// deduction to succeed, but for partial ordering purposes a template
4773	// parameter may remain without a value provided it is not used in the
4774	// types being used for partial ordering. [ Note: a template parameter used
4775	// in a non-deduced context is considered used. -end note]
4776	unsigned ArgIdx = 0, NumArgs = Deduced.size();
4777	for (; ArgIdx != NumArgs; ++ArgIdx)
4778	if (Deduced[ArgIdx].isNull())
4779	break;
4780
4781	// FIXME: We fail to implement [temp.deduct.type]p1 along this path. We need
4782	// to substitute the deduced arguments back into the template and check that
4783	// we get the right type.
4784
4785	if (ArgIdx == NumArgs) {
4786	// All template arguments were deduced. FT1 is at least as specialized
4787	// as FT2.
4788	return true;
4789	}
4790
4791	// Figure out which template parameters were used.
4792	llvm::SmallBitVector UsedParameters(TemplateParams->size());
4793	switch (TPOC) {
4794	case TPOC_Call:
4795	for (unsigned I = 0, N = Args2.size(); I != N; ++I)
4796	::MarkUsedTemplateParameters(S.Context, Args2[I], false,
4797	TemplateParams->getDepth(),
4798	UsedParameters);
4799	break;
4800
4801	case TPOC_Conversion:
4802	::MarkUsedTemplateParameters(S.Context, Proto2->getReturnType(), false,
4803	TemplateParams->getDepth(), UsedParameters);
4804	break;
4805
4806	case TPOC_Other:
4807	::MarkUsedTemplateParameters(S.Context, FD2->getType(), false,
4808	TemplateParams->getDepth(),
4809	UsedParameters);
4810	break;
4811	}
4812
4813	for (; ArgIdx != NumArgs; ++ArgIdx)
4814	// If this argument had no value deduced but was used in one of the types
4815	// used for partial ordering, then deduction fails.
4816	if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx])
4817	return false;
4818
4819	return true;
4820	}
4821
4822	/// Determine whether this a function template whose parameter-type-list
4823	/// ends with a function parameter pack.
4824	static bool isVariadicFunctionTemplate(FunctionTemplateDecl *FunTmpl) {
4825	FunctionDecl *Function = FunTmpl->getTemplatedDecl();
4826	unsigned NumParams = Function->getNumParams();
4827	if (NumParams == 0)
4828	return false;
4829
4830	ParmVarDecl *Last = Function->getParamDecl(NumParams - 1);
4831	if (!Last->isParameterPack())
4832	return false;
4833
4834	// Make sure that no previous parameter is a parameter pack.
4835	while (--NumParams > 0) {
4836	if (Function->getParamDecl(NumParams - 1)->isParameterPack())
4837	return false;
4838	}
4839
4840	return true;
4841	}
4842
4843	/// Returns the more specialized function template according
4844	/// to the rules of function template partial ordering (C++ [temp.func.order]).
4845	///
4846	/// \param FT1 the first function template
4847	///
4848	/// \param FT2 the second function template
4849	///
4850	/// \param TPOC the context in which we are performing partial ordering of
4851	/// function templates.
4852	///
4853	/// \param NumCallArguments1 The number of arguments in the call to FT1, used
4854	/// only when \c TPOC is \c TPOC_Call.
4855	///
4856	/// \param NumCallArguments2 The number of arguments in the call to FT2, used
4857	/// only when \c TPOC is \c TPOC_Call.
4858	///
4859	/// \returns the more specialized function template. If neither
4860	/// template is more specialized, returns NULL.
4861	FunctionTemplateDecl *
4862	Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1,
4863	FunctionTemplateDecl *FT2,
4864	SourceLocation Loc,
4865	TemplatePartialOrderingContext TPOC,
4866	unsigned NumCallArguments1,
4867	unsigned NumCallArguments2) {
4868	bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC,
4869	NumCallArguments1);
4870	bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC,
4871	NumCallArguments2);
4872
4873	if (Better1 != Better2) // We have a clear winner
4874	return Better1 ? FT1 : FT2;
4875
4876	if (!Better1 && !Better2) // Neither is better than the other
4877	return nullptr;
4878
4879	// FIXME: This mimics what GCC implements, but doesn't match up with the
4880	// proposed resolution for core issue 692. This area needs to be sorted out,
4881	// but for now we attempt to maintain compatibility.
4882	bool Variadic1 = isVariadicFunctionTemplate(FT1);
4883	bool Variadic2 = isVariadicFunctionTemplate(FT2);
4884	if (Variadic1 != Variadic2)
4885	return Variadic1? FT2 : FT1;
4886
4887	return nullptr;
4888	}
4889
4890	/// Determine if the two templates are equivalent.
4891	static bool isSameTemplate(TemplateDecl T1, TemplateDecl T2) {
4892	if (T1 == T2)
4893	return true;
4894
4895	if (!T1 \|\| !T2)
4896	return false;
4897
4898	return T1->getCanonicalDecl() == T2->getCanonicalDecl();
4899	}
4900
4901	/// Retrieve the most specialized of the given function template
4902	/// specializations.
4903	///
4904	/// \param SpecBegin the start iterator of the function template
4905	/// specializations that we will be comparing.
4906	///
4907	/// \param SpecEnd the end iterator of the function template
4908	/// specializations, paired with \p SpecBegin.
4909	///
4910	/// \param Loc the location where the ambiguity or no-specializations
4911	/// diagnostic should occur.
4912	///
4913	/// \param NoneDiag partial diagnostic used to diagnose cases where there are
4914	/// no matching candidates.
4915	///
4916	/// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one
4917	/// occurs.
4918	///
4919	/// \param CandidateDiag partial diagnostic used for each function template
4920	/// specialization that is a candidate in the ambiguous ordering. One parameter
4921	/// in this diagnostic should be unbound, which will correspond to the string
4922	/// describing the template arguments for the function template specialization.
4923	///
4924	/// \returns the most specialized function template specialization, if
4925	/// found. Otherwise, returns SpecEnd.
4926	UnresolvedSetIterator Sema::getMostSpecialized(
4927	UnresolvedSetIterator SpecBegin, UnresolvedSetIterator SpecEnd,
4928	TemplateSpecCandidateSet &FailedCandidates,
4929	SourceLocation Loc, const PartialDiagnostic &NoneDiag,
4930	const PartialDiagnostic &AmbigDiag, const PartialDiagnostic &CandidateDiag,
4931	bool Complain, QualType TargetType) {
4932	if (SpecBegin == SpecEnd) {
4933	if (Complain) {
4934	Diag(Loc, NoneDiag);
4935	FailedCandidates.NoteCandidates(*this, Loc);
4936	}
4937	return SpecEnd;
4938	}
4939
4940	if (SpecBegin + 1 == SpecEnd)
4941	return SpecBegin;
4942
4943	// Find the function template that is better than all of the templates it
4944	// has been compared to.
4945	UnresolvedSetIterator Best = SpecBegin;
4946	FunctionTemplateDecl *BestTemplate
4947	= cast<FunctionDecl>(*Best)->getPrimaryTemplate();
4948	(0) . __assert_fail ("BestTemplate && \"Not a function template specialization?\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 4948, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(BestTemplate && "Not a function template specialization?");
4949	for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) {
4950	FunctionTemplateDecl *Challenger
4951	= cast<FunctionDecl>(*I)->getPrimaryTemplate();
4952	(0) . __assert_fail ("Challenger && \"Not a function template specialization?\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 4952, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(Challenger && "Not a function template specialization?");
4953	if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
4954	Loc, TPOC_Other, 0, 0),
4955	Challenger)) {
4956	Best = I;
4957	BestTemplate = Challenger;
4958	}
4959	}
4960
4961	// Make sure that the "best" function template is more specialized than all
4962	// of the others.
4963	bool Ambiguous = false;
4964	for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
4965	FunctionTemplateDecl *Challenger
4966	= cast<FunctionDecl>(*I)->getPrimaryTemplate();
4967	if (I != Best &&
4968	!isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
4969	Loc, TPOC_Other, 0, 0),
4970	BestTemplate)) {
4971	Ambiguous = true;
4972	break;
4973	}
4974	}
4975
4976	if (!Ambiguous) {
4977	// We found an answer. Return it.
4978	return Best;
4979	}
4980
4981	// Diagnose the ambiguity.
4982	if (Complain) {
4983	Diag(Loc, AmbigDiag);
4984
4985	// FIXME: Can we order the candidates in some sane way?
4986	for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
4987	PartialDiagnostic PD = CandidateDiag;
4988	const auto FD = cast<FunctionDecl>(I);
4989	PD << FD << getTemplateArgumentBindingsText(
4990	FD->getPrimaryTemplate()->getTemplateParameters(),
4991	*FD->getTemplateSpecializationArgs());
4992	if (!TargetType.isNull())
4993	HandleFunctionTypeMismatch(PD, FD->getType(), TargetType);
4994	Diag((*I)->getLocation(), PD);
4995	}
4996	}
4997
4998	return SpecEnd;
4999	}
5000
5001	/// Determine whether one partial specialization, P1, is at least as
5002	/// specialized than another, P2.
5003	///
5004	/// \tparam TemplateLikeDecl The kind of P2, which must be a
5005	/// TemplateDecl or {Class,Var}TemplatePartialSpecializationDecl.
5006	/// \param T1 The injected-class-name of P1 (faked for a variable template).
5007	/// \param T2 The injected-class-name of P2 (faked for a variable template).
5008	template<typename TemplateLikeDecl>
5009	static bool isAtLeastAsSpecializedAs(Sema &S, QualType T1, QualType T2,
5010	TemplateLikeDecl *P2,
5011	TemplateDeductionInfo &Info) {
5012	// C++ [temp.class.order]p1:
5013	// For two class template partial specializations, the first is at least as
5014	// specialized as the second if, given the following rewrite to two
5015	// function templates, the first function template is at least as
5016	// specialized as the second according to the ordering rules for function
5017	// templates (14.6.6.2):
5018	// - the first function template has the same template parameters as the
5019	// first partial specialization and has a single function parameter
5020	// whose type is a class template specialization with the template
5021	// arguments of the first partial specialization, and
5022	// - the second function template has the same template parameters as the
5023	// second partial specialization and has a single function parameter
5024	// whose type is a class template specialization with the template
5025	// arguments of the second partial specialization.
5026	//
5027	// Rather than synthesize function templates, we merely perform the
5028	// equivalent partial ordering by performing deduction directly on
5029	// the template arguments of the class template partial
5030	// specializations. This computation is slightly simpler than the
5031	// general problem of function template partial ordering, because
5032	// class template partial specializations are more constrained. We
5033	// know that every template parameter is deducible from the class
5034	// template partial specialization's template arguments, for
5035	// example.
5036	SmallVector<DeducedTemplateArgument, 4> Deduced;
5037
5038	// Determine whether P1 is at least as specialized as P2.
5039	Deduced.resize(P2->getTemplateParameters()->size());
5040	if (DeduceTemplateArgumentsByTypeMatch(S, P2->getTemplateParameters(),
5041	T2, T1, Info, Deduced, TDF_None,
5042	/PartialOrdering=/true))
5043	return false;
5044
5045	SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),
5046	Deduced.end());
5047	Sema::InstantiatingTemplate Inst(S, Info.getLocation(), P2, DeducedArgs,
5048	Info);
5049	auto *TST1 = T1->castAs<TemplateSpecializationType>();
5050	if (FinishTemplateArgumentDeduction(
5051	S, P2, /PartialOrdering=/true,
5052	TemplateArgumentList(TemplateArgumentList::OnStack,
5053	TST1->template_arguments()),
5054	Deduced, Info))
5055	return false;
5056
5057	return true;
5058	}
5059
5060	/// Returns the more specialized class template partial specialization
5061	/// according to the rules of partial ordering of class template partial
5062	/// specializations (C++ [temp.class.order]).
5063	///
5064	/// \param PS1 the first class template partial specialization
5065	///
5066	/// \param PS2 the second class template partial specialization
5067	///
5068	/// \returns the more specialized class template partial specialization. If
5069	/// neither partial specialization is more specialized, returns NULL.
5070	ClassTemplatePartialSpecializationDecl *
5071	Sema::getMoreSpecializedPartialSpecialization(
5072	ClassTemplatePartialSpecializationDecl *PS1,
5073	ClassTemplatePartialSpecializationDecl *PS2,
5074	SourceLocation Loc) {
5075	QualType PT1 = PS1->getInjectedSpecializationType();
5076	QualType PT2 = PS2->getInjectedSpecializationType();
5077
5078	TemplateDeductionInfo Info(Loc);
5079	bool Better1 = isAtLeastAsSpecializedAs(*this, PT1, PT2, PS2, Info);
5080	bool Better2 = isAtLeastAsSpecializedAs(*this, PT2, PT1, PS1, Info);
5081
5082	if (Better1 == Better2)
5083	return nullptr;
5084
5085	return Better1 ? PS1 : PS2;
5086	}
5087
5088	bool Sema::isMoreSpecializedThanPrimary(
5089	ClassTemplatePartialSpecializationDecl *Spec, TemplateDeductionInfo &Info) {
5090	ClassTemplateDecl *Primary = Spec->getSpecializedTemplate();
5091	QualType PrimaryT = Primary->getInjectedClassNameSpecialization();
5092	QualType PartialT = Spec->getInjectedSpecializationType();
5093	if (!isAtLeastAsSpecializedAs(*this, PartialT, PrimaryT, Primary, Info))
5094	return false;
5095	if (isAtLeastAsSpecializedAs(*this, PrimaryT, PartialT, Spec, Info)) {
5096	Info.clearSFINAEDiagnostic();
5097	return false;
5098	}
5099	return true;
5100	}
5101
5102	VarTemplatePartialSpecializationDecl *
5103	Sema::getMoreSpecializedPartialSpecialization(
5104	VarTemplatePartialSpecializationDecl *PS1,
5105	VarTemplatePartialSpecializationDecl *PS2, SourceLocation Loc) {
5106	// Pretend the variable template specializations are class template
5107	// specializations and form a fake injected class name type for comparison.
5108	(0) . __assert_fail ("PS1->getSpecializedTemplate() == PS2->getSpecializedTemplate() && \"the partial specializations being compared should specialize\" \" the same template.\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 5110, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(PS1->getSpecializedTemplate() == PS2->getSpecializedTemplate() &&
5109	(0) . __assert_fail ("PS1->getSpecializedTemplate() == PS2->getSpecializedTemplate() && \"the partial specializations being compared should specialize\" \" the same template.\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 5110, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "the partial specializations being compared should specialize"
5110	(0) . __assert_fail ("PS1->getSpecializedTemplate() == PS2->getSpecializedTemplate() && \"the partial specializations being compared should specialize\" \" the same template.\"", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 5110, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> " the same template.");
5111	TemplateName Name(PS1->getSpecializedTemplate());
5112	TemplateName CanonTemplate = Context.getCanonicalTemplateName(Name);
5113	QualType PT1 = Context.getTemplateSpecializationType(
5114	CanonTemplate, PS1->getTemplateArgs().asArray());
5115	QualType PT2 = Context.getTemplateSpecializationType(
5116	CanonTemplate, PS2->getTemplateArgs().asArray());
5117
5118	TemplateDeductionInfo Info(Loc);
5119	bool Better1 = isAtLeastAsSpecializedAs(*this, PT1, PT2, PS2, Info);
5120	bool Better2 = isAtLeastAsSpecializedAs(*this, PT2, PT1, PS1, Info);
5121
5122	if (Better1 == Better2)
5123	return nullptr;
5124
5125	return Better1 ? PS1 : PS2;
5126	}
5127
5128	bool Sema::isMoreSpecializedThanPrimary(
5129	VarTemplatePartialSpecializationDecl *Spec, TemplateDeductionInfo &Info) {
5130	TemplateDecl *Primary = Spec->getSpecializedTemplate();
5131	// FIXME: Cache the injected template arguments rather than recomputing
5132	// them for each partial specialization.
5133	SmallVector<TemplateArgument, 8> PrimaryArgs;
5134	Context.getInjectedTemplateArgs(Primary->getTemplateParameters(),
5135	PrimaryArgs);
5136
5137	TemplateName CanonTemplate =
5138	Context.getCanonicalTemplateName(TemplateName(Primary));
5139	QualType PrimaryT = Context.getTemplateSpecializationType(
5140	CanonTemplate, PrimaryArgs);
5141	QualType PartialT = Context.getTemplateSpecializationType(
5142	CanonTemplate, Spec->getTemplateArgs().asArray());
5143	if (!isAtLeastAsSpecializedAs(*this, PartialT, PrimaryT, Primary, Info))
5144	return false;
5145	if (isAtLeastAsSpecializedAs(*this, PrimaryT, PartialT, Spec, Info)) {
5146	Info.clearSFINAEDiagnostic();
5147	return false;
5148	}
5149	return true;
5150	}
5151
5152	bool Sema::isTemplateTemplateParameterAtLeastAsSpecializedAs(
5153	TemplateParameterList P, TemplateDecl AArg, SourceLocation Loc) {
5154	// C++1z [temp.arg.template]p4: (DR 150)
5155	// A template template-parameter P is at least as specialized as a
5156	// template template-argument A if, given the following rewrite to two
5157	// function templates...
5158
5159	// Rather than synthesize function templates, we merely perform the
5160	// equivalent partial ordering by performing deduction directly on
5161	// the template parameter lists of the template template parameters.
5162	//
5163	// Given an invented class template X with the template parameter list of
5164	// A (including default arguments):
5165	TemplateName X = Context.getCanonicalTemplateName(TemplateName(AArg));
5166	TemplateParameterList *A = AArg->getTemplateParameters();
5167
5168	// - Each function template has a single function parameter whose type is
5169	// a specialization of X with template arguments corresponding to the
5170	// template parameters from the respective function template
5171	SmallVector<TemplateArgument, 8> AArgs;
5172	Context.getInjectedTemplateArgs(A, AArgs);
5173
5174	// Check P's arguments against A's parameter list. This will fill in default
5175	// template arguments as needed. AArgs are already correct by construction.
5176	// We can't just use CheckTemplateIdType because that will expand alias
5177	// templates.
5178	SmallVector<TemplateArgument, 4> PArgs;
5179	{
5180	SFINAETrap Trap(*this);
5181
5182	Context.getInjectedTemplateArgs(P, PArgs);
5183	TemplateArgumentListInfo PArgList(P->getLAngleLoc(), P->getRAngleLoc());
5184	for (unsigned I = 0, N = P->size(); I != N; ++I) {
5185	// Unwrap packs that getInjectedTemplateArgs wrapped around pack
5186	// expansions, to form an "as written" argument list.
5187	TemplateArgument Arg = PArgs[I];
5188	if (Arg.getKind() == TemplateArgument::Pack) {
5189	isPackExpansion()", "/home/seafit/code_projects/clang_source/clang/lib/Sema/SemaTemplateDeduction.cpp", 5189, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(Arg.pack_size() == 1 && Arg.pack_begin()->isPackExpansion());
5190	Arg = *Arg.pack_begin();
5191	}
5192	PArgList.addArgument(getTrivialTemplateArgumentLoc(
5193	Arg, QualType(), P->getParam(I)->getLocation()));
5194	}
5195	PArgs.clear();
5196
5197	// C++1z [temp.arg.template]p3:
5198	// If the rewrite produces an invalid type, then P is not at least as
5199	// specialized as A.
5200	if (CheckTemplateArgumentList(AArg, Loc, PArgList, false, PArgs) \|\|
5201	Trap.hasErrorOccurred())
5202	return false;
5203	}
5204
5205	QualType AType = Context.getTemplateSpecializationType(X, AArgs);
5206	QualType PType = Context.getTemplateSpecializationType(X, PArgs);
5207
5208	// ... the function template corresponding to P is at least as specialized
5209	// as the function template corresponding to A according to the partial
5210	// ordering rules for function templates.
5211	TemplateDeductionInfo Info(Loc, A->getDepth());
5212	return isAtLeastAsSpecializedAs(*this, PType, AType, AArg, Info);
5213	}
5214
5215	/// Mark the template parameters that are used by the given
5216	/// expression.
5217	static void
5218	MarkUsedTemplateParameters(ASTContext &Ctx,
5219	const Expr *E,
5220	bool OnlyDeduced,
5221	unsigned Depth,
5222	llvm::SmallBitVector &Used) {
5223	// We can deduce from a pack expansion.
5224	if (const PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(E))
5225	E = Expansion->getPattern();
5226
5227	// Skip through any implicit casts we added while type-checking, and any
5228	// substitutions performed by template alias expansion.
5229	while (true) {
5230	if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E))
5231	E = ICE->getSubExpr();
5232	else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(E))
5233	E = CE->getSubExpr();
5234	else if (const SubstNonTypeTemplateParmExpr *Subst =
5235	dyn_cast<SubstNonTypeTemplateParmExpr>(E))
5236	E = Subst->getReplacement();
5237	else
5238	break;
5239	}
5240
5241	// FIXME: if !OnlyDeduced, we have to walk the whole subexpression to
5242	// find other occurrences of template parameters.
5243	const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E);
5244	if (!DRE)
5245	return;
5246
5247	const NonTypeTemplateParmDecl *NTTP
5248	= dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
5249	if (!NTTP)
5250	return;
5251
5252	if (NTTP->getDepth() == Depth)
5253	Used[NTTP->getIndex()] = true;
5254
5255	// In C++17 mode, additional arguments may be deduced from the type of a
5256	// non-type argument.
5257	if (Ctx.getLangOpts().CPlusPlus17)
5258	MarkUsedTemplateParameters(Ctx, NTTP->getType(), OnlyDeduced, Depth, Used);
5259	}
5260
5261	/// Mark the template parameters that are used by the given
5262	/// nested name specifier.
5263	static void
5264	MarkUsedTemplateParameters(ASTContext &Ctx,
5265	NestedNameSpecifier *NNS,
5266	bool OnlyDeduced,
5267	unsigned Depth,
5268	llvm::SmallBitVector &Used) {
5269	if (!NNS)
5270	return;
5271
5272	MarkUsedTemplateParameters(Ctx, NNS->getPrefix(), OnlyDeduced, Depth,
5273	Used);
5274	MarkUsedTemplateParameters(Ctx, QualType(NNS->getAsType(), 0),
5275	OnlyDeduced, Depth, Used);
5276	}
5277
5278	/// Mark the template parameters that are used by the given
5279	/// template name.
5280	static void
5281	MarkUsedTemplateParameters(ASTContext &Ctx,
5282	TemplateName Name,
5283	bool OnlyDeduced,
5284	unsigned Depth,
5285	llvm::SmallBitVector &Used) {
5286	if (TemplateDecl *Template = Name.getAsTemplateDecl()) {
5287	if (TemplateTemplateParmDecl *TTP
5288	= dyn_cast<TemplateTemplateParmDecl>(Template)) {
5289	if (TTP->getDepth() == Depth)
5290	Used[TTP->getIndex()] = true;
5291	}
5292	return;
5293	}
5294
5295	if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName())
5296	MarkUsedTemplateParameters(Ctx, QTN->getQualifier(), OnlyDeduced,
5297	Depth, Used);
5298	if (DependentTemplateName *DTN = Name.getAsDependentTemplateName())
5299	MarkUsedTemplateParameters(Ctx, DTN->getQualifier(), OnlyDeduced,
5300	Depth, Used);
5301	}
5302
5303	/// Mark the template parameters that are used by the given
5304	/// type.
5305	static void
5306	MarkUsedTemplateParameters(ASTContext &Ctx, QualType T,
5307	bool OnlyDeduced,
5308	unsigned Depth,
5309	llvm::SmallBitVector &Used) {
5310	if (T.isNull())
5311	return;
5312
5313	// Non-dependent types have nothing deducible
5314	if (!T->isDependentType())
5315	return;
5316
5317	T = Ctx.getCanonicalType(T);
5318	switch (T->getTypeClass()) {
5319	case Type::Pointer:
5320	MarkUsedTemplateParameters(Ctx,
5321	cast<PointerType>(T)->getPointeeType(),
5322	OnlyDeduced,
5323	Depth,
5324	Used);
5325	break;
5326
5327	case Type::BlockPointer:
5328	MarkUsedTemplateParameters(Ctx,
5329	cast<BlockPointerType>(T)->getPointeeType(),
5330	OnlyDeduced,
5331	Depth,
5332	Used);
5333	break;
5334
5335	case Type::LValueReference:
5336	case Type::RValueReference:
5337	MarkUsedTemplateParameters(Ctx,
5338	cast<ReferenceType>(T)->getPointeeType(),
5339	OnlyDeduced,
5340	Depth,
5341	Used);
5342	break;
5343
5344	case Type::MemberPointer: {
5345	const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr());
5346	MarkUsedTemplateParameters(Ctx, MemPtr->getPointeeType(), OnlyDeduced,
5347	Depth, Used);
5348	MarkUsedTemplateParameters(Ctx, QualType(MemPtr->getClass(), 0),
5349	OnlyDeduced, Depth, Used);
5350	break;
5351	}
5352
5353	case Type::DependentSizedArray:
5354	MarkUsedTemplateParameters(Ctx,
5355	cast<DependentSizedArrayType>(T)->getSizeExpr(),
5356	OnlyDeduced, Depth, Used);
5357	// Fall through to check the element type
5358	LLVM_FALLTHROUGH;
5359
5360	case Type::ConstantArray:
5361	case Type::IncompleteArray:
5362	MarkUsedTemplateParameters(Ctx,
5363	cast<ArrayType>(T)->getElementType(),
5364	OnlyDeduced, Depth, Used);
5365	break;
5366
5367	case Type::Vector:
5368	case Type::ExtVector:
5369	MarkUsedTemplateParameters(Ctx,
5370	cast<VectorType>(T)->getElementType(),
5371	OnlyDeduced, Depth, Used);
5372	break;
5373
5374	case Type::DependentVector: {
5375	const auto *VecType = cast<DependentVectorType>(T);
5376	MarkUsedTemplateParameters(Ctx, VecType->getElementType(), OnlyDeduced,
5377	Depth, Used);
5378	MarkUsedTemplateParameters(Ctx, VecType->getSizeExpr(), OnlyDeduced, Depth,
5379	Used);
5380	break;
5381	}
5382	case Type::DependentSizedExtVector: {
5383	const DependentSizedExtVectorType *VecType
5384	= cast<DependentSizedExtVectorType>(T);
5385	MarkUsedTemplateParameters(Ctx, VecType->getElementType(), OnlyDeduced,
5386	Depth, Used);
5387	MarkUsedTemplateParameters(Ctx, VecType->getSizeExpr(), OnlyDeduced,
5388	Depth, Used);
5389	break;
5390	}
5391
5392	case Type::DependentAddressSpace: {
5393	const DependentAddressSpaceType *DependentASType =
5394	cast<DependentAddressSpaceType>(T);
5395	MarkUsedTemplateParameters(Ctx, DependentASType->getPointeeType(),
5396	OnlyDeduced, Depth, Used);
5397	MarkUsedTemplateParameters(Ctx,
5398	DependentASType->getAddrSpaceExpr(),
5399	OnlyDeduced, Depth, Used);
5400	break;
5401	}
5402
5403	case Type::FunctionProto: {
5404	const FunctionProtoType *Proto = cast<FunctionProtoType>(T);
5405	MarkUsedTemplateParameters(Ctx, Proto->getReturnType(), OnlyDeduced, Depth,
5406	Used);
5407	for (unsigned I = 0, N = Proto->getNumParams(); I != N; ++I) {
5408	// C++17 [temp.deduct.type]p5:
5409	// The non-deduced contexts are: [...]
5410	// -- A function parameter pack that does not occur at the end of the
5411	// parameter-declaration-list.
5412	if (!OnlyDeduced \|\| I + 1 == N \|\|
5413	!Proto->getParamType(I)->getAs<PackExpansionType>()) {
5414	MarkUsedTemplateParameters(Ctx, Proto->getParamType(I), OnlyDeduced,
5415	Depth, Used);
5416	} else {
5417	// FIXME: C++17 [temp.deduct.call]p1:
5418	// When a function parameter pack appears in a non-deduced context,
5419	// the type of that pack is never deduced.
5420	//
5421	// We should also track a set of "never deduced" parameters, and
5422	// subtract that from the list of deduced parameters after marking.
5423	}
5424	}
5425	if (auto *E = Proto->getNoexceptExpr())
5426	MarkUsedTemplateParameters(Ctx, E, OnlyDeduced, Depth, Used);
5427	break;
5428	}
5429
5430	case Type::TemplateTypeParm: {
5431	const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T);
5432	if (TTP->getDepth() == Depth)
5433	Used[TTP->getIndex()] = true;
5434	break;
5435	}
5436
5437	case Type::SubstTemplateTypeParmPack: {
5438	const SubstTemplateTypeParmPackType *Subst
5439	= cast<SubstTemplateTypeParmPackType>(T);
5440	MarkUsedTemplateParameters(Ctx,
5441	QualType(Subst->getReplacedParameter(), 0),
5442	OnlyDeduced, Depth, Used);
5443	MarkUsedTemplateParameters(Ctx, Subst->getArgumentPack(),
5444	OnlyDeduced, Depth, Used);
5445	break;
5446	}
5447
5448	case Type::InjectedClassName:
5449	T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType();
5450	LLVM_FALLTHROUGH;
5451
5452	case Type::TemplateSpecialization: {
5453	const TemplateSpecializationType *Spec
5454	= cast<TemplateSpecializationType>(T);
5455	MarkUsedTemplateParameters(Ctx, Spec->getTemplateName(), OnlyDeduced,
5456	Depth, Used);
5457
5458	// C++0x [temp.deduct.type]p9:
5459	// If the template argument list of P contains a pack expansion that is
5460	// not the last template argument, the entire template argument list is a
5461	// non-deduced context.
5462	if (OnlyDeduced &&
5463	hasPackExpansionBeforeEnd(Spec->template_arguments()))
5464	break;
5465
5466	for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
5467	MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth,
5468	Used);
5469	break;
5470	}
5471
5472	case Type::Complex:
5473	if (!OnlyDeduced)
5474	MarkUsedTemplateParameters(Ctx,
5475	cast<ComplexType>(T)->getElementType(),
5476	OnlyDeduced, Depth, Used);
5477	break;
5478
5479	case Type::Atomic:
5480	if (!OnlyDeduced)
5481	MarkUsedTemplateParameters(Ctx,
5482	cast<AtomicType>(T)->getValueType(),
5483	OnlyDeduced, Depth, Used);
5484	break;
5485
5486	case Type::DependentName:
5487	if (!OnlyDeduced)
5488	MarkUsedTemplateParameters(Ctx,
5489	cast<DependentNameType>(T)->getQualifier(),
5490	OnlyDeduced, Depth, Used);
5491	break;
5492
5493	case Type::DependentTemplateSpecialization: {
5494	// C++14 [temp.deduct.type]p5:
5495	// The non-deduced contexts are:
5496	// -- The nested-name-specifier of a type that was specified using a
5497	// qualified-id
5498	//
5499	// C++14 [temp.deduct.type]p6:
5500	// When a type name is specified in a way that includes a non-deduced
5501	// context, all of the types that comprise that type name are also
5502	// non-deduced.
5503	if (OnlyDeduced)
5504	break;
5505
5506	const DependentTemplateSpecializationType *Spec
5507	= cast<DependentTemplateSpecializationType>(T);
5508
5509	MarkUsedTemplateParameters(Ctx, Spec->getQualifier(),
5510	OnlyDeduced, Depth, Used);
5511
5512	for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
5513	MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth,
5514	Used);
5515	break;
5516	}
5517
5518	case Type::TypeOf:
5519	if (!OnlyDeduced)
5520	MarkUsedTemplateParameters(Ctx,
5521	cast<TypeOfType>(T)->getUnderlyingType(),
5522	OnlyDeduced, Depth, Used);
5523	break;
5524
5525	case Type::TypeOfExpr:
5526	if (!OnlyDeduced)
5527	MarkUsedTemplateParameters(Ctx,
5528	cast<TypeOfExprType>(T)->getUnderlyingExpr(),
5529	OnlyDeduced, Depth, Used);
5530	break;
5531
5532	case Type::Decltype:
5533	if (!OnlyDeduced)
5534	MarkUsedTemplateParameters(Ctx,
5535	cast<DecltypeType>(T)->getUnderlyingExpr(),
5536	OnlyDeduced, Depth, Used);
5537	break;
5538
5539	case Type::UnaryTransform:
5540	if (!OnlyDeduced)
5541	MarkUsedTemplateParameters(Ctx,
5542	cast<UnaryTransformType>(T)->getUnderlyingType(),
5543	OnlyDeduced, Depth, Used);
5544	break;
5545
5546	case Type::PackExpansion:
5547	MarkUsedTemplateParameters(Ctx,
5548	cast<PackExpansionType>(T)->getPattern(),
5549	OnlyDeduced, Depth, Used);
5550	break;
5551
5552	case Type::Auto:
5553	case Type::DeducedTemplateSpecialization:
5554	MarkUsedTemplateParameters(Ctx,
5555	cast<DeducedType>(T)->getDeducedType(),
5556	OnlyDeduced, Depth, Used);
5557	break;
5558
5559	// None of these types have any template parameters in them.
5560	case Type::Builtin:
5561	case Type::VariableArray:
5562	case Type::FunctionNoProto:
5563	case Type::Record:
5564	case Type::Enum:
5565	case Type::ObjCInterface:
5566	case Type::ObjCObject:
5567	case Type::ObjCObjectPointer:
5568	case Type::UnresolvedUsing:
5569	case Type::Pipe:
5570	#define TYPE(Class, Base)
5571	#define ABSTRACT_TYPE(Class, Base)
5572	#define DEPENDENT_TYPE(Class, Base)
5573	#define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
5574	#include "clang/AST/TypeNodes.def"
5575	break;
5576	}
5577	}
5578
5579	/// Mark the template parameters that are used by this
5580	/// template argument.
5581	static void
5582	MarkUsedTemplateParameters(ASTContext &Ctx,
5583	const TemplateArgument &TemplateArg,
5584	bool OnlyDeduced,
5585	unsigned Depth,
5586	llvm::SmallBitVector &Used) {
5587	switch (TemplateArg.getKind()) {
5588	case TemplateArgument::Null:
5589	case TemplateArgument::Integral:
5590	case TemplateArgument::Declaration:
5591	break;
5592
5593	case TemplateArgument::NullPtr:
5594	MarkUsedTemplateParameters(Ctx, TemplateArg.getNullPtrType(), OnlyDeduced,
5595	Depth, Used);
5596	break;
5597
5598	case TemplateArgument::Type:
5599	MarkUsedTemplateParameters(Ctx, TemplateArg.getAsType(), OnlyDeduced,
5600	Depth, Used);
5601	break;
5602
5603	case TemplateArgument::Template:
5604	case TemplateArgument::TemplateExpansion:
5605	MarkUsedTemplateParameters(Ctx,
5606	TemplateArg.getAsTemplateOrTemplatePattern(),
5607	OnlyDeduced, Depth, Used);
5608	break;
5609
5610	case TemplateArgument::Expression:
5611	MarkUsedTemplateParameters(Ctx, TemplateArg.getAsExpr(), OnlyDeduced,
5612	Depth, Used);
5613	break;
5614
5615	case TemplateArgument::Pack:
5616	for (const auto &P : TemplateArg.pack_elements())
5617	MarkUsedTemplateParameters(Ctx, P, OnlyDeduced, Depth, Used);
5618	break;
5619	}
5620	}
5621
5622	/// Mark which template parameters can be deduced from a given
5623	/// template argument list.
5624	///
5625	/// \param TemplateArgs the template argument list from which template
5626	/// parameters will be deduced.
5627	///
5628	/// \param Used a bit vector whose elements will be set to \c true
5629	/// to indicate when the corresponding template parameter will be
5630	/// deduced.
5631	void
5632	Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs,
5633	bool OnlyDeduced, unsigned Depth,
5634	llvm::SmallBitVector &Used) {
5635	// C++0x [temp.deduct.type]p9:
5636	// If the template argument list of P contains a pack expansion that is not
5637	// the last template argument, the entire template argument list is a
5638	// non-deduced context.
5639	if (OnlyDeduced &&
5640	hasPackExpansionBeforeEnd(TemplateArgs.asArray()))
5641	return;
5642
5643	for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I)
5644	::MarkUsedTemplateParameters(Context, TemplateArgs[I], OnlyDeduced,
5645	Depth, Used);
5646	}
5647
5648	/// Marks all of the template parameters that will be deduced by a
5649	/// call to the given function template.
5650	void Sema::MarkDeducedTemplateParameters(
5651	ASTContext &Ctx, const FunctionTemplateDecl *FunctionTemplate,
5652	llvm::SmallBitVector &Deduced) {
5653	TemplateParameterList *TemplateParams
5654	= FunctionTemplate->getTemplateParameters();
5655	Deduced.clear();
5656	Deduced.resize(TemplateParams->size());
5657
5658	FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
5659	for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I)
5660	::MarkUsedTemplateParameters(Ctx, Function->getParamDecl(I)->getType(),
5661	true, TemplateParams->getDepth(), Deduced);
5662	}
5663
5664	bool hasDeducibleTemplateParameters(Sema &S,
5665	FunctionTemplateDecl *FunctionTemplate,
5666	QualType T) {
5667	if (!T->isDependentType())
5668	return false;
5669
5670	TemplateParameterList *TemplateParams
5671	= FunctionTemplate->getTemplateParameters();
5672	llvm::SmallBitVector Deduced(TemplateParams->size());
5673	::MarkUsedTemplateParameters(S.Context, T, true, TemplateParams->getDepth(),
5674	Deduced);
5675
5676	return Deduced.any();
5677	}
5678