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/Sema.h"
14 #include "clang/Sema/DeclSpec.h"
15 #include "clang/Sema/Template.h"
16 #include "clang/Sema/TemplateDeduction.h"
17 #include "clang/AST/ASTContext.h"
18 #include "clang/AST/DeclObjC.h"
19 #include "clang/AST/DeclTemplate.h"
20 #include "clang/AST/StmtVisitor.h"
21 #include "clang/AST/Expr.h"
22 #include "clang/AST/ExprCXX.h"
23 #include "llvm/ADT/BitVector.h"
24 #include "TreeTransform.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
59 using namespace clang;
61 /// \brief Compare two APSInts, extending and switching the sign as
62 /// necessary to compare their values regardless of underlying type.
63 static bool hasSameExtendedValue(llvm::APSInt X, llvm::APSInt Y) {
64 if (Y.getBitWidth() > X.getBitWidth())
65 X = X.extend(Y.getBitWidth());
66 else if (Y.getBitWidth() < X.getBitWidth())
67 Y = Y.extend(X.getBitWidth());
69 // If there is a signedness mismatch, correct it.
70 if (X.isSigned() != Y.isSigned()) {
71 // If the signed value is negative, then the values cannot be the same.
72 if ((Y.isSigned() && Y.isNegative()) || (X.isSigned() && X.isNegative()))
82 static Sema::TemplateDeductionResult
83 DeduceTemplateArguments(Sema &S,
84 TemplateParameterList *TemplateParams,
85 const TemplateArgument &Param,
87 TemplateDeductionInfo &Info,
88 SmallVectorImpl<DeducedTemplateArgument> &Deduced);
90 /// \brief Whether template argument deduction for two reference parameters
91 /// resulted in the argument type, parameter type, or neither type being more
92 /// qualified than the other.
93 enum DeductionQualifierComparison {
94 NeitherMoreQualified = 0,
99 /// \brief Stores the result of comparing two reference parameters while
100 /// performing template argument deduction for partial ordering of function
102 struct RefParamPartialOrderingComparison {
103 /// \brief Whether the parameter type is an rvalue reference type.
104 bool ParamIsRvalueRef;
105 /// \brief Whether the argument type is an rvalue reference type.
108 /// \brief Whether the parameter or argument (or neither) is more qualified.
109 DeductionQualifierComparison Qualifiers;
114 static Sema::TemplateDeductionResult
115 DeduceTemplateArguments(Sema &S,
116 TemplateParameterList *TemplateParams,
119 TemplateDeductionInfo &Info,
120 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
122 bool PartialOrdering = false,
123 SmallVectorImpl<RefParamPartialOrderingComparison> *
124 RefParamComparisons = 0);
126 static Sema::TemplateDeductionResult
127 DeduceTemplateArguments(Sema &S,
128 TemplateParameterList *TemplateParams,
129 const TemplateArgument *Params, unsigned NumParams,
130 const TemplateArgument *Args, unsigned NumArgs,
131 TemplateDeductionInfo &Info,
132 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
133 bool NumberOfArgumentsMustMatch = true);
135 /// \brief If the given expression is of a form that permits the deduction
136 /// of a non-type template parameter, return the declaration of that
137 /// non-type template parameter.
138 static NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) {
139 if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E))
140 E = IC->getSubExpr();
142 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
143 return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
148 /// \brief Determine whether two declaration pointers refer to the same
150 static bool isSameDeclaration(Decl *X, Decl *Y) {
154 if (NamedDecl *NX = dyn_cast<NamedDecl>(X))
155 X = NX->getUnderlyingDecl();
156 if (NamedDecl *NY = dyn_cast<NamedDecl>(Y))
157 Y = NY->getUnderlyingDecl();
159 return X->getCanonicalDecl() == Y->getCanonicalDecl();
162 /// \brief Verify that the given, deduced template arguments are compatible.
164 /// \returns The deduced template argument, or a NULL template argument if
165 /// the deduced template arguments were incompatible.
166 static DeducedTemplateArgument
167 checkDeducedTemplateArguments(ASTContext &Context,
168 const DeducedTemplateArgument &X,
169 const DeducedTemplateArgument &Y) {
170 // We have no deduction for one or both of the arguments; they're compatible.
176 switch (X.getKind()) {
177 case TemplateArgument::Null:
178 llvm_unreachable("Non-deduced template arguments handled above");
180 case TemplateArgument::Type:
181 // If two template type arguments have the same type, they're compatible.
182 if (Y.getKind() == TemplateArgument::Type &&
183 Context.hasSameType(X.getAsType(), Y.getAsType()))
186 return DeducedTemplateArgument();
188 case TemplateArgument::Integral:
189 // If we deduced a constant in one case and either a dependent expression or
190 // declaration in another case, keep the integral constant.
191 // If both are integral constants with the same value, keep that value.
192 if (Y.getKind() == TemplateArgument::Expression ||
193 Y.getKind() == TemplateArgument::Declaration ||
194 (Y.getKind() == TemplateArgument::Integral &&
195 hasSameExtendedValue(*X.getAsIntegral(), *Y.getAsIntegral())))
196 return DeducedTemplateArgument(X,
197 X.wasDeducedFromArrayBound() &&
198 Y.wasDeducedFromArrayBound());
200 // All other combinations are incompatible.
201 return DeducedTemplateArgument();
203 case TemplateArgument::Template:
204 if (Y.getKind() == TemplateArgument::Template &&
205 Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate()))
208 // All other combinations are incompatible.
209 return DeducedTemplateArgument();
211 case TemplateArgument::TemplateExpansion:
212 if (Y.getKind() == TemplateArgument::TemplateExpansion &&
213 Context.hasSameTemplateName(X.getAsTemplateOrTemplatePattern(),
214 Y.getAsTemplateOrTemplatePattern()))
217 // All other combinations are incompatible.
218 return DeducedTemplateArgument();
220 case TemplateArgument::Expression:
221 // If we deduced a dependent expression in one case and either an integral
222 // constant or a declaration in another case, keep the integral constant
224 if (Y.getKind() == TemplateArgument::Integral ||
225 Y.getKind() == TemplateArgument::Declaration)
226 return DeducedTemplateArgument(Y, X.wasDeducedFromArrayBound() &&
227 Y.wasDeducedFromArrayBound());
229 if (Y.getKind() == TemplateArgument::Expression) {
230 // Compare the expressions for equality
231 llvm::FoldingSetNodeID ID1, ID2;
232 X.getAsExpr()->Profile(ID1, Context, true);
233 Y.getAsExpr()->Profile(ID2, Context, true);
238 // All other combinations are incompatible.
239 return DeducedTemplateArgument();
241 case TemplateArgument::Declaration:
242 // If we deduced a declaration and a dependent expression, keep the
244 if (Y.getKind() == TemplateArgument::Expression)
247 // If we deduced a declaration and an integral constant, keep the
248 // integral constant.
249 if (Y.getKind() == TemplateArgument::Integral)
252 // If we deduced two declarations, make sure they they refer to the
254 if (Y.getKind() == TemplateArgument::Declaration &&
255 isSameDeclaration(X.getAsDecl(), Y.getAsDecl()))
258 // All other combinations are incompatible.
259 return DeducedTemplateArgument();
261 case TemplateArgument::Pack:
262 if (Y.getKind() != TemplateArgument::Pack ||
263 X.pack_size() != Y.pack_size())
264 return DeducedTemplateArgument();
266 for (TemplateArgument::pack_iterator XA = X.pack_begin(),
267 XAEnd = X.pack_end(),
269 XA != XAEnd; ++XA, ++YA) {
270 if (checkDeducedTemplateArguments(Context,
271 DeducedTemplateArgument(*XA, X.wasDeducedFromArrayBound()),
272 DeducedTemplateArgument(*YA, Y.wasDeducedFromArrayBound()))
274 return DeducedTemplateArgument();
280 return DeducedTemplateArgument();
283 /// \brief Deduce the value of the given non-type template parameter
284 /// from the given constant.
285 static Sema::TemplateDeductionResult
286 DeduceNonTypeTemplateArgument(Sema &S,
287 NonTypeTemplateParmDecl *NTTP,
288 llvm::APSInt Value, QualType ValueType,
289 bool DeducedFromArrayBound,
290 TemplateDeductionInfo &Info,
291 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
292 assert(NTTP->getDepth() == 0 &&
293 "Cannot deduce non-type template argument with depth > 0");
295 DeducedTemplateArgument NewDeduced(Value, ValueType, DeducedFromArrayBound);
296 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
297 Deduced[NTTP->getIndex()],
299 if (Result.isNull()) {
301 Info.FirstArg = Deduced[NTTP->getIndex()];
302 Info.SecondArg = NewDeduced;
303 return Sema::TDK_Inconsistent;
306 Deduced[NTTP->getIndex()] = Result;
307 return Sema::TDK_Success;
310 /// \brief Deduce the value of the given non-type template parameter
311 /// from the given type- or value-dependent expression.
313 /// \returns true if deduction succeeded, false otherwise.
314 static Sema::TemplateDeductionResult
315 DeduceNonTypeTemplateArgument(Sema &S,
316 NonTypeTemplateParmDecl *NTTP,
318 TemplateDeductionInfo &Info,
319 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
320 assert(NTTP->getDepth() == 0 &&
321 "Cannot deduce non-type template argument with depth > 0");
322 assert((Value->isTypeDependent() || Value->isValueDependent()) &&
323 "Expression template argument must be type- or value-dependent.");
325 DeducedTemplateArgument NewDeduced(Value);
326 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
327 Deduced[NTTP->getIndex()],
330 if (Result.isNull()) {
332 Info.FirstArg = Deduced[NTTP->getIndex()];
333 Info.SecondArg = NewDeduced;
334 return Sema::TDK_Inconsistent;
337 Deduced[NTTP->getIndex()] = Result;
338 return Sema::TDK_Success;
341 /// \brief Deduce the value of the given non-type template parameter
342 /// from the given declaration.
344 /// \returns true if deduction succeeded, false otherwise.
345 static Sema::TemplateDeductionResult
346 DeduceNonTypeTemplateArgument(Sema &S,
347 NonTypeTemplateParmDecl *NTTP,
349 TemplateDeductionInfo &Info,
350 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
351 assert(NTTP->getDepth() == 0 &&
352 "Cannot deduce non-type template argument with depth > 0");
354 DeducedTemplateArgument NewDeduced(D? D->getCanonicalDecl() : 0);
355 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
356 Deduced[NTTP->getIndex()],
358 if (Result.isNull()) {
360 Info.FirstArg = Deduced[NTTP->getIndex()];
361 Info.SecondArg = NewDeduced;
362 return Sema::TDK_Inconsistent;
365 Deduced[NTTP->getIndex()] = Result;
366 return Sema::TDK_Success;
369 static Sema::TemplateDeductionResult
370 DeduceTemplateArguments(Sema &S,
371 TemplateParameterList *TemplateParams,
374 TemplateDeductionInfo &Info,
375 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
376 TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
378 // The parameter type is dependent and is not a template template parameter,
379 // so there is nothing that we can deduce.
380 return Sema::TDK_Success;
383 if (TemplateTemplateParmDecl *TempParam
384 = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) {
385 DeducedTemplateArgument NewDeduced(S.Context.getCanonicalTemplateName(Arg));
386 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
387 Deduced[TempParam->getIndex()],
389 if (Result.isNull()) {
390 Info.Param = TempParam;
391 Info.FirstArg = Deduced[TempParam->getIndex()];
392 Info.SecondArg = NewDeduced;
393 return Sema::TDK_Inconsistent;
396 Deduced[TempParam->getIndex()] = Result;
397 return Sema::TDK_Success;
400 // Verify that the two template names are equivalent.
401 if (S.Context.hasSameTemplateName(Param, Arg))
402 return Sema::TDK_Success;
404 // Mismatch of non-dependent template parameter to argument.
405 Info.FirstArg = TemplateArgument(Param);
406 Info.SecondArg = TemplateArgument(Arg);
407 return Sema::TDK_NonDeducedMismatch;
410 /// \brief Deduce the template arguments by comparing the template parameter
411 /// type (which is a template-id) with the template argument type.
413 /// \param S the Sema
415 /// \param TemplateParams the template parameters that we are deducing
417 /// \param Param the parameter type
419 /// \param Arg the argument type
421 /// \param Info information about the template argument deduction itself
423 /// \param Deduced the deduced template arguments
425 /// \returns the result of template argument deduction so far. Note that a
426 /// "success" result means that template argument deduction has not yet failed,
427 /// but it may still fail, later, for other reasons.
428 static Sema::TemplateDeductionResult
429 DeduceTemplateArguments(Sema &S,
430 TemplateParameterList *TemplateParams,
431 const TemplateSpecializationType *Param,
433 TemplateDeductionInfo &Info,
434 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
435 assert(Arg.isCanonical() && "Argument type must be canonical");
437 // Check whether the template argument is a dependent template-id.
438 if (const TemplateSpecializationType *SpecArg
439 = dyn_cast<TemplateSpecializationType>(Arg)) {
440 // Perform template argument deduction for the template name.
441 if (Sema::TemplateDeductionResult Result
442 = DeduceTemplateArguments(S, TemplateParams,
443 Param->getTemplateName(),
444 SpecArg->getTemplateName(),
449 // Perform template argument deduction on each template
450 // argument. Ignore any missing/extra arguments, since they could be
451 // filled in by default arguments.
452 return DeduceTemplateArguments(S, TemplateParams,
453 Param->getArgs(), Param->getNumArgs(),
454 SpecArg->getArgs(), SpecArg->getNumArgs(),
456 /*NumberOfArgumentsMustMatch=*/false);
459 // If the argument type is a class template specialization, we
460 // perform template argument deduction using its template
462 const RecordType *RecordArg = dyn_cast<RecordType>(Arg);
464 return Sema::TDK_NonDeducedMismatch;
466 ClassTemplateSpecializationDecl *SpecArg
467 = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl());
469 return Sema::TDK_NonDeducedMismatch;
471 // Perform template argument deduction for the template name.
472 if (Sema::TemplateDeductionResult Result
473 = DeduceTemplateArguments(S,
475 Param->getTemplateName(),
476 TemplateName(SpecArg->getSpecializedTemplate()),
480 // Perform template argument deduction for the template arguments.
481 return DeduceTemplateArguments(S, TemplateParams,
482 Param->getArgs(), Param->getNumArgs(),
483 SpecArg->getTemplateArgs().data(),
484 SpecArg->getTemplateArgs().size(),
488 /// \brief Determines whether the given type is an opaque type that
489 /// might be more qualified when instantiated.
490 static bool IsPossiblyOpaquelyQualifiedType(QualType T) {
491 switch (T->getTypeClass()) {
492 case Type::TypeOfExpr:
494 case Type::DependentName:
496 case Type::UnresolvedUsing:
497 case Type::TemplateTypeParm:
500 case Type::ConstantArray:
501 case Type::IncompleteArray:
502 case Type::VariableArray:
503 case Type::DependentSizedArray:
504 return IsPossiblyOpaquelyQualifiedType(
505 cast<ArrayType>(T)->getElementType());
512 /// \brief Retrieve the depth and index of a template parameter.
513 static std::pair<unsigned, unsigned>
514 getDepthAndIndex(NamedDecl *ND) {
515 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND))
516 return std::make_pair(TTP->getDepth(), TTP->getIndex());
518 if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND))
519 return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
521 TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
522 return std::make_pair(TTP->getDepth(), TTP->getIndex());
525 /// \brief Retrieve the depth and index of an unexpanded parameter pack.
526 static std::pair<unsigned, unsigned>
527 getDepthAndIndex(UnexpandedParameterPack UPP) {
528 if (const TemplateTypeParmType *TTP
529 = UPP.first.dyn_cast<const TemplateTypeParmType *>())
530 return std::make_pair(TTP->getDepth(), TTP->getIndex());
532 return getDepthAndIndex(UPP.first.get<NamedDecl *>());
535 /// \brief Helper function to build a TemplateParameter when we don't
536 /// know its type statically.
537 static TemplateParameter makeTemplateParameter(Decl *D) {
538 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D))
539 return TemplateParameter(TTP);
540 else if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D))
541 return TemplateParameter(NTTP);
543 return TemplateParameter(cast<TemplateTemplateParmDecl>(D));
546 /// \brief Prepare to perform template argument deduction for all of the
547 /// arguments in a set of argument packs.
548 static void PrepareArgumentPackDeduction(Sema &S,
549 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
550 const SmallVectorImpl<unsigned> &PackIndices,
551 SmallVectorImpl<DeducedTemplateArgument> &SavedPacks,
553 SmallVector<DeducedTemplateArgument, 4> > &NewlyDeducedPacks) {
554 // Save the deduced template arguments for each parameter pack expanded
555 // by this pack expansion, then clear out the deduction.
556 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
557 // Save the previously-deduced argument pack, then clear it out so that we
558 // can deduce a new argument pack.
559 SavedPacks[I] = Deduced[PackIndices[I]];
560 Deduced[PackIndices[I]] = TemplateArgument();
562 // If the template arugment pack was explicitly specified, add that to
563 // the set of deduced arguments.
564 const TemplateArgument *ExplicitArgs;
565 unsigned NumExplicitArgs;
566 if (NamedDecl *PartiallySubstitutedPack
567 = S.CurrentInstantiationScope->getPartiallySubstitutedPack(
570 if (getDepthAndIndex(PartiallySubstitutedPack).second == PackIndices[I])
571 NewlyDeducedPacks[I].append(ExplicitArgs,
572 ExplicitArgs + NumExplicitArgs);
577 /// \brief Finish template argument deduction for a set of argument packs,
578 /// producing the argument packs and checking for consistency with prior
580 static Sema::TemplateDeductionResult
581 FinishArgumentPackDeduction(Sema &S,
582 TemplateParameterList *TemplateParams,
583 bool HasAnyArguments,
584 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
585 const SmallVectorImpl<unsigned> &PackIndices,
586 SmallVectorImpl<DeducedTemplateArgument> &SavedPacks,
588 SmallVector<DeducedTemplateArgument, 4> > &NewlyDeducedPacks,
589 TemplateDeductionInfo &Info) {
590 // Build argument packs for each of the parameter packs expanded by this
592 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
593 if (HasAnyArguments && NewlyDeducedPacks[I].empty()) {
594 // We were not able to deduce anything for this parameter pack,
595 // so just restore the saved argument pack.
596 Deduced[PackIndices[I]] = SavedPacks[I];
600 DeducedTemplateArgument NewPack;
602 if (NewlyDeducedPacks[I].empty()) {
603 // If we deduced an empty argument pack, create it now.
604 NewPack = DeducedTemplateArgument(TemplateArgument(0, 0));
606 TemplateArgument *ArgumentPack
607 = new (S.Context) TemplateArgument [NewlyDeducedPacks[I].size()];
608 std::copy(NewlyDeducedPacks[I].begin(), NewlyDeducedPacks[I].end(),
611 = DeducedTemplateArgument(TemplateArgument(ArgumentPack,
612 NewlyDeducedPacks[I].size()),
613 NewlyDeducedPacks[I][0].wasDeducedFromArrayBound());
616 DeducedTemplateArgument Result
617 = checkDeducedTemplateArguments(S.Context, SavedPacks[I], NewPack);
618 if (Result.isNull()) {
620 = makeTemplateParameter(TemplateParams->getParam(PackIndices[I]));
621 Info.FirstArg = SavedPacks[I];
622 Info.SecondArg = NewPack;
623 return Sema::TDK_Inconsistent;
626 Deduced[PackIndices[I]] = Result;
629 return Sema::TDK_Success;
632 /// \brief Deduce the template arguments by comparing the list of parameter
633 /// types to the list of argument types, as in the parameter-type-lists of
634 /// function types (C++ [temp.deduct.type]p10).
636 /// \param S The semantic analysis object within which we are deducing
638 /// \param TemplateParams The template parameters that we are deducing
640 /// \param Params The list of parameter types
642 /// \param NumParams The number of types in \c Params
644 /// \param Args The list of argument types
646 /// \param NumArgs The number of types in \c Args
648 /// \param Info information about the template argument deduction itself
650 /// \param Deduced the deduced template arguments
652 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
653 /// how template argument deduction is performed.
655 /// \param PartialOrdering If true, we are performing template argument
656 /// deduction for during partial ordering for a call
657 /// (C++0x [temp.deduct.partial]).
659 /// \param RefParamComparisons If we're performing template argument deduction
660 /// in the context of partial ordering, the set of qualifier comparisons.
662 /// \returns the result of template argument deduction so far. Note that a
663 /// "success" result means that template argument deduction has not yet failed,
664 /// but it may still fail, later, for other reasons.
665 static Sema::TemplateDeductionResult
666 DeduceTemplateArguments(Sema &S,
667 TemplateParameterList *TemplateParams,
668 const QualType *Params, unsigned NumParams,
669 const QualType *Args, unsigned NumArgs,
670 TemplateDeductionInfo &Info,
671 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
673 bool PartialOrdering = false,
674 SmallVectorImpl<RefParamPartialOrderingComparison> *
675 RefParamComparisons = 0) {
676 // Fast-path check to see if we have too many/too few arguments.
677 if (NumParams != NumArgs &&
678 !(NumParams && isa<PackExpansionType>(Params[NumParams - 1])) &&
679 !(NumArgs && isa<PackExpansionType>(Args[NumArgs - 1])))
680 return Sema::TDK_NonDeducedMismatch;
682 // C++0x [temp.deduct.type]p10:
683 // Similarly, if P has a form that contains (T), then each parameter type
684 // Pi of the respective parameter-type- list of P is compared with the
685 // corresponding parameter type Ai of the corresponding parameter-type-list
687 unsigned ArgIdx = 0, ParamIdx = 0;
688 for (; ParamIdx != NumParams; ++ParamIdx) {
689 // Check argument types.
690 const PackExpansionType *Expansion
691 = dyn_cast<PackExpansionType>(Params[ParamIdx]);
693 // Simple case: compare the parameter and argument types at this point.
695 // Make sure we have an argument.
696 if (ArgIdx >= NumArgs)
697 return Sema::TDK_NonDeducedMismatch;
699 if (isa<PackExpansionType>(Args[ArgIdx])) {
700 // C++0x [temp.deduct.type]p22:
701 // If the original function parameter associated with A is a function
702 // parameter pack and the function parameter associated with P is not
703 // a function parameter pack, then template argument deduction fails.
704 return Sema::TDK_NonDeducedMismatch;
707 if (Sema::TemplateDeductionResult Result
708 = DeduceTemplateArguments(S, TemplateParams,
713 RefParamComparisons))
720 // C++0x [temp.deduct.type]p5:
721 // The non-deduced contexts are:
722 // - A function parameter pack that does not occur at the end of the
723 // parameter-declaration-clause.
724 if (ParamIdx + 1 < NumParams)
725 return Sema::TDK_Success;
727 // C++0x [temp.deduct.type]p10:
728 // If the parameter-declaration corresponding to Pi is a function
729 // parameter pack, then the type of its declarator- id is compared with
730 // each remaining parameter type in the parameter-type-list of A. Each
731 // comparison deduces template arguments for subsequent positions in the
732 // template parameter packs expanded by the function parameter pack.
734 // Compute the set of template parameter indices that correspond to
735 // parameter packs expanded by the pack expansion.
736 SmallVector<unsigned, 2> PackIndices;
737 QualType Pattern = Expansion->getPattern();
739 llvm::BitVector SawIndices(TemplateParams->size());
740 SmallVector<UnexpandedParameterPack, 2> Unexpanded;
741 S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
742 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
743 unsigned Depth, Index;
744 llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
745 if (Depth == 0 && !SawIndices[Index]) {
746 SawIndices[Index] = true;
747 PackIndices.push_back(Index);
751 assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?");
753 // Keep track of the deduced template arguments for each parameter pack
754 // expanded by this pack expansion (the outer index) and for each
755 // template argument (the inner SmallVectors).
756 SmallVector<SmallVector<DeducedTemplateArgument, 4>, 2>
757 NewlyDeducedPacks(PackIndices.size());
758 SmallVector<DeducedTemplateArgument, 2>
759 SavedPacks(PackIndices.size());
760 PrepareArgumentPackDeduction(S, Deduced, PackIndices, SavedPacks,
763 bool HasAnyArguments = false;
764 for (; ArgIdx < NumArgs; ++ArgIdx) {
765 HasAnyArguments = true;
767 // Deduce template arguments from the pattern.
768 if (Sema::TemplateDeductionResult Result
769 = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx],
770 Info, Deduced, TDF, PartialOrdering,
771 RefParamComparisons))
774 // Capture the deduced template arguments for each parameter pack expanded
775 // by this pack expansion, add them to the list of arguments we've deduced
776 // for that pack, then clear out the deduced argument.
777 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
778 DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]];
779 if (!DeducedArg.isNull()) {
780 NewlyDeducedPacks[I].push_back(DeducedArg);
781 DeducedArg = DeducedTemplateArgument();
786 // Build argument packs for each of the parameter packs expanded by this
788 if (Sema::TemplateDeductionResult Result
789 = FinishArgumentPackDeduction(S, TemplateParams, HasAnyArguments,
790 Deduced, PackIndices, SavedPacks,
791 NewlyDeducedPacks, Info))
795 // Make sure we don't have any extra arguments.
796 if (ArgIdx < NumArgs)
797 return Sema::TDK_NonDeducedMismatch;
799 return Sema::TDK_Success;
802 /// \brief Determine whether the parameter has qualifiers that are either
803 /// inconsistent with or a superset of the argument's qualifiers.
804 static bool hasInconsistentOrSupersetQualifiersOf(QualType ParamType,
806 Qualifiers ParamQs = ParamType.getQualifiers();
807 Qualifiers ArgQs = ArgType.getQualifiers();
809 if (ParamQs == ArgQs)
812 // Mismatched (but not missing) Objective-C GC attributes.
813 if (ParamQs.getObjCGCAttr() != ArgQs.getObjCGCAttr() &&
814 ParamQs.hasObjCGCAttr())
817 // Mismatched (but not missing) address spaces.
818 if (ParamQs.getAddressSpace() != ArgQs.getAddressSpace() &&
819 ParamQs.hasAddressSpace())
822 // Mismatched (but not missing) Objective-C lifetime qualifiers.
823 if (ParamQs.getObjCLifetime() != ArgQs.getObjCLifetime() &&
824 ParamQs.hasObjCLifetime())
827 // CVR qualifier superset.
828 return (ParamQs.getCVRQualifiers() != ArgQs.getCVRQualifiers()) &&
829 ((ParamQs.getCVRQualifiers() | ArgQs.getCVRQualifiers())
830 == ParamQs.getCVRQualifiers());
833 /// \brief Deduce the template arguments by comparing the parameter type and
834 /// the argument type (C++ [temp.deduct.type]).
836 /// \param S the semantic analysis object within which we are deducing
838 /// \param TemplateParams the template parameters that we are deducing
840 /// \param ParamIn the parameter type
842 /// \param ArgIn the argument type
844 /// \param Info information about the template argument deduction itself
846 /// \param Deduced the deduced template arguments
848 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
849 /// how template argument deduction is performed.
851 /// \param PartialOrdering Whether we're performing template argument deduction
852 /// in the context of partial ordering (C++0x [temp.deduct.partial]).
854 /// \param RefParamComparisons If we're performing template argument deduction
855 /// in the context of partial ordering, the set of qualifier comparisons.
857 /// \returns the result of template argument deduction so far. Note that a
858 /// "success" result means that template argument deduction has not yet failed,
859 /// but it may still fail, later, for other reasons.
860 static Sema::TemplateDeductionResult
861 DeduceTemplateArguments(Sema &S,
862 TemplateParameterList *TemplateParams,
863 QualType ParamIn, QualType ArgIn,
864 TemplateDeductionInfo &Info,
865 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
867 bool PartialOrdering,
868 SmallVectorImpl<RefParamPartialOrderingComparison> *RefParamComparisons) {
869 // We only want to look at the canonical types, since typedefs and
870 // sugar are not part of template argument deduction.
871 QualType Param = S.Context.getCanonicalType(ParamIn);
872 QualType Arg = S.Context.getCanonicalType(ArgIn);
874 // If the argument type is a pack expansion, look at its pattern.
875 // This isn't explicitly called out
876 if (const PackExpansionType *ArgExpansion
877 = dyn_cast<PackExpansionType>(Arg))
878 Arg = ArgExpansion->getPattern();
880 if (PartialOrdering) {
881 // C++0x [temp.deduct.partial]p5:
882 // Before the partial ordering is done, certain transformations are
883 // performed on the types used for partial ordering:
884 // - If P is a reference type, P is replaced by the type referred to.
885 const ReferenceType *ParamRef = Param->getAs<ReferenceType>();
887 Param = ParamRef->getPointeeType();
889 // - If A is a reference type, A is replaced by the type referred to.
890 const ReferenceType *ArgRef = Arg->getAs<ReferenceType>();
892 Arg = ArgRef->getPointeeType();
894 if (RefParamComparisons && ParamRef && ArgRef) {
895 // C++0x [temp.deduct.partial]p6:
896 // If both P and A were reference types (before being replaced with the
897 // type referred to above), determine which of the two types (if any) is
898 // more cv-qualified than the other; otherwise the types are considered
899 // to be equally cv-qualified for partial ordering purposes. The result
900 // of this determination will be used below.
902 // We save this information for later, using it only when deduction
903 // succeeds in both directions.
904 RefParamPartialOrderingComparison Comparison;
905 Comparison.ParamIsRvalueRef = ParamRef->getAs<RValueReferenceType>();
906 Comparison.ArgIsRvalueRef = ArgRef->getAs<RValueReferenceType>();
907 Comparison.Qualifiers = NeitherMoreQualified;
909 Qualifiers ParamQuals = Param.getQualifiers();
910 Qualifiers ArgQuals = Arg.getQualifiers();
911 if (ParamQuals.isStrictSupersetOf(ArgQuals))
912 Comparison.Qualifiers = ParamMoreQualified;
913 else if (ArgQuals.isStrictSupersetOf(ParamQuals))
914 Comparison.Qualifiers = ArgMoreQualified;
915 RefParamComparisons->push_back(Comparison);
918 // C++0x [temp.deduct.partial]p7:
919 // Remove any top-level cv-qualifiers:
920 // - If P is a cv-qualified type, P is replaced by the cv-unqualified
922 Param = Param.getUnqualifiedType();
923 // - If A is a cv-qualified type, A is replaced by the cv-unqualified
925 Arg = Arg.getUnqualifiedType();
927 // C++0x [temp.deduct.call]p4 bullet 1:
928 // - If the original P is a reference type, the deduced A (i.e., the type
929 // referred to by the reference) can be more cv-qualified than the
931 if (TDF & TDF_ParamWithReferenceType) {
933 QualType UnqualParam = S.Context.getUnqualifiedArrayType(Param, Quals);
934 Quals.setCVRQualifiers(Quals.getCVRQualifiers() &
935 Arg.getCVRQualifiers());
936 Param = S.Context.getQualifiedType(UnqualParam, Quals);
939 if ((TDF & TDF_TopLevelParameterTypeList) && !Param->isFunctionType()) {
940 // C++0x [temp.deduct.type]p10:
941 // If P and A are function types that originated from deduction when
942 // taking the address of a function template (14.8.2.2) or when deducing
943 // template arguments from a function declaration (14.8.2.6) and Pi and
944 // Ai are parameters of the top-level parameter-type-list of P and A,
945 // respectively, Pi is adjusted if it is an rvalue reference to a
946 // cv-unqualified template parameter and Ai is an lvalue reference, in
947 // which case the type of Pi is changed to be the template parameter
948 // type (i.e., T&& is changed to simply T). [ Note: As a result, when
949 // Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be
950 // deduced as X&. - end note ]
951 TDF &= ~TDF_TopLevelParameterTypeList;
953 if (const RValueReferenceType *ParamRef
954 = Param->getAs<RValueReferenceType>()) {
955 if (isa<TemplateTypeParmType>(ParamRef->getPointeeType()) &&
956 !ParamRef->getPointeeType().getQualifiers())
957 if (Arg->isLValueReferenceType())
958 Param = ParamRef->getPointeeType();
963 // If the parameter type is not dependent, there is nothing to deduce.
964 if (!Param->isDependentType()) {
965 if (!(TDF & TDF_SkipNonDependent) && Param != Arg)
966 return Sema::TDK_NonDeducedMismatch;
968 return Sema::TDK_Success;
971 // C++ [temp.deduct.type]p9:
972 // A template type argument T, a template template argument TT or a
973 // template non-type argument i can be deduced if P and A have one of
974 // the following forms:
978 if (const TemplateTypeParmType *TemplateTypeParm
979 = Param->getAs<TemplateTypeParmType>()) {
980 // Just skip any attempts to deduce from a placeholder type.
981 if (Arg->isPlaceholderType())
982 return Sema::TDK_Success;
984 unsigned Index = TemplateTypeParm->getIndex();
985 bool RecanonicalizeArg = false;
987 // If the argument type is an array type, move the qualifiers up to the
988 // top level, so they can be matched with the qualifiers on the parameter.
989 if (isa<ArrayType>(Arg)) {
991 Arg = S.Context.getUnqualifiedArrayType(Arg, Quals);
993 Arg = S.Context.getQualifiedType(Arg, Quals);
994 RecanonicalizeArg = true;
998 // The argument type can not be less qualified than the parameter
1000 if (!(TDF & TDF_IgnoreQualifiers) &&
1001 hasInconsistentOrSupersetQualifiersOf(Param, Arg)) {
1002 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1003 Info.FirstArg = TemplateArgument(Param);
1004 Info.SecondArg = TemplateArgument(Arg);
1005 return Sema::TDK_Underqualified;
1008 assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0");
1009 assert(Arg != S.Context.OverloadTy && "Unresolved overloaded function");
1010 QualType DeducedType = Arg;
1012 // Remove any qualifiers on the parameter from the deduced type.
1013 // We checked the qualifiers for consistency above.
1014 Qualifiers DeducedQs = DeducedType.getQualifiers();
1015 Qualifiers ParamQs = Param.getQualifiers();
1016 DeducedQs.removeCVRQualifiers(ParamQs.getCVRQualifiers());
1017 if (ParamQs.hasObjCGCAttr())
1018 DeducedQs.removeObjCGCAttr();
1019 if (ParamQs.hasAddressSpace())
1020 DeducedQs.removeAddressSpace();
1021 if (ParamQs.hasObjCLifetime())
1022 DeducedQs.removeObjCLifetime();
1025 // If template deduction would produce a lifetime qualifier on a type
1026 // that is not a lifetime type, template argument deduction fails.
1027 if (ParamQs.hasObjCLifetime() && !DeducedType->isObjCLifetimeType() &&
1028 !DeducedType->isDependentType()) {
1029 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1030 Info.FirstArg = TemplateArgument(Param);
1031 Info.SecondArg = TemplateArgument(Arg);
1032 return Sema::TDK_Underqualified;
1036 // If template deduction would produce an argument type with lifetime type
1037 // but no lifetime qualifier, the __strong lifetime qualifier is inferred.
1038 if (S.getLangOptions().ObjCAutoRefCount &&
1039 DeducedType->isObjCLifetimeType() &&
1040 !DeducedQs.hasObjCLifetime())
1041 DeducedQs.setObjCLifetime(Qualifiers::OCL_Strong);
1043 DeducedType = S.Context.getQualifiedType(DeducedType.getUnqualifiedType(),
1046 if (RecanonicalizeArg)
1047 DeducedType = S.Context.getCanonicalType(DeducedType);
1049 DeducedTemplateArgument NewDeduced(DeducedType);
1050 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
1053 if (Result.isNull()) {
1054 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1055 Info.FirstArg = Deduced[Index];
1056 Info.SecondArg = NewDeduced;
1057 return Sema::TDK_Inconsistent;
1060 Deduced[Index] = Result;
1061 return Sema::TDK_Success;
1064 // Set up the template argument deduction information for a failure.
1065 Info.FirstArg = TemplateArgument(ParamIn);
1066 Info.SecondArg = TemplateArgument(ArgIn);
1068 // If the parameter is an already-substituted template parameter
1069 // pack, do nothing: we don't know which of its arguments to look
1070 // at, so we have to wait until all of the parameter packs in this
1071 // expansion have arguments.
1072 if (isa<SubstTemplateTypeParmPackType>(Param))
1073 return Sema::TDK_Success;
1075 // Check the cv-qualifiers on the parameter and argument types.
1076 if (!(TDF & TDF_IgnoreQualifiers)) {
1077 if (TDF & TDF_ParamWithReferenceType) {
1078 if (hasInconsistentOrSupersetQualifiersOf(Param, Arg))
1079 return Sema::TDK_NonDeducedMismatch;
1080 } else if (!IsPossiblyOpaquelyQualifiedType(Param)) {
1081 if (Param.getCVRQualifiers() != Arg.getCVRQualifiers())
1082 return Sema::TDK_NonDeducedMismatch;
1086 switch (Param->getTypeClass()) {
1087 // Non-canonical types cannot appear here.
1088 #define NON_CANONICAL_TYPE(Class, Base) \
1089 case Type::Class: llvm_unreachable("deducing non-canonical type: " #Class);
1090 #define TYPE(Class, Base)
1091 #include "clang/AST/TypeNodes.def"
1093 case Type::TemplateTypeParm:
1094 case Type::SubstTemplateTypeParmPack:
1095 llvm_unreachable("Type nodes handled above");
1097 // These types cannot be used in templates or cannot be dependent, so
1098 // deduction always fails.
1100 case Type::VariableArray:
1102 case Type::FunctionNoProto:
1105 case Type::ObjCObject:
1106 case Type::ObjCInterface:
1107 case Type::ObjCObjectPointer:
1108 return Sema::TDK_NonDeducedMismatch;
1110 // _Complex T [placeholder extension]
1112 if (const ComplexType *ComplexArg = Arg->getAs<ComplexType>())
1113 return DeduceTemplateArguments(S, TemplateParams,
1114 cast<ComplexType>(Param)->getElementType(),
1115 ComplexArg->getElementType(),
1116 Info, Deduced, TDF);
1118 return Sema::TDK_NonDeducedMismatch;
1120 // _Atomic T [extension]
1122 if (const AtomicType *AtomicArg = Arg->getAs<AtomicType>())
1123 return DeduceTemplateArguments(S, TemplateParams,
1124 cast<AtomicType>(Param)->getValueType(),
1125 AtomicArg->getValueType(),
1126 Info, Deduced, TDF);
1128 return Sema::TDK_NonDeducedMismatch;
1131 case Type::Pointer: {
1132 QualType PointeeType;
1133 if (const PointerType *PointerArg = Arg->getAs<PointerType>()) {
1134 PointeeType = PointerArg->getPointeeType();
1135 } else if (const ObjCObjectPointerType *PointerArg
1136 = Arg->getAs<ObjCObjectPointerType>()) {
1137 PointeeType = PointerArg->getPointeeType();
1139 return Sema::TDK_NonDeducedMismatch;
1142 unsigned SubTDF = TDF & (TDF_IgnoreQualifiers | TDF_DerivedClass);
1143 return DeduceTemplateArguments(S, TemplateParams,
1144 cast<PointerType>(Param)->getPointeeType(),
1146 Info, Deduced, SubTDF);
1150 case Type::LValueReference: {
1151 const LValueReferenceType *ReferenceArg = Arg->getAs<LValueReferenceType>();
1153 return Sema::TDK_NonDeducedMismatch;
1155 return DeduceTemplateArguments(S, TemplateParams,
1156 cast<LValueReferenceType>(Param)->getPointeeType(),
1157 ReferenceArg->getPointeeType(),
1162 case Type::RValueReference: {
1163 const RValueReferenceType *ReferenceArg = Arg->getAs<RValueReferenceType>();
1165 return Sema::TDK_NonDeducedMismatch;
1167 return DeduceTemplateArguments(S, TemplateParams,
1168 cast<RValueReferenceType>(Param)->getPointeeType(),
1169 ReferenceArg->getPointeeType(),
1173 // T [] (implied, but not stated explicitly)
1174 case Type::IncompleteArray: {
1175 const IncompleteArrayType *IncompleteArrayArg =
1176 S.Context.getAsIncompleteArrayType(Arg);
1177 if (!IncompleteArrayArg)
1178 return Sema::TDK_NonDeducedMismatch;
1180 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1181 return DeduceTemplateArguments(S, TemplateParams,
1182 S.Context.getAsIncompleteArrayType(Param)->getElementType(),
1183 IncompleteArrayArg->getElementType(),
1184 Info, Deduced, SubTDF);
1187 // T [integer-constant]
1188 case Type::ConstantArray: {
1189 const ConstantArrayType *ConstantArrayArg =
1190 S.Context.getAsConstantArrayType(Arg);
1191 if (!ConstantArrayArg)
1192 return Sema::TDK_NonDeducedMismatch;
1194 const ConstantArrayType *ConstantArrayParm =
1195 S.Context.getAsConstantArrayType(Param);
1196 if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize())
1197 return Sema::TDK_NonDeducedMismatch;
1199 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1200 return DeduceTemplateArguments(S, TemplateParams,
1201 ConstantArrayParm->getElementType(),
1202 ConstantArrayArg->getElementType(),
1203 Info, Deduced, SubTDF);
1207 case Type::DependentSizedArray: {
1208 const ArrayType *ArrayArg = S.Context.getAsArrayType(Arg);
1210 return Sema::TDK_NonDeducedMismatch;
1212 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1214 // Check the element type of the arrays
1215 const DependentSizedArrayType *DependentArrayParm
1216 = S.Context.getAsDependentSizedArrayType(Param);
1217 if (Sema::TemplateDeductionResult Result
1218 = DeduceTemplateArguments(S, TemplateParams,
1219 DependentArrayParm->getElementType(),
1220 ArrayArg->getElementType(),
1221 Info, Deduced, SubTDF))
1224 // Determine the array bound is something we can deduce.
1225 NonTypeTemplateParmDecl *NTTP
1226 = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr());
1228 return Sema::TDK_Success;
1230 // We can perform template argument deduction for the given non-type
1231 // template parameter.
1232 assert(NTTP->getDepth() == 0 &&
1233 "Cannot deduce non-type template argument at depth > 0");
1234 if (const ConstantArrayType *ConstantArrayArg
1235 = dyn_cast<ConstantArrayType>(ArrayArg)) {
1236 llvm::APSInt Size(ConstantArrayArg->getSize());
1237 return DeduceNonTypeTemplateArgument(S, NTTP, Size,
1238 S.Context.getSizeType(),
1239 /*ArrayBound=*/true,
1242 if (const DependentSizedArrayType *DependentArrayArg
1243 = dyn_cast<DependentSizedArrayType>(ArrayArg))
1244 if (DependentArrayArg->getSizeExpr())
1245 return DeduceNonTypeTemplateArgument(S, NTTP,
1246 DependentArrayArg->getSizeExpr(),
1249 // Incomplete type does not match a dependently-sized array type
1250 return Sema::TDK_NonDeducedMismatch;
1256 case Type::FunctionProto: {
1257 unsigned SubTDF = TDF & TDF_TopLevelParameterTypeList;
1258 const FunctionProtoType *FunctionProtoArg =
1259 dyn_cast<FunctionProtoType>(Arg);
1260 if (!FunctionProtoArg)
1261 return Sema::TDK_NonDeducedMismatch;
1263 const FunctionProtoType *FunctionProtoParam =
1264 cast<FunctionProtoType>(Param);
1266 if (FunctionProtoParam->getTypeQuals()
1267 != FunctionProtoArg->getTypeQuals() ||
1268 FunctionProtoParam->getRefQualifier()
1269 != FunctionProtoArg->getRefQualifier() ||
1270 FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic())
1271 return Sema::TDK_NonDeducedMismatch;
1273 // Check return types.
1274 if (Sema::TemplateDeductionResult Result
1275 = DeduceTemplateArguments(S, TemplateParams,
1276 FunctionProtoParam->getResultType(),
1277 FunctionProtoArg->getResultType(),
1281 return DeduceTemplateArguments(S, TemplateParams,
1282 FunctionProtoParam->arg_type_begin(),
1283 FunctionProtoParam->getNumArgs(),
1284 FunctionProtoArg->arg_type_begin(),
1285 FunctionProtoArg->getNumArgs(),
1286 Info, Deduced, SubTDF);
1289 case Type::InjectedClassName: {
1290 // Treat a template's injected-class-name as if the template
1291 // specialization type had been used.
1292 Param = cast<InjectedClassNameType>(Param)
1293 ->getInjectedSpecializationType();
1294 assert(isa<TemplateSpecializationType>(Param) &&
1295 "injected class name is not a template specialization type");
1299 // template-name<T> (where template-name refers to a class template)
1304 case Type::TemplateSpecialization: {
1305 const TemplateSpecializationType *SpecParam
1306 = cast<TemplateSpecializationType>(Param);
1308 // Try to deduce template arguments from the template-id.
1309 Sema::TemplateDeductionResult Result
1310 = DeduceTemplateArguments(S, TemplateParams, SpecParam, Arg,
1313 if (Result && (TDF & TDF_DerivedClass)) {
1314 // C++ [temp.deduct.call]p3b3:
1315 // If P is a class, and P has the form template-id, then A can be a
1316 // derived class of the deduced A. Likewise, if P is a pointer to a
1317 // class of the form template-id, A can be a pointer to a derived
1318 // class pointed to by the deduced A.
1320 // More importantly:
1321 // These alternatives are considered only if type deduction would
1323 if (const RecordType *RecordT = Arg->getAs<RecordType>()) {
1324 // We cannot inspect base classes as part of deduction when the type
1325 // is incomplete, so either instantiate any templates necessary to
1326 // complete the type, or skip over it if it cannot be completed.
1327 if (S.RequireCompleteType(Info.getLocation(), Arg, 0))
1330 // Use data recursion to crawl through the list of base classes.
1331 // Visited contains the set of nodes we have already visited, while
1332 // ToVisit is our stack of records that we still need to visit.
1333 llvm::SmallPtrSet<const RecordType *, 8> Visited;
1334 SmallVector<const RecordType *, 8> ToVisit;
1335 ToVisit.push_back(RecordT);
1336 bool Successful = false;
1337 SmallVectorImpl<DeducedTemplateArgument> DeducedOrig(0);
1338 DeducedOrig = Deduced;
1339 while (!ToVisit.empty()) {
1340 // Retrieve the next class in the inheritance hierarchy.
1341 const RecordType *NextT = ToVisit.back();
1344 // If we have already seen this type, skip it.
1345 if (!Visited.insert(NextT))
1348 // If this is a base class, try to perform template argument
1349 // deduction from it.
1350 if (NextT != RecordT) {
1351 Sema::TemplateDeductionResult BaseResult
1352 = DeduceTemplateArguments(S, TemplateParams, SpecParam,
1353 QualType(NextT, 0), Info, Deduced);
1355 // If template argument deduction for this base was successful,
1356 // note that we had some success. Otherwise, ignore any deductions
1357 // from this base class.
1358 if (BaseResult == Sema::TDK_Success) {
1360 DeducedOrig = Deduced;
1363 Deduced = DeducedOrig;
1366 // Visit base classes
1367 CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl());
1368 for (CXXRecordDecl::base_class_iterator Base = Next->bases_begin(),
1369 BaseEnd = Next->bases_end();
1370 Base != BaseEnd; ++Base) {
1371 assert(Base->getType()->isRecordType() &&
1372 "Base class that isn't a record?");
1373 ToVisit.push_back(Base->getType()->getAs<RecordType>());
1378 return Sema::TDK_Success;
1390 // type (type::*)(T)
1395 case Type::MemberPointer: {
1396 const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param);
1397 const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg);
1399 return Sema::TDK_NonDeducedMismatch;
1401 if (Sema::TemplateDeductionResult Result
1402 = DeduceTemplateArguments(S, TemplateParams,
1403 MemPtrParam->getPointeeType(),
1404 MemPtrArg->getPointeeType(),
1406 TDF & TDF_IgnoreQualifiers))
1409 return DeduceTemplateArguments(S, TemplateParams,
1410 QualType(MemPtrParam->getClass(), 0),
1411 QualType(MemPtrArg->getClass(), 0),
1415 // (clang extension)
1420 case Type::BlockPointer: {
1421 const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param);
1422 const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg);
1425 return Sema::TDK_NonDeducedMismatch;
1427 return DeduceTemplateArguments(S, TemplateParams,
1428 BlockPtrParam->getPointeeType(),
1429 BlockPtrArg->getPointeeType(), Info,
1433 // (clang extension)
1435 // T __attribute__(((ext_vector_type(<integral constant>))))
1436 case Type::ExtVector: {
1437 const ExtVectorType *VectorParam = cast<ExtVectorType>(Param);
1438 if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1439 // Make sure that the vectors have the same number of elements.
1440 if (VectorParam->getNumElements() != VectorArg->getNumElements())
1441 return Sema::TDK_NonDeducedMismatch;
1443 // Perform deduction on the element types.
1444 return DeduceTemplateArguments(S, TemplateParams,
1445 VectorParam->getElementType(),
1446 VectorArg->getElementType(),
1451 if (const DependentSizedExtVectorType *VectorArg
1452 = dyn_cast<DependentSizedExtVectorType>(Arg)) {
1453 // We can't check the number of elements, since the argument has a
1454 // dependent number of elements. This can only occur during partial
1457 // Perform deduction on the element types.
1458 return DeduceTemplateArguments(S, TemplateParams,
1459 VectorParam->getElementType(),
1460 VectorArg->getElementType(),
1465 return Sema::TDK_NonDeducedMismatch;
1468 // (clang extension)
1470 // T __attribute__(((ext_vector_type(N))))
1471 case Type::DependentSizedExtVector: {
1472 const DependentSizedExtVectorType *VectorParam
1473 = cast<DependentSizedExtVectorType>(Param);
1475 if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1476 // Perform deduction on the element types.
1477 if (Sema::TemplateDeductionResult Result
1478 = DeduceTemplateArguments(S, TemplateParams,
1479 VectorParam->getElementType(),
1480 VectorArg->getElementType(),
1485 // Perform deduction on the vector size, if we can.
1486 NonTypeTemplateParmDecl *NTTP
1487 = getDeducedParameterFromExpr(VectorParam->getSizeExpr());
1489 return Sema::TDK_Success;
1491 llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
1492 ArgSize = VectorArg->getNumElements();
1493 return DeduceNonTypeTemplateArgument(S, NTTP, ArgSize, S.Context.IntTy,
1494 false, Info, Deduced);
1497 if (const DependentSizedExtVectorType *VectorArg
1498 = dyn_cast<DependentSizedExtVectorType>(Arg)) {
1499 // Perform deduction on the element types.
1500 if (Sema::TemplateDeductionResult Result
1501 = DeduceTemplateArguments(S, TemplateParams,
1502 VectorParam->getElementType(),
1503 VectorArg->getElementType(),
1508 // Perform deduction on the vector size, if we can.
1509 NonTypeTemplateParmDecl *NTTP
1510 = getDeducedParameterFromExpr(VectorParam->getSizeExpr());
1512 return Sema::TDK_Success;
1514 return DeduceNonTypeTemplateArgument(S, NTTP, VectorArg->getSizeExpr(),
1518 return Sema::TDK_NonDeducedMismatch;
1521 case Type::TypeOfExpr:
1523 case Type::DependentName:
1524 case Type::UnresolvedUsing:
1525 case Type::Decltype:
1526 case Type::UnaryTransform:
1528 case Type::DependentTemplateSpecialization:
1529 case Type::PackExpansion:
1530 // No template argument deduction for these types
1531 return Sema::TDK_Success;
1534 return Sema::TDK_Success;
1537 static Sema::TemplateDeductionResult
1538 DeduceTemplateArguments(Sema &S,
1539 TemplateParameterList *TemplateParams,
1540 const TemplateArgument &Param,
1541 TemplateArgument Arg,
1542 TemplateDeductionInfo &Info,
1543 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1544 // If the template argument is a pack expansion, perform template argument
1545 // deduction against the pattern of that expansion. This only occurs during
1546 // partial ordering.
1547 if (Arg.isPackExpansion())
1548 Arg = Arg.getPackExpansionPattern();
1550 switch (Param.getKind()) {
1551 case TemplateArgument::Null:
1552 llvm_unreachable("Null template argument in parameter list");
1554 case TemplateArgument::Type:
1555 if (Arg.getKind() == TemplateArgument::Type)
1556 return DeduceTemplateArguments(S, TemplateParams, Param.getAsType(),
1557 Arg.getAsType(), Info, Deduced, 0);
1558 Info.FirstArg = Param;
1559 Info.SecondArg = Arg;
1560 return Sema::TDK_NonDeducedMismatch;
1562 case TemplateArgument::Template:
1563 if (Arg.getKind() == TemplateArgument::Template)
1564 return DeduceTemplateArguments(S, TemplateParams,
1565 Param.getAsTemplate(),
1566 Arg.getAsTemplate(), Info, Deduced);
1567 Info.FirstArg = Param;
1568 Info.SecondArg = Arg;
1569 return Sema::TDK_NonDeducedMismatch;
1571 case TemplateArgument::TemplateExpansion:
1572 llvm_unreachable("caller should handle pack expansions");
1575 case TemplateArgument::Declaration:
1576 if (Arg.getKind() == TemplateArgument::Declaration &&
1577 Param.getAsDecl()->getCanonicalDecl() ==
1578 Arg.getAsDecl()->getCanonicalDecl())
1579 return Sema::TDK_Success;
1581 Info.FirstArg = Param;
1582 Info.SecondArg = Arg;
1583 return Sema::TDK_NonDeducedMismatch;
1585 case TemplateArgument::Integral:
1586 if (Arg.getKind() == TemplateArgument::Integral) {
1587 if (hasSameExtendedValue(*Param.getAsIntegral(), *Arg.getAsIntegral()))
1588 return Sema::TDK_Success;
1590 Info.FirstArg = Param;
1591 Info.SecondArg = Arg;
1592 return Sema::TDK_NonDeducedMismatch;
1595 if (Arg.getKind() == TemplateArgument::Expression) {
1596 Info.FirstArg = Param;
1597 Info.SecondArg = Arg;
1598 return Sema::TDK_NonDeducedMismatch;
1601 Info.FirstArg = Param;
1602 Info.SecondArg = Arg;
1603 return Sema::TDK_NonDeducedMismatch;
1605 case TemplateArgument::Expression: {
1606 if (NonTypeTemplateParmDecl *NTTP
1607 = getDeducedParameterFromExpr(Param.getAsExpr())) {
1608 if (Arg.getKind() == TemplateArgument::Integral)
1609 return DeduceNonTypeTemplateArgument(S, NTTP,
1610 *Arg.getAsIntegral(),
1611 Arg.getIntegralType(),
1612 /*ArrayBound=*/false,
1614 if (Arg.getKind() == TemplateArgument::Expression)
1615 return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsExpr(),
1617 if (Arg.getKind() == TemplateArgument::Declaration)
1618 return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsDecl(),
1621 Info.FirstArg = Param;
1622 Info.SecondArg = Arg;
1623 return Sema::TDK_NonDeducedMismatch;
1626 // Can't deduce anything, but that's okay.
1627 return Sema::TDK_Success;
1629 case TemplateArgument::Pack:
1630 llvm_unreachable("Argument packs should be expanded by the caller!");
1633 return Sema::TDK_Success;
1636 /// \brief Determine whether there is a template argument to be used for
1639 /// This routine "expands" argument packs in-place, overriding its input
1640 /// parameters so that \c Args[ArgIdx] will be the available template argument.
1642 /// \returns true if there is another template argument (which will be at
1643 /// \c Args[ArgIdx]), false otherwise.
1644 static bool hasTemplateArgumentForDeduction(const TemplateArgument *&Args,
1646 unsigned &NumArgs) {
1647 if (ArgIdx == NumArgs)
1650 const TemplateArgument &Arg = Args[ArgIdx];
1651 if (Arg.getKind() != TemplateArgument::Pack)
1654 assert(ArgIdx == NumArgs - 1 && "Pack not at the end of argument list?");
1655 Args = Arg.pack_begin();
1656 NumArgs = Arg.pack_size();
1658 return ArgIdx < NumArgs;
1661 /// \brief Determine whether the given set of template arguments has a pack
1662 /// expansion that is not the last template argument.
1663 static bool hasPackExpansionBeforeEnd(const TemplateArgument *Args,
1665 unsigned ArgIdx = 0;
1666 while (ArgIdx < NumArgs) {
1667 const TemplateArgument &Arg = Args[ArgIdx];
1669 // Unwrap argument packs.
1670 if (Args[ArgIdx].getKind() == TemplateArgument::Pack) {
1671 Args = Arg.pack_begin();
1672 NumArgs = Arg.pack_size();
1678 if (ArgIdx == NumArgs)
1681 if (Arg.isPackExpansion())
1688 static Sema::TemplateDeductionResult
1689 DeduceTemplateArguments(Sema &S,
1690 TemplateParameterList *TemplateParams,
1691 const TemplateArgument *Params, unsigned NumParams,
1692 const TemplateArgument *Args, unsigned NumArgs,
1693 TemplateDeductionInfo &Info,
1694 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
1695 bool NumberOfArgumentsMustMatch) {
1696 // C++0x [temp.deduct.type]p9:
1697 // If the template argument list of P contains a pack expansion that is not
1698 // the last template argument, the entire template argument list is a
1699 // non-deduced context.
1700 if (hasPackExpansionBeforeEnd(Params, NumParams))
1701 return Sema::TDK_Success;
1703 // C++0x [temp.deduct.type]p9:
1704 // If P has a form that contains <T> or <i>, then each argument Pi of the
1705 // respective template argument list P is compared with the corresponding
1706 // argument Ai of the corresponding template argument list of A.
1707 unsigned ArgIdx = 0, ParamIdx = 0;
1708 for (; hasTemplateArgumentForDeduction(Params, ParamIdx, NumParams);
1710 if (!Params[ParamIdx].isPackExpansion()) {
1711 // The simple case: deduce template arguments by matching Pi and Ai.
1713 // Check whether we have enough arguments.
1714 if (!hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs))
1715 return NumberOfArgumentsMustMatch? Sema::TDK_NonDeducedMismatch
1716 : Sema::TDK_Success;
1718 if (Args[ArgIdx].isPackExpansion()) {
1719 // FIXME: We follow the logic of C++0x [temp.deduct.type]p22 here,
1720 // but applied to pack expansions that are template arguments.
1721 return Sema::TDK_NonDeducedMismatch;
1724 // Perform deduction for this Pi/Ai pair.
1725 if (Sema::TemplateDeductionResult Result
1726 = DeduceTemplateArguments(S, TemplateParams,
1727 Params[ParamIdx], Args[ArgIdx],
1731 // Move to the next argument.
1736 // The parameter is a pack expansion.
1738 // C++0x [temp.deduct.type]p9:
1739 // If Pi is a pack expansion, then the pattern of Pi is compared with
1740 // each remaining argument in the template argument list of A. Each
1741 // comparison deduces template arguments for subsequent positions in the
1742 // template parameter packs expanded by Pi.
1743 TemplateArgument Pattern = Params[ParamIdx].getPackExpansionPattern();
1745 // Compute the set of template parameter indices that correspond to
1746 // parameter packs expanded by the pack expansion.
1747 SmallVector<unsigned, 2> PackIndices;
1749 llvm::BitVector SawIndices(TemplateParams->size());
1750 SmallVector<UnexpandedParameterPack, 2> Unexpanded;
1751 S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
1752 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
1753 unsigned Depth, Index;
1754 llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
1755 if (Depth == 0 && !SawIndices[Index]) {
1756 SawIndices[Index] = true;
1757 PackIndices.push_back(Index);
1761 assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?");
1763 // FIXME: If there are no remaining arguments, we can bail out early
1764 // and set any deduced parameter packs to an empty argument pack.
1765 // The latter part of this is a (minor) correctness issue.
1767 // Save the deduced template arguments for each parameter pack expanded
1768 // by this pack expansion, then clear out the deduction.
1769 SmallVector<DeducedTemplateArgument, 2>
1770 SavedPacks(PackIndices.size());
1771 SmallVector<SmallVector<DeducedTemplateArgument, 4>, 2>
1772 NewlyDeducedPacks(PackIndices.size());
1773 PrepareArgumentPackDeduction(S, Deduced, PackIndices, SavedPacks,
1776 // Keep track of the deduced template arguments for each parameter pack
1777 // expanded by this pack expansion (the outer index) and for each
1778 // template argument (the inner SmallVectors).
1779 bool HasAnyArguments = false;
1780 while (hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs)) {
1781 HasAnyArguments = true;
1783 // Deduce template arguments from the pattern.
1784 if (Sema::TemplateDeductionResult Result
1785 = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx],
1789 // Capture the deduced template arguments for each parameter pack expanded
1790 // by this pack expansion, add them to the list of arguments we've deduced
1791 // for that pack, then clear out the deduced argument.
1792 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
1793 DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]];
1794 if (!DeducedArg.isNull()) {
1795 NewlyDeducedPacks[I].push_back(DeducedArg);
1796 DeducedArg = DeducedTemplateArgument();
1803 // Build argument packs for each of the parameter packs expanded by this
1805 if (Sema::TemplateDeductionResult Result
1806 = FinishArgumentPackDeduction(S, TemplateParams, HasAnyArguments,
1807 Deduced, PackIndices, SavedPacks,
1808 NewlyDeducedPacks, Info))
1812 // If there is an argument remaining, then we had too many arguments.
1813 if (NumberOfArgumentsMustMatch &&
1814 hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs))
1815 return Sema::TDK_NonDeducedMismatch;
1817 return Sema::TDK_Success;
1820 static Sema::TemplateDeductionResult
1821 DeduceTemplateArguments(Sema &S,
1822 TemplateParameterList *TemplateParams,
1823 const TemplateArgumentList &ParamList,
1824 const TemplateArgumentList &ArgList,
1825 TemplateDeductionInfo &Info,
1826 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1827 return DeduceTemplateArguments(S, TemplateParams,
1828 ParamList.data(), ParamList.size(),
1829 ArgList.data(), ArgList.size(),
1833 /// \brief Determine whether two template arguments are the same.
1834 static bool isSameTemplateArg(ASTContext &Context,
1835 const TemplateArgument &X,
1836 const TemplateArgument &Y) {
1837 if (X.getKind() != Y.getKind())
1840 switch (X.getKind()) {
1841 case TemplateArgument::Null:
1842 llvm_unreachable("Comparing NULL template argument");
1844 case TemplateArgument::Type:
1845 return Context.getCanonicalType(X.getAsType()) ==
1846 Context.getCanonicalType(Y.getAsType());
1848 case TemplateArgument::Declaration:
1849 return X.getAsDecl()->getCanonicalDecl() ==
1850 Y.getAsDecl()->getCanonicalDecl();
1852 case TemplateArgument::Template:
1853 case TemplateArgument::TemplateExpansion:
1854 return Context.getCanonicalTemplateName(
1855 X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() ==
1856 Context.getCanonicalTemplateName(
1857 Y.getAsTemplateOrTemplatePattern()).getAsVoidPointer();
1859 case TemplateArgument::Integral:
1860 return *X.getAsIntegral() == *Y.getAsIntegral();
1862 case TemplateArgument::Expression: {
1863 llvm::FoldingSetNodeID XID, YID;
1864 X.getAsExpr()->Profile(XID, Context, true);
1865 Y.getAsExpr()->Profile(YID, Context, true);
1869 case TemplateArgument::Pack:
1870 if (X.pack_size() != Y.pack_size())
1873 for (TemplateArgument::pack_iterator XP = X.pack_begin(),
1874 XPEnd = X.pack_end(),
1875 YP = Y.pack_begin();
1876 XP != XPEnd; ++XP, ++YP)
1877 if (!isSameTemplateArg(Context, *XP, *YP))
1886 /// \brief Allocate a TemplateArgumentLoc where all locations have
1887 /// been initialized to the given location.
1889 /// \param S The semantic analysis object.
1891 /// \param The template argument we are producing template argument
1892 /// location information for.
1894 /// \param NTTPType For a declaration template argument, the type of
1895 /// the non-type template parameter that corresponds to this template
1898 /// \param Loc The source location to use for the resulting template
1900 static TemplateArgumentLoc
1901 getTrivialTemplateArgumentLoc(Sema &S,
1902 const TemplateArgument &Arg,
1904 SourceLocation Loc) {
1905 switch (Arg.getKind()) {
1906 case TemplateArgument::Null:
1907 llvm_unreachable("Can't get a NULL template argument here");
1910 case TemplateArgument::Type:
1911 return TemplateArgumentLoc(Arg,
1912 S.Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc));
1914 case TemplateArgument::Declaration: {
1916 = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
1918 return TemplateArgumentLoc(TemplateArgument(E), E);
1921 case TemplateArgument::Integral: {
1923 = S.BuildExpressionFromIntegralTemplateArgument(Arg, Loc).takeAs<Expr>();
1924 return TemplateArgumentLoc(TemplateArgument(E), E);
1927 case TemplateArgument::Template:
1928 case TemplateArgument::TemplateExpansion: {
1929 NestedNameSpecifierLocBuilder Builder;
1930 TemplateName Template = Arg.getAsTemplate();
1931 if (DependentTemplateName *DTN = Template.getAsDependentTemplateName())
1932 Builder.MakeTrivial(S.Context, DTN->getQualifier(), Loc);
1933 else if (QualifiedTemplateName *QTN = Template.getAsQualifiedTemplateName())
1934 Builder.MakeTrivial(S.Context, QTN->getQualifier(), Loc);
1936 if (Arg.getKind() == TemplateArgument::Template)
1937 return TemplateArgumentLoc(Arg,
1938 Builder.getWithLocInContext(S.Context),
1942 return TemplateArgumentLoc(Arg, Builder.getWithLocInContext(S.Context),
1946 case TemplateArgument::Expression:
1947 return TemplateArgumentLoc(Arg, Arg.getAsExpr());
1949 case TemplateArgument::Pack:
1950 return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo());
1953 return TemplateArgumentLoc();
1957 /// \brief Convert the given deduced template argument and add it to the set of
1958 /// fully-converted template arguments.
1959 static bool ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param,
1960 DeducedTemplateArgument Arg,
1961 NamedDecl *Template,
1963 unsigned ArgumentPackIndex,
1964 TemplateDeductionInfo &Info,
1965 bool InFunctionTemplate,
1966 SmallVectorImpl<TemplateArgument> &Output) {
1967 if (Arg.getKind() == TemplateArgument::Pack) {
1968 // This is a template argument pack, so check each of its arguments against
1969 // the template parameter.
1970 SmallVector<TemplateArgument, 2> PackedArgsBuilder;
1971 for (TemplateArgument::pack_iterator PA = Arg.pack_begin(),
1972 PAEnd = Arg.pack_end();
1973 PA != PAEnd; ++PA) {
1974 // When converting the deduced template argument, append it to the
1975 // general output list. We need to do this so that the template argument
1976 // checking logic has all of the prior template arguments available.
1977 DeducedTemplateArgument InnerArg(*PA);
1978 InnerArg.setDeducedFromArrayBound(Arg.wasDeducedFromArrayBound());
1979 if (ConvertDeducedTemplateArgument(S, Param, InnerArg, Template,
1980 NTTPType, PackedArgsBuilder.size(),
1981 Info, InFunctionTemplate, Output))
1984 // Move the converted template argument into our argument pack.
1985 PackedArgsBuilder.push_back(Output.back());
1989 // Create the resulting argument pack.
1990 Output.push_back(TemplateArgument::CreatePackCopy(S.Context,
1991 PackedArgsBuilder.data(),
1992 PackedArgsBuilder.size()));
1996 // Convert the deduced template argument into a template
1997 // argument that we can check, almost as if the user had written
1998 // the template argument explicitly.
1999 TemplateArgumentLoc ArgLoc = getTrivialTemplateArgumentLoc(S, Arg, NTTPType,
2000 Info.getLocation());
2002 // Check the template argument, converting it as necessary.
2003 return S.CheckTemplateArgument(Param, ArgLoc,
2005 Template->getLocation(),
2006 Template->getSourceRange().getEnd(),
2010 ? (Arg.wasDeducedFromArrayBound()
2011 ? Sema::CTAK_DeducedFromArrayBound
2012 : Sema::CTAK_Deduced)
2013 : Sema::CTAK_Specified);
2016 /// Complete template argument deduction for a class template partial
2018 static Sema::TemplateDeductionResult
2019 FinishTemplateArgumentDeduction(Sema &S,
2020 ClassTemplatePartialSpecializationDecl *Partial,
2021 const TemplateArgumentList &TemplateArgs,
2022 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2023 TemplateDeductionInfo &Info) {
2025 Sema::SFINAETrap Trap(S);
2027 Sema::ContextRAII SavedContext(S, Partial);
2029 // C++ [temp.deduct.type]p2:
2030 // [...] or if any template argument remains neither deduced nor
2031 // explicitly specified, template argument deduction fails.
2032 SmallVector<TemplateArgument, 4> Builder;
2033 TemplateParameterList *PartialParams = Partial->getTemplateParameters();
2034 for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) {
2035 NamedDecl *Param = PartialParams->getParam(I);
2036 if (Deduced[I].isNull()) {
2037 Info.Param = makeTemplateParameter(Param);
2038 return Sema::TDK_Incomplete;
2041 // We have deduced this argument, so it still needs to be
2042 // checked and converted.
2044 // First, for a non-type template parameter type that is
2045 // initialized by a declaration, we need the type of the
2046 // corresponding non-type template parameter.
2048 if (NonTypeTemplateParmDecl *NTTP
2049 = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2050 NTTPType = NTTP->getType();
2051 if (NTTPType->isDependentType()) {
2052 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2053 Builder.data(), Builder.size());
2054 NTTPType = S.SubstType(NTTPType,
2055 MultiLevelTemplateArgumentList(TemplateArgs),
2056 NTTP->getLocation(),
2057 NTTP->getDeclName());
2058 if (NTTPType.isNull()) {
2059 Info.Param = makeTemplateParameter(Param);
2060 // FIXME: These template arguments are temporary. Free them!
2061 Info.reset(TemplateArgumentList::CreateCopy(S.Context,
2064 return Sema::TDK_SubstitutionFailure;
2069 if (ConvertDeducedTemplateArgument(S, Param, Deduced[I],
2070 Partial, NTTPType, 0, Info, false,
2072 Info.Param = makeTemplateParameter(Param);
2073 // FIXME: These template arguments are temporary. Free them!
2074 Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2076 return Sema::TDK_SubstitutionFailure;
2080 // Form the template argument list from the deduced template arguments.
2081 TemplateArgumentList *DeducedArgumentList
2082 = TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2085 Info.reset(DeducedArgumentList);
2087 // Substitute the deduced template arguments into the template
2088 // arguments of the class template partial specialization, and
2089 // verify that the instantiated template arguments are both valid
2090 // and are equivalent to the template arguments originally provided
2091 // to the class template.
2092 LocalInstantiationScope InstScope(S);
2093 ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate();
2094 const TemplateArgumentLoc *PartialTemplateArgs
2095 = Partial->getTemplateArgsAsWritten();
2097 // Note that we don't provide the langle and rangle locations.
2098 TemplateArgumentListInfo InstArgs;
2100 if (S.Subst(PartialTemplateArgs,
2101 Partial->getNumTemplateArgsAsWritten(),
2102 InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
2103 unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2104 if (ParamIdx >= Partial->getTemplateParameters()->size())
2105 ParamIdx = Partial->getTemplateParameters()->size() - 1;
2108 = const_cast<NamedDecl *>(
2109 Partial->getTemplateParameters()->getParam(ParamIdx));
2110 Info.Param = makeTemplateParameter(Param);
2111 Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
2112 return Sema::TDK_SubstitutionFailure;
2115 SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2116 if (S.CheckTemplateArgumentList(ClassTemplate, Partial->getLocation(),
2117 InstArgs, false, ConvertedInstArgs))
2118 return Sema::TDK_SubstitutionFailure;
2120 TemplateParameterList *TemplateParams
2121 = ClassTemplate->getTemplateParameters();
2122 for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2123 TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2124 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2125 Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2126 Info.FirstArg = TemplateArgs[I];
2127 Info.SecondArg = InstArg;
2128 return Sema::TDK_NonDeducedMismatch;
2132 if (Trap.hasErrorOccurred())
2133 return Sema::TDK_SubstitutionFailure;
2135 return Sema::TDK_Success;
2138 /// \brief Perform template argument deduction to determine whether
2139 /// the given template arguments match the given class template
2140 /// partial specialization per C++ [temp.class.spec.match].
2141 Sema::TemplateDeductionResult
2142 Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
2143 const TemplateArgumentList &TemplateArgs,
2144 TemplateDeductionInfo &Info) {
2145 // C++ [temp.class.spec.match]p2:
2146 // A partial specialization matches a given actual template
2147 // argument list if the template arguments of the partial
2148 // specialization can be deduced from the actual template argument
2150 SFINAETrap Trap(*this);
2151 SmallVector<DeducedTemplateArgument, 4> Deduced;
2152 Deduced.resize(Partial->getTemplateParameters()->size());
2153 if (TemplateDeductionResult Result
2154 = ::DeduceTemplateArguments(*this,
2155 Partial->getTemplateParameters(),
2156 Partial->getTemplateArgs(),
2157 TemplateArgs, Info, Deduced))
2160 InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial,
2161 Deduced.data(), Deduced.size(), Info);
2163 return TDK_InstantiationDepth;
2165 if (Trap.hasErrorOccurred())
2166 return Sema::TDK_SubstitutionFailure;
2168 return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs,
2172 /// \brief Determine whether the given type T is a simple-template-id type.
2173 static bool isSimpleTemplateIdType(QualType T) {
2174 if (const TemplateSpecializationType *Spec
2175 = T->getAs<TemplateSpecializationType>())
2176 return Spec->getTemplateName().getAsTemplateDecl() != 0;
2181 /// \brief Substitute the explicitly-provided template arguments into the
2182 /// given function template according to C++ [temp.arg.explicit].
2184 /// \param FunctionTemplate the function template into which the explicit
2185 /// template arguments will be substituted.
2187 /// \param ExplicitTemplateArguments the explicitly-specified template
2190 /// \param Deduced the deduced template arguments, which will be populated
2191 /// with the converted and checked explicit template arguments.
2193 /// \param ParamTypes will be populated with the instantiated function
2196 /// \param FunctionType if non-NULL, the result type of the function template
2197 /// will also be instantiated and the pointed-to value will be updated with
2198 /// the instantiated function type.
2200 /// \param Info if substitution fails for any reason, this object will be
2201 /// populated with more information about the failure.
2203 /// \returns TDK_Success if substitution was successful, or some failure
2205 Sema::TemplateDeductionResult
2206 Sema::SubstituteExplicitTemplateArguments(
2207 FunctionTemplateDecl *FunctionTemplate,
2208 TemplateArgumentListInfo &ExplicitTemplateArgs,
2209 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2210 SmallVectorImpl<QualType> &ParamTypes,
2211 QualType *FunctionType,
2212 TemplateDeductionInfo &Info) {
2213 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
2214 TemplateParameterList *TemplateParams
2215 = FunctionTemplate->getTemplateParameters();
2217 if (ExplicitTemplateArgs.size() == 0) {
2218 // No arguments to substitute; just copy over the parameter types and
2219 // fill in the function type.
2220 for (FunctionDecl::param_iterator P = Function->param_begin(),
2221 PEnd = Function->param_end();
2224 ParamTypes.push_back((*P)->getType());
2227 *FunctionType = Function->getType();
2231 // Substitution of the explicit template arguments into a function template
2232 /// is a SFINAE context. Trap any errors that might occur.
2233 SFINAETrap Trap(*this);
2235 // C++ [temp.arg.explicit]p3:
2236 // Template arguments that are present shall be specified in the
2237 // declaration order of their corresponding template-parameters. The
2238 // template argument list shall not specify more template-arguments than
2239 // there are corresponding template-parameters.
2240 SmallVector<TemplateArgument, 4> Builder;
2242 // Enter a new template instantiation context where we check the
2243 // explicitly-specified template arguments against this function template,
2244 // and then substitute them into the function parameter types.
2245 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(),
2246 FunctionTemplate, Deduced.data(), Deduced.size(),
2247 ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution,
2250 return TDK_InstantiationDepth;
2252 if (CheckTemplateArgumentList(FunctionTemplate,
2254 ExplicitTemplateArgs,
2256 Builder) || Trap.hasErrorOccurred()) {
2257 unsigned Index = Builder.size();
2258 if (Index >= TemplateParams->size())
2259 Index = TemplateParams->size() - 1;
2260 Info.Param = makeTemplateParameter(TemplateParams->getParam(Index));
2261 return TDK_InvalidExplicitArguments;
2264 // Form the template argument list from the explicitly-specified
2265 // template arguments.
2266 TemplateArgumentList *ExplicitArgumentList
2267 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
2268 Info.reset(ExplicitArgumentList);
2270 // Template argument deduction and the final substitution should be
2271 // done in the context of the templated declaration. Explicit
2272 // argument substitution, on the other hand, needs to happen in the
2274 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2276 // If we deduced template arguments for a template parameter pack,
2277 // note that the template argument pack is partially substituted and record
2278 // the explicit template arguments. They'll be used as part of deduction
2279 // for this template parameter pack.
2280 for (unsigned I = 0, N = Builder.size(); I != N; ++I) {
2281 const TemplateArgument &Arg = Builder[I];
2282 if (Arg.getKind() == TemplateArgument::Pack) {
2283 CurrentInstantiationScope->SetPartiallySubstitutedPack(
2284 TemplateParams->getParam(I),
2291 // Instantiate the types of each of the function parameters given the
2292 // explicitly-specified template arguments.
2293 if (SubstParmTypes(Function->getLocation(),
2294 Function->param_begin(), Function->getNumParams(),
2295 MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2297 return TDK_SubstitutionFailure;
2299 // If the caller wants a full function type back, instantiate the return
2300 // type and form that function type.
2302 // FIXME: exception-specifications?
2303 const FunctionProtoType *Proto
2304 = Function->getType()->getAs<FunctionProtoType>();
2305 assert(Proto && "Function template does not have a prototype?");
2308 = SubstType(Proto->getResultType(),
2309 MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2310 Function->getTypeSpecStartLoc(),
2311 Function->getDeclName());
2312 if (ResultType.isNull() || Trap.hasErrorOccurred())
2313 return TDK_SubstitutionFailure;
2315 *FunctionType = BuildFunctionType(ResultType,
2316 ParamTypes.data(), ParamTypes.size(),
2317 Proto->isVariadic(),
2318 Proto->getTypeQuals(),
2319 Proto->getRefQualifier(),
2320 Function->getLocation(),
2321 Function->getDeclName(),
2322 Proto->getExtInfo());
2323 if (FunctionType->isNull() || Trap.hasErrorOccurred())
2324 return TDK_SubstitutionFailure;
2327 // C++ [temp.arg.explicit]p2:
2328 // Trailing template arguments that can be deduced (14.8.2) may be
2329 // omitted from the list of explicit template-arguments. If all of the
2330 // template arguments can be deduced, they may all be omitted; in this
2331 // case, the empty template argument list <> itself may also be omitted.
2333 // Take all of the explicitly-specified arguments and put them into
2334 // the set of deduced template arguments. Explicitly-specified
2335 // parameter packs, however, will be set to NULL since the deduction
2336 // mechanisms handle explicitly-specified argument packs directly.
2337 Deduced.reserve(TemplateParams->size());
2338 for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) {
2339 const TemplateArgument &Arg = ExplicitArgumentList->get(I);
2340 if (Arg.getKind() == TemplateArgument::Pack)
2341 Deduced.push_back(DeducedTemplateArgument());
2343 Deduced.push_back(Arg);
2349 /// \brief Check whether the deduced argument type for a call to a function
2350 /// template matches the actual argument type per C++ [temp.deduct.call]p4.
2352 CheckOriginalCallArgDeduction(Sema &S, Sema::OriginalCallArg OriginalArg,
2353 QualType DeducedA) {
2354 ASTContext &Context = S.Context;
2356 QualType A = OriginalArg.OriginalArgType;
2357 QualType OriginalParamType = OriginalArg.OriginalParamType;
2359 // Check for type equality (top-level cv-qualifiers are ignored).
2360 if (Context.hasSameUnqualifiedType(A, DeducedA))
2363 // Strip off references on the argument types; they aren't needed for
2364 // the following checks.
2365 if (const ReferenceType *DeducedARef = DeducedA->getAs<ReferenceType>())
2366 DeducedA = DeducedARef->getPointeeType();
2367 if (const ReferenceType *ARef = A->getAs<ReferenceType>())
2368 A = ARef->getPointeeType();
2370 // C++ [temp.deduct.call]p4:
2371 // [...] However, there are three cases that allow a difference:
2372 // - If the original P is a reference type, the deduced A (i.e., the
2373 // type referred to by the reference) can be more cv-qualified than
2374 // the transformed A.
2375 if (const ReferenceType *OriginalParamRef
2376 = OriginalParamType->getAs<ReferenceType>()) {
2377 // We don't want to keep the reference around any more.
2378 OriginalParamType = OriginalParamRef->getPointeeType();
2380 Qualifiers AQuals = A.getQualifiers();
2381 Qualifiers DeducedAQuals = DeducedA.getQualifiers();
2382 if (AQuals == DeducedAQuals) {
2383 // Qualifiers match; there's nothing to do.
2384 } else if (!DeducedAQuals.compatiblyIncludes(AQuals)) {
2387 // Qualifiers are compatible, so have the argument type adopt the
2388 // deduced argument type's qualifiers as if we had performed the
2389 // qualification conversion.
2390 A = Context.getQualifiedType(A.getUnqualifiedType(), DeducedAQuals);
2394 // - The transformed A can be another pointer or pointer to member
2395 // type that can be converted to the deduced A via a qualification
2398 // Also allow conversions which merely strip [[noreturn]] from function types
2399 // (recursively) as an extension.
2400 // FIXME: Currently, this doesn't place nicely with qualfication conversions.
2401 bool ObjCLifetimeConversion = false;
2403 if ((A->isAnyPointerType() || A->isMemberPointerType()) &&
2404 (S.IsQualificationConversion(A, DeducedA, false,
2405 ObjCLifetimeConversion) ||
2406 S.IsNoReturnConversion(A, DeducedA, ResultTy)))
2410 // - If P is a class and P has the form simple-template-id, then the
2411 // transformed A can be a derived class of the deduced A. [...]
2412 // [...] Likewise, if P is a pointer to a class of the form
2413 // simple-template-id, the transformed A can be a pointer to a
2414 // derived class pointed to by the deduced A.
2415 if (const PointerType *OriginalParamPtr
2416 = OriginalParamType->getAs<PointerType>()) {
2417 if (const PointerType *DeducedAPtr = DeducedA->getAs<PointerType>()) {
2418 if (const PointerType *APtr = A->getAs<PointerType>()) {
2419 if (A->getPointeeType()->isRecordType()) {
2420 OriginalParamType = OriginalParamPtr->getPointeeType();
2421 DeducedA = DeducedAPtr->getPointeeType();
2422 A = APtr->getPointeeType();
2428 if (Context.hasSameUnqualifiedType(A, DeducedA))
2431 if (A->isRecordType() && isSimpleTemplateIdType(OriginalParamType) &&
2432 S.IsDerivedFrom(A, DeducedA))
2438 /// \brief Finish template argument deduction for a function template,
2439 /// checking the deduced template arguments for completeness and forming
2440 /// the function template specialization.
2442 /// \param OriginalCallArgs If non-NULL, the original call arguments against
2443 /// which the deduced argument types should be compared.
2444 Sema::TemplateDeductionResult
2445 Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate,
2446 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2447 unsigned NumExplicitlySpecified,
2448 FunctionDecl *&Specialization,
2449 TemplateDeductionInfo &Info,
2450 SmallVectorImpl<OriginalCallArg> const *OriginalCallArgs) {
2451 TemplateParameterList *TemplateParams
2452 = FunctionTemplate->getTemplateParameters();
2454 // Template argument deduction for function templates in a SFINAE context.
2455 // Trap any errors that might occur.
2456 SFINAETrap Trap(*this);
2458 // Enter a new template instantiation context while we instantiate the
2459 // actual function declaration.
2460 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(),
2461 FunctionTemplate, Deduced.data(), Deduced.size(),
2462 ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution,
2465 return TDK_InstantiationDepth;
2467 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2469 // C++ [temp.deduct.type]p2:
2470 // [...] or if any template argument remains neither deduced nor
2471 // explicitly specified, template argument deduction fails.
2472 SmallVector<TemplateArgument, 4> Builder;
2473 for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) {
2474 NamedDecl *Param = TemplateParams->getParam(I);
2476 if (!Deduced[I].isNull()) {
2477 if (I < NumExplicitlySpecified) {
2478 // We have already fully type-checked and converted this
2479 // argument, because it was explicitly-specified. Just record the
2480 // presence of this argument.
2481 Builder.push_back(Deduced[I]);
2485 // We have deduced this argument, so it still needs to be
2486 // checked and converted.
2488 // First, for a non-type template parameter type that is
2489 // initialized by a declaration, we need the type of the
2490 // corresponding non-type template parameter.
2492 if (NonTypeTemplateParmDecl *NTTP
2493 = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2494 NTTPType = NTTP->getType();
2495 if (NTTPType->isDependentType()) {
2496 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2497 Builder.data(), Builder.size());
2498 NTTPType = SubstType(NTTPType,
2499 MultiLevelTemplateArgumentList(TemplateArgs),
2500 NTTP->getLocation(),
2501 NTTP->getDeclName());
2502 if (NTTPType.isNull()) {
2503 Info.Param = makeTemplateParameter(Param);
2504 // FIXME: These template arguments are temporary. Free them!
2505 Info.reset(TemplateArgumentList::CreateCopy(Context,
2508 return TDK_SubstitutionFailure;
2513 if (ConvertDeducedTemplateArgument(*this, Param, Deduced[I],
2514 FunctionTemplate, NTTPType, 0, Info,
2516 Info.Param = makeTemplateParameter(Param);
2517 // FIXME: These template arguments are temporary. Free them!
2518 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2520 return TDK_SubstitutionFailure;
2526 // C++0x [temp.arg.explicit]p3:
2527 // A trailing template parameter pack (14.5.3) not otherwise deduced will
2528 // be deduced to an empty sequence of template arguments.
2529 // FIXME: Where did the word "trailing" come from?
2530 if (Param->isTemplateParameterPack()) {
2531 // We may have had explicitly-specified template arguments for this
2532 // template parameter pack. If so, our empty deduction extends the
2533 // explicitly-specified set (C++0x [temp.arg.explicit]p9).
2534 const TemplateArgument *ExplicitArgs;
2535 unsigned NumExplicitArgs;
2536 if (CurrentInstantiationScope->getPartiallySubstitutedPack(&ExplicitArgs,
2539 Builder.push_back(TemplateArgument(ExplicitArgs, NumExplicitArgs));
2541 Builder.push_back(TemplateArgument(0, 0));
2546 // Substitute into the default template argument, if available.
2547 TemplateArgumentLoc DefArg
2548 = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate,
2549 FunctionTemplate->getLocation(),
2550 FunctionTemplate->getSourceRange().getEnd(),
2554 // If there was no default argument, deduction is incomplete.
2555 if (DefArg.getArgument().isNull()) {
2556 Info.Param = makeTemplateParameter(
2557 const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2558 return TDK_Incomplete;
2561 // Check whether we can actually use the default argument.
2562 if (CheckTemplateArgument(Param, DefArg,
2564 FunctionTemplate->getLocation(),
2565 FunctionTemplate->getSourceRange().getEnd(),
2568 Info.Param = makeTemplateParameter(
2569 const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2570 // FIXME: These template arguments are temporary. Free them!
2571 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2573 return TDK_SubstitutionFailure;
2576 // If we get here, we successfully used the default template argument.
2579 // Form the template argument list from the deduced template arguments.
2580 TemplateArgumentList *DeducedArgumentList
2581 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
2582 Info.reset(DeducedArgumentList);
2584 // Substitute the deduced template arguments into the function template
2585 // declaration to produce the function template specialization.
2586 DeclContext *Owner = FunctionTemplate->getDeclContext();
2587 if (FunctionTemplate->getFriendObjectKind())
2588 Owner = FunctionTemplate->getLexicalDeclContext();
2589 Specialization = cast_or_null<FunctionDecl>(
2590 SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner,
2591 MultiLevelTemplateArgumentList(*DeducedArgumentList)));
2592 if (!Specialization || Specialization->isInvalidDecl())
2593 return TDK_SubstitutionFailure;
2595 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() ==
2596 FunctionTemplate->getCanonicalDecl());
2598 // If the template argument list is owned by the function template
2599 // specialization, release it.
2600 if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList &&
2601 !Trap.hasErrorOccurred())
2604 // There may have been an error that did not prevent us from constructing a
2605 // declaration. Mark the declaration invalid and return with a substitution
2607 if (Trap.hasErrorOccurred()) {
2608 Specialization->setInvalidDecl(true);
2609 return TDK_SubstitutionFailure;
2612 if (OriginalCallArgs) {
2613 // C++ [temp.deduct.call]p4:
2614 // In general, the deduction process attempts to find template argument
2615 // values that will make the deduced A identical to A (after the type A
2616 // is transformed as described above). [...]
2617 for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; ++I) {
2618 OriginalCallArg OriginalArg = (*OriginalCallArgs)[I];
2619 unsigned ParamIdx = OriginalArg.ArgIdx;
2621 if (ParamIdx >= Specialization->getNumParams())
2624 QualType DeducedA = Specialization->getParamDecl(ParamIdx)->getType();
2625 if (CheckOriginalCallArgDeduction(*this, OriginalArg, DeducedA))
2626 return Sema::TDK_SubstitutionFailure;
2630 // If we suppressed any diagnostics while performing template argument
2631 // deduction, and if we haven't already instantiated this declaration,
2632 // keep track of these diagnostics. They'll be emitted if this specialization
2633 // is actually used.
2634 if (Info.diag_begin() != Info.diag_end()) {
2635 llvm::DenseMap<Decl *, SmallVector<PartialDiagnosticAt, 1> >::iterator
2636 Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl());
2637 if (Pos == SuppressedDiagnostics.end())
2638 SuppressedDiagnostics[Specialization->getCanonicalDecl()]
2639 .append(Info.diag_begin(), Info.diag_end());
2645 /// Gets the type of a function for template-argument-deducton
2646 /// purposes when it's considered as part of an overload set.
2647 static QualType GetTypeOfFunction(ASTContext &Context,
2648 const OverloadExpr::FindResult &R,
2650 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn))
2651 if (Method->isInstance()) {
2652 // An instance method that's referenced in a form that doesn't
2653 // look like a member pointer is just invalid.
2654 if (!R.HasFormOfMemberPointer) return QualType();
2656 return Context.getMemberPointerType(Fn->getType(),
2657 Context.getTypeDeclType(Method->getParent()).getTypePtr());
2660 if (!R.IsAddressOfOperand) return Fn->getType();
2661 return Context.getPointerType(Fn->getType());
2664 /// Apply the deduction rules for overload sets.
2666 /// \return the null type if this argument should be treated as an
2667 /// undeduced context
2669 ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams,
2670 Expr *Arg, QualType ParamType,
2671 bool ParamWasReference) {
2673 OverloadExpr::FindResult R = OverloadExpr::find(Arg);
2675 OverloadExpr *Ovl = R.Expression;
2677 // C++0x [temp.deduct.call]p4
2679 if (ParamWasReference)
2680 TDF |= TDF_ParamWithReferenceType;
2681 if (R.IsAddressOfOperand)
2682 TDF |= TDF_IgnoreQualifiers;
2684 // If there were explicit template arguments, we can only find
2685 // something via C++ [temp.arg.explicit]p3, i.e. if the arguments
2686 // unambiguously name a full specialization.
2687 if (Ovl->hasExplicitTemplateArgs()) {
2688 // But we can still look for an explicit specialization.
2689 if (FunctionDecl *ExplicitSpec
2690 = S.ResolveSingleFunctionTemplateSpecialization(Ovl))
2691 return GetTypeOfFunction(S.Context, R, ExplicitSpec);
2695 // C++0x [temp.deduct.call]p6:
2696 // When P is a function type, pointer to function type, or pointer
2697 // to member function type:
2699 if (!ParamType->isFunctionType() &&
2700 !ParamType->isFunctionPointerType() &&
2701 !ParamType->isMemberFunctionPointerType())
2705 for (UnresolvedSetIterator I = Ovl->decls_begin(),
2706 E = Ovl->decls_end(); I != E; ++I) {
2707 NamedDecl *D = (*I)->getUnderlyingDecl();
2709 // - If the argument is an overload set containing one or more
2710 // function templates, the parameter is treated as a
2711 // non-deduced context.
2712 if (isa<FunctionTemplateDecl>(D))
2715 FunctionDecl *Fn = cast<FunctionDecl>(D);
2716 QualType ArgType = GetTypeOfFunction(S.Context, R, Fn);
2717 if (ArgType.isNull()) continue;
2719 // Function-to-pointer conversion.
2720 if (!ParamWasReference && ParamType->isPointerType() &&
2721 ArgType->isFunctionType())
2722 ArgType = S.Context.getPointerType(ArgType);
2724 // - If the argument is an overload set (not containing function
2725 // templates), trial argument deduction is attempted using each
2726 // of the members of the set. If deduction succeeds for only one
2727 // of the overload set members, that member is used as the
2728 // argument value for the deduction. If deduction succeeds for
2729 // more than one member of the overload set the parameter is
2730 // treated as a non-deduced context.
2732 // We do all of this in a fresh context per C++0x [temp.deduct.type]p2:
2733 // Type deduction is done independently for each P/A pair, and
2734 // the deduced template argument values are then combined.
2735 // So we do not reject deductions which were made elsewhere.
2736 SmallVector<DeducedTemplateArgument, 8>
2737 Deduced(TemplateParams->size());
2738 TemplateDeductionInfo Info(S.Context, Ovl->getNameLoc());
2739 Sema::TemplateDeductionResult Result
2740 = DeduceTemplateArguments(S, TemplateParams,
2742 Info, Deduced, TDF);
2743 if (Result) continue;
2744 if (!Match.isNull()) return QualType();
2751 /// \brief Perform the adjustments to the parameter and argument types
2752 /// described in C++ [temp.deduct.call].
2754 /// \returns true if the caller should not attempt to perform any template
2755 /// argument deduction based on this P/A pair.
2756 static bool AdjustFunctionParmAndArgTypesForDeduction(Sema &S,
2757 TemplateParameterList *TemplateParams,
2758 QualType &ParamType,
2762 // C++0x [temp.deduct.call]p3:
2763 // If P is a cv-qualified type, the top level cv-qualifiers of P's type
2764 // are ignored for type deduction.
2765 if (ParamType.hasQualifiers())
2766 ParamType = ParamType.getUnqualifiedType();
2767 const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>();
2769 QualType PointeeType = ParamRefType->getPointeeType();
2771 // If the argument has incomplete array type, try to complete it's type.
2772 if (ArgType->isIncompleteArrayType() &&
2773 !S.RequireCompleteExprType(Arg, S.PDiag(),
2774 std::make_pair(SourceLocation(), S.PDiag())))
2775 ArgType = Arg->getType();
2777 // [C++0x] If P is an rvalue reference to a cv-unqualified
2778 // template parameter and the argument is an lvalue, the type
2779 // "lvalue reference to A" is used in place of A for type
2781 if (isa<RValueReferenceType>(ParamType)) {
2782 if (!PointeeType.getQualifiers() &&
2783 isa<TemplateTypeParmType>(PointeeType) &&
2784 Arg->Classify(S.Context).isLValue() &&
2785 Arg->getType() != S.Context.OverloadTy &&
2786 Arg->getType() != S.Context.BoundMemberTy)
2787 ArgType = S.Context.getLValueReferenceType(ArgType);
2790 // [...] If P is a reference type, the type referred to by P is used
2791 // for type deduction.
2792 ParamType = PointeeType;
2795 // Overload sets usually make this parameter an undeduced
2796 // context, but there are sometimes special circumstances.
2797 if (ArgType == S.Context.OverloadTy) {
2798 ArgType = ResolveOverloadForDeduction(S, TemplateParams,
2801 if (ArgType.isNull())
2806 // C++0x [temp.deduct.call]p3:
2807 // [...] If P is of the form T&&, where T is a template parameter, and
2808 // the argument is an lvalue, the type A& is used in place of A for
2810 if (ParamRefType->isRValueReferenceType() &&
2811 ParamRefType->getAs<TemplateTypeParmType>() &&
2813 ArgType = S.Context.getLValueReferenceType(ArgType);
2815 // C++ [temp.deduct.call]p2:
2816 // If P is not a reference type:
2817 // - If A is an array type, the pointer type produced by the
2818 // array-to-pointer standard conversion (4.2) is used in place of
2819 // A for type deduction; otherwise,
2820 if (ArgType->isArrayType())
2821 ArgType = S.Context.getArrayDecayedType(ArgType);
2822 // - If A is a function type, the pointer type produced by the
2823 // function-to-pointer standard conversion (4.3) is used in place
2824 // of A for type deduction; otherwise,
2825 else if (ArgType->isFunctionType())
2826 ArgType = S.Context.getPointerType(ArgType);
2828 // - If A is a cv-qualified type, the top level cv-qualifiers of A's
2829 // type are ignored for type deduction.
2830 ArgType = ArgType.getUnqualifiedType();
2834 // C++0x [temp.deduct.call]p4:
2835 // In general, the deduction process attempts to find template argument
2836 // values that will make the deduced A identical to A (after the type A
2837 // is transformed as described above). [...]
2838 TDF = TDF_SkipNonDependent;
2840 // - If the original P is a reference type, the deduced A (i.e., the
2841 // type referred to by the reference) can be more cv-qualified than
2842 // the transformed A.
2844 TDF |= TDF_ParamWithReferenceType;
2845 // - The transformed A can be another pointer or pointer to member
2846 // type that can be converted to the deduced A via a qualification
2847 // conversion (4.4).
2848 if (ArgType->isPointerType() || ArgType->isMemberPointerType() ||
2849 ArgType->isObjCObjectPointerType())
2850 TDF |= TDF_IgnoreQualifiers;
2851 // - If P is a class and P has the form simple-template-id, then the
2852 // transformed A can be a derived class of the deduced A. Likewise,
2853 // if P is a pointer to a class of the form simple-template-id, the
2854 // transformed A can be a pointer to a derived class pointed to by
2856 if (isSimpleTemplateIdType(ParamType) ||
2857 (isa<PointerType>(ParamType) &&
2858 isSimpleTemplateIdType(
2859 ParamType->getAs<PointerType>()->getPointeeType())))
2860 TDF |= TDF_DerivedClass;
2865 static bool hasDeducibleTemplateParameters(Sema &S,
2866 FunctionTemplateDecl *FunctionTemplate,
2869 /// \brief Perform template argument deduction from a function call
2870 /// (C++ [temp.deduct.call]).
2872 /// \param FunctionTemplate the function template for which we are performing
2873 /// template argument deduction.
2875 /// \param ExplicitTemplateArguments the explicit template arguments provided
2878 /// \param Args the function call arguments
2880 /// \param NumArgs the number of arguments in Args
2882 /// \param Name the name of the function being called. This is only significant
2883 /// when the function template is a conversion function template, in which
2884 /// case this routine will also perform template argument deduction based on
2885 /// the function to which
2887 /// \param Specialization if template argument deduction was successful,
2888 /// this will be set to the function template specialization produced by
2889 /// template argument deduction.
2891 /// \param Info the argument will be updated to provide additional information
2892 /// about template argument deduction.
2894 /// \returns the result of template argument deduction.
2895 Sema::TemplateDeductionResult
2896 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
2897 TemplateArgumentListInfo *ExplicitTemplateArgs,
2898 Expr **Args, unsigned NumArgs,
2899 FunctionDecl *&Specialization,
2900 TemplateDeductionInfo &Info) {
2901 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
2903 // C++ [temp.deduct.call]p1:
2904 // Template argument deduction is done by comparing each function template
2905 // parameter type (call it P) with the type of the corresponding argument
2906 // of the call (call it A) as described below.
2907 unsigned CheckArgs = NumArgs;
2908 if (NumArgs < Function->getMinRequiredArguments())
2909 return TDK_TooFewArguments;
2910 else if (NumArgs > Function->getNumParams()) {
2911 const FunctionProtoType *Proto
2912 = Function->getType()->getAs<FunctionProtoType>();
2913 if (Proto->isTemplateVariadic())
2915 else if (Proto->isVariadic())
2916 CheckArgs = Function->getNumParams();
2918 return TDK_TooManyArguments;
2921 // The types of the parameters from which we will perform template argument
2923 LocalInstantiationScope InstScope(*this);
2924 TemplateParameterList *TemplateParams
2925 = FunctionTemplate->getTemplateParameters();
2926 SmallVector<DeducedTemplateArgument, 4> Deduced;
2927 SmallVector<QualType, 4> ParamTypes;
2928 unsigned NumExplicitlySpecified = 0;
2929 if (ExplicitTemplateArgs) {
2930 TemplateDeductionResult Result =
2931 SubstituteExplicitTemplateArguments(FunctionTemplate,
2932 *ExplicitTemplateArgs,
2940 NumExplicitlySpecified = Deduced.size();
2942 // Just fill in the parameter types from the function declaration.
2943 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I)
2944 ParamTypes.push_back(Function->getParamDecl(I)->getType());
2947 // Deduce template arguments from the function parameters.
2948 Deduced.resize(TemplateParams->size());
2949 unsigned ArgIdx = 0;
2950 SmallVector<OriginalCallArg, 4> OriginalCallArgs;
2951 for (unsigned ParamIdx = 0, NumParams = ParamTypes.size();
2952 ParamIdx != NumParams; ++ParamIdx) {
2953 QualType OrigParamType = ParamTypes[ParamIdx];
2954 QualType ParamType = OrigParamType;
2956 const PackExpansionType *ParamExpansion
2957 = dyn_cast<PackExpansionType>(ParamType);
2958 if (!ParamExpansion) {
2959 // Simple case: matching a function parameter to a function argument.
2960 if (ArgIdx >= CheckArgs)
2963 Expr *Arg = Args[ArgIdx++];
2964 QualType ArgType = Arg->getType();
2967 if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
2968 ParamType, ArgType, Arg,
2972 // If we have nothing to deduce, we're done.
2973 if (!hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
2976 // Keep track of the argument type and corresponding parameter index,
2977 // so we can check for compatibility between the deduced A and A.
2978 OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx-1,
2981 if (TemplateDeductionResult Result
2982 = ::DeduceTemplateArguments(*this, TemplateParams,
2983 ParamType, ArgType, Info, Deduced,
2990 // C++0x [temp.deduct.call]p1:
2991 // For a function parameter pack that occurs at the end of the
2992 // parameter-declaration-list, the type A of each remaining argument of
2993 // the call is compared with the type P of the declarator-id of the
2994 // function parameter pack. Each comparison deduces template arguments
2995 // for subsequent positions in the template parameter packs expanded by
2996 // the function parameter pack. For a function parameter pack that does
2997 // not occur at the end of the parameter-declaration-list, the type of
2998 // the parameter pack is a non-deduced context.
2999 if (ParamIdx + 1 < NumParams)
3002 QualType ParamPattern = ParamExpansion->getPattern();
3003 SmallVector<unsigned, 2> PackIndices;
3005 llvm::BitVector SawIndices(TemplateParams->size());
3006 SmallVector<UnexpandedParameterPack, 2> Unexpanded;
3007 collectUnexpandedParameterPacks(ParamPattern, Unexpanded);
3008 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
3009 unsigned Depth, Index;
3010 llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
3011 if (Depth == 0 && !SawIndices[Index]) {
3012 SawIndices[Index] = true;
3013 PackIndices.push_back(Index);
3017 assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?");
3019 // Keep track of the deduced template arguments for each parameter pack
3020 // expanded by this pack expansion (the outer index) and for each
3021 // template argument (the inner SmallVectors).
3022 SmallVector<SmallVector<DeducedTemplateArgument, 4>, 2>
3023 NewlyDeducedPacks(PackIndices.size());
3024 SmallVector<DeducedTemplateArgument, 2>
3025 SavedPacks(PackIndices.size());
3026 PrepareArgumentPackDeduction(*this, Deduced, PackIndices, SavedPacks,
3028 bool HasAnyArguments = false;
3029 for (; ArgIdx < NumArgs; ++ArgIdx) {
3030 HasAnyArguments = true;
3032 QualType OrigParamType = ParamPattern;
3033 ParamType = OrigParamType;
3034 Expr *Arg = Args[ArgIdx];
3035 QualType ArgType = Arg->getType();
3038 if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
3039 ParamType, ArgType, Arg,
3041 // We can't actually perform any deduction for this argument, so stop
3042 // deduction at this point.
3047 // Keep track of the argument type and corresponding argument index,
3048 // so we can check for compatibility between the deduced A and A.
3049 if (hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
3050 OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx,
3053 if (TemplateDeductionResult Result
3054 = ::DeduceTemplateArguments(*this, TemplateParams,
3055 ParamType, ArgType, Info, Deduced,
3059 // Capture the deduced template arguments for each parameter pack expanded
3060 // by this pack expansion, add them to the list of arguments we've deduced
3061 // for that pack, then clear out the deduced argument.
3062 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
3063 DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]];
3064 if (!DeducedArg.isNull()) {
3065 NewlyDeducedPacks[I].push_back(DeducedArg);
3066 DeducedArg = DeducedTemplateArgument();
3071 // Build argument packs for each of the parameter packs expanded by this
3073 if (Sema::TemplateDeductionResult Result
3074 = FinishArgumentPackDeduction(*this, TemplateParams, HasAnyArguments,
3075 Deduced, PackIndices, SavedPacks,
3076 NewlyDeducedPacks, Info))
3079 // After we've matching against a parameter pack, we're done.
3083 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
3084 NumExplicitlySpecified,
3085 Specialization, Info, &OriginalCallArgs);
3088 /// \brief Deduce template arguments when taking the address of a function
3089 /// template (C++ [temp.deduct.funcaddr]) or matching a specialization to
3092 /// \param FunctionTemplate the function template for which we are performing
3093 /// template argument deduction.
3095 /// \param ExplicitTemplateArguments the explicitly-specified template
3098 /// \param ArgFunctionType the function type that will be used as the
3099 /// "argument" type (A) when performing template argument deduction from the
3100 /// function template's function type. This type may be NULL, if there is no
3101 /// argument type to compare against, in C++0x [temp.arg.explicit]p3.
3103 /// \param Specialization if template argument deduction was successful,
3104 /// this will be set to the function template specialization produced by
3105 /// template argument deduction.
3107 /// \param Info the argument will be updated to provide additional information
3108 /// about template argument deduction.
3110 /// \returns the result of template argument deduction.
3111 Sema::TemplateDeductionResult
3112 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3113 TemplateArgumentListInfo *ExplicitTemplateArgs,
3114 QualType ArgFunctionType,
3115 FunctionDecl *&Specialization,
3116 TemplateDeductionInfo &Info) {
3117 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3118 TemplateParameterList *TemplateParams
3119 = FunctionTemplate->getTemplateParameters();
3120 QualType FunctionType = Function->getType();
3122 // Substitute any explicit template arguments.
3123 LocalInstantiationScope InstScope(*this);
3124 SmallVector<DeducedTemplateArgument, 4> Deduced;
3125 unsigned NumExplicitlySpecified = 0;
3126 SmallVector<QualType, 4> ParamTypes;
3127 if (ExplicitTemplateArgs) {
3128 if (TemplateDeductionResult Result
3129 = SubstituteExplicitTemplateArguments(FunctionTemplate,
3130 *ExplicitTemplateArgs,
3131 Deduced, ParamTypes,
3132 &FunctionType, Info))
3135 NumExplicitlySpecified = Deduced.size();
3138 // Template argument deduction for function templates in a SFINAE context.
3139 // Trap any errors that might occur.
3140 SFINAETrap Trap(*this);
3142 Deduced.resize(TemplateParams->size());
3144 if (!ArgFunctionType.isNull()) {
3145 // Deduce template arguments from the function type.
3146 if (TemplateDeductionResult Result
3147 = ::DeduceTemplateArguments(*this, TemplateParams,
3148 FunctionType, ArgFunctionType, Info,
3149 Deduced, TDF_TopLevelParameterTypeList))
3153 if (TemplateDeductionResult Result
3154 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
3155 NumExplicitlySpecified,
3156 Specialization, Info))
3159 // If the requested function type does not match the actual type of the
3160 // specialization, template argument deduction fails.
3161 if (!ArgFunctionType.isNull() &&
3162 !Context.hasSameType(ArgFunctionType, Specialization->getType()))
3163 return TDK_NonDeducedMismatch;
3168 /// \brief Deduce template arguments for a templated conversion
3169 /// function (C++ [temp.deduct.conv]) and, if successful, produce a
3170 /// conversion function template specialization.
3171 Sema::TemplateDeductionResult
3172 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3174 CXXConversionDecl *&Specialization,
3175 TemplateDeductionInfo &Info) {
3176 CXXConversionDecl *Conv
3177 = cast<CXXConversionDecl>(FunctionTemplate->getTemplatedDecl());
3178 QualType FromType = Conv->getConversionType();
3180 // Canonicalize the types for deduction.
3181 QualType P = Context.getCanonicalType(FromType);
3182 QualType A = Context.getCanonicalType(ToType);
3184 // C++0x [temp.deduct.conv]p2:
3185 // If P is a reference type, the type referred to by P is used for
3187 if (const ReferenceType *PRef = P->getAs<ReferenceType>())
3188 P = PRef->getPointeeType();
3190 // C++0x [temp.deduct.conv]p4:
3191 // [...] If A is a reference type, the type referred to by A is used
3192 // for type deduction.
3193 if (const ReferenceType *ARef = A->getAs<ReferenceType>())
3194 A = ARef->getPointeeType().getUnqualifiedType();
3195 // C++ [temp.deduct.conv]p3:
3197 // If A is not a reference type:
3199 assert(!A->isReferenceType() && "Reference types were handled above");
3201 // - If P is an array type, the pointer type produced by the
3202 // array-to-pointer standard conversion (4.2) is used in place
3203 // of P for type deduction; otherwise,
3204 if (P->isArrayType())
3205 P = Context.getArrayDecayedType(P);
3206 // - If P is a function type, the pointer type produced by the
3207 // function-to-pointer standard conversion (4.3) is used in
3208 // place of P for type deduction; otherwise,
3209 else if (P->isFunctionType())
3210 P = Context.getPointerType(P);
3211 // - If P is a cv-qualified type, the top level cv-qualifiers of
3212 // P's type are ignored for type deduction.
3214 P = P.getUnqualifiedType();
3216 // C++0x [temp.deduct.conv]p4:
3217 // If A is a cv-qualified type, the top level cv-qualifiers of A's
3218 // type are ignored for type deduction. If A is a reference type, the type
3219 // referred to by A is used for type deduction.
3220 A = A.getUnqualifiedType();
3223 // Template argument deduction for function templates in a SFINAE context.
3224 // Trap any errors that might occur.
3225 SFINAETrap Trap(*this);
3227 // C++ [temp.deduct.conv]p1:
3228 // Template argument deduction is done by comparing the return
3229 // type of the template conversion function (call it P) with the
3230 // type that is required as the result of the conversion (call it
3231 // A) as described in 14.8.2.4.
3232 TemplateParameterList *TemplateParams
3233 = FunctionTemplate->getTemplateParameters();
3234 SmallVector<DeducedTemplateArgument, 4> Deduced;
3235 Deduced.resize(TemplateParams->size());
3237 // C++0x [temp.deduct.conv]p4:
3238 // In general, the deduction process attempts to find template
3239 // argument values that will make the deduced A identical to
3240 // A. However, there are two cases that allow a difference:
3242 // - If the original A is a reference type, A can be more
3243 // cv-qualified than the deduced A (i.e., the type referred to
3244 // by the reference)
3245 if (ToType->isReferenceType())
3246 TDF |= TDF_ParamWithReferenceType;
3247 // - The deduced A can be another pointer or pointer to member
3248 // type that can be converted to A via a qualification
3251 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when
3252 // both P and A are pointers or member pointers. In this case, we
3253 // just ignore cv-qualifiers completely).
3254 if ((P->isPointerType() && A->isPointerType()) ||
3255 (P->isMemberPointerType() && A->isMemberPointerType()))
3256 TDF |= TDF_IgnoreQualifiers;
3257 if (TemplateDeductionResult Result
3258 = ::DeduceTemplateArguments(*this, TemplateParams,
3259 P, A, Info, Deduced, TDF))
3262 // Finish template argument deduction.
3263 LocalInstantiationScope InstScope(*this);
3264 FunctionDecl *Spec = 0;
3265 TemplateDeductionResult Result
3266 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 0, Spec,
3268 Specialization = cast_or_null<CXXConversionDecl>(Spec);
3272 /// \brief Deduce template arguments for a function template when there is
3273 /// nothing to deduce against (C++0x [temp.arg.explicit]p3).
3275 /// \param FunctionTemplate the function template for which we are performing
3276 /// template argument deduction.
3278 /// \param ExplicitTemplateArguments the explicitly-specified template
3281 /// \param Specialization if template argument deduction was successful,
3282 /// this will be set to the function template specialization produced by
3283 /// template argument deduction.
3285 /// \param Info the argument will be updated to provide additional information
3286 /// about template argument deduction.
3288 /// \returns the result of template argument deduction.
3289 Sema::TemplateDeductionResult
3290 Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3291 TemplateArgumentListInfo *ExplicitTemplateArgs,
3292 FunctionDecl *&Specialization,
3293 TemplateDeductionInfo &Info) {
3294 return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs,
3295 QualType(), Specialization, Info);
3299 /// Substitute the 'auto' type specifier within a type for a given replacement
3301 class SubstituteAutoTransform :
3302 public TreeTransform<SubstituteAutoTransform> {
3303 QualType Replacement;
3305 SubstituteAutoTransform(Sema &SemaRef, QualType Replacement) :
3306 TreeTransform<SubstituteAutoTransform>(SemaRef), Replacement(Replacement) {
3308 QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) {
3309 // If we're building the type pattern to deduce against, don't wrap the
3310 // substituted type in an AutoType. Certain template deduction rules
3311 // apply only when a template type parameter appears directly (and not if
3312 // the parameter is found through desugaring). For instance:
3313 // auto &&lref = lvalue;
3314 // must transform into "rvalue reference to T" not "rvalue reference to
3315 // auto type deduced as T" in order for [temp.deduct.call]p3 to apply.
3316 if (isa<TemplateTypeParmType>(Replacement)) {
3317 QualType Result = Replacement;
3318 TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
3319 NewTL.setNameLoc(TL.getNameLoc());
3322 QualType Result = RebuildAutoType(Replacement);
3323 AutoTypeLoc NewTL = TLB.push<AutoTypeLoc>(Result);
3324 NewTL.setNameLoc(TL.getNameLoc());
3331 /// \brief Deduce the type for an auto type-specifier (C++0x [dcl.spec.auto]p6)
3333 /// \param Type the type pattern using the auto type-specifier.
3335 /// \param Init the initializer for the variable whose type is to be deduced.
3337 /// \param Result if type deduction was successful, this will be set to the
3338 /// deduced type. This may still contain undeduced autos if the type is
3339 /// dependent. This will be set to null if deduction succeeded, but auto
3340 /// substitution failed; the appropriate diagnostic will already have been
3341 /// produced in that case.
3343 /// \returns true if deduction succeeded, false if it failed.
3345 Sema::DeduceAutoType(TypeSourceInfo *Type, Expr *Init,
3346 TypeSourceInfo *&Result) {
3347 if (Init->isTypeDependent()) {
3352 SourceLocation Loc = Init->getExprLoc();
3354 LocalInstantiationScope InstScope(*this);
3356 // Build template<class TemplParam> void Func(FuncParam);
3357 TemplateTypeParmDecl *TemplParam =
3358 TemplateTypeParmDecl::Create(Context, 0, SourceLocation(), Loc, 0, 0, 0,
3360 QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0);
3361 NamedDecl *TemplParamPtr = TemplParam;
3362 FixedSizeTemplateParameterList<1> TemplateParams(Loc, Loc, &TemplParamPtr,
3365 TypeSourceInfo *FuncParamInfo =
3366 SubstituteAutoTransform(*this, TemplArg).TransformType(Type);
3367 assert(FuncParamInfo && "substituting template parameter for 'auto' failed");
3368 QualType FuncParam = FuncParamInfo->getType();
3370 // Deduce type of TemplParam in Func(Init)
3371 SmallVector<DeducedTemplateArgument, 1> Deduced;
3373 QualType InitType = Init->getType();
3375 if (AdjustFunctionParmAndArgTypesForDeduction(*this, &TemplateParams,
3376 FuncParam, InitType, Init,
3380 TemplateDeductionInfo Info(Context, Loc);
3381 if (::DeduceTemplateArguments(*this, &TemplateParams,
3382 FuncParam, InitType, Info, Deduced,
3386 QualType DeducedType = Deduced[0].getAsType();
3387 if (DeducedType.isNull())
3390 Result = SubstituteAutoTransform(*this, DeducedType).TransformType(Type);
3392 // Check that the deduced argument type is compatible with the original
3393 // argument type per C++ [temp.deduct.call]p4.
3395 CheckOriginalCallArgDeduction(*this,
3396 Sema::OriginalCallArg(FuncParam,0,InitType),
3397 Result->getType())) {
3406 MarkUsedTemplateParameters(Sema &SemaRef, QualType T,
3409 SmallVectorImpl<bool> &Deduced);
3411 /// \brief If this is a non-static member function,
3412 static void MaybeAddImplicitObjectParameterType(ASTContext &Context,
3413 CXXMethodDecl *Method,
3414 SmallVectorImpl<QualType> &ArgTypes) {
3415 if (Method->isStatic())
3418 // C++ [over.match.funcs]p4:
3420 // For non-static member functions, the type of the implicit
3421 // object parameter is
3422 // - "lvalue reference to cv X" for functions declared without a
3423 // ref-qualifier or with the & ref-qualifier
3424 // - "rvalue reference to cv X" for functions declared with the
3427 // FIXME: We don't have ref-qualifiers yet, so we don't do that part.
3428 QualType ArgTy = Context.getTypeDeclType(Method->getParent());
3429 ArgTy = Context.getQualifiedType(ArgTy,
3430 Qualifiers::fromCVRMask(Method->getTypeQualifiers()));
3431 ArgTy = Context.getLValueReferenceType(ArgTy);
3432 ArgTypes.push_back(ArgTy);
3435 /// \brief Determine whether the function template \p FT1 is at least as
3436 /// specialized as \p FT2.
3437 static bool isAtLeastAsSpecializedAs(Sema &S,
3439 FunctionTemplateDecl *FT1,
3440 FunctionTemplateDecl *FT2,
3441 TemplatePartialOrderingContext TPOC,
3442 unsigned NumCallArguments,
3443 SmallVectorImpl<RefParamPartialOrderingComparison> *RefParamComparisons) {
3444 FunctionDecl *FD1 = FT1->getTemplatedDecl();
3445 FunctionDecl *FD2 = FT2->getTemplatedDecl();
3446 const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>();
3447 const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>();
3449 assert(Proto1 && Proto2 && "Function templates must have prototypes");
3450 TemplateParameterList *TemplateParams = FT2->getTemplateParameters();
3451 SmallVector<DeducedTemplateArgument, 4> Deduced;
3452 Deduced.resize(TemplateParams->size());
3454 // C++0x [temp.deduct.partial]p3:
3455 // The types used to determine the ordering depend on the context in which
3456 // the partial ordering is done:
3457 TemplateDeductionInfo Info(S.Context, Loc);
3458 CXXMethodDecl *Method1 = 0;
3459 CXXMethodDecl *Method2 = 0;
3460 bool IsNonStatic2 = false;
3461 bool IsNonStatic1 = false;
3465 // - In the context of a function call, the function parameter types are
3467 Method1 = dyn_cast<CXXMethodDecl>(FD1);
3468 Method2 = dyn_cast<CXXMethodDecl>(FD2);
3469 IsNonStatic1 = Method1 && !Method1->isStatic();
3470 IsNonStatic2 = Method2 && !Method2->isStatic();
3472 // C++0x [temp.func.order]p3:
3473 // [...] If only one of the function templates is a non-static
3474 // member, that function template is considered to have a new
3475 // first parameter inserted in its function parameter list. The
3476 // new parameter is of type "reference to cv A," where cv are
3477 // the cv-qualifiers of the function template (if any) and A is
3478 // the class of which the function template is a member.
3480 // C++98/03 doesn't have this provision, so instead we drop the
3481 // first argument of the free function or static member, which
3482 // seems to match existing practice.
3483 SmallVector<QualType, 4> Args1;
3484 unsigned Skip1 = !S.getLangOptions().CPlusPlus0x &&
3485 IsNonStatic2 && !IsNonStatic1;
3486 if (S.getLangOptions().CPlusPlus0x && IsNonStatic1 && !IsNonStatic2)
3487 MaybeAddImplicitObjectParameterType(S.Context, Method1, Args1);
3488 Args1.insert(Args1.end(),
3489 Proto1->arg_type_begin() + Skip1, Proto1->arg_type_end());
3491 SmallVector<QualType, 4> Args2;
3492 Skip2 = !S.getLangOptions().CPlusPlus0x &&
3493 IsNonStatic1 && !IsNonStatic2;
3494 if (S.getLangOptions().CPlusPlus0x && IsNonStatic2 && !IsNonStatic1)
3495 MaybeAddImplicitObjectParameterType(S.Context, Method2, Args2);
3496 Args2.insert(Args2.end(),
3497 Proto2->arg_type_begin() + Skip2, Proto2->arg_type_end());
3499 // C++ [temp.func.order]p5:
3500 // The presence of unused ellipsis and default arguments has no effect on
3501 // the partial ordering of function templates.
3502 if (Args1.size() > NumCallArguments)
3503 Args1.resize(NumCallArguments);
3504 if (Args2.size() > NumCallArguments)
3505 Args2.resize(NumCallArguments);
3506 if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(),
3507 Args1.data(), Args1.size(), Info, Deduced,
3508 TDF_None, /*PartialOrdering=*/true,
3509 RefParamComparisons))
3515 case TPOC_Conversion:
3516 // - In the context of a call to a conversion operator, the return types
3517 // of the conversion function templates are used.
3518 if (DeduceTemplateArguments(S, TemplateParams, Proto2->getResultType(),
3519 Proto1->getResultType(), Info, Deduced,
3520 TDF_None, /*PartialOrdering=*/true,
3521 RefParamComparisons))
3526 // - In other contexts (14.6.6.2) the function template's function type
3528 if (DeduceTemplateArguments(S, TemplateParams, FD2->getType(),
3529 FD1->getType(), Info, Deduced, TDF_None,
3530 /*PartialOrdering=*/true, RefParamComparisons))
3535 // C++0x [temp.deduct.partial]p11:
3536 // In most cases, all template parameters must have values in order for
3537 // deduction to succeed, but for partial ordering purposes a template
3538 // parameter may remain without a value provided it is not used in the
3539 // types being used for partial ordering. [ Note: a template parameter used
3540 // in a non-deduced context is considered used. -end note]
3541 unsigned ArgIdx = 0, NumArgs = Deduced.size();
3542 for (; ArgIdx != NumArgs; ++ArgIdx)
3543 if (Deduced[ArgIdx].isNull())
3546 if (ArgIdx == NumArgs) {
3547 // All template arguments were deduced. FT1 is at least as specialized
3552 // Figure out which template parameters were used.
3553 SmallVector<bool, 4> UsedParameters;
3554 UsedParameters.resize(TemplateParams->size());
3557 unsigned NumParams = std::min(NumCallArguments,
3558 std::min(Proto1->getNumArgs(),
3559 Proto2->getNumArgs()));
3560 if (S.getLangOptions().CPlusPlus0x && IsNonStatic2 && !IsNonStatic1)
3561 ::MarkUsedTemplateParameters(S, Method2->getThisType(S.Context), false,
3562 TemplateParams->getDepth(), UsedParameters);
3563 for (unsigned I = Skip2; I < NumParams; ++I)
3564 ::MarkUsedTemplateParameters(S, Proto2->getArgType(I), false,
3565 TemplateParams->getDepth(),
3570 case TPOC_Conversion:
3571 ::MarkUsedTemplateParameters(S, Proto2->getResultType(), false,
3572 TemplateParams->getDepth(),
3577 ::MarkUsedTemplateParameters(S, FD2->getType(), false,
3578 TemplateParams->getDepth(),
3583 for (; ArgIdx != NumArgs; ++ArgIdx)
3584 // If this argument had no value deduced but was used in one of the types
3585 // used for partial ordering, then deduction fails.
3586 if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx])
3592 /// \brief Determine whether this a function template whose parameter-type-list
3593 /// ends with a function parameter pack.
3594 static bool isVariadicFunctionTemplate(FunctionTemplateDecl *FunTmpl) {
3595 FunctionDecl *Function = FunTmpl->getTemplatedDecl();
3596 unsigned NumParams = Function->getNumParams();
3600 ParmVarDecl *Last = Function->getParamDecl(NumParams - 1);
3601 if (!Last->isParameterPack())
3604 // Make sure that no previous parameter is a parameter pack.
3605 while (--NumParams > 0) {
3606 if (Function->getParamDecl(NumParams - 1)->isParameterPack())
3613 /// \brief Returns the more specialized function template according
3614 /// to the rules of function template partial ordering (C++ [temp.func.order]).
3616 /// \param FT1 the first function template
3618 /// \param FT2 the second function template
3620 /// \param TPOC the context in which we are performing partial ordering of
3621 /// function templates.
3623 /// \param NumCallArguments The number of arguments in a call, used only
3624 /// when \c TPOC is \c TPOC_Call.
3626 /// \returns the more specialized function template. If neither
3627 /// template is more specialized, returns NULL.
3628 FunctionTemplateDecl *
3629 Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1,
3630 FunctionTemplateDecl *FT2,
3632 TemplatePartialOrderingContext TPOC,
3633 unsigned NumCallArguments) {
3634 SmallVector<RefParamPartialOrderingComparison, 4> RefParamComparisons;
3635 bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC,
3636 NumCallArguments, 0);
3637 bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC,
3639 &RefParamComparisons);
3641 if (Better1 != Better2) // We have a clear winner
3642 return Better1? FT1 : FT2;
3644 if (!Better1 && !Better2) // Neither is better than the other
3647 // C++0x [temp.deduct.partial]p10:
3648 // If for each type being considered a given template is at least as
3649 // specialized for all types and more specialized for some set of types and
3650 // the other template is not more specialized for any types or is not at
3651 // least as specialized for any types, then the given template is more
3652 // specialized than the other template. Otherwise, neither template is more
3653 // specialized than the other.
3656 for (unsigned I = 0, N = RefParamComparisons.size(); I != N; ++I) {
3657 // C++0x [temp.deduct.partial]p9:
3658 // If, for a given type, deduction succeeds in both directions (i.e., the
3659 // types are identical after the transformations above) and both P and A
3660 // were reference types (before being replaced with the type referred to
3663 // -- if the type from the argument template was an lvalue reference
3664 // and the type from the parameter template was not, the argument
3665 // type is considered to be more specialized than the other;
3667 if (!RefParamComparisons[I].ArgIsRvalueRef &&
3668 RefParamComparisons[I].ParamIsRvalueRef) {
3673 } else if (!RefParamComparisons[I].ParamIsRvalueRef &&
3674 RefParamComparisons[I].ArgIsRvalueRef) {
3681 // -- if the type from the argument template is more cv-qualified than
3682 // the type from the parameter template (as described above), the
3683 // argument type is considered to be more specialized than the
3684 // other; otherwise,
3685 switch (RefParamComparisons[I].Qualifiers) {
3686 case NeitherMoreQualified:
3689 case ParamMoreQualified:
3695 case ArgMoreQualified:
3702 // -- neither type is more specialized than the other.
3705 assert(!(Better1 && Better2) && "Should have broken out in the loop above");
3711 // FIXME: This mimics what GCC implements, but doesn't match up with the
3712 // proposed resolution for core issue 692. This area needs to be sorted out,
3713 // but for now we attempt to maintain compatibility.
3714 bool Variadic1 = isVariadicFunctionTemplate(FT1);
3715 bool Variadic2 = isVariadicFunctionTemplate(FT2);
3716 if (Variadic1 != Variadic2)
3717 return Variadic1? FT2 : FT1;
3722 /// \brief Determine if the two templates are equivalent.
3723 static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) {
3730 return T1->getCanonicalDecl() == T2->getCanonicalDecl();
3733 /// \brief Retrieve the most specialized of the given function template
3734 /// specializations.
3736 /// \param SpecBegin the start iterator of the function template
3737 /// specializations that we will be comparing.
3739 /// \param SpecEnd the end iterator of the function template
3740 /// specializations, paired with \p SpecBegin.
3742 /// \param TPOC the partial ordering context to use to compare the function
3743 /// template specializations.
3745 /// \param NumCallArguments The number of arguments in a call, used only
3746 /// when \c TPOC is \c TPOC_Call.
3748 /// \param Loc the location where the ambiguity or no-specializations
3749 /// diagnostic should occur.
3751 /// \param NoneDiag partial diagnostic used to diagnose cases where there are
3752 /// no matching candidates.
3754 /// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one
3757 /// \param CandidateDiag partial diagnostic used for each function template
3758 /// specialization that is a candidate in the ambiguous ordering. One parameter
3759 /// in this diagnostic should be unbound, which will correspond to the string
3760 /// describing the template arguments for the function template specialization.
3762 /// \param Index if non-NULL and the result of this function is non-nULL,
3763 /// receives the index corresponding to the resulting function template
3766 /// \returns the most specialized function template specialization, if
3767 /// found. Otherwise, returns SpecEnd.
3769 /// \todo FIXME: Consider passing in the "also-ran" candidates that failed
3770 /// template argument deduction.
3771 UnresolvedSetIterator
3772 Sema::getMostSpecialized(UnresolvedSetIterator SpecBegin,
3773 UnresolvedSetIterator SpecEnd,
3774 TemplatePartialOrderingContext TPOC,
3775 unsigned NumCallArguments,
3777 const PartialDiagnostic &NoneDiag,
3778 const PartialDiagnostic &AmbigDiag,
3779 const PartialDiagnostic &CandidateDiag,
3781 if (SpecBegin == SpecEnd) {
3783 Diag(Loc, NoneDiag);
3787 if (SpecBegin + 1 == SpecEnd)
3790 // Find the function template that is better than all of the templates it
3791 // has been compared to.
3792 UnresolvedSetIterator Best = SpecBegin;
3793 FunctionTemplateDecl *BestTemplate
3794 = cast<FunctionDecl>(*Best)->getPrimaryTemplate();
3795 assert(BestTemplate && "Not a function template specialization?");
3796 for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) {
3797 FunctionTemplateDecl *Challenger
3798 = cast<FunctionDecl>(*I)->getPrimaryTemplate();
3799 assert(Challenger && "Not a function template specialization?");
3800 if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
3801 Loc, TPOC, NumCallArguments),
3804 BestTemplate = Challenger;
3808 // Make sure that the "best" function template is more specialized than all
3810 bool Ambiguous = false;
3811 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
3812 FunctionTemplateDecl *Challenger
3813 = cast<FunctionDecl>(*I)->getPrimaryTemplate();
3815 !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
3816 Loc, TPOC, NumCallArguments),
3824 // We found an answer. Return it.
3828 // Diagnose the ambiguity.
3830 Diag(Loc, AmbigDiag);
3833 // FIXME: Can we order the candidates in some sane way?
3834 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I)
3835 Diag((*I)->getLocation(), CandidateDiag)
3836 << getTemplateArgumentBindingsText(
3837 cast<FunctionDecl>(*I)->getPrimaryTemplate()->getTemplateParameters(),
3838 *cast<FunctionDecl>(*I)->getTemplateSpecializationArgs());
3843 /// \brief Returns the more specialized class template partial specialization
3844 /// according to the rules of partial ordering of class template partial
3845 /// specializations (C++ [temp.class.order]).
3847 /// \param PS1 the first class template partial specialization
3849 /// \param PS2 the second class template partial specialization
3851 /// \returns the more specialized class template partial specialization. If
3852 /// neither partial specialization is more specialized, returns NULL.
3853 ClassTemplatePartialSpecializationDecl *
3854 Sema::getMoreSpecializedPartialSpecialization(
3855 ClassTemplatePartialSpecializationDecl *PS1,
3856 ClassTemplatePartialSpecializationDecl *PS2,
3857 SourceLocation Loc) {
3858 // C++ [temp.class.order]p1:
3859 // For two class template partial specializations, the first is at least as
3860 // specialized as the second if, given the following rewrite to two
3861 // function templates, the first function template is at least as
3862 // specialized as the second according to the ordering rules for function
3863 // templates (14.6.6.2):
3864 // - the first function template has the same template parameters as the
3865 // first partial specialization and has a single function parameter
3866 // whose type is a class template specialization with the template
3867 // arguments of the first partial specialization, and
3868 // - the second function template has the same template parameters as the
3869 // second partial specialization and has a single function parameter
3870 // whose type is a class template specialization with the template
3871 // arguments of the second partial specialization.
3873 // Rather than synthesize function templates, we merely perform the
3874 // equivalent partial ordering by performing deduction directly on
3875 // the template arguments of the class template partial
3876 // specializations. This computation is slightly simpler than the
3877 // general problem of function template partial ordering, because
3878 // class template partial specializations are more constrained. We
3879 // know that every template parameter is deducible from the class
3880 // template partial specialization's template arguments, for
3882 SmallVector<DeducedTemplateArgument, 4> Deduced;
3883 TemplateDeductionInfo Info(Context, Loc);
3885 QualType PT1 = PS1->getInjectedSpecializationType();
3886 QualType PT2 = PS2->getInjectedSpecializationType();
3888 // Determine whether PS1 is at least as specialized as PS2
3889 Deduced.resize(PS2->getTemplateParameters()->size());
3890 bool Better1 = !::DeduceTemplateArguments(*this, PS2->getTemplateParameters(),
3891 PT2, PT1, Info, Deduced, TDF_None,
3892 /*PartialOrdering=*/true,
3893 /*RefParamComparisons=*/0);
3895 InstantiatingTemplate Inst(*this, PS2->getLocation(), PS2,
3896 Deduced.data(), Deduced.size(), Info);
3897 Better1 = !::FinishTemplateArgumentDeduction(*this, PS2,
3898 PS1->getTemplateArgs(),
3902 // Determine whether PS2 is at least as specialized as PS1
3904 Deduced.resize(PS1->getTemplateParameters()->size());
3905 bool Better2 = !::DeduceTemplateArguments(*this, PS1->getTemplateParameters(),
3906 PT1, PT2, Info, Deduced, TDF_None,
3907 /*PartialOrdering=*/true,
3908 /*RefParamComparisons=*/0);
3910 InstantiatingTemplate Inst(*this, PS1->getLocation(), PS1,
3911 Deduced.data(), Deduced.size(), Info);
3912 Better2 = !::FinishTemplateArgumentDeduction(*this, PS1,
3913 PS2->getTemplateArgs(),
3917 if (Better1 == Better2)
3920 return Better1? PS1 : PS2;
3924 MarkUsedTemplateParameters(Sema &SemaRef,
3925 const TemplateArgument &TemplateArg,
3928 SmallVectorImpl<bool> &Used);
3930 /// \brief Mark the template parameters that are used by the given
3933 MarkUsedTemplateParameters(Sema &SemaRef,
3937 SmallVectorImpl<bool> &Used) {
3938 // We can deduce from a pack expansion.
3939 if (const PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(E))
3940 E = Expansion->getPattern();
3942 // Skip through any implicit casts we added while type-checking.
3943 while (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E))
3944 E = ICE->getSubExpr();
3946 // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to
3947 // find other occurrences of template parameters.
3948 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E);
3952 const NonTypeTemplateParmDecl *NTTP
3953 = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
3957 if (NTTP->getDepth() == Depth)
3958 Used[NTTP->getIndex()] = true;
3961 /// \brief Mark the template parameters that are used by the given
3962 /// nested name specifier.
3964 MarkUsedTemplateParameters(Sema &SemaRef,
3965 NestedNameSpecifier *NNS,
3968 SmallVectorImpl<bool> &Used) {
3972 MarkUsedTemplateParameters(SemaRef, NNS->getPrefix(), OnlyDeduced, Depth,
3974 MarkUsedTemplateParameters(SemaRef, QualType(NNS->getAsType(), 0),
3975 OnlyDeduced, Depth, Used);
3978 /// \brief Mark the template parameters that are used by the given
3981 MarkUsedTemplateParameters(Sema &SemaRef,
3985 SmallVectorImpl<bool> &Used) {
3986 if (TemplateDecl *Template = Name.getAsTemplateDecl()) {
3987 if (TemplateTemplateParmDecl *TTP
3988 = dyn_cast<TemplateTemplateParmDecl>(Template)) {
3989 if (TTP->getDepth() == Depth)
3990 Used[TTP->getIndex()] = true;
3995 if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName())
3996 MarkUsedTemplateParameters(SemaRef, QTN->getQualifier(), OnlyDeduced,
3998 if (DependentTemplateName *DTN = Name.getAsDependentTemplateName())
3999 MarkUsedTemplateParameters(SemaRef, DTN->getQualifier(), OnlyDeduced,
4003 /// \brief Mark the template parameters that are used by the given
4006 MarkUsedTemplateParameters(Sema &SemaRef, QualType T,
4009 SmallVectorImpl<bool> &Used) {
4013 // Non-dependent types have nothing deducible
4014 if (!T->isDependentType())
4017 T = SemaRef.Context.getCanonicalType(T);
4018 switch (T->getTypeClass()) {
4020 MarkUsedTemplateParameters(SemaRef,
4021 cast<PointerType>(T)->getPointeeType(),
4027 case Type::BlockPointer:
4028 MarkUsedTemplateParameters(SemaRef,
4029 cast<BlockPointerType>(T)->getPointeeType(),
4035 case Type::LValueReference:
4036 case Type::RValueReference:
4037 MarkUsedTemplateParameters(SemaRef,
4038 cast<ReferenceType>(T)->getPointeeType(),
4044 case Type::MemberPointer: {
4045 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr());
4046 MarkUsedTemplateParameters(SemaRef, MemPtr->getPointeeType(), OnlyDeduced,
4048 MarkUsedTemplateParameters(SemaRef, QualType(MemPtr->getClass(), 0),
4049 OnlyDeduced, Depth, Used);
4053 case Type::DependentSizedArray:
4054 MarkUsedTemplateParameters(SemaRef,
4055 cast<DependentSizedArrayType>(T)->getSizeExpr(),
4056 OnlyDeduced, Depth, Used);
4057 // Fall through to check the element type
4059 case Type::ConstantArray:
4060 case Type::IncompleteArray:
4061 MarkUsedTemplateParameters(SemaRef,
4062 cast<ArrayType>(T)->getElementType(),
4063 OnlyDeduced, Depth, Used);
4067 case Type::ExtVector:
4068 MarkUsedTemplateParameters(SemaRef,
4069 cast<VectorType>(T)->getElementType(),
4070 OnlyDeduced, Depth, Used);
4073 case Type::DependentSizedExtVector: {
4074 const DependentSizedExtVectorType *VecType
4075 = cast<DependentSizedExtVectorType>(T);
4076 MarkUsedTemplateParameters(SemaRef, VecType->getElementType(), OnlyDeduced,
4078 MarkUsedTemplateParameters(SemaRef, VecType->getSizeExpr(), OnlyDeduced,
4083 case Type::FunctionProto: {
4084 const FunctionProtoType *Proto = cast<FunctionProtoType>(T);
4085 MarkUsedTemplateParameters(SemaRef, Proto->getResultType(), OnlyDeduced,
4087 for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I)
4088 MarkUsedTemplateParameters(SemaRef, Proto->getArgType(I), OnlyDeduced,
4093 case Type::TemplateTypeParm: {
4094 const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T);
4095 if (TTP->getDepth() == Depth)
4096 Used[TTP->getIndex()] = true;
4100 case Type::SubstTemplateTypeParmPack: {
4101 const SubstTemplateTypeParmPackType *Subst
4102 = cast<SubstTemplateTypeParmPackType>(T);
4103 MarkUsedTemplateParameters(SemaRef,
4104 QualType(Subst->getReplacedParameter(), 0),
4105 OnlyDeduced, Depth, Used);
4106 MarkUsedTemplateParameters(SemaRef, Subst->getArgumentPack(),
4107 OnlyDeduced, Depth, Used);
4111 case Type::InjectedClassName:
4112 T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType();
4115 case Type::TemplateSpecialization: {
4116 const TemplateSpecializationType *Spec
4117 = cast<TemplateSpecializationType>(T);
4118 MarkUsedTemplateParameters(SemaRef, Spec->getTemplateName(), OnlyDeduced,
4121 // C++0x [temp.deduct.type]p9:
4122 // If the template argument list of P contains a pack expansion that is not
4123 // the last template argument, the entire template argument list is a
4124 // non-deduced context.
4126 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs()))
4129 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
4130 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth,
4137 MarkUsedTemplateParameters(SemaRef,
4138 cast<ComplexType>(T)->getElementType(),
4139 OnlyDeduced, Depth, Used);
4144 MarkUsedTemplateParameters(SemaRef,
4145 cast<AtomicType>(T)->getValueType(),
4146 OnlyDeduced, Depth, Used);
4149 case Type::DependentName:
4151 MarkUsedTemplateParameters(SemaRef,
4152 cast<DependentNameType>(T)->getQualifier(),
4153 OnlyDeduced, Depth, Used);
4156 case Type::DependentTemplateSpecialization: {
4157 const DependentTemplateSpecializationType *Spec
4158 = cast<DependentTemplateSpecializationType>(T);
4160 MarkUsedTemplateParameters(SemaRef, Spec->getQualifier(),
4161 OnlyDeduced, Depth, Used);
4163 // C++0x [temp.deduct.type]p9:
4164 // If the template argument list of P contains a pack expansion that is not
4165 // the last template argument, the entire template argument list is a
4166 // non-deduced context.
4168 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs()))
4171 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
4172 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth,
4179 MarkUsedTemplateParameters(SemaRef,
4180 cast<TypeOfType>(T)->getUnderlyingType(),
4181 OnlyDeduced, Depth, Used);
4184 case Type::TypeOfExpr:
4186 MarkUsedTemplateParameters(SemaRef,
4187 cast<TypeOfExprType>(T)->getUnderlyingExpr(),
4188 OnlyDeduced, Depth, Used);
4191 case Type::Decltype:
4193 MarkUsedTemplateParameters(SemaRef,
4194 cast<DecltypeType>(T)->getUnderlyingExpr(),
4195 OnlyDeduced, Depth, Used);
4198 case Type::UnaryTransform:
4200 MarkUsedTemplateParameters(SemaRef,
4201 cast<UnaryTransformType>(T)->getUnderlyingType(),
4202 OnlyDeduced, Depth, Used);
4205 case Type::PackExpansion:
4206 MarkUsedTemplateParameters(SemaRef,
4207 cast<PackExpansionType>(T)->getPattern(),
4208 OnlyDeduced, Depth, Used);
4212 MarkUsedTemplateParameters(SemaRef,
4213 cast<AutoType>(T)->getDeducedType(),
4214 OnlyDeduced, Depth, Used);
4216 // None of these types have any template parameters in them.
4218 case Type::VariableArray:
4219 case Type::FunctionNoProto:
4222 case Type::ObjCInterface:
4223 case Type::ObjCObject:
4224 case Type::ObjCObjectPointer:
4225 case Type::UnresolvedUsing:
4226 #define TYPE(Class, Base)
4227 #define ABSTRACT_TYPE(Class, Base)
4228 #define DEPENDENT_TYPE(Class, Base)
4229 #define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
4230 #include "clang/AST/TypeNodes.def"
4235 /// \brief Mark the template parameters that are used by this
4236 /// template argument.
4238 MarkUsedTemplateParameters(Sema &SemaRef,
4239 const TemplateArgument &TemplateArg,
4242 SmallVectorImpl<bool> &Used) {
4243 switch (TemplateArg.getKind()) {
4244 case TemplateArgument::Null:
4245 case TemplateArgument::Integral:
4246 case TemplateArgument::Declaration:
4249 case TemplateArgument::Type:
4250 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsType(), OnlyDeduced,
4254 case TemplateArgument::Template:
4255 case TemplateArgument::TemplateExpansion:
4256 MarkUsedTemplateParameters(SemaRef,
4257 TemplateArg.getAsTemplateOrTemplatePattern(),
4258 OnlyDeduced, Depth, Used);
4261 case TemplateArgument::Expression:
4262 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsExpr(), OnlyDeduced,
4266 case TemplateArgument::Pack:
4267 for (TemplateArgument::pack_iterator P = TemplateArg.pack_begin(),
4268 PEnd = TemplateArg.pack_end();
4270 MarkUsedTemplateParameters(SemaRef, *P, OnlyDeduced, Depth, Used);
4275 /// \brief Mark the template parameters can be deduced by the given
4276 /// template argument list.
4278 /// \param TemplateArgs the template argument list from which template
4279 /// parameters will be deduced.
4281 /// \param Deduced a bit vector whose elements will be set to \c true
4282 /// to indicate when the corresponding template parameter will be
4285 Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs,
4286 bool OnlyDeduced, unsigned Depth,
4287 SmallVectorImpl<bool> &Used) {
4288 // C++0x [temp.deduct.type]p9:
4289 // If the template argument list of P contains a pack expansion that is not
4290 // the last template argument, the entire template argument list is a
4291 // non-deduced context.
4293 hasPackExpansionBeforeEnd(TemplateArgs.data(), TemplateArgs.size()))
4296 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I)
4297 ::MarkUsedTemplateParameters(*this, TemplateArgs[I], OnlyDeduced,
4301 /// \brief Marks all of the template parameters that will be deduced by a
4302 /// call to the given function template.
4304 Sema::MarkDeducedTemplateParameters(FunctionTemplateDecl *FunctionTemplate,
4305 SmallVectorImpl<bool> &Deduced) {
4306 TemplateParameterList *TemplateParams
4307 = FunctionTemplate->getTemplateParameters();
4309 Deduced.resize(TemplateParams->size());
4311 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
4312 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I)
4313 ::MarkUsedTemplateParameters(*this, Function->getParamDecl(I)->getType(),
4314 true, TemplateParams->getDepth(), Deduced);
4317 bool hasDeducibleTemplateParameters(Sema &S,
4318 FunctionTemplateDecl *FunctionTemplate,
4320 if (!T->isDependentType())
4323 TemplateParameterList *TemplateParams
4324 = FunctionTemplate->getTemplateParameters();
4325 SmallVector<bool, 4> Deduced;
4326 Deduced.resize(TemplateParams->size());
4327 ::MarkUsedTemplateParameters(S, T, true, TemplateParams->getDepth(),
4330 for (unsigned I = 0, N = Deduced.size(); I != N; ++I)