1 //===------- SemaTemplateDeduction.cpp - Template Argument Deduction ------===/
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //===----------------------------------------------------------------------===/
9 // This file implements C++ template argument deduction.
11 //===----------------------------------------------------------------------===/
13 #include "clang/Sema/TemplateDeduction.h"
14 #include "TreeTransform.h"
15 #include "clang/AST/ASTContext.h"
16 #include "clang/AST/ASTLambda.h"
17 #include "clang/AST/DeclObjC.h"
18 #include "clang/AST/DeclTemplate.h"
19 #include "clang/AST/Expr.h"
20 #include "clang/AST/ExprCXX.h"
21 #include "clang/AST/StmtVisitor.h"
22 #include "clang/Sema/DeclSpec.h"
23 #include "clang/Sema/Sema.h"
24 #include "clang/Sema/Template.h"
25 #include "llvm/ADT/SmallBitVector.h"
30 /// \brief Various flags that control template argument deduction.
32 /// These flags can be bitwise-OR'd together.
33 enum TemplateDeductionFlags {
34 /// \brief No template argument deduction flags, which indicates the
35 /// strictest results for template argument deduction (as used for, e.g.,
36 /// matching class template partial specializations).
38 /// \brief Within template argument deduction from a function call, we are
39 /// matching with a parameter type for which the original parameter was
41 TDF_ParamWithReferenceType = 0x1,
42 /// \brief Within template argument deduction from a function call, we
43 /// are matching in a case where we ignore cv-qualifiers.
44 TDF_IgnoreQualifiers = 0x02,
45 /// \brief Within template argument deduction from a function call,
46 /// we are matching in a case where we can perform template argument
47 /// deduction from a template-id of a derived class of the argument type.
48 TDF_DerivedClass = 0x04,
49 /// \brief Allow non-dependent types to differ, e.g., when performing
50 /// template argument deduction from a function call where conversions
52 TDF_SkipNonDependent = 0x08,
53 /// \brief Whether we are performing template argument deduction for
54 /// parameters and arguments in a top-level template argument
55 TDF_TopLevelParameterTypeList = 0x10,
56 /// \brief Within template argument deduction from overload resolution per
57 /// C++ [over.over] allow matching function types that are compatible in
58 /// terms of noreturn and default calling convention adjustments.
59 TDF_InOverloadResolution = 0x20
63 using namespace clang;
65 /// \brief Compare two APSInts, extending and switching the sign as
66 /// necessary to compare their values regardless of underlying type.
67 static bool hasSameExtendedValue(llvm::APSInt X, llvm::APSInt Y) {
68 if (Y.getBitWidth() > X.getBitWidth())
69 X = X.extend(Y.getBitWidth());
70 else if (Y.getBitWidth() < X.getBitWidth())
71 Y = Y.extend(X.getBitWidth());
73 // If there is a signedness mismatch, correct it.
74 if (X.isSigned() != Y.isSigned()) {
75 // If the signed value is negative, then the values cannot be the same.
76 if ((Y.isSigned() && Y.isNegative()) || (X.isSigned() && X.isNegative()))
86 static Sema::TemplateDeductionResult
87 DeduceTemplateArguments(Sema &S,
88 TemplateParameterList *TemplateParams,
89 const TemplateArgument &Param,
91 TemplateDeductionInfo &Info,
92 SmallVectorImpl<DeducedTemplateArgument> &Deduced);
94 static Sema::TemplateDeductionResult
95 DeduceTemplateArgumentsByTypeMatch(Sema &S,
96 TemplateParameterList *TemplateParams,
99 TemplateDeductionInfo &Info,
100 SmallVectorImpl<DeducedTemplateArgument> &
103 bool PartialOrdering = false);
105 static Sema::TemplateDeductionResult
106 DeduceTemplateArguments(Sema &S,
107 TemplateParameterList *TemplateParams,
108 const TemplateArgument *Params, unsigned NumParams,
109 const TemplateArgument *Args, unsigned NumArgs,
110 TemplateDeductionInfo &Info,
111 SmallVectorImpl<DeducedTemplateArgument> &Deduced);
113 /// \brief If the given expression is of a form that permits the deduction
114 /// of a non-type template parameter, return the declaration of that
115 /// non-type template parameter.
116 static NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) {
117 // If we are within an alias template, the expression may have undergone
118 // any number of parameter substitutions already.
120 if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E))
121 E = IC->getSubExpr();
122 else if (SubstNonTypeTemplateParmExpr *Subst =
123 dyn_cast<SubstNonTypeTemplateParmExpr>(E))
124 E = Subst->getReplacement();
129 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
130 return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
135 /// \brief Determine whether two declaration pointers refer to the same
137 static bool isSameDeclaration(Decl *X, Decl *Y) {
138 if (NamedDecl *NX = dyn_cast<NamedDecl>(X))
139 X = NX->getUnderlyingDecl();
140 if (NamedDecl *NY = dyn_cast<NamedDecl>(Y))
141 Y = NY->getUnderlyingDecl();
143 return X->getCanonicalDecl() == Y->getCanonicalDecl();
146 /// \brief Verify that the given, deduced template arguments are compatible.
148 /// \returns The deduced template argument, or a NULL template argument if
149 /// the deduced template arguments were incompatible.
150 static DeducedTemplateArgument
151 checkDeducedTemplateArguments(ASTContext &Context,
152 const DeducedTemplateArgument &X,
153 const DeducedTemplateArgument &Y) {
154 // We have no deduction for one or both of the arguments; they're compatible.
160 switch (X.getKind()) {
161 case TemplateArgument::Null:
162 llvm_unreachable("Non-deduced template arguments handled above");
164 case TemplateArgument::Type:
165 // If two template type arguments have the same type, they're compatible.
166 if (Y.getKind() == TemplateArgument::Type &&
167 Context.hasSameType(X.getAsType(), Y.getAsType()))
170 return DeducedTemplateArgument();
172 case TemplateArgument::Integral:
173 // If we deduced a constant in one case and either a dependent expression or
174 // declaration in another case, keep the integral constant.
175 // If both are integral constants with the same value, keep that value.
176 if (Y.getKind() == TemplateArgument::Expression ||
177 Y.getKind() == TemplateArgument::Declaration ||
178 (Y.getKind() == TemplateArgument::Integral &&
179 hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral())))
180 return DeducedTemplateArgument(X,
181 X.wasDeducedFromArrayBound() &&
182 Y.wasDeducedFromArrayBound());
184 // All other combinations are incompatible.
185 return DeducedTemplateArgument();
187 case TemplateArgument::Template:
188 if (Y.getKind() == TemplateArgument::Template &&
189 Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate()))
192 // All other combinations are incompatible.
193 return DeducedTemplateArgument();
195 case TemplateArgument::TemplateExpansion:
196 if (Y.getKind() == TemplateArgument::TemplateExpansion &&
197 Context.hasSameTemplateName(X.getAsTemplateOrTemplatePattern(),
198 Y.getAsTemplateOrTemplatePattern()))
201 // All other combinations are incompatible.
202 return DeducedTemplateArgument();
204 case TemplateArgument::Expression:
205 // If we deduced a dependent expression in one case and either an integral
206 // constant or a declaration in another case, keep the integral constant
208 if (Y.getKind() == TemplateArgument::Integral ||
209 Y.getKind() == TemplateArgument::Declaration)
210 return DeducedTemplateArgument(Y, X.wasDeducedFromArrayBound() &&
211 Y.wasDeducedFromArrayBound());
213 if (Y.getKind() == TemplateArgument::Expression) {
214 // Compare the expressions for equality
215 llvm::FoldingSetNodeID ID1, ID2;
216 X.getAsExpr()->Profile(ID1, Context, true);
217 Y.getAsExpr()->Profile(ID2, Context, true);
222 // All other combinations are incompatible.
223 return DeducedTemplateArgument();
225 case TemplateArgument::Declaration:
226 // If we deduced a declaration and a dependent expression, keep the
228 if (Y.getKind() == TemplateArgument::Expression)
231 // If we deduced a declaration and an integral constant, keep the
232 // integral constant.
233 if (Y.getKind() == TemplateArgument::Integral)
236 // If we deduced two declarations, make sure they they refer to the
238 if (Y.getKind() == TemplateArgument::Declaration &&
239 isSameDeclaration(X.getAsDecl(), Y.getAsDecl()))
242 // All other combinations are incompatible.
243 return DeducedTemplateArgument();
245 case TemplateArgument::NullPtr:
246 // If we deduced a null pointer and a dependent expression, keep the
248 if (Y.getKind() == TemplateArgument::Expression)
251 // If we deduced a null pointer and an integral constant, keep the
252 // integral constant.
253 if (Y.getKind() == TemplateArgument::Integral)
256 // If we deduced two null pointers, make sure they have the same type.
257 if (Y.getKind() == TemplateArgument::NullPtr &&
258 Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType()))
261 // All other combinations are incompatible.
262 return DeducedTemplateArgument();
264 case TemplateArgument::Pack:
265 if (Y.getKind() != TemplateArgument::Pack ||
266 X.pack_size() != Y.pack_size())
267 return DeducedTemplateArgument();
269 for (TemplateArgument::pack_iterator XA = X.pack_begin(),
270 XAEnd = X.pack_end(),
272 XA != XAEnd; ++XA, ++YA) {
273 // FIXME: Do we need to merge the results together here?
274 if (checkDeducedTemplateArguments(Context,
275 DeducedTemplateArgument(*XA, X.wasDeducedFromArrayBound()),
276 DeducedTemplateArgument(*YA, Y.wasDeducedFromArrayBound()))
278 return DeducedTemplateArgument();
284 llvm_unreachable("Invalid TemplateArgument Kind!");
287 /// \brief Deduce the value of the given non-type template parameter
288 /// from the given constant.
289 static Sema::TemplateDeductionResult
290 DeduceNonTypeTemplateArgument(Sema &S,
291 NonTypeTemplateParmDecl *NTTP,
292 llvm::APSInt Value, QualType ValueType,
293 bool DeducedFromArrayBound,
294 TemplateDeductionInfo &Info,
295 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
296 assert(NTTP->getDepth() == 0 &&
297 "Cannot deduce non-type template argument with depth > 0");
299 DeducedTemplateArgument NewDeduced(S.Context, Value, ValueType,
300 DeducedFromArrayBound);
301 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
302 Deduced[NTTP->getIndex()],
304 if (Result.isNull()) {
306 Info.FirstArg = Deduced[NTTP->getIndex()];
307 Info.SecondArg = NewDeduced;
308 return Sema::TDK_Inconsistent;
311 Deduced[NTTP->getIndex()] = Result;
312 return Sema::TDK_Success;
315 /// \brief Deduce the value of the given non-type template parameter
316 /// from the given type- or value-dependent expression.
318 /// \returns true if deduction succeeded, false otherwise.
319 static Sema::TemplateDeductionResult
320 DeduceNonTypeTemplateArgument(Sema &S,
321 NonTypeTemplateParmDecl *NTTP,
323 TemplateDeductionInfo &Info,
324 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
325 assert(NTTP->getDepth() == 0 &&
326 "Cannot deduce non-type template argument with depth > 0");
327 assert((Value->isTypeDependent() || Value->isValueDependent()) &&
328 "Expression template argument must be type- or value-dependent.");
330 DeducedTemplateArgument NewDeduced(Value);
331 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
332 Deduced[NTTP->getIndex()],
335 if (Result.isNull()) {
337 Info.FirstArg = Deduced[NTTP->getIndex()];
338 Info.SecondArg = NewDeduced;
339 return Sema::TDK_Inconsistent;
342 Deduced[NTTP->getIndex()] = Result;
343 return Sema::TDK_Success;
346 /// \brief Deduce the value of the given non-type template parameter
347 /// from the given declaration.
349 /// \returns true if deduction succeeded, false otherwise.
350 static Sema::TemplateDeductionResult
351 DeduceNonTypeTemplateArgument(Sema &S,
352 NonTypeTemplateParmDecl *NTTP,
354 TemplateDeductionInfo &Info,
355 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
356 assert(NTTP->getDepth() == 0 &&
357 "Cannot deduce non-type template argument with depth > 0");
359 D = D ? cast<ValueDecl>(D->getCanonicalDecl()) : nullptr;
360 TemplateArgument New(D, NTTP->getType());
361 DeducedTemplateArgument NewDeduced(New);
362 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
363 Deduced[NTTP->getIndex()],
365 if (Result.isNull()) {
367 Info.FirstArg = Deduced[NTTP->getIndex()];
368 Info.SecondArg = NewDeduced;
369 return Sema::TDK_Inconsistent;
372 Deduced[NTTP->getIndex()] = Result;
373 return Sema::TDK_Success;
376 static Sema::TemplateDeductionResult
377 DeduceTemplateArguments(Sema &S,
378 TemplateParameterList *TemplateParams,
381 TemplateDeductionInfo &Info,
382 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
383 TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
385 // The parameter type is dependent and is not a template template parameter,
386 // so there is nothing that we can deduce.
387 return Sema::TDK_Success;
390 if (TemplateTemplateParmDecl *TempParam
391 = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) {
392 DeducedTemplateArgument NewDeduced(S.Context.getCanonicalTemplateName(Arg));
393 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
394 Deduced[TempParam->getIndex()],
396 if (Result.isNull()) {
397 Info.Param = TempParam;
398 Info.FirstArg = Deduced[TempParam->getIndex()];
399 Info.SecondArg = NewDeduced;
400 return Sema::TDK_Inconsistent;
403 Deduced[TempParam->getIndex()] = Result;
404 return Sema::TDK_Success;
407 // Verify that the two template names are equivalent.
408 if (S.Context.hasSameTemplateName(Param, Arg))
409 return Sema::TDK_Success;
411 // Mismatch of non-dependent template parameter to argument.
412 Info.FirstArg = TemplateArgument(Param);
413 Info.SecondArg = TemplateArgument(Arg);
414 return Sema::TDK_NonDeducedMismatch;
417 /// \brief Deduce the template arguments by comparing the template parameter
418 /// type (which is a template-id) with the template argument type.
420 /// \param S the Sema
422 /// \param TemplateParams the template parameters that we are deducing
424 /// \param Param the parameter type
426 /// \param Arg the argument type
428 /// \param Info information about the template argument deduction itself
430 /// \param Deduced the deduced template arguments
432 /// \returns the result of template argument deduction so far. Note that a
433 /// "success" result means that template argument deduction has not yet failed,
434 /// but it may still fail, later, for other reasons.
435 static Sema::TemplateDeductionResult
436 DeduceTemplateArguments(Sema &S,
437 TemplateParameterList *TemplateParams,
438 const TemplateSpecializationType *Param,
440 TemplateDeductionInfo &Info,
441 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
442 assert(Arg.isCanonical() && "Argument type must be canonical");
444 // Check whether the template argument is a dependent template-id.
445 if (const TemplateSpecializationType *SpecArg
446 = dyn_cast<TemplateSpecializationType>(Arg)) {
447 // Perform template argument deduction for the template name.
448 if (Sema::TemplateDeductionResult Result
449 = DeduceTemplateArguments(S, TemplateParams,
450 Param->getTemplateName(),
451 SpecArg->getTemplateName(),
456 // Perform template argument deduction on each template
457 // argument. Ignore any missing/extra arguments, since they could be
458 // filled in by default arguments.
459 return DeduceTemplateArguments(S, TemplateParams,
460 Param->getArgs(), Param->getNumArgs(),
461 SpecArg->getArgs(), SpecArg->getNumArgs(),
465 // If the argument type is a class template specialization, we
466 // perform template argument deduction using its template
468 const RecordType *RecordArg = dyn_cast<RecordType>(Arg);
470 Info.FirstArg = TemplateArgument(QualType(Param, 0));
471 Info.SecondArg = TemplateArgument(Arg);
472 return Sema::TDK_NonDeducedMismatch;
475 ClassTemplateSpecializationDecl *SpecArg
476 = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl());
478 Info.FirstArg = TemplateArgument(QualType(Param, 0));
479 Info.SecondArg = TemplateArgument(Arg);
480 return Sema::TDK_NonDeducedMismatch;
483 // Perform template argument deduction for the template name.
484 if (Sema::TemplateDeductionResult Result
485 = DeduceTemplateArguments(S,
487 Param->getTemplateName(),
488 TemplateName(SpecArg->getSpecializedTemplate()),
492 // Perform template argument deduction for the template arguments.
493 return DeduceTemplateArguments(S, TemplateParams,
494 Param->getArgs(), Param->getNumArgs(),
495 SpecArg->getTemplateArgs().data(),
496 SpecArg->getTemplateArgs().size(),
500 /// \brief Determines whether the given type is an opaque type that
501 /// might be more qualified when instantiated.
502 static bool IsPossiblyOpaquelyQualifiedType(QualType T) {
503 switch (T->getTypeClass()) {
504 case Type::TypeOfExpr:
506 case Type::DependentName:
508 case Type::UnresolvedUsing:
509 case Type::TemplateTypeParm:
512 case Type::ConstantArray:
513 case Type::IncompleteArray:
514 case Type::VariableArray:
515 case Type::DependentSizedArray:
516 return IsPossiblyOpaquelyQualifiedType(
517 cast<ArrayType>(T)->getElementType());
524 /// \brief Retrieve the depth and index of a template parameter.
525 static std::pair<unsigned, unsigned>
526 getDepthAndIndex(NamedDecl *ND) {
527 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND))
528 return std::make_pair(TTP->getDepth(), TTP->getIndex());
530 if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND))
531 return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
533 TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
534 return std::make_pair(TTP->getDepth(), TTP->getIndex());
537 /// \brief Retrieve the depth and index of an unexpanded parameter pack.
538 static std::pair<unsigned, unsigned>
539 getDepthAndIndex(UnexpandedParameterPack UPP) {
540 if (const TemplateTypeParmType *TTP
541 = UPP.first.dyn_cast<const TemplateTypeParmType *>())
542 return std::make_pair(TTP->getDepth(), TTP->getIndex());
544 return getDepthAndIndex(UPP.first.get<NamedDecl *>());
547 /// \brief Helper function to build a TemplateParameter when we don't
548 /// know its type statically.
549 static TemplateParameter makeTemplateParameter(Decl *D) {
550 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D))
551 return TemplateParameter(TTP);
552 if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D))
553 return TemplateParameter(NTTP);
555 return TemplateParameter(cast<TemplateTemplateParmDecl>(D));
558 /// A pack that we're currently deducing.
559 struct clang::DeducedPack {
560 DeducedPack(unsigned Index) : Index(Index), Outer(nullptr) {}
562 // The index of the pack.
565 // The old value of the pack before we started deducing it.
566 DeducedTemplateArgument Saved;
568 // A deferred value of this pack from an inner deduction, that couldn't be
569 // deduced because this deduction hadn't happened yet.
570 DeducedTemplateArgument DeferredDeduction;
572 // The new value of the pack.
573 SmallVector<DeducedTemplateArgument, 4> New;
575 // The outer deduction for this pack, if any.
580 /// A scope in which we're performing pack deduction.
581 class PackDeductionScope {
583 PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams,
584 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
585 TemplateDeductionInfo &Info, TemplateArgument Pattern)
586 : S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info) {
587 // Compute the set of template parameter indices that correspond to
588 // parameter packs expanded by the pack expansion.
590 llvm::SmallBitVector SawIndices(TemplateParams->size());
591 SmallVector<UnexpandedParameterPack, 2> Unexpanded;
592 S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
593 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
594 unsigned Depth, Index;
595 std::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
596 if (Depth == 0 && !SawIndices[Index]) {
597 SawIndices[Index] = true;
599 // Save the deduced template argument for the parameter pack expanded
600 // by this pack expansion, then clear out the deduction.
601 DeducedPack Pack(Index);
602 Pack.Saved = Deduced[Index];
603 Deduced[Index] = TemplateArgument();
605 Packs.push_back(Pack);
609 assert(!Packs.empty() && "Pack expansion without unexpanded packs?");
611 for (auto &Pack : Packs) {
612 if (Info.PendingDeducedPacks.size() > Pack.Index)
613 Pack.Outer = Info.PendingDeducedPacks[Pack.Index];
615 Info.PendingDeducedPacks.resize(Pack.Index + 1);
616 Info.PendingDeducedPacks[Pack.Index] = &Pack;
618 if (S.CurrentInstantiationScope) {
619 // If the template argument pack was explicitly specified, add that to
620 // the set of deduced arguments.
621 const TemplateArgument *ExplicitArgs;
622 unsigned NumExplicitArgs;
623 NamedDecl *PartiallySubstitutedPack =
624 S.CurrentInstantiationScope->getPartiallySubstitutedPack(
625 &ExplicitArgs, &NumExplicitArgs);
626 if (PartiallySubstitutedPack &&
627 getDepthAndIndex(PartiallySubstitutedPack).second == Pack.Index)
628 Pack.New.append(ExplicitArgs, ExplicitArgs + NumExplicitArgs);
633 ~PackDeductionScope() {
634 for (auto &Pack : Packs)
635 Info.PendingDeducedPacks[Pack.Index] = Pack.Outer;
638 /// Move to deducing the next element in each pack that is being deduced.
639 void nextPackElement() {
640 // Capture the deduced template arguments for each parameter pack expanded
641 // by this pack expansion, add them to the list of arguments we've deduced
642 // for that pack, then clear out the deduced argument.
643 for (auto &Pack : Packs) {
644 DeducedTemplateArgument &DeducedArg = Deduced[Pack.Index];
645 if (!DeducedArg.isNull()) {
646 Pack.New.push_back(DeducedArg);
647 DeducedArg = DeducedTemplateArgument();
652 /// \brief Finish template argument deduction for a set of argument packs,
653 /// producing the argument packs and checking for consistency with prior
655 Sema::TemplateDeductionResult finish(bool HasAnyArguments) {
656 // Build argument packs for each of the parameter packs expanded by this
658 for (auto &Pack : Packs) {
659 // Put back the old value for this pack.
660 Deduced[Pack.Index] = Pack.Saved;
662 // Build or find a new value for this pack.
663 DeducedTemplateArgument NewPack;
664 if (HasAnyArguments && Pack.New.empty()) {
665 if (Pack.DeferredDeduction.isNull()) {
666 // We were not able to deduce anything for this parameter pack
667 // (because it only appeared in non-deduced contexts), so just
668 // restore the saved argument pack.
672 NewPack = Pack.DeferredDeduction;
673 Pack.DeferredDeduction = TemplateArgument();
674 } else if (Pack.New.empty()) {
675 // If we deduced an empty argument pack, create it now.
676 NewPack = DeducedTemplateArgument(TemplateArgument::getEmptyPack());
678 TemplateArgument *ArgumentPack =
679 new (S.Context) TemplateArgument[Pack.New.size()];
680 std::copy(Pack.New.begin(), Pack.New.end(), ArgumentPack);
681 NewPack = DeducedTemplateArgument(
682 TemplateArgument(ArgumentPack, Pack.New.size()),
683 Pack.New[0].wasDeducedFromArrayBound());
686 // Pick where we're going to put the merged pack.
687 DeducedTemplateArgument *Loc;
689 if (Pack.Outer->DeferredDeduction.isNull()) {
690 // Defer checking this pack until we have a complete pack to compare
692 Pack.Outer->DeferredDeduction = NewPack;
695 Loc = &Pack.Outer->DeferredDeduction;
697 Loc = &Deduced[Pack.Index];
700 // Check the new pack matches any previous value.
701 DeducedTemplateArgument OldPack = *Loc;
702 DeducedTemplateArgument Result =
703 checkDeducedTemplateArguments(S.Context, OldPack, NewPack);
705 // If we deferred a deduction of this pack, check that one now too.
706 if (!Result.isNull() && !Pack.DeferredDeduction.isNull()) {
708 NewPack = Pack.DeferredDeduction;
709 Result = checkDeducedTemplateArguments(S.Context, OldPack, NewPack);
712 if (Result.isNull()) {
714 makeTemplateParameter(TemplateParams->getParam(Pack.Index));
715 Info.FirstArg = OldPack;
716 Info.SecondArg = NewPack;
717 return Sema::TDK_Inconsistent;
723 return Sema::TDK_Success;
728 TemplateParameterList *TemplateParams;
729 SmallVectorImpl<DeducedTemplateArgument> &Deduced;
730 TemplateDeductionInfo &Info;
732 SmallVector<DeducedPack, 2> Packs;
736 /// \brief Deduce the template arguments by comparing the list of parameter
737 /// types to the list of argument types, as in the parameter-type-lists of
738 /// function types (C++ [temp.deduct.type]p10).
740 /// \param S The semantic analysis object within which we are deducing
742 /// \param TemplateParams The template parameters that we are deducing
744 /// \param Params The list of parameter types
746 /// \param NumParams The number of types in \c Params
748 /// \param Args The list of argument types
750 /// \param NumArgs The number of types in \c Args
752 /// \param Info information about the template argument deduction itself
754 /// \param Deduced the deduced template arguments
756 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
757 /// how template argument deduction is performed.
759 /// \param PartialOrdering If true, we are performing template argument
760 /// deduction for during partial ordering for a call
761 /// (C++0x [temp.deduct.partial]).
763 /// \returns the result of template argument deduction so far. Note that a
764 /// "success" result means that template argument deduction has not yet failed,
765 /// but it may still fail, later, for other reasons.
766 static Sema::TemplateDeductionResult
767 DeduceTemplateArguments(Sema &S,
768 TemplateParameterList *TemplateParams,
769 const QualType *Params, unsigned NumParams,
770 const QualType *Args, unsigned NumArgs,
771 TemplateDeductionInfo &Info,
772 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
774 bool PartialOrdering = false) {
775 // Fast-path check to see if we have too many/too few arguments.
776 if (NumParams != NumArgs &&
777 !(NumParams && isa<PackExpansionType>(Params[NumParams - 1])) &&
778 !(NumArgs && isa<PackExpansionType>(Args[NumArgs - 1])))
779 return Sema::TDK_MiscellaneousDeductionFailure;
781 // C++0x [temp.deduct.type]p10:
782 // Similarly, if P has a form that contains (T), then each parameter type
783 // Pi of the respective parameter-type- list of P is compared with the
784 // corresponding parameter type Ai of the corresponding parameter-type-list
786 unsigned ArgIdx = 0, ParamIdx = 0;
787 for (; ParamIdx != NumParams; ++ParamIdx) {
788 // Check argument types.
789 const PackExpansionType *Expansion
790 = dyn_cast<PackExpansionType>(Params[ParamIdx]);
792 // Simple case: compare the parameter and argument types at this point.
794 // Make sure we have an argument.
795 if (ArgIdx >= NumArgs)
796 return Sema::TDK_MiscellaneousDeductionFailure;
798 if (isa<PackExpansionType>(Args[ArgIdx])) {
799 // C++0x [temp.deduct.type]p22:
800 // If the original function parameter associated with A is a function
801 // parameter pack and the function parameter associated with P is not
802 // a function parameter pack, then template argument deduction fails.
803 return Sema::TDK_MiscellaneousDeductionFailure;
806 if (Sema::TemplateDeductionResult Result
807 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
808 Params[ParamIdx], Args[ArgIdx],
817 // C++0x [temp.deduct.type]p5:
818 // The non-deduced contexts are:
819 // - A function parameter pack that does not occur at the end of the
820 // parameter-declaration-clause.
821 if (ParamIdx + 1 < NumParams)
822 return Sema::TDK_Success;
824 // C++0x [temp.deduct.type]p10:
825 // If the parameter-declaration corresponding to Pi is a function
826 // parameter pack, then the type of its declarator- id is compared with
827 // each remaining parameter type in the parameter-type-list of A. Each
828 // comparison deduces template arguments for subsequent positions in the
829 // template parameter packs expanded by the function parameter pack.
831 QualType Pattern = Expansion->getPattern();
832 PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
834 bool HasAnyArguments = false;
835 for (; ArgIdx < NumArgs; ++ArgIdx) {
836 HasAnyArguments = true;
838 // Deduce template arguments from the pattern.
839 if (Sema::TemplateDeductionResult Result
840 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, Pattern,
841 Args[ArgIdx], Info, Deduced,
842 TDF, PartialOrdering))
845 PackScope.nextPackElement();
848 // Build argument packs for each of the parameter packs expanded by this
850 if (auto Result = PackScope.finish(HasAnyArguments))
854 // Make sure we don't have any extra arguments.
855 if (ArgIdx < NumArgs)
856 return Sema::TDK_MiscellaneousDeductionFailure;
858 return Sema::TDK_Success;
861 /// \brief Determine whether the parameter has qualifiers that are either
862 /// inconsistent with or a superset of the argument's qualifiers.
863 static bool hasInconsistentOrSupersetQualifiersOf(QualType ParamType,
865 Qualifiers ParamQs = ParamType.getQualifiers();
866 Qualifiers ArgQs = ArgType.getQualifiers();
868 if (ParamQs == ArgQs)
871 // Mismatched (but not missing) Objective-C GC attributes.
872 if (ParamQs.getObjCGCAttr() != ArgQs.getObjCGCAttr() &&
873 ParamQs.hasObjCGCAttr())
876 // Mismatched (but not missing) address spaces.
877 if (ParamQs.getAddressSpace() != ArgQs.getAddressSpace() &&
878 ParamQs.hasAddressSpace())
881 // Mismatched (but not missing) Objective-C lifetime qualifiers.
882 if (ParamQs.getObjCLifetime() != ArgQs.getObjCLifetime() &&
883 ParamQs.hasObjCLifetime())
886 // CVR qualifier superset.
887 return (ParamQs.getCVRQualifiers() != ArgQs.getCVRQualifiers()) &&
888 ((ParamQs.getCVRQualifiers() | ArgQs.getCVRQualifiers())
889 == ParamQs.getCVRQualifiers());
892 /// \brief Compare types for equality with respect to possibly compatible
893 /// function types (noreturn adjustment, implicit calling conventions). If any
894 /// of parameter and argument is not a function, just perform type comparison.
896 /// \param Param the template parameter type.
898 /// \param Arg the argument type.
899 bool Sema::isSameOrCompatibleFunctionType(CanQualType Param,
901 const FunctionType *ParamFunction = Param->getAs<FunctionType>(),
902 *ArgFunction = Arg->getAs<FunctionType>();
904 // Just compare if not functions.
905 if (!ParamFunction || !ArgFunction)
908 // Noreturn adjustment.
909 QualType AdjustedParam;
910 if (IsNoReturnConversion(Param, Arg, AdjustedParam))
911 return Arg == Context.getCanonicalType(AdjustedParam);
913 // FIXME: Compatible calling conventions.
918 /// \brief Deduce the template arguments by comparing the parameter type and
919 /// the argument type (C++ [temp.deduct.type]).
921 /// \param S the semantic analysis object within which we are deducing
923 /// \param TemplateParams the template parameters that we are deducing
925 /// \param ParamIn the parameter type
927 /// \param ArgIn the argument type
929 /// \param Info information about the template argument deduction itself
931 /// \param Deduced the deduced template arguments
933 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
934 /// how template argument deduction is performed.
936 /// \param PartialOrdering Whether we're performing template argument deduction
937 /// in the context of partial ordering (C++0x [temp.deduct.partial]).
939 /// \returns the result of template argument deduction so far. Note that a
940 /// "success" result means that template argument deduction has not yet failed,
941 /// but it may still fail, later, for other reasons.
942 static Sema::TemplateDeductionResult
943 DeduceTemplateArgumentsByTypeMatch(Sema &S,
944 TemplateParameterList *TemplateParams,
945 QualType ParamIn, QualType ArgIn,
946 TemplateDeductionInfo &Info,
947 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
949 bool PartialOrdering) {
950 // We only want to look at the canonical types, since typedefs and
951 // sugar are not part of template argument deduction.
952 QualType Param = S.Context.getCanonicalType(ParamIn);
953 QualType Arg = S.Context.getCanonicalType(ArgIn);
955 // If the argument type is a pack expansion, look at its pattern.
956 // This isn't explicitly called out
957 if (const PackExpansionType *ArgExpansion
958 = dyn_cast<PackExpansionType>(Arg))
959 Arg = ArgExpansion->getPattern();
961 if (PartialOrdering) {
962 // C++11 [temp.deduct.partial]p5:
963 // Before the partial ordering is done, certain transformations are
964 // performed on the types used for partial ordering:
965 // - If P is a reference type, P is replaced by the type referred to.
966 const ReferenceType *ParamRef = Param->getAs<ReferenceType>();
968 Param = ParamRef->getPointeeType();
970 // - If A is a reference type, A is replaced by the type referred to.
971 const ReferenceType *ArgRef = Arg->getAs<ReferenceType>();
973 Arg = ArgRef->getPointeeType();
975 if (ParamRef && ArgRef && S.Context.hasSameUnqualifiedType(Param, Arg)) {
976 // C++11 [temp.deduct.partial]p9:
977 // If, for a given type, deduction succeeds in both directions (i.e.,
978 // the types are identical after the transformations above) and both
979 // P and A were reference types [...]:
980 // - if [one type] was an lvalue reference and [the other type] was
981 // not, [the other type] is not considered to be at least as
982 // specialized as [the first type]
983 // - if [one type] is more cv-qualified than [the other type],
984 // [the other type] is not considered to be at least as specialized
985 // as [the first type]
986 // Objective-C ARC adds:
987 // - [one type] has non-trivial lifetime, [the other type] has
988 // __unsafe_unretained lifetime, and the types are otherwise
991 // A is "considered to be at least as specialized" as P iff deduction
992 // succeeds, so we model this as a deduction failure. Note that
993 // [the first type] is P and [the other type] is A here; the standard
994 // gets this backwards.
995 Qualifiers ParamQuals = Param.getQualifiers();
996 Qualifiers ArgQuals = Arg.getQualifiers();
997 if ((ParamRef->isLValueReferenceType() &&
998 !ArgRef->isLValueReferenceType()) ||
999 ParamQuals.isStrictSupersetOf(ArgQuals) ||
1000 (ParamQuals.hasNonTrivialObjCLifetime() &&
1001 ArgQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone &&
1002 ParamQuals.withoutObjCLifetime() ==
1003 ArgQuals.withoutObjCLifetime())) {
1004 Info.FirstArg = TemplateArgument(ParamIn);
1005 Info.SecondArg = TemplateArgument(ArgIn);
1006 return Sema::TDK_NonDeducedMismatch;
1010 // C++11 [temp.deduct.partial]p7:
1011 // Remove any top-level cv-qualifiers:
1012 // - If P is a cv-qualified type, P is replaced by the cv-unqualified
1014 Param = Param.getUnqualifiedType();
1015 // - If A is a cv-qualified type, A is replaced by the cv-unqualified
1017 Arg = Arg.getUnqualifiedType();
1019 // C++0x [temp.deduct.call]p4 bullet 1:
1020 // - If the original P is a reference type, the deduced A (i.e., the type
1021 // referred to by the reference) can be more cv-qualified than the
1023 if (TDF & TDF_ParamWithReferenceType) {
1025 QualType UnqualParam = S.Context.getUnqualifiedArrayType(Param, Quals);
1026 Quals.setCVRQualifiers(Quals.getCVRQualifiers() &
1027 Arg.getCVRQualifiers());
1028 Param = S.Context.getQualifiedType(UnqualParam, Quals);
1031 if ((TDF & TDF_TopLevelParameterTypeList) && !Param->isFunctionType()) {
1032 // C++0x [temp.deduct.type]p10:
1033 // If P and A are function types that originated from deduction when
1034 // taking the address of a function template (14.8.2.2) or when deducing
1035 // template arguments from a function declaration (14.8.2.6) and Pi and
1036 // Ai are parameters of the top-level parameter-type-list of P and A,
1037 // respectively, Pi is adjusted if it is an rvalue reference to a
1038 // cv-unqualified template parameter and Ai is an lvalue reference, in
1039 // which case the type of Pi is changed to be the template parameter
1040 // type (i.e., T&& is changed to simply T). [ Note: As a result, when
1041 // Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be
1042 // deduced as X&. - end note ]
1043 TDF &= ~TDF_TopLevelParameterTypeList;
1045 if (const RValueReferenceType *ParamRef
1046 = Param->getAs<RValueReferenceType>()) {
1047 if (isa<TemplateTypeParmType>(ParamRef->getPointeeType()) &&
1048 !ParamRef->getPointeeType().getQualifiers())
1049 if (Arg->isLValueReferenceType())
1050 Param = ParamRef->getPointeeType();
1055 // C++ [temp.deduct.type]p9:
1056 // A template type argument T, a template template argument TT or a
1057 // template non-type argument i can be deduced if P and A have one of
1058 // the following forms:
1062 if (const TemplateTypeParmType *TemplateTypeParm
1063 = Param->getAs<TemplateTypeParmType>()) {
1064 // Just skip any attempts to deduce from a placeholder type.
1065 if (Arg->isPlaceholderType())
1066 return Sema::TDK_Success;
1068 unsigned Index = TemplateTypeParm->getIndex();
1069 bool RecanonicalizeArg = false;
1071 // If the argument type is an array type, move the qualifiers up to the
1072 // top level, so they can be matched with the qualifiers on the parameter.
1073 if (isa<ArrayType>(Arg)) {
1075 Arg = S.Context.getUnqualifiedArrayType(Arg, Quals);
1077 Arg = S.Context.getQualifiedType(Arg, Quals);
1078 RecanonicalizeArg = true;
1082 // The argument type can not be less qualified than the parameter
1084 if (!(TDF & TDF_IgnoreQualifiers) &&
1085 hasInconsistentOrSupersetQualifiersOf(Param, Arg)) {
1086 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1087 Info.FirstArg = TemplateArgument(Param);
1088 Info.SecondArg = TemplateArgument(Arg);
1089 return Sema::TDK_Underqualified;
1092 assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0");
1093 assert(Arg != S.Context.OverloadTy && "Unresolved overloaded function");
1094 QualType DeducedType = Arg;
1096 // Remove any qualifiers on the parameter from the deduced type.
1097 // We checked the qualifiers for consistency above.
1098 Qualifiers DeducedQs = DeducedType.getQualifiers();
1099 Qualifiers ParamQs = Param.getQualifiers();
1100 DeducedQs.removeCVRQualifiers(ParamQs.getCVRQualifiers());
1101 if (ParamQs.hasObjCGCAttr())
1102 DeducedQs.removeObjCGCAttr();
1103 if (ParamQs.hasAddressSpace())
1104 DeducedQs.removeAddressSpace();
1105 if (ParamQs.hasObjCLifetime())
1106 DeducedQs.removeObjCLifetime();
1109 // If template deduction would produce a lifetime qualifier on a type
1110 // that is not a lifetime type, template argument deduction fails.
1111 if (ParamQs.hasObjCLifetime() && !DeducedType->isObjCLifetimeType() &&
1112 !DeducedType->isDependentType()) {
1113 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1114 Info.FirstArg = TemplateArgument(Param);
1115 Info.SecondArg = TemplateArgument(Arg);
1116 return Sema::TDK_Underqualified;
1120 // If template deduction would produce an argument type with lifetime type
1121 // but no lifetime qualifier, the __strong lifetime qualifier is inferred.
1122 if (S.getLangOpts().ObjCAutoRefCount &&
1123 DeducedType->isObjCLifetimeType() &&
1124 !DeducedQs.hasObjCLifetime())
1125 DeducedQs.setObjCLifetime(Qualifiers::OCL_Strong);
1127 DeducedType = S.Context.getQualifiedType(DeducedType.getUnqualifiedType(),
1130 if (RecanonicalizeArg)
1131 DeducedType = S.Context.getCanonicalType(DeducedType);
1133 DeducedTemplateArgument NewDeduced(DeducedType);
1134 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
1137 if (Result.isNull()) {
1138 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1139 Info.FirstArg = Deduced[Index];
1140 Info.SecondArg = NewDeduced;
1141 return Sema::TDK_Inconsistent;
1144 Deduced[Index] = Result;
1145 return Sema::TDK_Success;
1148 // Set up the template argument deduction information for a failure.
1149 Info.FirstArg = TemplateArgument(ParamIn);
1150 Info.SecondArg = TemplateArgument(ArgIn);
1152 // If the parameter is an already-substituted template parameter
1153 // pack, do nothing: we don't know which of its arguments to look
1154 // at, so we have to wait until all of the parameter packs in this
1155 // expansion have arguments.
1156 if (isa<SubstTemplateTypeParmPackType>(Param))
1157 return Sema::TDK_Success;
1159 // Check the cv-qualifiers on the parameter and argument types.
1160 CanQualType CanParam = S.Context.getCanonicalType(Param);
1161 CanQualType CanArg = S.Context.getCanonicalType(Arg);
1162 if (!(TDF & TDF_IgnoreQualifiers)) {
1163 if (TDF & TDF_ParamWithReferenceType) {
1164 if (hasInconsistentOrSupersetQualifiersOf(Param, Arg))
1165 return Sema::TDK_NonDeducedMismatch;
1166 } else if (!IsPossiblyOpaquelyQualifiedType(Param)) {
1167 if (Param.getCVRQualifiers() != Arg.getCVRQualifiers())
1168 return Sema::TDK_NonDeducedMismatch;
1171 // If the parameter type is not dependent, there is nothing to deduce.
1172 if (!Param->isDependentType()) {
1173 if (!(TDF & TDF_SkipNonDependent)) {
1174 bool NonDeduced = (TDF & TDF_InOverloadResolution)?
1175 !S.isSameOrCompatibleFunctionType(CanParam, CanArg) :
1178 return Sema::TDK_NonDeducedMismatch;
1181 return Sema::TDK_Success;
1183 } else if (!Param->isDependentType()) {
1184 CanQualType ParamUnqualType = CanParam.getUnqualifiedType(),
1185 ArgUnqualType = CanArg.getUnqualifiedType();
1186 bool Success = (TDF & TDF_InOverloadResolution)?
1187 S.isSameOrCompatibleFunctionType(ParamUnqualType,
1189 ParamUnqualType == ArgUnqualType;
1191 return Sema::TDK_Success;
1194 switch (Param->getTypeClass()) {
1195 // Non-canonical types cannot appear here.
1196 #define NON_CANONICAL_TYPE(Class, Base) \
1197 case Type::Class: llvm_unreachable("deducing non-canonical type: " #Class);
1198 #define TYPE(Class, Base)
1199 #include "clang/AST/TypeNodes.def"
1201 case Type::TemplateTypeParm:
1202 case Type::SubstTemplateTypeParmPack:
1203 llvm_unreachable("Type nodes handled above");
1205 // These types cannot be dependent, so simply check whether the types are
1208 case Type::VariableArray:
1210 case Type::FunctionNoProto:
1213 case Type::ObjCObject:
1214 case Type::ObjCInterface:
1215 case Type::ObjCObjectPointer: {
1216 if (TDF & TDF_SkipNonDependent)
1217 return Sema::TDK_Success;
1219 if (TDF & TDF_IgnoreQualifiers) {
1220 Param = Param.getUnqualifiedType();
1221 Arg = Arg.getUnqualifiedType();
1224 return Param == Arg? Sema::TDK_Success : Sema::TDK_NonDeducedMismatch;
1227 // _Complex T [placeholder extension]
1229 if (const ComplexType *ComplexArg = Arg->getAs<ComplexType>())
1230 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1231 cast<ComplexType>(Param)->getElementType(),
1232 ComplexArg->getElementType(),
1233 Info, Deduced, TDF);
1235 return Sema::TDK_NonDeducedMismatch;
1237 // _Atomic T [extension]
1239 if (const AtomicType *AtomicArg = Arg->getAs<AtomicType>())
1240 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1241 cast<AtomicType>(Param)->getValueType(),
1242 AtomicArg->getValueType(),
1243 Info, Deduced, TDF);
1245 return Sema::TDK_NonDeducedMismatch;
1248 case Type::Pointer: {
1249 QualType PointeeType;
1250 if (const PointerType *PointerArg = Arg->getAs<PointerType>()) {
1251 PointeeType = PointerArg->getPointeeType();
1252 } else if (const ObjCObjectPointerType *PointerArg
1253 = Arg->getAs<ObjCObjectPointerType>()) {
1254 PointeeType = PointerArg->getPointeeType();
1256 return Sema::TDK_NonDeducedMismatch;
1259 unsigned SubTDF = TDF & (TDF_IgnoreQualifiers | TDF_DerivedClass);
1260 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1261 cast<PointerType>(Param)->getPointeeType(),
1263 Info, Deduced, SubTDF);
1267 case Type::LValueReference: {
1268 const LValueReferenceType *ReferenceArg =
1269 Arg->getAs<LValueReferenceType>();
1271 return Sema::TDK_NonDeducedMismatch;
1273 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1274 cast<LValueReferenceType>(Param)->getPointeeType(),
1275 ReferenceArg->getPointeeType(), Info, Deduced, 0);
1279 case Type::RValueReference: {
1280 const RValueReferenceType *ReferenceArg =
1281 Arg->getAs<RValueReferenceType>();
1283 return Sema::TDK_NonDeducedMismatch;
1285 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1286 cast<RValueReferenceType>(Param)->getPointeeType(),
1287 ReferenceArg->getPointeeType(),
1291 // T [] (implied, but not stated explicitly)
1292 case Type::IncompleteArray: {
1293 const IncompleteArrayType *IncompleteArrayArg =
1294 S.Context.getAsIncompleteArrayType(Arg);
1295 if (!IncompleteArrayArg)
1296 return Sema::TDK_NonDeducedMismatch;
1298 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1299 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1300 S.Context.getAsIncompleteArrayType(Param)->getElementType(),
1301 IncompleteArrayArg->getElementType(),
1302 Info, Deduced, SubTDF);
1305 // T [integer-constant]
1306 case Type::ConstantArray: {
1307 const ConstantArrayType *ConstantArrayArg =
1308 S.Context.getAsConstantArrayType(Arg);
1309 if (!ConstantArrayArg)
1310 return Sema::TDK_NonDeducedMismatch;
1312 const ConstantArrayType *ConstantArrayParm =
1313 S.Context.getAsConstantArrayType(Param);
1314 if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize())
1315 return Sema::TDK_NonDeducedMismatch;
1317 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1318 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1319 ConstantArrayParm->getElementType(),
1320 ConstantArrayArg->getElementType(),
1321 Info, Deduced, SubTDF);
1325 case Type::DependentSizedArray: {
1326 const ArrayType *ArrayArg = S.Context.getAsArrayType(Arg);
1328 return Sema::TDK_NonDeducedMismatch;
1330 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1332 // Check the element type of the arrays
1333 const DependentSizedArrayType *DependentArrayParm
1334 = S.Context.getAsDependentSizedArrayType(Param);
1335 if (Sema::TemplateDeductionResult Result
1336 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1337 DependentArrayParm->getElementType(),
1338 ArrayArg->getElementType(),
1339 Info, Deduced, SubTDF))
1342 // Determine the array bound is something we can deduce.
1343 NonTypeTemplateParmDecl *NTTP
1344 = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr());
1346 return Sema::TDK_Success;
1348 // We can perform template argument deduction for the given non-type
1349 // template parameter.
1350 assert(NTTP->getDepth() == 0 &&
1351 "Cannot deduce non-type template argument at depth > 0");
1352 if (const ConstantArrayType *ConstantArrayArg
1353 = dyn_cast<ConstantArrayType>(ArrayArg)) {
1354 llvm::APSInt Size(ConstantArrayArg->getSize());
1355 return DeduceNonTypeTemplateArgument(S, NTTP, Size,
1356 S.Context.getSizeType(),
1357 /*ArrayBound=*/true,
1360 if (const DependentSizedArrayType *DependentArrayArg
1361 = dyn_cast<DependentSizedArrayType>(ArrayArg))
1362 if (DependentArrayArg->getSizeExpr())
1363 return DeduceNonTypeTemplateArgument(S, NTTP,
1364 DependentArrayArg->getSizeExpr(),
1367 // Incomplete type does not match a dependently-sized array type
1368 return Sema::TDK_NonDeducedMismatch;
1374 case Type::FunctionProto: {
1375 unsigned SubTDF = TDF & TDF_TopLevelParameterTypeList;
1376 const FunctionProtoType *FunctionProtoArg =
1377 dyn_cast<FunctionProtoType>(Arg);
1378 if (!FunctionProtoArg)
1379 return Sema::TDK_NonDeducedMismatch;
1381 const FunctionProtoType *FunctionProtoParam =
1382 cast<FunctionProtoType>(Param);
1384 if (FunctionProtoParam->getTypeQuals()
1385 != FunctionProtoArg->getTypeQuals() ||
1386 FunctionProtoParam->getRefQualifier()
1387 != FunctionProtoArg->getRefQualifier() ||
1388 FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic())
1389 return Sema::TDK_NonDeducedMismatch;
1391 // Check return types.
1392 if (Sema::TemplateDeductionResult Result =
1393 DeduceTemplateArgumentsByTypeMatch(
1394 S, TemplateParams, FunctionProtoParam->getReturnType(),
1395 FunctionProtoArg->getReturnType(), Info, Deduced, 0))
1398 return DeduceTemplateArguments(
1399 S, TemplateParams, FunctionProtoParam->param_type_begin(),
1400 FunctionProtoParam->getNumParams(),
1401 FunctionProtoArg->param_type_begin(),
1402 FunctionProtoArg->getNumParams(), Info, Deduced, SubTDF);
1405 case Type::InjectedClassName: {
1406 // Treat a template's injected-class-name as if the template
1407 // specialization type had been used.
1408 Param = cast<InjectedClassNameType>(Param)
1409 ->getInjectedSpecializationType();
1410 assert(isa<TemplateSpecializationType>(Param) &&
1411 "injected class name is not a template specialization type");
1415 // template-name<T> (where template-name refers to a class template)
1420 case Type::TemplateSpecialization: {
1421 const TemplateSpecializationType *SpecParam
1422 = cast<TemplateSpecializationType>(Param);
1424 // Try to deduce template arguments from the template-id.
1425 Sema::TemplateDeductionResult Result
1426 = DeduceTemplateArguments(S, TemplateParams, SpecParam, Arg,
1429 if (Result && (TDF & TDF_DerivedClass)) {
1430 // C++ [temp.deduct.call]p3b3:
1431 // If P is a class, and P has the form template-id, then A can be a
1432 // derived class of the deduced A. Likewise, if P is a pointer to a
1433 // class of the form template-id, A can be a pointer to a derived
1434 // class pointed to by the deduced A.
1436 // More importantly:
1437 // These alternatives are considered only if type deduction would
1439 if (const RecordType *RecordT = Arg->getAs<RecordType>()) {
1440 // We cannot inspect base classes as part of deduction when the type
1441 // is incomplete, so either instantiate any templates necessary to
1442 // complete the type, or skip over it if it cannot be completed.
1443 if (S.RequireCompleteType(Info.getLocation(), Arg, 0))
1446 // Use data recursion to crawl through the list of base classes.
1447 // Visited contains the set of nodes we have already visited, while
1448 // ToVisit is our stack of records that we still need to visit.
1449 llvm::SmallPtrSet<const RecordType *, 8> Visited;
1450 SmallVector<const RecordType *, 8> ToVisit;
1451 ToVisit.push_back(RecordT);
1452 bool Successful = false;
1453 SmallVector<DeducedTemplateArgument, 8> DeducedOrig(Deduced.begin(),
1455 while (!ToVisit.empty()) {
1456 // Retrieve the next class in the inheritance hierarchy.
1457 const RecordType *NextT = ToVisit.pop_back_val();
1459 // If we have already seen this type, skip it.
1460 if (!Visited.insert(NextT).second)
1463 // If this is a base class, try to perform template argument
1464 // deduction from it.
1465 if (NextT != RecordT) {
1466 TemplateDeductionInfo BaseInfo(Info.getLocation());
1467 Sema::TemplateDeductionResult BaseResult
1468 = DeduceTemplateArguments(S, TemplateParams, SpecParam,
1469 QualType(NextT, 0), BaseInfo,
1472 // If template argument deduction for this base was successful,
1473 // note that we had some success. Otherwise, ignore any deductions
1474 // from this base class.
1475 if (BaseResult == Sema::TDK_Success) {
1477 DeducedOrig.clear();
1478 DeducedOrig.append(Deduced.begin(), Deduced.end());
1479 Info.Param = BaseInfo.Param;
1480 Info.FirstArg = BaseInfo.FirstArg;
1481 Info.SecondArg = BaseInfo.SecondArg;
1484 Deduced = DeducedOrig;
1487 // Visit base classes
1488 CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl());
1489 for (const auto &Base : Next->bases()) {
1490 assert(Base.getType()->isRecordType() &&
1491 "Base class that isn't a record?");
1492 ToVisit.push_back(Base.getType()->getAs<RecordType>());
1497 return Sema::TDK_Success;
1509 // type (type::*)(T)
1514 case Type::MemberPointer: {
1515 const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param);
1516 const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg);
1518 return Sema::TDK_NonDeducedMismatch;
1520 if (Sema::TemplateDeductionResult Result
1521 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1522 MemPtrParam->getPointeeType(),
1523 MemPtrArg->getPointeeType(),
1525 TDF & TDF_IgnoreQualifiers))
1528 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1529 QualType(MemPtrParam->getClass(), 0),
1530 QualType(MemPtrArg->getClass(), 0),
1532 TDF & TDF_IgnoreQualifiers);
1535 // (clang extension)
1540 case Type::BlockPointer: {
1541 const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param);
1542 const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg);
1545 return Sema::TDK_NonDeducedMismatch;
1547 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1548 BlockPtrParam->getPointeeType(),
1549 BlockPtrArg->getPointeeType(),
1553 // (clang extension)
1555 // T __attribute__(((ext_vector_type(<integral constant>))))
1556 case Type::ExtVector: {
1557 const ExtVectorType *VectorParam = cast<ExtVectorType>(Param);
1558 if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1559 // Make sure that the vectors have the same number of elements.
1560 if (VectorParam->getNumElements() != VectorArg->getNumElements())
1561 return Sema::TDK_NonDeducedMismatch;
1563 // Perform deduction on the element types.
1564 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1565 VectorParam->getElementType(),
1566 VectorArg->getElementType(),
1567 Info, Deduced, TDF);
1570 if (const DependentSizedExtVectorType *VectorArg
1571 = dyn_cast<DependentSizedExtVectorType>(Arg)) {
1572 // We can't check the number of elements, since the argument has a
1573 // dependent number of elements. This can only occur during partial
1576 // Perform deduction on the element types.
1577 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1578 VectorParam->getElementType(),
1579 VectorArg->getElementType(),
1580 Info, Deduced, TDF);
1583 return Sema::TDK_NonDeducedMismatch;
1586 // (clang extension)
1588 // T __attribute__(((ext_vector_type(N))))
1589 case Type::DependentSizedExtVector: {
1590 const DependentSizedExtVectorType *VectorParam
1591 = cast<DependentSizedExtVectorType>(Param);
1593 if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1594 // Perform deduction on the element types.
1595 if (Sema::TemplateDeductionResult Result
1596 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1597 VectorParam->getElementType(),
1598 VectorArg->getElementType(),
1599 Info, Deduced, TDF))
1602 // Perform deduction on the vector size, if we can.
1603 NonTypeTemplateParmDecl *NTTP
1604 = getDeducedParameterFromExpr(VectorParam->getSizeExpr());
1606 return Sema::TDK_Success;
1608 llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
1609 ArgSize = VectorArg->getNumElements();
1610 return DeduceNonTypeTemplateArgument(S, NTTP, ArgSize, S.Context.IntTy,
1611 false, Info, Deduced);
1614 if (const DependentSizedExtVectorType *VectorArg
1615 = dyn_cast<DependentSizedExtVectorType>(Arg)) {
1616 // Perform deduction on the element types.
1617 if (Sema::TemplateDeductionResult Result
1618 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1619 VectorParam->getElementType(),
1620 VectorArg->getElementType(),
1621 Info, Deduced, TDF))
1624 // Perform deduction on the vector size, if we can.
1625 NonTypeTemplateParmDecl *NTTP
1626 = getDeducedParameterFromExpr(VectorParam->getSizeExpr());
1628 return Sema::TDK_Success;
1630 return DeduceNonTypeTemplateArgument(S, NTTP, VectorArg->getSizeExpr(),
1634 return Sema::TDK_NonDeducedMismatch;
1637 case Type::TypeOfExpr:
1639 case Type::DependentName:
1640 case Type::UnresolvedUsing:
1641 case Type::Decltype:
1642 case Type::UnaryTransform:
1644 case Type::DependentTemplateSpecialization:
1645 case Type::PackExpansion:
1646 // No template argument deduction for these types
1647 return Sema::TDK_Success;
1650 llvm_unreachable("Invalid Type Class!");
1653 static Sema::TemplateDeductionResult
1654 DeduceTemplateArguments(Sema &S,
1655 TemplateParameterList *TemplateParams,
1656 const TemplateArgument &Param,
1657 TemplateArgument Arg,
1658 TemplateDeductionInfo &Info,
1659 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1660 // If the template argument is a pack expansion, perform template argument
1661 // deduction against the pattern of that expansion. This only occurs during
1662 // partial ordering.
1663 if (Arg.isPackExpansion())
1664 Arg = Arg.getPackExpansionPattern();
1666 switch (Param.getKind()) {
1667 case TemplateArgument::Null:
1668 llvm_unreachable("Null template argument in parameter list");
1670 case TemplateArgument::Type:
1671 if (Arg.getKind() == TemplateArgument::Type)
1672 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1676 Info.FirstArg = Param;
1677 Info.SecondArg = Arg;
1678 return Sema::TDK_NonDeducedMismatch;
1680 case TemplateArgument::Template:
1681 if (Arg.getKind() == TemplateArgument::Template)
1682 return DeduceTemplateArguments(S, TemplateParams,
1683 Param.getAsTemplate(),
1684 Arg.getAsTemplate(), Info, Deduced);
1685 Info.FirstArg = Param;
1686 Info.SecondArg = Arg;
1687 return Sema::TDK_NonDeducedMismatch;
1689 case TemplateArgument::TemplateExpansion:
1690 llvm_unreachable("caller should handle pack expansions");
1692 case TemplateArgument::Declaration:
1693 if (Arg.getKind() == TemplateArgument::Declaration &&
1694 isSameDeclaration(Param.getAsDecl(), Arg.getAsDecl()))
1695 return Sema::TDK_Success;
1697 Info.FirstArg = Param;
1698 Info.SecondArg = Arg;
1699 return Sema::TDK_NonDeducedMismatch;
1701 case TemplateArgument::NullPtr:
1702 if (Arg.getKind() == TemplateArgument::NullPtr &&
1703 S.Context.hasSameType(Param.getNullPtrType(), Arg.getNullPtrType()))
1704 return Sema::TDK_Success;
1706 Info.FirstArg = Param;
1707 Info.SecondArg = Arg;
1708 return Sema::TDK_NonDeducedMismatch;
1710 case TemplateArgument::Integral:
1711 if (Arg.getKind() == TemplateArgument::Integral) {
1712 if (hasSameExtendedValue(Param.getAsIntegral(), Arg.getAsIntegral()))
1713 return Sema::TDK_Success;
1715 Info.FirstArg = Param;
1716 Info.SecondArg = Arg;
1717 return Sema::TDK_NonDeducedMismatch;
1720 if (Arg.getKind() == TemplateArgument::Expression) {
1721 Info.FirstArg = Param;
1722 Info.SecondArg = Arg;
1723 return Sema::TDK_NonDeducedMismatch;
1726 Info.FirstArg = Param;
1727 Info.SecondArg = Arg;
1728 return Sema::TDK_NonDeducedMismatch;
1730 case TemplateArgument::Expression: {
1731 if (NonTypeTemplateParmDecl *NTTP
1732 = getDeducedParameterFromExpr(Param.getAsExpr())) {
1733 if (Arg.getKind() == TemplateArgument::Integral)
1734 return DeduceNonTypeTemplateArgument(S, NTTP,
1735 Arg.getAsIntegral(),
1736 Arg.getIntegralType(),
1737 /*ArrayBound=*/false,
1739 if (Arg.getKind() == TemplateArgument::Expression)
1740 return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsExpr(),
1742 if (Arg.getKind() == TemplateArgument::Declaration)
1743 return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsDecl(),
1746 Info.FirstArg = Param;
1747 Info.SecondArg = Arg;
1748 return Sema::TDK_NonDeducedMismatch;
1751 // Can't deduce anything, but that's okay.
1752 return Sema::TDK_Success;
1754 case TemplateArgument::Pack:
1755 llvm_unreachable("Argument packs should be expanded by the caller!");
1758 llvm_unreachable("Invalid TemplateArgument Kind!");
1761 /// \brief Determine whether there is a template argument to be used for
1764 /// This routine "expands" argument packs in-place, overriding its input
1765 /// parameters so that \c Args[ArgIdx] will be the available template argument.
1767 /// \returns true if there is another template argument (which will be at
1768 /// \c Args[ArgIdx]), false otherwise.
1769 static bool hasTemplateArgumentForDeduction(const TemplateArgument *&Args,
1771 unsigned &NumArgs) {
1772 if (ArgIdx == NumArgs)
1775 const TemplateArgument &Arg = Args[ArgIdx];
1776 if (Arg.getKind() != TemplateArgument::Pack)
1779 assert(ArgIdx == NumArgs - 1 && "Pack not at the end of argument list?");
1780 Args = Arg.pack_begin();
1781 NumArgs = Arg.pack_size();
1783 return ArgIdx < NumArgs;
1786 /// \brief Determine whether the given set of template arguments has a pack
1787 /// expansion that is not the last template argument.
1788 static bool hasPackExpansionBeforeEnd(const TemplateArgument *Args,
1790 unsigned ArgIdx = 0;
1791 while (ArgIdx < NumArgs) {
1792 const TemplateArgument &Arg = Args[ArgIdx];
1794 // Unwrap argument packs.
1795 if (Args[ArgIdx].getKind() == TemplateArgument::Pack) {
1796 Args = Arg.pack_begin();
1797 NumArgs = Arg.pack_size();
1803 if (ArgIdx == NumArgs)
1806 if (Arg.isPackExpansion())
1813 static Sema::TemplateDeductionResult
1814 DeduceTemplateArguments(Sema &S,
1815 TemplateParameterList *TemplateParams,
1816 const TemplateArgument *Params, unsigned NumParams,
1817 const TemplateArgument *Args, unsigned NumArgs,
1818 TemplateDeductionInfo &Info,
1819 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1820 // C++0x [temp.deduct.type]p9:
1821 // If the template argument list of P contains a pack expansion that is not
1822 // the last template argument, the entire template argument list is a
1823 // non-deduced context.
1824 if (hasPackExpansionBeforeEnd(Params, NumParams))
1825 return Sema::TDK_Success;
1827 // C++0x [temp.deduct.type]p9:
1828 // If P has a form that contains <T> or <i>, then each argument Pi of the
1829 // respective template argument list P is compared with the corresponding
1830 // argument Ai of the corresponding template argument list of A.
1831 unsigned ArgIdx = 0, ParamIdx = 0;
1832 for (; hasTemplateArgumentForDeduction(Params, ParamIdx, NumParams);
1834 if (!Params[ParamIdx].isPackExpansion()) {
1835 // The simple case: deduce template arguments by matching Pi and Ai.
1837 // Check whether we have enough arguments.
1838 if (!hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs))
1839 return Sema::TDK_Success;
1841 if (Args[ArgIdx].isPackExpansion()) {
1842 // FIXME: We follow the logic of C++0x [temp.deduct.type]p22 here,
1843 // but applied to pack expansions that are template arguments.
1844 return Sema::TDK_MiscellaneousDeductionFailure;
1847 // Perform deduction for this Pi/Ai pair.
1848 if (Sema::TemplateDeductionResult Result
1849 = DeduceTemplateArguments(S, TemplateParams,
1850 Params[ParamIdx], Args[ArgIdx],
1854 // Move to the next argument.
1859 // The parameter is a pack expansion.
1861 // C++0x [temp.deduct.type]p9:
1862 // If Pi is a pack expansion, then the pattern of Pi is compared with
1863 // each remaining argument in the template argument list of A. Each
1864 // comparison deduces template arguments for subsequent positions in the
1865 // template parameter packs expanded by Pi.
1866 TemplateArgument Pattern = Params[ParamIdx].getPackExpansionPattern();
1868 // FIXME: If there are no remaining arguments, we can bail out early
1869 // and set any deduced parameter packs to an empty argument pack.
1870 // The latter part of this is a (minor) correctness issue.
1872 // Prepare to deduce the packs within the pattern.
1873 PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
1875 // Keep track of the deduced template arguments for each parameter pack
1876 // expanded by this pack expansion (the outer index) and for each
1877 // template argument (the inner SmallVectors).
1878 bool HasAnyArguments = false;
1879 for (; hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs); ++ArgIdx) {
1880 HasAnyArguments = true;
1882 // Deduce template arguments from the pattern.
1883 if (Sema::TemplateDeductionResult Result
1884 = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx],
1888 PackScope.nextPackElement();
1891 // Build argument packs for each of the parameter packs expanded by this
1893 if (auto Result = PackScope.finish(HasAnyArguments))
1897 return Sema::TDK_Success;
1900 static Sema::TemplateDeductionResult
1901 DeduceTemplateArguments(Sema &S,
1902 TemplateParameterList *TemplateParams,
1903 const TemplateArgumentList &ParamList,
1904 const TemplateArgumentList &ArgList,
1905 TemplateDeductionInfo &Info,
1906 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1907 return DeduceTemplateArguments(S, TemplateParams,
1908 ParamList.data(), ParamList.size(),
1909 ArgList.data(), ArgList.size(),
1913 /// \brief Determine whether two template arguments are the same.
1914 static bool isSameTemplateArg(ASTContext &Context,
1915 const TemplateArgument &X,
1916 const TemplateArgument &Y) {
1917 if (X.getKind() != Y.getKind())
1920 switch (X.getKind()) {
1921 case TemplateArgument::Null:
1922 llvm_unreachable("Comparing NULL template argument");
1924 case TemplateArgument::Type:
1925 return Context.getCanonicalType(X.getAsType()) ==
1926 Context.getCanonicalType(Y.getAsType());
1928 case TemplateArgument::Declaration:
1929 return isSameDeclaration(X.getAsDecl(), Y.getAsDecl());
1931 case TemplateArgument::NullPtr:
1932 return Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType());
1934 case TemplateArgument::Template:
1935 case TemplateArgument::TemplateExpansion:
1936 return Context.getCanonicalTemplateName(
1937 X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() ==
1938 Context.getCanonicalTemplateName(
1939 Y.getAsTemplateOrTemplatePattern()).getAsVoidPointer();
1941 case TemplateArgument::Integral:
1942 return X.getAsIntegral() == Y.getAsIntegral();
1944 case TemplateArgument::Expression: {
1945 llvm::FoldingSetNodeID XID, YID;
1946 X.getAsExpr()->Profile(XID, Context, true);
1947 Y.getAsExpr()->Profile(YID, Context, true);
1951 case TemplateArgument::Pack:
1952 if (X.pack_size() != Y.pack_size())
1955 for (TemplateArgument::pack_iterator XP = X.pack_begin(),
1956 XPEnd = X.pack_end(),
1957 YP = Y.pack_begin();
1958 XP != XPEnd; ++XP, ++YP)
1959 if (!isSameTemplateArg(Context, *XP, *YP))
1965 llvm_unreachable("Invalid TemplateArgument Kind!");
1968 /// \brief Allocate a TemplateArgumentLoc where all locations have
1969 /// been initialized to the given location.
1971 /// \param S The semantic analysis object.
1973 /// \param Arg The template argument we are producing template argument
1974 /// location information for.
1976 /// \param NTTPType For a declaration template argument, the type of
1977 /// the non-type template parameter that corresponds to this template
1980 /// \param Loc The source location to use for the resulting template
1982 static TemplateArgumentLoc
1983 getTrivialTemplateArgumentLoc(Sema &S,
1984 const TemplateArgument &Arg,
1986 SourceLocation Loc) {
1987 switch (Arg.getKind()) {
1988 case TemplateArgument::Null:
1989 llvm_unreachable("Can't get a NULL template argument here");
1991 case TemplateArgument::Type:
1992 return TemplateArgumentLoc(Arg,
1993 S.Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc));
1995 case TemplateArgument::Declaration: {
1997 = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
1999 return TemplateArgumentLoc(TemplateArgument(E), E);
2002 case TemplateArgument::NullPtr: {
2004 = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2006 return TemplateArgumentLoc(TemplateArgument(NTTPType, /*isNullPtr*/true),
2010 case TemplateArgument::Integral: {
2012 = S.BuildExpressionFromIntegralTemplateArgument(Arg, Loc).getAs<Expr>();
2013 return TemplateArgumentLoc(TemplateArgument(E), E);
2016 case TemplateArgument::Template:
2017 case TemplateArgument::TemplateExpansion: {
2018 NestedNameSpecifierLocBuilder Builder;
2019 TemplateName Template = Arg.getAsTemplate();
2020 if (DependentTemplateName *DTN = Template.getAsDependentTemplateName())
2021 Builder.MakeTrivial(S.Context, DTN->getQualifier(), Loc);
2022 else if (QualifiedTemplateName *QTN =
2023 Template.getAsQualifiedTemplateName())
2024 Builder.MakeTrivial(S.Context, QTN->getQualifier(), Loc);
2026 if (Arg.getKind() == TemplateArgument::Template)
2027 return TemplateArgumentLoc(Arg,
2028 Builder.getWithLocInContext(S.Context),
2032 return TemplateArgumentLoc(Arg, Builder.getWithLocInContext(S.Context),
2036 case TemplateArgument::Expression:
2037 return TemplateArgumentLoc(Arg, Arg.getAsExpr());
2039 case TemplateArgument::Pack:
2040 return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo());
2043 llvm_unreachable("Invalid TemplateArgument Kind!");
2047 /// \brief Convert the given deduced template argument and add it to the set of
2048 /// fully-converted template arguments.
2050 ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param,
2051 DeducedTemplateArgument Arg,
2052 NamedDecl *Template,
2054 unsigned ArgumentPackIndex,
2055 TemplateDeductionInfo &Info,
2056 bool InFunctionTemplate,
2057 SmallVectorImpl<TemplateArgument> &Output) {
2058 if (Arg.getKind() == TemplateArgument::Pack) {
2059 // This is a template argument pack, so check each of its arguments against
2060 // the template parameter.
2061 SmallVector<TemplateArgument, 2> PackedArgsBuilder;
2062 for (const auto &P : Arg.pack_elements()) {
2063 // When converting the deduced template argument, append it to the
2064 // general output list. We need to do this so that the template argument
2065 // checking logic has all of the prior template arguments available.
2066 DeducedTemplateArgument InnerArg(P);
2067 InnerArg.setDeducedFromArrayBound(Arg.wasDeducedFromArrayBound());
2068 if (ConvertDeducedTemplateArgument(S, Param, InnerArg, Template,
2069 NTTPType, PackedArgsBuilder.size(),
2070 Info, InFunctionTemplate, Output))
2073 // Move the converted template argument into our argument pack.
2074 PackedArgsBuilder.push_back(Output.pop_back_val());
2077 // Create the resulting argument pack.
2078 Output.push_back(TemplateArgument::CreatePackCopy(S.Context,
2079 PackedArgsBuilder.data(),
2080 PackedArgsBuilder.size()));
2084 // Convert the deduced template argument into a template
2085 // argument that we can check, almost as if the user had written
2086 // the template argument explicitly.
2087 TemplateArgumentLoc ArgLoc = getTrivialTemplateArgumentLoc(S, Arg, NTTPType,
2088 Info.getLocation());
2090 // Check the template argument, converting it as necessary.
2091 return S.CheckTemplateArgument(Param, ArgLoc,
2093 Template->getLocation(),
2094 Template->getSourceRange().getEnd(),
2098 ? (Arg.wasDeducedFromArrayBound()
2099 ? Sema::CTAK_DeducedFromArrayBound
2100 : Sema::CTAK_Deduced)
2101 : Sema::CTAK_Specified);
2104 /// Complete template argument deduction for a class template partial
2106 static Sema::TemplateDeductionResult
2107 FinishTemplateArgumentDeduction(Sema &S,
2108 ClassTemplatePartialSpecializationDecl *Partial,
2109 const TemplateArgumentList &TemplateArgs,
2110 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2111 TemplateDeductionInfo &Info) {
2112 // Unevaluated SFINAE context.
2113 EnterExpressionEvaluationContext Unevaluated(S, Sema::Unevaluated);
2114 Sema::SFINAETrap Trap(S);
2116 Sema::ContextRAII SavedContext(S, Partial);
2118 // C++ [temp.deduct.type]p2:
2119 // [...] or if any template argument remains neither deduced nor
2120 // explicitly specified, template argument deduction fails.
2121 SmallVector<TemplateArgument, 4> Builder;
2122 TemplateParameterList *PartialParams = Partial->getTemplateParameters();
2123 for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) {
2124 NamedDecl *Param = PartialParams->getParam(I);
2125 if (Deduced[I].isNull()) {
2126 Info.Param = makeTemplateParameter(Param);
2127 return Sema::TDK_Incomplete;
2130 // We have deduced this argument, so it still needs to be
2131 // checked and converted.
2133 // First, for a non-type template parameter type that is
2134 // initialized by a declaration, we need the type of the
2135 // corresponding non-type template parameter.
2137 if (NonTypeTemplateParmDecl *NTTP
2138 = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2139 NTTPType = NTTP->getType();
2140 if (NTTPType->isDependentType()) {
2141 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2142 Builder.data(), Builder.size());
2143 NTTPType = S.SubstType(NTTPType,
2144 MultiLevelTemplateArgumentList(TemplateArgs),
2145 NTTP->getLocation(),
2146 NTTP->getDeclName());
2147 if (NTTPType.isNull()) {
2148 Info.Param = makeTemplateParameter(Param);
2149 // FIXME: These template arguments are temporary. Free them!
2150 Info.reset(TemplateArgumentList::CreateCopy(S.Context,
2153 return Sema::TDK_SubstitutionFailure;
2158 if (ConvertDeducedTemplateArgument(S, Param, Deduced[I],
2159 Partial, NTTPType, 0, Info, false,
2161 Info.Param = makeTemplateParameter(Param);
2162 // FIXME: These template arguments are temporary. Free them!
2163 Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2165 return Sema::TDK_SubstitutionFailure;
2169 // Form the template argument list from the deduced template arguments.
2170 TemplateArgumentList *DeducedArgumentList
2171 = TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2174 Info.reset(DeducedArgumentList);
2176 // Substitute the deduced template arguments into the template
2177 // arguments of the class template partial specialization, and
2178 // verify that the instantiated template arguments are both valid
2179 // and are equivalent to the template arguments originally provided
2180 // to the class template.
2181 LocalInstantiationScope InstScope(S);
2182 ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate();
2183 const ASTTemplateArgumentListInfo *PartialTemplArgInfo
2184 = Partial->getTemplateArgsAsWritten();
2185 const TemplateArgumentLoc *PartialTemplateArgs
2186 = PartialTemplArgInfo->getTemplateArgs();
2188 TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc,
2189 PartialTemplArgInfo->RAngleLoc);
2191 if (S.Subst(PartialTemplateArgs, PartialTemplArgInfo->NumTemplateArgs,
2192 InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
2193 unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2194 if (ParamIdx >= Partial->getTemplateParameters()->size())
2195 ParamIdx = Partial->getTemplateParameters()->size() - 1;
2198 = const_cast<NamedDecl *>(
2199 Partial->getTemplateParameters()->getParam(ParamIdx));
2200 Info.Param = makeTemplateParameter(Param);
2201 Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
2202 return Sema::TDK_SubstitutionFailure;
2205 SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2206 if (S.CheckTemplateArgumentList(ClassTemplate, Partial->getLocation(),
2207 InstArgs, false, ConvertedInstArgs))
2208 return Sema::TDK_SubstitutionFailure;
2210 TemplateParameterList *TemplateParams
2211 = ClassTemplate->getTemplateParameters();
2212 for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2213 TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2214 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2215 Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2216 Info.FirstArg = TemplateArgs[I];
2217 Info.SecondArg = InstArg;
2218 return Sema::TDK_NonDeducedMismatch;
2222 if (Trap.hasErrorOccurred())
2223 return Sema::TDK_SubstitutionFailure;
2225 return Sema::TDK_Success;
2228 /// \brief Perform template argument deduction to determine whether
2229 /// the given template arguments match the given class template
2230 /// partial specialization per C++ [temp.class.spec.match].
2231 Sema::TemplateDeductionResult
2232 Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
2233 const TemplateArgumentList &TemplateArgs,
2234 TemplateDeductionInfo &Info) {
2235 if (Partial->isInvalidDecl())
2238 // C++ [temp.class.spec.match]p2:
2239 // A partial specialization matches a given actual template
2240 // argument list if the template arguments of the partial
2241 // specialization can be deduced from the actual template argument
2244 // Unevaluated SFINAE context.
2245 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2246 SFINAETrap Trap(*this);
2248 SmallVector<DeducedTemplateArgument, 4> Deduced;
2249 Deduced.resize(Partial->getTemplateParameters()->size());
2250 if (TemplateDeductionResult Result
2251 = ::DeduceTemplateArguments(*this,
2252 Partial->getTemplateParameters(),
2253 Partial->getTemplateArgs(),
2254 TemplateArgs, Info, Deduced))
2257 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2258 InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
2260 if (Inst.isInvalid())
2261 return TDK_InstantiationDepth;
2263 if (Trap.hasErrorOccurred())
2264 return Sema::TDK_SubstitutionFailure;
2266 return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs,
2270 /// Complete template argument deduction for a variable template partial
2272 /// TODO: Unify with ClassTemplatePartialSpecializationDecl version?
2273 /// May require unifying ClassTemplate(Partial)SpecializationDecl and
2274 /// VarTemplate(Partial)SpecializationDecl with a new data
2275 /// structure Template(Partial)SpecializationDecl, and
2276 /// using Template(Partial)SpecializationDecl as input type.
2277 static Sema::TemplateDeductionResult FinishTemplateArgumentDeduction(
2278 Sema &S, VarTemplatePartialSpecializationDecl *Partial,
2279 const TemplateArgumentList &TemplateArgs,
2280 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2281 TemplateDeductionInfo &Info) {
2282 // Unevaluated SFINAE context.
2283 EnterExpressionEvaluationContext Unevaluated(S, Sema::Unevaluated);
2284 Sema::SFINAETrap Trap(S);
2286 // C++ [temp.deduct.type]p2:
2287 // [...] or if any template argument remains neither deduced nor
2288 // explicitly specified, template argument deduction fails.
2289 SmallVector<TemplateArgument, 4> Builder;
2290 TemplateParameterList *PartialParams = Partial->getTemplateParameters();
2291 for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) {
2292 NamedDecl *Param = PartialParams->getParam(I);
2293 if (Deduced[I].isNull()) {
2294 Info.Param = makeTemplateParameter(Param);
2295 return Sema::TDK_Incomplete;
2298 // We have deduced this argument, so it still needs to be
2299 // checked and converted.
2301 // First, for a non-type template parameter type that is
2302 // initialized by a declaration, we need the type of the
2303 // corresponding non-type template parameter.
2305 if (NonTypeTemplateParmDecl *NTTP =
2306 dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2307 NTTPType = NTTP->getType();
2308 if (NTTPType->isDependentType()) {
2309 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2310 Builder.data(), Builder.size());
2312 S.SubstType(NTTPType, MultiLevelTemplateArgumentList(TemplateArgs),
2313 NTTP->getLocation(), NTTP->getDeclName());
2314 if (NTTPType.isNull()) {
2315 Info.Param = makeTemplateParameter(Param);
2316 // FIXME: These template arguments are temporary. Free them!
2317 Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2319 return Sema::TDK_SubstitutionFailure;
2324 if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Partial, NTTPType,
2325 0, Info, false, Builder)) {
2326 Info.Param = makeTemplateParameter(Param);
2327 // FIXME: These template arguments are temporary. Free them!
2328 Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2330 return Sema::TDK_SubstitutionFailure;
2334 // Form the template argument list from the deduced template arguments.
2335 TemplateArgumentList *DeducedArgumentList = TemplateArgumentList::CreateCopy(
2336 S.Context, Builder.data(), Builder.size());
2338 Info.reset(DeducedArgumentList);
2340 // Substitute the deduced template arguments into the template
2341 // arguments of the class template partial specialization, and
2342 // verify that the instantiated template arguments are both valid
2343 // and are equivalent to the template arguments originally provided
2344 // to the class template.
2345 LocalInstantiationScope InstScope(S);
2346 VarTemplateDecl *VarTemplate = Partial->getSpecializedTemplate();
2347 const ASTTemplateArgumentListInfo *PartialTemplArgInfo
2348 = Partial->getTemplateArgsAsWritten();
2349 const TemplateArgumentLoc *PartialTemplateArgs
2350 = PartialTemplArgInfo->getTemplateArgs();
2352 TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc,
2353 PartialTemplArgInfo->RAngleLoc);
2355 if (S.Subst(PartialTemplateArgs, PartialTemplArgInfo->NumTemplateArgs,
2356 InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
2357 unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2358 if (ParamIdx >= Partial->getTemplateParameters()->size())
2359 ParamIdx = Partial->getTemplateParameters()->size() - 1;
2361 Decl *Param = const_cast<NamedDecl *>(
2362 Partial->getTemplateParameters()->getParam(ParamIdx));
2363 Info.Param = makeTemplateParameter(Param);
2364 Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
2365 return Sema::TDK_SubstitutionFailure;
2367 SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2368 if (S.CheckTemplateArgumentList(VarTemplate, Partial->getLocation(), InstArgs,
2369 false, ConvertedInstArgs))
2370 return Sema::TDK_SubstitutionFailure;
2372 TemplateParameterList *TemplateParams = VarTemplate->getTemplateParameters();
2373 for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2374 TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2375 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2376 Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2377 Info.FirstArg = TemplateArgs[I];
2378 Info.SecondArg = InstArg;
2379 return Sema::TDK_NonDeducedMismatch;
2383 if (Trap.hasErrorOccurred())
2384 return Sema::TDK_SubstitutionFailure;
2386 return Sema::TDK_Success;
2389 /// \brief Perform template argument deduction to determine whether
2390 /// the given template arguments match the given variable template
2391 /// partial specialization per C++ [temp.class.spec.match].
2392 /// TODO: Unify with ClassTemplatePartialSpecializationDecl version?
2393 /// May require unifying ClassTemplate(Partial)SpecializationDecl and
2394 /// VarTemplate(Partial)SpecializationDecl with a new data
2395 /// structure Template(Partial)SpecializationDecl, and
2396 /// using Template(Partial)SpecializationDecl as input type.
2397 Sema::TemplateDeductionResult
2398 Sema::DeduceTemplateArguments(VarTemplatePartialSpecializationDecl *Partial,
2399 const TemplateArgumentList &TemplateArgs,
2400 TemplateDeductionInfo &Info) {
2401 if (Partial->isInvalidDecl())
2404 // C++ [temp.class.spec.match]p2:
2405 // A partial specialization matches a given actual template
2406 // argument list if the template arguments of the partial
2407 // specialization can be deduced from the actual template argument
2410 // Unevaluated SFINAE context.
2411 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2412 SFINAETrap Trap(*this);
2414 SmallVector<DeducedTemplateArgument, 4> Deduced;
2415 Deduced.resize(Partial->getTemplateParameters()->size());
2416 if (TemplateDeductionResult Result = ::DeduceTemplateArguments(
2417 *this, Partial->getTemplateParameters(), Partial->getTemplateArgs(),
2418 TemplateArgs, Info, Deduced))
2421 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2422 InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
2424 if (Inst.isInvalid())
2425 return TDK_InstantiationDepth;
2427 if (Trap.hasErrorOccurred())
2428 return Sema::TDK_SubstitutionFailure;
2430 return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs,
2434 /// \brief Determine whether the given type T is a simple-template-id type.
2435 static bool isSimpleTemplateIdType(QualType T) {
2436 if (const TemplateSpecializationType *Spec
2437 = T->getAs<TemplateSpecializationType>())
2438 return Spec->getTemplateName().getAsTemplateDecl() != nullptr;
2443 /// \brief Substitute the explicitly-provided template arguments into the
2444 /// given function template according to C++ [temp.arg.explicit].
2446 /// \param FunctionTemplate the function template into which the explicit
2447 /// template arguments will be substituted.
2449 /// \param ExplicitTemplateArgs the explicitly-specified template
2452 /// \param Deduced the deduced template arguments, which will be populated
2453 /// with the converted and checked explicit template arguments.
2455 /// \param ParamTypes will be populated with the instantiated function
2458 /// \param FunctionType if non-NULL, the result type of the function template
2459 /// will also be instantiated and the pointed-to value will be updated with
2460 /// the instantiated function type.
2462 /// \param Info if substitution fails for any reason, this object will be
2463 /// populated with more information about the failure.
2465 /// \returns TDK_Success if substitution was successful, or some failure
2467 Sema::TemplateDeductionResult
2468 Sema::SubstituteExplicitTemplateArguments(
2469 FunctionTemplateDecl *FunctionTemplate,
2470 TemplateArgumentListInfo &ExplicitTemplateArgs,
2471 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2472 SmallVectorImpl<QualType> &ParamTypes,
2473 QualType *FunctionType,
2474 TemplateDeductionInfo &Info) {
2475 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
2476 TemplateParameterList *TemplateParams
2477 = FunctionTemplate->getTemplateParameters();
2479 if (ExplicitTemplateArgs.size() == 0) {
2480 // No arguments to substitute; just copy over the parameter types and
2481 // fill in the function type.
2482 for (auto P : Function->params())
2483 ParamTypes.push_back(P->getType());
2486 *FunctionType = Function->getType();
2490 // Unevaluated SFINAE context.
2491 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2492 SFINAETrap Trap(*this);
2494 // C++ [temp.arg.explicit]p3:
2495 // Template arguments that are present shall be specified in the
2496 // declaration order of their corresponding template-parameters. The
2497 // template argument list shall not specify more template-arguments than
2498 // there are corresponding template-parameters.
2499 SmallVector<TemplateArgument, 4> Builder;
2501 // Enter a new template instantiation context where we check the
2502 // explicitly-specified template arguments against this function template,
2503 // and then substitute them into the function parameter types.
2504 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2505 InstantiatingTemplate Inst(*this, Info.getLocation(), FunctionTemplate,
2507 ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution,
2509 if (Inst.isInvalid())
2510 return TDK_InstantiationDepth;
2512 if (CheckTemplateArgumentList(FunctionTemplate,
2514 ExplicitTemplateArgs,
2516 Builder) || Trap.hasErrorOccurred()) {
2517 unsigned Index = Builder.size();
2518 if (Index >= TemplateParams->size())
2519 Index = TemplateParams->size() - 1;
2520 Info.Param = makeTemplateParameter(TemplateParams->getParam(Index));
2521 return TDK_InvalidExplicitArguments;
2524 // Form the template argument list from the explicitly-specified
2525 // template arguments.
2526 TemplateArgumentList *ExplicitArgumentList
2527 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
2528 Info.reset(ExplicitArgumentList);
2530 // Template argument deduction and the final substitution should be
2531 // done in the context of the templated declaration. Explicit
2532 // argument substitution, on the other hand, needs to happen in the
2534 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2536 // If we deduced template arguments for a template parameter pack,
2537 // note that the template argument pack is partially substituted and record
2538 // the explicit template arguments. They'll be used as part of deduction
2539 // for this template parameter pack.
2540 for (unsigned I = 0, N = Builder.size(); I != N; ++I) {
2541 const TemplateArgument &Arg = Builder[I];
2542 if (Arg.getKind() == TemplateArgument::Pack) {
2543 CurrentInstantiationScope->SetPartiallySubstitutedPack(
2544 TemplateParams->getParam(I),
2551 const FunctionProtoType *Proto
2552 = Function->getType()->getAs<FunctionProtoType>();
2553 assert(Proto && "Function template does not have a prototype?");
2555 // Isolate our substituted parameters from our caller.
2556 LocalInstantiationScope InstScope(*this, /*MergeWithOuterScope*/true);
2558 // Instantiate the types of each of the function parameters given the
2559 // explicitly-specified template arguments. If the function has a trailing
2560 // return type, substitute it after the arguments to ensure we substitute
2561 // in lexical order.
2562 if (Proto->hasTrailingReturn()) {
2563 if (SubstParmTypes(Function->getLocation(),
2564 Function->param_begin(), Function->getNumParams(),
2565 MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2567 return TDK_SubstitutionFailure;
2570 // Instantiate the return type.
2571 QualType ResultType;
2573 // C++11 [expr.prim.general]p3:
2574 // If a declaration declares a member function or member function
2575 // template of a class X, the expression this is a prvalue of type
2576 // "pointer to cv-qualifier-seq X" between the optional cv-qualifer-seq
2577 // and the end of the function-definition, member-declarator, or
2579 unsigned ThisTypeQuals = 0;
2580 CXXRecordDecl *ThisContext = nullptr;
2581 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Function)) {
2582 ThisContext = Method->getParent();
2583 ThisTypeQuals = Method->getTypeQualifiers();
2586 CXXThisScopeRAII ThisScope(*this, ThisContext, ThisTypeQuals,
2587 getLangOpts().CPlusPlus11);
2590 SubstType(Proto->getReturnType(),
2591 MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2592 Function->getTypeSpecStartLoc(), Function->getDeclName());
2593 if (ResultType.isNull() || Trap.hasErrorOccurred())
2594 return TDK_SubstitutionFailure;
2597 // Instantiate the types of each of the function parameters given the
2598 // explicitly-specified template arguments if we didn't do so earlier.
2599 if (!Proto->hasTrailingReturn() &&
2600 SubstParmTypes(Function->getLocation(),
2601 Function->param_begin(), Function->getNumParams(),
2602 MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2604 return TDK_SubstitutionFailure;
2607 *FunctionType = BuildFunctionType(ResultType, ParamTypes,
2608 Function->getLocation(),
2609 Function->getDeclName(),
2610 Proto->getExtProtoInfo());
2611 if (FunctionType->isNull() || Trap.hasErrorOccurred())
2612 return TDK_SubstitutionFailure;
2615 // C++ [temp.arg.explicit]p2:
2616 // Trailing template arguments that can be deduced (14.8.2) may be
2617 // omitted from the list of explicit template-arguments. If all of the
2618 // template arguments can be deduced, they may all be omitted; in this
2619 // case, the empty template argument list <> itself may also be omitted.
2621 // Take all of the explicitly-specified arguments and put them into
2622 // the set of deduced template arguments. Explicitly-specified
2623 // parameter packs, however, will be set to NULL since the deduction
2624 // mechanisms handle explicitly-specified argument packs directly.
2625 Deduced.reserve(TemplateParams->size());
2626 for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) {
2627 const TemplateArgument &Arg = ExplicitArgumentList->get(I);
2628 if (Arg.getKind() == TemplateArgument::Pack)
2629 Deduced.push_back(DeducedTemplateArgument());
2631 Deduced.push_back(Arg);
2637 /// \brief Check whether the deduced argument type for a call to a function
2638 /// template matches the actual argument type per C++ [temp.deduct.call]p4.
2640 CheckOriginalCallArgDeduction(Sema &S, Sema::OriginalCallArg OriginalArg,
2641 QualType DeducedA) {
2642 ASTContext &Context = S.Context;
2644 QualType A = OriginalArg.OriginalArgType;
2645 QualType OriginalParamType = OriginalArg.OriginalParamType;
2647 // Check for type equality (top-level cv-qualifiers are ignored).
2648 if (Context.hasSameUnqualifiedType(A, DeducedA))
2651 // Strip off references on the argument types; they aren't needed for
2652 // the following checks.
2653 if (const ReferenceType *DeducedARef = DeducedA->getAs<ReferenceType>())
2654 DeducedA = DeducedARef->getPointeeType();
2655 if (const ReferenceType *ARef = A->getAs<ReferenceType>())
2656 A = ARef->getPointeeType();
2658 // C++ [temp.deduct.call]p4:
2659 // [...] However, there are three cases that allow a difference:
2660 // - If the original P is a reference type, the deduced A (i.e., the
2661 // type referred to by the reference) can be more cv-qualified than
2662 // the transformed A.
2663 if (const ReferenceType *OriginalParamRef
2664 = OriginalParamType->getAs<ReferenceType>()) {
2665 // We don't want to keep the reference around any more.
2666 OriginalParamType = OriginalParamRef->getPointeeType();
2668 Qualifiers AQuals = A.getQualifiers();
2669 Qualifiers DeducedAQuals = DeducedA.getQualifiers();
2671 // Under Objective-C++ ARC, the deduced type may have implicitly
2672 // been given strong or (when dealing with a const reference)
2673 // unsafe_unretained lifetime. If so, update the original
2674 // qualifiers to include this lifetime.
2675 if (S.getLangOpts().ObjCAutoRefCount &&
2676 ((DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_Strong &&
2677 AQuals.getObjCLifetime() == Qualifiers::OCL_None) ||
2678 (DeducedAQuals.hasConst() &&
2679 DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone))) {
2680 AQuals.setObjCLifetime(DeducedAQuals.getObjCLifetime());
2683 if (AQuals == DeducedAQuals) {
2684 // Qualifiers match; there's nothing to do.
2685 } else if (!DeducedAQuals.compatiblyIncludes(AQuals)) {
2688 // Qualifiers are compatible, so have the argument type adopt the
2689 // deduced argument type's qualifiers as if we had performed the
2690 // qualification conversion.
2691 A = Context.getQualifiedType(A.getUnqualifiedType(), DeducedAQuals);
2695 // - The transformed A can be another pointer or pointer to member
2696 // type that can be converted to the deduced A via a qualification
2699 // Also allow conversions which merely strip [[noreturn]] from function types
2700 // (recursively) as an extension.
2701 // FIXME: Currently, this doesn't play nicely with qualification conversions.
2702 bool ObjCLifetimeConversion = false;
2704 if ((A->isAnyPointerType() || A->isMemberPointerType()) &&
2705 (S.IsQualificationConversion(A, DeducedA, false,
2706 ObjCLifetimeConversion) ||
2707 S.IsNoReturnConversion(A, DeducedA, ResultTy)))
2711 // - If P is a class and P has the form simple-template-id, then the
2712 // transformed A can be a derived class of the deduced A. [...]
2713 // [...] Likewise, if P is a pointer to a class of the form
2714 // simple-template-id, the transformed A can be a pointer to a
2715 // derived class pointed to by the deduced A.
2716 if (const PointerType *OriginalParamPtr
2717 = OriginalParamType->getAs<PointerType>()) {
2718 if (const PointerType *DeducedAPtr = DeducedA->getAs<PointerType>()) {
2719 if (const PointerType *APtr = A->getAs<PointerType>()) {
2720 if (A->getPointeeType()->isRecordType()) {
2721 OriginalParamType = OriginalParamPtr->getPointeeType();
2722 DeducedA = DeducedAPtr->getPointeeType();
2723 A = APtr->getPointeeType();
2729 if (Context.hasSameUnqualifiedType(A, DeducedA))
2732 if (A->isRecordType() && isSimpleTemplateIdType(OriginalParamType) &&
2733 S.IsDerivedFrom(A, DeducedA))
2739 /// \brief Finish template argument deduction for a function template,
2740 /// checking the deduced template arguments for completeness and forming
2741 /// the function template specialization.
2743 /// \param OriginalCallArgs If non-NULL, the original call arguments against
2744 /// which the deduced argument types should be compared.
2745 Sema::TemplateDeductionResult
2746 Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate,
2747 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2748 unsigned NumExplicitlySpecified,
2749 FunctionDecl *&Specialization,
2750 TemplateDeductionInfo &Info,
2751 SmallVectorImpl<OriginalCallArg> const *OriginalCallArgs,
2752 bool PartialOverloading) {
2753 TemplateParameterList *TemplateParams
2754 = FunctionTemplate->getTemplateParameters();
2756 // Unevaluated SFINAE context.
2757 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2758 SFINAETrap Trap(*this);
2760 // Enter a new template instantiation context while we instantiate the
2761 // actual function declaration.
2762 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2763 InstantiatingTemplate Inst(*this, Info.getLocation(), FunctionTemplate,
2765 ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution,
2767 if (Inst.isInvalid())
2768 return TDK_InstantiationDepth;
2770 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2772 // C++ [temp.deduct.type]p2:
2773 // [...] or if any template argument remains neither deduced nor
2774 // explicitly specified, template argument deduction fails.
2775 SmallVector<TemplateArgument, 4> Builder;
2776 for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) {
2777 NamedDecl *Param = TemplateParams->getParam(I);
2779 if (!Deduced[I].isNull()) {
2780 if (I < NumExplicitlySpecified) {
2781 // We have already fully type-checked and converted this
2782 // argument, because it was explicitly-specified. Just record the
2783 // presence of this argument.
2784 Builder.push_back(Deduced[I]);
2785 // We may have had explicitly-specified template arguments for a
2786 // template parameter pack (that may or may not have been extended
2787 // via additional deduced arguments).
2788 if (Param->isParameterPack() && CurrentInstantiationScope) {
2789 if (CurrentInstantiationScope->getPartiallySubstitutedPack() ==
2791 // Forget the partially-substituted pack; its substitution is now
2793 CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2798 // We have deduced this argument, so it still needs to be
2799 // checked and converted.
2801 // First, for a non-type template parameter type that is
2802 // initialized by a declaration, we need the type of the
2803 // corresponding non-type template parameter.
2805 if (NonTypeTemplateParmDecl *NTTP
2806 = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2807 NTTPType = NTTP->getType();
2808 if (NTTPType->isDependentType()) {
2809 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2810 Builder.data(), Builder.size());
2811 NTTPType = SubstType(NTTPType,
2812 MultiLevelTemplateArgumentList(TemplateArgs),
2813 NTTP->getLocation(),
2814 NTTP->getDeclName());
2815 if (NTTPType.isNull()) {
2816 Info.Param = makeTemplateParameter(Param);
2817 // FIXME: These template arguments are temporary. Free them!
2818 Info.reset(TemplateArgumentList::CreateCopy(Context,
2821 return TDK_SubstitutionFailure;
2826 if (ConvertDeducedTemplateArgument(*this, Param, Deduced[I],
2827 FunctionTemplate, NTTPType, 0, Info,
2829 Info.Param = makeTemplateParameter(Param);
2830 // FIXME: These template arguments are temporary. Free them!
2831 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2833 return TDK_SubstitutionFailure;
2839 // C++0x [temp.arg.explicit]p3:
2840 // A trailing template parameter pack (14.5.3) not otherwise deduced will
2841 // be deduced to an empty sequence of template arguments.
2842 // FIXME: Where did the word "trailing" come from?
2843 if (Param->isTemplateParameterPack()) {
2844 // We may have had explicitly-specified template arguments for this
2845 // template parameter pack. If so, our empty deduction extends the
2846 // explicitly-specified set (C++0x [temp.arg.explicit]p9).
2847 const TemplateArgument *ExplicitArgs;
2848 unsigned NumExplicitArgs;
2849 if (CurrentInstantiationScope &&
2850 CurrentInstantiationScope->getPartiallySubstitutedPack(&ExplicitArgs,
2853 Builder.push_back(TemplateArgument(ExplicitArgs, NumExplicitArgs));
2855 // Forget the partially-substituted pack; it's substitution is now
2857 CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2859 Builder.push_back(TemplateArgument::getEmptyPack());
2864 // Substitute into the default template argument, if available.
2865 bool HasDefaultArg = false;
2866 TemplateArgumentLoc DefArg
2867 = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate,
2868 FunctionTemplate->getLocation(),
2869 FunctionTemplate->getSourceRange().getEnd(),
2871 Builder, HasDefaultArg);
2873 // If there was no default argument, deduction is incomplete.
2874 if (DefArg.getArgument().isNull()) {
2875 Info.Param = makeTemplateParameter(
2876 const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2877 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2879 if (PartialOverloading) break;
2881 return HasDefaultArg ? TDK_SubstitutionFailure : TDK_Incomplete;
2884 // Check whether we can actually use the default argument.
2885 if (CheckTemplateArgument(Param, DefArg,
2887 FunctionTemplate->getLocation(),
2888 FunctionTemplate->getSourceRange().getEnd(),
2891 Info.Param = makeTemplateParameter(
2892 const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2893 // FIXME: These template arguments are temporary. Free them!
2894 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2896 return TDK_SubstitutionFailure;
2899 // If we get here, we successfully used the default template argument.
2902 // Form the template argument list from the deduced template arguments.
2903 TemplateArgumentList *DeducedArgumentList
2904 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
2905 Info.reset(DeducedArgumentList);
2907 // Substitute the deduced template arguments into the function template
2908 // declaration to produce the function template specialization.
2909 DeclContext *Owner = FunctionTemplate->getDeclContext();
2910 if (FunctionTemplate->getFriendObjectKind())
2911 Owner = FunctionTemplate->getLexicalDeclContext();
2912 Specialization = cast_or_null<FunctionDecl>(
2913 SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner,
2914 MultiLevelTemplateArgumentList(*DeducedArgumentList)));
2915 if (!Specialization || Specialization->isInvalidDecl())
2916 return TDK_SubstitutionFailure;
2918 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() ==
2919 FunctionTemplate->getCanonicalDecl());
2921 // If the template argument list is owned by the function template
2922 // specialization, release it.
2923 if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList &&
2924 !Trap.hasErrorOccurred())
2927 // There may have been an error that did not prevent us from constructing a
2928 // declaration. Mark the declaration invalid and return with a substitution
2930 if (Trap.hasErrorOccurred()) {
2931 Specialization->setInvalidDecl(true);
2932 return TDK_SubstitutionFailure;
2935 if (OriginalCallArgs) {
2936 // C++ [temp.deduct.call]p4:
2937 // In general, the deduction process attempts to find template argument
2938 // values that will make the deduced A identical to A (after the type A
2939 // is transformed as described above). [...]
2940 for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; ++I) {
2941 OriginalCallArg OriginalArg = (*OriginalCallArgs)[I];
2942 unsigned ParamIdx = OriginalArg.ArgIdx;
2944 if (ParamIdx >= Specialization->getNumParams())
2947 QualType DeducedA = Specialization->getParamDecl(ParamIdx)->getType();
2948 if (CheckOriginalCallArgDeduction(*this, OriginalArg, DeducedA))
2949 return Sema::TDK_SubstitutionFailure;
2953 // If we suppressed any diagnostics while performing template argument
2954 // deduction, and if we haven't already instantiated this declaration,
2955 // keep track of these diagnostics. They'll be emitted if this specialization
2956 // is actually used.
2957 if (Info.diag_begin() != Info.diag_end()) {
2958 SuppressedDiagnosticsMap::iterator
2959 Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl());
2960 if (Pos == SuppressedDiagnostics.end())
2961 SuppressedDiagnostics[Specialization->getCanonicalDecl()]
2962 .append(Info.diag_begin(), Info.diag_end());
2968 /// Gets the type of a function for template-argument-deducton
2969 /// purposes when it's considered as part of an overload set.
2970 static QualType GetTypeOfFunction(Sema &S, const OverloadExpr::FindResult &R,
2972 // We may need to deduce the return type of the function now.
2973 if (S.getLangOpts().CPlusPlus14 && Fn->getReturnType()->isUndeducedType() &&
2974 S.DeduceReturnType(Fn, R.Expression->getExprLoc(), /*Diagnose*/ false))
2977 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn))
2978 if (Method->isInstance()) {
2979 // An instance method that's referenced in a form that doesn't
2980 // look like a member pointer is just invalid.
2981 if (!R.HasFormOfMemberPointer) return QualType();
2983 return S.Context.getMemberPointerType(Fn->getType(),
2984 S.Context.getTypeDeclType(Method->getParent()).getTypePtr());
2987 if (!R.IsAddressOfOperand) return Fn->getType();
2988 return S.Context.getPointerType(Fn->getType());
2991 /// Apply the deduction rules for overload sets.
2993 /// \return the null type if this argument should be treated as an
2994 /// undeduced context
2996 ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams,
2997 Expr *Arg, QualType ParamType,
2998 bool ParamWasReference) {
3000 OverloadExpr::FindResult R = OverloadExpr::find(Arg);
3002 OverloadExpr *Ovl = R.Expression;
3004 // C++0x [temp.deduct.call]p4
3006 if (ParamWasReference)
3007 TDF |= TDF_ParamWithReferenceType;
3008 if (R.IsAddressOfOperand)
3009 TDF |= TDF_IgnoreQualifiers;
3011 // C++0x [temp.deduct.call]p6:
3012 // When P is a function type, pointer to function type, or pointer
3013 // to member function type:
3015 if (!ParamType->isFunctionType() &&
3016 !ParamType->isFunctionPointerType() &&
3017 !ParamType->isMemberFunctionPointerType()) {
3018 if (Ovl->hasExplicitTemplateArgs()) {
3019 // But we can still look for an explicit specialization.
3020 if (FunctionDecl *ExplicitSpec
3021 = S.ResolveSingleFunctionTemplateSpecialization(Ovl))
3022 return GetTypeOfFunction(S, R, ExplicitSpec);
3028 // Gather the explicit template arguments, if any.
3029 TemplateArgumentListInfo ExplicitTemplateArgs;
3030 if (Ovl->hasExplicitTemplateArgs())
3031 Ovl->getExplicitTemplateArgs().copyInto(ExplicitTemplateArgs);
3033 for (UnresolvedSetIterator I = Ovl->decls_begin(),
3034 E = Ovl->decls_end(); I != E; ++I) {
3035 NamedDecl *D = (*I)->getUnderlyingDecl();
3037 if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) {
3038 // - If the argument is an overload set containing one or more
3039 // function templates, the parameter is treated as a
3040 // non-deduced context.
3041 if (!Ovl->hasExplicitTemplateArgs())
3044 // Otherwise, see if we can resolve a function type
3045 FunctionDecl *Specialization = nullptr;
3046 TemplateDeductionInfo Info(Ovl->getNameLoc());
3047 if (S.DeduceTemplateArguments(FunTmpl, &ExplicitTemplateArgs,
3048 Specialization, Info))
3054 FunctionDecl *Fn = cast<FunctionDecl>(D);
3055 QualType ArgType = GetTypeOfFunction(S, R, Fn);
3056 if (ArgType.isNull()) continue;
3058 // Function-to-pointer conversion.
3059 if (!ParamWasReference && ParamType->isPointerType() &&
3060 ArgType->isFunctionType())
3061 ArgType = S.Context.getPointerType(ArgType);
3063 // - If the argument is an overload set (not containing function
3064 // templates), trial argument deduction is attempted using each
3065 // of the members of the set. If deduction succeeds for only one
3066 // of the overload set members, that member is used as the
3067 // argument value for the deduction. If deduction succeeds for
3068 // more than one member of the overload set the parameter is
3069 // treated as a non-deduced context.
3071 // We do all of this in a fresh context per C++0x [temp.deduct.type]p2:
3072 // Type deduction is done independently for each P/A pair, and
3073 // the deduced template argument values are then combined.
3074 // So we do not reject deductions which were made elsewhere.
3075 SmallVector<DeducedTemplateArgument, 8>
3076 Deduced(TemplateParams->size());
3077 TemplateDeductionInfo Info(Ovl->getNameLoc());
3078 Sema::TemplateDeductionResult Result
3079 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3080 ArgType, Info, Deduced, TDF);
3081 if (Result) continue;
3082 if (!Match.isNull()) return QualType();
3089 /// \brief Perform the adjustments to the parameter and argument types
3090 /// described in C++ [temp.deduct.call].
3092 /// \returns true if the caller should not attempt to perform any template
3093 /// argument deduction based on this P/A pair because the argument is an
3094 /// overloaded function set that could not be resolved.
3095 static bool AdjustFunctionParmAndArgTypesForDeduction(Sema &S,
3096 TemplateParameterList *TemplateParams,
3097 QualType &ParamType,
3101 // C++0x [temp.deduct.call]p3:
3102 // If P is a cv-qualified type, the top level cv-qualifiers of P's type
3103 // are ignored for type deduction.
3104 if (ParamType.hasQualifiers())
3105 ParamType = ParamType.getUnqualifiedType();
3107 // [...] If P is a reference type, the type referred to by P is
3108 // used for type deduction.
3109 const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>();
3111 ParamType = ParamRefType->getPointeeType();
3113 // Overload sets usually make this parameter an undeduced context,
3114 // but there are sometimes special circumstances. Typically
3115 // involving a template-id-expr.
3116 if (ArgType == S.Context.OverloadTy) {
3117 ArgType = ResolveOverloadForDeduction(S, TemplateParams,
3119 ParamRefType != nullptr);
3120 if (ArgType.isNull())
3125 // If the argument has incomplete array type, try to complete its type.
3126 if (ArgType->isIncompleteArrayType() && !S.RequireCompleteExprType(Arg, 0))
3127 ArgType = Arg->getType();
3129 // C++0x [temp.deduct.call]p3:
3130 // If P is an rvalue reference to a cv-unqualified template
3131 // parameter and the argument is an lvalue, the type "lvalue
3132 // reference to A" is used in place of A for type deduction.
3133 if (ParamRefType->isRValueReferenceType() &&
3134 !ParamType.getQualifiers() &&
3135 isa<TemplateTypeParmType>(ParamType) &&
3137 ArgType = S.Context.getLValueReferenceType(ArgType);
3139 // C++ [temp.deduct.call]p2:
3140 // If P is not a reference type:
3141 // - If A is an array type, the pointer type produced by the
3142 // array-to-pointer standard conversion (4.2) is used in place of
3143 // A for type deduction; otherwise,
3144 if (ArgType->isArrayType())
3145 ArgType = S.Context.getArrayDecayedType(ArgType);
3146 // - If A is a function type, the pointer type produced by the
3147 // function-to-pointer standard conversion (4.3) is used in place
3148 // of A for type deduction; otherwise,
3149 else if (ArgType->isFunctionType())
3150 ArgType = S.Context.getPointerType(ArgType);
3152 // - If A is a cv-qualified type, the top level cv-qualifiers of A's
3153 // type are ignored for type deduction.
3154 ArgType = ArgType.getUnqualifiedType();
3158 // C++0x [temp.deduct.call]p4:
3159 // In general, the deduction process attempts to find template argument
3160 // values that will make the deduced A identical to A (after the type A
3161 // is transformed as described above). [...]
3162 TDF = TDF_SkipNonDependent;
3164 // - If the original P is a reference type, the deduced A (i.e., the
3165 // type referred to by the reference) can be more cv-qualified than
3166 // the transformed A.
3168 TDF |= TDF_ParamWithReferenceType;
3169 // - The transformed A can be another pointer or pointer to member
3170 // type that can be converted to the deduced A via a qualification
3171 // conversion (4.4).
3172 if (ArgType->isPointerType() || ArgType->isMemberPointerType() ||
3173 ArgType->isObjCObjectPointerType())
3174 TDF |= TDF_IgnoreQualifiers;
3175 // - If P is a class and P has the form simple-template-id, then the
3176 // transformed A can be a derived class of the deduced A. Likewise,
3177 // if P is a pointer to a class of the form simple-template-id, the
3178 // transformed A can be a pointer to a derived class pointed to by
3180 if (isSimpleTemplateIdType(ParamType) ||
3181 (isa<PointerType>(ParamType) &&
3182 isSimpleTemplateIdType(
3183 ParamType->getAs<PointerType>()->getPointeeType())))
3184 TDF |= TDF_DerivedClass;
3190 hasDeducibleTemplateParameters(Sema &S, FunctionTemplateDecl *FunctionTemplate,
3193 static Sema::TemplateDeductionResult DeduceTemplateArgumentByListElement(
3194 Sema &S, TemplateParameterList *TemplateParams, QualType ParamType,
3195 Expr *Arg, TemplateDeductionInfo &Info,
3196 SmallVectorImpl<DeducedTemplateArgument> &Deduced, unsigned TDF);
3198 /// \brief Attempt template argument deduction from an initializer list
3199 /// deemed to be an argument in a function call.
3201 DeduceFromInitializerList(Sema &S, TemplateParameterList *TemplateParams,
3202 QualType AdjustedParamType, InitListExpr *ILE,
3203 TemplateDeductionInfo &Info,
3204 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3205 unsigned TDF, Sema::TemplateDeductionResult &Result) {
3206 // If the argument is an initializer list then the parameter is an undeduced
3207 // context, unless the parameter type is (reference to cv)
3208 // std::initializer_list<P'>, in which case deduction is done for each element
3209 // of the initializer list as-if it were an argument in a function call, and
3210 // the result is the deduced type if it's the same for all elements.
3212 if (!S.isStdInitializerList(AdjustedParamType, &X))
3215 Result = Sema::TDK_Success;
3217 // Recurse down into the init list.
3218 for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) {
3219 if ((Result = DeduceTemplateArgumentByListElement(
3220 S, TemplateParams, X, ILE->getInit(i), Info, Deduced, TDF)))
3227 /// \brief Perform template argument deduction by matching a parameter type
3228 /// against a single expression, where the expression is an element of
3229 /// an initializer list that was originally matched against a parameter
3230 /// of type \c initializer_list\<ParamType\>.
3231 static Sema::TemplateDeductionResult
3232 DeduceTemplateArgumentByListElement(Sema &S,
3233 TemplateParameterList *TemplateParams,
3234 QualType ParamType, Expr *Arg,
3235 TemplateDeductionInfo &Info,
3236 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3238 // Handle the case where an init list contains another init list as the
3240 if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) {
3241 Sema::TemplateDeductionResult Result;
3242 if (!DeduceFromInitializerList(S, TemplateParams,
3243 ParamType.getNonReferenceType(), ILE, Info,
3244 Deduced, TDF, Result))
3245 return Sema::TDK_Success; // Just ignore this expression.
3250 // For all other cases, just match by type.
3251 QualType ArgType = Arg->getType();
3252 if (AdjustFunctionParmAndArgTypesForDeduction(S, TemplateParams, ParamType,
3253 ArgType, Arg, TDF)) {
3254 Info.Expression = Arg;
3255 return Sema::TDK_FailedOverloadResolution;
3257 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3258 ArgType, Info, Deduced, TDF);
3261 /// \brief Perform template argument deduction from a function call
3262 /// (C++ [temp.deduct.call]).
3264 /// \param FunctionTemplate the function template for which we are performing
3265 /// template argument deduction.
3267 /// \param ExplicitTemplateArgs the explicit template arguments provided
3270 /// \param Args the function call arguments
3272 /// \param Specialization if template argument deduction was successful,
3273 /// this will be set to the function template specialization produced by
3274 /// template argument deduction.
3276 /// \param Info the argument will be updated to provide additional information
3277 /// about template argument deduction.
3279 /// \returns the result of template argument deduction.
3280 Sema::TemplateDeductionResult Sema::DeduceTemplateArguments(
3281 FunctionTemplateDecl *FunctionTemplate,
3282 TemplateArgumentListInfo *ExplicitTemplateArgs, ArrayRef<Expr *> Args,
3283 FunctionDecl *&Specialization, TemplateDeductionInfo &Info,
3284 bool PartialOverloading) {
3285 if (FunctionTemplate->isInvalidDecl())
3288 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3289 unsigned NumParams = Function->getNumParams();
3291 // C++ [temp.deduct.call]p1:
3292 // Template argument deduction is done by comparing each function template
3293 // parameter type (call it P) with the type of the corresponding argument
3294 // of the call (call it A) as described below.
3295 unsigned CheckArgs = Args.size();
3296 if (Args.size() < Function->getMinRequiredArguments() && !PartialOverloading)
3297 return TDK_TooFewArguments;
3298 else if (TooManyArguments(NumParams, Args.size(), PartialOverloading)) {
3299 const FunctionProtoType *Proto
3300 = Function->getType()->getAs<FunctionProtoType>();
3301 if (Proto->isTemplateVariadic())
3303 else if (Proto->isVariadic())
3304 CheckArgs = NumParams;
3306 return TDK_TooManyArguments;
3309 // The types of the parameters from which we will perform template argument
3311 LocalInstantiationScope InstScope(*this);
3312 TemplateParameterList *TemplateParams
3313 = FunctionTemplate->getTemplateParameters();
3314 SmallVector<DeducedTemplateArgument, 4> Deduced;
3315 SmallVector<QualType, 4> ParamTypes;
3316 unsigned NumExplicitlySpecified = 0;
3317 if (ExplicitTemplateArgs) {
3318 TemplateDeductionResult Result =
3319 SubstituteExplicitTemplateArguments(FunctionTemplate,
3320 *ExplicitTemplateArgs,
3328 NumExplicitlySpecified = Deduced.size();
3330 // Just fill in the parameter types from the function declaration.
3331 for (unsigned I = 0; I != NumParams; ++I)
3332 ParamTypes.push_back(Function->getParamDecl(I)->getType());
3335 // Deduce template arguments from the function parameters.
3336 Deduced.resize(TemplateParams->size());
3337 unsigned ArgIdx = 0;
3338 SmallVector<OriginalCallArg, 4> OriginalCallArgs;
3339 for (unsigned ParamIdx = 0, NumParamTypes = ParamTypes.size();
3340 ParamIdx != NumParamTypes; ++ParamIdx) {
3341 QualType OrigParamType = ParamTypes[ParamIdx];
3342 QualType ParamType = OrigParamType;
3344 const PackExpansionType *ParamExpansion
3345 = dyn_cast<PackExpansionType>(ParamType);
3346 if (!ParamExpansion) {
3347 // Simple case: matching a function parameter to a function argument.
3348 if (ArgIdx >= CheckArgs)
3351 Expr *Arg = Args[ArgIdx++];
3352 QualType ArgType = Arg->getType();
3355 if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
3356 ParamType, ArgType, Arg,
3360 // If we have nothing to deduce, we're done.
3361 if (!hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
3364 // If the argument is an initializer list ...
3365 if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) {
3366 TemplateDeductionResult Result;
3367 // Removing references was already done.
3368 if (!DeduceFromInitializerList(*this, TemplateParams, ParamType, ILE,
3369 Info, Deduced, TDF, Result))
3374 // Don't track the argument type, since an initializer list has none.
3378 // Keep track of the argument type and corresponding parameter index,
3379 // so we can check for compatibility between the deduced A and A.
3380 OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx-1,
3383 if (TemplateDeductionResult Result
3384 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3386 Info, Deduced, TDF))
3392 // C++0x [temp.deduct.call]p1:
3393 // For a function parameter pack that occurs at the end of the
3394 // parameter-declaration-list, the type A of each remaining argument of
3395 // the call is compared with the type P of the declarator-id of the
3396 // function parameter pack. Each comparison deduces template arguments
3397 // for subsequent positions in the template parameter packs expanded by
3398 // the function parameter pack. For a function parameter pack that does
3399 // not occur at the end of the parameter-declaration-list, the type of
3400 // the parameter pack is a non-deduced context.
3401 if (ParamIdx + 1 < NumParamTypes)
3404 QualType ParamPattern = ParamExpansion->getPattern();
3405 PackDeductionScope PackScope(*this, TemplateParams, Deduced, Info,
3408 bool HasAnyArguments = false;
3409 for (; ArgIdx < Args.size(); ++ArgIdx) {
3410 HasAnyArguments = true;
3412 QualType OrigParamType = ParamPattern;
3413 ParamType = OrigParamType;
3414 Expr *Arg = Args[ArgIdx];
3415 QualType ArgType = Arg->getType();
3418 if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
3419 ParamType, ArgType, Arg,
3421 // We can't actually perform any deduction for this argument, so stop
3422 // deduction at this point.
3427 // As above, initializer lists need special handling.
3428 if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) {
3429 TemplateDeductionResult Result;
3430 if (!DeduceFromInitializerList(*this, TemplateParams, ParamType, ILE,
3431 Info, Deduced, TDF, Result)) {
3440 // Keep track of the argument type and corresponding argument index,
3441 // so we can check for compatibility between the deduced A and A.
3442 if (hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
3443 OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx,
3446 if (TemplateDeductionResult Result
3447 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3448 ParamType, ArgType, Info,
3453 PackScope.nextPackElement();
3456 // Build argument packs for each of the parameter packs expanded by this
3458 if (auto Result = PackScope.finish(HasAnyArguments))
3461 // After we've matching against a parameter pack, we're done.
3465 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
3466 NumExplicitlySpecified, Specialization,
3467 Info, &OriginalCallArgs,
3468 PartialOverloading);
3471 QualType Sema::adjustCCAndNoReturn(QualType ArgFunctionType,
3472 QualType FunctionType) {
3473 if (ArgFunctionType.isNull())
3474 return ArgFunctionType;
3476 const FunctionProtoType *FunctionTypeP =
3477 FunctionType->castAs<FunctionProtoType>();
3478 CallingConv CC = FunctionTypeP->getCallConv();
3479 bool NoReturn = FunctionTypeP->getNoReturnAttr();
3480 const FunctionProtoType *ArgFunctionTypeP =
3481 ArgFunctionType->getAs<FunctionProtoType>();
3482 if (ArgFunctionTypeP->getCallConv() == CC &&
3483 ArgFunctionTypeP->getNoReturnAttr() == NoReturn)
3484 return ArgFunctionType;
3486 FunctionType::ExtInfo EI = ArgFunctionTypeP->getExtInfo().withCallingConv(CC);
3487 EI = EI.withNoReturn(NoReturn);
3489 cast<FunctionProtoType>(Context.adjustFunctionType(ArgFunctionTypeP, EI));
3490 return QualType(ArgFunctionTypeP, 0);
3493 /// \brief Deduce template arguments when taking the address of a function
3494 /// template (C++ [temp.deduct.funcaddr]) or matching a specialization to
3497 /// \param FunctionTemplate the function template for which we are performing
3498 /// template argument deduction.
3500 /// \param ExplicitTemplateArgs the explicitly-specified template
3503 /// \param ArgFunctionType the function type that will be used as the
3504 /// "argument" type (A) when performing template argument deduction from the
3505 /// function template's function type. This type may be NULL, if there is no
3506 /// argument type to compare against, in C++0x [temp.arg.explicit]p3.
3508 /// \param Specialization if template argument deduction was successful,
3509 /// this will be set to the function template specialization produced by
3510 /// template argument deduction.
3512 /// \param Info the argument will be updated to provide additional information
3513 /// about template argument deduction.
3515 /// \returns the result of template argument deduction.
3516 Sema::TemplateDeductionResult
3517 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3518 TemplateArgumentListInfo *ExplicitTemplateArgs,
3519 QualType ArgFunctionType,
3520 FunctionDecl *&Specialization,
3521 TemplateDeductionInfo &Info,
3522 bool InOverloadResolution) {
3523 if (FunctionTemplate->isInvalidDecl())
3526 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3527 TemplateParameterList *TemplateParams
3528 = FunctionTemplate->getTemplateParameters();
3529 QualType FunctionType = Function->getType();
3530 if (!InOverloadResolution)
3531 ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, FunctionType);
3533 // Substitute any explicit template arguments.
3534 LocalInstantiationScope InstScope(*this);
3535 SmallVector<DeducedTemplateArgument, 4> Deduced;
3536 unsigned NumExplicitlySpecified = 0;
3537 SmallVector<QualType, 4> ParamTypes;
3538 if (ExplicitTemplateArgs) {
3539 if (TemplateDeductionResult Result
3540 = SubstituteExplicitTemplateArguments(FunctionTemplate,
3541 *ExplicitTemplateArgs,
3542 Deduced, ParamTypes,
3543 &FunctionType, Info))
3546 NumExplicitlySpecified = Deduced.size();
3549 // Unevaluated SFINAE context.
3550 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
3551 SFINAETrap Trap(*this);
3553 Deduced.resize(TemplateParams->size());
3555 // If the function has a deduced return type, substitute it for a dependent
3556 // type so that we treat it as a non-deduced context in what follows.
3557 bool HasDeducedReturnType = false;
3558 if (getLangOpts().CPlusPlus14 && InOverloadResolution &&
3559 Function->getReturnType()->getContainedAutoType()) {
3560 FunctionType = SubstAutoType(FunctionType, Context.DependentTy);
3561 HasDeducedReturnType = true;
3564 if (!ArgFunctionType.isNull()) {
3565 unsigned TDF = TDF_TopLevelParameterTypeList;
3566 if (InOverloadResolution) TDF |= TDF_InOverloadResolution;
3567 // Deduce template arguments from the function type.
3568 if (TemplateDeductionResult Result
3569 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3570 FunctionType, ArgFunctionType,
3571 Info, Deduced, TDF))
3575 if (TemplateDeductionResult Result
3576 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
3577 NumExplicitlySpecified,
3578 Specialization, Info))
3581 // If the function has a deduced return type, deduce it now, so we can check
3582 // that the deduced function type matches the requested type.
3583 if (HasDeducedReturnType &&
3584 Specialization->getReturnType()->isUndeducedType() &&
3585 DeduceReturnType(Specialization, Info.getLocation(), false))
3586 return TDK_MiscellaneousDeductionFailure;
3588 // If the requested function type does not match the actual type of the
3589 // specialization with respect to arguments of compatible pointer to function
3590 // types, template argument deduction fails.
3591 if (!ArgFunctionType.isNull()) {
3592 if (InOverloadResolution && !isSameOrCompatibleFunctionType(
3593 Context.getCanonicalType(Specialization->getType()),
3594 Context.getCanonicalType(ArgFunctionType)))
3595 return TDK_MiscellaneousDeductionFailure;
3596 else if(!InOverloadResolution &&
3597 !Context.hasSameType(Specialization->getType(), ArgFunctionType))
3598 return TDK_MiscellaneousDeductionFailure;
3604 /// \brief Given a function declaration (e.g. a generic lambda conversion
3605 /// function) that contains an 'auto' in its result type, substitute it
3606 /// with TypeToReplaceAutoWith. Be careful to pass in the type you want
3607 /// to replace 'auto' with and not the actual result type you want
3608 /// to set the function to.
3610 SubstAutoWithinFunctionReturnType(FunctionDecl *F,
3611 QualType TypeToReplaceAutoWith, Sema &S) {
3612 assert(!TypeToReplaceAutoWith->getContainedAutoType());
3613 QualType AutoResultType = F->getReturnType();
3614 assert(AutoResultType->getContainedAutoType());
3615 QualType DeducedResultType = S.SubstAutoType(AutoResultType,
3616 TypeToReplaceAutoWith);
3617 S.Context.adjustDeducedFunctionResultType(F, DeducedResultType);
3620 /// \brief Given a specialized conversion operator of a generic lambda
3621 /// create the corresponding specializations of the call operator and
3622 /// the static-invoker. If the return type of the call operator is auto,
3623 /// deduce its return type and check if that matches the
3624 /// return type of the destination function ptr.
3626 static inline Sema::TemplateDeductionResult
3627 SpecializeCorrespondingLambdaCallOperatorAndInvoker(
3628 CXXConversionDecl *ConversionSpecialized,
3629 SmallVectorImpl<DeducedTemplateArgument> &DeducedArguments,
3630 QualType ReturnTypeOfDestFunctionPtr,
3631 TemplateDeductionInfo &TDInfo,
3634 CXXRecordDecl *LambdaClass = ConversionSpecialized->getParent();
3635 assert(LambdaClass && LambdaClass->isGenericLambda());
3637 CXXMethodDecl *CallOpGeneric = LambdaClass->getLambdaCallOperator();
3638 QualType CallOpResultType = CallOpGeneric->getReturnType();
3639 const bool GenericLambdaCallOperatorHasDeducedReturnType =
3640 CallOpResultType->getContainedAutoType();
3642 FunctionTemplateDecl *CallOpTemplate =
3643 CallOpGeneric->getDescribedFunctionTemplate();
3645 FunctionDecl *CallOpSpecialized = nullptr;
3646 // Use the deduced arguments of the conversion function, to specialize our
3647 // generic lambda's call operator.
3648 if (Sema::TemplateDeductionResult Result
3649 = S.FinishTemplateArgumentDeduction(CallOpTemplate,
3651 0, CallOpSpecialized, TDInfo))
3654 // If we need to deduce the return type, do so (instantiates the callop).
3655 if (GenericLambdaCallOperatorHasDeducedReturnType &&
3656 CallOpSpecialized->getReturnType()->isUndeducedType())
3657 S.DeduceReturnType(CallOpSpecialized,
3658 CallOpSpecialized->getPointOfInstantiation(),
3661 // Check to see if the return type of the destination ptr-to-function
3662 // matches the return type of the call operator.
3663 if (!S.Context.hasSameType(CallOpSpecialized->getReturnType(),
3664 ReturnTypeOfDestFunctionPtr))
3665 return Sema::TDK_NonDeducedMismatch;
3666 // Since we have succeeded in matching the source and destination
3667 // ptr-to-functions (now including return type), and have successfully
3668 // specialized our corresponding call operator, we are ready to
3669 // specialize the static invoker with the deduced arguments of our
3671 FunctionDecl *InvokerSpecialized = nullptr;
3672 FunctionTemplateDecl *InvokerTemplate = LambdaClass->
3673 getLambdaStaticInvoker()->getDescribedFunctionTemplate();
3676 Sema::TemplateDeductionResult LLVM_ATTRIBUTE_UNUSED Result =
3678 S.FinishTemplateArgumentDeduction(InvokerTemplate, DeducedArguments, 0,
3679 InvokerSpecialized, TDInfo);
3680 assert(Result == Sema::TDK_Success &&
3681 "If the call operator succeeded so should the invoker!");
3682 // Set the result type to match the corresponding call operator
3683 // specialization's result type.
3684 if (GenericLambdaCallOperatorHasDeducedReturnType &&
3685 InvokerSpecialized->getReturnType()->isUndeducedType()) {
3686 // Be sure to get the type to replace 'auto' with and not
3687 // the full result type of the call op specialization
3688 // to substitute into the 'auto' of the invoker and conversion
3691 // int* (*fp)(int*) = [](auto* a) -> auto* { return a; };
3692 // We don't want to subst 'int*' into 'auto' to get int**.
3694 QualType TypeToReplaceAutoWith = CallOpSpecialized->getReturnType()
3695 ->getContainedAutoType()
3697 SubstAutoWithinFunctionReturnType(InvokerSpecialized,
3698 TypeToReplaceAutoWith, S);
3699 SubstAutoWithinFunctionReturnType(ConversionSpecialized,
3700 TypeToReplaceAutoWith, S);
3703 // Ensure that static invoker doesn't have a const qualifier.
3704 // FIXME: When creating the InvokerTemplate in SemaLambda.cpp
3705 // do not use the CallOperator's TypeSourceInfo which allows
3706 // the const qualifier to leak through.
3707 const FunctionProtoType *InvokerFPT = InvokerSpecialized->
3708 getType().getTypePtr()->castAs<FunctionProtoType>();
3709 FunctionProtoType::ExtProtoInfo EPI = InvokerFPT->getExtProtoInfo();
3711 InvokerSpecialized->setType(S.Context.getFunctionType(
3712 InvokerFPT->getReturnType(), InvokerFPT->getParamTypes(), EPI));
3713 return Sema::TDK_Success;
3715 /// \brief Deduce template arguments for a templated conversion
3716 /// function (C++ [temp.deduct.conv]) and, if successful, produce a
3717 /// conversion function template specialization.
3718 Sema::TemplateDeductionResult
3719 Sema::DeduceTemplateArguments(FunctionTemplateDecl *ConversionTemplate,
3721 CXXConversionDecl *&Specialization,
3722 TemplateDeductionInfo &Info) {
3723 if (ConversionTemplate->isInvalidDecl())
3726 CXXConversionDecl *ConversionGeneric
3727 = cast<CXXConversionDecl>(ConversionTemplate->getTemplatedDecl());
3729 QualType FromType = ConversionGeneric->getConversionType();
3731 // Canonicalize the types for deduction.
3732 QualType P = Context.getCanonicalType(FromType);
3733 QualType A = Context.getCanonicalType(ToType);
3735 // C++0x [temp.deduct.conv]p2:
3736 // If P is a reference type, the type referred to by P is used for
3738 if (const ReferenceType *PRef = P->getAs<ReferenceType>())
3739 P = PRef->getPointeeType();
3741 // C++0x [temp.deduct.conv]p4:
3742 // [...] If A is a reference type, the type referred to by A is used
3743 // for type deduction.
3744 if (const ReferenceType *ARef = A->getAs<ReferenceType>())
3745 A = ARef->getPointeeType().getUnqualifiedType();
3746 // C++ [temp.deduct.conv]p3:
3748 // If A is not a reference type:
3750 assert(!A->isReferenceType() && "Reference types were handled above");
3752 // - If P is an array type, the pointer type produced by the
3753 // array-to-pointer standard conversion (4.2) is used in place
3754 // of P for type deduction; otherwise,
3755 if (P->isArrayType())
3756 P = Context.getArrayDecayedType(P);
3757 // - If P is a function type, the pointer type produced by the
3758 // function-to-pointer standard conversion (4.3) is used in
3759 // place of P for type deduction; otherwise,
3760 else if (P->isFunctionType())
3761 P = Context.getPointerType(P);
3762 // - If P is a cv-qualified type, the top level cv-qualifiers of
3763 // P's type are ignored for type deduction.
3765 P = P.getUnqualifiedType();
3767 // C++0x [temp.deduct.conv]p4:
3768 // If A is a cv-qualified type, the top level cv-qualifiers of A's
3769 // type are ignored for type deduction. If A is a reference type, the type
3770 // referred to by A is used for type deduction.
3771 A = A.getUnqualifiedType();
3774 // Unevaluated SFINAE context.
3775 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
3776 SFINAETrap Trap(*this);
3778 // C++ [temp.deduct.conv]p1:
3779 // Template argument deduction is done by comparing the return
3780 // type of the template conversion function (call it P) with the
3781 // type that is required as the result of the conversion (call it
3782 // A) as described in 14.8.2.4.
3783 TemplateParameterList *TemplateParams
3784 = ConversionTemplate->getTemplateParameters();
3785 SmallVector<DeducedTemplateArgument, 4> Deduced;
3786 Deduced.resize(TemplateParams->size());
3788 // C++0x [temp.deduct.conv]p4:
3789 // In general, the deduction process attempts to find template
3790 // argument values that will make the deduced A identical to
3791 // A. However, there are two cases that allow a difference:
3793 // - If the original A is a reference type, A can be more
3794 // cv-qualified than the deduced A (i.e., the type referred to
3795 // by the reference)
3796 if (ToType->isReferenceType())
3797 TDF |= TDF_ParamWithReferenceType;
3798 // - The deduced A can be another pointer or pointer to member
3799 // type that can be converted to A via a qualification
3802 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when
3803 // both P and A are pointers or member pointers. In this case, we
3804 // just ignore cv-qualifiers completely).
3805 if ((P->isPointerType() && A->isPointerType()) ||
3806 (P->isMemberPointerType() && A->isMemberPointerType()))
3807 TDF |= TDF_IgnoreQualifiers;
3808 if (TemplateDeductionResult Result
3809 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3810 P, A, Info, Deduced, TDF))
3813 // Create an Instantiation Scope for finalizing the operator.
3814 LocalInstantiationScope InstScope(*this);
3815 // Finish template argument deduction.
3816 FunctionDecl *ConversionSpecialized = nullptr;
3817 TemplateDeductionResult Result
3818 = FinishTemplateArgumentDeduction(ConversionTemplate, Deduced, 0,
3819 ConversionSpecialized, Info);
3820 Specialization = cast_or_null<CXXConversionDecl>(ConversionSpecialized);
3822 // If the conversion operator is being invoked on a lambda closure to convert
3823 // to a ptr-to-function, use the deduced arguments from the conversion
3824 // function to specialize the corresponding call operator.
3825 // e.g., int (*fp)(int) = [](auto a) { return a; };
3826 if (Result == TDK_Success && isLambdaConversionOperator(ConversionGeneric)) {
3828 // Get the return type of the destination ptr-to-function we are converting
3829 // to. This is necessary for matching the lambda call operator's return
3830 // type to that of the destination ptr-to-function's return type.
3831 assert(A->isPointerType() &&
3832 "Can only convert from lambda to ptr-to-function");
3833 const FunctionType *ToFunType =
3834 A->getPointeeType().getTypePtr()->getAs<FunctionType>();
3835 const QualType DestFunctionPtrReturnType = ToFunType->getReturnType();
3837 // Create the corresponding specializations of the call operator and
3838 // the static-invoker; and if the return type is auto,
3839 // deduce the return type and check if it matches the
3840 // DestFunctionPtrReturnType.
3842 // auto L = [](auto a) { return f(a); };
3843 // int (*fp)(int) = L;
3844 // char (*fp2)(int) = L; <-- Not OK.
3846 Result = SpecializeCorrespondingLambdaCallOperatorAndInvoker(
3847 Specialization, Deduced, DestFunctionPtrReturnType,
3853 /// \brief Deduce template arguments for a function template when there is
3854 /// nothing to deduce against (C++0x [temp.arg.explicit]p3).
3856 /// \param FunctionTemplate the function template for which we are performing
3857 /// template argument deduction.
3859 /// \param ExplicitTemplateArgs the explicitly-specified template
3862 /// \param Specialization if template argument deduction was successful,
3863 /// this will be set to the function template specialization produced by
3864 /// template argument deduction.
3866 /// \param Info the argument will be updated to provide additional information
3867 /// about template argument deduction.
3869 /// \returns the result of template argument deduction.
3870 Sema::TemplateDeductionResult
3871 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3872 TemplateArgumentListInfo *ExplicitTemplateArgs,
3873 FunctionDecl *&Specialization,
3874 TemplateDeductionInfo &Info,
3875 bool InOverloadResolution) {
3876 return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs,
3877 QualType(), Specialization, Info,
3878 InOverloadResolution);
3882 /// Substitute the 'auto' type specifier within a type for a given replacement
3884 class SubstituteAutoTransform :
3885 public TreeTransform<SubstituteAutoTransform> {
3886 QualType Replacement;
3888 SubstituteAutoTransform(Sema &SemaRef, QualType Replacement)
3889 : TreeTransform<SubstituteAutoTransform>(SemaRef),
3890 Replacement(Replacement) {}
3892 QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) {
3893 // If we're building the type pattern to deduce against, don't wrap the
3894 // substituted type in an AutoType. Certain template deduction rules
3895 // apply only when a template type parameter appears directly (and not if
3896 // the parameter is found through desugaring). For instance:
3897 // auto &&lref = lvalue;
3898 // must transform into "rvalue reference to T" not "rvalue reference to
3899 // auto type deduced as T" in order for [temp.deduct.call]p3 to apply.
3900 if (!Replacement.isNull() && isa<TemplateTypeParmType>(Replacement)) {
3901 QualType Result = Replacement;
3902 TemplateTypeParmTypeLoc NewTL =
3903 TLB.push<TemplateTypeParmTypeLoc>(Result);
3904 NewTL.setNameLoc(TL.getNameLoc());
3908 !Replacement.isNull() && Replacement->isDependentType();
3910 SemaRef.Context.getAutoType(Dependent ? QualType() : Replacement,
3911 TL.getTypePtr()->isDecltypeAuto(),
3913 AutoTypeLoc NewTL = TLB.push<AutoTypeLoc>(Result);
3914 NewTL.setNameLoc(TL.getNameLoc());
3919 ExprResult TransformLambdaExpr(LambdaExpr *E) {
3920 // Lambdas never need to be transformed.
3924 QualType Apply(TypeLoc TL) {
3925 // Create some scratch storage for the transformed type locations.
3926 // FIXME: We're just going to throw this information away. Don't build it.
3928 TLB.reserve(TL.getFullDataSize());
3929 return TransformType(TLB, TL);
3934 Sema::DeduceAutoResult
3935 Sema::DeduceAutoType(TypeSourceInfo *Type, Expr *&Init, QualType &Result) {
3936 return DeduceAutoType(Type->getTypeLoc(), Init, Result);
3939 /// \brief Deduce the type for an auto type-specifier (C++11 [dcl.spec.auto]p6)
3941 /// \param Type the type pattern using the auto type-specifier.
3942 /// \param Init the initializer for the variable whose type is to be deduced.
3943 /// \param Result if type deduction was successful, this will be set to the
3945 Sema::DeduceAutoResult
3946 Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result) {
3947 if (Init->getType()->isNonOverloadPlaceholderType()) {
3948 ExprResult NonPlaceholder = CheckPlaceholderExpr(Init);
3949 if (NonPlaceholder.isInvalid())
3950 return DAR_FailedAlreadyDiagnosed;
3951 Init = NonPlaceholder.get();
3954 if (Init->isTypeDependent() || Type.getType()->isDependentType()) {
3955 Result = SubstituteAutoTransform(*this, Context.DependentTy).Apply(Type);
3956 assert(!Result.isNull() && "substituting DependentTy can't fail");
3957 return DAR_Succeeded;
3960 // If this is a 'decltype(auto)' specifier, do the decltype dance.
3961 // Since 'decltype(auto)' can only occur at the top of the type, we
3962 // don't need to go digging for it.
3963 if (const AutoType *AT = Type.getType()->getAs<AutoType>()) {
3964 if (AT->isDecltypeAuto()) {
3965 if (isa<InitListExpr>(Init)) {
3966 Diag(Init->getLocStart(), diag::err_decltype_auto_initializer_list);
3967 return DAR_FailedAlreadyDiagnosed;
3970 QualType Deduced = BuildDecltypeType(Init, Init->getLocStart(), false);
3971 if (Deduced.isNull())
3972 return DAR_FailedAlreadyDiagnosed;
3973 // FIXME: Support a non-canonical deduced type for 'auto'.
3974 Deduced = Context.getCanonicalType(Deduced);
3975 Result = SubstituteAutoTransform(*this, Deduced).Apply(Type);
3976 if (Result.isNull())
3977 return DAR_FailedAlreadyDiagnosed;
3978 return DAR_Succeeded;
3982 SourceLocation Loc = Init->getExprLoc();
3984 LocalInstantiationScope InstScope(*this);
3986 // Build template<class TemplParam> void Func(FuncParam);
3987 TemplateTypeParmDecl *TemplParam =
3988 TemplateTypeParmDecl::Create(Context, nullptr, SourceLocation(), Loc, 0, 0,
3989 nullptr, false, false);
3990 QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0);
3991 NamedDecl *TemplParamPtr = TemplParam;
3992 FixedSizeTemplateParameterList<1> TemplateParams(Loc, Loc, &TemplParamPtr,
3995 QualType FuncParam = SubstituteAutoTransform(*this, TemplArg).Apply(Type);
3996 assert(!FuncParam.isNull() &&
3997 "substituting template parameter for 'auto' failed");
3999 // Deduce type of TemplParam in Func(Init)
4000 SmallVector<DeducedTemplateArgument, 1> Deduced;
4002 QualType InitType = Init->getType();
4005 TemplateDeductionInfo Info(Loc);
4007 InitListExpr *InitList = dyn_cast<InitListExpr>(Init);
4009 for (unsigned i = 0, e = InitList->getNumInits(); i < e; ++i) {
4010 if (DeduceTemplateArgumentByListElement(*this, &TemplateParams,
4012 InitList->getInit(i),
4013 Info, Deduced, TDF))
4017 if (AdjustFunctionParmAndArgTypesForDeduction(*this, &TemplateParams,
4018 FuncParam, InitType, Init,
4022 if (DeduceTemplateArgumentsByTypeMatch(*this, &TemplateParams, FuncParam,
4023 InitType, Info, Deduced, TDF))
4027 if (Deduced[0].getKind() != TemplateArgument::Type)
4030 QualType DeducedType = Deduced[0].getAsType();
4033 DeducedType = BuildStdInitializerList(DeducedType, Loc);
4034 if (DeducedType.isNull())
4035 return DAR_FailedAlreadyDiagnosed;
4038 Result = SubstituteAutoTransform(*this, DeducedType).Apply(Type);
4039 if (Result.isNull())
4040 return DAR_FailedAlreadyDiagnosed;
4042 // Check that the deduced argument type is compatible with the original
4043 // argument type per C++ [temp.deduct.call]p4.
4044 if (!InitList && !Result.isNull() &&
4045 CheckOriginalCallArgDeduction(*this,
4046 Sema::OriginalCallArg(FuncParam,0,InitType),
4048 Result = QualType();
4052 return DAR_Succeeded;
4055 QualType Sema::SubstAutoType(QualType TypeWithAuto,
4056 QualType TypeToReplaceAuto) {
4057 return SubstituteAutoTransform(*this, TypeToReplaceAuto).
4058 TransformType(TypeWithAuto);
4061 TypeSourceInfo* Sema::SubstAutoTypeSourceInfo(TypeSourceInfo *TypeWithAuto,
4062 QualType TypeToReplaceAuto) {
4063 return SubstituteAutoTransform(*this, TypeToReplaceAuto).
4064 TransformType(TypeWithAuto);
4067 void Sema::DiagnoseAutoDeductionFailure(VarDecl *VDecl, Expr *Init) {
4068 if (isa<InitListExpr>(Init))
4069 Diag(VDecl->getLocation(),
4070 VDecl->isInitCapture()
4071 ? diag::err_init_capture_deduction_failure_from_init_list
4072 : diag::err_auto_var_deduction_failure_from_init_list)
4073 << VDecl->getDeclName() << VDecl->getType() << Init->getSourceRange();
4075 Diag(VDecl->getLocation(),
4076 VDecl->isInitCapture() ? diag::err_init_capture_deduction_failure
4077 : diag::err_auto_var_deduction_failure)
4078 << VDecl->getDeclName() << VDecl->getType() << Init->getType()
4079 << Init->getSourceRange();
4082 bool Sema::DeduceReturnType(FunctionDecl *FD, SourceLocation Loc,
4084 assert(FD->getReturnType()->isUndeducedType());
4086 if (FD->getTemplateInstantiationPattern())
4087 InstantiateFunctionDefinition(Loc, FD);
4089 bool StillUndeduced = FD->getReturnType()->isUndeducedType();
4090 if (StillUndeduced && Diagnose && !FD->isInvalidDecl()) {
4091 Diag(Loc, diag::err_auto_fn_used_before_defined) << FD;
4092 Diag(FD->getLocation(), diag::note_callee_decl) << FD;
4095 return StillUndeduced;
4099 MarkUsedTemplateParameters(ASTContext &Ctx, QualType T,
4102 llvm::SmallBitVector &Deduced);
4104 /// \brief If this is a non-static member function,
4106 AddImplicitObjectParameterType(ASTContext &Context,
4107 CXXMethodDecl *Method,
4108 SmallVectorImpl<QualType> &ArgTypes) {
4109 // C++11 [temp.func.order]p3:
4110 // [...] The new parameter is of type "reference to cv A," where cv are
4111 // the cv-qualifiers of the function template (if any) and A is
4112 // the class of which the function template is a member.
4114 // The standard doesn't say explicitly, but we pick the appropriate kind of
4115 // reference type based on [over.match.funcs]p4.
4116 QualType ArgTy = Context.getTypeDeclType(Method->getParent());
4117 ArgTy = Context.getQualifiedType(ArgTy,
4118 Qualifiers::fromCVRMask(Method->getTypeQualifiers()));
4119 if (Method->getRefQualifier() == RQ_RValue)
4120 ArgTy = Context.getRValueReferenceType(ArgTy);
4122 ArgTy = Context.getLValueReferenceType(ArgTy);
4123 ArgTypes.push_back(ArgTy);
4126 /// \brief Determine whether the function template \p FT1 is at least as
4127 /// specialized as \p FT2.
4128 static bool isAtLeastAsSpecializedAs(Sema &S,
4130 FunctionTemplateDecl *FT1,
4131 FunctionTemplateDecl *FT2,
4132 TemplatePartialOrderingContext TPOC,
4133 unsigned NumCallArguments1) {
4134 FunctionDecl *FD1 = FT1->getTemplatedDecl();
4135 FunctionDecl *FD2 = FT2->getTemplatedDecl();
4136 const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>();
4137 const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>();
4139 assert(Proto1 && Proto2 && "Function templates must have prototypes");
4140 TemplateParameterList *TemplateParams = FT2->getTemplateParameters();
4141 SmallVector<DeducedTemplateArgument, 4> Deduced;
4142 Deduced.resize(TemplateParams->size());
4144 // C++0x [temp.deduct.partial]p3:
4145 // The types used to determine the ordering depend on the context in which
4146 // the partial ordering is done:
4147 TemplateDeductionInfo Info(Loc);
4148 SmallVector<QualType, 4> Args2;
4151 // - In the context of a function call, the function parameter types are
4153 CXXMethodDecl *Method1 = dyn_cast<CXXMethodDecl>(FD1);
4154 CXXMethodDecl *Method2 = dyn_cast<CXXMethodDecl>(FD2);
4156 // C++11 [temp.func.order]p3:
4157 // [...] If only one of the function templates is a non-static
4158 // member, that function template is considered to have a new
4159 // first parameter inserted in its function parameter list. The
4160 // new parameter is of type "reference to cv A," where cv are
4161 // the cv-qualifiers of the function template (if any) and A is
4162 // the class of which the function template is a member.
4164 // Note that we interpret this to mean "if one of the function
4165 // templates is a non-static member and the other is a non-member";
4166 // otherwise, the ordering rules for static functions against non-static
4167 // functions don't make any sense.
4169 // C++98/03 doesn't have this provision but we've extended DR532 to cover
4170 // it as wording was broken prior to it.
4171 SmallVector<QualType, 4> Args1;
4173 unsigned NumComparedArguments = NumCallArguments1;
4175 if (!Method2 && Method1 && !Method1->isStatic()) {
4176 // Compare 'this' from Method1 against first parameter from Method2.
4177 AddImplicitObjectParameterType(S.Context, Method1, Args1);
4178 ++NumComparedArguments;
4179 } else if (!Method1 && Method2 && !Method2->isStatic()) {
4180 // Compare 'this' from Method2 against first parameter from Method1.
4181 AddImplicitObjectParameterType(S.Context, Method2, Args2);
4184 Args1.insert(Args1.end(), Proto1->param_type_begin(),
4185 Proto1->param_type_end());
4186 Args2.insert(Args2.end(), Proto2->param_type_begin(),
4187 Proto2->param_type_end());
4189 // C++ [temp.func.order]p5:
4190 // The presence of unused ellipsis and default arguments has no effect on
4191 // the partial ordering of function templates.
4192 if (Args1.size() > NumComparedArguments)
4193 Args1.resize(NumComparedArguments);
4194 if (Args2.size() > NumComparedArguments)
4195 Args2.resize(NumComparedArguments);
4196 if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(),
4197 Args1.data(), Args1.size(), Info, Deduced,
4198 TDF_None, /*PartialOrdering=*/true))
4204 case TPOC_Conversion:
4205 // - In the context of a call to a conversion operator, the return types
4206 // of the conversion function templates are used.
4207 if (DeduceTemplateArgumentsByTypeMatch(
4208 S, TemplateParams, Proto2->getReturnType(), Proto1->getReturnType(),
4209 Info, Deduced, TDF_None,
4210 /*PartialOrdering=*/true))
4215 // - In other contexts (14.6.6.2) the function template's function type
4217 if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
4218 FD2->getType(), FD1->getType(),
4219 Info, Deduced, TDF_None,
4220 /*PartialOrdering=*/true))
4225 // C++0x [temp.deduct.partial]p11:
4226 // In most cases, all template parameters must have values in order for
4227 // deduction to succeed, but for partial ordering purposes a template
4228 // parameter may remain without a value provided it is not used in the
4229 // types being used for partial ordering. [ Note: a template parameter used
4230 // in a non-deduced context is considered used. -end note]
4231 unsigned ArgIdx = 0, NumArgs = Deduced.size();
4232 for (; ArgIdx != NumArgs; ++ArgIdx)
4233 if (Deduced[ArgIdx].isNull())
4236 if (ArgIdx == NumArgs) {
4237 // All template arguments were deduced. FT1 is at least as specialized
4242 // Figure out which template parameters were used.
4243 llvm::SmallBitVector UsedParameters(TemplateParams->size());
4246 for (unsigned I = 0, N = Args2.size(); I != N; ++I)
4247 ::MarkUsedTemplateParameters(S.Context, Args2[I], false,
4248 TemplateParams->getDepth(),
4252 case TPOC_Conversion:
4253 ::MarkUsedTemplateParameters(S.Context, Proto2->getReturnType(), false,
4254 TemplateParams->getDepth(), UsedParameters);
4258 ::MarkUsedTemplateParameters(S.Context, FD2->getType(), false,
4259 TemplateParams->getDepth(),
4264 for (; ArgIdx != NumArgs; ++ArgIdx)
4265 // If this argument had no value deduced but was used in one of the types
4266 // used for partial ordering, then deduction fails.
4267 if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx])
4273 /// \brief Determine whether this a function template whose parameter-type-list
4274 /// ends with a function parameter pack.
4275 static bool isVariadicFunctionTemplate(FunctionTemplateDecl *FunTmpl) {
4276 FunctionDecl *Function = FunTmpl->getTemplatedDecl();
4277 unsigned NumParams = Function->getNumParams();
4281 ParmVarDecl *Last = Function->getParamDecl(NumParams - 1);
4282 if (!Last->isParameterPack())
4285 // Make sure that no previous parameter is a parameter pack.
4286 while (--NumParams > 0) {
4287 if (Function->getParamDecl(NumParams - 1)->isParameterPack())
4294 /// \brief Returns the more specialized function template according
4295 /// to the rules of function template partial ordering (C++ [temp.func.order]).
4297 /// \param FT1 the first function template
4299 /// \param FT2 the second function template
4301 /// \param TPOC the context in which we are performing partial ordering of
4302 /// function templates.
4304 /// \param NumCallArguments1 The number of arguments in the call to FT1, used
4305 /// only when \c TPOC is \c TPOC_Call.
4307 /// \param NumCallArguments2 The number of arguments in the call to FT2, used
4308 /// only when \c TPOC is \c TPOC_Call.
4310 /// \returns the more specialized function template. If neither
4311 /// template is more specialized, returns NULL.
4312 FunctionTemplateDecl *
4313 Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1,
4314 FunctionTemplateDecl *FT2,
4316 TemplatePartialOrderingContext TPOC,
4317 unsigned NumCallArguments1,
4318 unsigned NumCallArguments2) {
4319 bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC,
4321 bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC,
4324 if (Better1 != Better2) // We have a clear winner
4325 return Better1 ? FT1 : FT2;
4327 if (!Better1 && !Better2) // Neither is better than the other
4330 // FIXME: This mimics what GCC implements, but doesn't match up with the
4331 // proposed resolution for core issue 692. This area needs to be sorted out,
4332 // but for now we attempt to maintain compatibility.
4333 bool Variadic1 = isVariadicFunctionTemplate(FT1);
4334 bool Variadic2 = isVariadicFunctionTemplate(FT2);
4335 if (Variadic1 != Variadic2)
4336 return Variadic1? FT2 : FT1;
4341 /// \brief Determine if the two templates are equivalent.
4342 static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) {
4349 return T1->getCanonicalDecl() == T2->getCanonicalDecl();
4352 /// \brief Retrieve the most specialized of the given function template
4353 /// specializations.
4355 /// \param SpecBegin the start iterator of the function template
4356 /// specializations that we will be comparing.
4358 /// \param SpecEnd the end iterator of the function template
4359 /// specializations, paired with \p SpecBegin.
4361 /// \param Loc the location where the ambiguity or no-specializations
4362 /// diagnostic should occur.
4364 /// \param NoneDiag partial diagnostic used to diagnose cases where there are
4365 /// no matching candidates.
4367 /// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one
4370 /// \param CandidateDiag partial diagnostic used for each function template
4371 /// specialization that is a candidate in the ambiguous ordering. One parameter
4372 /// in this diagnostic should be unbound, which will correspond to the string
4373 /// describing the template arguments for the function template specialization.
4375 /// \returns the most specialized function template specialization, if
4376 /// found. Otherwise, returns SpecEnd.
4377 UnresolvedSetIterator Sema::getMostSpecialized(
4378 UnresolvedSetIterator SpecBegin, UnresolvedSetIterator SpecEnd,
4379 TemplateSpecCandidateSet &FailedCandidates,
4380 SourceLocation Loc, const PartialDiagnostic &NoneDiag,
4381 const PartialDiagnostic &AmbigDiag, const PartialDiagnostic &CandidateDiag,
4382 bool Complain, QualType TargetType) {
4383 if (SpecBegin == SpecEnd) {
4385 Diag(Loc, NoneDiag);
4386 FailedCandidates.NoteCandidates(*this, Loc);
4391 if (SpecBegin + 1 == SpecEnd)
4394 // Find the function template that is better than all of the templates it
4395 // has been compared to.
4396 UnresolvedSetIterator Best = SpecBegin;
4397 FunctionTemplateDecl *BestTemplate
4398 = cast<FunctionDecl>(*Best)->getPrimaryTemplate();
4399 assert(BestTemplate && "Not a function template specialization?");
4400 for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) {
4401 FunctionTemplateDecl *Challenger
4402 = cast<FunctionDecl>(*I)->getPrimaryTemplate();
4403 assert(Challenger && "Not a function template specialization?");
4404 if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
4405 Loc, TPOC_Other, 0, 0),
4408 BestTemplate = Challenger;
4412 // Make sure that the "best" function template is more specialized than all
4414 bool Ambiguous = false;
4415 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
4416 FunctionTemplateDecl *Challenger
4417 = cast<FunctionDecl>(*I)->getPrimaryTemplate();
4419 !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
4420 Loc, TPOC_Other, 0, 0),
4428 // We found an answer. Return it.
4432 // Diagnose the ambiguity.
4434 Diag(Loc, AmbigDiag);
4436 // FIXME: Can we order the candidates in some sane way?
4437 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
4438 PartialDiagnostic PD = CandidateDiag;
4439 PD << getTemplateArgumentBindingsText(
4440 cast<FunctionDecl>(*I)->getPrimaryTemplate()->getTemplateParameters(),
4441 *cast<FunctionDecl>(*I)->getTemplateSpecializationArgs());
4442 if (!TargetType.isNull())
4443 HandleFunctionTypeMismatch(PD, cast<FunctionDecl>(*I)->getType(),
4445 Diag((*I)->getLocation(), PD);
4452 /// \brief Returns the more specialized class template partial specialization
4453 /// according to the rules of partial ordering of class template partial
4454 /// specializations (C++ [temp.class.order]).
4456 /// \param PS1 the first class template partial specialization
4458 /// \param PS2 the second class template partial specialization
4460 /// \returns the more specialized class template partial specialization. If
4461 /// neither partial specialization is more specialized, returns NULL.
4462 ClassTemplatePartialSpecializationDecl *
4463 Sema::getMoreSpecializedPartialSpecialization(
4464 ClassTemplatePartialSpecializationDecl *PS1,
4465 ClassTemplatePartialSpecializationDecl *PS2,
4466 SourceLocation Loc) {
4467 // C++ [temp.class.order]p1:
4468 // For two class template partial specializations, the first is at least as
4469 // specialized as the second if, given the following rewrite to two
4470 // function templates, the first function template is at least as
4471 // specialized as the second according to the ordering rules for function
4472 // templates (14.6.6.2):
4473 // - the first function template has the same template parameters as the
4474 // first partial specialization and has a single function parameter
4475 // whose type is a class template specialization with the template
4476 // arguments of the first partial specialization, and
4477 // - the second function template has the same template parameters as the
4478 // second partial specialization and has a single function parameter
4479 // whose type is a class template specialization with the template
4480 // arguments of the second partial specialization.
4482 // Rather than synthesize function templates, we merely perform the
4483 // equivalent partial ordering by performing deduction directly on
4484 // the template arguments of the class template partial
4485 // specializations. This computation is slightly simpler than the
4486 // general problem of function template partial ordering, because
4487 // class template partial specializations are more constrained. We
4488 // know that every template parameter is deducible from the class
4489 // template partial specialization's template arguments, for
4491 SmallVector<DeducedTemplateArgument, 4> Deduced;
4492 TemplateDeductionInfo Info(Loc);
4494 QualType PT1 = PS1->getInjectedSpecializationType();
4495 QualType PT2 = PS2->getInjectedSpecializationType();
4497 // Determine whether PS1 is at least as specialized as PS2
4498 Deduced.resize(PS2->getTemplateParameters()->size());
4499 bool Better1 = !DeduceTemplateArgumentsByTypeMatch(*this,
4500 PS2->getTemplateParameters(),
4501 PT2, PT1, Info, Deduced, TDF_None,
4502 /*PartialOrdering=*/true);
4504 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),Deduced.end());
4505 InstantiatingTemplate Inst(*this, Loc, PS2, DeducedArgs, Info);
4506 Better1 = !::FinishTemplateArgumentDeduction(
4507 *this, PS2, PS1->getTemplateArgs(), Deduced, Info);
4510 // Determine whether PS2 is at least as specialized as PS1
4512 Deduced.resize(PS1->getTemplateParameters()->size());
4513 bool Better2 = !DeduceTemplateArgumentsByTypeMatch(
4514 *this, PS1->getTemplateParameters(), PT1, PT2, Info, Deduced, TDF_None,
4515 /*PartialOrdering=*/true);
4517 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),
4519 InstantiatingTemplate Inst(*this, Loc, PS1, DeducedArgs, Info);
4520 Better2 = !::FinishTemplateArgumentDeduction(
4521 *this, PS1, PS2->getTemplateArgs(), Deduced, Info);
4524 if (Better1 == Better2)
4527 return Better1 ? PS1 : PS2;
4530 /// TODO: Unify with ClassTemplatePartialSpecializationDecl version?
4531 /// May require unifying ClassTemplate(Partial)SpecializationDecl and
4532 /// VarTemplate(Partial)SpecializationDecl with a new data
4533 /// structure Template(Partial)SpecializationDecl, and
4534 /// using Template(Partial)SpecializationDecl as input type.
4535 VarTemplatePartialSpecializationDecl *
4536 Sema::getMoreSpecializedPartialSpecialization(
4537 VarTemplatePartialSpecializationDecl *PS1,
4538 VarTemplatePartialSpecializationDecl *PS2, SourceLocation Loc) {
4539 SmallVector<DeducedTemplateArgument, 4> Deduced;
4540 TemplateDeductionInfo Info(Loc);
4542 assert(PS1->getSpecializedTemplate() == PS2->getSpecializedTemplate() &&
4543 "the partial specializations being compared should specialize"
4544 " the same template.");
4545 TemplateName Name(PS1->getSpecializedTemplate());
4546 TemplateName CanonTemplate = Context.getCanonicalTemplateName(Name);
4547 QualType PT1 = Context.getTemplateSpecializationType(
4548 CanonTemplate, PS1->getTemplateArgs().data(),
4549 PS1->getTemplateArgs().size());
4550 QualType PT2 = Context.getTemplateSpecializationType(
4551 CanonTemplate, PS2->getTemplateArgs().data(),
4552 PS2->getTemplateArgs().size());
4554 // Determine whether PS1 is at least as specialized as PS2
4555 Deduced.resize(PS2->getTemplateParameters()->size());
4556 bool Better1 = !DeduceTemplateArgumentsByTypeMatch(
4557 *this, PS2->getTemplateParameters(), PT2, PT1, Info, Deduced, TDF_None,
4558 /*PartialOrdering=*/true);
4560 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),
4562 InstantiatingTemplate Inst(*this, Loc, PS2, DeducedArgs, Info);
4563 Better1 = !::FinishTemplateArgumentDeduction(*this, PS2,
4564 PS1->getTemplateArgs(),
4568 // Determine whether PS2 is at least as specialized as PS1
4570 Deduced.resize(PS1->getTemplateParameters()->size());
4571 bool Better2 = !DeduceTemplateArgumentsByTypeMatch(*this,
4572 PS1->getTemplateParameters(),
4573 PT1, PT2, Info, Deduced, TDF_None,
4574 /*PartialOrdering=*/true);
4576 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),Deduced.end());
4577 InstantiatingTemplate Inst(*this, Loc, PS1, DeducedArgs, Info);
4578 Better2 = !::FinishTemplateArgumentDeduction(*this, PS1,
4579 PS2->getTemplateArgs(),
4583 if (Better1 == Better2)
4586 return Better1? PS1 : PS2;
4590 MarkUsedTemplateParameters(ASTContext &Ctx,
4591 const TemplateArgument &TemplateArg,
4594 llvm::SmallBitVector &Used);
4596 /// \brief Mark the template parameters that are used by the given
4599 MarkUsedTemplateParameters(ASTContext &Ctx,
4603 llvm::SmallBitVector &Used) {
4604 // We can deduce from a pack expansion.
4605 if (const PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(E))
4606 E = Expansion->getPattern();
4608 // Skip through any implicit casts we added while type-checking, and any
4609 // substitutions performed by template alias expansion.
4611 if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E))
4612 E = ICE->getSubExpr();
4613 else if (const SubstNonTypeTemplateParmExpr *Subst =
4614 dyn_cast<SubstNonTypeTemplateParmExpr>(E))
4615 E = Subst->getReplacement();
4620 // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to
4621 // find other occurrences of template parameters.
4622 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E);
4626 const NonTypeTemplateParmDecl *NTTP
4627 = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
4631 if (NTTP->getDepth() == Depth)
4632 Used[NTTP->getIndex()] = true;
4635 /// \brief Mark the template parameters that are used by the given
4636 /// nested name specifier.
4638 MarkUsedTemplateParameters(ASTContext &Ctx,
4639 NestedNameSpecifier *NNS,
4642 llvm::SmallBitVector &Used) {
4646 MarkUsedTemplateParameters(Ctx, NNS->getPrefix(), OnlyDeduced, Depth,
4648 MarkUsedTemplateParameters(Ctx, QualType(NNS->getAsType(), 0),
4649 OnlyDeduced, Depth, Used);
4652 /// \brief Mark the template parameters that are used by the given
4655 MarkUsedTemplateParameters(ASTContext &Ctx,
4659 llvm::SmallBitVector &Used) {
4660 if (TemplateDecl *Template = Name.getAsTemplateDecl()) {
4661 if (TemplateTemplateParmDecl *TTP
4662 = dyn_cast<TemplateTemplateParmDecl>(Template)) {
4663 if (TTP->getDepth() == Depth)
4664 Used[TTP->getIndex()] = true;
4669 if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName())
4670 MarkUsedTemplateParameters(Ctx, QTN->getQualifier(), OnlyDeduced,
4672 if (DependentTemplateName *DTN = Name.getAsDependentTemplateName())
4673 MarkUsedTemplateParameters(Ctx, DTN->getQualifier(), OnlyDeduced,
4677 /// \brief Mark the template parameters that are used by the given
4680 MarkUsedTemplateParameters(ASTContext &Ctx, QualType T,
4683 llvm::SmallBitVector &Used) {
4687 // Non-dependent types have nothing deducible
4688 if (!T->isDependentType())
4691 T = Ctx.getCanonicalType(T);
4692 switch (T->getTypeClass()) {
4694 MarkUsedTemplateParameters(Ctx,
4695 cast<PointerType>(T)->getPointeeType(),
4701 case Type::BlockPointer:
4702 MarkUsedTemplateParameters(Ctx,
4703 cast<BlockPointerType>(T)->getPointeeType(),
4709 case Type::LValueReference:
4710 case Type::RValueReference:
4711 MarkUsedTemplateParameters(Ctx,
4712 cast<ReferenceType>(T)->getPointeeType(),
4718 case Type::MemberPointer: {
4719 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr());
4720 MarkUsedTemplateParameters(Ctx, MemPtr->getPointeeType(), OnlyDeduced,
4722 MarkUsedTemplateParameters(Ctx, QualType(MemPtr->getClass(), 0),
4723 OnlyDeduced, Depth, Used);
4727 case Type::DependentSizedArray:
4728 MarkUsedTemplateParameters(Ctx,
4729 cast<DependentSizedArrayType>(T)->getSizeExpr(),
4730 OnlyDeduced, Depth, Used);
4731 // Fall through to check the element type
4733 case Type::ConstantArray:
4734 case Type::IncompleteArray:
4735 MarkUsedTemplateParameters(Ctx,
4736 cast<ArrayType>(T)->getElementType(),
4737 OnlyDeduced, Depth, Used);
4741 case Type::ExtVector:
4742 MarkUsedTemplateParameters(Ctx,
4743 cast<VectorType>(T)->getElementType(),
4744 OnlyDeduced, Depth, Used);
4747 case Type::DependentSizedExtVector: {
4748 const DependentSizedExtVectorType *VecType
4749 = cast<DependentSizedExtVectorType>(T);
4750 MarkUsedTemplateParameters(Ctx, VecType->getElementType(), OnlyDeduced,
4752 MarkUsedTemplateParameters(Ctx, VecType->getSizeExpr(), OnlyDeduced,
4757 case Type::FunctionProto: {
4758 const FunctionProtoType *Proto = cast<FunctionProtoType>(T);
4759 MarkUsedTemplateParameters(Ctx, Proto->getReturnType(), OnlyDeduced, Depth,
4761 for (unsigned I = 0, N = Proto->getNumParams(); I != N; ++I)
4762 MarkUsedTemplateParameters(Ctx, Proto->getParamType(I), OnlyDeduced,
4767 case Type::TemplateTypeParm: {
4768 const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T);
4769 if (TTP->getDepth() == Depth)
4770 Used[TTP->getIndex()] = true;
4774 case Type::SubstTemplateTypeParmPack: {
4775 const SubstTemplateTypeParmPackType *Subst
4776 = cast<SubstTemplateTypeParmPackType>(T);
4777 MarkUsedTemplateParameters(Ctx,
4778 QualType(Subst->getReplacedParameter(), 0),
4779 OnlyDeduced, Depth, Used);
4780 MarkUsedTemplateParameters(Ctx, Subst->getArgumentPack(),
4781 OnlyDeduced, Depth, Used);
4785 case Type::InjectedClassName:
4786 T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType();
4789 case Type::TemplateSpecialization: {
4790 const TemplateSpecializationType *Spec
4791 = cast<TemplateSpecializationType>(T);
4792 MarkUsedTemplateParameters(Ctx, Spec->getTemplateName(), OnlyDeduced,
4795 // C++0x [temp.deduct.type]p9:
4796 // If the template argument list of P contains a pack expansion that is
4797 // not the last template argument, the entire template argument list is a
4798 // non-deduced context.
4800 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs()))
4803 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
4804 MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth,
4811 MarkUsedTemplateParameters(Ctx,
4812 cast<ComplexType>(T)->getElementType(),
4813 OnlyDeduced, Depth, Used);
4818 MarkUsedTemplateParameters(Ctx,
4819 cast<AtomicType>(T)->getValueType(),
4820 OnlyDeduced, Depth, Used);
4823 case Type::DependentName:
4825 MarkUsedTemplateParameters(Ctx,
4826 cast<DependentNameType>(T)->getQualifier(),
4827 OnlyDeduced, Depth, Used);
4830 case Type::DependentTemplateSpecialization: {
4831 const DependentTemplateSpecializationType *Spec
4832 = cast<DependentTemplateSpecializationType>(T);
4834 MarkUsedTemplateParameters(Ctx, Spec->getQualifier(),
4835 OnlyDeduced, Depth, Used);
4837 // C++0x [temp.deduct.type]p9:
4838 // If the template argument list of P contains a pack expansion that is not
4839 // the last template argument, the entire template argument list is a
4840 // non-deduced context.
4842 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs()))
4845 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
4846 MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth,
4853 MarkUsedTemplateParameters(Ctx,
4854 cast<TypeOfType>(T)->getUnderlyingType(),
4855 OnlyDeduced, Depth, Used);
4858 case Type::TypeOfExpr:
4860 MarkUsedTemplateParameters(Ctx,
4861 cast<TypeOfExprType>(T)->getUnderlyingExpr(),
4862 OnlyDeduced, Depth, Used);
4865 case Type::Decltype:
4867 MarkUsedTemplateParameters(Ctx,
4868 cast<DecltypeType>(T)->getUnderlyingExpr(),
4869 OnlyDeduced, Depth, Used);
4872 case Type::UnaryTransform:
4874 MarkUsedTemplateParameters(Ctx,
4875 cast<UnaryTransformType>(T)->getUnderlyingType(),
4876 OnlyDeduced, Depth, Used);
4879 case Type::PackExpansion:
4880 MarkUsedTemplateParameters(Ctx,
4881 cast<PackExpansionType>(T)->getPattern(),
4882 OnlyDeduced, Depth, Used);
4886 MarkUsedTemplateParameters(Ctx,
4887 cast<AutoType>(T)->getDeducedType(),
4888 OnlyDeduced, Depth, Used);
4890 // None of these types have any template parameters in them.
4892 case Type::VariableArray:
4893 case Type::FunctionNoProto:
4896 case Type::ObjCInterface:
4897 case Type::ObjCObject:
4898 case Type::ObjCObjectPointer:
4899 case Type::UnresolvedUsing:
4900 #define TYPE(Class, Base)
4901 #define ABSTRACT_TYPE(Class, Base)
4902 #define DEPENDENT_TYPE(Class, Base)
4903 #define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
4904 #include "clang/AST/TypeNodes.def"
4909 /// \brief Mark the template parameters that are used by this
4910 /// template argument.
4912 MarkUsedTemplateParameters(ASTContext &Ctx,
4913 const TemplateArgument &TemplateArg,
4916 llvm::SmallBitVector &Used) {
4917 switch (TemplateArg.getKind()) {
4918 case TemplateArgument::Null:
4919 case TemplateArgument::Integral:
4920 case TemplateArgument::Declaration:
4923 case TemplateArgument::NullPtr:
4924 MarkUsedTemplateParameters(Ctx, TemplateArg.getNullPtrType(), OnlyDeduced,
4928 case TemplateArgument::Type:
4929 MarkUsedTemplateParameters(Ctx, TemplateArg.getAsType(), OnlyDeduced,
4933 case TemplateArgument::Template:
4934 case TemplateArgument::TemplateExpansion:
4935 MarkUsedTemplateParameters(Ctx,
4936 TemplateArg.getAsTemplateOrTemplatePattern(),
4937 OnlyDeduced, Depth, Used);
4940 case TemplateArgument::Expression:
4941 MarkUsedTemplateParameters(Ctx, TemplateArg.getAsExpr(), OnlyDeduced,
4945 case TemplateArgument::Pack:
4946 for (const auto &P : TemplateArg.pack_elements())
4947 MarkUsedTemplateParameters(Ctx, P, OnlyDeduced, Depth, Used);
4952 /// \brief Mark which template parameters can be deduced from a given
4953 /// template argument list.
4955 /// \param TemplateArgs the template argument list from which template
4956 /// parameters will be deduced.
4958 /// \param Used a bit vector whose elements will be set to \c true
4959 /// to indicate when the corresponding template parameter will be
4962 Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs,
4963 bool OnlyDeduced, unsigned Depth,
4964 llvm::SmallBitVector &Used) {
4965 // C++0x [temp.deduct.type]p9:
4966 // If the template argument list of P contains a pack expansion that is not
4967 // the last template argument, the entire template argument list is a
4968 // non-deduced context.
4970 hasPackExpansionBeforeEnd(TemplateArgs.data(), TemplateArgs.size()))
4973 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I)
4974 ::MarkUsedTemplateParameters(Context, TemplateArgs[I], OnlyDeduced,
4978 /// \brief Marks all of the template parameters that will be deduced by a
4979 /// call to the given function template.
4980 void Sema::MarkDeducedTemplateParameters(
4981 ASTContext &Ctx, const FunctionTemplateDecl *FunctionTemplate,
4982 llvm::SmallBitVector &Deduced) {
4983 TemplateParameterList *TemplateParams
4984 = FunctionTemplate->getTemplateParameters();
4986 Deduced.resize(TemplateParams->size());
4988 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
4989 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I)
4990 ::MarkUsedTemplateParameters(Ctx, Function->getParamDecl(I)->getType(),
4991 true, TemplateParams->getDepth(), Deduced);
4994 bool hasDeducibleTemplateParameters(Sema &S,
4995 FunctionTemplateDecl *FunctionTemplate,
4997 if (!T->isDependentType())
5000 TemplateParameterList *TemplateParams
5001 = FunctionTemplate->getTemplateParameters();
5002 llvm::SmallBitVector Deduced(TemplateParams->size());
5003 ::MarkUsedTemplateParameters(S.Context, T, true, TemplateParams->getDepth(),
5006 return Deduced.any();