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(llvm::makeArrayRef(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.isCompleteType(Info.getLocation(), Arg))
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 QualType ParamPointeeType = MemPtrParam->getPointeeType();
1521 if (ParamPointeeType->isFunctionType())
1522 S.adjustMemberFunctionCC(ParamPointeeType, /*IsStatic=*/true,
1523 /*IsCtorOrDtor=*/false, Info.getLocation());
1524 QualType ArgPointeeType = MemPtrArg->getPointeeType();
1525 if (ArgPointeeType->isFunctionType())
1526 S.adjustMemberFunctionCC(ArgPointeeType, /*IsStatic=*/true,
1527 /*IsCtorOrDtor=*/false, Info.getLocation());
1529 if (Sema::TemplateDeductionResult Result
1530 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1534 TDF & TDF_IgnoreQualifiers))
1537 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1538 QualType(MemPtrParam->getClass(), 0),
1539 QualType(MemPtrArg->getClass(), 0),
1541 TDF & TDF_IgnoreQualifiers);
1544 // (clang extension)
1549 case Type::BlockPointer: {
1550 const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param);
1551 const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg);
1554 return Sema::TDK_NonDeducedMismatch;
1556 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1557 BlockPtrParam->getPointeeType(),
1558 BlockPtrArg->getPointeeType(),
1562 // (clang extension)
1564 // T __attribute__(((ext_vector_type(<integral constant>))))
1565 case Type::ExtVector: {
1566 const ExtVectorType *VectorParam = cast<ExtVectorType>(Param);
1567 if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1568 // Make sure that the vectors have the same number of elements.
1569 if (VectorParam->getNumElements() != VectorArg->getNumElements())
1570 return Sema::TDK_NonDeducedMismatch;
1572 // Perform deduction on the element types.
1573 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1574 VectorParam->getElementType(),
1575 VectorArg->getElementType(),
1576 Info, Deduced, TDF);
1579 if (const DependentSizedExtVectorType *VectorArg
1580 = dyn_cast<DependentSizedExtVectorType>(Arg)) {
1581 // We can't check the number of elements, since the argument has a
1582 // dependent number of elements. This can only occur during partial
1585 // Perform deduction on the element types.
1586 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1587 VectorParam->getElementType(),
1588 VectorArg->getElementType(),
1589 Info, Deduced, TDF);
1592 return Sema::TDK_NonDeducedMismatch;
1595 // (clang extension)
1597 // T __attribute__(((ext_vector_type(N))))
1598 case Type::DependentSizedExtVector: {
1599 const DependentSizedExtVectorType *VectorParam
1600 = cast<DependentSizedExtVectorType>(Param);
1602 if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1603 // Perform deduction on the element types.
1604 if (Sema::TemplateDeductionResult Result
1605 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1606 VectorParam->getElementType(),
1607 VectorArg->getElementType(),
1608 Info, Deduced, TDF))
1611 // Perform deduction on the vector size, if we can.
1612 NonTypeTemplateParmDecl *NTTP
1613 = getDeducedParameterFromExpr(VectorParam->getSizeExpr());
1615 return Sema::TDK_Success;
1617 llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
1618 ArgSize = VectorArg->getNumElements();
1619 return DeduceNonTypeTemplateArgument(S, NTTP, ArgSize, S.Context.IntTy,
1620 false, Info, Deduced);
1623 if (const DependentSizedExtVectorType *VectorArg
1624 = dyn_cast<DependentSizedExtVectorType>(Arg)) {
1625 // Perform deduction on the element types.
1626 if (Sema::TemplateDeductionResult Result
1627 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1628 VectorParam->getElementType(),
1629 VectorArg->getElementType(),
1630 Info, Deduced, TDF))
1633 // Perform deduction on the vector size, if we can.
1634 NonTypeTemplateParmDecl *NTTP
1635 = getDeducedParameterFromExpr(VectorParam->getSizeExpr());
1637 return Sema::TDK_Success;
1639 return DeduceNonTypeTemplateArgument(S, NTTP, VectorArg->getSizeExpr(),
1643 return Sema::TDK_NonDeducedMismatch;
1646 case Type::TypeOfExpr:
1648 case Type::DependentName:
1649 case Type::UnresolvedUsing:
1650 case Type::Decltype:
1651 case Type::UnaryTransform:
1653 case Type::DependentTemplateSpecialization:
1654 case Type::PackExpansion:
1656 // No template argument deduction for these types
1657 return Sema::TDK_Success;
1660 llvm_unreachable("Invalid Type Class!");
1663 static Sema::TemplateDeductionResult
1664 DeduceTemplateArguments(Sema &S,
1665 TemplateParameterList *TemplateParams,
1666 const TemplateArgument &Param,
1667 TemplateArgument Arg,
1668 TemplateDeductionInfo &Info,
1669 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1670 // If the template argument is a pack expansion, perform template argument
1671 // deduction against the pattern of that expansion. This only occurs during
1672 // partial ordering.
1673 if (Arg.isPackExpansion())
1674 Arg = Arg.getPackExpansionPattern();
1676 switch (Param.getKind()) {
1677 case TemplateArgument::Null:
1678 llvm_unreachable("Null template argument in parameter list");
1680 case TemplateArgument::Type:
1681 if (Arg.getKind() == TemplateArgument::Type)
1682 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1686 Info.FirstArg = Param;
1687 Info.SecondArg = Arg;
1688 return Sema::TDK_NonDeducedMismatch;
1690 case TemplateArgument::Template:
1691 if (Arg.getKind() == TemplateArgument::Template)
1692 return DeduceTemplateArguments(S, TemplateParams,
1693 Param.getAsTemplate(),
1694 Arg.getAsTemplate(), Info, Deduced);
1695 Info.FirstArg = Param;
1696 Info.SecondArg = Arg;
1697 return Sema::TDK_NonDeducedMismatch;
1699 case TemplateArgument::TemplateExpansion:
1700 llvm_unreachable("caller should handle pack expansions");
1702 case TemplateArgument::Declaration:
1703 if (Arg.getKind() == TemplateArgument::Declaration &&
1704 isSameDeclaration(Param.getAsDecl(), Arg.getAsDecl()))
1705 return Sema::TDK_Success;
1707 Info.FirstArg = Param;
1708 Info.SecondArg = Arg;
1709 return Sema::TDK_NonDeducedMismatch;
1711 case TemplateArgument::NullPtr:
1712 if (Arg.getKind() == TemplateArgument::NullPtr &&
1713 S.Context.hasSameType(Param.getNullPtrType(), Arg.getNullPtrType()))
1714 return Sema::TDK_Success;
1716 Info.FirstArg = Param;
1717 Info.SecondArg = Arg;
1718 return Sema::TDK_NonDeducedMismatch;
1720 case TemplateArgument::Integral:
1721 if (Arg.getKind() == TemplateArgument::Integral) {
1722 if (hasSameExtendedValue(Param.getAsIntegral(), Arg.getAsIntegral()))
1723 return Sema::TDK_Success;
1725 Info.FirstArg = Param;
1726 Info.SecondArg = Arg;
1727 return Sema::TDK_NonDeducedMismatch;
1730 if (Arg.getKind() == TemplateArgument::Expression) {
1731 Info.FirstArg = Param;
1732 Info.SecondArg = Arg;
1733 return Sema::TDK_NonDeducedMismatch;
1736 Info.FirstArg = Param;
1737 Info.SecondArg = Arg;
1738 return Sema::TDK_NonDeducedMismatch;
1740 case TemplateArgument::Expression: {
1741 if (NonTypeTemplateParmDecl *NTTP
1742 = getDeducedParameterFromExpr(Param.getAsExpr())) {
1743 if (Arg.getKind() == TemplateArgument::Integral)
1744 return DeduceNonTypeTemplateArgument(S, NTTP,
1745 Arg.getAsIntegral(),
1746 Arg.getIntegralType(),
1747 /*ArrayBound=*/false,
1749 if (Arg.getKind() == TemplateArgument::Expression)
1750 return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsExpr(),
1752 if (Arg.getKind() == TemplateArgument::Declaration)
1753 return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsDecl(),
1756 Info.FirstArg = Param;
1757 Info.SecondArg = Arg;
1758 return Sema::TDK_NonDeducedMismatch;
1761 // Can't deduce anything, but that's okay.
1762 return Sema::TDK_Success;
1764 case TemplateArgument::Pack:
1765 llvm_unreachable("Argument packs should be expanded by the caller!");
1768 llvm_unreachable("Invalid TemplateArgument Kind!");
1771 /// \brief Determine whether there is a template argument to be used for
1774 /// This routine "expands" argument packs in-place, overriding its input
1775 /// parameters so that \c Args[ArgIdx] will be the available template argument.
1777 /// \returns true if there is another template argument (which will be at
1778 /// \c Args[ArgIdx]), false otherwise.
1779 static bool hasTemplateArgumentForDeduction(const TemplateArgument *&Args,
1781 unsigned &NumArgs) {
1782 if (ArgIdx == NumArgs)
1785 const TemplateArgument &Arg = Args[ArgIdx];
1786 if (Arg.getKind() != TemplateArgument::Pack)
1789 assert(ArgIdx == NumArgs - 1 && "Pack not at the end of argument list?");
1790 Args = Arg.pack_begin();
1791 NumArgs = Arg.pack_size();
1793 return ArgIdx < NumArgs;
1796 /// \brief Determine whether the given set of template arguments has a pack
1797 /// expansion that is not the last template argument.
1798 static bool hasPackExpansionBeforeEnd(const TemplateArgument *Args,
1800 unsigned ArgIdx = 0;
1801 while (ArgIdx < NumArgs) {
1802 const TemplateArgument &Arg = Args[ArgIdx];
1804 // Unwrap argument packs.
1805 if (Args[ArgIdx].getKind() == TemplateArgument::Pack) {
1806 Args = Arg.pack_begin();
1807 NumArgs = Arg.pack_size();
1813 if (ArgIdx == NumArgs)
1816 if (Arg.isPackExpansion())
1823 static Sema::TemplateDeductionResult
1824 DeduceTemplateArguments(Sema &S,
1825 TemplateParameterList *TemplateParams,
1826 const TemplateArgument *Params, unsigned NumParams,
1827 const TemplateArgument *Args, unsigned NumArgs,
1828 TemplateDeductionInfo &Info,
1829 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1830 // C++0x [temp.deduct.type]p9:
1831 // If the template argument list of P contains a pack expansion that is not
1832 // the last template argument, the entire template argument list is a
1833 // non-deduced context.
1834 if (hasPackExpansionBeforeEnd(Params, NumParams))
1835 return Sema::TDK_Success;
1837 // C++0x [temp.deduct.type]p9:
1838 // If P has a form that contains <T> or <i>, then each argument Pi of the
1839 // respective template argument list P is compared with the corresponding
1840 // argument Ai of the corresponding template argument list of A.
1841 unsigned ArgIdx = 0, ParamIdx = 0;
1842 for (; hasTemplateArgumentForDeduction(Params, ParamIdx, NumParams);
1844 if (!Params[ParamIdx].isPackExpansion()) {
1845 // The simple case: deduce template arguments by matching Pi and Ai.
1847 // Check whether we have enough arguments.
1848 if (!hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs))
1849 return Sema::TDK_Success;
1851 if (Args[ArgIdx].isPackExpansion()) {
1852 // FIXME: We follow the logic of C++0x [temp.deduct.type]p22 here,
1853 // but applied to pack expansions that are template arguments.
1854 return Sema::TDK_MiscellaneousDeductionFailure;
1857 // Perform deduction for this Pi/Ai pair.
1858 if (Sema::TemplateDeductionResult Result
1859 = DeduceTemplateArguments(S, TemplateParams,
1860 Params[ParamIdx], Args[ArgIdx],
1864 // Move to the next argument.
1869 // The parameter is a pack expansion.
1871 // C++0x [temp.deduct.type]p9:
1872 // If Pi is a pack expansion, then the pattern of Pi is compared with
1873 // each remaining argument in the template argument list of A. Each
1874 // comparison deduces template arguments for subsequent positions in the
1875 // template parameter packs expanded by Pi.
1876 TemplateArgument Pattern = Params[ParamIdx].getPackExpansionPattern();
1878 // FIXME: If there are no remaining arguments, we can bail out early
1879 // and set any deduced parameter packs to an empty argument pack.
1880 // The latter part of this is a (minor) correctness issue.
1882 // Prepare to deduce the packs within the pattern.
1883 PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
1885 // Keep track of the deduced template arguments for each parameter pack
1886 // expanded by this pack expansion (the outer index) and for each
1887 // template argument (the inner SmallVectors).
1888 bool HasAnyArguments = false;
1889 for (; hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs); ++ArgIdx) {
1890 HasAnyArguments = true;
1892 // Deduce template arguments from the pattern.
1893 if (Sema::TemplateDeductionResult Result
1894 = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx],
1898 PackScope.nextPackElement();
1901 // Build argument packs for each of the parameter packs expanded by this
1903 if (auto Result = PackScope.finish(HasAnyArguments))
1907 return Sema::TDK_Success;
1910 static Sema::TemplateDeductionResult
1911 DeduceTemplateArguments(Sema &S,
1912 TemplateParameterList *TemplateParams,
1913 const TemplateArgumentList &ParamList,
1914 const TemplateArgumentList &ArgList,
1915 TemplateDeductionInfo &Info,
1916 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1917 return DeduceTemplateArguments(S, TemplateParams,
1918 ParamList.data(), ParamList.size(),
1919 ArgList.data(), ArgList.size(),
1923 /// \brief Determine whether two template arguments are the same.
1924 static bool isSameTemplateArg(ASTContext &Context,
1925 const TemplateArgument &X,
1926 const TemplateArgument &Y) {
1927 if (X.getKind() != Y.getKind())
1930 switch (X.getKind()) {
1931 case TemplateArgument::Null:
1932 llvm_unreachable("Comparing NULL template argument");
1934 case TemplateArgument::Type:
1935 return Context.getCanonicalType(X.getAsType()) ==
1936 Context.getCanonicalType(Y.getAsType());
1938 case TemplateArgument::Declaration:
1939 return isSameDeclaration(X.getAsDecl(), Y.getAsDecl());
1941 case TemplateArgument::NullPtr:
1942 return Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType());
1944 case TemplateArgument::Template:
1945 case TemplateArgument::TemplateExpansion:
1946 return Context.getCanonicalTemplateName(
1947 X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() ==
1948 Context.getCanonicalTemplateName(
1949 Y.getAsTemplateOrTemplatePattern()).getAsVoidPointer();
1951 case TemplateArgument::Integral:
1952 return X.getAsIntegral() == Y.getAsIntegral();
1954 case TemplateArgument::Expression: {
1955 llvm::FoldingSetNodeID XID, YID;
1956 X.getAsExpr()->Profile(XID, Context, true);
1957 Y.getAsExpr()->Profile(YID, Context, true);
1961 case TemplateArgument::Pack:
1962 if (X.pack_size() != Y.pack_size())
1965 for (TemplateArgument::pack_iterator XP = X.pack_begin(),
1966 XPEnd = X.pack_end(),
1967 YP = Y.pack_begin();
1968 XP != XPEnd; ++XP, ++YP)
1969 if (!isSameTemplateArg(Context, *XP, *YP))
1975 llvm_unreachable("Invalid TemplateArgument Kind!");
1978 /// \brief Allocate a TemplateArgumentLoc where all locations have
1979 /// been initialized to the given location.
1981 /// \param S The semantic analysis object.
1983 /// \param Arg The template argument we are producing template argument
1984 /// location information for.
1986 /// \param NTTPType For a declaration template argument, the type of
1987 /// the non-type template parameter that corresponds to this template
1990 /// \param Loc The source location to use for the resulting template
1992 static TemplateArgumentLoc
1993 getTrivialTemplateArgumentLoc(Sema &S,
1994 const TemplateArgument &Arg,
1996 SourceLocation Loc) {
1997 switch (Arg.getKind()) {
1998 case TemplateArgument::Null:
1999 llvm_unreachable("Can't get a NULL template argument here");
2001 case TemplateArgument::Type:
2002 return TemplateArgumentLoc(Arg,
2003 S.Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc));
2005 case TemplateArgument::Declaration: {
2007 = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2009 return TemplateArgumentLoc(TemplateArgument(E), E);
2012 case TemplateArgument::NullPtr: {
2014 = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2016 return TemplateArgumentLoc(TemplateArgument(NTTPType, /*isNullPtr*/true),
2020 case TemplateArgument::Integral: {
2022 = S.BuildExpressionFromIntegralTemplateArgument(Arg, Loc).getAs<Expr>();
2023 return TemplateArgumentLoc(TemplateArgument(E), E);
2026 case TemplateArgument::Template:
2027 case TemplateArgument::TemplateExpansion: {
2028 NestedNameSpecifierLocBuilder Builder;
2029 TemplateName Template = Arg.getAsTemplate();
2030 if (DependentTemplateName *DTN = Template.getAsDependentTemplateName())
2031 Builder.MakeTrivial(S.Context, DTN->getQualifier(), Loc);
2032 else if (QualifiedTemplateName *QTN =
2033 Template.getAsQualifiedTemplateName())
2034 Builder.MakeTrivial(S.Context, QTN->getQualifier(), Loc);
2036 if (Arg.getKind() == TemplateArgument::Template)
2037 return TemplateArgumentLoc(Arg,
2038 Builder.getWithLocInContext(S.Context),
2042 return TemplateArgumentLoc(Arg, Builder.getWithLocInContext(S.Context),
2046 case TemplateArgument::Expression:
2047 return TemplateArgumentLoc(Arg, Arg.getAsExpr());
2049 case TemplateArgument::Pack:
2050 return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo());
2053 llvm_unreachable("Invalid TemplateArgument Kind!");
2057 /// \brief Convert the given deduced template argument and add it to the set of
2058 /// fully-converted template arguments.
2060 ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param,
2061 DeducedTemplateArgument Arg,
2062 NamedDecl *Template,
2064 unsigned ArgumentPackIndex,
2065 TemplateDeductionInfo &Info,
2066 bool InFunctionTemplate,
2067 SmallVectorImpl<TemplateArgument> &Output) {
2068 if (Arg.getKind() == TemplateArgument::Pack) {
2069 // This is a template argument pack, so check each of its arguments against
2070 // the template parameter.
2071 SmallVector<TemplateArgument, 2> PackedArgsBuilder;
2072 for (const auto &P : Arg.pack_elements()) {
2073 // When converting the deduced template argument, append it to the
2074 // general output list. We need to do this so that the template argument
2075 // checking logic has all of the prior template arguments available.
2076 DeducedTemplateArgument InnerArg(P);
2077 InnerArg.setDeducedFromArrayBound(Arg.wasDeducedFromArrayBound());
2078 if (ConvertDeducedTemplateArgument(S, Param, InnerArg, Template,
2079 NTTPType, PackedArgsBuilder.size(),
2080 Info, InFunctionTemplate, Output))
2083 // Move the converted template argument into our argument pack.
2084 PackedArgsBuilder.push_back(Output.pop_back_val());
2087 // Create the resulting argument pack.
2089 TemplateArgument::CreatePackCopy(S.Context, PackedArgsBuilder));
2093 // Convert the deduced template argument into a template
2094 // argument that we can check, almost as if the user had written
2095 // the template argument explicitly.
2096 TemplateArgumentLoc ArgLoc = getTrivialTemplateArgumentLoc(S, Arg, NTTPType,
2097 Info.getLocation());
2099 // Check the template argument, converting it as necessary.
2100 return S.CheckTemplateArgument(Param, ArgLoc,
2102 Template->getLocation(),
2103 Template->getSourceRange().getEnd(),
2107 ? (Arg.wasDeducedFromArrayBound()
2108 ? Sema::CTAK_DeducedFromArrayBound
2109 : Sema::CTAK_Deduced)
2110 : Sema::CTAK_Specified);
2113 /// Complete template argument deduction for a class template partial
2115 static Sema::TemplateDeductionResult
2116 FinishTemplateArgumentDeduction(Sema &S,
2117 ClassTemplatePartialSpecializationDecl *Partial,
2118 const TemplateArgumentList &TemplateArgs,
2119 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2120 TemplateDeductionInfo &Info) {
2121 // Unevaluated SFINAE context.
2122 EnterExpressionEvaluationContext Unevaluated(S, Sema::Unevaluated);
2123 Sema::SFINAETrap Trap(S);
2125 Sema::ContextRAII SavedContext(S, Partial);
2127 // C++ [temp.deduct.type]p2:
2128 // [...] or if any template argument remains neither deduced nor
2129 // explicitly specified, template argument deduction fails.
2130 SmallVector<TemplateArgument, 4> Builder;
2131 TemplateParameterList *PartialParams = Partial->getTemplateParameters();
2132 for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) {
2133 NamedDecl *Param = PartialParams->getParam(I);
2134 if (Deduced[I].isNull()) {
2135 Info.Param = makeTemplateParameter(Param);
2136 return Sema::TDK_Incomplete;
2139 // We have deduced this argument, so it still needs to be
2140 // checked and converted.
2142 // First, for a non-type template parameter type that is
2143 // initialized by a declaration, we need the type of the
2144 // corresponding non-type template parameter.
2146 if (NonTypeTemplateParmDecl *NTTP
2147 = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2148 NTTPType = NTTP->getType();
2149 if (NTTPType->isDependentType()) {
2150 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2151 Builder.data(), Builder.size());
2152 NTTPType = S.SubstType(NTTPType,
2153 MultiLevelTemplateArgumentList(TemplateArgs),
2154 NTTP->getLocation(),
2155 NTTP->getDeclName());
2156 if (NTTPType.isNull()) {
2157 Info.Param = makeTemplateParameter(Param);
2158 // FIXME: These template arguments are temporary. Free them!
2159 Info.reset(TemplateArgumentList::CreateCopy(S.Context,
2162 return Sema::TDK_SubstitutionFailure;
2167 if (ConvertDeducedTemplateArgument(S, Param, Deduced[I],
2168 Partial, NTTPType, 0, Info, false,
2170 Info.Param = makeTemplateParameter(Param);
2171 // FIXME: These template arguments are temporary. Free them!
2172 Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2174 return Sema::TDK_SubstitutionFailure;
2178 // Form the template argument list from the deduced template arguments.
2179 TemplateArgumentList *DeducedArgumentList
2180 = TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2183 Info.reset(DeducedArgumentList);
2185 // Substitute the deduced template arguments into the template
2186 // arguments of the class template partial specialization, and
2187 // verify that the instantiated template arguments are both valid
2188 // and are equivalent to the template arguments originally provided
2189 // to the class template.
2190 LocalInstantiationScope InstScope(S);
2191 ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate();
2192 const ASTTemplateArgumentListInfo *PartialTemplArgInfo
2193 = Partial->getTemplateArgsAsWritten();
2194 const TemplateArgumentLoc *PartialTemplateArgs
2195 = PartialTemplArgInfo->getTemplateArgs();
2197 TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc,
2198 PartialTemplArgInfo->RAngleLoc);
2200 if (S.Subst(PartialTemplateArgs, PartialTemplArgInfo->NumTemplateArgs,
2201 InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
2202 unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2203 if (ParamIdx >= Partial->getTemplateParameters()->size())
2204 ParamIdx = Partial->getTemplateParameters()->size() - 1;
2207 = const_cast<NamedDecl *>(
2208 Partial->getTemplateParameters()->getParam(ParamIdx));
2209 Info.Param = makeTemplateParameter(Param);
2210 Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
2211 return Sema::TDK_SubstitutionFailure;
2214 SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2215 if (S.CheckTemplateArgumentList(ClassTemplate, Partial->getLocation(),
2216 InstArgs, false, ConvertedInstArgs))
2217 return Sema::TDK_SubstitutionFailure;
2219 TemplateParameterList *TemplateParams
2220 = ClassTemplate->getTemplateParameters();
2221 for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2222 TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2223 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2224 Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2225 Info.FirstArg = TemplateArgs[I];
2226 Info.SecondArg = InstArg;
2227 return Sema::TDK_NonDeducedMismatch;
2231 if (Trap.hasErrorOccurred())
2232 return Sema::TDK_SubstitutionFailure;
2234 return Sema::TDK_Success;
2237 /// \brief Perform template argument deduction to determine whether
2238 /// the given template arguments match the given class template
2239 /// partial specialization per C++ [temp.class.spec.match].
2240 Sema::TemplateDeductionResult
2241 Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
2242 const TemplateArgumentList &TemplateArgs,
2243 TemplateDeductionInfo &Info) {
2244 if (Partial->isInvalidDecl())
2247 // C++ [temp.class.spec.match]p2:
2248 // A partial specialization matches a given actual template
2249 // argument list if the template arguments of the partial
2250 // specialization can be deduced from the actual template argument
2253 // Unevaluated SFINAE context.
2254 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2255 SFINAETrap Trap(*this);
2257 SmallVector<DeducedTemplateArgument, 4> Deduced;
2258 Deduced.resize(Partial->getTemplateParameters()->size());
2259 if (TemplateDeductionResult Result
2260 = ::DeduceTemplateArguments(*this,
2261 Partial->getTemplateParameters(),
2262 Partial->getTemplateArgs(),
2263 TemplateArgs, Info, Deduced))
2266 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2267 InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
2269 if (Inst.isInvalid())
2270 return TDK_InstantiationDepth;
2272 if (Trap.hasErrorOccurred())
2273 return Sema::TDK_SubstitutionFailure;
2275 return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs,
2279 /// Complete template argument deduction for a variable template partial
2281 /// TODO: Unify with ClassTemplatePartialSpecializationDecl version?
2282 /// May require unifying ClassTemplate(Partial)SpecializationDecl and
2283 /// VarTemplate(Partial)SpecializationDecl with a new data
2284 /// structure Template(Partial)SpecializationDecl, and
2285 /// using Template(Partial)SpecializationDecl as input type.
2286 static Sema::TemplateDeductionResult FinishTemplateArgumentDeduction(
2287 Sema &S, VarTemplatePartialSpecializationDecl *Partial,
2288 const TemplateArgumentList &TemplateArgs,
2289 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2290 TemplateDeductionInfo &Info) {
2291 // Unevaluated SFINAE context.
2292 EnterExpressionEvaluationContext Unevaluated(S, Sema::Unevaluated);
2293 Sema::SFINAETrap Trap(S);
2295 // C++ [temp.deduct.type]p2:
2296 // [...] or if any template argument remains neither deduced nor
2297 // explicitly specified, template argument deduction fails.
2298 SmallVector<TemplateArgument, 4> Builder;
2299 TemplateParameterList *PartialParams = Partial->getTemplateParameters();
2300 for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) {
2301 NamedDecl *Param = PartialParams->getParam(I);
2302 if (Deduced[I].isNull()) {
2303 Info.Param = makeTemplateParameter(Param);
2304 return Sema::TDK_Incomplete;
2307 // We have deduced this argument, so it still needs to be
2308 // checked and converted.
2310 // First, for a non-type template parameter type that is
2311 // initialized by a declaration, we need the type of the
2312 // corresponding non-type template parameter.
2314 if (NonTypeTemplateParmDecl *NTTP =
2315 dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2316 NTTPType = NTTP->getType();
2317 if (NTTPType->isDependentType()) {
2318 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2319 Builder.data(), Builder.size());
2321 S.SubstType(NTTPType, MultiLevelTemplateArgumentList(TemplateArgs),
2322 NTTP->getLocation(), NTTP->getDeclName());
2323 if (NTTPType.isNull()) {
2324 Info.Param = makeTemplateParameter(Param);
2325 // FIXME: These template arguments are temporary. Free them!
2326 Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2328 return Sema::TDK_SubstitutionFailure;
2333 if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Partial, NTTPType,
2334 0, Info, false, Builder)) {
2335 Info.Param = makeTemplateParameter(Param);
2336 // FIXME: These template arguments are temporary. Free them!
2337 Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2339 return Sema::TDK_SubstitutionFailure;
2343 // Form the template argument list from the deduced template arguments.
2344 TemplateArgumentList *DeducedArgumentList = TemplateArgumentList::CreateCopy(
2345 S.Context, Builder.data(), Builder.size());
2347 Info.reset(DeducedArgumentList);
2349 // Substitute the deduced template arguments into the template
2350 // arguments of the class template partial specialization, and
2351 // verify that the instantiated template arguments are both valid
2352 // and are equivalent to the template arguments originally provided
2353 // to the class template.
2354 LocalInstantiationScope InstScope(S);
2355 VarTemplateDecl *VarTemplate = Partial->getSpecializedTemplate();
2356 const ASTTemplateArgumentListInfo *PartialTemplArgInfo
2357 = Partial->getTemplateArgsAsWritten();
2358 const TemplateArgumentLoc *PartialTemplateArgs
2359 = PartialTemplArgInfo->getTemplateArgs();
2361 TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc,
2362 PartialTemplArgInfo->RAngleLoc);
2364 if (S.Subst(PartialTemplateArgs, PartialTemplArgInfo->NumTemplateArgs,
2365 InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
2366 unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2367 if (ParamIdx >= Partial->getTemplateParameters()->size())
2368 ParamIdx = Partial->getTemplateParameters()->size() - 1;
2370 Decl *Param = const_cast<NamedDecl *>(
2371 Partial->getTemplateParameters()->getParam(ParamIdx));
2372 Info.Param = makeTemplateParameter(Param);
2373 Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
2374 return Sema::TDK_SubstitutionFailure;
2376 SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2377 if (S.CheckTemplateArgumentList(VarTemplate, Partial->getLocation(), InstArgs,
2378 false, ConvertedInstArgs))
2379 return Sema::TDK_SubstitutionFailure;
2381 TemplateParameterList *TemplateParams = VarTemplate->getTemplateParameters();
2382 for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2383 TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2384 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2385 Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2386 Info.FirstArg = TemplateArgs[I];
2387 Info.SecondArg = InstArg;
2388 return Sema::TDK_NonDeducedMismatch;
2392 if (Trap.hasErrorOccurred())
2393 return Sema::TDK_SubstitutionFailure;
2395 return Sema::TDK_Success;
2398 /// \brief Perform template argument deduction to determine whether
2399 /// the given template arguments match the given variable template
2400 /// partial specialization per C++ [temp.class.spec.match].
2401 /// TODO: Unify with ClassTemplatePartialSpecializationDecl version?
2402 /// May require unifying ClassTemplate(Partial)SpecializationDecl and
2403 /// VarTemplate(Partial)SpecializationDecl with a new data
2404 /// structure Template(Partial)SpecializationDecl, and
2405 /// using Template(Partial)SpecializationDecl as input type.
2406 Sema::TemplateDeductionResult
2407 Sema::DeduceTemplateArguments(VarTemplatePartialSpecializationDecl *Partial,
2408 const TemplateArgumentList &TemplateArgs,
2409 TemplateDeductionInfo &Info) {
2410 if (Partial->isInvalidDecl())
2413 // C++ [temp.class.spec.match]p2:
2414 // A partial specialization matches a given actual template
2415 // argument list if the template arguments of the partial
2416 // specialization can be deduced from the actual template argument
2419 // Unevaluated SFINAE context.
2420 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2421 SFINAETrap Trap(*this);
2423 SmallVector<DeducedTemplateArgument, 4> Deduced;
2424 Deduced.resize(Partial->getTemplateParameters()->size());
2425 if (TemplateDeductionResult Result = ::DeduceTemplateArguments(
2426 *this, Partial->getTemplateParameters(), Partial->getTemplateArgs(),
2427 TemplateArgs, Info, Deduced))
2430 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2431 InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
2433 if (Inst.isInvalid())
2434 return TDK_InstantiationDepth;
2436 if (Trap.hasErrorOccurred())
2437 return Sema::TDK_SubstitutionFailure;
2439 return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs,
2443 /// \brief Determine whether the given type T is a simple-template-id type.
2444 static bool isSimpleTemplateIdType(QualType T) {
2445 if (const TemplateSpecializationType *Spec
2446 = T->getAs<TemplateSpecializationType>())
2447 return Spec->getTemplateName().getAsTemplateDecl() != nullptr;
2452 /// \brief Substitute the explicitly-provided template arguments into the
2453 /// given function template according to C++ [temp.arg.explicit].
2455 /// \param FunctionTemplate the function template into which the explicit
2456 /// template arguments will be substituted.
2458 /// \param ExplicitTemplateArgs the explicitly-specified template
2461 /// \param Deduced the deduced template arguments, which will be populated
2462 /// with the converted and checked explicit template arguments.
2464 /// \param ParamTypes will be populated with the instantiated function
2467 /// \param FunctionType if non-NULL, the result type of the function template
2468 /// will also be instantiated and the pointed-to value will be updated with
2469 /// the instantiated function type.
2471 /// \param Info if substitution fails for any reason, this object will be
2472 /// populated with more information about the failure.
2474 /// \returns TDK_Success if substitution was successful, or some failure
2476 Sema::TemplateDeductionResult
2477 Sema::SubstituteExplicitTemplateArguments(
2478 FunctionTemplateDecl *FunctionTemplate,
2479 TemplateArgumentListInfo &ExplicitTemplateArgs,
2480 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2481 SmallVectorImpl<QualType> &ParamTypes,
2482 QualType *FunctionType,
2483 TemplateDeductionInfo &Info) {
2484 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
2485 TemplateParameterList *TemplateParams
2486 = FunctionTemplate->getTemplateParameters();
2488 if (ExplicitTemplateArgs.size() == 0) {
2489 // No arguments to substitute; just copy over the parameter types and
2490 // fill in the function type.
2491 for (auto P : Function->params())
2492 ParamTypes.push_back(P->getType());
2495 *FunctionType = Function->getType();
2499 // Unevaluated SFINAE context.
2500 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2501 SFINAETrap Trap(*this);
2503 // C++ [temp.arg.explicit]p3:
2504 // Template arguments that are present shall be specified in the
2505 // declaration order of their corresponding template-parameters. The
2506 // template argument list shall not specify more template-arguments than
2507 // there are corresponding template-parameters.
2508 SmallVector<TemplateArgument, 4> Builder;
2510 // Enter a new template instantiation context where we check the
2511 // explicitly-specified template arguments against this function template,
2512 // and then substitute them into the function parameter types.
2513 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2514 InstantiatingTemplate Inst(*this, Info.getLocation(), FunctionTemplate,
2516 ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution,
2518 if (Inst.isInvalid())
2519 return TDK_InstantiationDepth;
2521 if (CheckTemplateArgumentList(FunctionTemplate,
2523 ExplicitTemplateArgs,
2525 Builder) || Trap.hasErrorOccurred()) {
2526 unsigned Index = Builder.size();
2527 if (Index >= TemplateParams->size())
2528 Index = TemplateParams->size() - 1;
2529 Info.Param = makeTemplateParameter(TemplateParams->getParam(Index));
2530 return TDK_InvalidExplicitArguments;
2533 // Form the template argument list from the explicitly-specified
2534 // template arguments.
2535 TemplateArgumentList *ExplicitArgumentList
2536 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
2537 Info.reset(ExplicitArgumentList);
2539 // Template argument deduction and the final substitution should be
2540 // done in the context of the templated declaration. Explicit
2541 // argument substitution, on the other hand, needs to happen in the
2543 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2545 // If we deduced template arguments for a template parameter pack,
2546 // note that the template argument pack is partially substituted and record
2547 // the explicit template arguments. They'll be used as part of deduction
2548 // for this template parameter pack.
2549 for (unsigned I = 0, N = Builder.size(); I != N; ++I) {
2550 const TemplateArgument &Arg = Builder[I];
2551 if (Arg.getKind() == TemplateArgument::Pack) {
2552 CurrentInstantiationScope->SetPartiallySubstitutedPack(
2553 TemplateParams->getParam(I),
2560 const FunctionProtoType *Proto
2561 = Function->getType()->getAs<FunctionProtoType>();
2562 assert(Proto && "Function template does not have a prototype?");
2564 // Isolate our substituted parameters from our caller.
2565 LocalInstantiationScope InstScope(*this, /*MergeWithOuterScope*/true);
2567 // Instantiate the types of each of the function parameters given the
2568 // explicitly-specified template arguments. If the function has a trailing
2569 // return type, substitute it after the arguments to ensure we substitute
2570 // in lexical order.
2571 if (Proto->hasTrailingReturn()) {
2572 if (SubstParmTypes(Function->getLocation(),
2573 Function->param_begin(), Function->getNumParams(),
2574 MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2576 return TDK_SubstitutionFailure;
2579 // Instantiate the return type.
2580 QualType ResultType;
2582 // C++11 [expr.prim.general]p3:
2583 // If a declaration declares a member function or member function
2584 // template of a class X, the expression this is a prvalue of type
2585 // "pointer to cv-qualifier-seq X" between the optional cv-qualifer-seq
2586 // and the end of the function-definition, member-declarator, or
2588 unsigned ThisTypeQuals = 0;
2589 CXXRecordDecl *ThisContext = nullptr;
2590 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Function)) {
2591 ThisContext = Method->getParent();
2592 ThisTypeQuals = Method->getTypeQualifiers();
2595 CXXThisScopeRAII ThisScope(*this, ThisContext, ThisTypeQuals,
2596 getLangOpts().CPlusPlus11);
2599 SubstType(Proto->getReturnType(),
2600 MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2601 Function->getTypeSpecStartLoc(), Function->getDeclName());
2602 if (ResultType.isNull() || Trap.hasErrorOccurred())
2603 return TDK_SubstitutionFailure;
2606 // Instantiate the types of each of the function parameters given the
2607 // explicitly-specified template arguments if we didn't do so earlier.
2608 if (!Proto->hasTrailingReturn() &&
2609 SubstParmTypes(Function->getLocation(),
2610 Function->param_begin(), Function->getNumParams(),
2611 MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2613 return TDK_SubstitutionFailure;
2616 *FunctionType = BuildFunctionType(ResultType, ParamTypes,
2617 Function->getLocation(),
2618 Function->getDeclName(),
2619 Proto->getExtProtoInfo());
2620 if (FunctionType->isNull() || Trap.hasErrorOccurred())
2621 return TDK_SubstitutionFailure;
2624 // C++ [temp.arg.explicit]p2:
2625 // Trailing template arguments that can be deduced (14.8.2) may be
2626 // omitted from the list of explicit template-arguments. If all of the
2627 // template arguments can be deduced, they may all be omitted; in this
2628 // case, the empty template argument list <> itself may also be omitted.
2630 // Take all of the explicitly-specified arguments and put them into
2631 // the set of deduced template arguments. Explicitly-specified
2632 // parameter packs, however, will be set to NULL since the deduction
2633 // mechanisms handle explicitly-specified argument packs directly.
2634 Deduced.reserve(TemplateParams->size());
2635 for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) {
2636 const TemplateArgument &Arg = ExplicitArgumentList->get(I);
2637 if (Arg.getKind() == TemplateArgument::Pack)
2638 Deduced.push_back(DeducedTemplateArgument());
2640 Deduced.push_back(Arg);
2646 /// \brief Check whether the deduced argument type for a call to a function
2647 /// template matches the actual argument type per C++ [temp.deduct.call]p4.
2649 CheckOriginalCallArgDeduction(Sema &S, Sema::OriginalCallArg OriginalArg,
2650 QualType DeducedA) {
2651 ASTContext &Context = S.Context;
2653 QualType A = OriginalArg.OriginalArgType;
2654 QualType OriginalParamType = OriginalArg.OriginalParamType;
2656 // Check for type equality (top-level cv-qualifiers are ignored).
2657 if (Context.hasSameUnqualifiedType(A, DeducedA))
2660 // Strip off references on the argument types; they aren't needed for
2661 // the following checks.
2662 if (const ReferenceType *DeducedARef = DeducedA->getAs<ReferenceType>())
2663 DeducedA = DeducedARef->getPointeeType();
2664 if (const ReferenceType *ARef = A->getAs<ReferenceType>())
2665 A = ARef->getPointeeType();
2667 // C++ [temp.deduct.call]p4:
2668 // [...] However, there are three cases that allow a difference:
2669 // - If the original P is a reference type, the deduced A (i.e., the
2670 // type referred to by the reference) can be more cv-qualified than
2671 // the transformed A.
2672 if (const ReferenceType *OriginalParamRef
2673 = OriginalParamType->getAs<ReferenceType>()) {
2674 // We don't want to keep the reference around any more.
2675 OriginalParamType = OriginalParamRef->getPointeeType();
2677 Qualifiers AQuals = A.getQualifiers();
2678 Qualifiers DeducedAQuals = DeducedA.getQualifiers();
2680 // Under Objective-C++ ARC, the deduced type may have implicitly
2681 // been given strong or (when dealing with a const reference)
2682 // unsafe_unretained lifetime. If so, update the original
2683 // qualifiers to include this lifetime.
2684 if (S.getLangOpts().ObjCAutoRefCount &&
2685 ((DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_Strong &&
2686 AQuals.getObjCLifetime() == Qualifiers::OCL_None) ||
2687 (DeducedAQuals.hasConst() &&
2688 DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone))) {
2689 AQuals.setObjCLifetime(DeducedAQuals.getObjCLifetime());
2692 if (AQuals == DeducedAQuals) {
2693 // Qualifiers match; there's nothing to do.
2694 } else if (!DeducedAQuals.compatiblyIncludes(AQuals)) {
2697 // Qualifiers are compatible, so have the argument type adopt the
2698 // deduced argument type's qualifiers as if we had performed the
2699 // qualification conversion.
2700 A = Context.getQualifiedType(A.getUnqualifiedType(), DeducedAQuals);
2704 // - The transformed A can be another pointer or pointer to member
2705 // type that can be converted to the deduced A via a qualification
2708 // Also allow conversions which merely strip [[noreturn]] from function types
2709 // (recursively) as an extension.
2710 // FIXME: Currently, this doesn't play nicely with qualification conversions.
2711 bool ObjCLifetimeConversion = false;
2713 if ((A->isAnyPointerType() || A->isMemberPointerType()) &&
2714 (S.IsQualificationConversion(A, DeducedA, false,
2715 ObjCLifetimeConversion) ||
2716 S.IsNoReturnConversion(A, DeducedA, ResultTy)))
2720 // - If P is a class and P has the form simple-template-id, then the
2721 // transformed A can be a derived class of the deduced A. [...]
2722 // [...] Likewise, if P is a pointer to a class of the form
2723 // simple-template-id, the transformed A can be a pointer to a
2724 // derived class pointed to by the deduced A.
2725 if (const PointerType *OriginalParamPtr
2726 = OriginalParamType->getAs<PointerType>()) {
2727 if (const PointerType *DeducedAPtr = DeducedA->getAs<PointerType>()) {
2728 if (const PointerType *APtr = A->getAs<PointerType>()) {
2729 if (A->getPointeeType()->isRecordType()) {
2730 OriginalParamType = OriginalParamPtr->getPointeeType();
2731 DeducedA = DeducedAPtr->getPointeeType();
2732 A = APtr->getPointeeType();
2738 if (Context.hasSameUnqualifiedType(A, DeducedA))
2741 if (A->isRecordType() && isSimpleTemplateIdType(OriginalParamType) &&
2742 S.IsDerivedFrom(SourceLocation(), A, DeducedA))
2748 /// \brief Finish template argument deduction for a function template,
2749 /// checking the deduced template arguments for completeness and forming
2750 /// the function template specialization.
2752 /// \param OriginalCallArgs If non-NULL, the original call arguments against
2753 /// which the deduced argument types should be compared.
2754 Sema::TemplateDeductionResult
2755 Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate,
2756 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2757 unsigned NumExplicitlySpecified,
2758 FunctionDecl *&Specialization,
2759 TemplateDeductionInfo &Info,
2760 SmallVectorImpl<OriginalCallArg> const *OriginalCallArgs,
2761 bool PartialOverloading) {
2762 TemplateParameterList *TemplateParams
2763 = FunctionTemplate->getTemplateParameters();
2765 // Unevaluated SFINAE context.
2766 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2767 SFINAETrap Trap(*this);
2769 // Enter a new template instantiation context while we instantiate the
2770 // actual function declaration.
2771 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2772 InstantiatingTemplate Inst(*this, Info.getLocation(), FunctionTemplate,
2774 ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution,
2776 if (Inst.isInvalid())
2777 return TDK_InstantiationDepth;
2779 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2781 // C++ [temp.deduct.type]p2:
2782 // [...] or if any template argument remains neither deduced nor
2783 // explicitly specified, template argument deduction fails.
2784 SmallVector<TemplateArgument, 4> Builder;
2785 for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) {
2786 NamedDecl *Param = TemplateParams->getParam(I);
2788 if (!Deduced[I].isNull()) {
2789 if (I < NumExplicitlySpecified) {
2790 // We have already fully type-checked and converted this
2791 // argument, because it was explicitly-specified. Just record the
2792 // presence of this argument.
2793 Builder.push_back(Deduced[I]);
2794 // We may have had explicitly-specified template arguments for a
2795 // template parameter pack (that may or may not have been extended
2796 // via additional deduced arguments).
2797 if (Param->isParameterPack() && CurrentInstantiationScope) {
2798 if (CurrentInstantiationScope->getPartiallySubstitutedPack() ==
2800 // Forget the partially-substituted pack; its substitution is now
2802 CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2807 // We have deduced this argument, so it still needs to be
2808 // checked and converted.
2810 // First, for a non-type template parameter type that is
2811 // initialized by a declaration, we need the type of the
2812 // corresponding non-type template parameter.
2814 if (NonTypeTemplateParmDecl *NTTP
2815 = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2816 NTTPType = NTTP->getType();
2817 if (NTTPType->isDependentType()) {
2818 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2819 Builder.data(), Builder.size());
2820 NTTPType = SubstType(NTTPType,
2821 MultiLevelTemplateArgumentList(TemplateArgs),
2822 NTTP->getLocation(),
2823 NTTP->getDeclName());
2824 if (NTTPType.isNull()) {
2825 Info.Param = makeTemplateParameter(Param);
2826 // FIXME: These template arguments are temporary. Free them!
2827 Info.reset(TemplateArgumentList::CreateCopy(Context,
2830 return TDK_SubstitutionFailure;
2835 if (ConvertDeducedTemplateArgument(*this, Param, Deduced[I],
2836 FunctionTemplate, NTTPType, 0, Info,
2838 Info.Param = makeTemplateParameter(Param);
2839 // FIXME: These template arguments are temporary. Free them!
2840 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2842 return TDK_SubstitutionFailure;
2848 // C++0x [temp.arg.explicit]p3:
2849 // A trailing template parameter pack (14.5.3) not otherwise deduced will
2850 // be deduced to an empty sequence of template arguments.
2851 // FIXME: Where did the word "trailing" come from?
2852 if (Param->isTemplateParameterPack()) {
2853 // We may have had explicitly-specified template arguments for this
2854 // template parameter pack. If so, our empty deduction extends the
2855 // explicitly-specified set (C++0x [temp.arg.explicit]p9).
2856 const TemplateArgument *ExplicitArgs;
2857 unsigned NumExplicitArgs;
2858 if (CurrentInstantiationScope &&
2859 CurrentInstantiationScope->getPartiallySubstitutedPack(&ExplicitArgs,
2862 Builder.push_back(TemplateArgument(
2863 llvm::makeArrayRef(ExplicitArgs, NumExplicitArgs)));
2865 // Forget the partially-substituted pack; it's substitution is now
2867 CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2869 Builder.push_back(TemplateArgument::getEmptyPack());
2874 // Substitute into the default template argument, if available.
2875 bool HasDefaultArg = false;
2876 TemplateArgumentLoc DefArg
2877 = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate,
2878 FunctionTemplate->getLocation(),
2879 FunctionTemplate->getSourceRange().getEnd(),
2881 Builder, HasDefaultArg);
2883 // If there was no default argument, deduction is incomplete.
2884 if (DefArg.getArgument().isNull()) {
2885 Info.Param = makeTemplateParameter(
2886 const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2887 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2889 if (PartialOverloading) break;
2891 return HasDefaultArg ? TDK_SubstitutionFailure : TDK_Incomplete;
2894 // Check whether we can actually use the default argument.
2895 if (CheckTemplateArgument(Param, DefArg,
2897 FunctionTemplate->getLocation(),
2898 FunctionTemplate->getSourceRange().getEnd(),
2901 Info.Param = makeTemplateParameter(
2902 const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2903 // FIXME: These template arguments are temporary. Free them!
2904 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2906 return TDK_SubstitutionFailure;
2909 // If we get here, we successfully used the default template argument.
2912 // Form the template argument list from the deduced template arguments.
2913 TemplateArgumentList *DeducedArgumentList
2914 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
2915 Info.reset(DeducedArgumentList);
2917 // Substitute the deduced template arguments into the function template
2918 // declaration to produce the function template specialization.
2919 DeclContext *Owner = FunctionTemplate->getDeclContext();
2920 if (FunctionTemplate->getFriendObjectKind())
2921 Owner = FunctionTemplate->getLexicalDeclContext();
2922 Specialization = cast_or_null<FunctionDecl>(
2923 SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner,
2924 MultiLevelTemplateArgumentList(*DeducedArgumentList)));
2925 if (!Specialization || Specialization->isInvalidDecl())
2926 return TDK_SubstitutionFailure;
2928 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() ==
2929 FunctionTemplate->getCanonicalDecl());
2931 // If the template argument list is owned by the function template
2932 // specialization, release it.
2933 if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList &&
2934 !Trap.hasErrorOccurred())
2937 // There may have been an error that did not prevent us from constructing a
2938 // declaration. Mark the declaration invalid and return with a substitution
2940 if (Trap.hasErrorOccurred()) {
2941 Specialization->setInvalidDecl(true);
2942 return TDK_SubstitutionFailure;
2945 if (OriginalCallArgs) {
2946 // C++ [temp.deduct.call]p4:
2947 // In general, the deduction process attempts to find template argument
2948 // values that will make the deduced A identical to A (after the type A
2949 // is transformed as described above). [...]
2950 for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; ++I) {
2951 OriginalCallArg OriginalArg = (*OriginalCallArgs)[I];
2952 unsigned ParamIdx = OriginalArg.ArgIdx;
2954 if (ParamIdx >= Specialization->getNumParams())
2957 QualType DeducedA = Specialization->getParamDecl(ParamIdx)->getType();
2958 if (CheckOriginalCallArgDeduction(*this, OriginalArg, DeducedA)) {
2959 Info.FirstArg = TemplateArgument(DeducedA);
2960 Info.SecondArg = TemplateArgument(OriginalArg.OriginalArgType);
2961 Info.CallArgIndex = OriginalArg.ArgIdx;
2962 return TDK_DeducedMismatch;
2967 // If we suppressed any diagnostics while performing template argument
2968 // deduction, and if we haven't already instantiated this declaration,
2969 // keep track of these diagnostics. They'll be emitted if this specialization
2970 // is actually used.
2971 if (Info.diag_begin() != Info.diag_end()) {
2972 SuppressedDiagnosticsMap::iterator
2973 Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl());
2974 if (Pos == SuppressedDiagnostics.end())
2975 SuppressedDiagnostics[Specialization->getCanonicalDecl()]
2976 .append(Info.diag_begin(), Info.diag_end());
2982 /// Gets the type of a function for template-argument-deducton
2983 /// purposes when it's considered as part of an overload set.
2984 static QualType GetTypeOfFunction(Sema &S, const OverloadExpr::FindResult &R,
2986 // We may need to deduce the return type of the function now.
2987 if (S.getLangOpts().CPlusPlus14 && Fn->getReturnType()->isUndeducedType() &&
2988 S.DeduceReturnType(Fn, R.Expression->getExprLoc(), /*Diagnose*/ false))
2991 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn))
2992 if (Method->isInstance()) {
2993 // An instance method that's referenced in a form that doesn't
2994 // look like a member pointer is just invalid.
2995 if (!R.HasFormOfMemberPointer) return QualType();
2997 return S.Context.getMemberPointerType(Fn->getType(),
2998 S.Context.getTypeDeclType(Method->getParent()).getTypePtr());
3001 if (!R.IsAddressOfOperand) return Fn->getType();
3002 return S.Context.getPointerType(Fn->getType());
3005 /// Apply the deduction rules for overload sets.
3007 /// \return the null type if this argument should be treated as an
3008 /// undeduced context
3010 ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams,
3011 Expr *Arg, QualType ParamType,
3012 bool ParamWasReference) {
3014 OverloadExpr::FindResult R = OverloadExpr::find(Arg);
3016 OverloadExpr *Ovl = R.Expression;
3018 // C++0x [temp.deduct.call]p4
3020 if (ParamWasReference)
3021 TDF |= TDF_ParamWithReferenceType;
3022 if (R.IsAddressOfOperand)
3023 TDF |= TDF_IgnoreQualifiers;
3025 // C++0x [temp.deduct.call]p6:
3026 // When P is a function type, pointer to function type, or pointer
3027 // to member function type:
3029 if (!ParamType->isFunctionType() &&
3030 !ParamType->isFunctionPointerType() &&
3031 !ParamType->isMemberFunctionPointerType()) {
3032 if (Ovl->hasExplicitTemplateArgs()) {
3033 // But we can still look for an explicit specialization.
3034 if (FunctionDecl *ExplicitSpec
3035 = S.ResolveSingleFunctionTemplateSpecialization(Ovl))
3036 return GetTypeOfFunction(S, R, ExplicitSpec);
3042 // Gather the explicit template arguments, if any.
3043 TemplateArgumentListInfo ExplicitTemplateArgs;
3044 if (Ovl->hasExplicitTemplateArgs())
3045 Ovl->copyTemplateArgumentsInto(ExplicitTemplateArgs);
3047 for (UnresolvedSetIterator I = Ovl->decls_begin(),
3048 E = Ovl->decls_end(); I != E; ++I) {
3049 NamedDecl *D = (*I)->getUnderlyingDecl();
3051 if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) {
3052 // - If the argument is an overload set containing one or more
3053 // function templates, the parameter is treated as a
3054 // non-deduced context.
3055 if (!Ovl->hasExplicitTemplateArgs())
3058 // Otherwise, see if we can resolve a function type
3059 FunctionDecl *Specialization = nullptr;
3060 TemplateDeductionInfo Info(Ovl->getNameLoc());
3061 if (S.DeduceTemplateArguments(FunTmpl, &ExplicitTemplateArgs,
3062 Specialization, Info))
3068 FunctionDecl *Fn = cast<FunctionDecl>(D);
3069 QualType ArgType = GetTypeOfFunction(S, R, Fn);
3070 if (ArgType.isNull()) continue;
3072 // Function-to-pointer conversion.
3073 if (!ParamWasReference && ParamType->isPointerType() &&
3074 ArgType->isFunctionType())
3075 ArgType = S.Context.getPointerType(ArgType);
3077 // - If the argument is an overload set (not containing function
3078 // templates), trial argument deduction is attempted using each
3079 // of the members of the set. If deduction succeeds for only one
3080 // of the overload set members, that member is used as the
3081 // argument value for the deduction. If deduction succeeds for
3082 // more than one member of the overload set the parameter is
3083 // treated as a non-deduced context.
3085 // We do all of this in a fresh context per C++0x [temp.deduct.type]p2:
3086 // Type deduction is done independently for each P/A pair, and
3087 // the deduced template argument values are then combined.
3088 // So we do not reject deductions which were made elsewhere.
3089 SmallVector<DeducedTemplateArgument, 8>
3090 Deduced(TemplateParams->size());
3091 TemplateDeductionInfo Info(Ovl->getNameLoc());
3092 Sema::TemplateDeductionResult Result
3093 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3094 ArgType, Info, Deduced, TDF);
3095 if (Result) continue;
3096 if (!Match.isNull()) return QualType();
3103 /// \brief Perform the adjustments to the parameter and argument types
3104 /// described in C++ [temp.deduct.call].
3106 /// \returns true if the caller should not attempt to perform any template
3107 /// argument deduction based on this P/A pair because the argument is an
3108 /// overloaded function set that could not be resolved.
3109 static bool AdjustFunctionParmAndArgTypesForDeduction(Sema &S,
3110 TemplateParameterList *TemplateParams,
3111 QualType &ParamType,
3115 // C++0x [temp.deduct.call]p3:
3116 // If P is a cv-qualified type, the top level cv-qualifiers of P's type
3117 // are ignored for type deduction.
3118 if (ParamType.hasQualifiers())
3119 ParamType = ParamType.getUnqualifiedType();
3121 // [...] If P is a reference type, the type referred to by P is
3122 // used for type deduction.
3123 const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>();
3125 ParamType = ParamRefType->getPointeeType();
3127 // Overload sets usually make this parameter an undeduced context,
3128 // but there are sometimes special circumstances. Typically
3129 // involving a template-id-expr.
3130 if (ArgType == S.Context.OverloadTy) {
3131 ArgType = ResolveOverloadForDeduction(S, TemplateParams,
3133 ParamRefType != nullptr);
3134 if (ArgType.isNull())
3139 // If the argument has incomplete array type, try to complete its type.
3140 if (ArgType->isIncompleteArrayType()) {
3141 S.completeExprArrayBound(Arg);
3142 ArgType = Arg->getType();
3145 // C++0x [temp.deduct.call]p3:
3146 // If P is an rvalue reference to a cv-unqualified template
3147 // parameter and the argument is an lvalue, the type "lvalue
3148 // reference to A" is used in place of A for type deduction.
3149 if (ParamRefType->isRValueReferenceType() &&
3150 !ParamType.getQualifiers() &&
3151 isa<TemplateTypeParmType>(ParamType) &&
3153 ArgType = S.Context.getLValueReferenceType(ArgType);
3155 // C++ [temp.deduct.call]p2:
3156 // If P is not a reference type:
3157 // - If A is an array type, the pointer type produced by the
3158 // array-to-pointer standard conversion (4.2) is used in place of
3159 // A for type deduction; otherwise,
3160 if (ArgType->isArrayType())
3161 ArgType = S.Context.getArrayDecayedType(ArgType);
3162 // - If A is a function type, the pointer type produced by the
3163 // function-to-pointer standard conversion (4.3) is used in place
3164 // of A for type deduction; otherwise,
3165 else if (ArgType->isFunctionType())
3166 ArgType = S.Context.getPointerType(ArgType);
3168 // - If A is a cv-qualified type, the top level cv-qualifiers of A's
3169 // type are ignored for type deduction.
3170 ArgType = ArgType.getUnqualifiedType();
3174 // C++0x [temp.deduct.call]p4:
3175 // In general, the deduction process attempts to find template argument
3176 // values that will make the deduced A identical to A (after the type A
3177 // is transformed as described above). [...]
3178 TDF = TDF_SkipNonDependent;
3180 // - If the original P is a reference type, the deduced A (i.e., the
3181 // type referred to by the reference) can be more cv-qualified than
3182 // the transformed A.
3184 TDF |= TDF_ParamWithReferenceType;
3185 // - The transformed A can be another pointer or pointer to member
3186 // type that can be converted to the deduced A via a qualification
3187 // conversion (4.4).
3188 if (ArgType->isPointerType() || ArgType->isMemberPointerType() ||
3189 ArgType->isObjCObjectPointerType())
3190 TDF |= TDF_IgnoreQualifiers;
3191 // - If P is a class and P has the form simple-template-id, then the
3192 // transformed A can be a derived class of the deduced A. Likewise,
3193 // if P is a pointer to a class of the form simple-template-id, the
3194 // transformed A can be a pointer to a derived class pointed to by
3196 if (isSimpleTemplateIdType(ParamType) ||
3197 (isa<PointerType>(ParamType) &&
3198 isSimpleTemplateIdType(
3199 ParamType->getAs<PointerType>()->getPointeeType())))
3200 TDF |= TDF_DerivedClass;
3206 hasDeducibleTemplateParameters(Sema &S, FunctionTemplateDecl *FunctionTemplate,
3209 static Sema::TemplateDeductionResult DeduceTemplateArgumentByListElement(
3210 Sema &S, TemplateParameterList *TemplateParams, QualType ParamType,
3211 Expr *Arg, TemplateDeductionInfo &Info,
3212 SmallVectorImpl<DeducedTemplateArgument> &Deduced, unsigned TDF);
3214 /// \brief Attempt template argument deduction from an initializer list
3215 /// deemed to be an argument in a function call.
3217 DeduceFromInitializerList(Sema &S, TemplateParameterList *TemplateParams,
3218 QualType AdjustedParamType, InitListExpr *ILE,
3219 TemplateDeductionInfo &Info,
3220 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3221 unsigned TDF, Sema::TemplateDeductionResult &Result) {
3223 // [temp.deduct.call] p1 (post CWG-1591)
3224 // If removing references and cv-qualifiers from P gives
3225 // std::initializer_list<P0> or P0[N] for some P0 and N and the argument is a
3226 // non-empty initializer list (8.5.4), then deduction is performed instead for
3227 // each element of the initializer list, taking P0 as a function template
3228 // parameter type and the initializer element as its argument, and in the
3229 // P0[N] case, if N is a non-type template parameter, N is deduced from the
3230 // length of the initializer list. Otherwise, an initializer list argument
3231 // causes the parameter to be considered a non-deduced context
3233 const bool IsConstSizedArray = AdjustedParamType->isConstantArrayType();
3235 const bool IsDependentSizedArray =
3236 !IsConstSizedArray && AdjustedParamType->isDependentSizedArrayType();
3238 QualType ElTy; // The element type of the std::initializer_list or the array.
3240 const bool IsSTDList = !IsConstSizedArray && !IsDependentSizedArray &&
3241 S.isStdInitializerList(AdjustedParamType, &ElTy);
3243 if (!IsConstSizedArray && !IsDependentSizedArray && !IsSTDList)
3246 Result = Sema::TDK_Success;
3247 // If we are not deducing against the 'T' in a std::initializer_list<T> then
3248 // deduce against the 'T' in T[N].
3249 if (ElTy.isNull()) {
3251 ElTy = S.Context.getAsArrayType(AdjustedParamType)->getElementType();
3253 // Deduction only needs to be done for dependent types.
3254 if (ElTy->isDependentType()) {
3255 for (Expr *E : ILE->inits()) {
3256 if ((Result = DeduceTemplateArgumentByListElement(S, TemplateParams, ElTy,
3257 E, Info, Deduced, TDF)))
3261 if (IsDependentSizedArray) {
3262 const DependentSizedArrayType *ArrTy =
3263 S.Context.getAsDependentSizedArrayType(AdjustedParamType);
3264 // Determine the array bound is something we can deduce.
3265 if (NonTypeTemplateParmDecl *NTTP =
3266 getDeducedParameterFromExpr(ArrTy->getSizeExpr())) {
3267 // We can perform template argument deduction for the given non-type
3268 // template parameter.
3269 assert(NTTP->getDepth() == 0 &&
3270 "Cannot deduce non-type template argument at depth > 0");
3271 llvm::APInt Size(S.Context.getIntWidth(NTTP->getType()),
3272 ILE->getNumInits());
3274 Result = DeduceNonTypeTemplateArgument(
3275 S, NTTP, llvm::APSInt(Size), NTTP->getType(),
3276 /*ArrayBound=*/true, Info, Deduced);
3282 /// \brief Perform template argument deduction by matching a parameter type
3283 /// against a single expression, where the expression is an element of
3284 /// an initializer list that was originally matched against a parameter
3285 /// of type \c initializer_list\<ParamType\>.
3286 static Sema::TemplateDeductionResult
3287 DeduceTemplateArgumentByListElement(Sema &S,
3288 TemplateParameterList *TemplateParams,
3289 QualType ParamType, Expr *Arg,
3290 TemplateDeductionInfo &Info,
3291 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3293 // Handle the case where an init list contains another init list as the
3295 if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) {
3296 Sema::TemplateDeductionResult Result;
3297 if (!DeduceFromInitializerList(S, TemplateParams,
3298 ParamType.getNonReferenceType(), ILE, Info,
3299 Deduced, TDF, Result))
3300 return Sema::TDK_Success; // Just ignore this expression.
3305 // For all other cases, just match by type.
3306 QualType ArgType = Arg->getType();
3307 if (AdjustFunctionParmAndArgTypesForDeduction(S, TemplateParams, ParamType,
3308 ArgType, Arg, TDF)) {
3309 Info.Expression = Arg;
3310 return Sema::TDK_FailedOverloadResolution;
3312 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3313 ArgType, Info, Deduced, TDF);
3316 /// \brief Perform template argument deduction from a function call
3317 /// (C++ [temp.deduct.call]).
3319 /// \param FunctionTemplate the function template for which we are performing
3320 /// template argument deduction.
3322 /// \param ExplicitTemplateArgs the explicit template arguments provided
3325 /// \param Args the function call arguments
3327 /// \param Specialization if template argument deduction was successful,
3328 /// this will be set to the function template specialization produced by
3329 /// template argument deduction.
3331 /// \param Info the argument will be updated to provide additional information
3332 /// about template argument deduction.
3334 /// \returns the result of template argument deduction.
3335 Sema::TemplateDeductionResult Sema::DeduceTemplateArguments(
3336 FunctionTemplateDecl *FunctionTemplate,
3337 TemplateArgumentListInfo *ExplicitTemplateArgs, ArrayRef<Expr *> Args,
3338 FunctionDecl *&Specialization, TemplateDeductionInfo &Info,
3339 bool PartialOverloading) {
3340 if (FunctionTemplate->isInvalidDecl())
3343 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3344 unsigned NumParams = Function->getNumParams();
3346 // C++ [temp.deduct.call]p1:
3347 // Template argument deduction is done by comparing each function template
3348 // parameter type (call it P) with the type of the corresponding argument
3349 // of the call (call it A) as described below.
3350 unsigned CheckArgs = Args.size();
3351 if (Args.size() < Function->getMinRequiredArguments() && !PartialOverloading)
3352 return TDK_TooFewArguments;
3353 else if (TooManyArguments(NumParams, Args.size(), PartialOverloading)) {
3354 const FunctionProtoType *Proto
3355 = Function->getType()->getAs<FunctionProtoType>();
3356 if (Proto->isTemplateVariadic())
3358 else if (Proto->isVariadic())
3359 CheckArgs = NumParams;
3361 return TDK_TooManyArguments;
3364 // The types of the parameters from which we will perform template argument
3366 LocalInstantiationScope InstScope(*this);
3367 TemplateParameterList *TemplateParams
3368 = FunctionTemplate->getTemplateParameters();
3369 SmallVector<DeducedTemplateArgument, 4> Deduced;
3370 SmallVector<QualType, 4> ParamTypes;
3371 unsigned NumExplicitlySpecified = 0;
3372 if (ExplicitTemplateArgs) {
3373 TemplateDeductionResult Result =
3374 SubstituteExplicitTemplateArguments(FunctionTemplate,
3375 *ExplicitTemplateArgs,
3383 NumExplicitlySpecified = Deduced.size();
3385 // Just fill in the parameter types from the function declaration.
3386 for (unsigned I = 0; I != NumParams; ++I)
3387 ParamTypes.push_back(Function->getParamDecl(I)->getType());
3390 // Deduce template arguments from the function parameters.
3391 Deduced.resize(TemplateParams->size());
3392 unsigned ArgIdx = 0;
3393 SmallVector<OriginalCallArg, 4> OriginalCallArgs;
3394 for (unsigned ParamIdx = 0, NumParamTypes = ParamTypes.size();
3395 ParamIdx != NumParamTypes; ++ParamIdx) {
3396 QualType OrigParamType = ParamTypes[ParamIdx];
3397 QualType ParamType = OrigParamType;
3399 const PackExpansionType *ParamExpansion
3400 = dyn_cast<PackExpansionType>(ParamType);
3401 if (!ParamExpansion) {
3402 // Simple case: matching a function parameter to a function argument.
3403 if (ArgIdx >= CheckArgs)
3406 Expr *Arg = Args[ArgIdx++];
3407 QualType ArgType = Arg->getType();
3410 if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
3411 ParamType, ArgType, Arg,
3415 // If we have nothing to deduce, we're done.
3416 if (!hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
3419 // If the argument is an initializer list ...
3420 if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) {
3421 TemplateDeductionResult Result;
3422 // Removing references was already done.
3423 if (!DeduceFromInitializerList(*this, TemplateParams, ParamType, ILE,
3424 Info, Deduced, TDF, Result))
3429 // Don't track the argument type, since an initializer list has none.
3433 // Keep track of the argument type and corresponding parameter index,
3434 // so we can check for compatibility between the deduced A and A.
3435 OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx-1,
3438 if (TemplateDeductionResult Result
3439 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3441 Info, Deduced, TDF))
3447 // C++0x [temp.deduct.call]p1:
3448 // For a function parameter pack that occurs at the end of the
3449 // parameter-declaration-list, the type A of each remaining argument of
3450 // the call is compared with the type P of the declarator-id of the
3451 // function parameter pack. Each comparison deduces template arguments
3452 // for subsequent positions in the template parameter packs expanded by
3453 // the function parameter pack. For a function parameter pack that does
3454 // not occur at the end of the parameter-declaration-list, the type of
3455 // the parameter pack is a non-deduced context.
3456 if (ParamIdx + 1 < NumParamTypes)
3459 QualType ParamPattern = ParamExpansion->getPattern();
3460 PackDeductionScope PackScope(*this, TemplateParams, Deduced, Info,
3463 bool HasAnyArguments = false;
3464 for (; ArgIdx < Args.size(); ++ArgIdx) {
3465 HasAnyArguments = true;
3467 QualType OrigParamType = ParamPattern;
3468 ParamType = OrigParamType;
3469 Expr *Arg = Args[ArgIdx];
3470 QualType ArgType = Arg->getType();
3473 if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
3474 ParamType, ArgType, Arg,
3476 // We can't actually perform any deduction for this argument, so stop
3477 // deduction at this point.
3482 // As above, initializer lists need special handling.
3483 if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) {
3484 TemplateDeductionResult Result;
3485 if (!DeduceFromInitializerList(*this, TemplateParams, ParamType, ILE,
3486 Info, Deduced, TDF, Result)) {
3495 // Keep track of the argument type and corresponding argument index,
3496 // so we can check for compatibility between the deduced A and A.
3497 if (hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
3498 OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx,
3501 if (TemplateDeductionResult Result
3502 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3503 ParamType, ArgType, Info,
3508 PackScope.nextPackElement();
3511 // Build argument packs for each of the parameter packs expanded by this
3513 if (auto Result = PackScope.finish(HasAnyArguments))
3516 // After we've matching against a parameter pack, we're done.
3520 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
3521 NumExplicitlySpecified, Specialization,
3522 Info, &OriginalCallArgs,
3523 PartialOverloading);
3526 QualType Sema::adjustCCAndNoReturn(QualType ArgFunctionType,
3527 QualType FunctionType) {
3528 if (ArgFunctionType.isNull())
3529 return ArgFunctionType;
3531 const FunctionProtoType *FunctionTypeP =
3532 FunctionType->castAs<FunctionProtoType>();
3533 CallingConv CC = FunctionTypeP->getCallConv();
3534 bool NoReturn = FunctionTypeP->getNoReturnAttr();
3535 const FunctionProtoType *ArgFunctionTypeP =
3536 ArgFunctionType->getAs<FunctionProtoType>();
3537 if (ArgFunctionTypeP->getCallConv() == CC &&
3538 ArgFunctionTypeP->getNoReturnAttr() == NoReturn)
3539 return ArgFunctionType;
3541 FunctionType::ExtInfo EI = ArgFunctionTypeP->getExtInfo().withCallingConv(CC);
3542 EI = EI.withNoReturn(NoReturn);
3544 cast<FunctionProtoType>(Context.adjustFunctionType(ArgFunctionTypeP, EI));
3545 return QualType(ArgFunctionTypeP, 0);
3548 /// \brief Deduce template arguments when taking the address of a function
3549 /// template (C++ [temp.deduct.funcaddr]) or matching a specialization to
3552 /// \param FunctionTemplate the function template for which we are performing
3553 /// template argument deduction.
3555 /// \param ExplicitTemplateArgs the explicitly-specified template
3558 /// \param ArgFunctionType the function type that will be used as the
3559 /// "argument" type (A) when performing template argument deduction from the
3560 /// function template's function type. This type may be NULL, if there is no
3561 /// argument type to compare against, in C++0x [temp.arg.explicit]p3.
3563 /// \param Specialization if template argument deduction was successful,
3564 /// this will be set to the function template specialization produced by
3565 /// template argument deduction.
3567 /// \param Info the argument will be updated to provide additional information
3568 /// about template argument deduction.
3570 /// \returns the result of template argument deduction.
3571 Sema::TemplateDeductionResult
3572 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3573 TemplateArgumentListInfo *ExplicitTemplateArgs,
3574 QualType ArgFunctionType,
3575 FunctionDecl *&Specialization,
3576 TemplateDeductionInfo &Info,
3577 bool InOverloadResolution) {
3578 if (FunctionTemplate->isInvalidDecl())
3581 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3582 TemplateParameterList *TemplateParams
3583 = FunctionTemplate->getTemplateParameters();
3584 QualType FunctionType = Function->getType();
3585 if (!InOverloadResolution)
3586 ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, FunctionType);
3588 // Substitute any explicit template arguments.
3589 LocalInstantiationScope InstScope(*this);
3590 SmallVector<DeducedTemplateArgument, 4> Deduced;
3591 unsigned NumExplicitlySpecified = 0;
3592 SmallVector<QualType, 4> ParamTypes;
3593 if (ExplicitTemplateArgs) {
3594 if (TemplateDeductionResult Result
3595 = SubstituteExplicitTemplateArguments(FunctionTemplate,
3596 *ExplicitTemplateArgs,
3597 Deduced, ParamTypes,
3598 &FunctionType, Info))
3601 NumExplicitlySpecified = Deduced.size();
3604 // Unevaluated SFINAE context.
3605 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
3606 SFINAETrap Trap(*this);
3608 Deduced.resize(TemplateParams->size());
3610 // If the function has a deduced return type, substitute it for a dependent
3611 // type so that we treat it as a non-deduced context in what follows.
3612 bool HasDeducedReturnType = false;
3613 if (getLangOpts().CPlusPlus14 && InOverloadResolution &&
3614 Function->getReturnType()->getContainedAutoType()) {
3615 FunctionType = SubstAutoType(FunctionType, Context.DependentTy);
3616 HasDeducedReturnType = true;
3619 if (!ArgFunctionType.isNull()) {
3620 unsigned TDF = TDF_TopLevelParameterTypeList;
3621 if (InOverloadResolution) TDF |= TDF_InOverloadResolution;
3622 // Deduce template arguments from the function type.
3623 if (TemplateDeductionResult Result
3624 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3625 FunctionType, ArgFunctionType,
3626 Info, Deduced, TDF))
3630 if (TemplateDeductionResult Result
3631 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
3632 NumExplicitlySpecified,
3633 Specialization, Info))
3636 // If the function has a deduced return type, deduce it now, so we can check
3637 // that the deduced function type matches the requested type.
3638 if (HasDeducedReturnType &&
3639 Specialization->getReturnType()->isUndeducedType() &&
3640 DeduceReturnType(Specialization, Info.getLocation(), false))
3641 return TDK_MiscellaneousDeductionFailure;
3643 // If the requested function type does not match the actual type of the
3644 // specialization with respect to arguments of compatible pointer to function
3645 // types, template argument deduction fails.
3646 if (!ArgFunctionType.isNull()) {
3647 if (InOverloadResolution && !isSameOrCompatibleFunctionType(
3648 Context.getCanonicalType(Specialization->getType()),
3649 Context.getCanonicalType(ArgFunctionType)))
3650 return TDK_MiscellaneousDeductionFailure;
3651 else if(!InOverloadResolution &&
3652 !Context.hasSameType(Specialization->getType(), ArgFunctionType))
3653 return TDK_MiscellaneousDeductionFailure;
3659 /// \brief Given a function declaration (e.g. a generic lambda conversion
3660 /// function) that contains an 'auto' in its result type, substitute it
3661 /// with TypeToReplaceAutoWith. Be careful to pass in the type you want
3662 /// to replace 'auto' with and not the actual result type you want
3663 /// to set the function to.
3665 SubstAutoWithinFunctionReturnType(FunctionDecl *F,
3666 QualType TypeToReplaceAutoWith, Sema &S) {
3667 assert(!TypeToReplaceAutoWith->getContainedAutoType());
3668 QualType AutoResultType = F->getReturnType();
3669 assert(AutoResultType->getContainedAutoType());
3670 QualType DeducedResultType = S.SubstAutoType(AutoResultType,
3671 TypeToReplaceAutoWith);
3672 S.Context.adjustDeducedFunctionResultType(F, DeducedResultType);
3675 /// \brief Given a specialized conversion operator of a generic lambda
3676 /// create the corresponding specializations of the call operator and
3677 /// the static-invoker. If the return type of the call operator is auto,
3678 /// deduce its return type and check if that matches the
3679 /// return type of the destination function ptr.
3681 static inline Sema::TemplateDeductionResult
3682 SpecializeCorrespondingLambdaCallOperatorAndInvoker(
3683 CXXConversionDecl *ConversionSpecialized,
3684 SmallVectorImpl<DeducedTemplateArgument> &DeducedArguments,
3685 QualType ReturnTypeOfDestFunctionPtr,
3686 TemplateDeductionInfo &TDInfo,
3689 CXXRecordDecl *LambdaClass = ConversionSpecialized->getParent();
3690 assert(LambdaClass && LambdaClass->isGenericLambda());
3692 CXXMethodDecl *CallOpGeneric = LambdaClass->getLambdaCallOperator();
3693 QualType CallOpResultType = CallOpGeneric->getReturnType();
3694 const bool GenericLambdaCallOperatorHasDeducedReturnType =
3695 CallOpResultType->getContainedAutoType();
3697 FunctionTemplateDecl *CallOpTemplate =
3698 CallOpGeneric->getDescribedFunctionTemplate();
3700 FunctionDecl *CallOpSpecialized = nullptr;
3701 // Use the deduced arguments of the conversion function, to specialize our
3702 // generic lambda's call operator.
3703 if (Sema::TemplateDeductionResult Result
3704 = S.FinishTemplateArgumentDeduction(CallOpTemplate,
3706 0, CallOpSpecialized, TDInfo))
3709 // If we need to deduce the return type, do so (instantiates the callop).
3710 if (GenericLambdaCallOperatorHasDeducedReturnType &&
3711 CallOpSpecialized->getReturnType()->isUndeducedType())
3712 S.DeduceReturnType(CallOpSpecialized,
3713 CallOpSpecialized->getPointOfInstantiation(),
3716 // Check to see if the return type of the destination ptr-to-function
3717 // matches the return type of the call operator.
3718 if (!S.Context.hasSameType(CallOpSpecialized->getReturnType(),
3719 ReturnTypeOfDestFunctionPtr))
3720 return Sema::TDK_NonDeducedMismatch;
3721 // Since we have succeeded in matching the source and destination
3722 // ptr-to-functions (now including return type), and have successfully
3723 // specialized our corresponding call operator, we are ready to
3724 // specialize the static invoker with the deduced arguments of our
3726 FunctionDecl *InvokerSpecialized = nullptr;
3727 FunctionTemplateDecl *InvokerTemplate = LambdaClass->
3728 getLambdaStaticInvoker()->getDescribedFunctionTemplate();
3731 Sema::TemplateDeductionResult LLVM_ATTRIBUTE_UNUSED Result =
3733 S.FinishTemplateArgumentDeduction(InvokerTemplate, DeducedArguments, 0,
3734 InvokerSpecialized, TDInfo);
3735 assert(Result == Sema::TDK_Success &&
3736 "If the call operator succeeded so should the invoker!");
3737 // Set the result type to match the corresponding call operator
3738 // specialization's result type.
3739 if (GenericLambdaCallOperatorHasDeducedReturnType &&
3740 InvokerSpecialized->getReturnType()->isUndeducedType()) {
3741 // Be sure to get the type to replace 'auto' with and not
3742 // the full result type of the call op specialization
3743 // to substitute into the 'auto' of the invoker and conversion
3746 // int* (*fp)(int*) = [](auto* a) -> auto* { return a; };
3747 // We don't want to subst 'int*' into 'auto' to get int**.
3749 QualType TypeToReplaceAutoWith = CallOpSpecialized->getReturnType()
3750 ->getContainedAutoType()
3752 SubstAutoWithinFunctionReturnType(InvokerSpecialized,
3753 TypeToReplaceAutoWith, S);
3754 SubstAutoWithinFunctionReturnType(ConversionSpecialized,
3755 TypeToReplaceAutoWith, S);
3758 // Ensure that static invoker doesn't have a const qualifier.
3759 // FIXME: When creating the InvokerTemplate in SemaLambda.cpp
3760 // do not use the CallOperator's TypeSourceInfo which allows
3761 // the const qualifier to leak through.
3762 const FunctionProtoType *InvokerFPT = InvokerSpecialized->
3763 getType().getTypePtr()->castAs<FunctionProtoType>();
3764 FunctionProtoType::ExtProtoInfo EPI = InvokerFPT->getExtProtoInfo();
3766 InvokerSpecialized->setType(S.Context.getFunctionType(
3767 InvokerFPT->getReturnType(), InvokerFPT->getParamTypes(), EPI));
3768 return Sema::TDK_Success;
3770 /// \brief Deduce template arguments for a templated conversion
3771 /// function (C++ [temp.deduct.conv]) and, if successful, produce a
3772 /// conversion function template specialization.
3773 Sema::TemplateDeductionResult
3774 Sema::DeduceTemplateArguments(FunctionTemplateDecl *ConversionTemplate,
3776 CXXConversionDecl *&Specialization,
3777 TemplateDeductionInfo &Info) {
3778 if (ConversionTemplate->isInvalidDecl())
3781 CXXConversionDecl *ConversionGeneric
3782 = cast<CXXConversionDecl>(ConversionTemplate->getTemplatedDecl());
3784 QualType FromType = ConversionGeneric->getConversionType();
3786 // Canonicalize the types for deduction.
3787 QualType P = Context.getCanonicalType(FromType);
3788 QualType A = Context.getCanonicalType(ToType);
3790 // C++0x [temp.deduct.conv]p2:
3791 // If P is a reference type, the type referred to by P is used for
3793 if (const ReferenceType *PRef = P->getAs<ReferenceType>())
3794 P = PRef->getPointeeType();
3796 // C++0x [temp.deduct.conv]p4:
3797 // [...] If A is a reference type, the type referred to by A is used
3798 // for type deduction.
3799 if (const ReferenceType *ARef = A->getAs<ReferenceType>())
3800 A = ARef->getPointeeType().getUnqualifiedType();
3801 // C++ [temp.deduct.conv]p3:
3803 // If A is not a reference type:
3805 assert(!A->isReferenceType() && "Reference types were handled above");
3807 // - If P is an array type, the pointer type produced by the
3808 // array-to-pointer standard conversion (4.2) is used in place
3809 // of P for type deduction; otherwise,
3810 if (P->isArrayType())
3811 P = Context.getArrayDecayedType(P);
3812 // - If P is a function type, the pointer type produced by the
3813 // function-to-pointer standard conversion (4.3) is used in
3814 // place of P for type deduction; otherwise,
3815 else if (P->isFunctionType())
3816 P = Context.getPointerType(P);
3817 // - If P is a cv-qualified type, the top level cv-qualifiers of
3818 // P's type are ignored for type deduction.
3820 P = P.getUnqualifiedType();
3822 // C++0x [temp.deduct.conv]p4:
3823 // If A is a cv-qualified type, the top level cv-qualifiers of A's
3824 // type are ignored for type deduction. If A is a reference type, the type
3825 // referred to by A is used for type deduction.
3826 A = A.getUnqualifiedType();
3829 // Unevaluated SFINAE context.
3830 EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
3831 SFINAETrap Trap(*this);
3833 // C++ [temp.deduct.conv]p1:
3834 // Template argument deduction is done by comparing the return
3835 // type of the template conversion function (call it P) with the
3836 // type that is required as the result of the conversion (call it
3837 // A) as described in 14.8.2.4.
3838 TemplateParameterList *TemplateParams
3839 = ConversionTemplate->getTemplateParameters();
3840 SmallVector<DeducedTemplateArgument, 4> Deduced;
3841 Deduced.resize(TemplateParams->size());
3843 // C++0x [temp.deduct.conv]p4:
3844 // In general, the deduction process attempts to find template
3845 // argument values that will make the deduced A identical to
3846 // A. However, there are two cases that allow a difference:
3848 // - If the original A is a reference type, A can be more
3849 // cv-qualified than the deduced A (i.e., the type referred to
3850 // by the reference)
3851 if (ToType->isReferenceType())
3852 TDF |= TDF_ParamWithReferenceType;
3853 // - The deduced A can be another pointer or pointer to member
3854 // type that can be converted to A via a qualification
3857 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when
3858 // both P and A are pointers or member pointers. In this case, we
3859 // just ignore cv-qualifiers completely).
3860 if ((P->isPointerType() && A->isPointerType()) ||
3861 (P->isMemberPointerType() && A->isMemberPointerType()))
3862 TDF |= TDF_IgnoreQualifiers;
3863 if (TemplateDeductionResult Result
3864 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3865 P, A, Info, Deduced, TDF))
3868 // Create an Instantiation Scope for finalizing the operator.
3869 LocalInstantiationScope InstScope(*this);
3870 // Finish template argument deduction.
3871 FunctionDecl *ConversionSpecialized = nullptr;
3872 TemplateDeductionResult Result
3873 = FinishTemplateArgumentDeduction(ConversionTemplate, Deduced, 0,
3874 ConversionSpecialized, Info);
3875 Specialization = cast_or_null<CXXConversionDecl>(ConversionSpecialized);
3877 // If the conversion operator is being invoked on a lambda closure to convert
3878 // to a ptr-to-function, use the deduced arguments from the conversion
3879 // function to specialize the corresponding call operator.
3880 // e.g., int (*fp)(int) = [](auto a) { return a; };
3881 if (Result == TDK_Success && isLambdaConversionOperator(ConversionGeneric)) {
3883 // Get the return type of the destination ptr-to-function we are converting
3884 // to. This is necessary for matching the lambda call operator's return
3885 // type to that of the destination ptr-to-function's return type.
3886 assert(A->isPointerType() &&
3887 "Can only convert from lambda to ptr-to-function");
3888 const FunctionType *ToFunType =
3889 A->getPointeeType().getTypePtr()->getAs<FunctionType>();
3890 const QualType DestFunctionPtrReturnType = ToFunType->getReturnType();
3892 // Create the corresponding specializations of the call operator and
3893 // the static-invoker; and if the return type is auto,
3894 // deduce the return type and check if it matches the
3895 // DestFunctionPtrReturnType.
3897 // auto L = [](auto a) { return f(a); };
3898 // int (*fp)(int) = L;
3899 // char (*fp2)(int) = L; <-- Not OK.
3901 Result = SpecializeCorrespondingLambdaCallOperatorAndInvoker(
3902 Specialization, Deduced, DestFunctionPtrReturnType,
3908 /// \brief Deduce template arguments for a function template when there is
3909 /// nothing to deduce against (C++0x [temp.arg.explicit]p3).
3911 /// \param FunctionTemplate the function template for which we are performing
3912 /// template argument deduction.
3914 /// \param ExplicitTemplateArgs the explicitly-specified template
3917 /// \param Specialization if template argument deduction was successful,
3918 /// this will be set to the function template specialization produced by
3919 /// template argument deduction.
3921 /// \param Info the argument will be updated to provide additional information
3922 /// about template argument deduction.
3924 /// \returns the result of template argument deduction.
3925 Sema::TemplateDeductionResult
3926 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3927 TemplateArgumentListInfo *ExplicitTemplateArgs,
3928 FunctionDecl *&Specialization,
3929 TemplateDeductionInfo &Info,
3930 bool InOverloadResolution) {
3931 return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs,
3932 QualType(), Specialization, Info,
3933 InOverloadResolution);
3937 /// Substitute the 'auto' type specifier within a type for a given replacement
3939 class SubstituteAutoTransform :
3940 public TreeTransform<SubstituteAutoTransform> {
3941 QualType Replacement;
3943 SubstituteAutoTransform(Sema &SemaRef, QualType Replacement)
3944 : TreeTransform<SubstituteAutoTransform>(SemaRef),
3945 Replacement(Replacement) {}
3947 QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) {
3948 // If we're building the type pattern to deduce against, don't wrap the
3949 // substituted type in an AutoType. Certain template deduction rules
3950 // apply only when a template type parameter appears directly (and not if
3951 // the parameter is found through desugaring). For instance:
3952 // auto &&lref = lvalue;
3953 // must transform into "rvalue reference to T" not "rvalue reference to
3954 // auto type deduced as T" in order for [temp.deduct.call]p3 to apply.
3955 if (!Replacement.isNull() && isa<TemplateTypeParmType>(Replacement)) {
3956 QualType Result = Replacement;
3957 TemplateTypeParmTypeLoc NewTL =
3958 TLB.push<TemplateTypeParmTypeLoc>(Result);
3959 NewTL.setNameLoc(TL.getNameLoc());
3963 !Replacement.isNull() && Replacement->isDependentType();
3965 SemaRef.Context.getAutoType(Dependent ? QualType() : Replacement,
3966 TL.getTypePtr()->getKeyword(),
3968 AutoTypeLoc NewTL = TLB.push<AutoTypeLoc>(Result);
3969 NewTL.setNameLoc(TL.getNameLoc());
3974 ExprResult TransformLambdaExpr(LambdaExpr *E) {
3975 // Lambdas never need to be transformed.
3979 QualType Apply(TypeLoc TL) {
3980 // Create some scratch storage for the transformed type locations.
3981 // FIXME: We're just going to throw this information away. Don't build it.
3983 TLB.reserve(TL.getFullDataSize());
3984 return TransformType(TLB, TL);
3989 Sema::DeduceAutoResult
3990 Sema::DeduceAutoType(TypeSourceInfo *Type, Expr *&Init, QualType &Result) {
3991 return DeduceAutoType(Type->getTypeLoc(), Init, Result);
3994 /// \brief Deduce the type for an auto type-specifier (C++11 [dcl.spec.auto]p6)
3996 /// \param Type the type pattern using the auto type-specifier.
3997 /// \param Init the initializer for the variable whose type is to be deduced.
3998 /// \param Result if type deduction was successful, this will be set to the
4000 Sema::DeduceAutoResult
4001 Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result) {
4002 if (Init->getType()->isNonOverloadPlaceholderType()) {
4003 ExprResult NonPlaceholder = CheckPlaceholderExpr(Init);
4004 if (NonPlaceholder.isInvalid())
4005 return DAR_FailedAlreadyDiagnosed;
4006 Init = NonPlaceholder.get();
4009 if (Init->isTypeDependent() || Type.getType()->isDependentType()) {
4010 Result = SubstituteAutoTransform(*this, Context.DependentTy).Apply(Type);
4011 assert(!Result.isNull() && "substituting DependentTy can't fail");
4012 return DAR_Succeeded;
4015 // If this is a 'decltype(auto)' specifier, do the decltype dance.
4016 // Since 'decltype(auto)' can only occur at the top of the type, we
4017 // don't need to go digging for it.
4018 if (const AutoType *AT = Type.getType()->getAs<AutoType>()) {
4019 if (AT->isDecltypeAuto()) {
4020 if (isa<InitListExpr>(Init)) {
4021 Diag(Init->getLocStart(), diag::err_decltype_auto_initializer_list);
4022 return DAR_FailedAlreadyDiagnosed;
4025 QualType Deduced = BuildDecltypeType(Init, Init->getLocStart(), false);
4026 if (Deduced.isNull())
4027 return DAR_FailedAlreadyDiagnosed;
4028 // FIXME: Support a non-canonical deduced type for 'auto'.
4029 Deduced = Context.getCanonicalType(Deduced);
4030 Result = SubstituteAutoTransform(*this, Deduced).Apply(Type);
4031 if (Result.isNull())
4032 return DAR_FailedAlreadyDiagnosed;
4033 return DAR_Succeeded;
4034 } else if (!getLangOpts().CPlusPlus) {
4035 if (isa<InitListExpr>(Init)) {
4036 Diag(Init->getLocStart(), diag::err_auto_init_list_from_c);
4037 return DAR_FailedAlreadyDiagnosed;
4042 SourceLocation Loc = Init->getExprLoc();
4044 LocalInstantiationScope InstScope(*this);
4046 // Build template<class TemplParam> void Func(FuncParam);
4047 TemplateTypeParmDecl *TemplParam =
4048 TemplateTypeParmDecl::Create(Context, nullptr, SourceLocation(), Loc, 0, 0,
4049 nullptr, false, false);
4050 QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0);
4051 NamedDecl *TemplParamPtr = TemplParam;
4052 FixedSizeTemplateParameterListStorage<1> TemplateParamsSt(
4053 Loc, Loc, TemplParamPtr, Loc);
4055 QualType FuncParam = SubstituteAutoTransform(*this, TemplArg).Apply(Type);
4056 assert(!FuncParam.isNull() &&
4057 "substituting template parameter for 'auto' failed");
4059 // Deduce type of TemplParam in Func(Init)
4060 SmallVector<DeducedTemplateArgument, 1> Deduced;
4062 QualType InitType = Init->getType();
4065 TemplateDeductionInfo Info(Loc);
4067 InitListExpr *InitList = dyn_cast<InitListExpr>(Init);
4069 for (unsigned i = 0, e = InitList->getNumInits(); i < e; ++i) {
4070 if (DeduceTemplateArgumentByListElement(*this, TemplateParamsSt.get(),
4071 TemplArg, InitList->getInit(i),
4072 Info, Deduced, TDF))
4076 if (!getLangOpts().CPlusPlus && Init->refersToBitField()) {
4077 Diag(Loc, diag::err_auto_bitfield);
4078 return DAR_FailedAlreadyDiagnosed;
4081 if (AdjustFunctionParmAndArgTypesForDeduction(
4082 *this, TemplateParamsSt.get(), FuncParam, InitType, Init, TDF))
4085 if (DeduceTemplateArgumentsByTypeMatch(*this, TemplateParamsSt.get(),
4086 FuncParam, InitType, Info, Deduced,
4091 if (Deduced[0].getKind() != TemplateArgument::Type)
4094 QualType DeducedType = Deduced[0].getAsType();
4097 DeducedType = BuildStdInitializerList(DeducedType, Loc);
4098 if (DeducedType.isNull())
4099 return DAR_FailedAlreadyDiagnosed;
4102 Result = SubstituteAutoTransform(*this, DeducedType).Apply(Type);
4103 if (Result.isNull())
4104 return DAR_FailedAlreadyDiagnosed;
4106 // Check that the deduced argument type is compatible with the original
4107 // argument type per C++ [temp.deduct.call]p4.
4108 if (!InitList && !Result.isNull() &&
4109 CheckOriginalCallArgDeduction(*this,
4110 Sema::OriginalCallArg(FuncParam,0,InitType),
4112 Result = QualType();
4116 return DAR_Succeeded;
4119 QualType Sema::SubstAutoType(QualType TypeWithAuto,
4120 QualType TypeToReplaceAuto) {
4121 return SubstituteAutoTransform(*this, TypeToReplaceAuto).
4122 TransformType(TypeWithAuto);
4125 TypeSourceInfo* Sema::SubstAutoTypeSourceInfo(TypeSourceInfo *TypeWithAuto,
4126 QualType TypeToReplaceAuto) {
4127 return SubstituteAutoTransform(*this, TypeToReplaceAuto).
4128 TransformType(TypeWithAuto);
4131 void Sema::DiagnoseAutoDeductionFailure(VarDecl *VDecl, Expr *Init) {
4132 if (isa<InitListExpr>(Init))
4133 Diag(VDecl->getLocation(),
4134 VDecl->isInitCapture()
4135 ? diag::err_init_capture_deduction_failure_from_init_list
4136 : diag::err_auto_var_deduction_failure_from_init_list)
4137 << VDecl->getDeclName() << VDecl->getType() << Init->getSourceRange();
4139 Diag(VDecl->getLocation(),
4140 VDecl->isInitCapture() ? diag::err_init_capture_deduction_failure
4141 : diag::err_auto_var_deduction_failure)
4142 << VDecl->getDeclName() << VDecl->getType() << Init->getType()
4143 << Init->getSourceRange();
4146 bool Sema::DeduceReturnType(FunctionDecl *FD, SourceLocation Loc,
4148 assert(FD->getReturnType()->isUndeducedType());
4150 if (FD->getTemplateInstantiationPattern())
4151 InstantiateFunctionDefinition(Loc, FD);
4153 bool StillUndeduced = FD->getReturnType()->isUndeducedType();
4154 if (StillUndeduced && Diagnose && !FD->isInvalidDecl()) {
4155 Diag(Loc, diag::err_auto_fn_used_before_defined) << FD;
4156 Diag(FD->getLocation(), diag::note_callee_decl) << FD;
4159 return StillUndeduced;
4163 MarkUsedTemplateParameters(ASTContext &Ctx, QualType T,
4166 llvm::SmallBitVector &Deduced);
4168 /// \brief If this is a non-static member function,
4170 AddImplicitObjectParameterType(ASTContext &Context,
4171 CXXMethodDecl *Method,
4172 SmallVectorImpl<QualType> &ArgTypes) {
4173 // C++11 [temp.func.order]p3:
4174 // [...] The new parameter is of type "reference to cv A," where cv are
4175 // the cv-qualifiers of the function template (if any) and A is
4176 // the class of which the function template is a member.
4178 // The standard doesn't say explicitly, but we pick the appropriate kind of
4179 // reference type based on [over.match.funcs]p4.
4180 QualType ArgTy = Context.getTypeDeclType(Method->getParent());
4181 ArgTy = Context.getQualifiedType(ArgTy,
4182 Qualifiers::fromCVRMask(Method->getTypeQualifiers()));
4183 if (Method->getRefQualifier() == RQ_RValue)
4184 ArgTy = Context.getRValueReferenceType(ArgTy);
4186 ArgTy = Context.getLValueReferenceType(ArgTy);
4187 ArgTypes.push_back(ArgTy);
4190 /// \brief Determine whether the function template \p FT1 is at least as
4191 /// specialized as \p FT2.
4192 static bool isAtLeastAsSpecializedAs(Sema &S,
4194 FunctionTemplateDecl *FT1,
4195 FunctionTemplateDecl *FT2,
4196 TemplatePartialOrderingContext TPOC,
4197 unsigned NumCallArguments1) {
4198 FunctionDecl *FD1 = FT1->getTemplatedDecl();
4199 FunctionDecl *FD2 = FT2->getTemplatedDecl();
4200 const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>();
4201 const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>();
4203 assert(Proto1 && Proto2 && "Function templates must have prototypes");
4204 TemplateParameterList *TemplateParams = FT2->getTemplateParameters();
4205 SmallVector<DeducedTemplateArgument, 4> Deduced;
4206 Deduced.resize(TemplateParams->size());
4208 // C++0x [temp.deduct.partial]p3:
4209 // The types used to determine the ordering depend on the context in which
4210 // the partial ordering is done:
4211 TemplateDeductionInfo Info(Loc);
4212 SmallVector<QualType, 4> Args2;
4215 // - In the context of a function call, the function parameter types are
4217 CXXMethodDecl *Method1 = dyn_cast<CXXMethodDecl>(FD1);
4218 CXXMethodDecl *Method2 = dyn_cast<CXXMethodDecl>(FD2);
4220 // C++11 [temp.func.order]p3:
4221 // [...] If only one of the function templates is a non-static
4222 // member, that function template is considered to have a new
4223 // first parameter inserted in its function parameter list. The
4224 // new parameter is of type "reference to cv A," where cv are
4225 // the cv-qualifiers of the function template (if any) and A is
4226 // the class of which the function template is a member.
4228 // Note that we interpret this to mean "if one of the function
4229 // templates is a non-static member and the other is a non-member";
4230 // otherwise, the ordering rules for static functions against non-static
4231 // functions don't make any sense.
4233 // C++98/03 doesn't have this provision but we've extended DR532 to cover
4234 // it as wording was broken prior to it.
4235 SmallVector<QualType, 4> Args1;
4237 unsigned NumComparedArguments = NumCallArguments1;
4239 if (!Method2 && Method1 && !Method1->isStatic()) {
4240 // Compare 'this' from Method1 against first parameter from Method2.
4241 AddImplicitObjectParameterType(S.Context, Method1, Args1);
4242 ++NumComparedArguments;
4243 } else if (!Method1 && Method2 && !Method2->isStatic()) {
4244 // Compare 'this' from Method2 against first parameter from Method1.
4245 AddImplicitObjectParameterType(S.Context, Method2, Args2);
4248 Args1.insert(Args1.end(), Proto1->param_type_begin(),
4249 Proto1->param_type_end());
4250 Args2.insert(Args2.end(), Proto2->param_type_begin(),
4251 Proto2->param_type_end());
4253 // C++ [temp.func.order]p5:
4254 // The presence of unused ellipsis and default arguments has no effect on
4255 // the partial ordering of function templates.
4256 if (Args1.size() > NumComparedArguments)
4257 Args1.resize(NumComparedArguments);
4258 if (Args2.size() > NumComparedArguments)
4259 Args2.resize(NumComparedArguments);
4260 if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(),
4261 Args1.data(), Args1.size(), Info, Deduced,
4262 TDF_None, /*PartialOrdering=*/true))
4268 case TPOC_Conversion:
4269 // - In the context of a call to a conversion operator, the return types
4270 // of the conversion function templates are used.
4271 if (DeduceTemplateArgumentsByTypeMatch(
4272 S, TemplateParams, Proto2->getReturnType(), Proto1->getReturnType(),
4273 Info, Deduced, TDF_None,
4274 /*PartialOrdering=*/true))
4279 // - In other contexts (14.6.6.2) the function template's function type
4281 if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
4282 FD2->getType(), FD1->getType(),
4283 Info, Deduced, TDF_None,
4284 /*PartialOrdering=*/true))
4289 // C++0x [temp.deduct.partial]p11:
4290 // In most cases, all template parameters must have values in order for
4291 // deduction to succeed, but for partial ordering purposes a template
4292 // parameter may remain without a value provided it is not used in the
4293 // types being used for partial ordering. [ Note: a template parameter used
4294 // in a non-deduced context is considered used. -end note]
4295 unsigned ArgIdx = 0, NumArgs = Deduced.size();
4296 for (; ArgIdx != NumArgs; ++ArgIdx)
4297 if (Deduced[ArgIdx].isNull())
4300 if (ArgIdx == NumArgs) {
4301 // All template arguments were deduced. FT1 is at least as specialized
4306 // Figure out which template parameters were used.
4307 llvm::SmallBitVector UsedParameters(TemplateParams->size());
4310 for (unsigned I = 0, N = Args2.size(); I != N; ++I)
4311 ::MarkUsedTemplateParameters(S.Context, Args2[I], false,
4312 TemplateParams->getDepth(),
4316 case TPOC_Conversion:
4317 ::MarkUsedTemplateParameters(S.Context, Proto2->getReturnType(), false,
4318 TemplateParams->getDepth(), UsedParameters);
4322 ::MarkUsedTemplateParameters(S.Context, FD2->getType(), false,
4323 TemplateParams->getDepth(),
4328 for (; ArgIdx != NumArgs; ++ArgIdx)
4329 // If this argument had no value deduced but was used in one of the types
4330 // used for partial ordering, then deduction fails.
4331 if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx])
4337 /// \brief Determine whether this a function template whose parameter-type-list
4338 /// ends with a function parameter pack.
4339 static bool isVariadicFunctionTemplate(FunctionTemplateDecl *FunTmpl) {
4340 FunctionDecl *Function = FunTmpl->getTemplatedDecl();
4341 unsigned NumParams = Function->getNumParams();
4345 ParmVarDecl *Last = Function->getParamDecl(NumParams - 1);
4346 if (!Last->isParameterPack())
4349 // Make sure that no previous parameter is a parameter pack.
4350 while (--NumParams > 0) {
4351 if (Function->getParamDecl(NumParams - 1)->isParameterPack())
4358 /// \brief Returns the more specialized function template according
4359 /// to the rules of function template partial ordering (C++ [temp.func.order]).
4361 /// \param FT1 the first function template
4363 /// \param FT2 the second function template
4365 /// \param TPOC the context in which we are performing partial ordering of
4366 /// function templates.
4368 /// \param NumCallArguments1 The number of arguments in the call to FT1, used
4369 /// only when \c TPOC is \c TPOC_Call.
4371 /// \param NumCallArguments2 The number of arguments in the call to FT2, used
4372 /// only when \c TPOC is \c TPOC_Call.
4374 /// \returns the more specialized function template. If neither
4375 /// template is more specialized, returns NULL.
4376 FunctionTemplateDecl *
4377 Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1,
4378 FunctionTemplateDecl *FT2,
4380 TemplatePartialOrderingContext TPOC,
4381 unsigned NumCallArguments1,
4382 unsigned NumCallArguments2) {
4383 bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC,
4385 bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC,
4388 if (Better1 != Better2) // We have a clear winner
4389 return Better1 ? FT1 : FT2;
4391 if (!Better1 && !Better2) // Neither is better than the other
4394 // FIXME: This mimics what GCC implements, but doesn't match up with the
4395 // proposed resolution for core issue 692. This area needs to be sorted out,
4396 // but for now we attempt to maintain compatibility.
4397 bool Variadic1 = isVariadicFunctionTemplate(FT1);
4398 bool Variadic2 = isVariadicFunctionTemplate(FT2);
4399 if (Variadic1 != Variadic2)
4400 return Variadic1? FT2 : FT1;
4405 /// \brief Determine if the two templates are equivalent.
4406 static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) {
4413 return T1->getCanonicalDecl() == T2->getCanonicalDecl();
4416 /// \brief Retrieve the most specialized of the given function template
4417 /// specializations.
4419 /// \param SpecBegin the start iterator of the function template
4420 /// specializations that we will be comparing.
4422 /// \param SpecEnd the end iterator of the function template
4423 /// specializations, paired with \p SpecBegin.
4425 /// \param Loc the location where the ambiguity or no-specializations
4426 /// diagnostic should occur.
4428 /// \param NoneDiag partial diagnostic used to diagnose cases where there are
4429 /// no matching candidates.
4431 /// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one
4434 /// \param CandidateDiag partial diagnostic used for each function template
4435 /// specialization that is a candidate in the ambiguous ordering. One parameter
4436 /// in this diagnostic should be unbound, which will correspond to the string
4437 /// describing the template arguments for the function template specialization.
4439 /// \returns the most specialized function template specialization, if
4440 /// found. Otherwise, returns SpecEnd.
4441 UnresolvedSetIterator Sema::getMostSpecialized(
4442 UnresolvedSetIterator SpecBegin, UnresolvedSetIterator SpecEnd,
4443 TemplateSpecCandidateSet &FailedCandidates,
4444 SourceLocation Loc, const PartialDiagnostic &NoneDiag,
4445 const PartialDiagnostic &AmbigDiag, const PartialDiagnostic &CandidateDiag,
4446 bool Complain, QualType TargetType) {
4447 if (SpecBegin == SpecEnd) {
4449 Diag(Loc, NoneDiag);
4450 FailedCandidates.NoteCandidates(*this, Loc);
4455 if (SpecBegin + 1 == SpecEnd)
4458 // Find the function template that is better than all of the templates it
4459 // has been compared to.
4460 UnresolvedSetIterator Best = SpecBegin;
4461 FunctionTemplateDecl *BestTemplate
4462 = cast<FunctionDecl>(*Best)->getPrimaryTemplate();
4463 assert(BestTemplate && "Not a function template specialization?");
4464 for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) {
4465 FunctionTemplateDecl *Challenger
4466 = cast<FunctionDecl>(*I)->getPrimaryTemplate();
4467 assert(Challenger && "Not a function template specialization?");
4468 if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
4469 Loc, TPOC_Other, 0, 0),
4472 BestTemplate = Challenger;
4476 // Make sure that the "best" function template is more specialized than all
4478 bool Ambiguous = false;
4479 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
4480 FunctionTemplateDecl *Challenger
4481 = cast<FunctionDecl>(*I)->getPrimaryTemplate();
4483 !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
4484 Loc, TPOC_Other, 0, 0),
4492 // We found an answer. Return it.
4496 // Diagnose the ambiguity.
4498 Diag(Loc, AmbigDiag);
4500 // FIXME: Can we order the candidates in some sane way?
4501 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
4502 PartialDiagnostic PD = CandidateDiag;
4503 PD << getTemplateArgumentBindingsText(
4504 cast<FunctionDecl>(*I)->getPrimaryTemplate()->getTemplateParameters(),
4505 *cast<FunctionDecl>(*I)->getTemplateSpecializationArgs());
4506 if (!TargetType.isNull())
4507 HandleFunctionTypeMismatch(PD, cast<FunctionDecl>(*I)->getType(),
4509 Diag((*I)->getLocation(), PD);
4516 /// \brief Returns the more specialized class template partial specialization
4517 /// according to the rules of partial ordering of class template partial
4518 /// specializations (C++ [temp.class.order]).
4520 /// \param PS1 the first class template partial specialization
4522 /// \param PS2 the second class template partial specialization
4524 /// \returns the more specialized class template partial specialization. If
4525 /// neither partial specialization is more specialized, returns NULL.
4526 ClassTemplatePartialSpecializationDecl *
4527 Sema::getMoreSpecializedPartialSpecialization(
4528 ClassTemplatePartialSpecializationDecl *PS1,
4529 ClassTemplatePartialSpecializationDecl *PS2,
4530 SourceLocation Loc) {
4531 // C++ [temp.class.order]p1:
4532 // For two class template partial specializations, the first is at least as
4533 // specialized as the second if, given the following rewrite to two
4534 // function templates, the first function template is at least as
4535 // specialized as the second according to the ordering rules for function
4536 // templates (14.6.6.2):
4537 // - the first function template has the same template parameters as the
4538 // first partial specialization and has a single function parameter
4539 // whose type is a class template specialization with the template
4540 // arguments of the first partial specialization, and
4541 // - the second function template has the same template parameters as the
4542 // second partial specialization and has a single function parameter
4543 // whose type is a class template specialization with the template
4544 // arguments of the second partial specialization.
4546 // Rather than synthesize function templates, we merely perform the
4547 // equivalent partial ordering by performing deduction directly on
4548 // the template arguments of the class template partial
4549 // specializations. This computation is slightly simpler than the
4550 // general problem of function template partial ordering, because
4551 // class template partial specializations are more constrained. We
4552 // know that every template parameter is deducible from the class
4553 // template partial specialization's template arguments, for
4555 SmallVector<DeducedTemplateArgument, 4> Deduced;
4556 TemplateDeductionInfo Info(Loc);
4558 QualType PT1 = PS1->getInjectedSpecializationType();
4559 QualType PT2 = PS2->getInjectedSpecializationType();
4561 // Determine whether PS1 is at least as specialized as PS2
4562 Deduced.resize(PS2->getTemplateParameters()->size());
4563 bool Better1 = !DeduceTemplateArgumentsByTypeMatch(*this,
4564 PS2->getTemplateParameters(),
4565 PT2, PT1, Info, Deduced, TDF_None,
4566 /*PartialOrdering=*/true);
4568 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),Deduced.end());
4569 InstantiatingTemplate Inst(*this, Loc, PS2, DeducedArgs, Info);
4570 Better1 = !::FinishTemplateArgumentDeduction(
4571 *this, PS2, PS1->getTemplateArgs(), Deduced, Info);
4574 // Determine whether PS2 is at least as specialized as PS1
4576 Deduced.resize(PS1->getTemplateParameters()->size());
4577 bool Better2 = !DeduceTemplateArgumentsByTypeMatch(
4578 *this, PS1->getTemplateParameters(), PT1, PT2, Info, Deduced, TDF_None,
4579 /*PartialOrdering=*/true);
4581 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),
4583 InstantiatingTemplate Inst(*this, Loc, PS1, DeducedArgs, Info);
4584 Better2 = !::FinishTemplateArgumentDeduction(
4585 *this, PS1, PS2->getTemplateArgs(), Deduced, Info);
4588 if (Better1 == Better2)
4591 return Better1 ? PS1 : PS2;
4594 /// TODO: Unify with ClassTemplatePartialSpecializationDecl version?
4595 /// May require unifying ClassTemplate(Partial)SpecializationDecl and
4596 /// VarTemplate(Partial)SpecializationDecl with a new data
4597 /// structure Template(Partial)SpecializationDecl, and
4598 /// using Template(Partial)SpecializationDecl as input type.
4599 VarTemplatePartialSpecializationDecl *
4600 Sema::getMoreSpecializedPartialSpecialization(
4601 VarTemplatePartialSpecializationDecl *PS1,
4602 VarTemplatePartialSpecializationDecl *PS2, SourceLocation Loc) {
4603 SmallVector<DeducedTemplateArgument, 4> Deduced;
4604 TemplateDeductionInfo Info(Loc);
4606 assert(PS1->getSpecializedTemplate() == PS2->getSpecializedTemplate() &&
4607 "the partial specializations being compared should specialize"
4608 " the same template.");
4609 TemplateName Name(PS1->getSpecializedTemplate());
4610 TemplateName CanonTemplate = Context.getCanonicalTemplateName(Name);
4611 QualType PT1 = Context.getTemplateSpecializationType(
4612 CanonTemplate, PS1->getTemplateArgs().data(),
4613 PS1->getTemplateArgs().size());
4614 QualType PT2 = Context.getTemplateSpecializationType(
4615 CanonTemplate, PS2->getTemplateArgs().data(),
4616 PS2->getTemplateArgs().size());
4618 // Determine whether PS1 is at least as specialized as PS2
4619 Deduced.resize(PS2->getTemplateParameters()->size());
4620 bool Better1 = !DeduceTemplateArgumentsByTypeMatch(
4621 *this, PS2->getTemplateParameters(), PT2, PT1, Info, Deduced, TDF_None,
4622 /*PartialOrdering=*/true);
4624 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),
4626 InstantiatingTemplate Inst(*this, Loc, PS2, DeducedArgs, Info);
4627 Better1 = !::FinishTemplateArgumentDeduction(*this, PS2,
4628 PS1->getTemplateArgs(),
4632 // Determine whether PS2 is at least as specialized as PS1
4634 Deduced.resize(PS1->getTemplateParameters()->size());
4635 bool Better2 = !DeduceTemplateArgumentsByTypeMatch(*this,
4636 PS1->getTemplateParameters(),
4637 PT1, PT2, Info, Deduced, TDF_None,
4638 /*PartialOrdering=*/true);
4640 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),Deduced.end());
4641 InstantiatingTemplate Inst(*this, Loc, PS1, DeducedArgs, Info);
4642 Better2 = !::FinishTemplateArgumentDeduction(*this, PS1,
4643 PS2->getTemplateArgs(),
4647 if (Better1 == Better2)
4650 return Better1? PS1 : PS2;
4654 MarkUsedTemplateParameters(ASTContext &Ctx,
4655 const TemplateArgument &TemplateArg,
4658 llvm::SmallBitVector &Used);
4660 /// \brief Mark the template parameters that are used by the given
4663 MarkUsedTemplateParameters(ASTContext &Ctx,
4667 llvm::SmallBitVector &Used) {
4668 // We can deduce from a pack expansion.
4669 if (const PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(E))
4670 E = Expansion->getPattern();
4672 // Skip through any implicit casts we added while type-checking, and any
4673 // substitutions performed by template alias expansion.
4675 if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E))
4676 E = ICE->getSubExpr();
4677 else if (const SubstNonTypeTemplateParmExpr *Subst =
4678 dyn_cast<SubstNonTypeTemplateParmExpr>(E))
4679 E = Subst->getReplacement();
4684 // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to
4685 // find other occurrences of template parameters.
4686 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E);
4690 const NonTypeTemplateParmDecl *NTTP
4691 = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
4695 if (NTTP->getDepth() == Depth)
4696 Used[NTTP->getIndex()] = true;
4699 /// \brief Mark the template parameters that are used by the given
4700 /// nested name specifier.
4702 MarkUsedTemplateParameters(ASTContext &Ctx,
4703 NestedNameSpecifier *NNS,
4706 llvm::SmallBitVector &Used) {
4710 MarkUsedTemplateParameters(Ctx, NNS->getPrefix(), OnlyDeduced, Depth,
4712 MarkUsedTemplateParameters(Ctx, QualType(NNS->getAsType(), 0),
4713 OnlyDeduced, Depth, Used);
4716 /// \brief Mark the template parameters that are used by the given
4719 MarkUsedTemplateParameters(ASTContext &Ctx,
4723 llvm::SmallBitVector &Used) {
4724 if (TemplateDecl *Template = Name.getAsTemplateDecl()) {
4725 if (TemplateTemplateParmDecl *TTP
4726 = dyn_cast<TemplateTemplateParmDecl>(Template)) {
4727 if (TTP->getDepth() == Depth)
4728 Used[TTP->getIndex()] = true;
4733 if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName())
4734 MarkUsedTemplateParameters(Ctx, QTN->getQualifier(), OnlyDeduced,
4736 if (DependentTemplateName *DTN = Name.getAsDependentTemplateName())
4737 MarkUsedTemplateParameters(Ctx, DTN->getQualifier(), OnlyDeduced,
4741 /// \brief Mark the template parameters that are used by the given
4744 MarkUsedTemplateParameters(ASTContext &Ctx, QualType T,
4747 llvm::SmallBitVector &Used) {
4751 // Non-dependent types have nothing deducible
4752 if (!T->isDependentType())
4755 T = Ctx.getCanonicalType(T);
4756 switch (T->getTypeClass()) {
4758 MarkUsedTemplateParameters(Ctx,
4759 cast<PointerType>(T)->getPointeeType(),
4765 case Type::BlockPointer:
4766 MarkUsedTemplateParameters(Ctx,
4767 cast<BlockPointerType>(T)->getPointeeType(),
4773 case Type::LValueReference:
4774 case Type::RValueReference:
4775 MarkUsedTemplateParameters(Ctx,
4776 cast<ReferenceType>(T)->getPointeeType(),
4782 case Type::MemberPointer: {
4783 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr());
4784 MarkUsedTemplateParameters(Ctx, MemPtr->getPointeeType(), OnlyDeduced,
4786 MarkUsedTemplateParameters(Ctx, QualType(MemPtr->getClass(), 0),
4787 OnlyDeduced, Depth, Used);
4791 case Type::DependentSizedArray:
4792 MarkUsedTemplateParameters(Ctx,
4793 cast<DependentSizedArrayType>(T)->getSizeExpr(),
4794 OnlyDeduced, Depth, Used);
4795 // Fall through to check the element type
4797 case Type::ConstantArray:
4798 case Type::IncompleteArray:
4799 MarkUsedTemplateParameters(Ctx,
4800 cast<ArrayType>(T)->getElementType(),
4801 OnlyDeduced, Depth, Used);
4805 case Type::ExtVector:
4806 MarkUsedTemplateParameters(Ctx,
4807 cast<VectorType>(T)->getElementType(),
4808 OnlyDeduced, Depth, Used);
4811 case Type::DependentSizedExtVector: {
4812 const DependentSizedExtVectorType *VecType
4813 = cast<DependentSizedExtVectorType>(T);
4814 MarkUsedTemplateParameters(Ctx, VecType->getElementType(), OnlyDeduced,
4816 MarkUsedTemplateParameters(Ctx, VecType->getSizeExpr(), OnlyDeduced,
4821 case Type::FunctionProto: {
4822 const FunctionProtoType *Proto = cast<FunctionProtoType>(T);
4823 MarkUsedTemplateParameters(Ctx, Proto->getReturnType(), OnlyDeduced, Depth,
4825 for (unsigned I = 0, N = Proto->getNumParams(); I != N; ++I)
4826 MarkUsedTemplateParameters(Ctx, Proto->getParamType(I), OnlyDeduced,
4831 case Type::TemplateTypeParm: {
4832 const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T);
4833 if (TTP->getDepth() == Depth)
4834 Used[TTP->getIndex()] = true;
4838 case Type::SubstTemplateTypeParmPack: {
4839 const SubstTemplateTypeParmPackType *Subst
4840 = cast<SubstTemplateTypeParmPackType>(T);
4841 MarkUsedTemplateParameters(Ctx,
4842 QualType(Subst->getReplacedParameter(), 0),
4843 OnlyDeduced, Depth, Used);
4844 MarkUsedTemplateParameters(Ctx, Subst->getArgumentPack(),
4845 OnlyDeduced, Depth, Used);
4849 case Type::InjectedClassName:
4850 T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType();
4853 case Type::TemplateSpecialization: {
4854 const TemplateSpecializationType *Spec
4855 = cast<TemplateSpecializationType>(T);
4856 MarkUsedTemplateParameters(Ctx, Spec->getTemplateName(), OnlyDeduced,
4859 // C++0x [temp.deduct.type]p9:
4860 // If the template argument list of P contains a pack expansion that is
4861 // not the last template argument, the entire template argument list is a
4862 // non-deduced context.
4864 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs()))
4867 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
4868 MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth,
4875 MarkUsedTemplateParameters(Ctx,
4876 cast<ComplexType>(T)->getElementType(),
4877 OnlyDeduced, Depth, Used);
4882 MarkUsedTemplateParameters(Ctx,
4883 cast<AtomicType>(T)->getValueType(),
4884 OnlyDeduced, Depth, Used);
4887 case Type::DependentName:
4889 MarkUsedTemplateParameters(Ctx,
4890 cast<DependentNameType>(T)->getQualifier(),
4891 OnlyDeduced, Depth, Used);
4894 case Type::DependentTemplateSpecialization: {
4895 // C++14 [temp.deduct.type]p5:
4896 // The non-deduced contexts are:
4897 // -- The nested-name-specifier of a type that was specified using a
4900 // C++14 [temp.deduct.type]p6:
4901 // When a type name is specified in a way that includes a non-deduced
4902 // context, all of the types that comprise that type name are also
4907 const DependentTemplateSpecializationType *Spec
4908 = cast<DependentTemplateSpecializationType>(T);
4910 MarkUsedTemplateParameters(Ctx, Spec->getQualifier(),
4911 OnlyDeduced, Depth, Used);
4913 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
4914 MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth,
4921 MarkUsedTemplateParameters(Ctx,
4922 cast<TypeOfType>(T)->getUnderlyingType(),
4923 OnlyDeduced, Depth, Used);
4926 case Type::TypeOfExpr:
4928 MarkUsedTemplateParameters(Ctx,
4929 cast<TypeOfExprType>(T)->getUnderlyingExpr(),
4930 OnlyDeduced, Depth, Used);
4933 case Type::Decltype:
4935 MarkUsedTemplateParameters(Ctx,
4936 cast<DecltypeType>(T)->getUnderlyingExpr(),
4937 OnlyDeduced, Depth, Used);
4940 case Type::UnaryTransform:
4942 MarkUsedTemplateParameters(Ctx,
4943 cast<UnaryTransformType>(T)->getUnderlyingType(),
4944 OnlyDeduced, Depth, Used);
4947 case Type::PackExpansion:
4948 MarkUsedTemplateParameters(Ctx,
4949 cast<PackExpansionType>(T)->getPattern(),
4950 OnlyDeduced, Depth, Used);
4954 MarkUsedTemplateParameters(Ctx,
4955 cast<AutoType>(T)->getDeducedType(),
4956 OnlyDeduced, Depth, Used);
4958 // None of these types have any template parameters in them.
4960 case Type::VariableArray:
4961 case Type::FunctionNoProto:
4964 case Type::ObjCInterface:
4965 case Type::ObjCObject:
4966 case Type::ObjCObjectPointer:
4967 case Type::UnresolvedUsing:
4969 #define TYPE(Class, Base)
4970 #define ABSTRACT_TYPE(Class, Base)
4971 #define DEPENDENT_TYPE(Class, Base)
4972 #define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
4973 #include "clang/AST/TypeNodes.def"
4978 /// \brief Mark the template parameters that are used by this
4979 /// template argument.
4981 MarkUsedTemplateParameters(ASTContext &Ctx,
4982 const TemplateArgument &TemplateArg,
4985 llvm::SmallBitVector &Used) {
4986 switch (TemplateArg.getKind()) {
4987 case TemplateArgument::Null:
4988 case TemplateArgument::Integral:
4989 case TemplateArgument::Declaration:
4992 case TemplateArgument::NullPtr:
4993 MarkUsedTemplateParameters(Ctx, TemplateArg.getNullPtrType(), OnlyDeduced,
4997 case TemplateArgument::Type:
4998 MarkUsedTemplateParameters(Ctx, TemplateArg.getAsType(), OnlyDeduced,
5002 case TemplateArgument::Template:
5003 case TemplateArgument::TemplateExpansion:
5004 MarkUsedTemplateParameters(Ctx,
5005 TemplateArg.getAsTemplateOrTemplatePattern(),
5006 OnlyDeduced, Depth, Used);
5009 case TemplateArgument::Expression:
5010 MarkUsedTemplateParameters(Ctx, TemplateArg.getAsExpr(), OnlyDeduced,
5014 case TemplateArgument::Pack:
5015 for (const auto &P : TemplateArg.pack_elements())
5016 MarkUsedTemplateParameters(Ctx, P, OnlyDeduced, Depth, Used);
5021 /// \brief Mark which template parameters can be deduced from a given
5022 /// template argument list.
5024 /// \param TemplateArgs the template argument list from which template
5025 /// parameters will be deduced.
5027 /// \param Used a bit vector whose elements will be set to \c true
5028 /// to indicate when the corresponding template parameter will be
5031 Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs,
5032 bool OnlyDeduced, unsigned Depth,
5033 llvm::SmallBitVector &Used) {
5034 // C++0x [temp.deduct.type]p9:
5035 // If the template argument list of P contains a pack expansion that is not
5036 // the last template argument, the entire template argument list is a
5037 // non-deduced context.
5039 hasPackExpansionBeforeEnd(TemplateArgs.data(), TemplateArgs.size()))
5042 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I)
5043 ::MarkUsedTemplateParameters(Context, TemplateArgs[I], OnlyDeduced,
5047 /// \brief Marks all of the template parameters that will be deduced by a
5048 /// call to the given function template.
5049 void Sema::MarkDeducedTemplateParameters(
5050 ASTContext &Ctx, const FunctionTemplateDecl *FunctionTemplate,
5051 llvm::SmallBitVector &Deduced) {
5052 TemplateParameterList *TemplateParams
5053 = FunctionTemplate->getTemplateParameters();
5055 Deduced.resize(TemplateParams->size());
5057 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
5058 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I)
5059 ::MarkUsedTemplateParameters(Ctx, Function->getParamDecl(I)->getType(),
5060 true, TemplateParams->getDepth(), Deduced);
5063 bool hasDeducibleTemplateParameters(Sema &S,
5064 FunctionTemplateDecl *FunctionTemplate,
5066 if (!T->isDependentType())
5069 TemplateParameterList *TemplateParams
5070 = FunctionTemplate->getTemplateParameters();
5071 llvm::SmallBitVector Deduced(TemplateParams->size());
5072 ::MarkUsedTemplateParameters(S.Context, T, true, TemplateParams->getDepth(),
5075 return Deduced.any();